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