Java > Open Source Codes > org > apache > commons > collections > bidimap > TreeBidiMap


1 /*
2  * Copyright 2001-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package org.apache.commons.collections.bidimap;
17
18 import java.util.AbstractSet ;
19 import java.util.Collection ;
20 import java.util.ConcurrentModificationException ;
21 import java.util.Iterator ;
22 import java.util.Map ;
23 import java.util.NoSuchElementException ;
24 import java.util.Set ;
25
26 import org.apache.commons.collections.BidiMap;
27 import org.apache.commons.collections.KeyValue;
28 import org.apache.commons.collections.MapIterator;
29 import org.apache.commons.collections.OrderedBidiMap;
30 import org.apache.commons.collections.OrderedIterator;
31 import org.apache.commons.collections.OrderedMapIterator;
32 import org.apache.commons.collections.iterators.EmptyOrderedMapIterator;
33 import org.apache.commons.collections.keyvalue.UnmodifiableMapEntry;
34
35 /**
36  * Red-Black tree-based implementation of BidiMap where all objects added
37  * implement the <code>Comparable</code> interface.
38  * <p>
39  * This class guarantees that the map will be in both ascending key order
40  * and ascending value order, sorted according to the natural order for
41  * the key's and value's classes.
42  * <p>
43  * This Map is intended for applications that need to be able to look
44  * up a key-value pairing by either key or value, and need to do so
45  * with equal efficiency.
46  * <p>
47  * While that goal could be accomplished by taking a pair of TreeMaps
48  * and redirecting requests to the appropriate TreeMap (e.g.,
49  * containsKey would be directed to the TreeMap that maps values to
50  * keys, containsValue would be directed to the TreeMap that maps keys
51  * to values), there are problems with that implementation.
52  * If the data contained in the TreeMaps is large, the cost of redundant
53  * storage becomes significant. The {@link DualTreeBidiMap} and
54  * {@link DualHashBidiMap} implementations use this approach.
55  * <p>
56  * This solution keeps minimizes the data storage by holding data only once.
57  * The red-black algorithm is based on java util TreeMap, but has been modified
58  * to simultaneously map a tree node by key and by value. This doubles the
59  * cost of put operations (but so does using two TreeMaps), and nearly doubles
60  * the cost of remove operations (there is a savings in that the lookup of the
61  * node to be removed only has to be performed once). And since only one node
62  * contains the key and value, storage is significantly less than that
63  * required by two TreeMaps.
64  * <p>
65  * The Map.Entry instances returned by the appropriate methods will
66  * not allow setValue() and will throw an
67  * UnsupportedOperationException on attempts to call that method.
68  *
69  * @since Commons Collections 3.0 (previously DoubleOrderedMap v2.0)
70  * @version $Revision: 1.14 $ $Date: 2004/05/26 21:58:02 $
71  *
72  * @author Marc Johnson
73  * @author Stephen Colebourne
74  */
75 public class TreeBidiMap implements OrderedBidiMap {
76
77     private static final int KEY = 0;
78     private static final int VALUE = 1;
79     private static final int MAPENTRY = 2;
80     private static final int INVERSEMAPENTRY = 3;
81     private static final int SUM_OF_INDICES = KEY + VALUE;
82     private static final int FIRST_INDEX = 0;
83     private static final int NUMBER_OF_INDICES = 2;
84     private static final String [] dataName = new String [] { "key", "value" };
85     
86     private Node[] rootNode = new Node[2];
87     private int nodeCount = 0;
88     private int modifications = 0;
89     private Set keySet;
90     private Set valuesSet;
91     private Set entrySet;
92     private TreeBidiMap.Inverse inverse = null;
93
94     //-----------------------------------------------------------------------
95 /**
96      * Constructs a new empty TreeBidiMap.
97      */
98     public TreeBidiMap() {
99         super();
100     }
101
102     /**
103      * Constructs a new TreeBidiMap by copying an existing Map.
104      *
105      * @param map the map to copy
106      * @throws ClassCastException if the keys/values in the map are
107      * not Comparable or are not mutually comparable
108      * @throws NullPointerException if any key or value in the map is null
109      */
110     public TreeBidiMap(final Map map) {
111         super();
112         putAll(map);
113     }
114
115     //-----------------------------------------------------------------------
116 /**
117      * Returns the number of key-value mappings in this map.
118      *
119      * @return the number of key-value mappings in this map
120      */
121     public int size() {
122         return nodeCount;
123     }
124
125     /**
126      * Checks whether the map is empty or not.
127      *
128      * @return true if the map is empty
129      */
130     public boolean isEmpty() {
131         return (nodeCount == 0);
132     }
133
134     /**
135      * Checks whether this map contains the a mapping for the specified key.
136      * <p>
137      * The key must implement <code>Comparable</code>.
138      *
139      * @param key key whose presence in this map is to be tested
140      * @return true if this map contains a mapping for the specified key
141      * @throws ClassCastException if the key is of an inappropriate type
142      * @throws NullPointerException if the key is null
143      */
144     public boolean containsKey(final Object key) {
145         checkKey(key);
146         return (lookup((Comparable ) key, KEY) != null);
147     }
148
149     /**
150      * Checks whether this map contains the a mapping for the specified value.
151      * <p>
152      * The value must implement <code>Comparable</code>.
153      *
154      * @param value value whose presence in this map is to be tested
155      * @return true if this map contains a mapping for the specified value
156      * @throws ClassCastException if the value is of an inappropriate type
157      * @throws NullPointerException if the value is null
158      */
159     public boolean containsValue(final Object value) {
160         checkValue(value);
161         return (lookup((Comparable ) value, VALUE) != null);
162     }
163
164     /**
165      * Gets the value to which this map maps the specified key.
166      * Returns null if the map contains no mapping for this key.
167      * <p>
168      * The key must implement <code>Comparable</code>.
169      *
170      * @param key key whose associated value is to be returned
171      * @return the value to which this map maps the specified key,
172      * or null if the map contains no mapping for this key
173      * @throws ClassCastException if the key is of an inappropriate type
174      * @throws NullPointerException if the key is null
175      */
176     public Object get(final Object key) {
177         return doGet((Comparable ) key, KEY);
178     }
179
180     /**
181      * Puts the key-value pair into the map, replacing any previous pair.
182      * <p>
183      * When adding a key-value pair, the value may already exist in the map
184      * against a different key. That mapping is removed, to ensure that the
185      * value only occurs once in the inverse map.
186      * <pre>
187      * BidiMap map1 = new TreeBidiMap();
188      * map.put("A","B"); // contains A mapped to B, as per Map
189      * map.put("A","C"); // contains A mapped to C, as per Map
190      *
191      * BidiMap map2 = new TreeBidiMap();
192      * map.put("A","B"); // contains A mapped to B, as per Map
193      * map.put("C","B"); // contains C mapped to B, key A is removed
194      * </pre>
195      * <p>
196      * Both key and value must implement <code>Comparable</code>.
197      *
198      * @param key key with which the specified value is to be associated
199      * @param value value to be associated with the specified key
200      * @return the previous value for the key
201      * @throws ClassCastException if the key is of an inappropriate type
202      * @throws NullPointerException if the key is null
203      */
204     public Object put(final Object key, final Object value) {
205         return doPut((Comparable ) key, (Comparable ) value, KEY);
206     }
207
208     /**
209      * Puts all the mappings from the specified map into this map.
210      * <p>
211      * All keys and values must implement <code>Comparable</code>.
212      *
213      * @param map the map to copy from
214      */
215     public void putAll(Map map) {
216         Iterator it = map.entrySet().iterator();
217         while (it.hasNext()) {
218             Map.Entry entry = (Map.Entry ) it.next();
219             put(entry.getKey(), entry.getValue());
220         }
221     }
222         
223     /**
224      * Removes the mapping for this key from this map if present.
225      * <p>
226      * The key must implement <code>Comparable</code>.
227      *
228      * @param key key whose mapping is to be removed from the map.
229      * @return previous value associated with specified key,
230      * or null if there was no mapping for key.
231      * @throws ClassCastException if the key is of an inappropriate type
232      * @throws NullPointerException if the key is null
233      */
234     public Object remove(final Object key) {
235         return doRemove((Comparable ) key, KEY);
236     }
237
238     /**
239      * Removes all mappings from this map.
240      */
241     public void clear() {
242         modify();
243
244         nodeCount = 0;
245         rootNode[KEY] = null;
246         rootNode[VALUE] = null;
247     }
248
249     //-----------------------------------------------------------------------
250 /**
251      * Returns the key to which this map maps the specified value.
252      * Returns null if the map contains no mapping for this value.
253      * <p>
254      * The value must implement <code>Comparable</code>.
255      *
256      * @param value value whose associated key is to be returned.
257      * @return the key to which this map maps the specified value,
258      * or null if the map contains no mapping for this value.
259      * @throws ClassCastException if the value is of an inappropriate type
260      * @throws NullPointerException if the value is null
261      */
262     public Object getKey(final Object value) {
263         return doGet((Comparable ) value, VALUE);
264     }
265
266     /**
267      * Removes the mapping for this value from this map if present.
268      * <p>
269      * The value must implement <code>Comparable</code>.
270      *
271      * @param value value whose mapping is to be removed from the map
272      * @return previous key associated with specified value,
273      * or null if there was no mapping for value.
274      * @throws ClassCastException if the value is of an inappropriate type
275      * @throws NullPointerException if the value is null
276      */
277     public Object removeValue(final Object value) {
278         return doRemove((Comparable ) value, VALUE);
279     }
280
281     //-----------------------------------------------------------------------
282 /**
283      * Gets the first (lowest) key currently in this map.
284      *
285      * @return the first (lowest) key currently in this sorted map
286      * @throws NoSuchElementException if this map is empty
287      */
288     public Object firstKey() {
289         if (nodeCount == 0) {
290             throw new NoSuchElementException ("Map is empty");
291         }
292         return leastNode(rootNode[KEY], KEY).getKey();
293     }
294
295     /**
296      * Gets the last (highest) key currently in this map.
297      *
298      * @return the last (highest) key currently in this sorted map
299      * @throws NoSuchElementException if this map is empty
300      */
301     public Object lastKey() {
302         if (nodeCount == 0) {
303             throw new NoSuchElementException ("Map is empty");
304         }
305         return greatestNode(rootNode[KEY], KEY).getKey();
306     }
307     
308     /**
309      * Gets the next key after the one specified.
310      * <p>
311      * The key must implement <code>Comparable</code>.
312      *
313      * @param key the key to search for next from
314      * @return the next key, null if no match or at end
315      */
316     public Object nextKey(Object key) {
317         checkKey(key);
318         Node node = nextGreater(lookup((Comparable ) key, KEY), KEY);
319         return (node == null ? null : node.getKey());
320     }
321
322     /**
323      * Gets the previous key before the one specified.
324      * <p>
325      * The key must implement <code>Comparable</code>.
326      *
327      * @param key the key to search for previous from
328      * @return the previous key, null if no match or at start
329      */
330     public Object previousKey(Object key) {
331         checkKey(key);
332         Node node = nextSmaller(lookup((Comparable ) key, KEY), KEY);
333         return (node == null ? null : node.getKey());
334     }
335     
336     //-----------------------------------------------------------------------
337 /**
338      * Returns a set view of the keys contained in this map in key order.
339      * <p>
340      * The set is backed by the map, so changes to the map are reflected in
341      * the set, and vice-versa. If the map is modified while an iteration over
342      * the set is in progress, the results of the iteration are undefined.
343      * <p>
344      * The set supports element removal, which removes the corresponding mapping
345      * from the map. It does not support the add or addAll operations.
346      *
347      * @return a set view of the keys contained in this map.
348      */
349     public Set keySet() {
350         if (keySet == null) {
351             keySet = new View(this, KEY, KEY);
352         }
353         return keySet;
354     }
355
356     //-----------------------------------------------------------------------
357 /**
358      * Returns a set view of the values contained in this map in key order.
359      * The returned object can be cast to a Set.
360      * <p>
361      * The set is backed by the map, so changes to the map are reflected in
362      * the set, and vice-versa. If the map is modified while an iteration over
363      * the set is in progress, the results of the iteration are undefined.
364      * <p>
365      * The set supports element removal, which removes the corresponding mapping
366      * from the map. It does not support the add or addAll operations.
367      *
368      * @return a set view of the values contained in this map.
369      */
370     public Collection values() {
371         if (valuesSet == null) {
372             valuesSet = new View(this, KEY, VALUE);
373         }
374         return valuesSet;
375     }
376
377     //-----------------------------------------------------------------------
378 /**
379      * Returns a set view of the entries contained in this map in key order.
380      * For simple iteration through the map, the MapIterator is quicker.
381      * <p>
382      * The set is backed by the map, so changes to the map are reflected in
383      * the set, and vice-versa. If the map is modified while an iteration over
384      * the set is in progress, the results of the iteration are undefined.
385      * <p>
386      * The set supports element removal, which removes the corresponding mapping
387      * from the map. It does not support the add or addAll operations.
388      * The returned MapEntry objects do not support setValue.
389      *
390      * @return a set view of the values contained in this map.
391      */
392     public Set entrySet() {
393         if (entrySet == null) {
394             return new EntryView(this, KEY, MAPENTRY);
395         }
396         return entrySet;
397     }
398
399     //-----------------------------------------------------------------------
400 /**
401      * Gets an iterator over the map entries.
402      * <p>
403      * For this map, this iterator is the fastest way to iterate over the entries.
404      *
405      * @return an iterator
406      */
407     public MapIterator mapIterator() {
408         if (isEmpty()) {
409             return EmptyOrderedMapIterator.INSTANCE;
410         }
411         return new ViewMapIterator(this, KEY);
412     }
413
414     /**
415      * Gets an ordered iterator over the map entries.
416      * <p>
417      * This iterator allows both forward and reverse iteration over the entries.
418      *
419      * @return an iterator
420      */
421     public OrderedMapIterator orderedMapIterator() {
422         if (isEmpty()) {
423             return EmptyOrderedMapIterator.INSTANCE;
424         }
425         return new ViewMapIterator(this, KEY);
426     }
427
428     //-----------------------------------------------------------------------
429 /**
430      * Gets the inverse map for comparison.
431      *
432      * @return the inverse map
433      */
434     public BidiMap inverseBidiMap() {
435         return inverseOrderedBidiMap();
436     }
437
438     /**
439      * Gets the inverse map for comparison.
440      *
441      * @return the inverse map
442      */
443     public OrderedBidiMap inverseOrderedBidiMap() {
444         if (inverse == null) {
445             inverse = new Inverse(this);
446         }
447         return inverse;
448     }
449
450     //-----------------------------------------------------------------------
451 /**
452      * Compares for equals as per the API.
453      *
454      * @param obj the object to compare to
455      * @return true if equal
456      */
457     public boolean equals(Object obj) {
458         return this.doEquals(obj, KEY);
459     }
460     
461     /**
462      * Gets the hash code value for this map as per the API.
463      *
464      * @return the hash code value for this map
465      */
466     public int hashCode() {
467         return this.doHashCode(KEY);
468     }
469     
470     /**
471      * Returns a string version of this Map in standard format.
472      *
473      * @return a standard format string version of the map
474      */
475     public String toString() {
476         return this.doToString(KEY);
477     }
478     
479     //-----------------------------------------------------------------------
480 /**
481      * Common get logic, used to get by key or get by value
482      *
483      * @param obj the key or value that we're looking for
484      * @param index the KEY or VALUE int
485      * @return the key (if the value was mapped) or the value (if the
486      * key was mapped); null if we couldn't find the specified
487      * object
488      */
489     private Object doGet(final Comparable obj, final int index) {
490         checkNonNullComparable(obj, index);
491         Node node = lookup(obj, index);
492         return ((node == null) ? null : node.getData(oppositeIndex(index)));
493     }
494
495     /**
496      * Common put logic, differing only in the return value.
497      *
498      * @param key the key, always the main map key
499      * @param value the value, always the main map value
500      * @param index the KEY or VALUE int, for the return value only
501      * @return the previously mapped value
502      */
503     private Object doPut(final Comparable key, final Comparable value, final int index) {
504         checkKeyAndValue(key, value);
505         
506         // store previous and remove previous mappings
507 Object prev = (index == KEY ? doGet(key, KEY) : doGet(value, VALUE));
508         doRemove(key, KEY);
509         doRemove(value, VALUE);
510         
511         Node node = rootNode[KEY];
512         if (node == null) {
513             // map is empty
514 Node root = new Node(key, value);
515             rootNode[KEY] = root;
516             rootNode[VALUE] = root;
517             grow();
518             
519         } else {
520             // add new mapping
521 while (true) {
522                 int cmp = compare(key, node.getData(KEY));
523         
524                 if (cmp == 0) {
525                     // shouldn't happen
526 throw new IllegalArgumentException ("Cannot store a duplicate key (\"" + key + "\") in this Map");
527                 } else if (cmp < 0) {
528                     if (node.getLeft(KEY) != null) {
529                         node = node.getLeft(KEY);
530                     } else {
531                         Node newNode = new Node(key, value);
532         
533                         insertValue(newNode);
534                         node.setLeft(newNode, KEY);
535                         newNode.setParent(node, KEY);
536                         doRedBlackInsert(newNode, KEY);
537                         grow();
538         
539                         break;
540                     }
541                 } else { // cmp > 0
542 if (node.getRight(KEY) != null) {
543                         node = node.getRight(KEY);
544                     } else {
545                         Node newNode = new Node(key, value);
546         
547                         insertValue(newNode);
548                         node.setRight(newNode, KEY);
549                         newNode.setParent(node, KEY);
550                         doRedBlackInsert(newNode, KEY);
551                         grow();
552         
553                         break;
554                     }
555                 }
556             }
557         }
558         return prev;
559     }
560
561     /**
562      * Remove by object (remove by key or remove by value)
563      *
564      * @param o the key, or value, that we're looking for
565      * @param index the KEY or VALUE int
566      *
567      * @return the key, if remove by value, or the value, if remove by
568      * key. null if the specified key or value could not be
569      * found
570      */
571     private Object doRemove(final Comparable o, final int index) {
572         Node node = lookup(o, index);
573         Object rval = null;
574         if (node != null) {
575             rval = node.getData(oppositeIndex(index));
576             doRedBlackDelete(node);
577         }
578         return rval;
579     }
580
581     /**
582      * do the actual lookup of a piece of data
583      *
584      * @param data the key or value to be looked up
585      * @param index the KEY or VALUE int
586      * @return the desired Node, or null if there is no mapping of the
587      * specified data
588      */
589     private Node lookup(final Comparable data, final int index) {
590         Node rval = null;
591         Node node = rootNode[index];
592
593         while (node != null) {
594             int cmp = compare(data, node.getData(index));
595             if (cmp == 0) {
596                 rval = node;
597                 break;
598             } else {
599                 node = (cmp < 0) ? node.getLeft(index) : node.getRight(index);
600             }
601         }
602
603         return rval;
604     }
605
606     /**
607      * get the next larger node from the specified node
608      *
609      * @param node the node to be searched from
610      * @param index the KEY or VALUE int
611      * @return the specified node
612      */
613     private Node nextGreater(final Node node, final int index) {
614         Node rval = null;
615         if (node == null) {
616             rval = null;
617         } else if (node.getRight(index) != null) {
618             // everything to the node's right is larger. The least of
619 // the right node's descendants is the next larger node
620 rval = leastNode(node.getRight(index), index);
621         } else {
622             // traverse up our ancestry until we find an ancestor that
623 // is null or one whose left child is our ancestor. If we
624 // find a null, then this node IS the largest node in the
625 // tree, and there is no greater node. Otherwise, we are
626 // the largest node in the subtree on that ancestor's left
627 // ... and that ancestor is the next greatest node
628 Node parent = node.getParent(index);
629             Node child = node;
630
631             while ((parent != null) && (child == parent.getRight(index))) {
632                 child = parent;
633                 parent = parent.getParent(index);
634             }
635             rval = parent;
636         }
637         return rval;
638     }
639
640     /**
641      * get the next larger node from the specified node
642      *
643      * @param node the node to be searched from
644      * @param index the KEY or VALUE int
645      * @return the specified node
646      */
647     private Node nextSmaller(final Node node, final int index) {
648         Node rval = null;
649         if (node == null) {
650             rval = null;
651         } else if (node.getLeft(index) != null) {
652             // everything to the node's left is smaller. The greatest of
653 // the left node's descendants is the next smaller node
654 rval = greatestNode(node.getLeft(index), index);
655         } else {
656             // traverse up our ancestry until we find an ancestor that
657 // is null or one whose right child is our ancestor. If we
658 // find a null, then this node IS the largest node in the
659 // tree, and there is no greater node. Otherwise, we are
660 // the largest node in the subtree on that ancestor's right
661 // ... and that ancestor is the next greatest node
662 Node parent = node.getParent(index);
663             Node child = node;
664
665             while ((parent != null) && (child == parent.getLeft(index))) {
666                 child = parent;
667                 parent = parent.getParent(index);
668             }
669             rval = parent;
670         }
671         return rval;
672     }
673
674     //-----------------------------------------------------------------------
675 /**
676      * Get the opposite index of the specified index
677      *
678      * @param index the KEY or VALUE int
679      * @return VALUE (if KEY was specified), else KEY
680      */
681     private static int oppositeIndex(final int index) {
682         // old trick ... to find the opposite of a value, m or n,
683 // subtract the value from the sum of the two possible
684 // values. (m + n) - m = n; (m + n) - n = m
685 return SUM_OF_INDICES - index;
686     }
687
688     /**
689      * Compare two objects
690      *
691      * @param o1 the first object
692      * @param o2 the second object
693      *
694      * @return negative value if o1 &lt; o2; 0 if o1 == o2; positive
695      * value if o1 &gt; o2
696      */
697     private static int compare(final Comparable o1, final Comparable o2) {
698         return o1.compareTo(o2);
699     }
700
701     /**
702      * Find the least node from a given node.
703      *
704      * @param node the node from which we will start searching
705      * @param index the KEY or VALUE int
706      * @return the smallest node, from the specified node, in the
707      * specified mapping
708      */
709     private static Node leastNode(final Node node, final int index) {
710         Node rval = node;
711         if (rval != null) {
712             while (rval.getLeft(index) != null) {
713                 rval = rval.getLeft(index);
714             }
715         }
716         return rval;
717     }
718
719     /**
720      * Find the greatest node from a given node.
721      *
722      * @param node the node from which we will start searching
723      * @param index the KEY or VALUE int
724      * @return the greatest node, from the specified node
725      */
726     private static Node greatestNode(final Node node, final int index) {
727         Node rval = node;
728         if (rval != null) {
729             while (rval.getRight(index) != null) {
730                 rval = rval.getRight(index);
731             }
732         }
733         return rval;
734     }
735
736     /**
737      * copy the color from one node to another, dealing with the fact
738      * that one or both nodes may, in fact, be null
739      *
740      * @param from the node whose color we're copying; may be null
741      * @param to the node whose color we're changing; may be null
742      * @param index the KEY or VALUE int
743      */
744     private static void copyColor(final Node from, final Node to, final int index) {
745         if (to != null) {
746             if (from == null) {
747                 // by default, make it black
748 to.setBlack(index);
749             } else {
750                 to.copyColor(from, index);
751             }
752         }
753     }
754
755     /**
756      * is the specified node red? if the node does not exist, no, it's
757      * black, thank you
758      *
759      * @param node the node (may be null) in question
760      * @param index the KEY or VALUE int
761      */
762     private static boolean isRed(final Node node, final int index) {
763         return ((node == null) ? false : node.isRed(index));
764     }
765
766     /**
767      * is the specified black red? if the node does not exist, sure,
768      * it's black, thank you
769      *
770      * @param node the node (may be null) in question
771      * @param index the KEY or VALUE int
772      */
773     private static boolean isBlack(final Node node, final int index) {
774         return ((node == null) ? true : node.isBlack(index));
775     }
776
777     /**
778      * force a node (if it exists) red
779      *
780      * @param node the node (may be null) in question
781      * @param index the KEY or VALUE int
782      */
783     private static void makeRed(final Node node, final int index) {
784         if (node != null) {
785             node.setRed(index);
786         }
787     }
788
789     /**
790      * force a node (if it exists) black
791      *
792      * @param node the node (may be null) in question
793      * @param index the KEY or VALUE int
794      */
795     private static void makeBlack(final Node node, final int index) {
796         if (node != null) {
797             node.setBlack(index);
798         }
799     }
800
801     /**
802      * get a node's grandparent. mind you, the node, its parent, or
803      * its grandparent may not exist. no problem
804      *
805      * @param node the node (may be null) in question
806      * @param index the KEY or VALUE int
807      */
808     private static Node getGrandParent(final Node node, final int index) {
809         return getParent(getParent(node, index), index);
810     }
811
812     /**
813      * get a node's parent. mind you, the node, or its parent, may not
814      * exist. no problem
815      *
816      * @param node the node (may be null) in question
817      * @param index the KEY or VALUE int
818      */
819     private static Node getParent(final Node node, final int index) {
820         return ((node == null) ? null : node.getParent(index));
821     }
822
823     /**
824      * get a node's right child. mind you, the node may not exist. no
825      * problem
826      *
827      * @param node the node (may be null) in question
828      * @param index the KEY or VALUE int
829      */
830     private static Node getRightChild(final Node node, final int index) {
831         return (node == null) ? null : node.getRight(index);
832     }
833
834     /**
835      * get a node's left child. mind you, the node may not exist. no
836      * problem
837      *
838      * @param node the node (may be null) in question
839      * @param index the KEY or VALUE int
840      */
841     private static Node getLeftChild(final Node node, final int index) {
842         return (node == null) ? null : node.getLeft(index);
843     }
844
845     /**
846      * is this node its parent's left child? mind you, the node, or
847      * its parent, may not exist. no problem. if the node doesn't
848      * exist ... it's its non-existent parent's left child. If the
849      * node does exist but has no parent ... no, we're not the
850      * non-existent parent's left child. Otherwise (both the specified
851      * node AND its parent exist), check.
852      *
853      * @param node the node (may be null) in question
854      * @param index the KEY or VALUE int
855      */
856     private static boolean isLeftChild(final Node node, final int index) {
857         return (node == null)
858             ? true
859             : ((node.getParent(index) == null) ?
860                 false : (node == node.getParent(index).getLeft(index)));
861     }
862
863     /**
864      * is this node its parent's right child? mind you, the node, or
865      * its parent, may not exist. no problem. if the node doesn't
866      * exist ... it's its non-existent parent's right child. If the
867      * node does exist but has no parent ... no, we're not the
868      * non-existent parent's right child. Otherwise (both the
869      * specified node AND its parent exist), check.
870      *
871      * @param node the node (may be null) in question
872      * @param index the KEY or VALUE int
873      */
874     private static boolean isRightChild(final Node node, final int index) {
875         return (node == null)
876             ? true
877             : ((node.getParent(index) == null) ?
878                 false : (node == node.getParent(index).getRight(index)));
879     }
880
881     /**
882      * do a rotate left. standard fare in the world of balanced trees
883      *
884      * @param node the node to be rotated
885      * @param index the KEY or VALUE int
886      */
887     private void rotateLeft(final Node node, final int index) {
888         Node rightChild = node.getRight(index);
889         node.setRight(rightChild.getLeft(index), index);
890
891         if (rightChild.getLeft(index) != null) {
892             rightChild.getLeft(index).setParent(node, index);
893         }
894         rightChild.setParent(node.getParent(index), index);
895         
896         if (node.getParent(index) == null) {
897             // node was the root ... now its right child is the root
898 rootNode[index] = rightChild;
899         } else if (node.getParent(index).getLeft(index) == node) {
900             node.getParent(index).setLeft(rightChild, index);
901         } else {
902             node.getParent(index).setRight(rightChild, index);
903         }
904
905         rightChild.setLeft(node, index);
906         node.setParent(rightChild, index);
907     }
908
909     /**
910      * do a rotate right. standard fare in the world of balanced trees
911      *
912      * @param node the node to be rotated
913      * @param index the KEY or VALUE int
914      */
915     private void rotateRight(final Node node, final int index) {
916         Node leftChild = node.getLeft(index);
917         node.setLeft(leftChild.getRight(index), index);
918         if (leftChild.getRight(index) != null) {
919             leftChild.getRight(index).setParent(node, index);
920         }
921         leftChild.setParent(node.getParent(index), index);
922
923         if (node.getParent(index) == null) {
924             // node was the root ... now its left child is the root
925 rootNode[index] = leftChild;
926         } else if (node.getParent(index).getRight(index) == node) {
927             node.getParent(index).setRight(leftChild, index);
928