2 * Copyright (C) 2014, United States Government, as represented by the
3 * Administrator of the National Aeronautics and Space Administration.
6 * The Java Pathfinder core (jpf-core) platform is licensed under the
7 * Apache License, Version 2.0 (the "License"); you may not use this file except
8 * in compliance with the License. You may obtain a copy of the License at
10 * http://www.apache.org/licenses/LICENSE-2.0.
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
19 package gov.nasa.jpf.util;
21 import java.io.PrintStream;
22 import java.util.Iterator;
23 import java.util.NoSuchElementException;
26 * Persistent (immutable) associative array that maps integer keys to generic reference values.
28 * PSIntMap is implemented as a bitwise trie which processes key bits in msb order
29 * (from left to right) and has the same depth along all paths (i.e. values are only kept at the
30 * terminal node level, which corresponds to the rightmost bit block in the key).
32 * This particular implementation was chosen to optimize performance for dense key value domains,
33 * e.g. keys that are computed from counters. More specifically, PSIntMap was designed to be a
34 * suitable basis for JPF Heap implementations with their characteristic usage pattern:
36 * transition{ ..alloc( n),..alloc(n+1),..alloc(n+2), ..}, garbage-collection{ remove(x),remove(y),..}
39 * The 32bit keys are broken up into 5bit blocks that represent the trie levels, each 5bit block
40 * (0..31) being the index for the respective child node or value.
41 * For instance, a key/value pair of 12345->'x' is stored as
43 * level: 6 5 4 3 2 1 0
44 * key: 00.00000.00000.00000.01100.00001.11001 = 12345
45 * block-val: 0 0 0 0 12 1 25
47 * Node0 (level 2 : nodes)
49 * [12] -> Node1 (level 1 : nodes)
51 * [1] -> Node2 (level 0 : values)
55 * The main benefit of using this representation is that existing maps are never modified (are
56 * persistent) and hence a previous state can be restored by simply keeping the reference of
57 * the respective map. The main drawback is that not only the changed value has to be stored
58 * upon add/remove, but everything from the node that contains this value up to the root node.
60 * This implementation partitions keys from left (msb) to right, which has the major property that
61 * consecutive keys are stored in the same node, which in turn allows for efficient caching of
62 * the last modified node. Keeping track of this 'stagingNode' avoids copying anything
63 * but the affected node until the next staging node miss, at which point the old stagingNode
64 * has to be merged. This merge only requires copying of old stagingNode parents up to the
65 * level that already has been copied due to the new key insertion that caused the stagingNode miss).
67 * The internal trie representation uses a protected Node type, which uses the bit block values (0..31)
68 * as index into an array that stores either child node references (in case this is not a
69 * terminal block), or value objects (if this is the terminal level). There are three Node
70 * subtypes that get promoted upon population in the following order:
72 * <li>OneNode - store only a single value/child element. Every node starts as a OneNode
73 * <li>BitmapNode - stores up to 31 elements (compressed)
74 * <li>FullNode - stores 32 elements
76 * Removal of keys leads to symmetric demotion of node types.
78 * The five major public operations for PersistentIntMaps are
81 * <li>set(int key, V value) -> PersistentIntMap : return a new map with an additional value
82 * <li>get(int key) -> V : retrieve value
83 * <li>remove(int key) -> PersistentIntMap : return a new map without the specified key/value
84 * <li>removeAllSatisfying(Predicate<V> predicate) -> PersistentIntMap : return a new map
85 * without all values satisfying the specified predicate
86 * <li>process(Processor<V> processor) : iterate over all values with specified processor
89 * Being a persistent data structure, the main property of PersistentIntMaps is that all
90 * add/remove operations (set,remove,removeAllSatisfying) have to return new PersistenIntMap
91 * instances, no destructive update is allowed. Normal usage patterns therefore look like this:
94 * PSIntMap<String> map = PSIntMap<String>();
96 * map = map.set(42, "fortytwo"); // returns a new map
98 * map = map.remove(42); // returns a new map
100 * map = map.removeAllSatisfying( new Predicate<String>(){ // returns a new map
101 * public boolean isTrue (String val){
102 * return val.endsWith("two");
105 * map.process( new Processor<String>(){
106 * public void process (String val){
107 * System.out.println(val);
109 * </pre></blockquote>
111 * NOTE: bitwise tries are inherently recursive data structures, which would naturally lend
112 * itself to implementations using recursive methods (over nodes). However, the recursion
113 * is always bounded (finite number of key bits), and we need to keep track of the terminal
114 * (value) node that was modified, which means we would have to return two values from
115 * every recursion level (new current level node and new (terminal) stagingNode), thus
116 * requiring additional allocation per map operation ( e.g. 'result' object to keep track
117 * of transient state, as in "node = node.assoc(..key, value, result)") or per recursive call
118 * ( result: {node,stagingNode}, as in "result = node.assoc( ..key, value)"). The first solution
119 * would allow to create/store a result object on the caller site, but this could compromise
120 * map consistency in case of concurrent map operations. Both solutions are counter-productive
121 * in a sense that PSIntMap is optimized to minimize allocation count, which is the crux of
122 * persistent data structures.
124 * The approach that is taken here is to manually unroll the recursion by means of explicit
125 * operand stacks, which leads to methods with large number of local variables (to avoid
126 * array allocation) and large switch statements to set respective fields. The resulting
127 * programming style should only be acceptable for critical runtime optimizations.
130 public class PSIntMap <V> implements Iterable<V> {
132 //--- auxiliary types
135 * Abstract root class for all node types. This type needs to be internal, no instances
136 * are allowed to be visible outside the PersistentIntMap class hierarchy in order to guarantee
139 * NOTE - since this is an internal type, we forego a lot of argument range checks in
140 * the Node subclasses, assuming that all internal use has been tested and bugs will not
141 * cause silent corruption of node data but will lead to follow-on exceptions such as
142 * ArrayIndexOutOfBounds etc.
144 protected abstract static class Node<E> {
146 abstract E getElementAtLevelIndex (int i);
148 abstract int getNumberOfElements();
149 abstract E getElementAtStorageIndex (int i);
151 abstract int storageToLevelIndex (int i);
154 abstract Node cloneWithAdded (int idx, E e);
155 abstract Node cloneWithReplaced (int idx, E e);
156 abstract Node cloneWithRemoved (int idx);
157 abstract Node removeAllSatisfying (Predicate<E> pred);
160 abstract void set (int idx, E e);
161 abstract void process (int level, Node<E> targetNode, Node<E> stagingNode, Processor<E> p);
163 boolean isEmptyNode(){
168 void printIndentOn (PrintStream ps, int level) {
169 for (int i=0; i<level; i++) {
174 void printNodeInfoOn (PrintStream ps, Node targetNode, Node stagingNode) {
175 String clsName = getClass().getSimpleName();
176 int idx = clsName.indexOf('$');
178 clsName = clsName.substring(idx+1);
182 if (this == targetNode){
183 ps.print( " (target)");
187 abstract void printOn(PrintStream ps, int level, Node targetNode, Node stagingNode);
191 * Node that has only one element and hence does not need an array.
192 * If a new element is added, this OneNode gets promoted into a BitmapNode
194 protected static class OneNode<E> extends Node<E> {
198 OneNode (int idx, E e){
204 int getNumberOfElements(){
209 E getElementAtStorageIndex (int i){
215 E getElementAtLevelIndex(int i) {
224 int storageToLevelIndex (int i){
232 * this assumes the index is not set
235 Node cloneWithAdded(int i, E newElement) {
238 Object[] a = new Object[2];
247 int bitmap = (1 << idx) | (1 << i);
249 return new BitmapNode(bitmap, a);
253 * this assumes the index is set
256 Node cloneWithReplaced(int i, E e) {
258 return new OneNode( i, e);
262 * this assumes the index is set
265 Node cloneWithRemoved(int i){
271 Node removeAllSatisfying (Predicate<E> pred){
280 void set (int i, E e){
286 boolean isEmptyNode(){
291 void process (int level, Node<E> targetNode, Node<E> stagingNode, Processor<E> p){
293 if (this == targetNode){
294 stagingNode.process( 0, null, null, p);
299 ((Node)e).process( level-1, targetNode, stagingNode, p);
304 public void printOn (PrintStream ps, int depth, Node targetNode, Node stagingNode) {
305 printIndentOn(ps, depth);
306 ps.printf("%2d: ", idx);
308 if (e instanceof Node) {
309 Node<E> n = (Node<E>) e;
310 n.printNodeInfoOn(ps, targetNode, stagingNode);
312 n.printOn(ps, depth+1, targetNode, stagingNode);
322 * A node that holds between 2 and 31 elements.
324 * We use bitmap based element array compaction - the corresponding bit block of the key
325 * [0..31] is used as an index into a bitmap. The elements are stored in a dense
326 * array at indices corresponding to the number of set bitmap bits to the right of the
327 * respective index in the bitmap, e.g. for
330 * key = 289 = 0b01001.00001, shift = 5, assuming node already contains key 97 = 0b00011.00001 =>
331 * idx = (key >>> shift) & 0x1f = 0b01001 = 9
332 * bitmap = 1000001000 : bit 9 from key 289 (0b01001.), bit 3 from key 97 (0b00011.)
333 * node element index for key 289 (level index 9) = 1 (one set bit to the right of bit 9)
334 * </pre></blockquote>
336 * While storage index computation seems complicated and expensive, there are efficient algorithms to
337 * count leading/trailing bits by means of binary operations and minimal branching, which is
338 * suitable for JIT compilation (see http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup)
341 * If the bit count of a BitmapNode is 2 and an element is removed, this gets demoted into q OneNode.
342 * If the bit count of a BitmapNode is 31 and an element is added, this gets promoted into a FullNode
344 protected static class BitmapNode<E> extends Node<E> {
348 BitmapNode (int idx, E e, E e0){
349 bitmap = (1 << idx) | 1;
351 elements = (E[]) new Object[2];
356 BitmapNode (int bitmap, E[] elements){
357 this.bitmap = bitmap;
358 this.elements = elements;
362 int getNumberOfElements(){
363 return elements.length;
367 E getElementAtStorageIndex (int i){
372 E getElementAtLevelIndex (int i) {
374 if ((bitmap & bit) != 0) {
375 int idx = Integer.bitCount( bitmap & (bit-1));
376 return elements[idx];
383 * get the position of the (n+1)'th set bit in bitmap
386 int storageToLevelIndex (int n){
424 for (int i=n; i>0; i--){
425 v &= v-1; // remove n-1 least significant bits
429 v = v & ~(v-1); // reduce to the least significant bit
430 return TrailingMultiplyDeBruijnBitPosition[((v & -v) * 0x077CB531) >>> 27];
434 Node cloneWithAdded(int i, E e) {
436 int idx = Integer.bitCount( bitmap & (bit -1));
438 if (elements.length == 31){
439 Object[] a = new Object[32];
442 System.arraycopy(elements, 0, a, 0, idx);
445 System.arraycopy(elements, idx, a, idx + 1, 31 - idx);
448 return new FullNode(a);
451 int n = elements.length;
452 Object[] a = new Object[n + 1];
455 System.arraycopy(elements, 0, a, 0, idx);
461 System.arraycopy(elements, idx, a, idx + 1, (n - idx));
464 return new BitmapNode( bitmap | bit, a);
469 Node cloneWithReplaced(int i, E e) {
470 int idx = Integer.bitCount( bitmap & ((1<<i) -1));
472 E[] a = elements.clone();
475 return new BitmapNode( bitmap, a);
479 Node cloneWithRemoved(int i){
481 int idx = Integer.bitCount( bitmap & (bit-1));
482 int n = elements.length;
485 E e = (idx == 0) ? elements[1] : elements[0]; // the remaining value
486 int i0 = Integer.numberOfTrailingZeros(bitmap ^ bit);
487 return new OneNode( i0, e);
490 Object[] a = new Object[n - 1];
492 System.arraycopy(elements, 0, a, 0, idx);
496 System.arraycopy(elements, idx + 1, a, idx, (n - idx));
498 return new BitmapNode(bitmap ^ bit, a);
503 Node removeAllSatisfying (Predicate<E> pred){
504 int newBitmap = bitmap;
505 int len = elements.length;
510 for (int i=0, bit=1; i<len; i++, bit<<=1){
511 while ((newBitmap & bit) == 0){
515 if (pred.isTrue(elem[i])){
522 if (newLen == 0){ // nothing left
525 } else if (newLen == len){ // nothing removed
528 } else if (newLen == 1) { // just one value left - reduce to OneNode
529 int i = Integer.bitCount( bitmap & (newBitmap -1));
530 int idx = Integer.numberOfTrailingZeros(newBitmap);
531 return new OneNode<E>( idx, elem[i]);
533 } else { // some values removed - reduced BitmapNode
534 E[] newElements = (E[]) new Object[newLen];
535 for (int i=0, j=0; j<newLen; i++){
536 if ((removed & (1<<i)) == 0){
537 newElements[j++] = elem[i];
540 return new BitmapNode( newBitmap, newElements);
546 void set (int i, E e){
547 int idx = Integer.bitCount( bitmap & ((1<<i) -1));
552 void process (int level, Node<E> targetNode, Node<E> stagingNode, Processor<E> p){
554 if (this == targetNode){
555 stagingNode.process(0, null, null, p);
557 for (int i = 0; i < elements.length; i++) {
558 p.process(elements[i]);
562 for (int i=0; i<elements.length; i++){
563 ((Node)elements[i]).process(level-1, targetNode, stagingNode, p);
569 void printOn (PrintStream ps, int depth, Node targetNode, Node stagingNode) {
571 for (int i=0; i<32; i++) {
572 if ((bitmap & (1<<i)) != 0) {
573 printIndentOn(ps, depth);
574 ps.printf("%2d: ", i);
577 if (e instanceof Node) {
578 Node<E> n = (Node<E>)e;
579 n.printNodeInfoOn(ps, targetNode, stagingNode);
581 n.printOn(ps, depth+1, targetNode, stagingNode);
593 * newElements node with 32 elements, for which we don't need newElements bitmap.
594 * No element can be added since this means we just promote an existing element
595 * If an element is removed, this FullNode gets demoted int newElements BitmapNode
597 protected static class FullNode<E> extends Node<E> {
600 FullNode (E[] elements){
601 this.elements = elements;
605 int getNumberOfElements(){
610 E getElementAtStorageIndex (int i){
615 E getElementAtLevelIndex (int i) {
620 int storageToLevelIndex (int i){
626 Node cloneWithAdded (int idx, E e){
627 throw new RuntimeException("can't add a new element to a FullNode");
631 Node cloneWithReplaced (int idx, E e){
632 E[] newElements = elements.clone();
633 newElements[idx] = e;
634 return new FullNode(newElements);
638 Node cloneWithRemoved(int idx){
639 Object[] a = new Object[31];
640 int bitmap = 0xffffffff ^ (1 << idx);
643 System.arraycopy(elements, 0, a, 0, idx);
646 System.arraycopy(elements, idx+1, a, idx, 31-idx);
649 return new BitmapNode( bitmap, a);
653 Node removeAllSatisfying (Predicate<E> pred){
654 int newBitmap = 0xffffffff;
659 for (int i=0, bit=1; i<32; i++, bit<<=1){
660 if (pred.isTrue(elem[i])){
667 if (newLen == 0){ // nothing left
670 } else if (newLen == 32){ // nothing removed
673 } else if (newLen == 1) { // just one value left - reduce to OneNode
674 int idx = Integer.numberOfTrailingZeros(newBitmap);
675 return new OneNode<E>( idx, elem[idx]);
677 } else { // some values removed - reduced BitmapNode
678 E[] newElements = (E[]) new Object[newLen];
679 for (int i=0, j=0; j<newLen; i++){
680 if ((removed & (1<<i)) == 0){
681 newElements[j++] = elem[i];
684 return new BitmapNode( newBitmap, newElements);
689 void set (int i, E e){
694 void process (int level, Node<E> targetNode, Node<E> stagingNode, Processor<E> p){
696 if (this == targetNode){
697 stagingNode.process(0, null, null, p);
699 for (int i = 0; i < elements.length; i++) {
700 p.process(elements[i]);
704 for (int i=0; i<elements.length; i++){
705 ((Node)elements[i]).process(level-1, targetNode, stagingNode, p);
711 void printOn (PrintStream ps, int depth, Node targetNode, Node stagingNode) {
712 for (int i=0; i<32; i++) {
713 printIndentOn(ps, depth);
714 ps.printf("%2d: ", i);
717 if (e instanceof Node) {
718 Node<E> n = (Node<E>) e;
719 n.printNodeInfoOn(ps, targetNode, stagingNode);
721 n.printOn(ps, depth+1, targetNode, stagingNode);
731 @SuppressWarnings({ "rawtypes", "unchecked" })
732 public Iterator<V> iterator(){
733 return new ValueIterator();
737 * this is less efficient than using map.process(processor), but required to use PSIntMaps in lieu of ordinary containers
738 * Since PSIntMaps are bounded recursive data structures, we have to model newElements stack explicitly, but at least we know it is
739 * not exceeding newElements depth of 6 (5 bit index blocks)
741 * Note - there are no empty nodes. Each one has at least newElements single child node or value
743 protected class ValueIterator implements Iterator<V> {
746 int nodeIdx, maxNodeIdx;
748 Node[] parentNodeStack;
749 int[] parentIdxStack;
751 int nVisited, nTotal;
754 @SuppressWarnings("unchecked")
755 public ValueIterator (){
756 node = PSIntMap.this.rootNode;
758 if (node == PSIntMap.this.targetNode){
759 node = PSIntMap.this.stagingNode;
762 maxNodeIdx = node.getNumberOfElements();
768 int depth = PSIntMap.this.rootLevel;
769 parentNodeStack = new Node[depth];
770 parentIdxStack = new int[depth];
772 nTotal = PSIntMap.this.size;
777 public boolean hasNext() {
778 return nVisited < nTotal;
782 @SuppressWarnings("unchecked")
784 if (nVisited >= nTotal) {
785 throw new NoSuchElementException();
789 Object nv = node.getElementAtStorageIndex( idx);
792 while (top < PSIntMap.this.rootLevel) {
793 parentNodeStack[top] = node; // push current node on stack
794 parentIdxStack[top] = idx;
797 if (nv == PSIntMap.this.targetNode){
798 node = PSIntMap.this.stagingNode;
804 maxNodeIdx = node.getNumberOfElements();
806 nv = node.getElementAtStorageIndex(0);
809 //--- newElements value, finally
813 if (idx == maxNodeIdx) { // done, no more child nodes/values for this node
814 while (top > 0) { // go up
816 node = parentNodeStack[top];
817 nodeIdx = parentIdxStack[top] + 1;
818 maxNodeIdx = node.getNumberOfElements();
819 if (nodeIdx < maxNodeIdx) break;
825 //assert (nVisited == nTotal) || (nodeIdx < maxNodeIdx);
830 public void remove() {
831 throw new UnsupportedOperationException("PersistentIntMap iterators don't support removal");
837 //--- auxiliary data and functions
839 static final int BASE_MASK = ~0x1f;
841 static final int TrailingMultiplyDeBruijnBitPosition[] = {
842 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
843 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
846 static int getNumberOfTrailingZeros (int v){
847 return TrailingMultiplyDeBruijnBitPosition[((v & -v) * 0x077CB531) >>> 27];
851 // the values are the respective block levels
852 static final int LeadingMultiplyDeBruijnBitPosition[] = {
853 0, 1, 0, 2, 2, 4, 0, 5, 2, 2, 3, 3, 4, 5, 0, 6,
854 1, 2, 4, 5, 3, 3, 4, 1, 3, 5, 4, 1, 5, 1, 0, 6
858 * get the start level [0..7] for the highest bit index (bit block). This is essentially counting the number of leading zero bits,
859 * which we can derive from http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup
861 static int getStartLevel (int v){
868 return LeadingMultiplyDeBruijnBitPosition[(v * 0x07C4ACDD) >>> 27];
873 final protected int size; // number of values in this map
874 final protected int rootLevel; // bit block level of the root node (highest non-0 bit block of all keys in map)
875 final protected Node rootNode; // topmost node of trie
878 * the following fields are used to cache consecutive key operations with the goal of avoiding
879 * path copies from the modified value node all the way up to the root node. As long as the same value
880 * node is modified (hence msb key block traversal) we just need to keep track which position in the
881 * trie the stagingNode refers to (stagingNodeMask), and only have to create a new stagingNode with the
882 * updated values. Once we have a key operation that refers to a different value node position (staging miss),
883 * we merge the old stagingNode back into the trie. If we do this after inserting the new key, only
884 * nodes from the old stagingNode parent up to the first node that is on the new key path have to be copied,
885 * the merge node (on the new stagingNode path) can be safely modified since it has only been created during
886 * the ongoing map operation. Example:
888 * last mod key/value (old stagingNode) : a.c.e -> Y => stagingNodeMask = a.c.FF
889 * new key/value (new stagingNode) : a.b.d -> X
892 * n0: [...n1...] root node (level 2)
898 * n2: [.X..] n3: [.....] value nodes (level 0) [...Y...]
899 * new stagingNode old targetNode <-------------------------- old stagingNode
902 * In this case, the sequence of operations is as follows:
904 * <li> insert new key/value pair (a.b.d)->X into the trie, which is a stagingNode miss since
905 * stagingNodeMasks are different (a.b.FF != a.c.FF). This leads to copied/new nodes n2,n1,n0
906 * <li> check if old stagingNode differs from targetNode (had several consecutive modifications), if
907 * targetNode != stagingNode then merge old stagingNode <em>after</em> n2,n1,n0 creation
908 * <li> since n1 is already a new node that is not shared with any prior version of this map,
909 * its [c] element can be simply set to the old stagingNode, i.e. the merge does not require
910 * any additional allocation. Note that n1 has to contain a [c] element since we always link
911 * new stagingNodes into the trie upon creation. This means the number of elements in n1
912 * (and hence the node type) does not change, i.e. setting the new [c] element involves
913 * just a single AASTORE instruction
914 * <li> set stagingNode = targetNode = n2
918 final protected Node<V> stagingNode; // last modified value node (not linked into the trie upon subsequent modification)
919 final protected int stagingNodeMask; // key mask for stagingNode (key | 0x1f)
920 final protected Node targetNode; // original stagingNode state that is linked into the trie
923 * the only public constructor
928 this.rootNode = null;
929 this.targetNode = null;
930 this.stagingNode = null;
931 this.stagingNodeMask = 0;
934 protected PSIntMap (int size, int rootLevel, Node rootNode, Node<V> stagingNode, Node<V> targetNode, int stagingNodeMask){
936 this.rootLevel = rootLevel;
937 this.rootNode = rootNode;
938 this.stagingNode = stagingNode;
939 this.targetNode = targetNode;
940 this.stagingNodeMask = stagingNodeMask;
949 public V get (int key){
950 if (stagingNodeMask == (key | 0x1f)){
951 int idx = key & 0x1f;
952 return stagingNode.getElementAtLevelIndex(idx);
955 if (rootNode == null) return null;
957 int l = getStartLevel(key);
958 if (l > rootLevel) return null;
960 Node<Node> n = rootNode;
964 n = n.getElementAtLevelIndex( key >>> 30);
965 if (n == null) return null;
967 n = n.getElementAtLevelIndex( (key >>> 25) & 0x1f);
968 if (n == null) return null;
970 n = n.getElementAtLevelIndex( (key >>> 20) & 0x1f);
971 if (n == null) return null;
973 n = n.getElementAtLevelIndex( (key >>> 15) & 0x1f);
974 if (n == null) return null;
976 n = n.getElementAtLevelIndex( (key >>> 10) & 0x1f);
977 if (n == null) return null;
979 n = n.getElementAtLevelIndex( (key >>> 5) & 0x1f);
980 if (n == null) return null;
982 return ((Node<V>)n).getElementAtLevelIndex(key & 0x1f);
985 return null; // can't get here
989 protected Node mergeStagingNode (){
990 Node<Node> n2=null, n3=null, n4=null, n5=null, n6=null;
991 int i1, i2=0, i3=0, i4=0, i5=0, i6=0;
993 int k = stagingNodeMask;
994 Node<Node> n = rootNode;
1000 n = n.getElementAtLevelIndex(i6);
1002 i5 = (k >>> 25) & 0x1f;
1004 n = n.getElementAtLevelIndex(i5);
1006 i4 = (k >>> 20) & 0x1f;
1008 n = n.getElementAtLevelIndex(i4);
1010 i3 = (k >>> 15) & 0x1f;
1012 n = n.getElementAtLevelIndex(i3);
1014 i2 = (k >>> 10) & 0x1f;
1016 n = n.getElementAtLevelIndex(i2);
1018 i1 = (k >>> 5) & 0x1f;
1019 n = n.cloneWithReplaced(i1, stagingNode);
1021 n = n2.cloneWithReplaced(i2, n);
1023 n = n3.cloneWithReplaced(i3, n);
1025 n = n4.cloneWithReplaced(i4, n);
1027 n = n5.cloneWithReplaced(i5, n);
1029 n = n6.cloneWithReplaced(i6, n);
1038 // special case - only node in the trie is the targetNode
1042 return null; // can't get here
1046 * this relies on that all nodes from the new staging node to the newRootNode have been copied
1047 * and can be modified without cloning.
1048 * The modification does not change the node type since the old staging/target node was in the trie
1049 * The first node where new and old staging indices differ is the mergeNode that needs to be
1050 * modified (old staging path node replaced). This has to be level 1..6
1051 * Everything above the mergeNode is not modified (the newRootNode does not have to be copied
1053 * All nodes between the old stagingNode and the mergeNode have to be copied
1054 * The old stagingNode itself does not need to be cloned.
1056 protected void mergeStagingNode (int key, int newRootLevel, Node newRootNode){
1057 int k = stagingNodeMask;
1058 int mergeLevel = getStartLevel( key ^ k); // block of first differing bit
1059 Node<Node> mergeNode = newRootNode;
1060 int shift = newRootLevel*5;
1062 //--- get the mergeNode
1063 for (int l=newRootLevel; l>mergeLevel; l--){
1064 int idx = (k >>> shift) & 0x1f;
1065 mergeNode = mergeNode.getElementAtLevelIndex(idx);
1068 int mergeIdx = (k >>> shift) & 0x1f;
1070 //--- copy from old staging up to mergeNode
1071 Node<Node> n5=null, n4=null, n3=null, n2=null, n1=null;
1072 int i5=0, i4=0, i3=0, i2=0, i1=0;
1073 Node<Node> n = mergeNode.getElementAtLevelIndex(mergeIdx);
1075 switch (mergeLevel-1){
1077 i5 = (k >>> 25) & 0x1f;
1079 n = n.getElementAtLevelIndex(i5);
1081 i4 = (k >>> 20) & 0x1f;
1083 n = n.getElementAtLevelIndex(i4);
1085 i3 = (k >>> 15) & 0x1f;
1087 n = n.getElementAtLevelIndex(i3);
1089 i2 = (k >>> 10) & 0x1f;
1091 n = n.getElementAtLevelIndex(i2);
1093 i1 = (k >>> 5) & 0x1f;
1096 n = (Node)stagingNode;
1099 n = n1.cloneWithReplaced(i1, n);
1101 n = n2.cloneWithReplaced(i2, n);
1103 n = n3.cloneWithReplaced(i3, n);
1105 n = n4.cloneWithReplaced(i4, n);
1107 n = n5.cloneWithReplaced(i5, n);
1115 //--- modify mergeNode
1116 mergeNode.set(mergeIdx, n);
1119 PSIntMap<V> remove (int key, boolean isTargetNode){
1120 Node<Node> n6=null, n5=null, n4=null, n3=null, n2=null, n1=null;
1122 int i6=0, i5=0, i4=0, i3=0, i2=0, i1=0, i0;
1124 Node<Node> n = rootNode;
1128 n5 = n.getElementAtLevelIndex(i6);
1130 return this; // key not in map
1136 i5 = (key >>> 25) & 0x1f;
1137 n4 = n.getElementAtLevelIndex(i5);
1139 return this; // key not in map
1145 i4 = (key >>> 20) & 0x1f;
1146 n3 = n.getElementAtLevelIndex(i4);
1148 return this; // key not in map
1154 i3 = (key >>> 15) & 0x1f;
1155 n2 = n.getElementAtLevelIndex(i3);
1157 return this; // key not in map
1163 i2 = (key >>> 10) & 0x1f;
1164 n1 = n.getElementAtLevelIndex(i2);
1166 return this; // key not in map
1172 i1 = (key >>> 5) & 0x1f;
1173 n0 = n.getElementAtLevelIndex(i1);
1187 if (n0 == null || n0.getElementAtLevelIndex(i0) == null){
1188 return this; // key not in map
1190 n0 = n0.cloneWithRemoved(i0);
1195 n = (n == null) ? n1.cloneWithRemoved(i1) : n1.cloneWithReplaced(i1, n);
1197 n = (n == null) ? n2.cloneWithRemoved(i2) : n2.cloneWithReplaced(i2, n);
1199 n = (n == null) ? n3.cloneWithRemoved(i3) : n3.cloneWithReplaced(i3, n);
1201 n = (n == null) ? n4.cloneWithRemoved(i4) : n4.cloneWithReplaced(i4, n);
1203 n = (n == null) ? n5.cloneWithRemoved(i5) : n5.cloneWithReplaced(i5, n);
1205 n = (n == null) ? n6.cloneWithRemoved(i6) : n6.cloneWithReplaced(i6, n);
1214 return new PSIntMap<V>();
1217 int newRootLevel = rootLevel;
1218 int newSb = (n0 == null) ? 0 : (key | 0x1f);
1220 while ((newRootLevel > 0) && n.isEmptyNode()){
1222 n = n.getElementAtLevelIndex(0);
1225 if (!isTargetNode && (stagingNode != targetNode)){
1226 mergeStagingNode(key, newRootLevel, n);
1229 return new PSIntMap<V>( size-1, newRootLevel, n, n0, n0, newSb);
1233 return null; // can't get here
1236 public PSIntMap<V> remove (int key){
1237 int newSm = key | 0x1f;
1239 if (newSm == stagingNodeMask){ // staging node hit - this should be the dominant case
1241 Node<V> n = stagingNode;
1242 if ((n.getElementAtLevelIndex(i)) != null) { // key is in the stagingNode
1243 n = n.cloneWithRemoved(i);
1244 if (n == null){ // staging node is empty, remove target node
1245 return remove(newSm, true);
1246 } else { // non-empty staging node, just replace it
1247 return new PSIntMap<V>( size-1, rootLevel, rootNode, n, targetNode, newSm);
1250 } else { // key wasn't in the stagingNode
1254 } else { // staging node miss
1255 return remove( key, false);
1260 * this either replaces or adds newElements new value
1262 public PSIntMap<V> set (int key, V value){
1265 // we don't store null values, this is a remove in disguise
1269 int newSm = key | 0x1f;
1271 if (newSm == stagingNodeMask){ // staging node hit - this should be the dominant case
1273 Node<V> n = stagingNode;
1275 if ((n.getElementAtLevelIndex(i)) == null) {
1276 n = n.cloneWithAdded(i, value);
1279 n = n.cloneWithReplaced(i, value);
1281 return new PSIntMap<V>( newSize, rootLevel, rootNode, n, targetNode, newSm);
1283 } else { // staging node miss
1284 int newRootLevel = getStartLevel(key);
1286 if (newRootLevel > rootLevel){ // old trie has to be merged in
1287 return setInNewRootLevel( newRootLevel, key, value);
1289 } else { // new value can be added to old trie (stagingNode change)
1290 return setInCurrentRootLevel( key, value);
1295 protected PSIntMap<V> setInNewRootLevel (int newRootLevel, int key, V value){
1296 int newSm = key | 0x1f;
1299 if (stagingNode != targetNode){
1300 nOld = mergeStagingNode();
1305 //--- expand old root upwards
1307 for (int l = rootLevel + 1; l < newRootLevel; l++) {
1308 nOld = new OneNode(0, nOld);
1312 //--- create chain of new value nodes
1314 Node nNew = new OneNode(i, value);
1316 Node newStagingNode = nNew;
1317 for (int l = 1; l < newRootLevel; l++) {
1318 i = (key >>> shift) & 0x1f;
1319 nNew = new OneNode(i, nNew);
1323 //--- create new root
1324 i = (key >>> shift); // no remainBmp needed, top level
1325 Node<Node> newRootNode = (nOld == null) ? new OneNode( i, nNew) : new BitmapNode<Node>(i, nNew, nOld);
1327 return new PSIntMap<V>(size + 1, newRootLevel, newRootNode, newStagingNode, newStagingNode, newSm);
1331 * that's ugly, but if we use recursion we need newElements result object to obtain the new stagingNode and
1332 * the size change, which means there would be an additional allocation per set() or newElements non-persistent,
1333 * transient object that would need synchronization
1335 protected PSIntMap<V> setInCurrentRootLevel (int key, V value){
1336 Node<Node> n6=null, n5=null, n4=null, n3=null, n2=null, n1=null;
1338 int i6=0, i5=0, i4=0, i3=0, i2=0, i1=0, i0;
1339 int newSb = key | 0x1f;
1340 boolean needsMerge = (targetNode != stagingNode);
1341 int newSize = size+1;
1343 //--- new stagingNode
1344 Node<Node> n = rootNode;
1349 n5 = n.getElementAtLevelIndex(i6);
1351 n0 = new OneNode( (key & 0x1f), value);
1352 n1 = new OneNode( (key >>> 5) & 0x1f, n0);
1353 n2 = new OneNode( (key >>> 10) & 0x1f, n1);
1354 n3 = new OneNode( (key >>> 15) & 0x1f, n2);
1355 n4 = new OneNode( (key >>> 20) & 0x1f, n3);
1356 n5 = new OneNode( (key >>> 25) & 0x1f, n4);
1357 n = n.cloneWithAdded( i6, n5);
1358 if (needsMerge) mergeStagingNode(key, rootLevel, n);
1359 return new PSIntMap<V>( newSize, rootLevel, n, n0, n0, newSb);
1367 i5 = (key >>> 25) & 0x1f;
1368 n4 = n.getElementAtLevelIndex(i5);
1370 n0 = new OneNode( (key & 0x1f), value);
1371 n1 = new OneNode( (key >>> 5) & 0x1f, n0);
1372 n2 = new OneNode( (key >>> 10) & 0x1f, n1);
1373 n3 = new OneNode( (key >>> 15) & 0x1f, n2);
1374 n4 = new OneNode( (key >>> 20) & 0x1f, n3);
1375 n = n.cloneWithAdded( i5, n4);
1378 n = n6.cloneWithReplaced( i6, n);
1380 if (needsMerge) mergeStagingNode(key, rootLevel, n);
1381 return new PSIntMap<V>( newSize, rootLevel, n, n0, n0, newSb);
1389 i4 = (key >>> 20) & 0x1f;
1390 n3 = n.getElementAtLevelIndex(i4);
1392 n0 = new OneNode( (key & 0x1f), value);
1393 n1 = new OneNode( (key >>> 5) & 0x1f, n0);
1394 n2 = new OneNode( (key >>> 10) & 0x1f, n1);
1395 n3 = new OneNode( (key >>> 15) & 0x1f, n2);
1396 n = n.cloneWithAdded( i4, n3);
1399 n = n5.cloneWithReplaced( i5, n);
1401 n = n6.cloneWithReplaced( i6, n);
1404 if (needsMerge) mergeStagingNode(key, rootLevel, n);
1405 return new PSIntMap<V>( newSize, rootLevel, n, n0, n0, newSb);
1413 i3 = (key >>> 15) & 0x1f;
1414 n2 = n.getElementAtLevelIndex(i3);
1416 n0 = new OneNode( (key & 0x1f), value);
1417 n1 = new OneNode( (key >>> 5) & 0x1f, n0);
1418 n2 = new OneNode( (key >>> 10) & 0x1f, n1);
1419 n = n.cloneWithAdded( i3, n2);
1422 n = n4.cloneWithReplaced( i4, n);
1424 n = n5.cloneWithReplaced( i5, n);
1426 n = n6.cloneWithReplaced( i6, n);
1430 if (needsMerge) mergeStagingNode(key, rootLevel, n);
1431 return new PSIntMap<V>( newSize, rootLevel, n, n0, n0, newSb);
1439 i2 = (key >>> 10) & 0x1f;
1440 n1 = n.getElementAtLevelIndex(i2);
1442 n0 = new OneNode( (key & 0x1f), value);
1443 n1 = new OneNode( (key >>> 5) & 0x1f, n0);
1444 n = n.cloneWithAdded( i2, n1);
1447 n = n3.cloneWithReplaced( i3, n);
1449 n = n4.cloneWithReplaced( i4, n);
1451 n = n5.cloneWithReplaced( i5, n);
1453 n = n6.cloneWithReplaced( i6, n);
1458 if (needsMerge) mergeStagingNode(key, rootLevel, n);
1459 return new PSIntMap<V>( newSize, rootLevel, n, n0, n0, newSb);
1467 i1 = (key >>> 5) & 0x1f;
1468 n0 = n.getElementAtLevelIndex(i1);
1470 n0 = new OneNode( (key & 0x1f), value);
1471 n = n.cloneWithAdded( i1, n0);
1474 n = n2.cloneWithReplaced( i2, n);
1476 n = n3.cloneWithReplaced( i3, n);
1478 n = n4.cloneWithReplaced( i4, n);
1480 n = n5.cloneWithReplaced( i5, n);
1482 n = n6.cloneWithReplaced( i6, n);
1488 if (needsMerge) mergeStagingNode(key, rootLevel, n);
1489 return new PSIntMap<V>( newSize, rootLevel, n, n0, n0, newSb);
1496 case 0: // finally the value level
1500 if (n0.getElementAtLevelIndex(i0) == null) {
1501 n0 = n0.cloneWithAdded(i0, value);
1503 n0 = n0.cloneWithReplaced(i0, value);
1506 } else { // first node
1507 n0 = new OneNode( i0, value);
1513 n = n1.cloneWithReplaced( i1, n);
1515 n = n2.cloneWithReplaced( i2, n);
1517 n = n3.cloneWithReplaced( i3, n);
1519 n = n4.cloneWithReplaced( i4, n);
1521 n = n5.cloneWithReplaced( i5, n);
1523 n = n6.cloneWithReplaced( i6, n);
1530 if (needsMerge) mergeStagingNode( key, rootLevel, n);
1531 return new PSIntMap<V>( newSize, rootLevel, n, n0, n0, newSb);
1534 return null; // can't get here
1538 public void process (Processor<V> p){
1539 if (rootNode != null){
1540 if (targetNode == stagingNode){
1541 rootNode.process( rootLevel, null, null, p);
1543 rootNode.process( rootLevel, targetNode, stagingNode, p);
1548 final protected Node removeAllSatisfying (int level, Node node, Predicate<V> pred){
1549 if (level == 0){ // value level
1550 return ((Node<V>)node).removeAllSatisfying(pred);
1552 } else { // node level
1553 // it sucks not having stack arrays but we don't want to allocate for temporary results
1554 Node n0=null,n1=null,n2=null,n3=null,n4=null,n5=null,n6=null,n7=null,n8=null,n9=null,n10=null,
1555 n11=null,n12=null,n13=null,n14=null,n15=null,n16=null,n17=null,n18=null,n19=null,n20=null,
1556 n21=null,n22=null,n23=null,n24=null,n25=null,n26=null,n27=null,n28=null,n29=null,n30=null,n31=null;
1557 int nRemaining = 0, nChanged = 0;
1558 int len = node.getNumberOfElements();
1560 //--- collect the remaining nodes
1561 for (int i=0; i<len; i++){
1562 Node e = (Node)node.getElementAtStorageIndex(i);
1563 Node n = removeAllSatisfying( level-1, e, pred);
1570 case 0: n0=n; break;
1571 case 1: n1=n; break;
1572 case 2: n2=n; break;
1573 case 3: n3=n; break;
1574 case 4: n4=n; break;
1575 case 5: n5=n; break;
1576 case 6: n6=n; break;
1577 case 7: n7=n; break;
1578 case 8: n8=n; break;
1579 case 9: n9=n; break;
1580 case 10: n10=n; break;
1581 case 11: n11=n; break;
1582 case 12: n12=n; break;
1583 case 13: n13=n; break;
1584 case 14: n14=n; break;
1585 case 15: n15=n; break;
1586 case 16: n16=n; break;
1587 case 17: n17=n; break;
1588 case 18: n18=n; break;
1589 case 19: n19=n; break;
1590 case 20: n20=n; break;
1591 case 21: n21=n; break;
1592 case 22: n22=n; break;
1593 case 23: n23=n; break;
1594 case 24: n24=n; break;
1595 case 25: n25=n; break;
1596 case 26: n26=n; break;
1597 case 27: n27=n; break;
1598 case 28: n28=n; break;
1599 case 29: n29=n; break;
1600 case 30: n30=n; break;
1601 case 31: n31=n; break;
1606 //--- construct the returned node
1607 if (nRemaining == 0){
1610 } else if ((nRemaining == len) && (nChanged == 0)){
1614 if (nRemaining == 1){ // becomes a OneNode
1615 for (int i=0; i<32; i++){
1617 case 0: if (n0!=null) return new OneNode( node.storageToLevelIndex(0), n0); break;
1618 case 1: if (n1!=null) return new OneNode( node.storageToLevelIndex(1), n1); break;
1619 case 2: if (n2!=null) return new OneNode( node.storageToLevelIndex(2), n2); break;
1620 case 3: if (n3!=null) return new OneNode( node.storageToLevelIndex(3), n3); break;
1621 case 4: if (n4!=null) return new OneNode( node.storageToLevelIndex(4), n4); break;
1622 case 5: if (n5!=null) return new OneNode( node.storageToLevelIndex(5), n5); break;
1623 case 6: if (n6!=null) return new OneNode( node.storageToLevelIndex(6), n6); break;
1624 case 7: if (n7!=null) return new OneNode( node.storageToLevelIndex(7), n7); break;
1625 case 8: if (n8!=null) return new OneNode( node.storageToLevelIndex(8), n8); break;
1626 case 9: if (n9!=null) return new OneNode( node.storageToLevelIndex(9), n9); break;
1627 case 10: if (n10!=null) return new OneNode( node.storageToLevelIndex(10),n10); break;
1628 case 11: if (n11!=null) return new OneNode( node.storageToLevelIndex(11),n11); break;
1629 case 12: if (n12!=null) return new OneNode( node.storageToLevelIndex(12),n12); break;
1630 case 13: if (n13!=null) return new OneNode( node.storageToLevelIndex(13),n13); break;
1631 case 14: if (n14!=null) return new OneNode( node.storageToLevelIndex(14),n14); break;
1632 case 15: if (n15!=null) return new OneNode( node.storageToLevelIndex(15),n15); break;
1633 case 16: if (n16!=null) return new OneNode( node.storageToLevelIndex(16),n16); break;
1634 case 17: if (n17!=null) return new OneNode( node.storageToLevelIndex(17),n17); break;
1635 case 18: if (n18!=null) return new OneNode( node.storageToLevelIndex(18),n18); break;
1636 case 19: if (n19!=null) return new OneNode( node.storageToLevelIndex(19),n19); break;
1637 case 20: if (n20!=null) return new OneNode( node.storageToLevelIndex(20),n20); break;
1638 case 21: if (n21!=null) return new OneNode( node.storageToLevelIndex(21),n21); break;
1639 case 22: if (n22!=null) return new OneNode( node.storageToLevelIndex(22),n22); break;
1640 case 23: if (n23!=null) return new OneNode( node.storageToLevelIndex(23),n23); break;
1641 case 24: if (n24!=null) return new OneNode( node.storageToLevelIndex(24),n24); break;
1642 case 25: if (n25!=null) return new OneNode( node.storageToLevelIndex(25),n25); break;
1643 case 26: if (n26!=null) return new OneNode( node.storageToLevelIndex(26),n26); break;
1644 case 27: if (n27!=null) return new OneNode( node.storageToLevelIndex(27),n27); break;
1645 case 28: if (n28!=null) return new OneNode( node.storageToLevelIndex(28),n28); break;
1646 case 29: if (n29!=null) return new OneNode( node.storageToLevelIndex(29),n29); break;
1647 case 30: if (n30!=null) return new OneNode( node.storageToLevelIndex(30),n30); break;
1648 case 31: if (n31!=null) return new OneNode( node.storageToLevelIndex(31),n31); break;
1652 } else if (nRemaining == 32) { // still a FullNode, but elements might have changed
1653 Node[] a = {n0,n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,
1654 n11,n12,n13,n14,n15,n16,n17,n18,n19,n20,
1655 n21,n22,n23,n24,n25,n26,n27,n28,n29,n30,n31};
1657 return new FullNode(a);
1661 Node[] a = new Node[nRemaining];
1664 // <2do> this is bad - there has to be a more efficient way to generate the bitmap
1665 for (int i=0; j < nRemaining; i++){
1667 case 0: if (n0!=null) { a[j++] = n0; bitmap |= (1<<node.storageToLevelIndex(0)); } break;
1668 case 1: if (n1!=null) { a[j++] = n1; bitmap |= (1<<node.storageToLevelIndex(1)); } break;
1669 case 2: if (n2!=null) { a[j++] = n2; bitmap |= (1<<node.storageToLevelIndex(2)); } break;
1670 case 3: if (n3!=null) { a[j++] = n3; bitmap |= (1<<node.storageToLevelIndex(3)); } break;
1671 case 4: if (n4!=null) { a[j++] = n4; bitmap |= (1<<node.storageToLevelIndex(4)); } break;
1672 case 5: if (n5!=null) { a[j++] = n5; bitmap |= (1<<node.storageToLevelIndex(5)); } break;
1673 case 6: if (n6!=null) { a[j++] = n6; bitmap |= (1<<node.storageToLevelIndex(6)); } break;
1674 case 7: if (n7!=null) { a[j++] = n7; bitmap |= (1<<node.storageToLevelIndex(7)); } break;
1675 case 8: if (n8!=null) { a[j++] = n8; bitmap |= (1<<node.storageToLevelIndex(8)); } break;
1676 case 9: if (n9!=null) { a[j++] = n9; bitmap |= (1<<node.storageToLevelIndex(9)); } break;
1677 case 10: if (n10!=null) { a[j++] = n10; bitmap |= (1<<node.storageToLevelIndex(10)); } break;
1678 case 11: if (n11!=null) { a[j++] = n11; bitmap |= (1<<node.storageToLevelIndex(11)); } break;
1679 case 12: if (n12!=null) { a[j++] = n12; bitmap |= (1<<node.storageToLevelIndex(12)); } break;
1680 case 13: if (n13!=null) { a[j++] = n13; bitmap |= (1<<node.storageToLevelIndex(13)); } break;
1681 case 14: if (n14!=null) { a[j++] = n14; bitmap |= (1<<node.storageToLevelIndex(14)); } break;
1682 case 15: if (n15!=null) { a[j++] = n15; bitmap |= (1<<node.storageToLevelIndex(15)); } break;
1683 case 16: if (n16!=null) { a[j++] = n16; bitmap |= (1<<node.storageToLevelIndex(16)); } break;
1684 case 17: if (n17!=null) { a[j++] = n17; bitmap |= (1<<node.storageToLevelIndex(17)); } break;
1685 case 18: if (n18!=null) { a[j++] = n18; bitmap |= (1<<node.storageToLevelIndex(18)); } break;
1686 case 19: if (n19!=null) { a[j++] = n19; bitmap |= (1<<node.storageToLevelIndex(19)); } break;
1687 case 20: if (n20!=null) { a[j++] = n20; bitmap |= (1<<node.storageToLevelIndex(20)); } break;
1688 case 21: if (n21!=null) { a[j++] = n21; bitmap |= (1<<node.storageToLevelIndex(21)); } break;
1689 case 22: if (n22!=null) { a[j++] = n22; bitmap |= (1<<node.storageToLevelIndex(22)); } break;
1690 case 23: if (n23!=null) { a[j++] = n23; bitmap |= (1<<node.storageToLevelIndex(23)); } break;
1691 case 24: if (n24!=null) { a[j++] = n24; bitmap |= (1<<node.storageToLevelIndex(24)); } break;
1692 case 25: if (n25!=null) { a[j++] = n25; bitmap |= (1<<node.storageToLevelIndex(25)); } break;
1693 case 26: if (n26!=null) { a[j++] = n26; bitmap |= (1<<node.storageToLevelIndex(26)); } break;
1694 case 27: if (n27!=null) { a[j++] = n27; bitmap |= (1<<node.storageToLevelIndex(27)); } break;
1695 case 28: if (n28!=null) { a[j++] = n28; bitmap |= (1<<node.storageToLevelIndex(28)); } break;
1696 case 29: if (n29!=null) { a[j++] = n29; bitmap |= (1<<node.storageToLevelIndex(29)); } break;
1697 case 30: if (n30!=null) { a[j++] = n30; bitmap |= (1<<node.storageToLevelIndex(30)); } break;
1698 case 31: if (n31!=null) { a[j++] = n31; bitmap |= (1<<node.storageToLevelIndex(31)); } break;
1702 return new BitmapNode( bitmap, a);
1707 throw new RuntimeException("can't get here");
1710 public PSIntMap<V> removeAllSatisfying( Predicate<V> pred){
1711 Node<Node> node = rootNode;
1713 if (stagingNode != targetNode){
1714 // we need to merge first since the target node might be gone after bulk removal
1715 node = mergeStagingNode();
1717 node = removeAllSatisfying( rootLevel, node, pred);
1721 int newRootLevel = rootLevel;
1722 int newSize = countSize( newRootLevel, node);
1724 return new PSIntMap<V>( newSize, newRootLevel, node, null, null, 0);
1727 protected final int countSize (int level, Node node){
1733 return node.getNumberOfElements();
1737 int len = node.getNumberOfElements();
1738 for (int i = 0; i < len; i++) {
1739 nValues += countSize(level - 1, (Node) node.getElementAtStorageIndex(i));
1746 public V[] values (){
1747 final Object[] values = new Object[size];
1748 Processor<V> flattener = new Processor<V>(){
1751 public void process (V v){
1763 public void printOn(PrintStream ps) {
1764 if (rootNode != null) {
1765 rootNode.printNodeInfoOn(ps, targetNode, stagingNode);
1767 rootNode.printOn(ps, rootLevel, targetNode, stagingNode);
1769 ps.println( "empty");
1772 if (stagingNode != null) {
1773 ps.println("--------------- staging");
1774 stagingNode.printNodeInfoOn(ps, targetNode, stagingNode);
1776 stagingNode.printOn(ps, 0, targetNode, stagingNode);
1780 public String keyDescription (int key) {
1781 StringBuilder sb = new StringBuilder();
1782 int ish = getStartLevel(key);
1786 sb.append(Integer.toHexString(key));
1789 for (int shift=ish*5; shift>=0; shift-=5) {
1790 sb.append((key>>shift) & 0x1f);
1796 return sb.toString();