RBTreeMap.java
0001 /*
0002  *  RBTreeMap.java
0003  *
0004  *  Copyright (c) 1995-2012, The University of Sheffield. See the file
0005  *  COPYRIGHT.txt in the software or at http://gate.ac.uk/gate/COPYRIGHT.txt
0006  *
0007  *  This file is part of GATE (see http://gate.ac.uk/), and is free
0008  *  software, licenced under the GNU Library General Public License,
0009  *  Version 2, June 1991 (in the distribution as file licence.html,
0010  *  and also available at http://gate.ac.uk/gate/licence.html).
0011  *
0012  *  Valentin Tablan, Jan/2000, modified from Sun sources
0013  *
0014  *  $Id: RBTreeMap.java 17639 2014-03-12 10:48:13Z markagreenwood $
0015  */
0016 
0017 package gate.util;
0018 import java.io.IOException;
0019 import java.util.AbstractCollection;
0020 import java.util.AbstractMap;
0021 import java.util.AbstractSet;
0022 import java.util.Collection;
0023 import java.util.Comparator;
0024 import java.util.ConcurrentModificationException;
0025 import java.util.Map;
0026 import java.util.NoSuchElementException;
0027 import java.util.Set;
0028 import java.util.SortedMap;
0029 import java.util.SortedSet;
0030 
0031 /** Slightly modified implementation of java.util.TreeMap in order to return the
0032   * closest neighbours in the case of a failed search.
0033   */
0034 public class RBTreeMap<K,V> extends AbstractMap<K,V>
0035                implements SortedMap<K,V>, Cloneable, java.io.Serializable
0036 {
0037 
0038   /** Freeze the serialization UID. */
0039   static final long serialVersionUID = -1454324265766936618L;
0040 
0041   /**
0042     * The Comparator used to maintain order in this RBTreeMap, or
0043     * null if this RBTreeMap uses its elements natural ordering.
0044     *
0045     @serial
0046     */
0047   private Comparator<? super K> comparator = null;
0048 
0049    private transient Entry<K,V> root = null;
0050 
0051   /**
0052     * The number of entries in the tree
0053     */
0054   private transient int size = 0;
0055 
0056   /**
0057     * The number of structural modifications to the tree.
0058     */
0059   private transient int modCount = 0;
0060 
0061   private void incrementSize()   { modCount++; size++; }
0062   private void decrementSize()   { modCount++; size--; }
0063 
0064   /**
0065     * Constructs a new, empty map, sorted according to the keys' natural
0066     * order.  All keys inserted into the map must implement the
0067     <tt>Comparable</tt> interface.  Furthermore, all such keys must be
0068     <i>mutually comparable</i><tt>k1.compareTo(k2)</tt> must not throw a
0069     * ClassCastException for any elements <tt>k1</tt> and <tt>k2</tt> in the
0070     * map.  If the user attempts to put a key into the map that violates this
0071     * constraint (for example, the user attempts to put a string key into a
0072     * map whose keys are integers), the <tt>put(Object key, Object
0073     * value)</tt> call will throw a <tt>ClassCastException</tt>.
0074     *
0075     @see Comparable
0076     */
0077   public RBTreeMap() {
0078   }
0079 
0080   /**
0081     * Constructs a new, empty map, sorted according to the given comparator.
0082     * All keys inserted into the map must be <i>mutually comparable</i> by
0083     * the given comparator: <tt>comparator.compare(k1, k2)</tt> must not
0084     * throw a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
0085     <tt>k2</tt> in the map.  If the user attempts to put a key into the
0086     * map that violates this constraint, the <tt>put(Object key, Object
0087     * value)</tt> call will throw a <tt>ClassCastException</tt>.
0088     */
0089   public RBTreeMap(Comparator<? super K> c) {
0090     this.comparator = c;
0091   }
0092 
0093   /**
0094     * Constructs a new map containing the same mappings as the given map,
0095     * sorted according to the keys' <i>natural order</i>.  All keys inserted
0096     * into the new map must implement the <tt>Comparable</tt> interface.
0097     * Furthermore, all such keys must be <i>mutually comparable</i>:
0098     <tt>k1.compareTo(k2)</tt> must not throw a <tt>ClassCastException</tt>
0099     * for any elements <tt>k1</tt> and <tt>k2</tt> in the map.  This method
0100     * runs in n*log(n) time.
0101     *
0102     @throws    ClassCastException the keys in t are not Comparable, or
0103     * are not mutually comparable.
0104     */
0105   public RBTreeMap(Map<? extends K, ? extends V> m) {
0106     putAll(m);
0107   }
0108 
0109   /**
0110     * Constructs a new map containing the same mappings as the given
0111     <tt>SortedMap</tt>, sorted according to the same ordering.  This method
0112     * runs in linear time.
0113     */
0114   public RBTreeMap(SortedMap<K, ? extends V> m) {
0115       comparator = m.comparator();
0116       try {
0117           buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
0118       catch (java.io.IOException cannotHappen) {
0119       catch (ClassNotFoundException cannotHappen) {
0120       }
0121   }
0122 
0123 
0124   // Query Operations
0125 
0126   /**
0127     * Returns the number of key-value mappings in this map.
0128     *
0129     @return the number of key-value mappings in this map.
0130     */
0131   @Override
0132   public int size() {
0133     return size;
0134   }
0135 
0136   /**
0137     * Returns <tt>true</tt> if this map contains a mapping for the specified
0138     * key.
0139     *
0140     @param key key whose presence in this map is to be tested.
0141     *
0142     @return <tt>true</tt> if this map contains a mapping for the
0143     *            specified key.
0144     @throws ClassCastException if the key cannot be compared with the keys
0145     *      currently in the map.
0146     @throws NullPointerException key is <tt>null</tt> and this map uses
0147     *      natural ordering, or its comparator does not tolerate
0148     *            <tt>null</tt> keys.
0149     */
0150   @Override
0151   public boolean containsKey(Object key) {
0152     return getEntry(key!= null;
0153   }
0154 
0155   /**
0156     * Returns <tt>true</tt> if this map maps one or more keys to the
0157     * specified value.  More formally, returns <tt>true</tt> if and only if
0158     * this map contains at least one mapping to a value <tt>v</tt> such
0159     * that <tt>(value==null ? v==null : value.equals(v))</tt>.  This
0160     * operation will probably require time linear in the Map size for most
0161     * implementations of Map.
0162     *
0163     @param value value whose presence in this Map is to be tested.
0164     @since JDK1.2
0165     */
0166   @Override
0167   public boolean containsValue(Object value) {
0168       return (value==null ? valueSearchNull(root)
0169               : valueSearchNonNull(root, value));
0170   }
0171 
0172   private boolean valueSearchNull(Entry<K,V> n) {
0173       if (n.value == null)
0174           return true;
0175 
0176       // Check left and right subtrees for value
0177       return (n.left  != null && valueSearchNull(n.left)) ||
0178              (n.right != null && valueSearchNull(n.right));
0179   }
0180 
0181   private boolean valueSearchNonNull(Entry<K,V> n, Object value) {
0182       // Check this node for the value
0183       if (value.equals(n.value))
0184           return true;
0185 
0186       // Check left and right subtrees for value
0187       return (n.left  != null && valueSearchNonNull(n.left, value)) ||
0188              (n.right != null && valueSearchNonNull(n.right, value));
0189   }
0190 
0191   /**
0192     * Returns a pair of values: (glb,lub).
0193     * If the given key is found in the map then glb=lub=the value associated
0194     * with the given key.
0195     * If the key is not in the map:
0196     * glb=the value associated with the greatest key in the map that is lower
0197     * than the given key; or null if the given key is smaller than any key in
0198     * the map.
0199     * lub=the value associated with the smaller key in the map that is greater
0200     * than the given key; or null the given key is greater than any key in the
0201     * map.
0202     * If the map is empty it returns (null,null).
0203     */
0204   @SuppressWarnings("unchecked")
0205   public V[] getClosestMatch(K key){
0206     if (root==null)return (V[])(new Object[]{null,null});
0207 
0208     Entry<K,V> lub=getCeilEntry(key);
0209 
0210     if(lub==null){//greatest key in set is still smaller then parameter "key"
0211       return (V[])new Object[]{lastEntry().value,null};
0212     };
0213 
0214     int cmp=compare(key,lub.key);
0215 
0216     if (cmp==0){return (V[])(new Object[]{lub.value,lub.value});}
0217     else {
0218       Entry<K,V> prec=getPrecedingEntry(lub.key);
0219       if (prec == nullreturn (V[])(new Object[]{null,lub.value});
0220       else return (V[])(new Object[]{prec.value,lub.value});
0221     }
0222   }
0223 
0224   /** Returns the value associated to the next key in the map if an exact match
0225     * doesn't exist. If there is an exact match, the method will return the
0226     * value associated to the given key.
0227     @param key the key for wich the look-up will be done.
0228     @return the value associated to the given key or the next available
0229     * value
0230     */
0231   public V getNextOf(K key){
0232     if (root==nullreturn null;
0233     Entry<K,V> lub=getCeilEntry(key);
0234     if (lub == nullreturn null;
0235     return lub.value;
0236   }
0237 
0238   /**
0239     * Returns the value to which this map maps the specified key.  Returns
0240     <tt>null</tt> if the map contains no mapping for this key.  A return
0241     * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
0242     * map contains no mapping for the key; it's also possible that the map
0243     * explicitly maps the key to <tt>null</tt>.  The <tt>containsKey</tt>
0244     * operation may be used to distinguish these two cases.
0245     *
0246     @param key key whose associated value is to be returned.
0247     @return the value to which this map maps the specified key, or
0248     *         <tt>null</tt> if the map contains no mapping for the key.
0249     @throws    ClassCastException key cannot be compared with the keys
0250     *      currently in the map.
0251     @throws NullPointerException key is <tt>null</tt> and this map uses
0252     *      natural ordering, or its comparator does not tolerate
0253     *      <tt>null</tt> keys.
0254     *
0255     @see #containsKey(Object)
0256     */
0257   @Override
0258   public V get(Object key) {
0259     Entry<K,V> p = getEntry(key);
0260     return p==null null : p.value;
0261   }
0262 
0263   /**
0264     * Returns the comparator used to order this map, or <tt>null</tt> if this
0265     * map uses its keys' natural order.
0266     *
0267     @return the comparator associated with this sorted map, or
0268     *          <tt>null</tt> if it uses its keys' natural sort method.
0269     */
0270   @Override
0271   public Comparator<? super K> comparator() {
0272       return comparator;
0273   }
0274 
0275   /**
0276     * Returns the first (lowest) key currently in this sorted map.
0277     *
0278     @return the first (lowest) key currently in this sorted map.
0279     @throws    NoSuchElementException Map is empty.
0280     */
0281   @Override
0282   public K firstKey() {
0283       return key(firstEntry());
0284   }
0285 
0286   /**
0287     * Returns the last (highest) key currently in this sorted map.
0288     *
0289     @return the last (highest) key currently in this sorted map.
0290     @throws    NoSuchElementException Map is empty.
0291     */
0292   @Override
0293   public K lastKey() {
0294       return key(lastEntry());
0295   }
0296 
0297   /**
0298     * Copies all of the mappings from the specified map to this map.  These
0299     * mappings replace any mappings that this map had for any of the keys
0300     * currently in the specified map.
0301     *
0302     @param map Mappings to be stored in this map.
0303     @throws    ClassCastException class of a key or value in the specified
0304     *             map prevents it from being stored in this map.
0305     *
0306     @throws NullPointerException this map does not permit <tt>null</tt>
0307     *            keys and a specified key is <tt>null</tt>.
0308     */
0309   @Override
0310   public void putAll(Map<? extends K, ? extends V> map) {
0311       int mapSize = map.size();
0312       if (size==&& mapSize!=&& map instanceof SortedMap) {
0313           @SuppressWarnings("unchecked")
0314           Comparator<? super K> c = ((SortedMap<K,V>)map).comparator();
0315           if (c == comparator || (c != null && c.equals(comparator))) {
0316             ++modCount;
0317             try {
0318                 buildFromSorted(mapSize, map.entrySet().iterator(),
0319                                 null, null);
0320             catch (java.io.IOException cannotHappen) {
0321             catch (ClassNotFoundException cannotHappen) {
0322             }
0323             return;
0324           }
0325       }
0326       super.putAll(map);
0327   }
0328 
0329   /**
0330     * Returns this map's entry for the given key, or <tt>null</tt> if the map
0331     * does not contain an entry for the key.
0332     *
0333     @return this map's entry for the given key, or <tt>null</tt> if the map
0334     *          does not contain an entry for the key.
0335     @throws ClassCastException if the key cannot be compared with the keys
0336     *      currently in the map.
0337     @throws NullPointerException key is <tt>null</tt> and this map uses
0338     *      natural order, or its comparator does not tolerate *
0339     *      <tt>null</tt> keys.
0340     */
0341   private Entry<K,V> getEntry(Object key) {
0342     Entry<K,V> p = root;
0343     while (p != null) {
0344         int cmp = compare(key,p.key);
0345         if (cmp == 0)
0346       return p;
0347         else if (cmp < 0)
0348       p = p.left;
0349         else
0350       p = p.right;
0351     }
0352     return null;
0353   }
0354 
0355 
0356   /**
0357     * Gets the entry corresponding to the specified key; if no such entry
0358     * exists, returns the entry for the least key greater than the specified
0359     * key; if no such entry exists (i.e., the greatest key in the Tree is less
0360     * than the specified key), returns <tt>null</tt>.
0361     */
0362   private Entry<K,V> getCeilEntry(Object key) {
0363     Entry<K,V> p = root;
0364     if (p==null)
0365         return null;
0366 
0367     while (true) {
0368         int cmp = compare(key, p.key);
0369         if (cmp == 0) {
0370       return p;
0371         else if (cmp < 0) {
0372       if (p.left != null)
0373           p = p.left;
0374       else
0375           return p;
0376         else {
0377       if (p.right != null) {
0378           p = p.right;
0379       else {
0380           Entry<K,V> parent = p.parent;
0381           Entry<K,V> ch = p;
0382           while (parent != null && ch == parent.right) {
0383         ch = parent;
0384         parent = parent.parent;
0385           }
0386           return parent;
0387       }
0388         }
0389     }
0390   }
0391 
0392   /**
0393     * Returns the entry for the greatest key less than the specified key; if
0394     * no such entry exists (i.e., the least key in the Tree is greater than
0395     * the specified key), returns <tt>null</tt>.
0396     */
0397   private Entry<K,V> getPrecedingEntry(Object key) {
0398     Entry<K,V> p = root;
0399     if (p==null)return null;
0400 
0401     while (true) {
0402       int cmp = compare(key, p.key);
0403       if (cmp > 0) {
0404         if (p.right != nullp = p.right;
0405         else return p;
0406         }else{
0407           if (p.left != null) {
0408             p = p.left;
0409           else {
0410             Entry<K,V> parent = p.parent;
0411             Entry<K,V> ch = p;
0412             while (parent != null && ch == parent.left) {
0413               ch = parent;
0414               parent = parent.parent;
0415             }
0416             return parent;
0417           }
0418         }
0419     }//while true
0420   }
0421 
0422   /**
0423     * Returns the key corresonding to the specified Entry.  Throw
0424     * NoSuchElementException if the Entry is <tt>null</tt>.
0425     */
0426   private static <X,Y> X key(Entry<X,Y> e) {
0427       if (e==null)
0428           throw new NoSuchElementException();
0429       return e.key;
0430   }
0431 
0432   /**
0433     * Associates the specified value with the specified key in this map.
0434     * If the map previously contained a mapping for this key, the old
0435     * value is replaced.
0436     *
0437     @param key key with which the specified value is to be associated.
0438     @param value value to be associated with the specified key.
0439     *
0440     @return previous value associated with specified key, or <tt>null</tt>
0441     *         if there was no mapping for key.  A <tt>null</tt> return can
0442     *         also indicate that the map previously associated <tt>null</tt>
0443     *         with the specified key.
0444     @throws    ClassCastException key cannot be compared with the keys
0445     *      currently in the map.
0446     @throws NullPointerException key is <tt>null</tt> and this map uses
0447     *      natural order, or its comparator does not tolerate
0448     *      <tt>null</tt> keys.
0449     */
0450   @Override
0451   public V put(K key, V value) {
0452     Entry<K,V> t = root;
0453 
0454     if (t == null) {
0455         incrementSize();
0456         root = new Entry<K,V>(key, value, null);
0457         return null;
0458     }
0459 
0460     while (true) {
0461         int cmp = compare(key, t.key);
0462         if (cmp == 0) {
0463       return t.setValue(value);
0464         else if (cmp < 0) {
0465       if (t.left != null) {
0466           t = t.left;
0467       else {
0468           incrementSize();
0469           t.left = new Entry<K,V>(key, value, t);
0470           fixAfterInsertion(t.left);
0471           return null;
0472       }
0473         else // cmp > 0
0474       if (t.right != null) {
0475           t = t.right;
0476       else {
0477           incrementSize();
0478           t.right = new Entry<K,V>(key, value, t);
0479           fixAfterInsertion(t.right);
0480           return null;
0481       }
0482         }
0483     }
0484   }
0485 
0486   /**
0487     * Removes the mapping for this key from this RBTreeMap if present.
0488     *
0489     @return previous value associated with specified key, or <tt>null</tt>
0490     *         if there was no mapping for key.  A <tt>null</tt> return can
0491     *         also indicate that the map previously associated
0492     *         <tt>null</tt> with the specified key.
0493     *
0494     @throws    ClassCastException key cannot be compared with the keys
0495     *      currently in the map.
0496     @throws NullPointerException key is <tt>null</tt> and this map uses
0497     *      natural order, or its comparator does not tolerate
0498     *      <tt>null</tt> keys.
0499     */
0500   @Override
0501   public V remove(Object key) {
0502     Entry<K,V> p = getEntry(key);
0503     if (p == null)
0504         return null;
0505 
0506     V oldValue = p.value;
0507     deleteEntry(p);
0508     return oldValue;
0509   }
0510 
0511   /**
0512     * Removes all mappings from this RBTreeMap.
0513     */
0514   @Override
0515   public void clear() {
0516     modCount++;
0517     size = 0;
0518     root = null;
0519   }
0520 
0521   /**
0522     * Returns a shallow copy of this <tt>RBTreeMap</tt> instance. (The keys and
0523     * values themselves are not cloned.)
0524     *
0525     @return a shallow copy of this Map.
0526     */
0527   @Override
0528   public Object clone() {
0529     return new RBTreeMap<K,V>(this);
0530   }
0531 
0532 
0533   // Views
0534 
0535   /**
0536     * These fields are initialized to contain an instance of the appropriate
0537     * view the first time this view is requested.  The views are stateless,
0538     * so there's no reason to create more than one of each.
0539     */
0540   private transient Set<K>    keySet = null;
0541   private transient Set<Map.Entry<K,V>>    entrySet = null;
0542   private transient Collection<V>  values = null;
0543 
0544   /**
0545     * Returns a Set view of the keys contained in this map.  The set's
0546     * iterator will return the keys in ascending order.  The map is backed by
0547     * this <tt>RBTreeMap</tt> instance, so changes to this map are reflected in
0548     * the Set, and vice-versa.  The Set supports element removal, which
0549     * removes the corresponding mapping from the map, via the
0550     <tt>Iterator.remove</tt><tt>Set.remove</tt><tt>removeAll</tt>,
0551     <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not support
0552     * the <tt>add</tt> or <tt>addAll</tt> operations.
0553     *
0554     @return a set view of the keys contained in this RBTreeMap.
0555     */
0556   @Override
0557   public Set<K> keySet() {
0558     if (keySet == null) {
0559       keySet = new AbstractSet<K>() {
0560 
0561         @Override
0562         public java.util.Iterator<K> iterator() {
0563             return new Iterator<K>(KEYS);
0564         }
0565 
0566         @Override
0567         public int size() {
0568           return RBTreeMap.this.size();
0569         }
0570 
0571         @Override
0572         public boolean contains(Object o) {
0573           return containsKey(o);
0574         }
0575 
0576         @Override
0577         public boolean remove(Object o) {
0578           return RBTreeMap.this.remove(o!= null;
0579         }
0580 
0581         @Override
0582         public void clear() {
0583           RBTreeMap.this.clear();
0584         }
0585       };
0586     }
0587     return keySet;
0588   }
0589 
0590   /**
0591     * Returns a collection view of the values contained in this map.  The
0592     * collection's iterator will return the values in the order that their
0593     * corresponding keys appear in the tree.  The collection is backed by
0594     * this <tt>RBTreeMap</tt> instance, so changes to this map are reflected in
0595     * the collection, and vice-versa.  The collection supports element
0596     * removal, which removes the corresponding mapping from the map through
0597     * the <tt>Iterator.remove</tt><tt>Collection.remove</tt>,
0598     <tt>removeAll</tt><tt>retainAll</tt>, and <tt>clear</tt> operations.
0599     * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
0600     *
0601     @return a collection view of the values contained in this map.
0602     */
0603   @Override
0604   public Collection<V> values() {
0605     if (values == null) {
0606       values = new AbstractCollection<V>() {
0607         @Override
0608         public java.util.Iterator<V> iterator() {
0609             return new Iterator<V>(VALUES);
0610         }
0611 
0612         @Override
0613         public int size() {
0614             return RBTreeMap.this.size();
0615         }
0616 
0617         @Override
0618         public boolean contains(Object o) {
0619             for (Entry<K,V> e = firstEntry(); e != null; e = successor(e))
0620                 if (valEquals(e.getValue(), o))
0621                     return true;
0622             return false;
0623         }
0624 
0625         @Override
0626         public boolean remove(Object o) {
0627           for (Entry<K,V> e = firstEntry(); e != null; e = successor(e)) {
0628             if (valEquals(e.getValue(), o)) {
0629                 deleteEntry(e);
0630                 return true;
0631             }
0632           }
0633           return false;
0634         }
0635 
0636         @Override
0637         public void clear() {
0638             RBTreeMap.this.clear();
0639         }
0640       };
0641     }
0642     return values;
0643   }
0644 
0645   /**
0646     * Returns a set view of the mappings contained in this map.  The set's
0647     * iterator returns the mappings in ascending key order.  Each element in
0648     * the returned set is a <tt>Map.Entry</tt>.  The set is backed by this
0649     * map, so changes to this map are reflected in the set, and vice-versa.
0650     * The set supports element removal, which removes the corresponding
0651     * mapping from the RBTreeMap, through the <tt>Iterator.remove</tt>,
0652     <tt>Set.remove</tt><tt>removeAll</tt><tt>retainAll</tt> and
0653     <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
0654     <tt>addAll</tt> operations.
0655     *
0656     @return a set view of the mappings contained in this map.
0657     */
0658   @Override
0659   public Set<Map.Entry<K,V>> entrySet() {
0660     if (entrySet == null) {
0661       entrySet = new AbstractSet<Map.Entry<K,V>>() {
0662         @Override
0663         public java.util.Iterator<Map.Entry<K,V>> iterator() {
0664           return new Iterator<Map.Entry<K,V>>(ENTRIES);
0665         }
0666 
0667         @Override
0668         public boolean contains(Object o) {
0669           if (!(instanceof Map.Entry))
0670               return false;
0671           @SuppressWarnings("unchecked")
0672           Map.Entry<K,V> entry = (Map.Entry<K,V>)o;
0673           Object value = entry.getValue();
0674           Entry<K,V> p = getEntry(entry.getKey());
0675           return p != null && valEquals(p.getValue(), value);
0676         }
0677 
0678         @Override
0679         public boolean remove(Object o) {
0680           if (!(instanceof Map.Entry))
0681               return false;
0682           @SuppressWarnings("unchecked")
0683           Map.Entry<K,V> entry = (Map.Entry<K,V>)o;
0684           Object value = entry.getValue();
0685           Entry<K,V> p = getEntry(entry.getKey());
0686           if (p != null && valEquals(p.getValue(), value)) {
0687               deleteEntry(p);
0688               return true;
0689           }
0690           return false;
0691         }
0692 
0693         @Override
0694         public int size() {
0695             return RBTreeMap.this.size();
0696         }
0697 
0698         @Override
0699         public void clear() {
0700             RBTreeMap.this.clear();
0701         }
0702       };
0703     }
0704     return entrySet;
0705   }
0706 
0707   /**
0708     * Returns a view of the portion of this map whose keys range from
0709     <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If
0710     <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
0711     * is empty.)  The returned sorted map is backed by this map, so changes
0712     * in the returned sorted map are reflected in this map, and vice-versa.
0713     * The returned sorted map supports all optional map operations.<p>
0714     *
0715     * The sorted map returned by this method will throw an
0716     <tt>IllegalArgumentException</tt> if the user attempts to insert a key
0717     * less than <tt>fromKey</tt> or greater than or equal to
0718     <tt>toKey</tt>.<p>
0719     *
0720     * Note: this method always returns a <i>half-open range</i> (which
0721     * includes its low endpoint but not its high endpoint).  If you need a
0722     <i>closed range</i> (which includes both endpoints), and the key type
0723     * allows for calculation of the successor a given key, merely request the
0724     * subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
0725     * For example, suppose that <tt>m</tt> is a sorted map whose keys are
0726     * strings.  The following idiom obtains a view containing all of the
0727     * key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
0728     * and <tt>high</tt>, inclusive:
0729     *       <pre>    SortedMap sub = m.submap(low, high+"\0");</pre>
0730     * A similar technique can be used to generate an <i>open range</i> (which
0731     * contains neither endpoint).  The following idiom obtains a view
0732     * containing all of the key-value mappings in <tt>m</tt> whose keys are
0733     * between <tt>low</tt> and <tt>high</tt>, exclusive:
0734     *       <pre>    SortedMap sub = m.subMap(low+"\0", high);</pre>
0735     *
0736     @param fromKey low endpoint (inclusive) of the subMap.
0737     @param toKey high endpoint (exclusive) of the subMap.
0738     *
0739     @return a view of the portion of this map whose keys range from
0740     *          <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
0741     *
0742     @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
0743     *      <tt>null</tt> and this map uses natural order, or its
0744     *      comparator does not tolerate <tt>null</tt> keys.
0745     *
0746     @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
0747     *            <tt>toKey</tt>.
0748     */
0749   @Override
0750   public SortedMap<K,V> subMap(Object fromKey, Object toKey) {
0751     return new SubMap(fromKey, toKey);
0752   }
0753 
0754   /**
0755     * Returns a view of the portion of this map whose keys are strictly less
0756     * than <tt>toKey</tt>.  The returned sorted map is backed by this map, so
0757     * changes in the returned sorted map are reflected in this map, and
0758     * vice-versa.  The returned sorted map supports all optional map
0759     * operations.<p>
0760     *
0761     * The sorted map returned by this method will throw an
0762     <tt>IllegalArgumentException</tt> if the user attempts to insert a key
0763     * greater than or equal to <tt>toKey</tt>.<p>
0764     *
0765     * Note: this method always returns a view that does not contain its
0766     * (high) endpoint.  If you need a view that does contain this endpoint,
0767     * and the key type allows for calculation of the successor a given key,
0768     * merely request a headMap bounded by <tt>successor(highEndpoint)</tt>.
0769     * For example, suppose that suppose that <tt>m</tt> is a sorted map whose
0770     * keys are strings.  The following idiom obtains a view containing all of
0771     * the key-value mappings in <tt>m</tt> whose keys are less than or equal
0772     * to <tt>high</tt>:
0773     <pre>
0774     *     SortedMap head = m.headMap(high+"\0");
0775     </pre>
0776     *
0777     @param toKey high endpoint (exclusive) of the headMap.
0778     @return a view of the portion of this map whose keys are strictly
0779     *          less than <tt>toKey</tt>.
0780     @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
0781     *      this map uses natural order, or its comparator does * not
0782     *      tolerate <tt>null</tt> keys.
0783     */
0784   @Override
0785   public SortedMap<K,V> headMap(K toKey) {
0786     return new SubMap(toKey, true);
0787   }
0788 
0789   /**
0790     * Returns a view of the portion of this map whose keys are greater than
0791     * or equal to <tt>fromKey</tt>.  The returned sorted map is backed by
0792     * this map, so changes in the returned sorted map are reflected in this
0793     * map, and vice-versa.  The returned sorted map supports all optional map
0794     * operations.<p>
0795     *
0796     * The sorted map returned by this method will throw an
0797     <tt>IllegalArgumentException</tt> if the user attempts to insert a key
0798     * less than <tt>fromKey</tt>.<p>
0799     *
0800     * Note: this method always returns a view that contains its (low)
0801     * endpoint.  If you need a view that does not contain this endpoint, and
0802     * the element type allows for calculation of the successor a given value,
0803     * merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
0804     * For For example, suppose that suppose that <tt>m</tt> is a sorted map
0805     * whose keys are strings.  The following idiom obtains a view containing
0806     * all of the key-value mappings in <tt>m</tt> whose keys are strictly
0807     * greater than <tt>low</tt><pre>
0808     *     SortedMap tail = m.tailMap(low+"\0");
0809     </pre>
0810     *
0811     @param fromKey low endpoint (inclusive) of the tailMap.
0812     @return a view of the portion of this map whose keys are greater
0813     *          than or equal to <tt>fromKey</tt>.
0814     @throws    NullPointerException fromKey is <tt>null</tt> and this
0815     *      map uses natural ordering, or its comparator does
0816     *            not tolerate <tt>null</tt> keys.
0817     */
0818   @Override
0819   public SortedMap<K,V> tailMap(K fromKey) {
0820     return new SubMap(fromKey, false);
0821   }
0822 
0823   private class SubMap extends AbstractMap<K,V>
0824          implements SortedMap<K,V>, java.io.Serializable {
0825 
0826     // fromKey is significant only if fromStart is false.  Similarly,
0827     // toKey is significant only if toStart is false.
0828     private boolean fromStart = false, toEnd = false;
0829     private Object  fromKey,           toKey;
0830 
0831     SubMap(Object fromKey, Object toKey) {
0832       if (compare(fromKey, toKey0)
0833         throw new IllegalArgumentException("fromKey > toKey");
0834       this.fromKey = fromKey;
0835       this.toKey = toKey;
0836     }
0837 
0838     SubMap(Object key, boolean headMap) {
0839       if (headMap) {
0840           fromStart = true;
0841           toKey = key;
0842       else {
0843           toEnd = true;
0844           fromKey = key;
0845       }
0846     }
0847 
0848     SubMap(boolean fromStart, Object fromKey, boolean toEnd, Object toKey){
0849       this.fromStart = fromStart;
0850       this.fromKey= fromKey;
0851       this.toEnd = toEnd;
0852       this.toKey = toKey;
0853     }
0854 
0855     @Override
0856     public boolean isEmpty() {
0857       return entrySet.isEmpty();
0858     }
0859 
0860     @Override
0861     public boolean containsKey(Object key) {
0862       return inRange(key&& RBTreeMap.this.containsKey(key);
0863     }
0864 
0865     @Override
0866     public V get(Object key) {
0867       if (!inRange(key))
0868         return null;
0869       return RBTreeMap.this.get(key);
0870     }
0871 
0872     @Override
0873     public V put(K key, V value) {
0874       if (!inRange(key))
0875         throw new IllegalArgumentException("key out of range");
0876       return RBTreeMap.this.put(key, value);
0877     }
0878 
0879     @Override
0880     public Comparator<? super K> comparator() {
0881         return comparator;
0882     }
0883 
0884     @Override
0885     public K firstKey() {
0886         return key(fromStart ? firstEntry() : getCeilEntry(fromKey));
0887     }
0888 
0889     @Override
0890     public K lastKey() {
0891         return key(toEnd ? lastEntry() : getPrecedingEntry(toKey));
0892     }
0893 
0894     private transient Set<Map.Entry<K, V>> entrySet = new EntrySetView();
0895 
0896     @Override
0897     public Set<Map.Entry<K, V>> entrySet() {
0898         return entrySet;
0899     }
0900 
0901     private class EntrySetView extends AbstractSet<Map.Entry<K, V>> {
0902       private transient int size = -1, sizeModCount;
0903 
0904       @Override
0905       public int size() {
0906         if (size == -|| sizeModCount != RBTreeMap.this.modCount) {
0907           size = 0;  sizeModCount = RBTreeMap.this.modCount;
0908           java.util.Iterator<Map.Entry<K,V>> i = iterator();
0909           while (i.hasNext()) {
0910             size++;
0911             i.next();
0912           }
0913         }
0914         return size;
0915       // size
0916 
0917       @Override
0918       public boolean isEmpty() {
0919         return !iterator().hasNext();
0920       }// isEmpty
0921 
0922       @Override
0923       public boolean contains(Object o) {
0924         if (!(instanceof Map.Entry))
0925           return false;
0926 
0927         @SuppressWarnings("unchecked")
0928         Map.Entry<K,V> entry = (Map.Entry<K,V>)o;
0929         Object key = entry.getKey();
0930         if (!inRange(key))
0931           return false;
0932         RBTreeMap.Entry<K,V> node = getEntry(key);
0933         return node != null &&
0934                  valEquals(node.getValue(), entry.getValue());
0935       // contains
0936 
0937       @Override
0938       public boolean remove(Object o) {
0939         if (!(instanceof Map.Entry))
0940           return false;
0941         
0942         @SuppressWarnings("unchecked")
0943         Map.Entry<K,V> entry = (Map.Entry<K,V>)o;
0944         Object key = entry.getKey();
0945         if (!inRange(key))
0946           return false;
0947         RBTreeMap.Entry<K,V> node = getEntry(key);
0948         if (node!=null && valEquals(node.getValue(),entry.getValue())){
0949           deleteEntry(node);
0950           return true;
0951         }
0952         return false;
0953       }
0954 
0955       @Override
0956       public java.util.Iterator<Map.Entry<K,V>> iterator() {
0957         return new Iterator<Map.Entry<K,V>>(
0958                   (fromStart ? firstEntry() : getCeilEntry(fromKey)),
0959                   (toEnd     ? null        : getCeilEntry(toKey)));
0960       }
0961     // EntrySetView
0962 
0963     @Override
0964     public SortedMap<K,V> subMap(Object fromKey, Object toKey) {
0965       if (!inRange(fromKey))
0966         throw new IllegalArgumentException("fromKey out of range");
0967       if (!inRange2(toKey))
0968         throw new IllegalArgumentException("toKey out of range");
0969       return new SubMap(fromKey, toKey);
0970     }
0971 
0972     @Override
0973     public SortedMap<K,V> headMap(Object toKey) {
0974       if (!inRange2(toKey))
0975         throw new IllegalArgumentException("toKey out of range");
0976       return new SubMap(fromStart, fromKey, false, toKey);
0977     }
0978 
0979     @Override
0980     public SortedMap<K,V> tailMap(Object fromKey) {
0981       if (!inRange(fromKey))
0982         throw new IllegalArgumentException("fromKey out of range");
0983       return new SubMap(false, fromKey, toEnd, toKey);
0984     }
0985 
0986     private boolean inRange(Object key) {
0987       return (fromStart || compare(key, fromKey>= 0&&
0988                      (toEnd     || compare(key, toKey)   <  0);
0989     }
0990 
0991     // This form allows the high endpoint (as well as all legit keys)
0992     private boolean inRange2(Object key) {
0993       return (fromStart || compare(key, fromKey>= 0&&
0994                  (toEnd     || compare(key, toKey)   <= 0);
0995     }
0996     static final long serialVersionUID = 4333473260468321526L;
0997   // SubMap
0998 
0999   // Types of Iterators
1000   private static final int KEYS = 0;
1001 
1002   private static final int VALUES = 1;
1003 
1004   private static final int ENTRIES = 2;
1005 
1006   /**
1007     * RBTreeMap Iterator.
1008     */
1009   private class Iterator<E> implements java.util.Iterator<E> {
1010     private int type;
1011 
1012     private int expectedModCount = RBTreeMap.this.modCount;
1013 
1014     private Entry<K,V> lastReturned = null;
1015 
1016     private Entry<K,V> next;
1017 
1018     private Entry<K,V> firstExcluded = null;
1019 
1020     Iterator(int type) {
1021       this.type = type;
1022       next = firstEntry();
1023     }
1024 
1025     Iterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1026       type = ENTRIES;
1027       next = first;
1028       this.firstExcluded = firstExcluded;
1029     }
1030 
1031     @Override
1032     public boolean hasNext() {
1033       return next != firstExcluded;
1034     //hasNext
1035 
1036     @SuppressWarnings("unchecked")
1037     @Override
1038     public E next() {
1039       if (next == firstExcluded)
1040         throw new NoSuchElementException();
1041 
1042       if (modCount != expectedModCount)
1043         throw new ConcurrentModificationException();
1044 
1045       lastReturned = next;
1046       next = successor(next);
1047       return (E)(type == KEYS ? lastReturned.key :
1048         (type == VALUES ? lastReturned.value : lastReturned));
1049     // next
1050 
1051     @Override
1052     public void remove() {
1053       if (lastReturned == null)
1054         throw new IllegalStateException();
1055 
1056       if (modCount != expectedModCount)
1057         throw new ConcurrentModificationException();
1058 
1059       deleteEntry(lastReturned);
1060       expectedModCount++;
1061       lastReturned = null;
1062     // remove
1063   //Iterator
1064 
1065   /**
1066     * Compares two keys using the correct comparison method for this RBTreeMap.
1067     */
1068   @SuppressWarnings({"unchecked""rawtypes"})
1069   private int compare(Object k1, Object k2) {
1070     return (comparator==null ((Comparable)k1).compareTo(k2)
1071        : comparator.compare((K)k1, (K)k2));
1072   }
1073 
1074   /**
1075     * Test two values  for equality.  Differs from o1.equals(o2) only in
1076     * that it copes with with <tt>null</tt> o1 properly.
1077     */
1078   private static boolean valEquals(Object o1, Object o2) {
1079     return (o1==null ? o2==null : o1.equals(o2));
1080   }
1081 
1082   private static final boolean RED   = false;
1083 
1084   private static final boolean BLACK = true;
1085 
1086   /**
1087     * Node in the Tree.  Doubles as a means to pass key-value pairs back to
1088     * user (see Map.Entry).
1089     */
1090 
1091   private static class Entry<M,N> implements Map.Entry<M,N> {
1092     M key;
1093     N value;
1094     Entry<M,N> left = null;
1095     Entry<M,N> right = null;
1096     Entry<M,N> parent;
1097     boolean color = BLACK;
1098 
1099     /** Make a new cell with given key, value, and parent, and with
1100       <tt>null</tt> child links, and BLACK color.
1101       */
1102     Entry(M key, N value, Entry<M,N> parent) {
1103       this.key = key;
1104       this.value = value;
1105       this.parent = parent;
1106     }
1107 
1108     /**
1109       * Returns the key.
1110       *
1111       @return the key.
1112       */
1113     @Override
1114     public M getKey() {
1115         return key;
1116     }
1117 
1118     /**
1119       * Returns the value associated with the key.
1120       *
1121       @return the value associated with the key.
1122       */
1123     @Override
1124     public N getValue() {
1125         return value;
1126     }
1127 
1128     /**
1129       * Replaces the value currently associated with the key with the given
1130       * value.
1131       *
1132       @return the value associated with the key before this method was
1133       * called.
1134       */
1135     @Override
1136     public N setValue(N value) {
1137         N oldValue = this.value;
1138         this.value = value;
1139         return oldValue;
1140     }
1141 
1142     @Override
1143     public boolean equals(Object o) {
1144         if (!(instanceof Map.Entry))
1145       return false;
1146         @SuppressWarnings("unchecked")
1147         Map.Entry<M,N> e = (Map.Entry<M,N>)o;
1148 
1149         return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1150     // equals
1151 
1152     @Override
1153     public int hashCode() {
1154         int keyHash = (key==null : key.hashCode());
1155         int valueHash = (value==null : value.hashCode());
1156         return keyHash ^ valueHash;
1157     // hashCode
1158 
1159     @Override
1160     public String toString() {
1161         return key + "=" + value;
1162     }
1163   // Entry
1164 
1165   /**
1166     * Returns the first Entry in the RBTreeMap (according to the RBTreeMap's
1167     * key-sort function).  Returns null if the RBTreeMap is empty.
1168     */
1169   private Entry<K,V> firstEntry() {
1170     Entry<K,V> p = root;
1171     if (p != null)
1172       while (p.left != null)
1173         p = p.left;
1174     return p;
1175   }
1176 
1177   /**
1178     * Returns the last Entry in the RBTreeMap (according to the RBTreeMap's
1179     * key-sort function).  Returns null if the RBTreeMap is empty.
1180     */
1181   private Entry<K,V> lastEntry() {
1182     Entry<K,V> p = root;
1183     if (p != null)
1184       while (p.right != null)
1185         p = p.right;
1186     return p;
1187   }
1188 
1189   /**
1190     * Returns the successor of the specified Entry, or null if no such.
1191     */
1192   private Entry<K,V> successor(Entry<K,V> t) {
1193     if (t == null)
1194       return null;
1195     else if (t.right != null) {
1196       Entry<K,V> p = t.right;
1197       while (p.left != null)
1198         p = p.left;
1199       return p;
1200     else {
1201       Entry<K,V> p = t.parent;
1202       Entry<K,V> ch = t;
1203       while (p != null && ch == p.right) {
1204         ch = p;
1205         p = p.parent;
1206       }
1207       return p;
1208     }
1209   // successor
1210 
1211   /**
1212     * Balancing operations.
1213     *
1214     * Implementations of rebalancings during insertion and deletion are
1215     * slightly different than the CLR version.  Rather than using dummy
1216     * nilnodes, we use a set of accessors that deal properly with null.  They
1217     * are used to avoid messiness surrounding nullness checks in the main
1218     * algorithms.
1219     */
1220 
1221   private static boolean colorOf(Entry<?,?> p) {
1222     return (p == null ? BLACK : p.color);
1223   }
1224 
1225   private static <X,Y> Entry<X,Y> parentOf(Entry<X,Y> p) {
1226     return (p == null null: p.parent);
1227   }
1228 
1229   private static void setColor(Entry<?,?> p, boolean c) {
1230     if (p != null)  p.color = c;
1231   }
1232 
1233   private static <X,Y> Entry<X,Y> leftOf(Entry<X,Y> p) {
1234     return (p == null)null: p.left;
1235   }
1236 
1237   private static <X,Y> Entry<X,Y> rightOf(Entry<X,Y> p) {
1238     return (p == null)null: p.right;
1239   }
1240 
1241   /** From CLR **/
1242   private void rotateLeft(Entry<K,V> p) {
1243     Entry<K,V> r = p.right;
1244     p.right = r.left;
1245 
1246     if (r.left != null)
1247       r.left.parent = p;
1248     r.parent = p.parent;
1249 
1250     if (p.parent == null)
1251       root = r;
1252     else if (p.parent.left == p)
1253       p.parent.left = r;
1254     else
1255       p.parent.right = r;
1256     r.left = p;
1257     p.parent = r;
1258   }
1259 
1260   /** From CLR **/
1261   private void rotateRight(Entry<K,V> p) {
1262     Entry<K,V> l = p.left;
1263     p.left = l.right;
1264 
1265     if (l.right != nulll.right.parent = p;
1266     l.parent = p.parent;
1267 
1268     if (p.parent == null)
1269         root = l;
1270     else if (p.parent.right == p)
1271         p.parent.right = l;
1272     else p.parent.left = l;
1273 
1274     l.right = p;
1275     p.parent = l;
1276   }
1277 
1278 
1279   /** From CLR **/
1280   private void fixAfterInsertion(Entry<K,V> x) {
1281     x.color = RED;
1282 
1283     while (x != null && x != root && x.parent.color == RED) {
1284       if (parentOf(x== leftOf(parentOf(parentOf(x)))) {
1285         Entry<K,V> y = rightOf(parentOf(parentOf(x)));
1286         if (colorOf(y== RED) {
1287           setColor(parentOf(x), BLACK);
1288           setColor(y, BLACK);
1289           setColor(parentOf(parentOf(x)), RED);
1290           x = parentOf(parentOf(x));
1291         else {
1292           if (x == rightOf(parentOf(x))) {
1293             x = parentOf(x);
1294             rotateLeft(x);
1295           }
1296           setColor(parentOf(x), BLACK);
1297           setColor(parentOf(parentOf(x)), RED);
1298           if (parentOf(parentOf(x)) != null)
1299             rotateRight(parentOf(parentOf(x)));
1300         }
1301       else {
1302         Entry<K,V> y = leftOf(parentOf(parentOf(x)));
1303         if (colorOf(y== RED) {
1304             setColor(parentOf(x), BLACK);
1305             setColor(y, BLACK);
1306             setColor(parentOf(parentOf(x)), RED);
1307             x = parentOf(parentOf(x));
1308         else {
1309           if (x == leftOf(parentOf(x))) {
1310             x = parentOf(x);
1311             rotateRight(x);
1312           }
1313           setColor(parentOf(x),  BLACK);
1314           setColor(parentOf(parentOf(x)), RED);
1315           if (parentOf(parentOf(x)) != null)
1316             rotateLeft(parentOf(parentOf(x)));
1317         }
1318       }
1319     }
1320     root.color = BLACK;
1321   // fixAfterInsertion
1322 
1323   /**
1324     * Delete node p, and then rebalance the tree.
1325     */
1326   private void deleteEntry(Entry<K,V> p) {
1327     decrementSize();
1328 
1329     // If strictly internal, first swap position with successor.
1330     if (p.left != null && p.right != null) {
1331         Entry<K,V> s = successor(p);
1332         swapPosition(s, p);
1333     }
1334 
1335     // Start fixup at replacement node, if it exists.
1336     Entry<K,V> replacement = (p.left != null ? p.left : p.right);
1337 
1338     if (replacement != null) {
1339       // Link replacement to parent
1340       replacement.parent = p.parent;
1341       if (p.parent == null)
1342         root = replacement;
1343       else if (p == p.parent.left)
1344         p.parent.left  = replacement;
1345       else
1346         p.parent.right = replacement;
1347 
1348     // Null out links so they are OK to use by fixAfterDeletion.
1349     p.left = p.right = p.parent = null;
1350 
1351     // Fix replacement
1352     if (p.color == BLACK)
1353       fixAfterDeletion(replacement);
1354     else if (p.parent == null) { // return if we are the only node.
1355       root = null;
1356     else //  No children. Use self as phantom replacement and unlink.
1357       if (p.color == BLACK)
1358         fixAfterDeletion(p);
1359 
1360       if (p.parent != null) {
1361         if (p == p.parent.left)
1362           p.parent.left = null;
1363         else if (p == p.parent.right)
1364           p.parent.right = null;
1365         p.parent = null;
1366       }
1367     }
1368   // deleteEntry
1369 
1370   /** From CLR **/
1371   private void fixAfterDeletion(Entry<K,V> x) {
1372     while (x != root && colorOf(x== BLACK) {
1373       if (x == leftOf(parentOf(x))) {
1374         Entry<K,V> sib = rightOf(parentOf(x));
1375 
1376         if (colorOf(sib== RED) {
1377           setColor(sib, BLACK);
1378           setColor(parentOf(x), RED);
1379           rotateLeft(parentOf(x));
1380           sib = rightOf(parentOf(x));
1381         }
1382 
1383         if (colorOf(leftOf(sib))  == BLACK &&
1384             colorOf(rightOf(sib)) == BLACK) {
1385           setColor(sib,  RED);
1386           x = parentOf(x);
1387         else {
1388           if (colorOf(rightOf(sib)) == BLACK) {
1389             setColor(leftOf(sib), BLACK);
1390             setColor(sib, RED);
1391             rotateRight(sib);
1392             sib = rightOf(parentOf(x));
1393           }
1394           setColor(sib, colorOf(parentOf(x)));
1395           setColor(parentOf(x), BLACK);
1396           setColor(rightOf(sib), BLACK);
1397           rotateLeft(parentOf(x));
1398           x = root;
1399         }
1400       else // symmetric
1401         Entry<K,V> sib = leftOf(parentOf(x));
1402 
1403         if (colorOf(sib== RED) {
1404           setColor(sib, BLACK);
1405           setColor(parentOf(x), RED);
1406           rotateRight(parentOf(x));
1407           sib = leftOf(parentOf(x));
1408         }
1409 
1410         if (colorOf(rightOf(sib)) == BLACK &&
1411           colorOf(leftOf(sib)) == BLACK) {
1412           setColor(sib,  RED);
1413           x = parentOf(x);
1414         else {
1415           if (colorOf(leftOf(sib)) == BLACK) {
1416             setColor(rightOf(sib), BLACK);
1417             setColor(sib, RED);
1418             rotateLeft(sib);
1419             sib = leftOf(parentOf(x));
1420           }
1421           setColor(sib, colorOf(parentOf(x)));
1422           setColor(parentOf(x), BLACK);
1423           setColor(leftOf(sib), BLACK);
1424           rotateRight(parentOf(x));
1425           x = root;
1426         }
1427       }
1428     }
1429     setColor(x, BLACK);
1430   // fixAfterDeletion
1431 
1432   /**
1433     * Swap the linkages of two nodes in a tree.
1434     */
1435   private void swapPosition(Entry<K,V> x, Entry<K,V> y) {
1436     // Save initial values.
1437     Entry<K,V> px = x.parent, lx = x.left, rx = x.right;
1438     Entry<K,V> py = y.parent, ly = y.left, ry = y.right;
1439     boolean xWasLeftChild = px != null && x == px.left;
1440     boolean yWasLeftChild = py != null && y == py.left;
1441 
1442     // Swap, handling special cases of one being the other's parent.
1443     if (x == py) {  // x was y's parent
1444       x.parent = y;
1445 
1446       if (yWasLeftChild) {
1447         y.left = x;
1448         y.right = rx;
1449       else {
1450         y.right = x;
1451         y.left = lx;
1452       }
1453     else {
1454       x.parent = py;
1455 
1456       if (py != null) {
1457         if (yWasLeftChild)
1458           py.left = x;
1459         else
1460           py.right = x;
1461       }
1462       y.left = lx;
1463       y.right = rx;
1464     }
1465 
1466     if (y == px) { // y was x's parent
1467       y.parent = x;
1468       if (xWasLeftChild) {
1469         x.left = y;
1470         x.right = ry;
1471       else {
1472         x.right = y;
1473         x.left = ly;
1474       }
1475     else {
1476       y.parent = px;
1477       if (px != null) {
1478         if (xWasLeftChild)
1479           px.left = y;
1480         else
1481           px.right = y;
1482       }
1483       x.left = ly;
1484       x.right = ry;
1485     }
1486 
1487     // Fix children's parent pointers
1488     if (x.left != null)
1489       x.left.parent = x;
1490 
1491     if (x.right != null)
1492       x.right.parent = x;
1493 
1494     if (y.left != null)
1495       y.left.parent = y;
1496 
1497     if (y.right != null)
1498       y.right.parent = y;
1499 
1500     // Swap colors
1501     boolean c = x.color;
1502     x.color = y.color;
1503     y.color = c;
1504 
1505     // Check if root changed
1506     if (root == x)
1507         root = y;
1508     else if (root == y)
1509         root = x;
1510   // swapPosition
1511 
1512 
1513 
1514 
1515   /**
1516     * Save the state of the <tt>RBTreeMap</tt> instance to a stream (i.e.,
1517     * serialize it).
1518     *
1519     @serialData The <i>size</i> of the RBTreeMap (the number of key-value
1520     *       mappings) is emitted (int), followed by the key (Object)
1521     *       and value (Object) for each key-value mapping represented
1522     *       by the RBTreeMap. The key-value mappings are emitted in
1523     *       key-order (as determined by the RBTreeMap's Comparator,
1524     *       or by the keys' natural ordering if the RBTreeMap has no
1525     *             Comparator).
1526     */
1527   private void writeObject(java.io.ObjectOutputStream s)
1528       throws java.io.IOException {
1529 
1530     // Write out the Comparator and any hidden stuff
1531     s.defaultWriteObject();
1532 
1533     // Write out size (number of Mappings)
1534     s.writeInt(size);
1535 
1536           // Write out keys and values (alternating)
1537     for (java.util.Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext()) {
1538               Map.Entry<K,V> e = i.next();
1539               s.writeObject(e.getKey());
1540               s.writeObject(e.getValue());
1541     }
1542   // writeObject
1543 
1544 
1545 
1546   /**
1547     * Reconstitute the <tt>RBTreeMap</tt> instance from a stream (i.e.,
1548     * deserialize it).
1549     */
1550   private void readObject(final java.io.ObjectInputStream s)
1551       throws java.io.IOException, ClassNotFoundException {
1552 
1553     // Read in the Comparator and any hidden stuff
1554     s.defaultReadObject();
1555 
1556     // Read in size
1557     int size = s.readInt();
1558 
1559     buildFromSorted(size, null, s, null);
1560   // readObject
1561 
1562   /** Intended to be called only from TreeSet.readObject */
1563   void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
1564       throws java.io.IOException, ClassNotFoundException {
1565     buildFromSorted(size, null, s, defaultVal);
1566   }
1567 
1568   /** Intended to be called only from TreeSet.addAll */
1569   void addAllForTreeSet(SortedSet<K> set, V defaultVal) {
1570     try {
1571       buildFromSorted(set.size(), set.iterator(), null, defaultVal);
1572     catch (java.io.IOException cannotHappen) {
1573     catch (ClassNotFoundException cannotHappen) {
1574     }
1575   }
1576 
1577 
1578   /**
1579     * Linear time tree building algorithm from sorted data.  Can accept keys
1580     * and/or values from iterator or stream. This leads to too many
1581     * parameters, but seems better than alternatives.  The four formats
1582     * that this method accepts are:
1583     *
1584     *    1) An iterator of Map.Entries.  (it != null, defaultVal == null).
1585     *    2) An iterator of keys.         (it != null, defaultVal != null).
1586     *    3) A stream of alternating serialized keys and values.
1587     *            (it == null, defaultVal == null).
1588     *    4) A stream of serialized keys. (it == null, defaultVal != null).
1589     *
1590     * It is assumed that the comparator of the RBTreeMap is already set prior
1591     * to calling this method.
1592     *
1593     @param size the number of keys (or key-value pairs) to be read from
1594     *        the iterator or stream.
1595     @param it If non-null, new entries are created from entries
1596     *        or keys read from this iterator.
1597     @param str If non-null, new entries are created from keys and
1598     *        possibly values read from this stream in serialized form.
1599     *        Exactly one of it and str should be non-null.
1600     @param defaultVal if non-null, this default value is used for
1601     *        each value in the map.  If null, each value is read from
1602     *        iterator or stream, as described above.
1603     @throws IOException propagated from stream reads. This cannot
1604     *         occur if str is null.
1605     @throws ClassNotFoundException propagated from readObject.
1606     *         This cannot occur if str is null.
1607     */
1608   private void buildFromSorted(int size, java.util.Iterator<?> it,
1609                                 java.io.ObjectInputStream str,
1610                                 V defaultVal)
1611     throws  java.io.IOException, ClassNotFoundException {
1612 
1613     this.size = size;
1614     root = buildFromSorted(00, size-1, computeRedLevel(size),
1615                              it, str, defaultVal);
1616   // buildFromSorted
1617 
1618   /**
1619     * Recursive "helper method" that does the real work of the
1620     * of the previous method.  Identically named parameters have
1621     * identical definitions.  Additional parameters are documented below.
1622     * It is assumed that the comparator and size fields of the RBTreeMap are
1623     * already set prior to calling this method.  (It ignores both fields.)
1624     *
1625     @param level the current level of tree. Initial call should be 0.
1626     @param lo the first element index of this subtree. Initial should be 0.
1627     @param hi the last element index of this subtree.  Initial should be
1628     *        size-1.
1629     @param redLevel the level at which nodes should be red.
1630     *        Must be equal to computeRedLevel for tree of this size.
1631     */
1632   @SuppressWarnings("unchecked")
1633   private static <X,Y> Entry<X,Y> buildFromSorted(int level, int lo, int hi,
1634                                        int redLevel,
1635                                        java.util.Iterator<?> it,
1636                                        java.io.ObjectInputStream str,
1637                                        Y defaultVal)
1638     throws  java.io.IOException, ClassNotFoundException {
1639     /*
1640      * Strategy: The root is the middlemost element. To get to it, we
1641      * have to first recursively construct the entire left subtree,
1642      * so as to grab all of its elements. We can then proceed with right
1643      * subtree.
1644      *
1645      * The lo and hi arguments are the minimum and maximum
1646      * indices to pull out of the iterator or stream for current subtree.
1647      * They are not actually indexed, we just proceed sequentially,
1648      * ensuring that items are extracted in corresponding order.
1649      */
1650 
1651     if (hi < loreturn null;
1652 
1653     int mid = (lo + hi2;
1654 
1655     Entry<X,Y> left  = null;
1656     if (lo < mid)
1657       left = buildFromSorted(level+1, lo, mid - 1, redLevel,
1658                                it, str, defaultVal);
1659 
1660     // extract key and/or value from iterator or stream
1661     X key;
1662     Y value;
1663 
1664     if (it != null) { // use iterator
1665 
1666       if (defaultVal==null) {
1667         Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
1668         key = (X)entry.getKey();
1669         value = (Y)entry.getValue();
1670       else {
1671         key = (X)it.next();
1672         value = defaultVal;
1673       }
1674     else // use stream
1675       key = (X)str.readObject();
1676       value = (defaultVal != null ? defaultVal : (Y)str.readObject());
1677     }
1678 
1679     Entry<X,Y> middle =  new Entry<X,Y>(key, value, null);
1680 
1681     // color nodes in non-full bottommost level red
1682     if (level == redLevel)
1683       middle.color = RED;
1684 
1685     if (left != null) {
1686       middle.left = left;
1687       left.parent = middle;
1688     }
1689 
1690     if (mid < hi) {
1691       Entry<X,Y> right = buildFromSorted(level+1, mid+1, hi, redLevel,
1692                                     it, str, defaultVal);
1693       middle.right = right;
1694       right.parent = middle;
1695     }
1696 
1697     return middle;
1698 
1699   // Entry buildFromSorted
1700 
1701   /**
1702     * Find the level down to which to assign all nodes BLACK.  This is the
1703     * last `full' level of the complete binary tree produced by
1704     * buildTree. The remaining nodes are colored RED. (This makes a `nice'
1705     * set of color assignments wrt future insertions.) This level number is
1706     * computed by finding the number of splits needed to reach the zeroeth
1707     * node.  (The answer is ~lg(N), but in any case must be computed by same
1708     * quick O(lg(N)) loop.)
1709     */
1710   private static int computeRedLevel(int sz) {
1711     int level = 0;
1712     for (int m = sz - 1; m >= 0; m = m / 1)
1713         level++;
1714     return level;
1715   }
1716 
1717 // class RBTreeMap