public TreeMap() 
{
        comparator = null;
}

Constructs a new, empty tree map, using the natural ordering of its keys. All keys inserted into the map must implement the Comparable interface. Furthermore, all such keys must be mutually comparable: {@code k1.compareTo(k2)} must not throw a {@code ClassCastException} for any keys {@code k1} and {@code k2} in the map. If the user attempts to put a key into the map that violates this constraint (for example, the user attempts to put a string key into a map whose keys are integers), the {@code put(Object key, Object value)} call will throw a {@code ClassCastException}.

 public TreeMap(Comparator<? super K> comparator) 
{
        this.comparator = comparator;
}

Constructs a new, empty tree map, ordered according to the given comparator. All keys inserted into the map must be mutually comparable by the given comparator: {@code comparator.compare(k1, k2)} must not throw a {@code ClassCastException} for any keys {@code k1} and {@code k2} in the map. If the user attempts to put a key into the map that violates this constraint, the {@code put(Object key, Object value)} call will throw a {@code ClassCastException}.

Parameters:

comparator - the comparator that will be used to order this map. If {@code null}, the {@linkplain Comparable natural ordering} of the keys will be used.

 public TreeMap(Map<? extends K, ? extends V> m) 
{
        comparator = null;
        putAll(m);
}

Constructs a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys. All keys inserted into the new map must implement the Comparable interface. Furthermore, all such keys must be mutually comparable: {@code k1.compareTo(k2)} must not throw a {@code ClassCastException} for any keys {@code k1} and {@code k2} in the map. This method runs in n*log(n) time.

Parameters:

m - the map whose mappings are to be placed in this map

Throws:

ClassCastException - if the keys in m are not Comparable , or are not mutually comparable

NullPointerException - if the specified map is null

 public TreeMap(SortedMap<K, ? extends V> m) 
{
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
}

Constructs a new tree map containing the same mappings and using the same ordering as the specified sorted map. This method runs in linear time.

Parameters:

m - the sorted map whose mappings are to be placed in this map, and whose comparator is to be used to sort this map

Throws:

NullPointerException - if the specified map is null

  void addAllForTreeSet(SortedSet<? extends K> set,
    V defaultVal) 
{
        try {
            buildFromSorted(set.size(), set.iterator(), null, defaultVal);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
}

Intended to be called only from TreeSet.addAll

 public Entry<K, V> ceilingEntry(K key) 
{
        return exportEntry(getCeilingEntry(key));
}

 public K ceilingKey(K key) 
{
        return keyOrNull(getCeilingEntry(key));
}

 public  void clear() 
{
        modCount++;
        size = 0;
        root = null;
}

Removes all of the mappings from this map. The map will be empty after this call returns.

 public Object clone() 
{
        TreeMap< K,V > clone = null;
        try {
            clone = (TreeMap< K,V >) 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;
        clone.navigableKeySet = null;
        clone.descendingMap = null;
        // Initialize clone with our mappings
        try {
            clone.buildFromSorted(size, entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
        return clone;
}

Returns a shallow copy of this {@code TreeMap} instance. (The keys and values themselves are not cloned.)

 public Comparator<? super K> comparator() 
{
        return comparator;
}

 final int compare(Object k1,
    Object k2) 
{
        return comparator==null ? ((Comparable< ? super K >)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
}

Compares two keys using the correct comparison method for this TreeMap.

 public boolean containsKey(Object key) 
{
        return getEntry(key) != null;
}

Returns {@code true} if this map contains a mapping for the specified key.

 public boolean containsValue(Object value) 
{
        for (Entry< K,V > e = getFirstEntry(); e != null; e = successor(e))
            if (valEquals(value, e.value))
                return true;
        return false;
}

Returns {@code true} if this map maps one or more keys to the specified value. More formally, returns {@code true} if and only if this map contains at least one mapping to a value {@code v} such that {@code (value==null ? v==null : value.equals(v))}. This operation will probably require time linear in the map size for most implementations.

 Iterator<K> descendingKeyIterator() 
{
        return new DescendingKeyIterator(getLastEntry());
}

 public NavigableSet<K> descendingKeySet() 
{
        return descendingMap().navigableKeySet();
}

 public NavigableMap<K, V> descendingMap() 
{
        NavigableMap< K, V > km = descendingMap;
        return (km != null) ? km :
            (descendingMap = new DescendingSubMap(this,
                                                  true, null, true,
                                                  true, null, true));
}

 public Set<K, V> entrySet() 
{
        EntrySet es = entrySet;
        return (es != null) ? es : (entrySet = new EntrySet());
}

Returns a Set view of the mappings contained in this map. The set's iterator returns the entries in ascending key order. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own {@code remove} operation, or through the {@code setValue} operation on a map entry returned by the iterator) the results of the iteration are undefined. The set supports element removal, which removes the corresponding mapping from the map, via the {@code Iterator.remove}, {@code Set.remove}, {@code removeAll}, {@code retainAll} and {@code clear} operations. It does not support the {@code add} or {@code addAll} operations.

 static Entry<K, V> exportEntry(Entry<K, V> e) 
{
        return (e == null) ? null :
            new AbstractMap.SimpleImmutableEntry<  >(e);
}

Return SimpleImmutableEntry for entry, or null if null

 public Entry<K, V> firstEntry() 
{
        return exportEntry(getFirstEntry());
}

 public K firstKey() 
{
        return key(getFirstEntry());
}

 public Entry<K, V> floorEntry(K key) 
{
        return exportEntry(getFloorEntry(key));
}

 public K floorKey(K key) 
{
        return keyOrNull(getFloorEntry(key));
}

 public V get(Object key) 
{
        Entry< K,V > p = getEntry(key);
        return (p==null ? null : p.value);
}

Returns the value to which the specified key is mapped, or {@code null} if this map contains no mapping for the key.

More formally, if this map contains a mapping from a key {@code k} to a value {@code v} such that {@code key} compares equal to {@code k} according to the map's ordering, then this method returns {@code v}; otherwise it returns {@code null}. (There can be at most one such mapping.)

A return value of {@code null} does not necessarily indicate that the map contains no mapping for the key; it's also possible that the map explicitly maps the key to {@code null}. The containsKey operation may be used to distinguish these two cases.

 final Entry<K, V> getCeilingEntry(K key) 
{
        Entry< K,V > p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            if (cmp <  0) {
                if (p.left != null)
                    p = p.left;
                else
                    return p;
            } else if (cmp  > 0) {
                if (p.right != null) {
                    p = p.right;
                } else {
                    Entry< K,V > parent = p.parent;
                    Entry< K,V > ch = p;
                    while (parent != null && ch == parent.right) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            } else
                return p;
        }
        return null;
}

Gets the entry corresponding to the specified key; if no such entry exists, returns the entry for the least key greater than the specified key; if no such entry exists (i.e., the greatest key in the Tree is less than the specified key), returns {@code null}.

 final Entry<K, V> getEntry(Object key) 
{
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        Comparable< ? super K > k = (Comparable< ? super K >) key;
        Entry< K,V > p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp <  0)
                p = p.left;
            else if (cmp  > 0)
                p = p.right;
            else
                return p;
        }
        return null;
}

Returns this map's entry for the given key, or {@code null} if the map does not contain an entry for the key.

 final Entry<K, V> getEntryUsingComparator(Object key) 
{
        K k = (K) key;
        Comparator< ? super K > cpr = comparator;
        if (cpr != null) {
            Entry< K,V > p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp <  0)
                    p = p.left;
                else if (cmp  > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
}

Version of getEntry using comparator. Split off from getEntry for performance. (This is not worth doing for most methods, that are less dependent on comparator performance, but is worthwhile here.)

 final Entry<K, V> getFirstEntry() 
{
        Entry< K,V > p = root;
        if (p != null)
            while (p.left != null)
                p = p.left;
        return p;
}

Returns the first Entry in the TreeMap (according to the TreeMap's key-sort function). Returns null if the TreeMap is empty.

 final Entry<K, V> getFloorEntry(K key) 
{
        Entry< K,V > p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            if (cmp  > 0) {
                if (p.right != null)
                    p = p.right;
                else
                    return p;
            } else if (cmp <  0) {
                if (p.left != null) {
                    p = p.left;
                } else {
                    Entry< K,V > parent = p.parent;
                    Entry< K,V > ch = p;
                    while (parent != null && ch == parent.left) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            } else
                return p;
        }
        return null;
}

Gets the entry corresponding to the specified key; if no such entry exists, returns the entry for the greatest key less than the specified key; if no such entry exists, returns {@code null}.

 final Entry<K, V> getHigherEntry(K key) 
{
        Entry< K,V > p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            if (cmp <  0) {
                if (p.left != null)
                    p = p.left;
                else
                    return p;
            } else {
                if (p.right != null) {
                    p = p.right;
                } else {
                    Entry< K,V > parent = p.parent;
                    Entry< K,V > ch = p;
                    while (parent != null && ch == parent.right) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            }
        }
        return null;
}

Gets the entry for the least key greater than the specified key; if no such entry exists, returns the entry for the least key greater than the specified key; if no such entry exists returns {@code null}.

 final Entry<K, V> getLastEntry() 
{
        Entry< K,V > p = root;
        if (p != null)
            while (p.right != null)
                p = p.right;
        return p;
}

Returns the last Entry in the TreeMap (according to the TreeMap's key-sort function). Returns null if the TreeMap is empty.

 final Entry<K, V> getLowerEntry(K key) 
{
        Entry< K,V > p = root;
        while (p != null) {
            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< K,V > parent = p.parent;
                    Entry< K,V > ch = p;
                    while (parent != null && ch == parent.left) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            }
        }
        return null;
}

Returns the entry for the greatest key less than the specified key; if no such entry exists (i.e., the least key in the Tree is greater than the specified key), returns {@code null}.

 public SortedMap<K, V> headMap(K toKey) 
{
        return headMap(toKey, false);
}

 public NavigableMap<K, V> headMap(K toKey,
    boolean inclusive) 
{
        return new AscendingSubMap(this,
                                   true,  null,  true,
                                   false, toKey, inclusive);
}

 public Entry<K, V> higherEntry(K key) 
{
        return exportEntry(getHigherEntry(key));
}

 public K higherKey(K key) 
{
        return keyOrNull(getHigherEntry(key));
}

 static K key(Entry<K, ?> e) 
{
        if (e==null)
            throw new NoSuchElementException();
        return e.key;
}

Returns the key corresponding to the specified Entry.

 Iterator<K> keyIterator() 
{
        return new KeyIterator(getFirstEntry());
}

 static K keyOrNull(Entry<K, V> e) 
{
        return (e == null) ? null : e.key;
}

Return key for entry, or null if null

 public Set<K> keySet() 
{
        return navigableKeySet();
}

Returns a Set view of the keys contained in this map. The set's iterator returns the keys in ascending order. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own {@code remove} operation), the results of the iteration are undefined. The set supports element removal, which removes the corresponding mapping from the map, via the {@code Iterator.remove}, {@code Set.remove}, {@code removeAll}, {@code retainAll}, and {@code clear} operations. It does not support the {@code add} or {@code addAll} operations.

 public Entry<K, V> lastEntry() 
{
        return exportEntry(getLastEntry());
}

 public K lastKey() 
{
        return key(getLastEntry());
}

 public Entry<K, V> lowerEntry(K key) 
{
        return exportEntry(getLowerEntry(key));
}

 public K lowerKey(K key) 
{
        return keyOrNull(getLowerEntry(key));
}

 public NavigableSet<K> navigableKeySet() 
{
        KeySet< K > nks = navigableKeySet;
        return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
}

 public Entry<K, V> pollFirstEntry() 
{
        Entry< K,V > p = getFirstEntry();
        Map.Entry< K,V > result = exportEntry(p);
        if (p != null)
            deleteEntry(p);
        return result;
}

 public Entry<K, V> pollLastEntry() 
{
        Entry< K,V > p = getLastEntry();
        Map.Entry< K,V > result = exportEntry(p);
        if (p != null)
            deleteEntry(p);
        return result;
}

 static Entry<K, V> predecessor(Entry<K, V> t) 
{
        if (t == null)
            return null;
        else if (t.left != null) {
            Entry< K,V > p = t.left;
            while (p.right != null)
                p = p.right;
            return p;
        } else {
            Entry< K,V > p = t.parent;
            Entry< K,V > ch = t;
            while (p != null && ch == p.left) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
}

Returns the predecessor of the specified Entry, or null if no such.

 public V put(K key,
    V value) 
{
        Entry< K,V > t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check
            root = new Entry<  >(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry< K,V > parent;
        // split comparator and comparable paths
        Comparator< ? super K > cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp <  0)
                    t = t.left;
                else if (cmp  > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            Comparable< ? super K > k = (Comparable< ? super K >) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp <  0)
                    t = t.left;
                else if (cmp  > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry< K,V > e = new Entry<  >(key, value, parent);
        if (cmp <  0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
}

Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.

 public  void putAll(Map<? extends K, ? extends V> map) 
{
        int mapSize = map.size();
        if (size==0 && mapSize!=0 && map instanceof SortedMap) {
            Comparator c = ((SortedMap)map).comparator();
            if (c == comparator || (c != null && c.equals(comparator))) {
                ++modCount;
                try {
                    buildFromSorted(mapSize, map.entrySet().iterator(),
                                    null, null);
                } catch (java.io.IOException cannotHappen) {
                } catch (ClassNotFoundException cannotHappen) {
                }
                return;
            }
        }
        super.putAll(map);
}

Copies all of the mappings from the specified map to this map. These mappings replace any mappings that this map had for any of the keys currently in the specified map.

  void readTreeSet(int size,
    ObjectInputStream s,
    V defaultVal) throws IOException, ClassNotFoundException 
{
        buildFromSorted(size, null, s, defaultVal);
}

Intended to be called only from TreeSet.readObject

 public V remove(Object key) 
{
        Entry< K,V > p = getEntry(key);
        if (p == null)
            return null;
        V oldValue = p.value;
        deleteEntry(p);
        return oldValue;
}

Removes the mapping for this key from this TreeMap if present.

 public int size() 
{
        return size;
}

Returns the number of key-value mappings in this map.

 public SortedMap<K, V> subMap(K fromKey,
    K toKey) 
{
        return subMap(fromKey, true, toKey, false);
}

 public NavigableMap<K, V> subMap(K fromKey,
    boolean fromInclusive,
    K toKey,
    boolean toInclusive) 
{
        return new AscendingSubMap(this,
                                   false, fromKey, fromInclusive,
                                   false, toKey,   toInclusive);
}

 static Entry<K, V> successor(Entry<K, V> t) 
{
        if (t == null)
            return null;
        else if (t.right != null) {
            Entry< K,V > p = t.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else {
            Entry< K,V > p = t.parent;
            Entry< K,V > ch = t;
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
}

Returns the successor of the specified Entry, or null if no such.

 public SortedMap<K, V> tailMap(K fromKey) 
{
        return tailMap(fromKey, true);
}

 public NavigableMap<K, V> tailMap(K fromKey,
    boolean inclusive) 
{
        return new AscendingSubMap(this,
                                   false, fromKey, inclusive,
                                   true,  null,    true);
}

 static final boolean valEquals(Object o1,
    Object o2) 
{
        return (o1==null ? o2==null : o1.equals(o2));
}

Test two values for equality. Differs from o1.equals(o2) only in that it copes with {@code null} o1 properly.

 public Collection<V> values() 
{
        Collection< V > vs = values;
        return (vs != null) ? vs : (values = new Values());
}

Returns a Collection view of the values contained in this map. The collection's iterator returns the values in ascending order of the corresponding keys. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. If the map is modified while an iteration over the collection is in progress (except through the iterator's own {@code remove} operation), the results of the iteration are undefined. The collection supports element removal, which removes the corresponding mapping from the map, via the {@code Iterator.remove}, {@code Collection.remove}, {@code removeAll}, {@code retainAll} and {@code clear} operations. It does not support the {@code add} or {@code addAll} operations.