Java > Open Source Codes > org > apache > commons > collections > DoubleOrderedMap


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