*/    private Entry getPrecedingEntry(Object key) {        Entry p = root;        if (p==null)            return null;        while (true) {            int cmp = compare(key, p.key);            if (cmp > 0) {                if (p.right != null)                    p = p.right;                else                    return p;            } else {                if (p.left != null) {                    p = p.left;                } else {                    Entry parent = p.parent;                    Entry ch = p;                    while (parent != null && ch == parent.left) {                        ch = parent;                        parent = parent.parent;                    }                    return parent;                }            }        }    }    /**     * Returns the key corresonding to the specified Entry.  Throw      * NoSuchElementException if the Entry is <tt>null</tt>.     */    private static Object key(Entry e) {        if (e==null)            throw new NoSuchElementException();        return e.key;    }    /**     * Associates the specified value with the specified key in this map.     * If the map previously contained a mapping for this key, the old     * value is replaced.     *     * @param key key with which the specified value is to be associated.     * @param value value to be associated with the specified key.     *      * @return previous value associated with specified key, or <tt>null</tt>     *         if there was no mapping for key.  A <tt>null</tt> return can     *         also indicate that the map previously associated <tt>null</tt>     *         with the specified key.     * @throws    ClassCastException key cannot be compared with the keys     *            currently in the map.     * @throws NullPointerException key is <tt>null</tt> and this map uses     *         natural order, or its comparator does not tolerate     *         <tt>null</tt> keys.     */    public Object put(Object key, Object value) {        Entry t = root;        if (t == null) {            incrementSize();            root = new Entry(key, value, null);            return null;       }        while (true) {            int cmp = compare(key, t.key);            if (cmp == 0) {                return t.setValue(value);            } else if (cmp < 0) {                if (t.left != null) {                    t = t.left;                } else {                    incrementSize();                    t.left = new Entry(key, value, t);                    fixAfterInsertion(t.left);                    return null;                }            } else { // cmp > 0                if (t.right != null) {                    t = t.right;                } else {                    incrementSize();                    t.right = new Entry(key, value, t);                    fixAfterInsertion(t.right);                    return null;                }            }        }    }    /**     * Removes the mapping for this key from this TreeMap if present.     *     * @param  key key for which mapping should be removed     * @return previous value associated with specified key, or <tt>null</tt>     *         if there was no mapping for key.  A <tt>null</tt> return can     *         also indicate that the map previously associated     *         <tt>null</tt> with the specified key.     *      * @throws    ClassCastException key cannot be compared with the keys     *            currently in the map.     * @throws NullPointerException key is <tt>null</tt> and this map uses     *         natural order, or its comparator does not tolerate     *         <tt>null</tt> keys.     */    public Object remove(Object key) {        Entry p = getEntry(key);        if (p == null)            return null;        Object oldValue = p.value;        deleteEntry(p);        return oldValue;    }    /**     * Removes all mappings from this TreeMap.     */    public void clear() {        modCount++;        size = 0;        root = null;    }    /**     * Returns a shallow copy of this <tt>TreeMap</tt> instance. (The keys and     * values themselves are not cloned.)     *     * @return a shallow copy of this Map.     */    public Object clone() {        TreeMap clone = null;        try {             clone = (TreeMap)super.clone();        } catch (CloneNotSupportedException e) {             throw new InternalError();        }        // Put clone into "virgin" state (except for comparator)        clone.root = null;        clone.size = 0;        clone.modCount = 0;        clone.entrySet = null;        // Initialize clone with our mappings        try {            clone.buildFromSorted(size, entrySet().iterator(), null, null);        } catch (java.io.IOException cannotHappen) {        } catch (ClassNotFoundException cannotHappen) {        }        return clone;    }    // Views    /**     * This field is initialized to contain an instance of the entry set     * view the first time this view is requested.  The view is stateless,     * so there's no reason to create more than one.     */    private transient volatile Set entrySet = null;    /**     * Returns a Set view of the keys contained in this map.  The set's     * iterator will return the keys in ascending order.  The map is backed by     * this <tt>TreeMap</tt> instance, so changes to this map are reflected in     * the Set, and vice-versa.  The Set supports element removal, which     * removes the corresponding mapping from the map, via the     * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,     * <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not support     * the <tt>add</tt> or <tt>addAll</tt> operations.     *     * @return a set view of the keys contained in this TreeMap.     */    public Set keySet() {        if (keySet == null) {            keySet = new AbstractSet() {                public Iterator iterator() {                    return new KeyIterator();                }                public int size() {                    return TreeMap.this.size();                }                public boolean contains(Object o) {                    return containsKey(o);                }                public boolean remove(Object o) {                    int oldSize = size;                    TreeMap.this.remove(o);                    return size != oldSize;                }                public void clear() {                    TreeMap.this.clear();                }            };        }        return keySet;    }    /**     * Returns a collection view of the values contained in this map.  The     * collection's iterator will return the values in the order that their     * corresponding keys appear in the tree.  The collection is backed by     * this <tt>TreeMap</tt> instance, so changes to this map are reflected in     * the collection, and vice-versa.  The collection supports element     * removal, which removes the corresponding mapping from the map through     * the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.     * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.     *     * @return a collection view of the values contained in this map.     */    public Collection values() {        if (values == null) {            values = new AbstractCollection() {                public Iterator iterator() {                    return new ValueIterator();                }                public int size() {                    return TreeMap.this.size();                }                public boolean contains(Object o) {                    for (Entry e = firstEntry(); e != null; e = successor(e))                        if (valEquals(e.getValue(), o))                            return true;                    return false;                }                public boolean remove(Object o) {                    for (Entry e = firstEntry(); e != null; e = successor(e)) {                        if (valEquals(e.getValue(), o)) {                            deleteEntry(e);                            return true;                        }                    }                    return false;                }                public void clear() {                    TreeMap.this.clear();                }            };        }        return values;    }    /**     * Returns a set view of the mappings contained in this map.  The set's     * iterator returns the mappings in ascending key order.  Each element in     * the returned set is a <tt>Map.Entry</tt>.  The set is backed by this     * map, so changes to this map are reflected in the set, and vice-versa.     * The set supports element removal, which removes the corresponding     * mapping from the TreeMap, through the <tt>Iterator.remove</tt>,     * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and     * <tt>clear</tt> operations.  It does not support the <tt>add</tt> or     * <tt>addAll</tt> operations.     *     * @return a set view of the mappings contained in this map.     * @see Map.Entry     */    public Set entrySet() {        if (entrySet == null) {            entrySet = new AbstractSet() {                public Iterator iterator() {                    return new EntryIterator();                }                public boolean contains(Object o) {                    if (!(o instanceof Map.Entry))                        return false;                    Map.Entry entry = (Map.Entry)o;                    Object value = entry.getValue();                    Entry p = getEntry(entry.getKey());                    return p != null && valEquals(p.getValue(), value);                }                public boolean remove(Object o) {                    if (!(o instanceof Map.Entry))                        return false;                    Map.Entry entry = (Map.Entry)o;                    Object value = entry.getValue();                    Entry p = getEntry(entry.getKey());                    if (p != null && valEquals(p.getValue(), value)) {                        deleteEntry(p);                        return true;                    }                    return false;                }                public int size() {                    return TreeMap.this.size();                }                public void clear() {                    TreeMap.this.clear();                }            };        }        return entrySet;    }    /**     * Returns a view of the portion of this map whose keys range from     * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If     * <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map     * is empty.)  The returned sorted map is backed by this map, so changes     * in the returned sorted map are reflected in this map, and vice-versa.     * The returned sorted map supports all optional map operations.<p>     *     * The sorted map returned by this method will throw an     * <tt>IllegalArgumentException</tt> if the user attempts to insert a key     * less than <tt>fromKey</tt> or greater than or equal to     * <tt>toKey</tt>.<p>     *     * Note: this method always returns a <i>half-open range</i> (which     * includes its low endpoint but not its high endpoint).  If you need a     * <i>closed range</i> (which includes both endpoints), and the key type     * allows for calculation of the successor a given key, merely request the     * subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.     * For example, suppose that <tt>m</tt> is a sorted map whose keys are     * strings.  The following idiom obtains a view containing all of the     * key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>     * and <tt>high</tt>, inclusive:     *             <pre>    SortedMap sub = m.submap(low, high+"\0");</pre>     * A similar technique can be used to generate an <i>open range</i> (which     * contains neither endpoint).  The following idiom obtains a view     * containing all of the key-value mappings in <tt>m</tt> whose keys are     * between <tt>low</tt> and <tt>high</tt>, exclusive:     *             <pre>    SortedMap sub = m.subMap(low+"\0", high);</pre>     *     * @param fromKey low endpoint (inclusive) of the subMap.     * @param toKey high endpoint (exclusive) of the subMap.     *      * @return a view of the portion of this map whose keys range from     *                <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.     *      * @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>     *         cannot be compared to one another using this map's comparator     *         (or, if the map has no comparator, using natural ordering).     * @throws IllegalArgumentException if <tt>fromKey</tt> is greater than     *         <tt>toKey</tt>.     * @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is     *               <tt>null</tt> and this map uses natural order, or its     *               comparator does not tolerate <tt>null</tt> keys.     */    public SortedMap subMap(Object fromKey, Object toKey) {        return new SubMap(fromKey, toKey);    }    /**     * Returns a view of the portion of this map whose keys are strictly less     * than <tt>toKey</tt>.  The returned sorted map is backed by this map, so     * changes in the returned sorted map are reflected in this map, and     * vice-versa.  The returned sorted map supports all optional map     * operations.<p>     *     * The sorted map returned by this method will throw an     * <tt>IllegalArgumentException</tt> if the user attempts to insert a key     * greater than or equal to <tt>toKey</tt>.<p>     *     * Note: this method always returns a view that does not contain its     * (high) endpoint.  If you need a view that does contain this endpoint,     * and the key type allows for calculation of the successor a given key,     * merely request a headMap bounded by <tt>successor(highEndpoint)</tt>.     * For example, suppose that suppose that <tt>m</tt> is a sorted map whose     * keys are strings.  The following idiom obtains a view containing all of     * the key-value mappings in <tt>m</tt> whose keys are less than or equal     * to <tt>high</tt>:     * <pre>     *     SortedMap head = m.headMap(high+"\0");     * </pre>     *     * @param toKey high endpoint (exclusive) of the headMap.     * @return a view of the portion of this map whose keys are strictly     *                less than <tt>toKey</tt>.     *     * @throws ClassCastException if <tt>toKey</tt> is not compatible     *         with this map's comparator (or, if the map has no comparator,     *         if <tt>toKey</tt> does not implement <tt>Comparable</tt>).     * @throws IllegalArgumentException if this map is itself a subMap,     *         headMap, or tailMap, and <tt>toKey</tt> is not within the     *         specified range of the subMap, headMap, or tailMap.     * @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and     *               this map uses natural order, or its comparator does not     *               tolerate <tt>null</tt> keys.     */    public SortedMap headMap(Object toKey) {        return new SubMap(toKey, true);    }    /**     * Returns a view of the portion of this map whose keys are greater than     * or equal to <tt>fromKey</tt>.  The returned sorted map is backed by     * this map, so changes in the returned sorted map are reflected in this     * map, and vice-versa.  The returned sorted map supports all optional map     * operations.<p>     *     * The sorted map returned by this method will throw an     * <tt>IllegalArgumentException</tt> if the user attempts to insert a key     * less than <tt>fromKey</tt>.<p>     *     * Note: this method always returns a view that contains its (low)     * endpoint.  If you need a view that does not contain this endpoint, and     * the element type allows for calculation of the successor a given value,     * merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.