* For 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 strictly     * greater than <tt>low</tt>: <pre>     *     SortedMap tail = m.tailMap(low+"\0");     * </pre>     *     * @param fromKey low endpoint (inclusive) of the tailMap.     * @return a view of the portion of this map whose keys are greater     *                than or equal to <tt>fromKey</tt>.     * @throws ClassCastException if <tt>fromKey</tt> is not compatible     *         with this map's comparator (or, if the map has no comparator,     *         if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).     * @throws IllegalArgumentException if this map is itself a subMap,     *         headMap, or tailMap, and <tt>fromKey</tt> is not within the     *         specified range of the subMap, headMap, or tailMap.     * @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and     *               this map uses natural order, or its comparator does not     *               tolerate <tt>null</tt> keys.     */    public SortedMap tailMap(Object fromKey) {        return new SubMap(fromKey, false);    }    private class SubMap extends AbstractMap                             implements SortedMap, java.io.Serializable {        private static final long serialVersionUID = -6520786458950516097L;        /**         * fromKey is significant only if fromStart is false.  Similarly,         * toKey is significant only if toStart is false.         */        private boolean fromStart = false, toEnd = false;        private Object  fromKey,           toKey;        SubMap(Object fromKey, Object toKey) {            if (compare(fromKey, toKey) > 0)                throw new IllegalArgumentException("fromKey > toKey");            this.fromKey = fromKey;            this.toKey = toKey;        }        SubMap(Object key, boolean headMap) {            compare(key, key); // Type-check key            if (headMap) {                fromStart = true;                toKey = key;            } else {                toEnd = true;                fromKey = key;            }        }        SubMap(boolean fromStart, Object fromKey, boolean toEnd, Object toKey){            this.fromStart = fromStart;            this.fromKey= fromKey;            this.toEnd = toEnd;            this.toKey = toKey;        }        public boolean isEmpty() {            return entrySet.isEmpty();        }        public boolean containsKey(Object key) {            return inRange(key) && TreeMap.this.containsKey(key);        }        public Object get(Object key) {            if (!inRange(key))                return null;            return TreeMap.this.get(key);        }        public Object put(Object key, Object value) {            if (!inRange(key))                throw new IllegalArgumentException("key out of range");            return TreeMap.this.put(key, value);        }        public Comparator comparator() {            return comparator;        }        public Object firstKey() {            Object first = key(fromStart ? firstEntry():getCeilEntry(fromKey));            if (!toEnd && compare(first, toKey) >= 0)                throw(new NoSuchElementException());            return first;        }        public Object lastKey() {            Object last = key(toEnd ? lastEntry() : getPrecedingEntry(toKey));            if (!fromStart && compare(last, fromKey) < 0)                throw(new NoSuchElementException());            return last;        }        private transient Set entrySet = new EntrySetView();        public Set entrySet() {            return entrySet;        }        private class EntrySetView extends AbstractSet {            private transient int size = -1, sizeModCount;            public int size() {                if (size == -1 || sizeModCount != TreeMap.this.modCount) {                    size = 0;  sizeModCount = TreeMap.this.modCount;                    Iterator i = iterator();                    while (i.hasNext()) {                        size++;                        i.next();                    }                }                return size;            }            public boolean isEmpty() {                return !iterator().hasNext();            }            public boolean contains(Object o) {                if (!(o instanceof Map.Entry))                    return false;                Map.Entry entry = (Map.Entry)o;                Object key = entry.getKey();                if (!inRange(key))                    return false;                TreeMap.Entry node = getEntry(key);                return node != null &&                       valEquals(node.getValue(), entry.getValue());            }            public boolean remove(Object o) {                if (!(o instanceof Map.Entry))                    return false;                Map.Entry entry = (Map.Entry)o;                Object key = entry.getKey();                if (!inRange(key))                    return false;                TreeMap.Entry node = getEntry(key);                if (node!=null && valEquals(node.getValue(),entry.getValue())){                    deleteEntry(node);                    return true;                }                return false;            }            public Iterator iterator() {                return new SubMapEntryIterator(                    (fromStart ? firstEntry() : getCeilEntry(fromKey)),                    (toEnd     ? null         : getCeilEntry(toKey)));            }        }        public SortedMap subMap(Object fromKey, Object toKey) {            if (!inRange2(fromKey))                throw new IllegalArgumentException("fromKey out of range");            if (!inRange2(toKey))                throw new IllegalArgumentException("toKey out of range");            return new SubMap(fromKey, toKey);        }        public SortedMap headMap(Object toKey) {            if (!inRange2(toKey))                throw new IllegalArgumentException("toKey out of range");            return new SubMap(fromStart, fromKey, false, toKey);        }        public SortedMap tailMap(Object fromKey) {            if (!inRange2(fromKey))                throw new IllegalArgumentException("fromKey out of range");            return new SubMap(false, fromKey, toEnd, toKey);        }        private boolean inRange(Object key) {            return (fromStart || compare(key, fromKey) >= 0) &&                   (toEnd     || compare(key, toKey)   <  0);        }        // This form allows the high endpoint (as well as all legit keys)        private boolean inRange2(Object key) {            return (fromStart || compare(key, fromKey) >= 0) &&                   (toEnd     || compare(key, toKey)   <= 0);        }    }    /**     * TreeMap Iterator.     */    private class EntryIterator implements Iterator {        private int expectedModCount = TreeMap.this.modCount;        private Entry lastReturned = null;        Entry next;        EntryIterator() {            next = firstEntry();        }        // Used by SubMapEntryIterator        EntryIterator(Entry first) {            next = first;        }        public boolean hasNext() {            return next != null;        }        final Entry nextEntry() {            if (next == null)                throw new NoSuchElementException();            if (modCount != expectedModCount)                throw new ConcurrentModificationException();            lastReturned = next;            next = successor(next);            return lastReturned;        }        public Object next() {            return nextEntry();        }        public void remove() {            if (lastReturned == null)                throw new IllegalStateException();            if (modCount != expectedModCount)                throw new ConcurrentModificationException();            if (lastReturned.left != null && lastReturned.right != null)                 next = lastReturned;             deleteEntry(lastReturned);            expectedModCount++;            lastReturned = null;        }    }    private class KeyIterator extends EntryIterator {        public Object next() {            return nextEntry().key;        }    }    private class ValueIterator extends EntryIterator {        public Object next() {            return nextEntry().value;        }    }    private class SubMapEntryIterator extends EntryIterator {        private final Object firstExcludedKey;        SubMapEntryIterator(Entry first, Entry firstExcluded) {            super(first);            firstExcludedKey = (firstExcluded == null ?                                firstExcluded : firstExcluded.key);        }        public boolean hasNext() {            return next != null && next.key != firstExcludedKey;        }        public Object next() {            if (next == null || next.key == firstExcludedKey)                throw new NoSuchElementException();            return nextEntry();        }    }    /**     * Compares two keys using the correct comparison method for this TreeMap.     */    private int compare(Object k1, Object k2) {        return (comparator==null ? ((Comparable)k1).compareTo(k2)                                 : comparator.compare(k1, k2));    }    /**     * Test two values  for equality.  Differs from o1.equals(o2) only in     * that it copes with with <tt>null</tt> o1 properly.     */    private static boolean valEquals(Object o1, Object o2) {        return (o1==null ? o2==null : o1.equals(o2));    }    private static final boolean RED   = false;    private static final boolean BLACK = true;    /**     * Node in the Tree.  Doubles as a means to pass key-value pairs back to     * user (see Map.Entry).     */    static class Entry implements Map.Entry {        Object key;        Object value;        Entry left = null;        Entry right = null;        Entry parent;        boolean color = BLACK;        /**         * Make a new cell with given key, value, and parent, and with          * <tt>null</tt> child links, and BLACK color.          */        Entry(Object key, Object value, Entry parent) {             this.key = key;            this.value = value;            this.parent = parent;        }        /**         * Returns the key.         *         * @return the key.         */        public Object getKey() {             return key;         }        /**         * Returns the value associated with the key.         *         * @return the value associated with the key.         */        public Object getValue() {            return value;        }        /**         * Replaces the value currently associated with the key with the given         * value.         *         * @return the value associated with the key before this method was         *           called.         */        public Object setValue(Object value) {            Object oldValue = this.value;            this.value = value;            return oldValue;        }        public boolean equals(Object o) {            if (!(o instanceof Map.Entry))                return false;            Map.Entry e = (Map.Entry)o;            return valEquals(key,e.getKey()) && valEquals(value,e.getValue());        }        public int hashCode() {            int keyHash = (key==null ? 0 : key.hashCode());            int valueHash = (value==null ? 0 : value.hashCode());            return keyHash ^ valueHash;        }        public String toString() {            return key + "=" + value;        }    }    /**     * Returns the first Entry in the TreeMap (according to the TreeMap's     * key-sort function).  Returns null if the TreeMap is empty.     */    private Entry firstEntry() {        Entry p = root;        if (p != null)            while (p.left != null)                p = p.left;        return p;    }    /**     * Returns the last Entry in the TreeMap (according to the TreeMap's     * key-sort function).  Returns null if the TreeMap is empty.     */    private Entry lastEntry() {        Entry p = root;        if (p != null)            while (p.right != null)                p = p.right;        return p;    }    /**     * Returns the successor of the specified Entry, or null if no such.     */    private Entry successor(Entry t) {        if (t == null)            return null;        else if (t.right != null) {            Entry p = t.right;            while (p.left != null)                p = p.left;            return p;        } else {            Entry p = t.parent;            Entry ch = t;            while (p != null && ch == p.right) {                ch = p;                p = p.parent;            }            return p;        }    }    /**     * Balancing operations.     *     * Implementations of rebalancings during insertion and deletion are     * slightly different than the CLR version.  Rather than using dummy     * nilnodes, we use a set of accessors that deal properly with null.  They     * are used to avoid messiness surrounding nullness checks in the main