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
911                 // replacement is null
912 if (deletedNode.getParent(index) == null) {
913
914                     // empty tree
915 rootNode[index] = null;
916                 } else {
917
918                     // deleted node had no children
919 if (isBlack(deletedNode, index)) {
920                         doRedBlackDeleteFixup(deletedNode, index);
921                     }
922
923                     if (deletedNode.getParent(index) != null) {
924                         if (deletedNode
925                                 == deletedNode.getParent(index)
926                                     .getLeft(index)) {
927                             deletedNode.getParent(index).setLeft(null, index);
928                         } else {
929                             deletedNode.getParent(index).setRight(null,
930                                                   index);
931                         }
932
933                         deletedNode.setParent(null, index);
934                     }
935                 }
936             }
937         }
938
939         shrink();
940     }
941
942     /**
943      * complicated red-black delete stuff. Based on Sun's TreeMap
944      * implementation, though it's barely recognizable any more. This
945      * rebalances the tree (somewhat, as red-black trees are not
946      * perfectly balanced -- perfect balancing takes longer)
947      *
948      * @param replacementNode the node being replaced
949      * @param index KEY or VALUE
950      */
951     private void doRedBlackDeleteFixup(final Node replacementNode,
952                                        final int index) {
953
954         Node currentNode = replacementNode;
955
956         while ((currentNode != rootNode[index])
957                 && (isBlack(currentNode, index))) {
958             if (isLeftChild(currentNode, index)) {
959                 Node siblingNode =
960                     getRightChild(getParent(currentNode, index), index);
961
962                 if (isRed(siblingNode, index)) {
963                     makeBlack(siblingNode, index);
964                     makeRed(getParent(currentNode, index), index);
965                     rotateLeft(getParent(currentNode, index), index);
966
967                     siblingNode = getRightChild(getParent(currentNode, index), index);
968                 }
969
970                 if (isBlack(getLeftChild(siblingNode, index), index)
971                         && isBlack(getRightChild(siblingNode, index),
972                                    index)) {
973                     makeRed(siblingNode, index);
974
975                     currentNode = getParent(currentNode, index);
976                 } else {
977                     if (isBlack(getRightChild(siblingNode, index), index)) {
978                         makeBlack(getLeftChild(siblingNode, index), index);
979                         makeRed(siblingNode, index);
980                         rotateRight(siblingNode, index);
981
982                         siblingNode =
983                             getRightChild(getParent(currentNode, index), index);
984                     }
985
986                     copyColor(getParent(currentNode, index), siblingNode,
987                               index);
988                     makeBlack(getParent(currentNode, index), index);
989                     makeBlack(getRightChild(siblingNode, index), index);
990                     rotateLeft(getParent(currentNode, index), index);
991
992                     currentNode = rootNode[index];
993                 }
994             } else {
995                 Node siblingNode = getLeftChild(getParent(currentNode, index), index);
996
997                 if (isRed(siblingNode, index)) {
998                     makeBlack(siblingNode, index);
999                     makeRed(getParent(currentNode, index), index);
1000                    rotateRight(getParent(currentNode, index), index);
1001
1002                    siblingNode = getLeftChild(getParent(currentNode, index), index);
1003                }
1004
1005                if (isBlack(getRightChild(siblingNode, index), index)
1006                        && isBlack(getLeftChild(siblingNode, index), index)) {
1007                    makeRed(siblingNode, index);
1008
1009                    currentNode = getParent(currentNode, index);
1010                } else {
1011                    if (isBlack(getLeftChild(siblingNode, index), index)) {
1012                        makeBlack(getRightChild(siblingNode, index), index);
1013                        makeRed(siblingNode, index);
1014                        rotateLeft(siblingNode, index);
1015
1016                        siblingNode =
1017                            getLeftChild(getParent(currentNode, index), index);
1018                    }
1019
1020                    copyColor(getParent(currentNode, index), siblingNode,
1021                              index);
1022                    makeBlack(getParent(currentNode, index), index);
1023                    makeBlack(getLeftChild(siblingNode, index), index);
1024                    rotateRight(getParent(currentNode, index), index);
1025
1026                    currentNode = rootNode[index];
1027                }
1028            }
1029        }
1030
1031        makeBlack(currentNode, index);
1032    }
1033
1034    /**
1035     * swap two nodes (except for their content), taking care of
1036     * special cases where one is the other's parent ... hey, it
1037     * happens.
1038     *
1039     * @param x one node
1040     * @param y another node
1041     * @param index KEY or VALUE
1042     */
1043    private void swapPosition(final Node x, final Node y, final int index) {
1044
1045        // Save initial values.
1046 Node xFormerParent = x.getParent(index);
1047        Node xFormerLeftChild = x.getLeft(index);
1048        Node xFormerRightChild = x.getRight(index);
1049        Node yFormerParent = y.getParent(index);
1050        Node yFormerLeftChild = y.getLeft(index);
1051        Node yFormerRightChild = y.getRight(index);
1052        boolean xWasLeftChild =
1053            (x.getParent(index) != null)
1054            && (x == x.getParent(index).getLeft(index));
1055        boolean yWasLeftChild =
1056            (y.getParent(index) != null)
1057            && (y == y.getParent(index).getLeft(index));
1058
1059        // Swap, handling special cases of one being the other's parent.
1060 if (x == yFormerParent) { // x was y's parent
1061 x.setParent(y, index);
1062
1063            if (yWasLeftChild) {
1064                y.setLeft(x, index);
1065                y.setRight(xFormerRightChild, index);
1066            } else {
1067                y.setRight(x, index);
1068                y.setLeft(xFormerLeftChild, index);
1069            }
1070        } else {
1071            x.setParent(yFormerParent, index);
1072
1073            if (yFormerParent != null) {
1074                if (yWasLeftChild) {
1075                    yFormerParent.setLeft(x, index);
1076                } else {
1077                    yFormerParent.setRight(x, index);
1078                }
1079            }
1080
1081            y.setLeft(xFormerLeftChild, index);
1082            y.setRight(xFormerRightChild, index);
1083        }
1084
1085        if (y == xFormerParent) { // y was x's parent
1086 y.setParent(x, index);
1087
1088            if (xWasLeftChild) {
1089                x.setLeft(y, index);
1090                x.setRight(yFormerRightChild, index);
1091            } else {
1092                x.setRight(y, index);
1093                x.setLeft(yFormerLeftChild, index);
1094            }
1095        } else {
1096            y.setParent(xFormerParent, index);
1097
1098            if (xFormerParent != null) {
1099                if (xWasLeftChild) {
1100                    xFormerParent.setLeft(y, index);
1101                } else {
1102                    xFormerParent.setRight(y, index);
1103                }
1104            }
1105
1106            x.setLeft(yFormerLeftChild, index);
1107            x.setRight(yFormerRightChild, index);
1108        }
1109
1110        // Fix children's parent pointers
1111 if (x.getLeft(index) != null) {
1112            x.getLeft(index).setParent(x, index);
1113        }
1114
1115        if (x.getRight(index) != null) {
1116            x.getRight(index).setParent(x, index);
1117        }
1118
1119        if (y.getLeft(index) != null) {
1120            y.getLeft(index).setParent(y, index);
1121        }
1122
1123        if (y.getRight(index) != null) {
1124            y.getRight(index).setParent(y, index);
1125        }
1126
1127        x.swapColors(y, index);
1128
1129        // Check if root changed
1130 if (rootNode[index] == x) {
1131            rootNode[index] = y;
1132        } else if (rootNode[index] == y) {
1133            rootNode[index] = x;
1134        }
1135    }
1136
1137    /**
1138     * check if an object is fit to be proper input ... has to be
1139     * Comparable and non-null
1140     *
1141     * @param o the object being checked
1142     * @param index KEY or VALUE (used to put the right word in the
1143     * exception message)
1144     *
1145     * @throws NullPointerException if o is null
1146     * @throws ClassCastException if o is not Comparable
1147     */
1148    private static void checkNonNullComparable(final Object o,
1149                                               final int index) {
1150
1151        if (o == null) {
1152            throw new NullPointerException (dataName[index]
1153                                           + " cannot be null");
1154        }
1155
1156        if (!(o instanceof Comparable )) {
1157            throw new ClassCastException (dataName[index]
1158                                         + " must be Comparable");
1159        }
1160    }
1161
1162    /**
1163     * check a key for validity (non-null and implements Comparable)
1164     *
1165     * @param key the key to be checked
1166     *
1167     * @throws NullPointerException if key is null
1168     * @throws ClassCastException if key is not Comparable
1169     */
1170    private static void checkKey(final Object key) {
1171        checkNonNullComparable(key, KEY);
1172    }
1173
1174    /**
1175     * check a value for validity (non-null and implements Comparable)
1176     *
1177     * @param value the value to be checked
1178     *
1179     * @throws NullPointerException if value is null
1180     * @throws ClassCastException if value is not Comparable
1181     */
1182    private static void checkValue(final Object value) {
1183        checkNonNullComparable(value, VALUE);
1184    }
1185
1186    /**
1187     * check a key and a value for validity (non-null and implements
1188     * Comparable)
1189     *
1190     * @param key the key to be checked
1191     * @param value the value to be checked
1192     *
1193     * @throws NullPointerException if key or value is null
1194     * @throws ClassCastException if key or value is not Comparable
1195     */
1196    private static void checkKeyAndValue(final Object key,
1197                                         final Object value) {
1198        checkKey(key);
1199        checkValue(value);
1200    }
1201
1202    /**
1203     * increment the modification count -- used to check for
1204     * concurrent modification of the map through the map and through
1205     * an Iterator from one of its Set or Collection views
1206     */
1207    private void modify() {
1208        modifications++;
1209    }
1210
1211    /**
1212     * bump up the size and note that the map has changed
1213     */
1214    private void grow() {
1215
1216        modify();
1217
1218        nodeCount++;
1219    }
1220
1221    /**
1222     * decrement the size and note that the map has changed
1223     */
1224    private void shrink() {
1225
1226        modify();
1227
1228        nodeCount--;
1229    }
1230
1231    /**
1232     * insert a node by its value
1233     *
1234     * @param newNode the node to be inserted
1235     *
1236     * @throws IllegalArgumentException if the node already exists
1237     * in the value mapping
1238     */
1239    private void insertValue(final Node newNode)
1240            throws IllegalArgumentException {
1241
1242        Node node = rootNode[VALUE];
1243
1244        while (true) {
1245            int cmp = compare(newNode.getData(VALUE), node.getData(VALUE));
1246
1247            if (cmp == 0) {
1248                throw new IllegalArgumentException (
1249                    "Cannot store a duplicate value (\""
1250                    + newNode.getData(VALUE) + "\") in this Map");
1251            } else if (cmp < 0) {
1252                if (node.getLeft(VALUE) != null) {
1253                    node = node.getLeft(VALUE);
1254                } else {
1255                    node.setLeft(newNode, VALUE);
1256                    newNode.setParent(node, VALUE);
1257                    doRedBlackInsert(newNode, VALUE);
1258
1259                    break;
1260                }
1261            } else { // cmp > 0
1262 if (node.getRight(VALUE) != null) {
1263                    node = node.getRight(VALUE);
1264                } else {
1265                    node.setRight(newNode, VALUE);
1266                    newNode.setParent(node, VALUE);
1267                    doRedBlackInsert(newNode, VALUE);
1268
1269                    break;
1270                }
1271            }
1272        }
1273    }
1274
1275    /* ********** START implementation of Map ********** */
1276
1277    /**
1278     * Returns the number of key-value mappings in this map. If the
1279     * map contains more than Integer.MAXVALUE elements, returns
1280     * Integer.MAXVALUE.
1281     *
1282     * @return the number of key-value mappings in this map.
1283     */
1284    public int size() {
1285        return nodeCount;
1286    }
1287
1288    /**
1289     * Returns true if this map contains a mapping for the specified
1290     * key.
1291     *
1292     * @param key key whose presence in this map is to be tested.
1293     *
1294     * @return true if this map contains a mapping for the specified
1295     * key.
1296     *
1297     * @throws ClassCastException if the key is of an inappropriate
1298     * type for this map.
1299     * @throws NullPointerException if the key is null
1300     */
1301    public boolean containsKey(final Object key)
1302            throws ClassCastException , NullPointerException {
1303
1304        checkKey(key);
1305
1306        return lookup((Comparable ) key, KEY) != null;
1307    }
1308
1309    /**
1310     * Returns true if this map maps one or more keys to the
1311     * specified value.
1312     *
1313     * @param value value whose presence in this map is to be tested.
1314     *
1315     * @return true if this map maps one or more keys to the specified
1316     * value.
1317     */
1318    public boolean containsValue(final Object value) {
1319
1320        checkValue(value);
1321
1322        return lookup((Comparable ) value, VALUE) != null;
1323    }
1324
1325    /**
1326     * Returns the value to which this map maps the specified
1327     * key. Returns null if the map contains no mapping for this key.
1328     *
1329     * @param key key whose associated value is to be returned.
1330     *
1331     * @return the value to which this map maps the specified key, or
1332     * null if the map contains no mapping for this key.
1333     *
1334     * @throws ClassCastException if the key is of an inappropriate
1335     * type for this map.
1336     * @throws NullPointerException if the key is null
1337     */
1338    public Object get(final Object key)
1339            throws ClassCastException , NullPointerException {
1340        return doGet((Comparable ) key, KEY);
1341    }
1342
1343    /**
1344     * Associates the specified value with the specified key in this
1345     * map.
1346     *
1347     * @param key key with which the specified value is to be
1348     * associated.
1349     * @param value value to be associated with the specified key.
1350     *
1351     * @return null
1352     *
1353     * @throws ClassCastException if the class of the specified key
1354     * or value prevents it from being
1355     * stored in this map.
1356     * @throws NullPointerException if the specified key or value
1357     * is null
1358     * @throws IllegalArgumentException if the key duplicates an
1359     * existing key, or if the
1360     * value duplicates an
1361     * existing value
1362     */
1363    public Object put(final Object key, final Object value)
1364            throws ClassCastException , NullPointerException ,
1365                   IllegalArgumentException {
1366
1367        checkKeyAndValue(key, value);
1368
1369        Node node = rootNode[KEY];
1370
1371        if (node == null) {
1372            Node root = new Node((Comparable ) key, (Comparable ) value);
1373
1374            rootNode[KEY] = root;
1375            rootNode[VALUE] = root;
1376
1377            grow();
1378        } else {
1379            while (true) {
1380                int cmp = compare((Comparable ) key, node.getData(KEY));
1381
1382                if (cmp == 0) {
1383                    throw new IllegalArgumentException (
1384                        "Cannot store a duplicate key (\"" + key
1385                        + "\") in this Map");
1386                } else if (cmp < 0) {
1387                    if (node.getLeft(KEY) != null) {
1388                        node = node.getLeft(KEY);
1389                    } else {
1390                        Node newNode = new Node((Comparable ) key,
1391                                                (Comparable ) value);
1392
1393                        insertValue(newNode);
1394                        node.setLeft(newNode, KEY);
1395                        newNode.setParent(node, KEY);
1396                        doRedBlackInsert(newNode, KEY);
1397                        grow();
1398
1399                        break;
1400                    }
1401                } else { // cmp > 0
1402 if (node.getRight(KEY) != null) {
1403                        node = node.getRight(KEY);
1404                    } else {
1405                        Node newNode = new Node((Comparable ) key,
1406                                                (Comparable ) value);
1407
1408                        insertValue(newNode);
1409                        node.setRight(newNode, KEY);
1410                        newNode.setParent(node, KEY);
1411                        doRedBlackInsert(newNode, KEY);
1412                        grow();
1413
1414                        break;
1415                    }
1416                }
1417            }
1418        }
1419
1420        return null;
1421    }
1422
1423    /**
1424     * Removes the mapping for this key from this map if present
1425     *
1426     * @param key key whose mapping is to be removed from the map.
1427     *
1428     * @return previous value associated with specified key, or null
1429     * if there was no mapping for key.
1430     */
1431    public Object remove(final Object key) {
1432        return doRemove((Comparable ) key, KEY);
1433    }
1434
1435    /**
1436     * Removes all mappings from this map
1437     */
1438    public void clear() {
1439
1440        modify();
1441
1442        nodeCount = 0;
1443        rootNode[KEY] = null;
1444        rootNode[VALUE] = null;
1445    }
1446
1447    /**
1448     * Returns a set view of the keys contained in this map. The set
1449     * is backed by the map, so changes to the map are reflected in
1450     * the set, and vice-versa. If the map is modified while an
1451     * iteration over the set is in progress, the results of the
1452     * iteration are undefined. The set supports element removal,
1453     * which removes the corresponding mapping from the map, via the
1454     * Iterator.remove, Set.remove, removeAll, retainAll, and clear
1455     * operations. It does not support the add or addAll operations.
1456     *
1457     * @return a set view of the keys contained in this map.
1458     */
1459    public Set keySet() {
1460
1461        if (setOfKeys[KEY] == null) {
1462            setOfKeys[KEY] = new AbstractSet () {
1463
1464                public Iterator iterator() {
1465
1466                    return new DoubleOrderedMapIterator(KEY) {
1467
1468                        protected Object doGetNext() {
1469                            return lastReturnedNode.getData(KEY);
1470                        }
1471                    };
1472                }
1473
1474                public int size() {
1475                    return DoubleOrderedMap.this.size();
1476                }
1477
1478                public boolean contains(Object o) {
1479                    return containsKey(o);
1480                }
1481
1482                public boolean remove(Object o) {
1483
1484                    int oldNodeCount = nodeCount;
1485
1486                    DoubleOrderedMap.this.remove(o);
1487
1488                    return nodeCount != oldNodeCount;
1489                }
1490
1491                public void clear() {
1492                    DoubleOrderedMap.this.clear();
1493                }
1494            };
1495        }
1496
1497        return setOfKeys[KEY];
1498    }
1499
1500    /**
1501     * Returns a collection view of the values contained in this
1502     * map. The collection is backed by the map, so changes to the map
1503     * are reflected in the collection, and vice-versa. If the map is
1504     * modified while an iteration over the collection is in progress,
1505     * the results of the iteration are undefined. The collection
1506     * supports element removal, which removes the corresponding
1507     * mapping from the map, via the Iterator.remove,
1508     * Collection.remove, removeAll, retainAll and clear operations.
1509     * It does not support the add or addAll operations.
1510     *
1511     * @return a collection view of the values contained in this map.
1512     */
1513    public Collection values() {
1514
1515        if (collectionOfValues[KEY] == null) {
1516            collectionOfValues[KEY] = new AbstractCollection () {
1517
1518                public Iterator iterator() {
1519
1520                    return new DoubleOrderedMapIterator(KEY) {
1521
1522                        protected Object doGetNext() {
1523                            return lastReturnedNode.getData(VALUE);
1524                        }
1525                    };
1526                }
1527
1528                public int size() {
1529                    return DoubleOrderedMap.this.size();
1530                }
1531
1532                public boolean contains(Object o) {
1533                    return containsValue(o);
1534                }
1535
1536                public boolean remove(Object o) {
1537
1538                    int oldNodeCount = nodeCount;
1539
1540                    removeValue(o);
1541
1542                    return nodeCount != oldNodeCount;
1543                }
1544
1545                public boolean removeAll(Collection c) {
1546
1547                    boolean modified = false;
1548                    Iterator iter = c.iterator();
1549
1550                    while (iter.hasNext()) {
1551                        if (removeValue(iter.next()) != null) {
1552                            modified = true;
1553                        }
1554                    }
1555
1556                    return modified;
1557                }
1558
1559                public void clear() {
1560                    DoubleOrderedMap.this.clear();
1561                }
1562            };
1563        }
1564
1565        return collectionOfValues[KEY];
1566    }
1567
1568    /**
1569     * Returns a set view of the mappings contained in this map. Each
1570     * element in the returned set is a Map.Entry. The set is backed
1571     * by the map, so changes to the map are reflected in the set, and
1572     * vice-versa. If the map is modified while an iteration over the
1573     * set is in progress, the results of the iteration are
1574     * undefined.
1575     * <p>
1576     * The set supports element removal, which removes the corresponding
1577     * mapping from the map, via the Iterator.remove, Set.remove, removeAll,
1578     * retainAll and clear operations.
1579     * It does not support the add or addAll operations.
1580     * The setValue method is not supported on the Map Entry.
1581     *
1582     * @return a set view of the mappings contained in this map.
1583     */
1584    public Set entrySet() {
1585
1586        if (setOfEntries[KEY] == null) {
1587            setOfEntries[KEY] = new AbstractSet () {
1588
1589                public Iterator iterator() {
1590
1591                    return new DoubleOrderedMapIterator(KEY) {
1592
1593                        protected Object doGetNext() {
1594                            return lastReturnedNode;
1595                        }
1596                    };
1597                }
1598
1599                public boolean contains(Object o) {
1600
1601                    if (!(o instanceof Map.Entry )) {
1602                        return false;
1603                    }
1604
1605                    Map.Entry entry = (Map.Entry ) o;
1606                    Object value = entry.getValue();
1607                    Node node = lookup((Comparable ) entry.getKey(),
1608                                             KEY);
1609
1610                    return (node != null)
1611                           && node.getData(VALUE).equals(value);
1612                }
1613
1614                public boolean remove(Object o) {
1615
1616                    if (!(o instanceof Map.Entry )) {
1617                        return false;
1618                    }
1619
1620                    Map.Entry entry = (Map.Entry ) o;
1621                    Object value = entry.getValue();
1622                    Node node = lookup((Comparable ) entry.getKey(),
1623                                             KEY);
1624
1625                    if ((node != null) && node.getData(VALUE).equals(value)) {
1626                        doRedBlackDelete(node);
1627
1628                        return true;
1629                    }
1630
1631                    return false;
1632                }
1633
1634                public int size() {
1635                    return DoubleOrderedMap.this.size();
1636                }
1637
1638                public void clear() {
1639                    DoubleOrderedMap.this.clear();
1640                }
1641            };
1642        }
1643
1644        return setOfEntries[KEY];
1645    }
1646
1647    /* ********** END implementation of Map ********** */
1648    private abstract class DoubleOrderedMapIterator implements Iterator {
1649
1650        private int expectedModifications;
1651        protected Node lastReturnedNode;
1652        private Node nextNode;
1653        private int iteratorType;
1654
1655        /**
1656         * Constructor
1657         *
1658         * @param type
1659         */
1660        DoubleOrderedMapIterator(final int type) {
1661
1662            iteratorType = type;
1663            expectedModifications = DoubleOrderedMap.this.modifications;
1664            lastReturnedNode = null;
1665            nextNode = leastNode(rootNode[iteratorType],
1666                                              iteratorType);
1667        }
1668
1669        /**
1670         * @return 'next', whatever that means for a given kind of
1671         * DoubleOrderedMapIterator
1672         */
1673        protected abstract Object doGetNext();
1674
1675        /* ********** START implementation of Iterator ********** */
1676
1677        /**
1678         * @return true if the iterator has more elements.
1679         */
1680        public final boolean hasNext() {
1681            return nextNode != null;
1682        }
1683
1684        /**
1685         * @return the next element in the iteration.
1686         *
1687         * @throws NoSuchElementException if iteration has no more
1688         * elements.
1689         * @throws ConcurrentModificationException if the
1690         * DoubleOrderedMap is
1691         * modified behind
1692         * the iterator's
1693         * back
1694         */
1695        public final Object next()
1696                throws NoSuchElementException ,
1697                       ConcurrentModificationException {
1698
1699            if (nextNode == null) {
1700                throw new NoSuchElementException ();
1701            }
1702
1703            if (modifications != expectedModifications) {
1704                throw new ConcurrentModificationException ();
1705            }
1706
1707            lastReturnedNode = nextNode;
1708            nextNode = nextGreater(nextNode, iteratorType);
1709
1710            return doGetNext();
1711        }
1712
1713        /**
1714         * Removes from the underlying collection the last element
1715         * returned by the iterator. This method can be called only
1716         * once per call to next. The behavior of an iterator is
1717         * unspecified if the underlying collection is modified while
1718         * the iteration is in progress in any way other than by
1719         * calling this method.
1720         *
1721         * @throws IllegalStateException if the next method has not
1722         * yet been called, or the
1723         * remove method has already
1724         * been called after the last
1725         * call to the next method.
1726         * @throws ConcurrentModificationException if the
1727         * DoubleOrderedMap is
1728         * modified behind
1729         * the iterator's
1730         * back
1731         */
1732        public final void remove()
1733                throws IllegalStateException ,
1734                       ConcurrentModificationException {
1735
1736            if (lastReturnedNode == null) {
1737                throw new IllegalStateException ();
1738            }
1739
1740            if (modifications != expectedModifications) {
1741                throw new ConcurrentModificationException ();
1742            }
1743
1744            doRedBlackDelete(lastReturnedNode);
1745
1746            expectedModifications++;
1747
1748            lastReturnedNode = null;
1749        }
1750
1751        /* ********** END implementation of Iterator ********** */
1752    } // end private abstract class DoubleOrderedMapIterator
1753
1754    // final for performance
1755 private static final class Node implements Map.Entry , KeyValue {
1756
1757        private Comparable [] data;
1758        private Node[] leftNode;
1759        private Node[] rightNode;
1760        private Node[] parentNode;
1761        private boolean[] blackColor;
1762        private int hashcodeValue;
1763        private boolean calculatedHashCode;
1764
1765        /**
1766         * Make a new cell with given key and value, and with null
1767         * links, and black (true) colors.
1768         *
1769         * @param key
1770         * @param value
1771         */
1772        Node(final Comparable key, final Comparable value) {
1773
1774            data = new Comparable []{ key, value };
1775            leftNode = new Node[]{ null, null };
1776            rightNode = new Node[]{ null, null };
1777            parentNode = new Node[]{ null, null };
1778            blackColor = new boolean[]{ true, true };
1779            calculatedHashCode = false;
1780        }
1781
1782        /**
1783         * get the specified data
1784         *
1785         * @param index KEY or VALUE
1786         *
1787         * @return the key or value
1788         */
1789        private Comparable getData(final int index) {
1790            return data[index];
1791        }
1792
1793        /**
1794         * Set this node's left node
1795         *
1796         * @param node the new left node
1797         * @param index KEY or VALUE
1798         */
1799        private void setLeft(final Node node, final int index) {
1800            leftNode[index] = node;
1801        }
1802
1803        /**
1804         * get the left node
1805         *
1806         * @param index KEY or VALUE
1807         *
1808         * @return the left node -- may be null
1809         */
1810        private Node getLeft(final int index) {
1811            return leftNode[index];
1812        }
1813
1814        /**
1815         * Set this node's right node
1816         *
1817         * @param node the new right node
1818         * @param index KEY or VALUE
1819         */
1820        private void setRight(final Node node, final int index) {
1821            rightNode[index] = node;
1822        }
1823
1824        /**
1825         * get the right node
1826         *
1827         * @param index KEY or VALUE
1828         *
1829         * @return the right node -- may be null
1830         */
1831        private Node getRight(final int index) {
1832            return rightNode[index];
1833        }
1834
1835        /**
1836         * Set this node's parent node
1837         *
1838         * @param node the new parent node
1839         * @param index KEY or VALUE
1840         */
1841        private void setParent(final Node node, final int index) {
1842            parentNode[index] = node;
1843        }
1844
1845        /**
1846         * get the parent node
1847         *
1848         * @param index KEY or VALUE
1849         *
1850         * @return the parent node -- may be null
1851         */
1852        private Node getParent(final int index) {
1853            return parentNode[index];
1854        }
1855
1856        /**
1857         * exchange colors with another node
1858         *
1859         * @param node the node to swap with
1860         * @param index KEY or VALUE
1861         */
1862        private void swapColors(final Node node, final int index) {
1863
1864            // Swap colors -- old hacker's trick
1865 blackColor[index] ^= node.blackColor[index];
1866            node.blackColor[index] ^= blackColor[index];
1867            blackColor[index] ^= node.blackColor[index];
1868        }
1869
1870        /**
1871         * is this node black?
1872         *
1873         * @param index KEY or VALUE
1874         *
1875         * @return true if black (which is represented as a true boolean)
1876         */
1877        private boolean isBlack(final int index) {
1878            return blackColor[index];
1879        }
1880
1881        /**
1882         * is this node red?
1883         *
1884         * @param index KEY or VALUE
1885         *
1886         * @return true if non-black
1887         */
1888        private boolean isRed(final int index) {
1889            return !blackColor[index];
1890        }
1891
1892        /**
1893         * make this node black
1894         *
1895         * @param index KEY or VALUE
1896         */
1897        private void setBlack(final int index) {
1898            blackColor[index] = true;
1899        }
1900
1901        /**
1902         * make this node red
1903         *
1904         * @param index KEY or VALUE
1905         */
1906        private void setRed(final int index) {
1907            blackColor[index] = false;
1908        }
1909
1910        /**
1911         * make this node the same color as another
1912         *
1913         * @param node the node whose color we're adopting
1914         * @param index KEY or VALUE
1915         */
1916        private void copyColor(final Node node, final int index) {
1917            blackColor[index] = node.blackColor[index];
1918        }
1919
1920        /* ********** START implementation of Map.Entry ********** */
1921
1922        /**
1923         * @return the key corresponding to this entry.
1924         */
1925        public Object getKey() {
1926            return data[KEY];
1927        }
1928
1929        /**
1930         * @return the value corresponding to this entry.
1931         */
1932        public Object getValue() {
1933            return data[VALUE];
1934        }
1935
1936        /**
1937         * Optional operation that is not permitted in this
1938         * implementation
1939         *
1940         * @param ignored
1941         *
1942         * @return does not return
1943         *
1944         * @throws UnsupportedOperationException
1945         */
1946        public Object setValue(Object ignored)
1947                throws UnsupportedOperationException {
1948            throw new UnsupportedOperationException (
1949                "Map.Entry.setValue is not supported");
1950        }
1951
1952        /**
1953         * Compares the specified object with this entry for equality.
1954         * Returns true if the given object is also a map entry and
1955         * the two entries represent the same mapping.
1956         *
1957         * @param o object to be compared for equality with this map
1958         * entry.
1959         * @return true if the specified object is equal to this map
1960         * entry.
1961         */
1962        public boolean equals(Object o) {
1963
1964            if (this == o) {
1965                return true;
1966            }
1967
1968            if (!(o instanceof Map.Entry )) {
1969                return false;
1970            }
1971
1972            Map.Entry e = (Map.Entry ) o;
1973
1974            return data[KEY].equals(e.getKey())
1975                   && data[VALUE].equals(e.getValue());
1976        }
1977
1978        /**
1979         * @return the hash code value for this map entry.
1980         */
1981        public int hashCode() {
1982
1983            if (!calculatedHashCode) {
1984                hashcodeValue = data[KEY].hashCode()
1985                                     ^ data[VALUE].hashCode();
1986                calculatedHashCode = true;
1987            }
1988
1989            return hashcodeValue;
1990        }
1991
1992        /* ********** END implementation of Map.Entry ********** */
1993    }
1994} // end public class DoubleOrderedMap
1995

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags