Java > Open Source Codes > org > apache > poi > util > BinaryTree


1
2 /* ====================================================================
3    Copyright 2002-2004 Apache Software Foundation
4
5    Licensed under the Apache License, Version 2.0 (the "License");
6    you may not use this file except in compliance with the License.
7    You may obtain a copy of the License at
8
9        http://www.apache.org/licenses/LICENSE-2.0
10
11    Unless required by applicable law or agreed to in writing, software
12    distributed under the License is distributed on an "AS IS" BASIS,
13    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14    See the License for the specific language governing permissions and
15    limitations under the License.
16 ==================================================================== */
17         
18
19 package org.apache.poi.util;
20
21 import java.util.*;
22
23 /**
24  * Red-Black tree-based implementation of Map. This class guarantees
25  * that the map will be in both ascending key order and ascending
26  * value order, sorted according to the natural order for the key's
27  * and value's classes.<p>
28  *
29  * This Map is intended for applications that need to be able to look
30  * up a key-value pairing by either key or value, and need to do so
31  * with equal efficiency.<p>
32  *
33  * While that goal could be accomplished by taking a pair of TreeMaps
34  * and redirecting requests to the appropriate TreeMap (e.g.,
35  * containsKey would be directed to the TreeMap that maps values to
36  * keys, containsValue would be directed to the TreeMap that maps keys
37  * to values), there are problems with that implementation,
38  * particularly when trying to keep the two TreeMaps synchronized with
39  * each other. And if the data contained in the TreeMaps is large, the
40  * cost of redundant storage becomes significant.<p>
41  *
42  * This solution keeps the data properly synchronized and minimizes
43  * the data storage. The red-black algorithm is based on TreeMap's,
44  * but has been modified to simultaneously map a tree node by key and
45  * by value. This doubles the cost of put operations (but so does
46  * using two TreeMaps), and nearly doubles the cost of remove
47  * operations (there is a savings in that the lookup of the node to be
48  * removed only has to be performed once). And since only one node
49  * contains the key and value, storage is significantly less than that
50  * required by two TreeMaps.<p>
51  *
52  * There are some limitations placed on data kept in this Map. The
53  * biggest one is this:<p>
54  *
55  * When performing a put operation, neither the key nor the value may
56  * already exist in the Map. In the java.util Map implementations
57  * (HashMap, TreeMap), you can perform a put with an already mapped
58  * key, and neither cares about duplicate values at all ... but this
59  * implementation's put method with throw an IllegalArgumentException
60  * if either the key or the value is already in the Map.<p>
61  *
62  * Obviously, that same restriction (and consequence of failing to
63  * heed that restriction) applies to the putAll method.<p>
64  *
65  * The Map.Entry instances returned by the appropriate methods will
66  * not allow setValue() and will throw an
67  * UnsupportedOperationException on attempts to call that method.<p>
68  *
69  * New methods are added to take advantage of the fact that values are
70  * kept sorted independently of their keys:<p>
71  *
72  * Object getKeyForValue(Object value) is the opposite of get; it
73  * takes a value and returns its key, if any.<p>
74  *
75  * Object removeValue(Object value) finds and removes the specified
76  * value and returns the now un-used key.<p>
77  *
78  * Set entrySetByValue() returns the Map.Entry's in a Set whose
79  * iterator will iterate over the Map.Entry's in ascending order by
80  * their corresponding values.<p>
81  *
82  * Set keySetByValue() returns the keys in a Set whose iterator will
83  * iterate over the keys in ascending order by their corresponding
84  * values.<p>
85  *
86  * Collection valuesByValue() returns the values in a Collection whose
87  * iterator will iterate over the values in ascending order.<p>
88  *
89  * @author Marc Johnson (mjohnson at apache dot org)
90  */
91 public final class BinaryTree // final for performance
92
93     extends AbstractMap
94 {
95     private Node[] _root = new Node[]
96     {
97         null, null
98     };
99     private int _size = 0;
100     private int _modifications = 0;
101     private Set[] _key_set = new Set[]
102     {
103         null, null
104     };
105     private Set[] _entry_set = new Set[]
106     {
107         null, null
108     };
109     private Collection[] _value_collection = new Collection[]
110     {
111         null, null
112     };
113     private static final int _KEY = 0;
114     private static final int _VALUE = 1;
115     private static final int _INDEX_SUM = _KEY + _VALUE;
116     private static final int _MINIMUM_INDEX = 0;
117     private static final int _INDEX_COUNT = 2;
118     private static final String [] _data_name = new String []
119     {
120         "key", "value"
121     };
122
123     /**
124      * Construct a new BinaryTree
125      */
126
127     public BinaryTree()
128     {
129     }
130
131     /**
132      * Constructs a new BinaryTree from an existing Map, with keys and
133      * values sorted
134      *
135      * @param map the map whose mappings are to be placed in this map.
136      *
137      * @exception ClassCastException if the keys in the map are not
138      * Comparable, or are not mutually
139      * comparable; also if the values in
140      * the map are not Comparable, or
141      * are not mutually Comparable
142      * @exception NullPointerException if any key or value in the map
143      * is null
144      * @exception IllegalArgumentException if there are duplicate keys
145      * or duplicate values in the
146      * map
147      */
148
149     public BinaryTree(final Map map)
150         throws ClassCastException , NullPointerException ,
151                 IllegalArgumentException
152     {
153         putAll(map);
154     }
155
156     /**
157      * Returns the key to which this map maps the specified value.
158      * Returns null if the map contains no mapping for this value.
159      *
160      * @param value value whose associated key is to be returned.
161      *
162      * @return the key to which this map maps the specified value, or
163      * null if the map contains no mapping for this value.
164      *
165      * @exception ClassCastException if the value is of an
166      * inappropriate type for this map.
167      * @exception NullPointerException if the value is null
168      */
169
170     public Object getKeyForValue(final Object value)
171         throws ClassCastException , NullPointerException
172     {
173         return doGet(( Comparable ) value, _VALUE);
174     }
175
176     /**
177      * Removes the mapping for this value from this map if present
178      *
179      * @param value value whose mapping is to be removed from the map.
180      *
181      * @return previous key associated with specified value, or null
182      * if there was no mapping for value.
183      */
184
185     public Object removeValue(final Object value)
186     {
187         return doRemove(( Comparable ) value, _VALUE);
188     }
189
190     /**
191      * Returns a set view of the mappings contained in this map. Each
192      * element in the returned set is a Map.Entry. The set is backed
193      * by the map, so changes to the map are reflected in the set, and
194      * vice-versa. If the map is modified while an iteration over the
195      * set is in progress, the results of the iteration are
196      * undefined. The set supports element removal, which removes the
197      * corresponding mapping from the map, via the Iterator.remove,
198      * Set.remove, removeAll, retainAll and clear operations. It does
199      * not support the add or addAll operations.<p>
200      *
201      * The difference between this method and entrySet is that
202      * entrySet's iterator() method returns an iterator that iterates
203      * over the mappings in ascending order by key. This method's
204      * iterator method iterates over the mappings in ascending order
205      * by value.
206      *
207      * @return a set view of the mappings contained in this map.
208      */
209
210     public Set entrySetByValue()
211     {
212         if (_entry_set[ _VALUE ] == null)
213         {
214             _entry_set[ _VALUE ] = new AbstractSet()
215             {
216                 public Iterator iterator()
217                 {
218                     return new BinaryTreeIterator(_VALUE)
219                     {
220                         protected Object doGetNext()
221                         {
222                             return _last_returned_node;
223                         }
224                     };
225                 }
226
227                 public boolean contains(Object o)
228                 {
229                     if (!(o instanceof Map.Entry))
230                     {
231                         return false;
232                     }
233                     Map.Entry entry = ( Map.Entry ) o;
234                     Object key = entry.getKey();
235                     Node node = lookup(( Comparable ) entry.getValue(),
236                                              _VALUE);
237
238                     return (node != null) && node.getData(_KEY).equals(key);
239                 }
240
241                 public boolean remove(Object o)
242                 {
243                     if (!(o instanceof Map.Entry))
244                     {
245                         return false;
246                     }
247                     Map.Entry entry = ( Map.Entry ) o;
248                     Object key = entry.getKey();
249                     Node node = lookup(( Comparable ) entry.getValue(),
250                                              _VALUE);
251
252                     if ((node != null) && node.getData(_KEY).equals(key))
253                     {
254                         doRedBlackDelete(node);
255                         return true;
256                     }
257                     return false;
258                 }
259
260                 public int size()
261                 {
262                     return BinaryTree.this.size();
263                 }
264
265                 public void clear()
266                 {
267                     BinaryTree.this.clear();
268                 }
269             };
270         }
271         return _entry_set[ _VALUE ];
272     }
273
274     /**
275      * Returns a set view of the keys contained in this map. The set
276      * is backed by the map, so changes to the map are reflected in
277      * the set, and vice-versa. If the map is modified while an
278      * iteration over the set is in progress, the results of the
279      * iteration are undefined. The set supports element removal,
280      * which removes the corresponding mapping from the map, via the
281      * Iterator.remove, Set.remove, removeAll, retainAll, and clear
282      * operations. It does not support the add or addAll
283      * operations.<p>
284      *
285      * The difference between this method and keySet is that keySet's
286      * iterator() method returns an iterator that iterates over the
287      * keys in ascending order by key. This method's iterator method
288      * iterates over the keys in ascending order by value.
289      *
290      * @return a set view of the keys contained in this map.
291      */
292
293     public Set keySetByValue()
294     {
295         if (_key_set[ _VALUE ] == null)
296         {
297             _key_set[ _VALUE ] = new AbstractSet()
298             {
299                 public Iterator iterator()
300                 {
301                     return new BinaryTreeIterator(_VALUE)
302                     {
303                         protected Object doGetNext()
304                         {
305                             return _last_returned_node.getData(_KEY);
306                         }
307                     };
308                 }
309
310                 public int size()
311                 {
312                     return BinaryTree.this.size();
313                 }
314
315                 public boolean contains(Object o)
316                 {
317                     return containsKey(o);
318                 }
319
320                 public boolean remove(Object o)
321                 {
322                     int old_size = _size;
323
324                     BinaryTree.this.remove(o);
325                     return _size != old_size;
326                 }
327
328                 public void clear()
329                 {
330                     BinaryTree.this.clear();
331                 }
332             };
333         }
334         return _key_set[ _VALUE ];
335     }
336
337     /**
338      * Returns a collection view of the values contained in this
339      * map. The collection is backed by the map, so changes to the map
340      * are reflected in the collection, and vice-versa. If the map is
341      * modified while an iteration over the collection is in progress,
342      * the results of the iteration are undefined. The collection
343      * supports element removal, which removes the corresponding
344      * mapping from the map, via the Iterator.remove,
345      * Collection.remove, removeAll, retainAll and clear operations.
346      * It does not support the add or addAll operations.<p>
347      *
348      * The difference between this method and values is that values's
349      * iterator() method returns an iterator that iterates over the
350      * values in ascending order by key. This method's iterator method
351      * iterates over the values in ascending order by key.
352      *
353      * @return a collection view of the values contained in this map.
354      */
355
356     public Collection valuesByValue()
357     {
358         if (_value_collection[ _VALUE ] == null)
359         {
360             _value_collection[ _VALUE ] = new AbstractCollection()
361             {
362                 public Iterator iterator()
363                 {
364                     return new BinaryTreeIterator(_VALUE)
365                     {
366                         protected Object doGetNext()
367                         {
368                             return _last_returned_node.getData(_VALUE);
369                         }
370                     };
371                 }
372
373                 public int size()
374                 {
375                     return BinaryTree.this.size();
376                 }
377
378                 public boolean contains(Object o)
379                 {
380                     return containsValue(o);
381                 }
382
383                 public boolean remove(Object o)
384                 {
385                     int old_size = _size;
386
387                     removeValue(o);
388                     return _size != old_size;
389                 }
390
391                 public boolean removeAll(Collection c)
392                 {
393                     boolean modified = false;
394                     Iterator iter = c.iterator();
395
396                     while (iter.hasNext())
397                     {
398                         if (removeValue(iter.next()) != null)
399                         {
400                             modified = true;
401                         }
402                     }
403                     return modified;
404                 }
405
406                 public void clear()
407                 {
408                     BinaryTree.this.clear();
409                 }
410             };
411         }
412         return _value_collection[ _VALUE ];
413     }
414
415     /**
416      * common remove logic (remove by key or remove by value)
417      *
418      * @param o the key, or value, that we're looking for
419      * @param index _KEY or _VALUE
420      *
421      * @return the key, if remove by value, or the value, if remove by
422      * key. null if the specified key or value could not be
423      * found
424      */
425
426     private Object doRemove(final Comparable o, final int index)
427     {
428         Node node = lookup(o, index);
429         Object rval = null;
430
431         if (node != null)
432         {
433             rval = node.getData(oppositeIndex(index));
434             doRedBlackDelete(node);
435         }
436         return rval;
437     }
438
439     /**
440      * common get logic, used to get by key or get by value
441      *
442      * @param o the key or value that we're looking for
443      * @param index _KEY or _VALUE
444      *
445      * @return the key (if the value was mapped) or the value (if the
446      * key was mapped); null if we couldn't find the specified
447      * object
448      */
449
450     private Object doGet(final Comparable o, final int index)
451     {
452         checkNonNullComparable(o, index);
453         Node node = lookup(o, index);
454
455         return ((node == null) ? null
456                                : node.getData(oppositeIndex(index)));
457     }
458
459     /**
460      * Get the opposite index of the specified index
461      *
462      * @param index _KEY or _VALUE
463      *
464      * @return _VALUE (if _KEY was specified), else _KEY
465      */
466
467     private int oppositeIndex(final int index)
468     {
469
470         // old trick ... to find the opposite of a value, m or n,
471 // subtract the value from the sum of the two possible
472 // values. (m + n) - m = n; (m + n) - n = m
473 return _INDEX_SUM - index;
474     }
475
476     /**
477      * do the actual lookup of a piece of data
478      *
479      * @param data the key or value to be looked up
480      * @param index _KEY or _VALUE
481      *
482      * @return the desired Node, or null if there is no mapping of the
483      * specified data
484      */
485
486     private Node lookup(final Comparable data, final int index)
487     {
488         Node rval = null;
489         Node node = _root[ index ];
490
491         while (node != null)
492         {
493             int cmp = compare(data, node.getData(index));
494
495             if (cmp == 0)
496             {
497                 rval = node;
498                 break;
499             }
500             else
501             {
502                 node = (cmp < 0) ? node.getLeft(index)
503                                  : node.getRight(index);
504             }
505         }
506         return rval;
507     }
508
509     /**
510      * Compare two objects
511      *
512      * @param o1 the first object
513      * @param o2 the second object
514      *
515      * @return negative value if o1 < o2; 0 if o1 == o2; positive
516      * value if o1 > o2
517      */
518
519     private static int compare(final Comparable o1, final Comparable o2)
520     {
521         return (( Comparable ) o1).compareTo(o2);
522     }
523
524     /**
525      * find the least node from a given node. very useful for starting
526      * a sorting iterator ...
527      *
528      * @param node the node from which we will start searching
529      * @param index _KEY or _VALUE
530      *
531      * @return the smallest node, from the specified node, in the
532      * specified mapping
533      */
534
535     private static Node leastNode(final Node node, final int index)
536     {
537         Node rval = node;
538
539         if (rval != null)
540         {
541             while (rval.getLeft(index) != null)
542             {
543                 rval = rval.getLeft(index);
544             }
545         }
546         return rval;
547     }
548
549     /**
550      * get the next larger node from the specified node
551      *
552      * @param node the node to be searched from
553      * @param index _KEY or _VALUE
554      *
555      * @return the specified node
556      */
557
558     private Node nextGreater(final Node node, final int index)
559     {
560         Node rval = null;
561
562         if (node == null)
563         {
564             rval = null;
565         }
566         else if (node.getRight(index) != null)
567         {
568
569             // everything to the node's right is larger. The least of
570 // the right node's descendents is the next larger node
571 rval = leastNode(node.getRight(index), index);
572         }
573         else
574         {
575
576             // traverse up our ancestry until we find an ancestor that
577 // is null or one whose left child is our ancestor. If we
578 // find a null, then this node IS the largest node in the
579 // tree, and there is no greater node. Otherwise, we are
580 // the largest node in the subtree on that ancestor's left
581 // ... and that ancestor is the next greatest node
582 Node parent = node.getParent(index);
583             Node child = node;
584
585             while ((parent != null) && (child == parent.getRight(index)))
586             {
587                 child = parent;
588                 parent = parent.getParent(index);
589             }
590             rval = parent;
591         }
592         return rval;
593     }
594
595     /**
596      * copy the color from one node to another, dealing with the fact
597      * that one or both nodes may, in fact, be null
598      *
599      * @param from the node whose color we're copying; may be null
600      * @param to the node whose color we're changing; may be null
601      * @param index _KEY or _VALUE
602      */
603
604     private static void copyColor(final Node from, final Node to,
605                                   final int index)
606     {
607         if (to != null)
608         {
609             if (from == null)
610             {
611
612                 // by default, make it black
613 to.setBlack(index);
614             }
615             else
616             {
617                 to.copyColor(from, index);
618             }
619         }
620     }
621
622     /**
623      * is the specified node red? if the node does not exist, no, it's
624      * black, thank you
625      *
626      * @param node the node (may be null) in question
627      * @param index _KEY or _VALUE
628      */
629
630     private static boolean isRed(final Node node, final int index)
631     {
632         return ((node == null) ? false
633                                : node.isRed(index));
634     }
635
636     /**
637      * is the specified black red? if the node does not exist, sure,
638      * it's black, thank you
639      *
640      * @param node the node (may be null) in question
641      * @param index _KEY or _VALUE
642      */
643
644     private static boolean isBlack(final Node node, final int index)
645     {
646         return ((node == null) ? true
647                                : node.isBlack(index));
648     }
649
650     /**
651      * force a node (if it exists) red
652      *
653      * @param node the node (may be null) in question
654      * @param index _KEY or _VALUE
655      */
656
657     private static void makeRed(final Node node, final int index)
658     {
659         if (node != null)
660         {
661             node.setRed(index);
662         }
663     }
664
665     /**
666      * force a node (if it exists) black
667      *
668      * @param node the node (may be null) in question
669      * @param index _KEY or _VALUE
670      */
671
672     private static void makeBlack(final Node node, final int index)
673     {
674         if (node != null)
675         {
676             node.setBlack(index);
677         }
678     }
679
680     /**
681      * get a node's grandparent. mind you, the node, its parent, or
682      * its grandparent may not exist. no problem
683      *
684      * @param node the node (may be null) in question
685      * @param index _KEY or _VALUE
686      */
687
688     private static Node getGrandParent(final Node node, final int index)
689     {
690         return getParent(getParent(node, index), index);
691     }
692
693     /**
694      * get a node's parent. mind you, the node, or its parent, may not
695      * exist. no problem
696      *
697      * @param node the node (may be null) in question
698      * @param index _KEY or _VALUE
699      */
700
701     private static Node getParent(final Node node, final int index)
702     {
703         return ((node == null) ? null
704                                : node.getParent(index));
705     }
706
707     /**
708      * get a node's right child. mind you, the node may not exist. no
709      * problem
710      *
711      * @param node the node (may be null) in question
712      * @param index _KEY or _VALUE
713      */
714
715     private static Node getRightChild(final Node node, final int index)
716     {
717         return (node == null) ? null
718                               : node.getRight(index);
719     }
720
721     /**
722      * get a node's left child. mind you, the node may not exist. no
723      * problem
724      *
725      * @param node the node (may be null) in question
726      * @param index _KEY or _VALUE
727      */
728
729     private static Node getLeftChild(final Node node, final int index)
730     {
731         return (node == null) ? null
732                               : node.getLeft(index);
733     }
734
735     /**
736      * is this node its parent's left child? mind you, the node, or
737      * its parent, may not exist. no problem. if the node doesn't
738      * exist ... it's its non-existent parent's left child. If the
739      * node does exist but has no parent ... no, we're not the
740      * non-existent parent's left child. Otherwise (both the specified
741      * node AND its parent exist), check.
742      *
743      * @param node the node (may be null) in question
744      * @param index _KEY or _VALUE
745      */
746
747     private static boolean isLeftChild(final Node node, final int index)
748     {
749         return (node == null) ? true
750                               : ((node.getParent(index) == null) ? false
751                                                                  : (node
752                                                                     == node.getParent(
753                                                                         index).getLeft(
754                                                                         index)));
755     }
756
757     /**
758      * is this node its parent's right child? mind you, the node, or
759      * its parent, may not exist. no problem. if the node doesn't
760      * exist ... it's its non-existent parent's right child. If the
761      * node does exist but has no parent ... no, we're not the
762      * non-existent parent's right child. Otherwise (both the
763      * specified node AND its parent exist), check.
764      *
765      * @param node the node (may be null) in question
766      * @param index _KEY or _VALUE
767      */
768
769     private static boolean isRightChild(final Node node, final int index)
770     {
771         return (node == null) ? true
772                               : ((node.getParent(index) == null) ? false
773                                                                  : (node
774                                                                     == node.getParent(
775                                                                         index).getRight(
776                                                                         index)));
777     }
778
779     /**
780      * do a rotate left. standard fare in the world of balanced trees
781      *
782      * @param node the node to be rotated
783      * @param index _KEY or _VALUE
784      */
785
786     private void rotateLeft(final Node node, final int index)
787     {
788         Node right_child = node.getRight(index);
789
790         node.setRight(right_child.getLeft(index), index);
791         if (right_child.getLeft(index) != null)
792         {
793             right_child.getLeft(index).setParent(node, index);
794         }
795         right_child.setParent(node.getParent(index), index);
796         if (node.getParent(index) == null)
797         {
798
799             // node was the root ... now its right child is the root
800 _root[ index ] = right_child;
801         }
802         else if (node.getParent(index).getLeft(index) == node)
803         {
804             node.getParent(index).setLeft(right_child, index);
805         }
806         else
807         {
808             node.getParent(index).setRight(right_child, index);
809         }
810         right_child.setLeft(node, index);
811         node.setParent(right_child, index);
812     }
813
814     /**
815      * do a rotate right. standard fare in the world of balanced trees
816      *
817      * @param node the node to be rotated
818      * @param index _KEY or _VALUE
819      */
820
821     private void rotateRight(final Node node, final int index)
822     {
823         Node left_child = node.getLeft(index);
824
825         node.setLeft(left_child.getRight(index), index);
826         if (left_child.getRight(index) != null)
827         {
828             left_child.getRight(index).setParent(node, index);
829         }
830         left_child.setParent(node.getParent(index), index);
831         if (node.getParent(index) == null)
832         {
833
834             // node was the root ... now its left child is the root
835 _root[ index ] = left_child;
836         }
837         else if (node.getParent(index).getRight(index) == node)
838         {
839             node.getParent(index).setRight(left_child, index);
840         }
841         else
842         {
843             node.getParent(index).setLeft(left_child, index);
844         }
845         left_child.setRight(node, index);
846         node.setParent(left_child, index);
847     }
848
849     /**
850      * complicated red-black insert stuff. Based on Sun's TreeMap
851      * implementation, though it's barely recognizeable any more
852      *
853      * @param inserted_node the node to be inserted
854      * @param index _KEY or _VALUE
855      */
856
857     private void doRedBlackInsert(final Node inserted_node, final int index)
858     {
859         Node current_node = inserted_node;
860
861         makeRed(current_node, index);
862         while ((current_node != null) && (current_node != _root[ index ])
863                 && (isRed(current_node.getParent(index), index)))
864         {
865             if (isLeftChild(getParent(current_node, index), index))
866             {
867                 Node y = getRightChild(getGrandParent(current_node, index),
868                                        index);
869
870                 if (isRed(y, index))
871                 {
872                     makeBlack(getParent(current_node, index), index);
873                     makeBlack(y, index);
874                     makeRed(getGrandParent(current_node, index), index);
875                     current_node = getGrandParent(current_node, index);
876                 }
877                 else
878                 {
879                     if (isRightChild(current_node, index))
880                     {
881                         current_node = getParent(current_node, index);
882                         rotateLeft(current_node, index);
883                     }
884                     makeBlack(getParent(current_node, index), index);
885                     makeRed(getGrandParent(current_node, index), index);
886                     if (getGrandParent(current_node, index) != null)
887                     {
888                         rotateRight(getGrandParent(current_node, index),
889                                     index);
890                     }
891                 }
892             }
893             else
894             {
895
896                 // just like clause above, except swap left for right
897 Node y = getLeftChild(getGrandParent(current_node, index),
898                                       index);
899
900                 if (isRed(y, index))
901                 {
902                     makeBlack(getParent(current_node, index), index);
903                     makeBlack(y, index);
904                     makeRed(getGrandParent(current_node, index), index);
905                     current_node = getGrandParent(current_node, index);
906                 }
907                 else
908                 {
909                     if (isLeftChild(current_node, index))
910                     {
911                         current_node = getParent(current_node, index);
912                         rotateRight(current_node, index);
913                     }
914                     makeBlack(getParent(current_node, index), index);
915                     makeRed(getGrandParent(current_node, index), index);
916                     if (getGrandParent(current_node, index) != null)
917                     {
918                         rotateLeft(getGrandParent(current_node, index),
919                                    index);
920                     }
921                 }
922             }
923         }
924         makeBlack(_root[ index ], index);
925     }
926
927     /**
928      * complicated red-black delete stuff. Based on Sun's TreeMap
929      * implementation, though it's barely recognizeable any more
930      *
931      * @param deleted_node the node to be deleted
932      */
933
934     private void doRedBlackDelete(final Node deleted_node)
935     {
936         for (int index = _MINIMUM_INDEX; index < _INDEX_COUNT; index++)
937         {
938
939             // if deleted node has both left and children, swap with
940 // the next greater node
941 if ((deleted_node.getLeft(index) != null)
942                     && (deleted_node.getRight(index) != null))
943             {
944                 swapPosition(nextGreater(deleted_node, index), deleted_node,
945                              index);
946             }
947             Node replacement = ((deleted_node.getLeft(index) != null)
948                                 ? deleted_node.getLeft(index)
949                                 : deleted_node.getRight(index));
950
951             if (replacement != null)
952             {
953                 replacement.setParent(deleted_node.getParent(index), index);
954                 if (deleted_node.getParent(index) == null)
955                 {
956                     _root[ index ] = replacement;
957                 }
958                 else if (deleted_node
959                          == deleted_node.getParent(index).getLeft(index))
960                 {
961                     deleted_node.getParent(index).setLeft(replacement, index);
962                 }
963                 else
964                 {
965                     deleted_node.getParent(index).setRight(replacement,
966                                            index);
967                 }
968                 deleted_node.setLeft(null, index);
969                 deleted_node.setRight(null, index);
970                 deleted_node.setParent(null, index);
971                 if (isBlack(deleted_node, index))
972                 {
973                     doRedBlackDeleteFixup(replacement, index);
974                 }
975             }
976             else
977             {
978
979                 // replacement is null
980 if (deleted_node.getParent(index) == null)
981                 {
982
983                     // empty tree
984 _root[ index ] = null;
985                 }
986                 else
987                 {
988
989                     // deleted node had no children
990 if (isBlack(deleted_node, index))
991                     {
992                         doRedBlackDeleteFixup(deleted_node, index);
993                     }
994                     if (deleted_node.getParent(index) != null)
995                     {
996                         if (deleted_node
997                                 == deleted_node.getParent(index)
998                                     .getLeft(index))
999                         {
1000                            deleted_node.getParent(index).setLeft(null,
1001                                                   index);
1002                        }
1003                        else
1004                        {
1005                            deleted_node.getParent(index).setRight(null,
1006                                                   index);
1007                        }
1008                        deleted_node.setParent(null, index);
1009                    }
1010                }
1011            }
1012        }
1013        shrink();
1014    }
1015
1016    /**
1017     * complicated red-black delete stuff. Based on Sun's TreeMap
1018     * implementation, though it's barely recognizeable any more. This
1019     * rebalances the tree (somewhat, as red-black trees are not
1020     * perfectly balanced -- perfect balancing takes longer)
1021     *
1022     * @param replacement_node the node being replaced
1023     * @param index _KEY or _VALUE
1024     */
1025
1026    private void doRedBlackDeleteFixup(final Node replacement_node,
1027                                       final int index)
1028    {
1029        Node current_node = replacement_node;
1030
1031        while ((current_node != _root[ index ])
1032                && (isBlack(current_node, index)))
1033        {
1034            if (isLeftChild(current_node, index))
1035            {
1036                Node sibling_node =
1037                    getRightChild(getParent(current_node, index), index);
1038
1039                if (isRed(sibling_node, index))
1040                {
1041                    makeBlack(sibling_node, index);
1042                    makeRed(getParent(current_node, index), index);
1043                    rotateLeft(getParent(current_node, index), index);
1044                    sibling_node =
1045                        getRightChild(getParent(current_node, index), index);
1046                }
1047                if (isBlack(getLeftChild(sibling_node, index), index)
1048                        && isBlack(getRightChild(sibling_node, index), index))
1049                {
1050                    makeRed(sibling_node, index);
1051                    current_node = getParent(current_node, index);
1052                }
1053                else
1054                {
1055                    if (isBlack(getRightChild(sibling_node, index), index))
1056                    {
1057                        makeBlack(getLeftChild(sibling_node, index), index);
1058                        makeRed(sibling_node, index);
1059                        rotateRight(sibling_node, index);
1060                        sibling_node =
1061                            getRightChild(getParent(current_node, index),
1062                                          index);
1063                    }
1064                    copyColor(getParent(current_node, index), sibling_node,
1065                              index);
1066                    makeBlack(getParent(current_node, index), index);
1067                    makeBlack(getRightChild(sibling_node, index), index);
1068                    rotateLeft(getParent(current_node, index), index);
1069                    current_node = _root[ index ];
1070                }
1071            }
1072            else
1073            {
1074                Node sibling_node =
1075                    getLeftChild(getParent(current_node, index), index);
1076
1077                if (isRed(sibling_node, index))
1078                {
1079                    makeBlack(sibling_node, index);
1080                    makeRed(getParent(current_node, index), index);
1081                    rotateRight(getParent(current_node, index), index);
1082                    sibling_node =
1083                        getLeftChild(getParent(current_node, index), index);
1084                }
1085                if (isBlack(getRightChild(sibling_node, index), index)
1086                        && isBlack(getLeftChild(sibling_node, index), index))
1087                {
1088                    makeRed(sibling_node, index);
1089                    current_node = getParent(current_node, index);
1090                }
1091                else
1092                {
1093                    if (isBlack(getLeftChild(sibling_node, index), index))
1094                    {
1095                        makeBlack(getRightChild(sibling_node, index), index);
1096                        makeRed(sibling_node, index);
1097                        rotateLeft(sibling_node, index);
1098                        sibling_node =
1099                            getLeftChild(getParent(current_node, index),
1100                                         index);
1101                    }
1102                    copyColor(getParent(current_node, index), sibling_node,
1103                              index);
1104                    makeBlack(getParent(current_node, index), index);
1105                    makeBlack(getLeftChild(sibling_node, index), index);
1106                    rotateRight(getParent(current_node, index), index);
1107                    current_node = _root[ index ];
1108                }
1109            }
1110        }
1111        makeBlack(current_node, index);
1112    }
1113
1114    /**
1115     * swap two nodes (except for their content), taking care of
1116     * special cases where one is the other's parent ... hey, it
1117     * happens.
1118     *
1119     * @param x one node
1120     * @param y another node
1121     * @param index _KEY or _VALUE
1122     */
1123
1124    private void swapPosition(final Node x, final Node y, final int index)
1125    {
1126
1127        // Save initial values.
1128 Node x_old_parent = x.getParent(index);
1129        Node x_old_left_child = x.getLeft(index);
1130        Node x_old_right_child = x.getRight(index);
1131        Node y_old_parent = y.getParent(index);
1132        Node y_old_left_child = y.getLeft(index);
1133        Node y_old_right_child = y.getRight(index);
1134        boolean x_was_left_child =
1135            (x.getParent(index) != null)
1136            && (x == x.getParent(index).getLeft(index));
1137        boolean y_was_left_child =
1138            (y.getParent(index) != null)
1139            && (y == y.getParent(index).getLeft(index));
1140
1141        // Swap, handling special cases of one being the other's parent.
1142 if (x == y_old_parent)
1143        { // x was y's parent
1144 x.setParent(y, index);
1145            if (y_was_left_child)
1146            {
1147                y.setLeft(x, index);
1148                y.setRight(x_old_right_child, index);
1149            }
1150            else
1151            {
1152                y.setRight(x, index);
1153                y.setLeft(x_old_left_child, index);
1154            }
1155        }
1156        else
1157        {
1158            x.setParent(y_old_parent, index);
1159            if (y_old_parent != null)
1160            {
1161                if (y_was_left_child)
1162                {
1163                    y_old_parent.setLeft(x, index);
1164                }
1165                else
1166                {
1167                    y_old_parent.setRight(x, index);
1168                }
1169            }
1170            y.setLeft(x_old_left_child, index);
1171            y.setRight(x_old_right_child, index);
1172        }
1173        if (y == x_old_parent)
1174        { // y was x's parent
1175 y.setParent(x, index);
1176            if (x_was_left_child)
1177            {
1178                x.setLeft(y, index);
1179                x.setRight(y_old_right_child, index);
1180            }
1181            else
1182            {
1183                x.setRight(y, index);
1184                x.setLeft(y_old_left_child, index);
1185            }
1186        }
1187        else
1188        {
1189            y.setParent(x_old_parent, index);
1190            if (x_old_parent != null)
1191            {
1192                if (x_was_left_child)
1193                {
1194                    x_old_parent.setLeft(y, index);
1195                }
1196                else
1197                {
1198                    x_old_parent.setRight(y, index);
1199                }
1200            }
1201            x.setLeft(y_old_left_child, index);
1202            x.setRight(y_old_right_child, index);
1203        }
1204
1205        // Fix children's parent pointers
1206 if (x.getLeft(index) != null)
1207        {
1208            x.getLeft(index).setParent(x, index);
1209        }
1210        if (x.getRight(index) != null)
1211        {
1212            x.getRight(index).setParent(x, index);
1213        }
1214        if (y.getLeft(index) != null)
1215        {
1216            y.getLeft(index).setParent(y, index);
1217        }
1218        if (y.getRight(index) != null)
1219        {
1220            y.getRight(index).setParent(y, index);
1221        }
1222        x.swapColors(y, index);
1223
1224        // Check if _root changed
1225 if (_root[ index ] == x)
1226        {
1227            _root[ index ] = y;
1228        }
1229        else if (_root[ index ] == y)
1230        {
1231            _root[ index ] = x;
1232        }
1233    }
1234
1235    /**
1236     * check if an object is fit to be proper input ... has to be
1237     * Comparable and non-null
1238     *
1239     * @param o the object being checked
1240     * @param index _KEY or _VALUE (used to put the right word in the
1241     * exception message)
1242     *
1243     * @exception NullPointerException if o is null
1244     * @exception ClassCastException if o is not Comparable
1245     */
1246
1247    private static void checkNonNullComparable(final Object o,
1248                                               final int index)
1249    {
1250        if (o == null)
1251        {
1252            throw new NullPointerException (_data_name[ index ]
1253                                           + " cannot be null");
1254        }
1255        if (!(o instanceof Comparable ))
1256        {
1257            throw new ClassCastException (_data_name[ index ]
1258                                         + " must be Comparable");
1259        }
1260    }
1261
1262    /**
1263     * check a key for validity (non-null and implements Comparable)
1264     *
1265     * @param key the key to be checked
1266     *
1267     * @exception NullPointerException if key is null
1268     * @exception ClassCastException if key is not Comparable
1269     */
1270
1271    private static void checkKey(final Object key)
1272    {
1273        checkNonNullComparable(key, _KEY);
1274    }
1275
1276    /**
1277     * check a value for validity (non-null and implements Comparable)
1278     *
1279     * @param value the value to be checked
1280     *
1281     * @exception NullPointerException if value is null
1282     * @exception ClassCastException if value is not Comparable
1283     */
1284
1285    private static void checkValue(final Object value)
1286    {
1287        checkNonNullComparable(value, _VALUE);
1288    }
1289
1290    /**
1291     * check a key and a value for validity (non-null and implements
1292     * Comparable)
1293     *
1294     * @param key the key to be checked
1295     * @param value the value to be checked
1296     *
1297     * @exception NullPointerException if key or value is null
1298     * @exception ClassCastException if key or value is not Comparable
1299     */
1300
1301    private static void checkKeyAndValue(final Object key, final Object value)
1302    {
1303        checkKey(key);
1304        checkValue(value);
1305    }
1306
1307    /**
1308     * increment the modification count -- used to check for
1309     * concurrent modification of the map through the map and through
1310     * an Iterator from one of its Set or Collection views
1311     */
1312
1313    private void modify()
1314    {
1315        _modifications++;
1316    }
1317
1318    /**
1319     * bump up the size and note that the map has changed
1320     */
1321
1322    private void grow()
1323    {
1324        modify();
1325        _size++;
1326    }
1327
1328    /**
1329     * decrement the size and note that the map has changed
1330     */
1331
1332    private void shrink()
1333    {
1334        modify();
1335        _size--;
1336    }
1337
1338    /**
1339     * insert a node by its value
1340     *
1341     * @param newNode the node to be inserted
1342     *
1343     * @exception IllegalArgumentException if the node already exists
1344     * in the value mapping
1345     */
1346
1347    private void insertValue(final Node newNode)
1348        throws IllegalArgumentException
1349    {
1350        Node node = _root[ _VALUE ];
1351
1352        while (true)
1353        {
1354            int cmp = compare(newNode.getData(_VALUE), node.getData(_VALUE));
1355
1356            if (cmp == 0)
1357            {
1358                throw new IllegalArgumentException (
1359                    "Cannot store a duplicate value (\""
1360                    + newNode.getData(_VALUE) + "\") in this Map");
1361            }
1362            else if (cmp < 0)
1363            {
1364                if (node.getLeft(_VALUE) != null)
1365                {
1366                    node = node.getLeft(_VALUE);
1367                }
1368                else
1369                {
1370                    node.setLeft(newNode, _VALUE);
1371                    newNode.setParent(node, _VALUE);
1372                    doRedBlackInsert(newNode, _VALUE);
1373                    break;
1374                }
1375            }
1376            else
1377            { // cmp > 0
1378 if (node.getRight(_VALUE) != null)
1379                {
1380                    node = node.getRight(_VALUE);
1381                }
1382                else
1383                {
1384                    node.setRight(newNode, _VALUE);
1385                    newNode.setParent(node, _VALUE);
1386                    doRedBlackInsert(newNode, _VALUE);
1387                    break;
1388                }
1389            }
1390        }
1391    }
1392
1393    /* ********** START implementation of Map ********** */
1394
1395    /**
1396     * Returns the number of key-value mappings in this map. If the
1397     * map contains more than Integer.MAX_VALUE elements, returns
1398     * Integer.MAX_VALUE.
1399     *
1400     * @return the number of key-value mappings in this map.
1401     */
1402
1403    public int size()
1404    {
1405        return _size;
1406    }
1407
1408    /**
1409     * Returns true if this map contains a mapping for the specified
1410     * key.
1411     *
1412     * @param key key whose presence in this map is to be tested.
1413     *
1414     * @return true if this map contains a mapping for the specified
1415     * key.
1416     *
1417     * @exception ClassCastException if the key is of an inappropriate
1418     * type for this map.
1419     * @exception NullPointerException if the key is null
1420     */
1421
1422    public boolean containsKey(final Object key)
1423        throws ClassCastException , NullPointerException
1424    {
1425        checkKey(key);
1426        return lookup(( Comparable ) key, _KEY) != null;
1427    }
1428
1429    /**
1430     * Returns true if this map maps one or more keys to the
1431     * specified value.
1432     *
1433     * @param value value whose presence in this map is to be tested.
1434     *
1435     * @return true if this map maps one or more keys to the specified
1436     * value.
1437     */
1438
1439    public boolean containsValue(final Object value)
1440    {
1441        checkValue(value);
1442        return lookup(( Comparable ) value, _VALUE) != null;
1443    }
1444
1445    /**
1446     * Returns the value to which this map maps the specified
1447     * key. Returns null if the map contains no mapping for this key.
1448     *
1449     * @param key key whose associated value is to be returned.
1450     *
1451     * @return the value to which this map maps the specified key, or
1452     * null if the map contains no mapping for this key.
1453     *
1454     * @exception ClassCastException if the key is of an inappropriate
1455     * type for this map.
1456     * @exception NullPointerException if the key is null
1457     */
1458
1459    public Object get(final Object key)
1460        throws ClassCastException , NullPointerException
1461    {
1462        return doGet(( Comparable ) key, _KEY);
1463    }
1464
1465    /**
1466     * Associates the specified value with the specified key in this
1467     * map.
1468     *
1469     * @param key key with which the specified value is to be
1470     * associated.
1471     * @param value value to be associated with the specified key.
1472     *
1473     * @return null
1474     *
1475     * @exception ClassCastException if the class of the specified key
1476     * or value prevents it from being
1477     * stored in this map.
1478     * @exception NullPointerException if the specified key or value
1479     * is null
1480     * @exception IllegalArgumentException if the key duplicates an
1481     * existing key, or if the
1482     * value duplicates an
1483     * existing value
1484     */
1485
1486    public Object put(final Object key, final Object value)
1487        throws ClassCastException , NullPointerException ,
1488                IllegalArgumentException
1489    {
1490        checkKeyAndValue(key, value);
1491        Node node = _root[ _KEY ];
1492
1493        if (node == null)
1494        {
1495            Node root = new Node(( Comparable ) key, ( Comparable ) value);
1496
1497            _root[ _KEY ] = root;
1498            _root[ _VALUE ] = root;
1499            grow();
1500        }
1501        else
1502        {
1503            while (true)
1504            {
1505                int cmp = compare(( Comparable ) key, node.getData(_KEY));
1506
1507                if (cmp == 0)
1508                {
1509                    throw new IllegalArgumentException (
1510                        "Cannot store a duplicate key (\"" + key
1511                        + "\") in this Map");
1512                }
1513                else if (cmp < 0)
1514                {
1515                    if (node.getLeft(_KEY) != null)
1516                    {
1517                        node = node.getLeft(_KEY);
1518                    }
1519                    else
1520                    {
1521                        Node newNode = new Node(( Comparable ) key,
1522                                                ( Comparable ) value);
1523
1524                        insertValue(newNode);
1525                        node.setLeft(newNode, _KEY);
1526                        newNode.setParent(node, _KEY);
1527                        doRedBlackInsert(newNode, _KEY);
1528                        grow();
1529                        break;
1530                    }
1531                }
1532                else
1533                { // cmp > 0
1534 if (node.getRight(_KEY) != null)
1535                    {
1536                        node = node.getRight(_KEY);
1537                    }
1538                    else
1539                    {
1540                        Node newNode = new Node(( Comparable ) key,
1541                                                ( Comparable ) value);
1542
1543                        insertValue(newNode);
1544                        node.setRight(newNode, _KEY);
1545                        newNode.setParent(node, _KEY);
1546                        doRedBlackInsert(newNode, _KEY);
1547                        grow();
1548                        break;
1549                    }
1550                }
1551            }
1552        }
1553        return null;
1554    }
1555
1556    /**
1557     * Removes the mapping for this key from this map if present
1558     *
1559     * @param key key whose mapping is to be removed from the map.
1560     *
1561     * @return previous value associated with specified key, or null
1562     * if there was no mapping for key.
1563     */
1564
1565    public Object remove(final Object key)
1566    {
1567        return doRemove(( Comparable ) key, _KEY);
1568    }
1569
1570    /**
1571     * Removes all mappings from this map
1572     */
1573
1574    public void clear()
1575    {
1576        modify();
1577        _size = 0;
1578        _root[ _KEY ] = null;
1579        _root[ _VALUE ] = null;
1580    }
1581
1582    /**
1583     * Returns a set view of the keys contained in this map. The set
1584     * is backed by the map, so changes to the map are reflected in
1585     * the set, and vice-versa. If the map is modified while an
1586     * iteration over the set is in progress, the results of the
1587     * iteration are undefined. The set supports element removal,
1588     * which removes the corresponding mapping from the map, via the
1589     * Iterator.remove, Set.remove, removeAll, retainAll, and clear
1590     * operations. It does not support the add or addAll operations.
1591     *
1592     * @return a set view of the keys contained in this map.
1593     */
1594
1595    public Set keySet()
1596    {
1597        if (_key_set[ _KEY ] == null)
1598        {
1599            _key_set[ _KEY ] = new AbstractSet()
1600            {
1601                public Iterator iterator()
1602                {
1603                    return new BinaryTreeIterator(_KEY)
1604                    {
1605                        protected Object doGetNext()
1606                        {
1607                            return _last_returned_node.getData(_KEY);
1608                        }
1609                    };
1610                }
1611
1612                public int size()
1613                {
1614                    return BinaryTree.this.size();
1615                }
1616
1617                public boolean contains(Object o)
1618                {
1619                    return containsKey(o);
1620                }
1621
1622                public boolean remove(Object o)
1623                {
1624                    int old_size = _size;
1625
1626                    BinaryTree.this.remove(o);
1627                    return _size != old_size;
1628                }
1629
1630                public void clear()
1631                {
1632                    BinaryTree.this.clear();
1633                }
1634            };
1635        }
1636        return _key_set[ _KEY ];
1637    }
1638
1639    /**
1640     * Returns a collection view of the values contained in this
1641     * map. The collection is backed by the map, so changes to the map
1642     * are reflected in the collection, and vice-versa. If the map is
1643     * modified while an iteration over the collection is in progress,
1644     * the results of the iteration are undefined. The collection
1645     * supports element removal, which removes the corresponding
1646     * mapping from the map, via the Iterator.remove,
1647     * Collection.remove, removeAll, retainAll and clear operations.
1648     * It does not support the add or addAll operations.
1649     *
1650     * @return a collection view of the values contained in this map.
1651     */
1652
1653    public Collection values()
1654    {
1655        if (_value_collection[ _KEY ] == null)
1656        {
1657            _value_collection[ _KEY ] = new AbstractCollection()
1658            {
1659                public Iterator iterator()
1660                {
1661                    return new BinaryTreeIterator(_KEY)
1662                    {
1663                        protected Object doGetNext()
1664                        {
1665                            return _last_returned_node.getData(_VALUE);
1666                        }
1667                    };
1668                }
1669
1670                public int size()
1671                {
1672                    return BinaryTree.this.size();
1673                }
1674
1675                public boolean contains(Object o)
1676                {
1677                    return containsValue(o);
1678                }
1679
1680                public boolean remove(Object o)
1681                {
1682                    int old_size = _size;
1683
1684                    removeValue(o);
1685                    return _size != old_size;
1686                }
1687
1688                public boolean removeAll(Collection c)
1689                {
1690                    boolean modified = false;
1691                    Iterator iter = c.iterator();
1692
1693                    while (iter.hasNext())
1694                    {
1695                        if (removeValue(iter.next()) != null)
1696                        {
1697                            modified = true;
1698                        }
1699                    }
1700                    return modified;
1701                }
1702
1703                public void clear()
1704                {
1705                    BinaryTree.this.clear();
1706                }
1707            };
1708        }
1709        return _value_collection[ _KEY ];
1710    }
1711
1712    /**
1713     * Returns a set view of the mappings contained in this map. Each
1714     * element in the returned set is a Map.Entry. The set is backed
1715     * by the map, so changes to the map are reflected in the set, and
1716     * vice-versa. If the map is modified while an iteration over the
1717     * set is in progress, the results of the iteration are
1718     * undefined. The set supports element removal, which removes the
1719     * corresponding mapping from the map, via the Iterator.remove,
1720     * Set.remove, removeAll, retainAll and clear operations. It does
1721     * not support the add or addAll operations.
1722     *
1723     * @return a set view of the mappings contained in this map.
1724     */
1725
1726    public Set entrySet()
1727    {
1728        if (_entry_set[ _KEY ] == null)
1729        {
1730            _entry_set[ _KEY ] = new AbstractSet()
1731            {
1732                public Iterator iterator()
1733                {
1734                    return new BinaryTreeIterator(_KEY)
1735                    {
1736                        protected Object doGetNext()
1737                        {
1738                            return _last_returned_node;
1739                        }
1740                    };
1741                }
1742
1743                public boolean contains(Object o)
1744                {
1745                    if (!(o instanceof Map.Entry))
1746                    {
1747                        return false;
1748                    }
1749                    Map.Entry entry = ( Map.Entry ) o;
1750                    Object value = entry.getValue();
1751                    Node node = lookup(( Comparable ) entry.getKey(),
1752                                             _KEY);
1753
1754                    return (node != null)
1755                           && node.getData(_VALUE).equals(value);
1756                }
1757
1758                public boolean remove(Object o)
1759                {
1760                    if (!(o instanceof Map.Entry))
1761                    {
1762                        return false;
1763                    }
1764                    Map.Entry entry = ( Map.Entry ) o;
1765                    Object value = entry.getValue();
1766                    Node node = lookup(( Comparable ) entry.getKey(),
1767                                             _KEY);
1768
1769                    if ((node != null) && node.getData(_VALUE).equals(value))
1770                    {
1771                        doRedBlackDelete(node);
1772                        return true;
1773                    }
1774                    return false;
1775                }
1776
1777                public int size()
1778                {
1779                    return BinaryTree.this.size();
1780                }
1781
1782                public void clear()
1783                {
1784                    BinaryTree.this.clear();
1785                }
1786            };
1787        }
1788        return _entry_set[ _KEY ];
1789    }
1790
1791    /* ********** END implementation of Map ********** */
1792    private abstract class BinaryTreeIterator
1793        implements Iterator
1794    {
1795        private int _expected_modifications;
1796        protected Node _last_returned_node;
1797        private Node _next_node;
1798        private int _type;
1799
1800        /**
1801         * Constructor
1802         *
1803         * @param type
1804         */
1805
1806        BinaryTreeIterator(final int type)
1807        {
1808            _type = type;
1809            _expected_modifications = BinaryTree.this._modifications;
1810            _last_returned_node = null;
1811            _next_node = leastNode(_root[ _type ], _type);
1812        }
1813
1814        /**
1815         * @return 'next', whatever that means for a given kind of
1816         * BinaryTreeIterator
1817         */
1818
1819        protected abstract Object doGetNext();
1820
1821        /* ********** START implementation of Iterator ********** */
1822
1823        /**
1824         * @return true if the iterator has more elements.
1825         */
1826
1827        public final boolean hasNext()
1828        {
1829            return _next_node != null;
1830        }
1831
1832        /**
1833         * @return the next element in the iteration.
1834         *
1835         * @exception NoSuchElementException if iteration has no more
1836         * elements.
1837         * @exception ConcurrentModificationException if the
1838         * BinaryTree is
1839         * modified behind
1840         * the iterator's
1841         * back
1842         */
1843
1844        public final Object next()
1845            throws NoSuchElementException, ConcurrentModificationException
1846        {
1847            if (_next_node == null)
1848            {
1849                throw new NoSuchElementException();
1850            }
1851            if (_modifications != _expected_modifications)
1852            {
1853                throw new ConcurrentModificationException();
1854            }
1855            _last_returned_node = _next_node;
1856            _next_node = nextGreater(_next_node, _type);
1857            return doGetNext();
1858        }
1859
1860        /**
1861         * Removes from the underlying collection the last element
1862         * returned by the iterator. This method can be called only
1863         * once per call to next. The behavior of an iterator is
1864         * unspecified if the underlying collection is modified while
1865         * the iteration is in progress in any way other than by
1866         * calling this method.
1867         *
1868         * @exception IllegalStateException if the next method has not
1869         * yet been called, or the
1870         * remove method has already
1871         * been called after the last
1872         * call to the next method.
1873         * @exception ConcurrentModificationException if the
1874         * BinaryTree is
1875         * modified behind
1876         * the iterator's
1877         * back
1878         */
1879
1880        public final void remove()
1881            throws IllegalStateException , ConcurrentModificationException
1882        {
1883            if (_last_returned_node == null)
1884            {
1885                throw new IllegalStateException ();
1886            }
1887            if (_modifications != _expected_modifications)
1888            {
1889                throw new ConcurrentModificationException();
1890            }
1891            doRedBlackDelete(_last_returned_node);
1892            _expected_modifications++;
1893            _last_returned_node = null;
1894        }
1895
1896        /* ********** END implementation of Iterator ********** */
1897    } // end private abstract class BinaryTreeIterator
1898
1899    // final for performance
1900 private static final class Node
1901        implements Map.Entry
1902    {
1903        private Comparable [] _data;
1904        private Node[] _left;
1905        private Node[] _right;
1906        private Node[] _parent;
1907        private boolean[] _black;
1908        private int _hashcode;
1909        private boolean _calculated_hashcode;
1910
1911        /**
1912         * Make a new cell with given key and value, and with null
1913         * links, and black (true) colors.
1914         *
1915         * @param key
1916         * @param value
1917         */
1918
1919        Node(final Comparable key, final Comparable value)
1920        {
1921            _data = new Comparable []
1922            {
1923                key, value
1924            };
1925            _left = new Node[]
1926            {
1927                null, null
1928            };
1929            _right = new Node[]
1930            {
1931                null, null
1932            };
1933            _parent = new Node[]
1934            {
1935                null, null
1936            };
1937            _black = new boolean[]
1938            {
1939                true, true
1940            };
1941            _calculated_hashcode = false;
1942        }
1943
1944        /**
1945         * get the specified data
1946         *
1947         * @param index _KEY or _VALUE
1948         *
1949         * @return the key or value
1950         */
1951
1952        private Comparable getData(final int index)
1953        {
1954            return _data[ index ];
1955        }
1956
1957        /**
1958         * Set this node's left node
1959         *
1960         * @param node the new left node
1961         * @param index _KEY or _VALUE
1962         */
1963
1964        private void setLeft(final Node node, final int index)
1965        {
1966            _left[ index ] = node;
1967        }
1968
1969        /**
1970         * get the left node
1971         *
1972         * @param index _KEY or _VALUE
1973         *
1974         * @return the left node -- may be null
1975         */
1976
1977        private Node getLeft(final int index)
1978        {
1979            return _left[ index ];
1980        }
1981
1982        /**
1983         * Set this node's right node
1984         *
1985         * @param node the new right node
1986         * @param index _KEY or _VALUE
1987         */
1988
1989        private void setRight(final Node node, final int index)
1990        {
1991            _right[ index ] = node;
1992        }
1993
1994        /**
1995         * get the right node
1996         *
1997         * @param index _KEY or _VALUE
1998         *
1999         * @return the right node -- may be null
2000         */
2001
2002        private Node getRight(final int index)
2003        {
2004            return _right[ index ];
2005        }
2006
2007        /**
2008         * Set this node's parent node
2009         *
2010         * @param node the new parent node
2011         * @param index _KEY or _VALUE
2012         */
2013
2014        private void setParent(final Node node, final int index)
2015        {
2016            _parent[ index ] = node;
2017        }
2018
2019        /**
2020         * get the parent node
2021         *
2022         * @param index _KEY or _VALUE
2023         *
2024         * @return the parent node -- may be null
2025         */
2026
2027        private Node getParent(final int index)
2028        {
2029            return _parent[ index ];
2030        }
2031
2032        /**
2033         * exchange colors with another node
2034         *
2035         * @param node the node to swap with
2036         * @param index _KEY or _VALUE
2037         */
2038
2039        private void swapColors(final Node node, final int index)
2040        {
2041
2042            // Swap colors -- old hacker's trick
2043 _black[ index ] ^= node._black[ index ];
2044            node._black[ index ] ^= _black[ index ];
2045            _black[ index ] ^= node._black[ index ];
2046        }
2047
2048        /**
2049         * is this node black?
2050         *
2051         * @param index _KEY or _VALUE
2052         *
2053         * @return true if black (which is represented as a true boolean)
2054         */
2055
2056        private boolean isBlack(final int index)
2057        {
2058            return _black[ index ];
2059        }
2060
2061        /**
2062         * is this node red?
2063         *
2064         * @param index _KEY or _VALUE
2065         *
2066         * @return true if non-black
2067         */
2068
2069        private boolean isRed(final int index)
2070        {
2071            return !_black[ index ];
2072        }
2073
2074        /**
2075         * make this node black
2076         *
2077         * @param index _KEY or _VALUE
2078         */
2079
2080        private void setBlack(final int index)
2081        {
2082            _black[ index ] = true;
2083        }
2084
2085        /**
2086         * make this node red
2087         *
2088         * @param index _KEY or _VALUE
2089         */
2090
2091        private void setRed(final int index)
2092        {
2093            _black[ index ] = false;
2094        }
2095
2096        /**
2097         * make this node the same color as another
2098         *
2099         * @param node the node whose color we're adopting
2100         * @param index _KEY or _VALUE
2101         */
2102
2103        private void copyColor(final Node node, final int index)
2104        {
2105            _black[ index ] = node._black[ index ];
2106        }
2107
2108        /* ********** START implementation of Map.Entry ********** */
2109
2110        /**
2111         * @return the key corresponding to this entry.
2112         */
2113
2114        public Object getKey()
2115        {
2116            return _data[ _KEY ];
2117        }
2118
2119        /**
2120         * @return the value corresponding to this entry.
2121         */
2122
2123        public Object getValue()
2124        {
2125            return _data[ _VALUE ];
2126        }
2127
2128        /**
2129         * Optional operation that is not permitted in this
2130         * implementation
2131         *
2132         * @param ignored
2133         *
2134         * @return does not return
2135         *
2136         * @exception UnsupportedOperationException
2137         */
2138
2139        public Object setValue(Object ignored)
2140            throws UnsupportedOperationException
2141        {
2142            throw new UnsupportedOperationException (
2143                "Map.Entry.setValue is not supported");
2144        }
2145
2146        /**
2147         * Compares the specified object with this entry for equality.
2148         * Returns true if the given object is also a map entry and
2149         * the two entries represent the same mapping.
2150         *
2151         * @param o object to be compared for equality with this map
2152         * entry.
2153         * @return true if the specified object is equal to this map
2154         * entry.
2155         */
2156
2157        public boolean equals(Object o)
2158        {
2159            if (this == o)
2160            {
2161                return true;
2162            }
2163            if (!(o instanceof Map.Entry))
2164            {
2165                return false;
2166            }
2167            Map.Entry e = ( Map.Entry ) o;
2168
2169            return _data[ _KEY ].equals(e.getKey())
2170                   && _data[ _VALUE ].equals(e.getValue());
2171        }
2172
2173        /**
2174         * @return the hash code value for this map entry.
2175         */
2176
2177        public int hashCode()
2178        {
2179            if (!_calculated_hashcode)
2180            {
2181                _hashcode = _data[ _KEY ].hashCode()
2182                                       ^ _data[ _VALUE ].hashCode();
2183                _calculated_hashcode = true;
2184            }
2185            return _hashcode;
2186        }
2187
2188        /* ********** END implementation of Map.Entry ********** */
2189    }
2190} // end public class BinaryTree
2191
2192

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags