src/main/gov/nasa/jpf/util/PSIntMap.java

   1 /*
   2  * Copyright (C) 2014, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   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
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  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.
  17  */
  18
  19 package gov.nasa.jpf.util;
  20
  21 import java.io.PrintStream;
  22 import java.util.Iterator;
  23 import java.util.NoSuchElementException;
  24
  25 /**
  26  * Persistent (immutable) associative array that maps integer keys to generic reference values.
  27  * <p>
  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).
  31  *
  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:
  35  *   ..
  36  *   transition{ ..alloc( n),..alloc(n+1),..alloc(n+2), ..}, garbage-collection{ remove(x),remove(y),..}
  37  *   ..
  38  *
  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
  42  * <blockquote><pre>
  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
  46  *
  47  *       Node0 (level 2 : nodes)
  48  *         ...
  49  *         [12] -> Node1 (level 1 : nodes)
  50  *                   ...
  51  *                   [1] -> Node2 (level 0 : values)
  52  *                            ...
  53  *                           [25] -> 'x'
  54  *</pre></blockquote>
  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.
  59  *
  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).
  66  *
  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:
  71  * <ul>
  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
  75  * </ul>
  76  * Removal of keys leads to symmetric demotion of node types.
  77  *
  78  * The five major public operations for PersistentIntMaps are
  79  *
  80  * <ol>
  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
  87  * </ol>
  88  *
  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:
  92  *
  93  * <blockquote><pre>
  94  *   PSIntMap<String> map = PSIntMap<String>();
  95  *   ..
  96  *   map = map.set(42, "fortytwo"); // returns a new map
  97  *   ..
  98  *   map = map.remove(42); // returns a new map
  99  *   ..
 100  *   map = map.removeAllSatisfying( new Predicate<String>(){ // returns a new map
 101  *     public boolean isTrue (String val){
 102  *       return val.endsWith("two");
 103  *     });
 104  *
 105  *   map.process( new Processor<String>(){
 106  *     public void process (String val){
 107  *       System.out.println(val);
 108  *     });
 109  * </pre></blockquote>
 110  *
 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.
 123  *
 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.
 128  */
 129
 130 public class PSIntMap <V> implements Iterable<V> {
 131
 132   //--- auxiliary types
 133
 134   /**
 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
 137    * invariant data.
 138    *
 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.
 143    */
 144   protected abstract static class Node<E> {
 145
 146     abstract E getElementAtLevelIndex (int i);
 147
 148     abstract int getNumberOfElements();
 149     abstract E getElementAtStorageIndex (int i);
 150
 151     abstract int storageToLevelIndex (int i);
 152
 153     //--- those clone
 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);
 158
 159     //--- no clone
 160     abstract void set (int idx, E e);
 161     abstract void process (int level, Node<E> targetNode, Node<E> stagingNode, Processor<E> p);
 162
 163     boolean isEmptyNode(){
 164       return false;
 165     }
 166
 167     //--- debugging
 168     void printIndentOn (PrintStream ps, int level) {
 169       for (int i=0; i<level; i++) {
 170         ps.print("    ");
 171       }
 172     }
 173
 174     void printNodeInfoOn (PrintStream ps, Node targetNode, Node stagingNode) {
 175       String clsName = getClass().getSimpleName();
 176       int idx = clsName.indexOf('$');
 177       if (idx > 0) {
 178         clsName = clsName.substring(idx+1);
 179       }
 180       ps.print(clsName);
 181
 182       if (this == targetNode){
 183         ps.print( " (target)");
 184       }
 185     }
 186
 187     abstract void printOn(PrintStream ps, int level, Node targetNode, Node stagingNode);
 188   }
 189
 190   /**
 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
 193    */
 194   protected static class OneNode<E> extends Node<E> {
 195     E e;
 196     int idx;
 197
 198     OneNode (int idx, E e){
 199       this.idx = idx;
 200       this.e = e;
 201     }
 202
 203     @Override
 204     int getNumberOfElements(){
 205       return 1;
 206     }
 207
 208     @Override
 209     E getElementAtStorageIndex (int i){
 210       assert i == 0;
 211       return e;
 212     }
 213
 214     @Override
 215     E getElementAtLevelIndex(int i) {
 216       if (i == idx){
 217         return e;
 218       } else {
 219         return null;
 220       }
 221     }
 222
 223     @Override
 224     int storageToLevelIndex (int i){
 225       if (i == 0){
 226         return idx;
 227       }
 228       return -1;
 229     }
 230
 231     /**
 232      * this assumes the index is not set
 233      */
 234     @Override
 235     Node cloneWithAdded(int i, E newElement) {
 236       assert i != idx;
 237
 238       Object[] a = new Object[2];
 239
 240       if (i < idx){
 241         a[0] = newElement;
 242         a[1] = e;
 243       } else {
 244         a[0] = e;
 245         a[1] = newElement;
 246       }
 247       int bitmap = (1 << idx) | (1 << i);
 248
 249       return new BitmapNode(bitmap, a);
 250     }
 251
 252     /**
 253      * this assumes the index is set
 254      */
 255     @Override
 256     Node cloneWithReplaced(int i, E e) {
 257       assert i == idx;
 258       return new OneNode( i, e);
 259     }
 260
 261     /**
 262      * this assumes the index is set
 263      */
 264     @Override
 265     Node cloneWithRemoved(int i){
 266       assert (i == idx);
 267       return null;
 268     }
 269
 270     @Override
 271     Node removeAllSatisfying (Predicate<E> pred){
 272       if (pred.isTrue(e)){
 273         return null;
 274       } else {
 275         return this;
 276       }
 277     }
 278
 279     @Override
 280     void set (int i, E e){
 281       assert i == idx;
 282       this.e = e;
 283     }
 284
 285     @Override
 286     boolean isEmptyNode(){
 287       return idx == 0;
 288     }
 289
 290     @Override
 291     void process (int level, Node<E> targetNode, Node<E> stagingNode, Processor<E> p){
 292       if (level == 0){
 293         if (this == targetNode){
 294           stagingNode.process( 0, null, null, p);
 295         } else {
 296           p.process(e);
 297         }
 298       } else {
 299         ((Node)e).process( level-1, targetNode, stagingNode, p);
 300       }
 301     }
 302
 303     @Override
 304         public void printOn (PrintStream ps, int depth, Node targetNode, Node stagingNode) {
 305       printIndentOn(ps, depth);
 306       ps.printf("%2d: ", idx);
 307
 308       if (e instanceof Node) {
 309         Node<E> n = (Node<E>) e;
 310         n.printNodeInfoOn(ps, targetNode, stagingNode);
 311         ps.println();
 312         n.printOn(ps, depth+1, targetNode, stagingNode);
 313       } else {
 314         ps.print("value=");
 315         ps.println(e);
 316       }
 317     }
 318
 319   }
 320
 321   /**
 322    * A node that holds between 2 and 31 elements.
 323    *
 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
 328    *
 329    * <blockquote><pre>
 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>
 335    *
 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)
 339    *
 340    * <p>
 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
 343    */
 344   protected static class BitmapNode<E> extends Node<E> {
 345     final E[] elements;
 346     final int bitmap;
 347
 348     BitmapNode (int idx, E e, E e0){
 349       bitmap = (1 << idx) | 1;
 350
 351       elements = (E[]) new Object[2];
 352       elements[0] = e0;
 353       elements[1] = e;
 354     }
 355
 356     BitmapNode (int bitmap, E[] elements){
 357       this.bitmap = bitmap;
 358       this.elements = elements;
 359     }
 360
 361     @Override
 362     int getNumberOfElements(){
 363       return elements.length;
 364     }
 365
 366     @Override
 367     E getElementAtStorageIndex (int i){
 368       return elements[i];
 369     }
 370
 371     @Override
 372     E getElementAtLevelIndex (int i) {
 373       int bit = 1 << i;
 374       if ((bitmap & bit) != 0) {
 375         int idx = Integer.bitCount( bitmap & (bit-1));
 376         return elements[idx];
 377       } else {
 378         return null;
 379       }
 380     }
 381
 382     /**
 383      * get the position of the (n+1)'th set bit in bitmap
 384      */
 385     @Override
 386     int storageToLevelIndex (int n){
 387       int v = bitmap;
 388       /**/
 389       switch (n){
 390         case 30: v &= v-1;
 391         case 29: v &= v-1;
 392         case 28: v &= v-1;
 393         case 27: v &= v-1;
 394         case 26: v &= v-1;
 395         case 25: v &= v-1;
 396         case 24: v &= v-1;
 397         case 23: v &= v-1;
 398         case 22: v &= v-1;
 399         case 21: v &= v-1;
 400         case 20: v &= v-1;
 401         case 19: v &= v-1;
 402         case 18: v &= v-1;
 403         case 17: v &= v-1;
 404         case 16: v &= v-1;
 405         case 15: v &= v-1;
 406         case 14: v &= v-1;
 407         case 13: v &= v-1;
 408         case 12: v &= v-1;
 409         case 11: v &= v-1;
 410         case 10: v &= v-1;
 411         case 9: v &= v-1;
 412         case 8: v &= v-1;
 413         case 7: v &= v-1;
 414         case 6: v &= v-1;
 415         case 5: v &= v-1;
 416         case 4: v &= v-1;
 417         case 3: v &= v-1;
 418         case 2: v &= v-1;
 419         case 1: v &= v-1;
 420       }
 421       /**/
 422
 423       /**
 424       for (int i=n; i>0; i--){
 425         v &= v-1; // remove n-1 least significant bits
 426       }
 427       **/
 428
 429       v = v & ~(v-1); // reduce to the least significant bit
 430       return TrailingMultiplyDeBruijnBitPosition[((v & -v) * 0x077CB531) >>> 27];
 431     }
 432
 433     @Override
 434     Node cloneWithAdded(int i, E e) {
 435       int bit = 1 << i;
 436       int idx = Integer.bitCount( bitmap & (bit -1));
 437
 438       if (elements.length == 31){
 439         Object[] a = new Object[32];
 440
 441         if (idx > 0) {
 442           System.arraycopy(elements, 0, a, 0, idx);
 443         }
 444         if (idx < 31) {
 445           System.arraycopy(elements, idx, a, idx + 1, 31 - idx);
 446         }
 447         a[idx] = e;
 448         return new FullNode(a);
 449
 450       } else {
 451         int n = elements.length;
 452         Object[] a = new Object[n + 1];
 453
 454         if (idx > 0) {
 455           System.arraycopy(elements, 0, a, 0, idx);
 456         }
 457
 458         a[idx] = e;
 459
 460         if (n > idx) {
 461           System.arraycopy(elements, idx, a, idx + 1, (n - idx));
 462         }
 463
 464         return new BitmapNode( bitmap | bit, a);
 465       }
 466     }
 467
 468     @Override
 469     Node cloneWithReplaced(int i, E e) {
 470       int idx = Integer.bitCount( bitmap & ((1<<i) -1));
 471
 472       E[] a = elements.clone();
 473       a[idx] = e;
 474
 475       return new BitmapNode( bitmap, a);
 476     }
 477
 478     @Override
 479     Node cloneWithRemoved(int i){
 480       int bit = (1<<i);
 481       int idx = Integer.bitCount( bitmap & (bit-1));
 482       int n = elements.length;
 483
 484       if (n == 2){
 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);
 488
 489       } else {
 490         Object[] a = new Object[n - 1];
 491         if (idx > 0) {
 492           System.arraycopy(elements, 0, a, 0, idx);
 493         }
 494         n--;
 495         if (n > idx) {
 496           System.arraycopy(elements, idx + 1, a, idx, (n - idx));
 497         }
 498         return new BitmapNode(bitmap ^ bit, a);
 499       }
 500     }
 501
 502     @Override
 503     Node removeAllSatisfying (Predicate<E> pred){
 504       int newBitmap = bitmap;
 505       int len = elements.length;
 506       int newLen = len;
 507       E[] elem = elements;
 508       int removed = 0;
 509
 510       for (int i=0, bit=1; i<len; i++, bit<<=1){
 511         while ((newBitmap & bit) == 0){
 512           bit <<= 1;
 513         }
 514
 515         if (pred.isTrue(elem[i])){
 516           newBitmap ^= bit;
 517           newLen--;
 518           removed |= (1 << i);
 519         }
 520       }
 521
 522       if (newLen == 0){ // nothing left
 523         return null;
 524
 525       } else if (newLen == len){ // nothing removed
 526         return this;
 527
 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]);
 532
 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];
 538           }
 539         }
 540         return new BitmapNode( newBitmap, newElements);
 541       }
 542     }
 543
 544
 545     @Override
 546     void set (int i, E e){
 547       int idx = Integer.bitCount( bitmap & ((1<<i) -1));
 548       elements[idx] = e;
 549     }
 550
 551     @Override
 552     void process (int level, Node<E> targetNode, Node<E> stagingNode, Processor<E> p){
 553       if (level == 0){
 554         if (this == targetNode){
 555           stagingNode.process(0, null, null, p);
 556         } else {
 557           for (int i = 0; i < elements.length; i++) {
 558             p.process(elements[i]);
 559           }
 560         }
 561       } else {
 562         for (int i=0; i<elements.length; i++){
 563           ((Node)elements[i]).process(level-1, targetNode, stagingNode, p);
 564         }
 565       }
 566     }
 567
 568     @Override
 569         void printOn (PrintStream ps, int depth, Node targetNode, Node stagingNode) {
 570       int j=0;
 571       for (int i=0; i<32; i++) {
 572         if ((bitmap & (1<<i)) != 0) {
 573           printIndentOn(ps, depth);
 574           ps.printf("%2d: ", i);
 575
 576           E e = elements[j++];
 577           if (e instanceof Node) {
 578             Node<E> n = (Node<E>)e;
 579             n.printNodeInfoOn(ps, targetNode, stagingNode);
 580             ps.println();
 581             n.printOn(ps, depth+1, targetNode, stagingNode);
 582           } else {
 583             ps.print("value=");
 584             ps.println(e);
 585           }
 586         }
 587       }
 588     }
 589
 590   }
 591
 592   /**
 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
 596    */
 597   protected static class FullNode<E> extends Node<E> {
 598     final E[] elements;
 599
 600     FullNode (E[] elements){
 601       this.elements = elements;
 602     }
 603
 604     @Override
 605     int getNumberOfElements(){
 606       return 32;
 607     }
 608
 609     @Override
 610     E getElementAtStorageIndex (int i){
 611       return elements[i];
 612     }
 613
 614     @Override
 615     E getElementAtLevelIndex (int i) {
 616       return elements[i];
 617     }
 618
 619     @Override
 620     int storageToLevelIndex (int i){
 621       return i;
 622     }
 623
 624
 625     @Override
 626     Node cloneWithAdded (int idx, E e){
 627       throw new RuntimeException("can't add a new element to a FullNode");
 628     }
 629
 630     @Override
 631     Node cloneWithReplaced (int idx, E e){
 632       E[] newElements = elements.clone();
 633       newElements[idx] = e;
 634       return new FullNode(newElements);
 635     }
 636
 637     @Override
 638     Node cloneWithRemoved(int idx){
 639       Object[] a = new Object[31];
 640       int bitmap = 0xffffffff ^ (1 << idx);
 641
 642       if (idx > 0){
 643         System.arraycopy(elements, 0, a, 0, idx);
 644       }
 645       if (idx < 31){
 646         System.arraycopy(elements, idx+1, a, idx, 31-idx);
 647       }
 648
 649       return new BitmapNode( bitmap, a);
 650     }
 651
 652     @Override
 653     Node removeAllSatisfying (Predicate<E> pred){
 654       int newBitmap = 0xffffffff;
 655       int newLen = 32;
 656       E[] elem = elements;
 657       int removed = 0;
 658
 659       for (int i=0, bit=1; i<32; i++, bit<<=1){
 660         if (pred.isTrue(elem[i])){
 661           newBitmap ^= bit;
 662           newLen--;
 663           removed |= (1 << i);
 664         }
 665       }
 666
 667       if (newLen == 0){ // nothing left
 668         return null;
 669
 670       } else if (newLen == 32){ // nothing removed
 671         return this;
 672
 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]);
 676
 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];
 682           }
 683         }
 684         return new BitmapNode( newBitmap, newElements);
 685       }
 686     }
 687
 688     @Override
 689     void set (int i, E e){
 690       elements[i] = e;
 691     }
 692
 693     @Override
 694     void process (int level, Node<E> targetNode, Node<E> stagingNode, Processor<E> p){
 695       if (level == 0){
 696         if (this == targetNode){
 697           stagingNode.process(0, null, null, p);
 698         } else {
 699           for (int i = 0; i < elements.length; i++) {
 700             p.process(elements[i]);
 701           }
 702         }
 703       } else {
 704         for (int i=0; i<elements.length; i++){
 705           ((Node)elements[i]).process(level-1, targetNode, stagingNode, p);
 706         }
 707       }
 708     }
 709
 710     @Override
 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);
 715
 716         E e = elements[i];
 717         if (e instanceof Node) {
 718           Node<E> n = (Node<E>) e;
 719           n.printNodeInfoOn(ps, targetNode, stagingNode);
 720           ps.println();
 721           n.printOn(ps, depth+1, targetNode, stagingNode);
 722         } else {
 723           ps.print("value=");
 724           ps.println(e);
 725         }
 726       }
 727     }
 728   }
 729
 730   @Override
 731 @SuppressWarnings({ "rawtypes", "unchecked" })
 732   public Iterator<V> iterator(){
 733     return new ValueIterator();
 734   }
 735
 736   /**
 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)
 740    *
 741    * Note - there are no empty nodes. Each one has at least newElements single child node or value
 742    */
 743   protected class ValueIterator implements Iterator<V> {
 744
 745     Node node;
 746     int nodeIdx, maxNodeIdx;
 747
 748     Node[] parentNodeStack;
 749     int[] parentIdxStack;
 750     int top;
 751     int nVisited, nTotal;
 752
 753
 754     @SuppressWarnings("unchecked")
 755     public ValueIterator (){
 756       node = PSIntMap.this.rootNode;
 757       if (node != null) {
 758         if (node == PSIntMap.this.targetNode){
 759           node = PSIntMap.this.stagingNode;
 760         }
 761
 762         maxNodeIdx = node.getNumberOfElements();
 763
 764         // nodeIdx = 0;
 765         // nVisited = 0;
 766         // top = 0;
 767
 768         int depth = PSIntMap.this.rootLevel;
 769         parentNodeStack = new Node[depth];
 770         parentIdxStack = new int[depth];
 771
 772         nTotal = PSIntMap.this.size;
 773       }
 774     }
 775
 776     @Override
 777     public boolean hasNext() {
 778       return nVisited < nTotal;
 779     }
 780
 781     @Override
 782     @SuppressWarnings("unchecked")
 783     public V next() {
 784       if (nVisited >= nTotal) {
 785         throw new NoSuchElementException();
 786       }
 787
 788       int idx = nodeIdx;
 789       Object nv = node.getElementAtStorageIndex( idx);
 790
 791       //--- descend
 792       while (top < PSIntMap.this.rootLevel) {
 793         parentNodeStack[top] = node; // push current node on stack
 794         parentIdxStack[top] = idx;
 795         top++;
 796
 797         if (nv == PSIntMap.this.targetNode){
 798           node = PSIntMap.this.stagingNode;
 799         } else {
 800           node = (Node)nv;
 801         }
 802
 803         idx = nodeIdx = 0;
 804         maxNodeIdx = node.getNumberOfElements();
 805
 806         nv = node.getElementAtStorageIndex(0);
 807       }
 808
 809       //--- newElements value, finally
 810       nVisited++;
 811       idx++;
 812
 813       if (idx == maxNodeIdx) { // done, no more child nodes/values for this node
 814         while (top > 0) { // go up
 815           top--;
 816           node = parentNodeStack[top];
 817           nodeIdx = parentIdxStack[top] + 1;
 818           maxNodeIdx = node.getNumberOfElements();
 819           if (nodeIdx < maxNodeIdx) break;
 820         }
 821       } else {
 822         nodeIdx = idx;
 823       }
 824
 825       //assert (nVisited == nTotal) || (nodeIdx < maxNodeIdx);
 826       return (V) nv;
 827     }
 828
 829     @Override
 830     public void remove() {
 831       throw new UnsupportedOperationException("PersistentIntMap iterators don't support removal");
 832     }
 833
 834   }
 835
 836
 837   //--- auxiliary data and functions
 838
 839   static final int BASE_MASK = ~0x1f;
 840
 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
 844   };
 845
 846   static int getNumberOfTrailingZeros (int v){
 847     return TrailingMultiplyDeBruijnBitPosition[((v & -v) * 0x077CB531) >>> 27];
 848   }
 849
 850
 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
 855   };
 856
 857   /**
 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
 860    */
 861   static int getStartLevel (int v){
 862     v |= v >>> 1;
 863     v |= v >>> 2;
 864     v |= v >>> 4;
 865     v |= v >>> 8;
 866     v |= v >>> 16;
 867
 868     return LeadingMultiplyDeBruijnBitPosition[(v * 0x07C4ACDD) >>> 27];
 869   }
 870
 871   //--- instance data
 872
 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
 876
 877   /*
 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:
 887    *                                          key    value
 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
 890    *
 891    *                            a
 892    *                    n0: [...n1...]            root node (level 2)
 893    *                           /
 894    *                 b    c   /
 895    *          n1:  [.n2...n3.]
 896    *                /       \
 897    *           d   /         \                                                  e
 898    *    n2:  [.X..]      n3:  [.....]             value nodes (level 0)     [...Y...]
 899    *      new stagingNode       old targetNode  <-------------------------- old stagingNode
 900    *    (= new targetNode)
 901    *
 902    * In this case, the sequence of operations is as follows:
 903    * <ol>
 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
 915    * </ol>
 916    */
 917
 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
 921
 922   /**
 923    * the only public constructor
 924    */
 925   public PSIntMap(){
 926     this.size = 0;
 927     this.rootLevel = 0;
 928     this.rootNode = null;
 929     this.targetNode = null;
 930     this.stagingNode = null;
 931     this.stagingNodeMask = 0;
 932   }
 933
 934   protected PSIntMap (int size, int rootLevel, Node rootNode, Node<V> stagingNode, Node<V> targetNode, int stagingNodeMask){
 935     this.size = size;
 936     this.rootLevel = rootLevel;
 937     this.rootNode = rootNode;
 938     this.stagingNode = stagingNode;
 939     this.targetNode = targetNode;
 940     this.stagingNodeMask = stagingNodeMask;
 941   }
 942
 943   //--- public API
 944
 945   public int size(){
 946     return size;
 947   }
 948
 949   public V get (int key){
 950     if (stagingNodeMask == (key | 0x1f)){
 951       int idx = key & 0x1f;
 952       return stagingNode.getElementAtLevelIndex(idx);
 953
 954     } else {
 955       if (rootNode == null) return null;
 956
 957       int l = getStartLevel(key);
 958       if (l > rootLevel) return null;
 959
 960       Node<Node> n = rootNode;
 961
 962       switch (rootLevel){
 963         case 6:
 964           n = n.getElementAtLevelIndex( key >>> 30);
 965           if (n == null) return null;
 966         case 5:
 967           n = n.getElementAtLevelIndex( (key >>> 25) & 0x1f);
 968           if (n == null) return null;
 969         case 4:
 970           n = n.getElementAtLevelIndex( (key >>> 20) & 0x1f);
 971           if (n == null) return null;
 972         case 3:
 973           n = n.getElementAtLevelIndex( (key >>> 15) & 0x1f);
 974           if (n == null) return null;
 975         case 2:
 976           n = n.getElementAtLevelIndex( (key >>> 10) & 0x1f);
 977           if (n == null) return null;
 978         case 1:
 979           n = n.getElementAtLevelIndex( (key >>>  5) & 0x1f);
 980           if (n == null) return null;
 981         case 0:
 982           return ((Node<V>)n).getElementAtLevelIndex(key & 0x1f);
 983       }
 984
 985       return null; // can't get here
 986     }
 987   }
 988
 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;
 992
 993     int k = stagingNodeMask;
 994     Node<Node> n = rootNode;
 995
 996     switch (rootLevel){
 997       case 6:
 998         i6 = (k >>> 30);
 999         n6 = n;
1000         n = n.getElementAtLevelIndex(i6);
1001       case 5:
1002         i5 = (k >>> 25) & 0x1f;
1003         n5 = n;
1004         n = n.getElementAtLevelIndex(i5);
1005       case 4:
1006         i4 = (k >>> 20) & 0x1f;
1007         n4 = n;
1008         n = n.getElementAtLevelIndex(i4);
1009       case 3:
1010         i3 = (k >>> 15) & 0x1f;
1011         n3 = n;
1012         n = n.getElementAtLevelIndex(i3);
1013       case 2:
1014         i2 = (k >>> 10) & 0x1f;
1015         n2 = n;
1016         n = n.getElementAtLevelIndex(i2);
1017       case 1:
1018         i1 = (k >>> 5) & 0x1f;
1019         n = n.cloneWithReplaced(i1, stagingNode);
1020         if (n2 != null){
1021           n = n2.cloneWithReplaced(i2, n);
1022           if (n3 != null){
1023             n = n3.cloneWithReplaced(i3, n);
1024             if (n4 != null){
1025               n = n4.cloneWithReplaced(i4, n);
1026               if (n5 != null){
1027                 n = n5.cloneWithReplaced(i5, n);
1028                 if (n6 != null){
1029                   n = n6.cloneWithReplaced(i6, n);
1030                 }
1031               }
1032             }
1033           }
1034         }
1035         return n;
1036
1037       case 0:
1038         // special case - only node in the trie is the targetNode
1039         return stagingNode;
1040     }
1041
1042     return null; //  can't get here
1043   }
1044
1045   /**
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
1052    * as it is new)
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.
1055    */
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;
1061
1062     //--- get the mergeNode
1063     for (int l=newRootLevel; l>mergeLevel; l--){
1064       int idx = (k >>> shift) & 0x1f;
1065       mergeNode = mergeNode.getElementAtLevelIndex(idx);
1066       shift -= 5;
1067     }
1068     int mergeIdx = (k >>> shift) & 0x1f;
1069
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);
1074
1075     switch (mergeLevel-1){
1076       case 5:
1077         i5 = (k >>> 25) & 0x1f;
1078         n5 = n;
1079         n = n.getElementAtLevelIndex(i5);
1080       case 4:
1081         i4 = (k >>> 20) & 0x1f;
1082         n4 = n;
1083         n = n.getElementAtLevelIndex(i4);
1084       case 3:
1085         i3 = (k >>> 15) & 0x1f;
1086         n3 = n;
1087         n = n.getElementAtLevelIndex(i3);
1088       case 2:
1089         i2 = (k >>> 10) & 0x1f;
1090         n2 = n;
1091         n = n.getElementAtLevelIndex(i2);
1092       case 1:
1093         i1 = (k >>> 5) & 0x1f;
1094         n1 = n;
1095       case 0:
1096         n = (Node)stagingNode;
1097
1098         if (n1 != null){
1099           n = n1.cloneWithReplaced(i1, n);
1100           if (n2 != null) {
1101             n = n2.cloneWithReplaced(i2, n);
1102             if (n3 != null) {
1103               n = n3.cloneWithReplaced(i3, n);
1104               if (n4 != null) {
1105                 n = n4.cloneWithReplaced(i4, n);
1106                 if (n5 != null) {
1107                   n = n5.cloneWithReplaced(i5, n);
1108                 }
1109               }
1110             }
1111           }
1112         }
1113     }
1114
1115     //--- modify mergeNode
1116     mergeNode.set(mergeIdx, n);
1117   }
1118
1119   PSIntMap<V> remove (int key, boolean isTargetNode){
1120     Node<Node> n6=null, n5=null, n4=null, n3=null, n2=null, n1=null;
1121     Node<V> n0;
1122     int i6=0, i5=0, i4=0, i3=0, i2=0, i1=0, i0;
1123
1124     Node<Node> n = rootNode;
1125     switch (rootLevel){
1126       case 6:
1127         i6 = (key >>> 30);
1128         n5 = n.getElementAtLevelIndex(i6);
1129         if (n5 == null){
1130           return this; // key not in map
1131         } else {
1132           n6 = n;
1133           n = n5;
1134         }
1135       case 5:
1136         i5 = (key >>> 25) & 0x1f;
1137         n4 = n.getElementAtLevelIndex(i5);
1138         if (n4 == null){
1139           return this; // key not in map
1140         } else {
1141           n5 = n;
1142           n = n4;
1143         }
1144       case 4:
1145         i4 = (key >>> 20) & 0x1f;
1146         n3 = n.getElementAtLevelIndex(i4);
1147         if (n3 == null){
1148           return this; // key not in map
1149         } else {
1150           n4 = n;
1151           n = n3;
1152         }
1153       case 3:
1154         i3 = (key >>> 15) & 0x1f;
1155         n2 = n.getElementAtLevelIndex(i3);
1156         if (n2 == null){
1157           return this; // key not in map
1158         } else {
1159           n3 = n;
1160           n = n2;
1161         }
1162       case 2:
1163         i2 = (key >>> 10) & 0x1f;
1164         n1 = n.getElementAtLevelIndex(i2);
1165         if (n1 == null){
1166           return this; // key not in map
1167         } else {
1168           n2 = n;
1169           n = n1;
1170         }
1171       case 1:
1172         i1 = (key >>> 5) & 0x1f;
1173         n0 = n.getElementAtLevelIndex(i1);
1174         if (n0 == null){
1175           return null;
1176         } else {
1177           n1 = n;
1178           n = (Node)n0;
1179         }
1180
1181       case 0:
1182         n0 = (Node<V>)n;
1183         if (isTargetNode){
1184           n0 = null;
1185         } else {
1186           i0 = key & 0x1f;
1187           if (n0 == null || n0.getElementAtLevelIndex(i0) == null){
1188             return this; // key not in map
1189           } else {
1190             n0 = n0.cloneWithRemoved(i0);
1191           }
1192         }
1193         n = (Node)n0;
1194         if (n1 != null){
1195           n = (n == null) ? n1.cloneWithRemoved(i1) : n1.cloneWithReplaced(i1, n);
1196           if (n2 != null){
1197             n = (n == null) ? n2.cloneWithRemoved(i2) : n2.cloneWithReplaced(i2, n);
1198             if (n3 != null){
1199               n = (n == null) ? n3.cloneWithRemoved(i3) : n3.cloneWithReplaced(i3, n);
1200               if (n4 != null){
1201                 n = (n == null) ? n4.cloneWithRemoved(i4) : n4.cloneWithReplaced(i4, n);
1202                 if (n5 != null){
1203                   n = (n == null) ? n5.cloneWithRemoved(i5) : n5.cloneWithReplaced(i5, n);
1204                   if (n6 != null){
1205                     n = (n == null) ? n6.cloneWithRemoved(i6) : n6.cloneWithReplaced(i6, n);
1206                   }
1207                 }
1208               }
1209             }
1210           }
1211         }
1212
1213         if (n == null){
1214           return new PSIntMap<V>();
1215
1216         } else {
1217           int newRootLevel = rootLevel;
1218           int newSb = (n0 == null) ? 0 : (key | 0x1f);
1219
1220           while ((newRootLevel > 0) && n.isEmptyNode()){
1221             newRootLevel--;
1222             n = n.getElementAtLevelIndex(0);
1223           }
1224
1225           if (!isTargetNode && (stagingNode != targetNode)){
1226             mergeStagingNode(key, newRootLevel, n);
1227           }
1228
1229           return new PSIntMap<V>( size-1, newRootLevel, n, n0, n0, newSb);
1230         }
1231     }
1232
1233     return null; // can't get here
1234   }
1235
1236   public PSIntMap<V> remove (int key){
1237     int newSm = key | 0x1f;
1238
1239     if (newSm == stagingNodeMask){ // staging node hit - this should be the dominant case
1240       int i = key & 0x1f;
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);
1248         }
1249
1250       } else { // key wasn't in the stagingNode
1251         return this;
1252       }
1253
1254     } else { // staging node miss
1255       return remove( key, false);
1256     }
1257   }
1258
1259   /**
1260    * this either replaces or adds newElements new value
1261    */
1262   public PSIntMap<V> set (int key, V value){
1263
1264     if (value == null){
1265       // we don't store null values, this is a remove in disguise
1266       return remove(key);
1267     }
1268
1269     int newSm = key | 0x1f;
1270
1271     if (newSm == stagingNodeMask){ // staging node hit - this should be the dominant case
1272       int i = key & 0x1f;
1273       Node<V> n = stagingNode;
1274       int newSize = size;
1275       if ((n.getElementAtLevelIndex(i)) == null) {
1276         n = n.cloneWithAdded(i, value);
1277         newSize = size+1;
1278       } else {
1279         n = n.cloneWithReplaced(i, value);
1280       }
1281       return new PSIntMap<V>( newSize, rootLevel, rootNode, n, targetNode, newSm);
1282
1283     } else { // staging node miss
1284       int newRootLevel = getStartLevel(key);
1285
1286       if (newRootLevel > rootLevel){ // old trie has to be merged in
1287         return setInNewRootLevel( newRootLevel, key, value);
1288
1289       } else {     // new value can be added to old trie (stagingNode change)
1290         return setInCurrentRootLevel( key, value);
1291       }
1292     }
1293   }
1294
1295   protected PSIntMap<V> setInNewRootLevel (int newRootLevel, int key, V value){
1296     int newSm = key | 0x1f;
1297
1298     Node<Node> nOld;
1299     if (stagingNode != targetNode){
1300       nOld = mergeStagingNode();
1301     } else {
1302       nOld = rootNode;
1303     }
1304
1305     //--- expand old root upwards
1306     if (nOld != null){
1307       for (int l = rootLevel + 1; l < newRootLevel; l++) {
1308         nOld = new OneNode(0, nOld);
1309       }
1310     }
1311
1312     //--- create chain of new value nodes
1313     int i = key & 0x1f;
1314     Node nNew = new OneNode(i, value);
1315     int shift = 5;
1316     Node newStagingNode = nNew;
1317     for (int l = 1; l < newRootLevel; l++) {
1318       i = (key >>> shift) & 0x1f;
1319       nNew = new OneNode(i, nNew);
1320       shift += 5;
1321     }
1322
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);
1326
1327     return new PSIntMap<V>(size + 1, newRootLevel, newRootNode, newStagingNode, newStagingNode, newSm);
1328   }
1329
1330   /**
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
1334    */
1335   protected PSIntMap<V> setInCurrentRootLevel (int key, V value){
1336     Node<Node> n6=null, n5=null, n4=null, n3=null, n2=null, n1=null;
1337     Node<V> n0;
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;
1342
1343     //--- new stagingNode
1344     Node<Node> n = rootNode;
1345
1346     switch(rootLevel){
1347       case 6:
1348         i6 = key >>> 30;
1349         n5 = n.getElementAtLevelIndex(i6);
1350         if (n5 == null) {
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);
1360
1361         } else {
1362           n6 = n;
1363           n = n5;
1364         }
1365
1366       case 5:
1367         i5 = (key >>> 25) & 0x1f;
1368         n4 = n.getElementAtLevelIndex(i5);
1369         if (n4 == null) {
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);
1376
1377           if (n6 != null){
1378             n = n6.cloneWithReplaced( i6, n);
1379           }
1380           if (needsMerge) mergeStagingNode(key, rootLevel, n);
1381           return new PSIntMap<V>( newSize, rootLevel, n, n0, n0, newSb);
1382
1383         } else {
1384           n5 = n;
1385           n = n4;
1386         }
1387
1388       case 4:
1389         i4 = (key >>> 20) & 0x1f;
1390         n3 = n.getElementAtLevelIndex(i4);
1391         if (n3 == null) {
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);
1397
1398           if (n5 != null){
1399             n = n5.cloneWithReplaced( i5, n);
1400             if (n6 != null){
1401               n = n6.cloneWithReplaced( i6, n);
1402             }
1403           }
1404           if (needsMerge) mergeStagingNode(key, rootLevel, n);
1405           return new PSIntMap<V>( newSize, rootLevel, n, n0, n0, newSb);
1406
1407         } else {
1408           n4 = n;
1409           n = n3;
1410         }
1411
1412       case 3:
1413         i3 = (key >>> 15) & 0x1f;
1414         n2 = n.getElementAtLevelIndex(i3);
1415         if (n2 == null) {
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);
1420
1421           if (n4 != null){
1422             n = n4.cloneWithReplaced( i4, n);
1423             if (n5 != null){
1424               n = n5.cloneWithReplaced( i5, n);
1425               if (n6 != null){
1426                 n = n6.cloneWithReplaced( i6, n);
1427               }
1428             }
1429           }
1430           if (needsMerge) mergeStagingNode(key, rootLevel, n);
1431           return new PSIntMap<V>( newSize, rootLevel, n, n0, n0, newSb);
1432
1433         } else {
1434           n3 = n;
1435           n = n2;
1436         }
1437
1438       case 2:
1439         i2 = (key >>> 10) & 0x1f;
1440         n1 = n.getElementAtLevelIndex(i2);
1441         if (n1 == null) {
1442           n0 = new OneNode( (key & 0x1f), value);
1443           n1 = new OneNode( (key >>> 5) & 0x1f, n0);
1444           n = n.cloneWithAdded( i2, n1);
1445
1446           if (n3 != null){
1447             n = n3.cloneWithReplaced( i3, n);
1448             if (n4 != null){
1449               n = n4.cloneWithReplaced( i4, n);
1450               if (n5 != null){
1451                 n = n5.cloneWithReplaced( i5, n);
1452                 if (n6 != null){
1453                   n = n6.cloneWithReplaced( i6, n);
1454                 }
1455               }
1456             }
1457           }
1458           if (needsMerge) mergeStagingNode(key, rootLevel, n);
1459           return new PSIntMap<V>( newSize, rootLevel, n, n0, n0, newSb);
1460
1461         } else {
1462           n2 = n;
1463           n = n1;
1464         }
1465
1466       case 1:
1467         i1 = (key >>> 5) & 0x1f;
1468         n0 = n.getElementAtLevelIndex(i1);
1469         if (n0 == null) {
1470           n0 = new OneNode( (key & 0x1f), value);
1471           n = n.cloneWithAdded( i1, n0);
1472
1473           if (n2 != null){
1474             n = n2.cloneWithReplaced( i2, n);
1475             if (n3 != null){
1476               n = n3.cloneWithReplaced( i3, n);
1477               if (n4 != null){
1478                 n = n4.cloneWithReplaced( i4, n);
1479                 if (n5 != null){
1480                   n = n5.cloneWithReplaced( i5, n);
1481                   if (n6 != null){
1482                     n = n6.cloneWithReplaced( i6, n);
1483                   }
1484                 }
1485               }
1486             }
1487           }
1488           if (needsMerge) mergeStagingNode(key, rootLevel, n);
1489           return new PSIntMap<V>( newSize, rootLevel, n, n0, n0, newSb);
1490
1491         } else {
1492           n1 = n;
1493           n = (Node)n0;
1494         }
1495
1496       case 0: // finally the value level
1497         i0 = key & 0x1f;
1498         n0 = (Node<V>)n;
1499         if (n0 != null){
1500           if (n0.getElementAtLevelIndex(i0) == null) {
1501             n0 = n0.cloneWithAdded(i0, value);
1502           } else {
1503             n0 = n0.cloneWithReplaced(i0, value);
1504             newSize = size;
1505           }
1506         } else { // first node
1507           n0 = new OneNode( i0, value);
1508           newSize = 1;
1509         }
1510
1511         n = (Node)n0;
1512         if (n1 != null){
1513           n = n1.cloneWithReplaced( i1, n);
1514           if (n2 != null){
1515             n = n2.cloneWithReplaced( i2, n);
1516             if (n3 != null){
1517               n = n3.cloneWithReplaced( i3, n);
1518               if (n4 != null){
1519                 n = n4.cloneWithReplaced( i4, n);
1520                 if (n5 != null){
1521                   n = n5.cloneWithReplaced( i5, n);
1522                   if (n6 != null){
1523                     n = n6.cloneWithReplaced( i6, n);
1524                   }
1525                 }
1526               }
1527             }
1528           }
1529         }
1530         if (needsMerge) mergeStagingNode( key, rootLevel, n);
1531         return new PSIntMap<V>( newSize, rootLevel, n, n0, n0, newSb);
1532     }
1533
1534     return null; // can't get here
1535   }
1536
1537
1538   public void process (Processor<V> p){
1539     if (rootNode != null){
1540       if (targetNode == stagingNode){
1541         rootNode.process( rootLevel, null, null, p);
1542       } else {
1543         rootNode.process( rootLevel, targetNode, stagingNode, p);
1544       }
1545     }
1546   }
1547
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);
1551
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();
1559
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);
1564         if (n != null){
1565           nRemaining++;
1566           if (n != e){
1567             nChanged++;
1568           }
1569           switch (i){
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;
1602           }
1603         }
1604       }
1605
1606       //--- construct the returned node
1607       if (nRemaining == 0){
1608         return null;
1609
1610       } else if ((nRemaining == len) && (nChanged == 0)){
1611         return node;
1612
1613       } else {
1614         if (nRemaining == 1){ // becomes a OneNode
1615           for (int i=0; i<32; i++){
1616             switch (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;
1649             }
1650           }
1651
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};
1656
1657           return new FullNode(a);
1658
1659         } else {
1660           int bitmap = 0;
1661           Node[] a = new Node[nRemaining];
1662           int j=0;
1663
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++){
1666             switch (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;
1699             }
1700           }
1701
1702           return new BitmapNode( bitmap, a);
1703         }
1704       }
1705     }
1706
1707     throw new RuntimeException("can't get here");
1708   }
1709
1710   public PSIntMap<V> removeAllSatisfying( Predicate<V> pred){
1711     Node<Node> node = rootNode;
1712
1713     if (stagingNode != targetNode){
1714       // we need to merge first since the target node might be gone after bulk removal
1715       node = mergeStagingNode();
1716     }
1717     node = removeAllSatisfying( rootLevel, node, pred);
1718
1719     // reduce depth
1720
1721     int newRootLevel = rootLevel;
1722     int newSize = countSize( newRootLevel, node);
1723
1724     return new PSIntMap<V>( newSize, newRootLevel, node, null, null, 0);
1725   }
1726
1727   protected final int countSize (int level, Node node){
1728     if (node == null){
1729       return 0;
1730
1731     } else {
1732       if (level == 0) {
1733         return node.getNumberOfElements();
1734
1735       } else {
1736         int nValues = 0;
1737         int len = node.getNumberOfElements();
1738         for (int i = 0; i < len; i++) {
1739           nValues += countSize(level - 1, (Node) node.getElementAtStorageIndex(i));
1740         }
1741         return nValues;
1742       }
1743     }
1744   }
1745
1746   public V[] values (){
1747     final Object[] values = new Object[size];
1748     Processor<V> flattener = new Processor<V>(){
1749       int i=0;
1750       @Override
1751         public void process (V v){
1752         values[i] = v;
1753       }
1754     };
1755
1756     process(flattener);
1757
1758     return (V[])values;
1759   }
1760
1761   //--- debugging
1762
1763   public void printOn(PrintStream ps) {
1764     if (rootNode != null) {
1765       rootNode.printNodeInfoOn(ps, targetNode, stagingNode);
1766       ps.println();
1767       rootNode.printOn(ps, rootLevel, targetNode, stagingNode);
1768     } else {
1769       ps.println( "empty");
1770     }
1771
1772     if (stagingNode != null) {
1773       ps.println("--------------- staging");
1774       stagingNode.printNodeInfoOn(ps, targetNode, stagingNode);
1775       ps.println();
1776       stagingNode.printOn(ps, 0, targetNode, stagingNode);
1777     }
1778   }
1779
1780   public String keyDescription (int key) {
1781     StringBuilder sb = new StringBuilder();
1782     int ish = getStartLevel(key);
1783
1784     sb.append(key);
1785     sb.append(" (0x");
1786     sb.append(Integer.toHexString(key));
1787     sb.append(") => ");
1788
1789     for (int shift=ish*5; shift>=0; shift-=5) {
1790       sb.append((key>>shift) & 0x1f);
1791       if (shift > 0) {
1792         sb.append('.');
1793       }
1794     }
1795
1796     return sb.toString();
1797   }
1798
1799 }