001    /* TreeMap.java -- a class providing a basic Red-Black Tree data structure,
002       mapping Object --> Object
003       Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006  Free Software Foundation, Inc.
004    
005    This file is part of GNU Classpath.
006    
007    GNU Classpath is free software; you can redistribute it and/or modify
008    it under the terms of the GNU General Public License as published by
009    the Free Software Foundation; either version 2, or (at your option)
010    any later version.
011    
012    GNU Classpath is distributed in the hope that it will be useful, but
013    WITHOUT ANY WARRANTY; without even the implied warranty of
014    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
015    General Public License for more details.
016    
017    You should have received a copy of the GNU General Public License
018    along with GNU Classpath; see the file COPYING.  If not, write to the
019    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
020    02110-1301 USA.
021    
022    Linking this library statically or dynamically with other modules is
023    making a combined work based on this library.  Thus, the terms and
024    conditions of the GNU General Public License cover the whole
025    combination.
026    
027    As a special exception, the copyright holders of this library give you
028    permission to link this library with independent modules to produce an
029    executable, regardless of the license terms of these independent
030    modules, and to copy and distribute the resulting executable under
031    terms of your choice, provided that you also meet, for each linked
032    independent module, the terms and conditions of the license of that
033    module.  An independent module is a module which is not derived from
034    or based on this library.  If you modify this library, you may extend
035    this exception to your version of the library, but you are not
036    obligated to do so.  If you do not wish to do so, delete this
037    exception statement from your version. */
038    
039    
040    package java.util;
041    
042    import gnu.java.lang.CPStringBuilder;
043    
044    import java.io.IOException;
045    import java.io.ObjectInputStream;
046    import java.io.ObjectOutputStream;
047    import java.io.Serializable;
048    
049    /**
050     * This class provides a red-black tree implementation of the SortedMap
051     * interface.  Elements in the Map will be sorted by either a user-provided
052     * Comparator object, or by the natural ordering of the keys.
053     *
054     * The algorithms are adopted from Corman, Leiserson, and Rivest's
055     * <i>Introduction to Algorithms.</i>  TreeMap guarantees O(log n)
056     * insertion and deletion of elements.  That being said, there is a large
057     * enough constant coefficient in front of that "log n" (overhead involved
058     * in keeping the tree balanced), that TreeMap may not be the best choice
059     * for small collections. If something is already sorted, you may want to
060     * just use a LinkedHashMap to maintain the order while providing O(1) access.
061     *
062     * TreeMap is a part of the JDK1.2 Collections API.  Null keys are allowed
063     * only if a Comparator is used which can deal with them; natural ordering
064     * cannot cope with null.  Null values are always allowed. Note that the
065     * ordering must be <i>consistent with equals</i> to correctly implement
066     * the Map interface. If this condition is violated, the map is still
067     * well-behaved, but you may have suprising results when comparing it to
068     * other maps.<p>
069     *
070     * This implementation is not synchronized. If you need to share this between
071     * multiple threads, do something like:<br>
072     * <code>SortedMap m
073     *       = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
074     *
075     * The iterators are <i>fail-fast</i>, meaning that any structural
076     * modification, except for <code>remove()</code> called on the iterator
077     * itself, cause the iterator to throw a
078     * <code>ConcurrentModificationException</code> rather than exhibit
079     * non-deterministic behavior.
080     *
081     * @author Jon Zeppieri
082     * @author Bryce McKinlay
083     * @author Eric Blake (ebb9@email.byu.edu)
084     * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
085     * @see Map
086     * @see HashMap
087     * @see Hashtable
088     * @see LinkedHashMap
089     * @see Comparable
090     * @see Comparator
091     * @see Collection
092     * @see Collections#synchronizedSortedMap(SortedMap)
093     * @since 1.2
094     * @status updated to 1.6
095     */
096    public class TreeMap<K, V> extends AbstractMap<K, V>
097      implements NavigableMap<K, V>, Cloneable, Serializable
098    {
099      // Implementation note:
100      // A red-black tree is a binary search tree with the additional properties
101      // that all paths to a leaf node visit the same number of black nodes,
102      // and no red node has red children. To avoid some null-pointer checks,
103      // we use the special node nil which is always black, has no relatives,
104      // and has key and value of null (but is not equal to a mapping of null).
105    
106      /**
107       * Compatible with JDK 1.2.
108       */
109      private static final long serialVersionUID = 919286545866124006L;
110    
111      /**
112       * Color status of a node. Package visible for use by nested classes.
113       */
114      static final int RED = -1,
115                       BLACK = 1;
116    
117      /**
118       * Sentinal node, used to avoid null checks for corner cases and make the
119       * delete rebalance code simpler. The rebalance code must never assign
120       * the parent, left, or right of nil, but may safely reassign the color
121       * to be black. This object must never be used as a key in a TreeMap, or
122       * it will break bounds checking of a SubMap.
123       */
124      static final Node nil = new Node(null, null, BLACK);
125      static
126        {
127          // Nil is self-referential, so we must initialize it after creation.
128          nil.parent = nil;
129          nil.left = nil;
130          nil.right = nil;
131        }
132    
133      /**
134       * The root node of this TreeMap.
135       */
136      private transient Node root;
137    
138      /**
139       * The size of this TreeMap. Package visible for use by nested classes.
140       */
141      transient int size;
142    
143      /**
144       * The cache for {@link #entrySet()}.
145       */
146      private transient Set<Map.Entry<K,V>> entries;
147    
148      /**
149       * The cache for {@link #descendingMap()}.
150       */
151      private transient NavigableMap<K,V> descendingMap;
152    
153      /**
154       * The cache for {@link #navigableKeySet()}.
155       */
156      private transient NavigableSet<K> nKeys;
157    
158      /**
159       * Counts the number of modifications this TreeMap has undergone, used
160       * by Iterators to know when to throw ConcurrentModificationExceptions.
161       * Package visible for use by nested classes.
162       */
163      transient int modCount;
164    
165      /**
166       * This TreeMap's comparator, or null for natural ordering.
167       * Package visible for use by nested classes.
168       * @serial the comparator ordering this tree, or null
169       */
170      final Comparator<? super K> comparator;
171    
172      /**
173       * Class to represent an entry in the tree. Holds a single key-value pair,
174       * plus pointers to parent and child nodes.
175       *
176       * @author Eric Blake (ebb9@email.byu.edu)
177       */
178      private static final class Node<K, V> extends AbstractMap.SimpleEntry<K, V>
179      {
180        // All fields package visible for use by nested classes.
181        /** The color of this node. */
182        int color;
183    
184        /** The left child node. */
185        Node<K, V> left = nil;
186        /** The right child node. */
187        Node<K, V> right = nil;
188        /** The parent node. */
189        Node<K, V> parent = nil;
190    
191        /**
192         * Simple constructor.
193         * @param key the key
194         * @param value the value
195         */
196        Node(K key, V value, int color)
197        {
198          super(key, value);
199          this.color = color;
200        }
201      }
202    
203      /**
204       * Instantiate a new TreeMap with no elements, using the keys' natural
205       * ordering to sort. All entries in the map must have a key which implements
206       * Comparable, and which are <i>mutually comparable</i>, otherwise map
207       * operations may throw a {@link ClassCastException}. Attempts to use
208       * a null key will throw a {@link NullPointerException}.
209       *
210       * @see Comparable
211       */
212      public TreeMap()
213      {
214        this((Comparator) null);
215      }
216    
217      /**
218       * Instantiate a new TreeMap with no elements, using the provided comparator
219       * to sort. All entries in the map must have keys which are mutually
220       * comparable by the Comparator, otherwise map operations may throw a
221       * {@link ClassCastException}.
222       *
223       * @param c the sort order for the keys of this map, or null
224       *        for the natural order
225       */
226      public TreeMap(Comparator<? super K> c)
227      {
228        comparator = c;
229        fabricateTree(0);
230      }
231    
232      /**
233       * Instantiate a new TreeMap, initializing it with all of the elements in
234       * the provided Map.  The elements will be sorted using the natural
235       * ordering of the keys. This algorithm runs in n*log(n) time. All entries
236       * in the map must have keys which implement Comparable and are mutually
237       * comparable, otherwise map operations may throw a
238       * {@link ClassCastException}.
239       *
240       * @param map a Map, whose entries will be put into this TreeMap
241       * @throws ClassCastException if the keys in the provided Map are not
242       *         comparable
243       * @throws NullPointerException if map is null
244       * @see Comparable
245       */
246      public TreeMap(Map<? extends K, ? extends V> map)
247      {
248        this((Comparator) null);
249        putAll(map);
250      }
251    
252      /**
253       * Instantiate a new TreeMap, initializing it with all of the elements in
254       * the provided SortedMap.  The elements will be sorted using the same
255       * comparator as in the provided SortedMap. This runs in linear time.
256       *
257       * @param sm a SortedMap, whose entries will be put into this TreeMap
258       * @throws NullPointerException if sm is null
259       */
260      public TreeMap(SortedMap<K, ? extends V> sm)
261      {
262        this(sm.comparator());
263        int pos = sm.size();
264        Iterator itr = sm.entrySet().iterator();
265    
266        fabricateTree(pos);
267        Node node = firstNode();
268    
269        while (--pos >= 0)
270          {
271            Map.Entry me = (Map.Entry) itr.next();
272            node.key = me.getKey();
273            node.value = me.getValue();
274            node = successor(node);
275          }
276      }
277    
278      /**
279       * Clears the Map so it has no keys. This is O(1).
280       */
281      public void clear()
282      {
283        if (size > 0)
284          {
285            modCount++;
286            root = nil;
287            size = 0;
288          }
289      }
290    
291      /**
292       * Returns a shallow clone of this TreeMap. The Map itself is cloned,
293       * but its contents are not.
294       *
295       * @return the clone
296       */
297      public Object clone()
298      {
299        TreeMap copy = null;
300        try
301          {
302            copy = (TreeMap) super.clone();
303          }
304        catch (CloneNotSupportedException x)
305          {
306          }
307        copy.entries = null;
308        copy.fabricateTree(size);
309    
310        Node node = firstNode();
311        Node cnode = copy.firstNode();
312    
313        while (node != nil)
314          {
315            cnode.key = node.key;
316            cnode.value = node.value;
317            node = successor(node);
318            cnode = copy.successor(cnode);
319          }
320        return copy;
321      }
322    
323      /**
324       * Return the comparator used to sort this map, or null if it is by
325       * natural order.
326       *
327       * @return the map's comparator
328       */
329      public Comparator<? super K> comparator()
330      {
331        return comparator;
332      }
333    
334      /**
335       * Returns true if the map contains a mapping for the given key.
336       *
337       * @param key the key to look for
338       * @return true if the key has a mapping
339       * @throws ClassCastException if key is not comparable to map elements
340       * @throws NullPointerException if key is null and the comparator is not
341       *         tolerant of nulls
342       */
343      public boolean containsKey(Object key)
344      {
345        return getNode((K) key) != nil;
346      }
347    
348      /**
349       * Returns true if the map contains at least one mapping to the given value.
350       * This requires linear time.
351       *
352       * @param value the value to look for
353       * @return true if the value appears in a mapping
354       */
355      public boolean containsValue(Object value)
356      {
357        Node node = firstNode();
358        while (node != nil)
359          {
360            if (equals(value, node.value))
361              return true;
362            node = successor(node);
363          }
364        return false;
365      }
366    
367      /**
368       * Returns a "set view" of this TreeMap's entries. The set is backed by
369       * the TreeMap, so changes in one show up in the other.  The set supports
370       * element removal, but not element addition.<p>
371       *
372       * Note that the iterators for all three views, from keySet(), entrySet(),
373       * and values(), traverse the TreeMap in sorted sequence.
374       *
375       * @return a set view of the entries
376       * @see #keySet()
377       * @see #values()
378       * @see Map.Entry
379       */
380      public Set<Map.Entry<K,V>> entrySet()
381      {
382        if (entries == null)
383          // Create an AbstractSet with custom implementations of those methods
384          // that can be overriden easily and efficiently.
385          entries = new NavigableEntrySet();
386        return entries;
387      }
388    
389      /**
390       * Returns the first (lowest) key in the map.
391       *
392       * @return the first key
393       * @throws NoSuchElementException if the map is empty
394       */
395      public K firstKey()
396      {
397        if (root == nil)
398          throw new NoSuchElementException();
399        return firstNode().key;
400      }
401    
402      /**
403       * Return the value in this TreeMap associated with the supplied key,
404       * or <code>null</code> if the key maps to nothing.  NOTE: Since the value
405       * could also be null, you must use containsKey to see if this key
406       * actually maps to something.
407       *
408       * @param key the key for which to fetch an associated value
409       * @return what the key maps to, if present
410       * @throws ClassCastException if key is not comparable to elements in the map
411       * @throws NullPointerException if key is null but the comparator does not
412       *         tolerate nulls
413       * @see #put(Object, Object)
414       * @see #containsKey(Object)
415       */
416      public V get(Object key)
417      {
418        // Exploit fact that nil.value == null.
419        return getNode((K) key).value;
420      }
421    
422      /**
423       * Returns a view of this Map including all entries with keys less than
424       * <code>toKey</code>. The returned map is backed by the original, so changes
425       * in one appear in the other. The submap will throw an
426       * {@link IllegalArgumentException} for any attempt to access or add an
427       * element beyond the specified cutoff. The returned map does not include
428       * the endpoint; if you want inclusion, pass the successor element
429       * or call <code>headMap(toKey, true)</code>.  This is equivalent to
430       * calling <code>headMap(toKey, false)</code>.
431       *
432       * @param toKey the (exclusive) cutoff point
433       * @return a view of the map less than the cutoff
434       * @throws ClassCastException if <code>toKey</code> is not compatible with
435       *         the comparator (or is not Comparable, for natural ordering)
436       * @throws NullPointerException if toKey is null, but the comparator does not
437       *         tolerate null elements
438       */
439      public SortedMap<K, V> headMap(K toKey)
440      {
441        return headMap(toKey, false);
442      }
443    
444      /**
445       * Returns a view of this Map including all entries with keys less than
446       * (or equal to, if <code>inclusive</code> is true) <code>toKey</code>.
447       * The returned map is backed by the original, so changes in one appear
448       * in the other. The submap will throw an {@link IllegalArgumentException}
449       * for any attempt to access or add an element beyond the specified cutoff.
450       *
451       * @param toKey the cutoff point
452       * @param inclusive true if the cutoff point should be included.
453       * @return a view of the map less than (or equal to, if <code>inclusive</code>
454       *         is true) the cutoff.
455       * @throws ClassCastException if <code>toKey</code> is not compatible with
456       *         the comparator (or is not Comparable, for natural ordering)
457       * @throws NullPointerException if toKey is null, but the comparator does not
458       *         tolerate null elements
459       */
460      public NavigableMap<K, V> headMap(K toKey, boolean inclusive)
461      {
462        return new SubMap((K)(Object)nil, inclusive
463                          ? successor(getNode(toKey)).key : toKey);
464      }
465    
466      /**
467       * Returns a "set view" of this TreeMap's keys. The set is backed by the
468       * TreeMap, so changes in one show up in the other.  The set supports
469       * element removal, but not element addition.
470       *
471       * @return a set view of the keys
472       * @see #values()
473       * @see #entrySet()
474       */
475      public Set<K> keySet()
476      {
477        if (keys == null)
478          // Create an AbstractSet with custom implementations of those methods
479          // that can be overriden easily and efficiently.
480          keys = new KeySet();
481        return keys;
482      }
483    
484      /**
485       * Returns the last (highest) key in the map.
486       *
487       * @return the last key
488       * @throws NoSuchElementException if the map is empty
489       */
490      public K lastKey()
491      {
492        if (root == nil)
493          throw new NoSuchElementException("empty");
494        return lastNode().key;
495      }
496    
497      /**
498       * Puts the supplied value into the Map, mapped by the supplied key.
499       * The value may be retrieved by any object which <code>equals()</code>
500       * this key. NOTE: Since the prior value could also be null, you must
501       * first use containsKey if you want to see if you are replacing the
502       * key's mapping.
503       *
504       * @param key the key used to locate the value
505       * @param value the value to be stored in the Map
506       * @return the prior mapping of the key, or null if there was none
507       * @throws ClassCastException if key is not comparable to current map keys
508       * @throws NullPointerException if key is null, but the comparator does
509       *         not tolerate nulls
510       * @see #get(Object)
511       * @see Object#equals(Object)
512       */
513      public V put(K key, V value)
514      {
515        Node<K,V> current = root;
516        Node<K,V> parent = nil;
517        int comparison = 0;
518    
519        // Find new node's parent.
520        while (current != nil)
521          {
522            parent = current;
523            comparison = compare(key, current.key);
524            if (comparison > 0)
525              current = current.right;
526            else if (comparison < 0)
527              current = current.left;
528            else // Key already in tree.
529              return current.setValue(value);
530          }
531    
532        // Set up new node.
533        Node n = new Node(key, value, RED);
534        n.parent = parent;
535    
536        // Insert node in tree.
537        modCount++;
538        size++;
539        if (parent == nil)
540          {
541            // Special case inserting into an empty tree.
542            root = n;
543            return null;
544          }
545        if (comparison > 0)
546          parent.right = n;
547        else
548          parent.left = n;
549    
550        // Rebalance after insert.
551        insertFixup(n);
552        return null;
553      }
554    
555      /**
556       * Copies all elements of the given map into this TreeMap.  If this map
557       * already has a mapping for a key, the new mapping replaces the current
558       * one.
559       *
560       * @param m the map to be added
561       * @throws ClassCastException if a key in m is not comparable with keys
562       *         in the map
563       * @throws NullPointerException if a key in m is null, and the comparator
564       *         does not tolerate nulls
565       */
566      public void putAll(Map<? extends K, ? extends V> m)
567      {
568        Iterator itr = m.entrySet().iterator();
569        int pos = m.size();
570        while (--pos >= 0)
571          {
572            Map.Entry<K,V> e = (Map.Entry<K,V>) itr.next();
573            put(e.getKey(), e.getValue());
574          }
575      }
576    
577      /**
578       * Removes from the TreeMap and returns the value which is mapped by the
579       * supplied key. If the key maps to nothing, then the TreeMap remains
580       * unchanged, and <code>null</code> is returned. NOTE: Since the value
581       * could also be null, you must use containsKey to see if you are
582       * actually removing a mapping.
583       *
584       * @param key the key used to locate the value to remove
585       * @return whatever the key mapped to, if present
586       * @throws ClassCastException if key is not comparable to current map keys
587       * @throws NullPointerException if key is null, but the comparator does
588       *         not tolerate nulls
589       */
590      public V remove(Object key)
591      {
592        Node<K, V> n = getNode((K)key);
593        if (n == nil)
594          return null;
595        // Note: removeNode can alter the contents of n, so save value now.
596        V result = n.value;
597        removeNode(n);
598        return result;
599      }
600    
601      /**
602       * Returns the number of key-value mappings currently in this Map.
603       *
604       * @return the size
605       */
606      public int size()
607      {
608        return size;
609      }
610    
611      /**
612       * Returns a view of this Map including all entries with keys greater or
613       * equal to <code>fromKey</code> and less than <code>toKey</code> (a
614       * half-open interval). The returned map is backed by the original, so
615       * changes in one appear in the other. The submap will throw an
616       * {@link IllegalArgumentException} for any attempt to access or add an
617       * element beyond the specified cutoffs. The returned map includes the low
618       * endpoint but not the high; if you want to reverse this behavior on
619       * either end, pass in the successor element or call
620       * {@link #subMap(K,boolean,K,boolean)}.  This call is equivalent to
621       * <code>subMap(fromKey, true, toKey, false)</code>.
622       *
623       * @param fromKey the (inclusive) low cutoff point
624       * @param toKey the (exclusive) high cutoff point
625       * @return a view of the map between the cutoffs
626       * @throws ClassCastException if either cutoff is not compatible with
627       *         the comparator (or is not Comparable, for natural ordering)
628       * @throws NullPointerException if fromKey or toKey is null, but the
629       *         comparator does not tolerate null elements
630       * @throws IllegalArgumentException if fromKey is greater than toKey
631       */
632      public SortedMap<K, V> subMap(K fromKey, K toKey)
633      {
634        return subMap(fromKey, true, toKey, false);
635      }
636    
637      /**
638       * Returns a view of this Map including all entries with keys greater (or
639       * equal to, if <code>fromInclusive</code> is true) <code>fromKey</code> and
640       * less than (or equal to, if <code>toInclusive</code> is true)
641       * <code>toKey</code>. The returned map is backed by the original, so
642       * changes in one appear in the other. The submap will throw an
643       * {@link IllegalArgumentException} for any attempt to access or add an
644       * element beyond the specified cutoffs.
645       *
646       * @param fromKey the low cutoff point
647       * @param fromInclusive true if the low cutoff point should be included.
648       * @param toKey the high cutoff point
649       * @param toInclusive true if the high cutoff point should be included.
650       * @return a view of the map for the specified range.
651       * @throws ClassCastException if either cutoff is not compatible with
652       *         the comparator (or is not Comparable, for natural ordering)
653       * @throws NullPointerException if fromKey or toKey is null, but the
654       *         comparator does not tolerate null elements
655       * @throws IllegalArgumentException if fromKey is greater than toKey
656       */
657      public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive,
658                                       K toKey, boolean toInclusive)
659      {
660        return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key,
661                          toInclusive ? successor(getNode(toKey)).key : toKey);
662      }
663    
664      /**
665       * Returns a view of this Map including all entries with keys greater or
666       * equal to <code>fromKey</code>. The returned map is backed by the
667       * original, so changes in one appear in the other. The submap will throw an
668       * {@link IllegalArgumentException} for any attempt to access or add an
669       * element beyond the specified cutoff. The returned map includes the
670       * endpoint; if you want to exclude it, pass in the successor element.
671       * This is equivalent to calling <code>tailMap(fromKey, true)</code>.
672       *
673       * @param fromKey the (inclusive) low cutoff point
674       * @return a view of the map above the cutoff
675       * @throws ClassCastException if <code>fromKey</code> is not compatible with
676       *         the comparator (or is not Comparable, for natural ordering)
677       * @throws NullPointerException if fromKey is null, but the comparator
678       *         does not tolerate null elements
679       */
680      public SortedMap<K, V> tailMap(K fromKey)
681      {
682        return tailMap(fromKey, true);
683      }
684    
685      /**
686       * Returns a view of this Map including all entries with keys greater or
687       * equal to <code>fromKey</code>. The returned map is backed by the
688       * original, so changes in one appear in the other. The submap will throw an
689       * {@link IllegalArgumentException} for any attempt to access or add an
690       * element beyond the specified cutoff. The returned map includes the
691       * endpoint; if you want to exclude it, pass in the successor element.
692       *
693       * @param fromKey the low cutoff point
694       * @param inclusive true if the cutoff point should be included.
695       * @return a view of the map above the cutoff
696       * @throws ClassCastException if <code>fromKey</code> is not compatible with
697       *         the comparator (or is not Comparable, for natural ordering)
698       * @throws NullPointerException if fromKey is null, but the comparator
699       *         does not tolerate null elements
700       */
701      public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive)
702      {
703        return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key,
704                          (K)(Object)nil);
705      }
706    
707      /**
708       * Returns a "collection view" (or "bag view") of this TreeMap's values.
709       * The collection is backed by the TreeMap, so changes in one show up
710       * in the other.  The collection supports element removal, but not element
711       * addition.
712       *
713       * @return a bag view of the values
714       * @see #keySet()
715       * @see #entrySet()
716       */
717      public Collection<V> values()
718      {
719        if (values == null)
720          // We don't bother overriding many of the optional methods, as doing so
721          // wouldn't provide any significant performance advantage.
722          values = new AbstractCollection<V>()
723          {
724            public int size()
725            {
726              return size;
727            }
728    
729            public Iterator<V> iterator()
730            {
731              return new TreeIterator(VALUES);
732            }
733    
734            public void clear()
735            {
736              TreeMap.this.clear();
737            }
738          };
739        return values;
740      }
741    
742      /**
743       * Compares two elements by the set comparator, or by natural ordering.
744       * Package visible for use by nested classes.
745       *
746       * @param o1 the first object
747       * @param o2 the second object
748       * @throws ClassCastException if o1 and o2 are not mutually comparable,
749       *         or are not Comparable with natural ordering
750       * @throws NullPointerException if o1 or o2 is null with natural ordering
751       */
752      final int compare(K o1, K o2)
753      {
754        return (comparator == null
755                ? ((Comparable) o1).compareTo(o2)
756                : comparator.compare(o1, o2));
757      }
758    
759      /**
760       * Maintain red-black balance after deleting a node.
761       *
762       * @param node the child of the node just deleted, possibly nil
763       * @param parent the parent of the node just deleted, never nil
764       */
765      private void deleteFixup(Node<K,V> node, Node<K,V> parent)
766      {
767        // if (parent == nil)
768        //   throw new InternalError();
769        // If a black node has been removed, we need to rebalance to avoid
770        // violating the "same number of black nodes on any path" rule. If
771        // node is red, we can simply recolor it black and all is well.
772        while (node != root && node.color == BLACK)
773          {
774            if (node == parent.left)
775              {
776                // Rebalance left side.
777                Node<K,V> sibling = parent.right;
778                // if (sibling == nil)
779                //   throw new InternalError();
780                if (sibling.color == RED)
781                  {
782                    // Case 1: Sibling is red.
783                    // Recolor sibling and parent, and rotate parent left.
784                    sibling.color = BLACK;
785                    parent.color = RED;
786                    rotateLeft(parent);
787                    sibling = parent.right;
788                  }
789    
790                if (sibling.left.color == BLACK && sibling.right.color == BLACK)
791                  {
792                    // Case 2: Sibling has no red children.
793                    // Recolor sibling, and move to parent.
794                    sibling.color = RED;
795                    node = parent;
796                    parent = parent.parent;
797                  }
798                else
799                  {
800                    if (sibling.right.color == BLACK)
801                      {
802                        // Case 3: Sibling has red left child.
803                        // Recolor sibling and left child, rotate sibling right.
804                        sibling.left.color = BLACK;
805                        sibling.color = RED;
806                        rotateRight(sibling);
807                        sibling = parent.right;
808                      }
809                    // Case 4: Sibling has red right child. Recolor sibling,
810                    // right child, and parent, and rotate parent left.
811                    sibling.color = parent.color;
812                    parent.color = BLACK;
813                    sibling.right.color = BLACK;
814                    rotateLeft(parent);
815                    node = root; // Finished.
816                  }
817              }
818            else
819              {
820                // Symmetric "mirror" of left-side case.
821                Node<K,V> sibling = parent.left;
822                // if (sibling == nil)
823                //   throw new InternalError();
824                if (sibling.color == RED)
825                  {
826                    // Case 1: Sibling is red.
827                    // Recolor sibling and parent, and rotate parent right.
828                    sibling.color = BLACK;
829                    parent.color = RED;
830                    rotateRight(parent);
831                    sibling = parent.left;
832                  }
833    
834                if (sibling.right.color == BLACK && sibling.left.color == BLACK)
835                  {
836                    // Case 2: Sibling has no red children.
837                    // Recolor sibling, and move to parent.
838                    sibling.color = RED;
839                    node = parent;
840                    parent = parent.parent;
841                  }
842                else
843                  {
844                    if (sibling.left.color == BLACK)
845                      {
846                        // Case 3: Sibling has red right child.
847                        // Recolor sibling and right child, rotate sibling left.
848                        sibling.right.color = BLACK;
849                        sibling.color = RED;
850                        rotateLeft(sibling);
851                        sibling = parent.left;
852                      }
853                    // Case 4: Sibling has red left child. Recolor sibling,
854                    // left child, and parent, and rotate parent right.
855                    sibling.color = parent.color;
856                    parent.color = BLACK;
857                    sibling.left.color = BLACK;
858                    rotateRight(parent);
859                    node = root; // Finished.
860                  }
861              }
862          }
863        node.color = BLACK;
864      }
865    
866      /**
867       * Construct a perfectly balanced tree consisting of n "blank" nodes. This
868       * permits a tree to be generated from pre-sorted input in linear time.
869       *
870       * @param count the number of blank nodes, non-negative
871       */
872      private void fabricateTree(final int count)
873      {
874        if (count == 0)
875          {
876            root = nil;
877            size = 0;
878            return;
879          }
880    
881        // We color every row of nodes black, except for the overflow nodes.
882        // I believe that this is the optimal arrangement. We construct the tree
883        // in place by temporarily linking each node to the next node in the row,
884        // then updating those links to the children when working on the next row.
885    
886        // Make the root node.
887        root = new Node(null, null, BLACK);
888        size = count;
889        Node row = root;
890        int rowsize;
891    
892        // Fill each row that is completely full of nodes.
893        for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1)
894          {
895            Node parent = row;
896            Node last = null;
897            for (int i = 0; i < rowsize; i += 2)
898              {
899                Node left = new Node(null, null, BLACK);
900                Node right = new Node(null, null, BLACK);
901                left.parent = parent;
902                left.right = right;
903                right.parent = parent;
904                parent.left = left;
905                Node next = parent.right;
906                parent.right = right;
907                parent = next;
908                if (last != null)
909                  last.right = left;
910                last = right;
911              }
912            row = row.left;
913          }
914    
915        // Now do the partial final row in red.
916        int overflow = count - rowsize;
917        Node parent = row;
918        int i;
919        for (i = 0; i < overflow; i += 2)
920          {
921            Node left = new Node(null, null, RED);
922            Node right = new Node(null, null, RED);
923            left.parent = parent;
924            right.parent = parent;
925            parent.left = left;
926            Node next = parent.right;
927            parent.right = right;
928            parent = next;
929          }
930        // Add a lone left node if necessary.
931        if (i - overflow == 0)
932          {
933            Node left = new Node(null, null, RED);
934            left.parent = parent;
935            parent.left = left;
936            parent = parent.right;
937            left.parent.right = nil;
938          }
939        // Unlink the remaining nodes of the previous row.
940        while (parent != nil)
941          {
942            Node next = parent.right;
943            parent.right = nil;
944            parent = next;
945          }
946      }
947    
948      /**
949       * Returns the first sorted node in the map, or nil if empty. Package
950       * visible for use by nested classes.
951       *
952       * @return the first node
953       */
954      final Node<K, V> firstNode()
955      {
956        // Exploit fact that nil.left == nil.
957        Node node = root;
958        while (node.left != nil)
959          node = node.left;
960        return node;
961      }
962    
963      /**
964       * Return the TreeMap.Node associated with key, or the nil node if no such
965       * node exists in the tree. Package visible for use by nested classes.
966       *
967       * @param key the key to search for
968       * @return the node where the key is found, or nil
969       */
970      final Node<K, V> getNode(K key)
971      {
972        Node<K,V> current = root;
973        while (current != nil)
974          {
975            int comparison = compare(key, current.key);
976            if (comparison > 0)
977              current = current.right;
978            else if (comparison < 0)
979              current = current.left;
980            else
981              return current;
982          }
983        return current;
984      }
985    
986      /**
987       * Find the "highest" node which is &lt; key. If key is nil, return last
988       * node. Package visible for use by nested classes.
989       *
990       * @param key the upper bound, exclusive
991       * @return the previous node
992       */
993      final Node<K,V> highestLessThan(K key)
994      {
995        return highestLessThan(key, false);
996      }
997    
998      /**
999       * Find the "highest" node which is &lt; (or equal to,
1000       * if <code>equal</code> is true) key. If key is nil,
1001       * return last node. Package visible for use by nested
1002       * classes.
1003       *
1004       * @param key the upper bound, exclusive
1005       * @param equal true if the key should be returned if found.
1006       * @return the previous node
1007       */
1008      final Node<K,V> highestLessThan(K key, boolean equal)
1009      {
1010        if (key == nil)
1011          return lastNode();
1012    
1013        Node<K,V> last = nil;
1014        Node<K,V> current = root;
1015        int comparison = 0;
1016    
1017        while (current != nil)
1018          {
1019            last = current;
1020            comparison = compare(key, current.key);
1021            if (comparison > 0)
1022              current = current.right;
1023            else if (comparison < 0)
1024              current = current.left;
1025            else // Exact match.
1026              return (equal ? last : predecessor(last));
1027          }
1028        return comparison < 0 ? predecessor(last) : last;
1029      }
1030    
1031      /**
1032       * Maintain red-black balance after inserting a new node.
1033       *
1034       * @param n the newly inserted node
1035       */
1036      private void insertFixup(Node<K,V> n)
1037      {
1038        // Only need to rebalance when parent is a RED node, and while at least
1039        // 2 levels deep into the tree (ie: node has a grandparent). Remember
1040        // that nil.color == BLACK.
1041        while (n.parent.color == RED && n.parent.parent != nil)
1042          {
1043            if (n.parent == n.parent.parent.left)
1044              {
1045                Node uncle = n.parent.parent.right;
1046                // Uncle may be nil, in which case it is BLACK.
1047                if (uncle.color == RED)
1048                  {
1049                    // Case 1. Uncle is RED: Change colors of parent, uncle,
1050                    // and grandparent, and move n to grandparent.
1051                    n.parent.color = BLACK;
1052                    uncle.color = BLACK;
1053                    uncle.parent.color = RED;
1054                    n = uncle.parent;
1055                  }
1056                else
1057                  {
1058                    if (n == n.parent.right)
1059                      {
1060                        // Case 2. Uncle is BLACK and x is right child.
1061                        // Move n to parent, and rotate n left.
1062                        n = n.parent;
1063                        rotateLeft(n);
1064                      }
1065                    // Case 3. Uncle is BLACK and x is left child.
1066                    // Recolor parent, grandparent, and rotate grandparent right.
1067                    n.parent.color = BLACK;
1068                    n.parent.parent.color = RED;
1069                    rotateRight(n.parent.parent);
1070                  }
1071              }
1072            else
1073              {
1074                // Mirror image of above code.
1075                Node uncle = n.parent.parent.left;
1076                // Uncle may be nil, in which case it is BLACK.
1077                if (uncle.color == RED)
1078                  {
1079                    // Case 1. Uncle is RED: Change colors of parent, uncle,
1080                    // and grandparent, and move n to grandparent.
1081                    n.parent.color = BLACK;
1082                    uncle.color = BLACK;
1083                    uncle.parent.color = RED;
1084                    n = uncle.parent;
1085                  }
1086                else
1087                  {
1088                    if (n == n.parent.left)
1089                    {
1090                        // Case 2. Uncle is BLACK and x is left child.
1091                        // Move n to parent, and rotate n right.
1092                        n = n.parent;
1093                        rotateRight(n);
1094                      }
1095                    // Case 3. Uncle is BLACK and x is right child.
1096                    // Recolor parent, grandparent, and rotate grandparent left.
1097                    n.parent.color = BLACK;
1098                    n.parent.parent.color = RED;
1099                    rotateLeft(n.parent.parent);
1100                  }
1101              }
1102          }
1103        root.color = BLACK;
1104      }
1105    
1106      /**
1107       * Returns the last sorted node in the map, or nil if empty.
1108       *
1109       * @return the last node
1110       */
1111      private Node<K,V> lastNode()
1112      {
1113        // Exploit fact that nil.right == nil.
1114        Node node = root;
1115        while (node.right != nil)
1116          node = node.right;
1117        return node;
1118      }
1119    
1120      /**
1121       * Find the "lowest" node which is &gt;= key. If key is nil, return either
1122       * nil or the first node, depending on the parameter first.  Package visible
1123       * for use by nested classes.
1124       *
1125       * @param key the lower bound, inclusive
1126       * @param first true to return the first element instead of nil for nil key
1127       * @return the next node
1128       */
1129      final Node<K,V> lowestGreaterThan(K key, boolean first)
1130      {
1131        return lowestGreaterThan(key, first, true);
1132      }
1133    
1134      /**
1135       * Find the "lowest" node which is &gt; (or equal to, if <code>equal</code>
1136       * is true) key. If key is nil, return either nil or the first node, depending
1137       * on the parameter first.  Package visible for use by nested classes.
1138       *
1139       * @param key the lower bound, inclusive
1140       * @param first true to return the first element instead of nil for nil key
1141       * @param equal true if the key should be returned if found.
1142       * @return the next node
1143       */
1144      final Node<K,V> lowestGreaterThan(K key, boolean first, boolean equal)
1145      {
1146        if (key == nil)
1147          return first ? firstNode() : nil;
1148    
1149        Node<K,V> last = nil;
1150        Node<K,V> current = root;
1151        int comparison = 0;
1152    
1153        while (current != nil)
1154          {
1155            last = current;
1156            comparison = compare(key, current.key);
1157            if (comparison > 0)
1158              current = current.right;
1159            else if (comparison < 0)
1160              current = current.left;
1161            else
1162              return (equal ? current : successor(current));
1163          }
1164        return comparison > 0 ? successor(last) : last;
1165      }
1166    
1167      /**
1168       * Return the node preceding the given one, or nil if there isn't one.
1169       *
1170       * @param node the current node, not nil
1171       * @return the prior node in sorted order
1172       */
1173      private Node<K,V> predecessor(Node<K,V> node)
1174      {
1175        if (node.left != nil)
1176          {
1177            node = node.left;
1178            while (node.right != nil)
1179              node = node.right;
1180            return node;
1181          }
1182    
1183        Node parent = node.parent;
1184        // Exploit fact that nil.left == nil and node is non-nil.
1185        while (node == parent.left)
1186          {
1187            node = parent;
1188            parent = node.parent;
1189          }
1190        return parent;
1191      }
1192    
1193      /**
1194       * Construct a tree from sorted keys in linear time. Package visible for
1195       * use by TreeSet.
1196       *
1197       * @param s the stream to read from
1198       * @param count the number of keys to read
1199       * @param readValues true to read values, false to insert "" as the value
1200       * @throws ClassNotFoundException if the underlying stream fails
1201       * @throws IOException if the underlying stream fails
1202       * @see #readObject(ObjectInputStream)
1203       * @see TreeSet#readObject(ObjectInputStream)
1204       */
1205      final void putFromObjStream(ObjectInputStream s, int count,
1206                                  boolean readValues)
1207        throws IOException, ClassNotFoundException
1208      {
1209        fabricateTree(count);
1210        Node node = firstNode();
1211    
1212        while (--count >= 0)
1213          {
1214            node.key = s.readObject();
1215            node.value = readValues ? s.readObject() : "";
1216            node = successor(node);
1217          }
1218      }
1219    
1220      /**
1221       * Construct a tree from sorted keys in linear time, with values of "".
1222       * Package visible for use by TreeSet, which uses a value type of String.
1223       *
1224       * @param keys the iterator over the sorted keys
1225       * @param count the number of nodes to insert
1226       * @see TreeSet#TreeSet(SortedSet)
1227       */
1228      final void putKeysLinear(Iterator<K> keys, int count)
1229      {
1230        fabricateTree(count);
1231        Node<K,V> node = firstNode();
1232    
1233        while (--count >= 0)
1234          {
1235            node.key = keys.next();
1236            node.value = (V) "";
1237            node = successor(node);
1238          }
1239      }
1240    
1241      /**
1242       * Deserializes this object from the given stream.
1243       *
1244       * @param s the stream to read from
1245       * @throws ClassNotFoundException if the underlying stream fails
1246       * @throws IOException if the underlying stream fails
1247       * @serialData the <i>size</i> (int), followed by key (Object) and value
1248       *             (Object) pairs in sorted order
1249       */
1250      private void readObject(ObjectInputStream s)
1251        throws IOException, ClassNotFoundException
1252      {
1253        s.defaultReadObject();
1254        int size = s.readInt();
1255        putFromObjStream(s, size, true);
1256      }
1257    
1258      /**
1259       * Remove node from tree. This will increment modCount and decrement size.
1260       * Node must exist in the tree. Package visible for use by nested classes.
1261       *
1262       * @param node the node to remove
1263       */
1264      final void removeNode(Node<K,V> node)
1265      {
1266        Node<K,V> splice;
1267        Node<K,V> child;
1268    
1269        modCount++;
1270        size--;
1271    
1272        // Find splice, the node at the position to actually remove from the tree.
1273        if (node.left == nil)
1274          {
1275            // Node to be deleted has 0 or 1 children.
1276            splice = node;
1277            child = node.right;
1278          }
1279        else if (node.right == nil)
1280          {
1281            // Node to be deleted has 1 child.
1282            splice = node;
1283            child = node.left;
1284          }
1285        else
1286          {
1287            // Node has 2 children. Splice is node's predecessor, and we swap
1288            // its contents into node.
1289            splice = node.left;
1290            while (splice.right != nil)
1291              splice = splice.right;
1292            child = splice.left;
1293            node.key = splice.key;
1294            node.value = splice.value;
1295          }
1296    
1297        // Unlink splice from the tree.
1298        Node parent = splice.parent;
1299        if (child != nil)
1300          child.parent = parent;
1301        if (parent == nil)
1302          {
1303            // Special case for 0 or 1 node remaining.
1304            root = child;
1305            return;
1306          }
1307        if (splice == parent.left)
1308          parent.left = child;
1309        else
1310          parent.right = child;
1311    
1312        if (splice.color == BLACK)
1313          deleteFixup(child, parent);
1314      }
1315    
1316      /**
1317       * Rotate node n to the left.
1318       *
1319       * @param node the node to rotate
1320       */
1321      private void rotateLeft(Node<K,V> node)
1322      {
1323        Node child = node.right;
1324        // if (node == nil || child == nil)
1325        //   throw new InternalError();
1326    
1327        // Establish node.right link.
1328        node.right = child.left;
1329        if (child.left != nil)
1330          child.left.parent = node;
1331    
1332        // Establish child->parent link.
1333        child.parent = node.parent;
1334        if (node.parent != nil)
1335          {
1336            if (node == node.parent.left)
1337              node.parent.left = child;
1338            else
1339              node.parent.right = child;
1340          }
1341        else
1342          root = child;
1343    
1344        // Link n and child.
1345        child.left = node;
1346        node.parent = child;
1347      }
1348    
1349      /**
1350       * Rotate node n to the right.
1351       *
1352       * @param node the node to rotate
1353       */
1354      private void rotateRight(Node<K,V> node)
1355      {
1356        Node child = node.left;
1357        // if (node == nil || child == nil)
1358        //   throw new InternalError();
1359    
1360        // Establish node.left link.
1361        node.left = child.right;
1362        if (child.right != nil)
1363          child.right.parent = node;
1364    
1365        // Establish child->parent link.
1366        child.parent = node.parent;
1367        if (node.parent != nil)
1368          {
1369            if (node == node.parent.right)
1370              node.parent.right = child;
1371            else
1372              node.parent.left = child;
1373          }
1374        else
1375          root = child;
1376    
1377        // Link n and child.
1378        child.right = node;
1379        node.parent = child;
1380      }
1381    
1382      /**
1383       * Return the node following the given one, or nil if there isn't one.
1384       * Package visible for use by nested classes.
1385       *
1386       * @param node the current node, not nil
1387       * @return the next node in sorted order
1388       */
1389      final Node<K,V> successor(Node<K,V> node)
1390      {
1391        if (node.right != nil)
1392          {
1393            node = node.right;
1394            while (node.left != nil)
1395              node = node.left;
1396            return node;
1397          }
1398    
1399        Node<K,V> parent = node.parent;
1400        // Exploit fact that nil.right == nil and node is non-nil.
1401        while (node == parent.right)
1402          {
1403            node = parent;
1404            parent = parent.parent;
1405          }
1406        return parent;
1407      }
1408    
1409      /**
1410       * Serializes this object to the given stream.
1411       *
1412       * @param s the stream to write to
1413       * @throws IOException if the underlying stream fails
1414       * @serialData the <i>size</i> (int), followed by key (Object) and value
1415       *             (Object) pairs in sorted order
1416       */
1417      private void writeObject(ObjectOutputStream s) throws IOException
1418      {
1419        s.defaultWriteObject();
1420    
1421        Node node = firstNode();
1422        s.writeInt(size);
1423        while (node != nil)
1424          {
1425            s.writeObject(node.key);
1426            s.writeObject(node.value);
1427            node = successor(node);
1428          }
1429      }
1430    
1431      /**
1432       * Iterate over TreeMap's entries. This implementation is parameterized
1433       * to give a sequential view of keys, values, or entries.
1434       *
1435       * @author Eric Blake (ebb9@email.byu.edu)
1436       */
1437      private final class TreeIterator implements Iterator
1438      {
1439        /**
1440         * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
1441         * or {@link #ENTRIES}.
1442         */
1443        private final int type;
1444        /** The number of modifications to the backing Map that we know about. */
1445        private int knownMod = modCount;
1446        /** The last Entry returned by a next() call. */
1447        private Node last;
1448        /** The next entry that should be returned by next(). */
1449        private Node next;
1450        /**
1451         * The last node visible to this iterator. This is used when iterating
1452         * on a SubMap.
1453         */
1454        private final Node max;
1455    
1456        /**
1457         * Construct a new TreeIterator with the supplied type.
1458         * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
1459         */
1460        TreeIterator(int type)
1461        {
1462          this(type, firstNode(), nil);
1463        }
1464    
1465        /**
1466         * Construct a new TreeIterator with the supplied type. Iteration will
1467         * be from "first" (inclusive) to "max" (exclusive).
1468         *
1469         * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
1470         * @param first where to start iteration, nil for empty iterator
1471         * @param max the cutoff for iteration, nil for all remaining nodes
1472         */
1473        TreeIterator(int type, Node first, Node max)
1474        {
1475          this.type = type;
1476          this.next = first;
1477          this.max = max;
1478        }
1479    
1480        /**
1481         * Returns true if the Iterator has more elements.
1482         * @return true if there are more elements
1483         */
1484        public boolean hasNext()
1485        {
1486          return next != max;
1487        }
1488    
1489        /**
1490         * Returns the next element in the Iterator's sequential view.
1491         * @return the next element
1492         * @throws ConcurrentModificationException if the TreeMap was modified
1493         * @throws NoSuchElementException if there is none
1494         */
1495        public Object next()
1496        {
1497          if (knownMod != modCount)
1498            throw new ConcurrentModificationException();
1499          if (next == max)
1500            throw new NoSuchElementException();
1501          last = next;
1502          next = successor(last);
1503    
1504          if (type == VALUES)
1505            return last.value;
1506          else if (type == KEYS)
1507            return last.key;
1508          return last;
1509        }
1510    
1511        /**
1512         * Removes from the backing TreeMap the last element which was fetched
1513         * with the <code>next()</code> method.
1514         * @throws ConcurrentModificationException if the TreeMap was modified
1515         * @throws IllegalStateException if called when there is no last element
1516         */
1517        public void remove()
1518        {
1519          if (last == null)
1520            throw new IllegalStateException();
1521          if (knownMod != modCount)
1522            throw new ConcurrentModificationException();
1523    
1524          removeNode(last);
1525          last = null;
1526          knownMod++;
1527        }
1528      } // class TreeIterator
1529    
1530      /**
1531       * Implementation of {@link #subMap(Object, Object)} and other map
1532       * ranges. This class provides a view of a portion of the original backing
1533       * map, and throws {@link IllegalArgumentException} for attempts to
1534       * access beyond that range.
1535       *
1536       * @author Eric Blake (ebb9@email.byu.edu)
1537       */
1538      private final class SubMap
1539        extends AbstractMap<K,V>
1540        implements NavigableMap<K,V>
1541      {
1542        /**
1543         * The lower range of this view, inclusive, or nil for unbounded.
1544         * Package visible for use by nested classes.
1545         */
1546        final K minKey;
1547    
1548        /**
1549         * The upper range of this view, exclusive, or nil for unbounded.
1550         * Package visible for use by nested classes.
1551         */
1552        final K maxKey;
1553    
1554        /**
1555         * The cache for {@link #entrySet()}.
1556         */
1557        private Set<Map.Entry<K,V>> entries;
1558    
1559        /**
1560         * The cache for {@link #descendingMap()}.
1561         */
1562        private NavigableMap<K,V> descendingMap;
1563    
1564        /**
1565         * The cache for {@link #navigableKeySet()}.
1566         */
1567        private NavigableSet<K> nKeys;
1568    
1569        /**
1570         * Create a SubMap representing the elements between minKey (inclusive)
1571         * and maxKey (exclusive). If minKey is nil, SubMap has no lower bound
1572         * (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap).
1573         *
1574         * @param minKey the lower bound
1575         * @param maxKey the upper bound
1576         * @throws IllegalArgumentException if minKey &gt; maxKey
1577         */
1578        SubMap(K minKey, K maxKey)
1579        {
1580          if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)
1581            throw new IllegalArgumentException("fromKey > toKey");
1582          this.minKey = minKey;
1583          this.maxKey = maxKey;
1584        }
1585    
1586        /**
1587         * Check if "key" is in within the range bounds for this SubMap. The
1588         * lower ("from") SubMap range is inclusive, and the upper ("to") bound
1589         * is exclusive. Package visible for use by nested classes.
1590         *
1591         * @param key the key to check
1592         * @return true if the key is in range
1593         */
1594        boolean keyInRange(K key)
1595        {
1596          return ((minKey == nil || compare(key, minKey) >= 0)
1597                  && (maxKey == nil || compare(key, maxKey) < 0));
1598        }
1599    
1600        public Entry<K,V> ceilingEntry(K key)
1601        {
1602          Entry<K,V> n = TreeMap.this.ceilingEntry(key);
1603          if (n != null && keyInRange(n.getKey()))
1604            return n;
1605          return null;
1606        }
1607    
1608        public K ceilingKey(K key)
1609        {
1610          K found = TreeMap.this.ceilingKey(key);
1611          if (keyInRange(found))
1612            return found;
1613          else
1614            return null;
1615        }
1616    
1617        public NavigableSet<K> descendingKeySet()
1618        {
1619          return descendingMap().navigableKeySet();
1620        }
1621    
1622        public NavigableMap<K,V> descendingMap()
1623        {
1624          if (descendingMap == null)
1625            descendingMap = new DescendingMap(this);
1626          return descendingMap;
1627        }
1628    
1629        public void clear()
1630        {
1631          Node next = lowestGreaterThan(minKey, true);
1632          Node max = lowestGreaterThan(maxKey, false);
1633          while (next != max)
1634            {
1635              Node current = next;
1636              next = successor(current);
1637              removeNode(current);
1638            }
1639        }
1640    
1641        public Comparator<? super K> comparator()
1642        {
1643          return comparator;
1644        }
1645    
1646        public boolean containsKey(Object key)
1647        {
1648          return keyInRange((K) key) && TreeMap.this.containsKey(key);
1649        }
1650    
1651        public boolean containsValue(Object value)
1652        {
1653          Node node = lowestGreaterThan(minKey, true);
1654          Node max = lowestGreaterThan(maxKey, false);
1655          while (node != max)
1656            {
1657              if (equals(value, node.getValue()))
1658                return true;
1659              node = successor(node);
1660            }
1661          return false;
1662        }
1663    
1664        public Set<Map.Entry<K,V>> entrySet()
1665        {
1666          if (entries == null)
1667            // Create an AbstractSet with custom implementations of those methods
1668            // that can be overriden easily and efficiently.
1669            entries = new SubMap.NavigableEntrySet();
1670          return entries;
1671        }
1672    
1673        public Entry<K,V> firstEntry()
1674        {
1675          Node<K,V> node = lowestGreaterThan(minKey, true);
1676          if (node == nil || ! keyInRange(node.key))
1677            return null;
1678          return node;
1679        }
1680    
1681        public K firstKey()
1682        {
1683          Entry<K,V> e = firstEntry();
1684          if (e == null)
1685            throw new NoSuchElementException();
1686          return e.getKey();
1687        }
1688    
1689        public Entry<K,V> floorEntry(K key)
1690        {
1691          Entry<K,V> n = TreeMap.this.floorEntry(key);
1692          if (n != null && keyInRange(n.getKey()))
1693            return n;
1694          return null;
1695        }
1696    
1697        public K floorKey(K key)
1698        {
1699          K found = TreeMap.this.floorKey(key);
1700          if (keyInRange(found))
1701            return found;
1702          else
1703            return null;
1704        }
1705    
1706        public V get(Object key)
1707        {
1708          if (keyInRange((K) key))
1709            return TreeMap.this.get(key);
1710          return null;
1711        }
1712    
1713        public SortedMap<K,V> headMap(K toKey)
1714        {
1715          return headMap(toKey, false);
1716        }
1717    
1718        public NavigableMap<K,V> headMap(K toKey, boolean inclusive)
1719        {
1720          if (!keyInRange(toKey))
1721            throw new IllegalArgumentException("Key outside submap range");
1722          return new SubMap(minKey, (inclusive ?
1723                                     successor(getNode(toKey)).key : toKey));
1724        }
1725    
1726        public Set<K> keySet()
1727        {
1728          if (this.keys == null)
1729            // Create an AbstractSet with custom implementations of those methods
1730            // that can be overriden easily and efficiently.
1731            this.keys = new SubMap.KeySet();
1732          return this.keys;
1733        }
1734    
1735        public Entry<K,V> higherEntry(K key)
1736        {
1737          Entry<K,V> n = TreeMap.this.higherEntry(key);
1738          if (n != null && keyInRange(n.getKey()))
1739            return n;
1740          return null;
1741        }
1742    
1743        public K higherKey(K key)
1744        {
1745          K found = TreeMap.this.higherKey(key);
1746          if (keyInRange(found))
1747            return found;
1748          else
1749            return null;
1750        }
1751    
1752        public Entry<K,V> lastEntry()
1753        {
1754          return lowerEntry(maxKey);
1755        }
1756    
1757        public K lastKey()
1758        {
1759          Entry<K,V> e = lastEntry();
1760          if (e == null)
1761            throw new NoSuchElementException();
1762          return e.getKey();
1763        }
1764    
1765        public Entry<K,V> lowerEntry(K key)
1766        {
1767          Entry<K,V> n = TreeMap.this.lowerEntry(key);
1768          if (n != null && keyInRange(n.getKey()))
1769            return n;
1770          return null;
1771        }
1772    
1773        public K lowerKey(K key)
1774        {
1775          K found = TreeMap.this.lowerKey(key);
1776          if (keyInRange(found))
1777            return found;
1778          else
1779            return null;
1780        }
1781    
1782        public NavigableSet<K> navigableKeySet()
1783        {
1784          if (this.nKeys == null)
1785            // Create an AbstractSet with custom implementations of those methods
1786            // that can be overriden easily and efficiently.
1787            this.nKeys = new SubMap.NavigableKeySet();
1788          return this.nKeys;
1789        }
1790    
1791        public Entry<K,V> pollFirstEntry()
1792        {
1793          Entry<K,V> e = firstEntry();
1794          if (e != null)
1795            removeNode((Node<K,V>) e);
1796          return e;
1797        }
1798    
1799        public Entry<K,V> pollLastEntry()
1800        {
1801          Entry<K,V> e = lastEntry();
1802          if (e != null)
1803            removeNode((Node<K,V>) e);
1804          return e;
1805        }
1806    
1807        public V put(K key, V value)
1808        {
1809          if (! keyInRange(key))
1810            throw new IllegalArgumentException("Key outside range");
1811          return TreeMap.this.put(key, value);
1812        }
1813    
1814        public V remove(Object key)
1815        {
1816          if (keyInRange((K)key))
1817            return TreeMap.this.remove(key);
1818          return null;
1819        }
1820    
1821        public int size()
1822        {
1823          Node node = lowestGreaterThan(minKey, true);
1824          Node max = lowestGreaterThan(maxKey, false);
1825          int count = 0;
1826          while (node != max)
1827            {
1828              count++;
1829              node = successor(node);
1830            }
1831          return count;
1832        }
1833    
1834        public SortedMap<K,V> subMap(K fromKey, K toKey)
1835        {
1836          return subMap(fromKey, true, toKey, false);
1837        }
1838    
1839        public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1840                                        K toKey, boolean toInclusive)
1841        {
1842          if (! keyInRange(fromKey) || ! keyInRange(toKey))
1843            throw new IllegalArgumentException("key outside range");
1844          return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key,
1845                            toInclusive ? successor(getNode(toKey)).key : toKey);
1846        }
1847    
1848        public SortedMap<K, V> tailMap(K fromKey)
1849        {
1850          return tailMap(fromKey, true);
1851        }
1852    
1853        public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
1854        {
1855          if (! keyInRange(fromKey))
1856            throw new IllegalArgumentException("key outside range");
1857          return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key,
1858                            maxKey);
1859        }
1860    
1861        public Collection<V> values()
1862        {
1863          if (this.values == null)
1864            // Create an AbstractCollection with custom implementations of those
1865            // methods that can be overriden easily and efficiently.
1866            this.values = new AbstractCollection()
1867            {
1868              public int size()
1869              {
1870                return SubMap.this.size();
1871              }
1872    
1873              public Iterator<V> iterator()
1874              {
1875                Node first = lowestGreaterThan(minKey, true);
1876                Node max = lowestGreaterThan(maxKey, false);
1877                return new TreeIterator(VALUES, first, max);
1878              }
1879    
1880              public void clear()
1881              {
1882                SubMap.this.clear();
1883              }
1884            };
1885          return this.values;
1886        }
1887    
1888        private class KeySet
1889          extends AbstractSet<K>
1890        {
1891          public int size()
1892          {
1893            return SubMap.this.size();
1894          }
1895    
1896          public Iterator<K> iterator()
1897          {
1898            Node first = lowestGreaterThan(minKey, true);
1899            Node max = lowestGreaterThan(maxKey, false);
1900            return new TreeIterator(KEYS, first, max);
1901          }
1902    
1903          public void clear()
1904          {
1905            SubMap.this.clear();
1906          }
1907    
1908          public boolean contains(Object o)
1909          {
1910            if (! keyInRange((K) o))
1911              return false;
1912            return getNode((K) o) != nil;
1913          }
1914    
1915          public boolean remove(Object o)
1916          {
1917            if (! keyInRange((K) o))
1918              return false;
1919            Node n = getNode((K) o);
1920            if (n != nil)
1921              {
1922                removeNode(n);
1923                return true;
1924              }
1925            return false;
1926          }
1927    
1928        } // class SubMap.KeySet
1929    
1930        private final class NavigableKeySet
1931          extends KeySet
1932          implements NavigableSet<K>
1933        {
1934    
1935          public K ceiling(K k)
1936          {
1937            return SubMap.this.ceilingKey(k);
1938          }
1939    
1940          public Comparator<? super K> comparator()
1941          {
1942            return comparator;
1943          }
1944    
1945          public Iterator<K> descendingIterator()
1946          {
1947            return descendingSet().iterator();
1948          }
1949    
1950          public NavigableSet<K> descendingSet()
1951          {
1952            return new DescendingSet(this);
1953          }
1954    
1955          public K first()
1956          {
1957            return SubMap.this.firstKey();
1958          }
1959    
1960          public K floor(K k)
1961          {
1962            return SubMap.this.floorKey(k);
1963          }
1964    
1965          public SortedSet<K> headSet(K to)
1966          {
1967            return headSet(to, false);
1968          }
1969    
1970          public NavigableSet<K> headSet(K to, boolean inclusive)
1971          {
1972            return SubMap.this.headMap(to, inclusive).navigableKeySet();
1973          }
1974    
1975          public K higher(K k)
1976          {
1977            return SubMap.this.higherKey(k);
1978          }
1979    
1980          public K last()
1981          {
1982            return SubMap.this.lastKey();
1983          }
1984    
1985          public K lower(K k)
1986          {
1987            return SubMap.this.lowerKey(k);
1988          }
1989    
1990          public K pollFirst()
1991          {
1992            return SubMap.this.pollFirstEntry().getKey();
1993          }
1994    
1995          public K pollLast()
1996          {
1997            return SubMap.this.pollLastEntry().getKey();
1998          }
1999    
2000          public SortedSet<K> subSet(K from, K to)
2001          {
2002            return subSet(from, true, to, false);
2003          }
2004    
2005          public NavigableSet<K> subSet(K from, boolean fromInclusive,
2006                                        K to, boolean toInclusive)
2007          {
2008            return SubMap.this.subMap(from, fromInclusive,
2009                                      to, toInclusive).navigableKeySet();
2010          }
2011    
2012          public SortedSet<K> tailSet(K from)
2013          {
2014            return tailSet(from, true);
2015          }
2016    
2017          public NavigableSet<K> tailSet(K from, boolean inclusive)
2018          {
2019            return SubMap.this.tailMap(from, inclusive).navigableKeySet();
2020          }
2021    
2022      } // class SubMap.NavigableKeySet
2023    
2024      /**
2025       * Implementation of {@link #entrySet()}.
2026       */
2027      private class EntrySet
2028        extends AbstractSet<Entry<K,V>>
2029      {
2030    
2031        public int size()
2032        {
2033          return SubMap.this.size();
2034        }
2035    
2036        public Iterator<Map.Entry<K,V>> iterator()
2037        {
2038          Node first = lowestGreaterThan(minKey, true);
2039          Node max = lowestGreaterThan(maxKey, false);
2040          return new TreeIterator(ENTRIES, first, max);
2041        }
2042    
2043        public void clear()
2044        {
2045          SubMap.this.clear();
2046        }
2047    
2048        public boolean contains(Object o)
2049        {
2050          if (! (o instanceof Map.Entry))
2051            return false;
2052          Map.Entry<K,V> me = (Map.Entry<K,V>) o;
2053          K key = me.getKey();
2054          if (! keyInRange(key))
2055            return false;
2056          Node<K,V> n = getNode(key);
2057          return n != nil && AbstractSet.equals(me.getValue(), n.value);
2058        }
2059    
2060        public boolean remove(Object o)
2061        {
2062          if (! (o instanceof Map.Entry))
2063            return false;
2064          Map.Entry<K,V> me = (Map.Entry<K,V>) o;
2065          K key = me.getKey();
2066          if (! keyInRange(key))
2067            return false;
2068          Node<K,V> n = getNode(key);
2069          if (n != nil && AbstractSet.equals(me.getValue(), n.value))
2070            {
2071              removeNode(n);
2072              return true;
2073            }
2074          return false;
2075        }
2076      } // class SubMap.EntrySet
2077    
2078        private final class NavigableEntrySet
2079          extends EntrySet
2080          implements NavigableSet<Entry<K,V>>
2081        {
2082    
2083          public Entry<K,V> ceiling(Entry<K,V> e)
2084          {
2085            return SubMap.this.ceilingEntry(e.getKey());
2086          }
2087    
2088          public Comparator<? super Entry<K,V>> comparator()
2089          {
2090            return new Comparator<Entry<K,V>>()
2091              {
2092                public int compare(Entry<K,V> t1, Entry<K,V> t2)
2093                  {
2094                    return comparator.compare(t1.getKey(), t2.getKey());
2095                  }
2096              };
2097          }
2098    
2099          public Iterator<Entry<K,V>> descendingIterator()
2100          {
2101            return descendingSet().iterator();
2102          }
2103    
2104          public NavigableSet<Entry<K,V>> descendingSet()
2105          {
2106            return new DescendingSet(this);
2107          }
2108    
2109          public Entry<K,V> first()
2110          {
2111            return SubMap.this.firstEntry();
2112          }
2113    
2114          public Entry<K,V> floor(Entry<K,V> e)
2115          {
2116            return SubMap.this.floorEntry(e.getKey());
2117          }
2118    
2119          public SortedSet<Entry<K,V>> headSet(Entry<K,V> to)
2120          {
2121            return headSet(to, false);
2122          }
2123    
2124          public NavigableSet<Entry<K,V>> headSet(Entry<K,V> to, boolean inclusive)
2125          {
2126            return (NavigableSet<Entry<K,V>>)
2127              SubMap.this.headMap(to.getKey(), inclusive).entrySet();
2128          }
2129    
2130          public Entry<K,V> higher(Entry<K,V> e)
2131          {
2132            return SubMap.this.higherEntry(e.getKey());
2133          }
2134    
2135          public Entry<K,V> last()
2136          {
2137            return SubMap.this.lastEntry();
2138          }
2139    
2140          public Entry<K,V> lower(Entry<K,V> e)
2141          {
2142            return SubMap.this.lowerEntry(e.getKey());
2143          }
2144    
2145          public Entry<K,V> pollFirst()
2146          {
2147            return SubMap.this.pollFirstEntry();
2148          }
2149    
2150          public Entry<K,V> pollLast()
2151          {
2152            return SubMap.this.pollLastEntry();
2153          }
2154    
2155          public SortedSet<Entry<K,V>> subSet(Entry<K,V> from, Entry<K,V> to)
2156          {
2157            return subSet(from, true, to, false);
2158          }
2159    
2160          public NavigableSet<Entry<K,V>> subSet(Entry<K,V> from, boolean fromInclusive,
2161                                                 Entry<K,V> to, boolean toInclusive)
2162          {
2163            return (NavigableSet<Entry<K,V>>)
2164              SubMap.this.subMap(from.getKey(), fromInclusive,
2165                                 to.getKey(), toInclusive).entrySet();
2166          }
2167    
2168          public SortedSet<Entry<K,V>> tailSet(Entry<K,V> from)
2169          {
2170            return tailSet(from, true);
2171          }
2172    
2173          public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive)
2174          {
2175            return (NavigableSet<Entry<K,V>>)
2176              SubMap.this.tailMap(from.getKey(), inclusive).navigableKeySet();
2177          }
2178    
2179      } // class SubMap.NavigableEntrySet
2180    
2181    } // class SubMap
2182    
2183      /**
2184       * Returns the entry associated with the least or lowest key
2185       * that is greater than or equal to the specified key, or
2186       * <code>null</code> if there is no such key.
2187       *
2188       * @param key the key relative to the returned entry.
2189       * @return the entry with the least key greater than or equal
2190       *         to the given key, or <code>null</code> if there is
2191       *         no such key.
2192       * @throws ClassCastException if the specified key can not
2193       *                            be compared with those in the map.
2194       * @throws NullPointerException if the key is <code>null</code>
2195       *                              and this map either uses natural
2196       *                              ordering or a comparator that does
2197       *                              not permit null keys.
2198       * @since 1.6
2199       */
2200      public Entry<K,V> ceilingEntry(K key)
2201      {
2202        Node<K,V> n = lowestGreaterThan(key, false);
2203        return (n == nil) ? null : n;
2204      }
2205    
2206      /**
2207       * Returns the the least or lowest key that is greater than
2208       * or equal to the specified key, or <code>null</code> if
2209       * there is no such key.
2210       *
2211       * @param key the key relative to the returned entry.
2212       * @return the least key greater than or equal to the given key,
2213       *         or <code>null</code> if there is no such key.
2214       * @throws ClassCastException if the specified key can not
2215       *                            be compared with those in the map.
2216       * @throws NullPointerException if the key is <code>null</code>
2217       *                              and this map either uses natural
2218       *                              ordering or a comparator that does
2219       *                              not permit null keys.
2220       * @since 1.6
2221       */
2222      public K ceilingKey(K key)
2223      {
2224        Entry<K,V> e = ceilingEntry(key);
2225        return (e == null) ? null : e.getKey();
2226      }
2227    
2228      /**
2229       * Returns a reverse ordered {@link NavigableSet} view of this
2230       * map's keys. The set is backed by the {@link TreeMap}, so changes
2231       * in one show up in the other.  The set supports element removal,
2232       * but not element addition.
2233       *
2234       * @return a reverse ordered set view of the keys.
2235       * @since 1.6
2236       * @see #descendingMap()
2237       */
2238      public NavigableSet<K> descendingKeySet()
2239      {
2240        return descendingMap().navigableKeySet();
2241      }
2242    
2243      /**
2244       * Returns a view of the map in reverse order.  The descending map
2245       * is backed by the original map, so that changes affect both maps.
2246       * Any changes occurring to either map while an iteration is taking
2247       * place (with the exception of a {@link Iterator#remove()} operation)
2248       * result in undefined behaviour from the iteration.  The ordering
2249       * of the descending map is the same as for a map with a
2250       * {@link Comparator} given by {@link Collections#reverseOrder()},
2251       * and calling {@link #descendingMap()} on the descending map itself
2252       * results in a view equivalent to the original map.
2253       *
2254       * @return a reverse order view of the map.
2255       * @since 1.6
2256       */
2257      public NavigableMap<K,V> descendingMap()
2258      {
2259        if (descendingMap == null)
2260          descendingMap = new DescendingMap<K,V>(this);
2261        return descendingMap;
2262      }
2263    
2264      /**
2265       * Returns the entry associated with the least or lowest key
2266       * in the map, or <code>null</code> if the map is empty.
2267       *
2268       * @return the lowest entry, or <code>null</code> if the map
2269       *         is empty.
2270       * @since 1.6
2271       */
2272      public Entry<K,V> firstEntry()
2273      {
2274        Node<K,V> n = firstNode();
2275        return (n == nil) ? null : n;
2276      }
2277    
2278      /**
2279       * Returns the entry associated with the greatest or highest key
2280       * that is less than or equal to the specified key, or
2281       * <code>null</code> if there is no such key.
2282       *
2283       * @param key the key relative to the returned entry.
2284       * @return the entry with the greatest key less than or equal
2285       *         to the given key, or <code>null</code> if there is
2286       *         no such key.
2287       * @throws ClassCastException if the specified key can not
2288       *                            be compared with those in the map.
2289       * @throws NullPointerException if the key is <code>null</code>
2290       *                              and this map either uses natural
2291       *                              ordering or a comparator that does
2292       *                              not permit null keys.
2293       * @since 1.6
2294       */
2295      public Entry<K,V> floorEntry(K key)
2296      {
2297        Node<K,V> n = highestLessThan(key, true);
2298        return (n == nil) ? null : n;
2299      }
2300    
2301      /**
2302       * Returns the the greatest or highest key that is less than
2303       * or equal to the specified key, or <code>null</code> if
2304       * there is no such key.
2305       *
2306       * @param key the key relative to the returned entry.
2307       * @return the greatest key less than or equal to the given key,
2308       *         or <code>null</code> if there is no such key.
2309       * @throws ClassCastException if the specified key can not
2310       *                            be compared with those in the map.
2311       * @throws NullPointerException if the key is <code>null</code>
2312       *                              and this map either uses natural
2313       *                              ordering or a comparator that does
2314       *                              not permit null keys.
2315       * @since 1.6
2316       */
2317      public K floorKey(K key)
2318      {
2319        Entry<K,V> e = floorEntry(key);
2320        return (e == null) ? null : e.getKey();
2321      }
2322    
2323      /**
2324       * Returns the entry associated with the least or lowest key
2325       * that is strictly greater than the specified key, or
2326       * <code>null</code> if there is no such key.
2327       *
2328       * @param key the key relative to the returned entry.
2329       * @return the entry with the least key greater than
2330       *         the given key, or <code>null</code> if there is
2331       *         no such key.
2332       * @throws ClassCastException if the specified key can not
2333       *                            be compared with those in the map.
2334       * @throws NullPointerException if the key is <code>null</code>
2335       *                              and this map either uses natural
2336       *                              ordering or a comparator that does
2337       *                              not permit null keys.
2338       * @since 1.6
2339       */
2340      public Entry<K,V> higherEntry(K key)
2341      {
2342        Node<K,V> n = lowestGreaterThan(key, false, false);
2343        return (n == nil) ? null : n;
2344      }
2345    
2346      /**
2347       * Returns the the least or lowest key that is strictly
2348       * greater than the specified key, or <code>null</code> if
2349       * there is no such key.
2350       *
2351       * @param key the key relative to the returned entry.
2352       * @return the least key greater than the given key,
2353       *         or <code>null</code> if there is no such key.
2354       * @throws ClassCastException if the specified key can not
2355       *                            be compared with those in the map.
2356       * @throws NullPointerException if the key is <code>null</code>
2357       *                              and this map either uses natural
2358       *                              ordering or a comparator that does
2359       *                              not permit null keys.
2360       * @since 1.6
2361       */
2362      public K higherKey(K key)
2363      {
2364        Entry<K,V> e = higherEntry(key);
2365        return (e == null) ? null : e.getKey();
2366      }
2367    
2368      /**
2369       * Returns the entry associated with the greatest or highest key
2370       * in the map, or <code>null</code> if the map is empty.
2371       *
2372       * @return the highest entry, or <code>null</code> if the map
2373       *         is empty.
2374       * @since 1.6
2375       */
2376      public Entry<K,V> lastEntry()
2377      {
2378        Node<K,V> n = lastNode();
2379        return (n == nil) ? null : n;
2380      }
2381    
2382      /**
2383       * Returns the entry associated with the greatest or highest key
2384       * that is strictly less than the specified key, or
2385       * <code>null</code> if there is no such key.
2386       *
2387       * @param key the key relative to the returned entry.
2388       * @return the entry with the greatest key less than
2389       *         the given key, or <code>null</code> if there is
2390       *         no such key.
2391       * @throws ClassCastException if the specified key can not
2392       *                            be compared with those in the map.
2393       * @throws NullPointerException if the key is <code>null</code>
2394       *                              and this map either uses natural
2395       *                              ordering or a comparator that does
2396       *                              not permit null keys.
2397       * @since 1.6
2398       */
2399      public Entry<K,V> lowerEntry(K key)
2400      {
2401        Node<K,V> n = highestLessThan(key);
2402        return (n == nil) ? null : n;
2403      }
2404    
2405      /**
2406       * Returns the the greatest or highest key that is strictly
2407       * less than the specified key, or <code>null</code> if
2408       * there is no such key.
2409       *
2410       * @param key the key relative to the returned entry.
2411       * @return the greatest key less than the given key,
2412       *         or <code>null</code> if there is no such key.
2413       * @throws ClassCastException if the specified key can not
2414       *                            be compared with those in the map.
2415       * @throws NullPointerException if the key is <code>null</code>
2416       *                              and this map either uses natural
2417       *                              ordering or a comparator that does
2418       *                              not permit null keys.
2419       * @since 1.6
2420       */
2421      public K lowerKey(K key)
2422      {
2423        Entry<K,V> e = lowerEntry(key);
2424        return (e == null) ? null : e.getKey();
2425      }
2426    
2427      /**
2428       * Returns a {@link NavigableSet} view of this map's keys. The set is
2429       * backed by the {@link TreeMap}, so changes in one show up in the other.
2430       * Any changes occurring to either while an iteration is taking
2431       * place (with the exception of a {@link Iterator#remove()} operation)
2432       * result in undefined behaviour from the iteration.  The ordering
2433       * The set supports element removal, but not element addition.
2434       *
2435       * @return a {@link NavigableSet} view of the keys.
2436       * @since 1.6
2437       */
2438      public NavigableSet<K> navigableKeySet()
2439      {
2440        if (nKeys == null)
2441          nKeys = new NavigableKeySet();
2442        return nKeys;
2443      }
2444    
2445      /**
2446       * Removes and returns the entry associated with the least
2447       * or lowest key in the map, or <code>null</code> if the map
2448       * is empty.
2449       *
2450       * @return the removed first entry, or <code>null</code> if the
2451       *         map is empty.
2452       * @since 1.6
2453       */
2454      public Entry<K,V> pollFirstEntry()
2455      {
2456        Entry<K,V> e = firstEntry();
2457        if (e != null)
2458          removeNode((Node<K,V>)e);
2459        return e;
2460      }
2461    
2462      /**
2463       * Removes and returns the entry associated with the greatest
2464       * or highest key in the map, or <code>null</code> if the map
2465       * is empty.
2466       *
2467       * @return the removed last entry, or <code>null</code> if the
2468       *         map is empty.
2469       * @since 1.6
2470       */
2471      public Entry<K,V> pollLastEntry()
2472      {
2473        Entry<K,V> e = lastEntry();
2474        if (e != null)
2475          removeNode((Node<K,V>)e);
2476        return e;
2477      }
2478    
2479      /**
2480       * Implementation of {@link #descendingMap()} and associated
2481       * derivatives. This class provides a view of the
2482       * original backing map in reverse order, and throws
2483       * {@link IllegalArgumentException} for attempts to
2484       * access beyond that range.
2485       *
2486       * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
2487       */
2488      private static final class DescendingMap<DK,DV>
2489        implements NavigableMap<DK,DV>
2490      {
2491    
2492        /**
2493         * The cache for {@link #entrySet()}.
2494         */
2495        private Set<Map.Entry<DK,DV>> entries;
2496    
2497        /**
2498         * The cache for {@link #keySet()}.
2499         */
2500        private Set<DK> keys;
2501    
2502        /**
2503         * The cache for {@link #navigableKeySet()}.
2504         */
2505        private NavigableSet<DK> nKeys;
2506    
2507        /**
2508         * The cache for {@link #values()}.
2509         */
2510        private Collection<DV> values;
2511    
2512        /**
2513         * The backing {@link NavigableMap}.
2514         */
2515        private NavigableMap<DK,DV> map;
2516    
2517        /**
2518         * Create a {@link DescendingMap} around the specified
2519         * map.
2520         *
2521         * @param map the map to wrap.
2522         */
2523        public DescendingMap(NavigableMap<DK,DV> map)
2524        {
2525          this.map = map;
2526        }
2527    
2528        public Map.Entry<DK,DV> ceilingEntry(DK key)
2529        {
2530          return map.floorEntry(key);
2531        }
2532    
2533        public DK ceilingKey(DK key)
2534        {
2535          return map.floorKey(key);
2536        }
2537    
2538        public void clear()
2539        {
2540          map.clear();
2541        }
2542    
2543        public Comparator<? super DK> comparator()
2544        {
2545          return Collections.reverseOrder(map.comparator());
2546        }
2547    
2548        public boolean containsKey(Object o)
2549        {
2550          return map.containsKey(o);
2551        }
2552    
2553        public boolean containsValue(Object o)
2554        {
2555          return map.containsValue(o);
2556        }
2557    
2558        public NavigableSet<DK> descendingKeySet()
2559        {
2560          return descendingMap().navigableKeySet();
2561        }
2562    
2563        public NavigableMap<DK,DV> descendingMap()
2564        {
2565          return map;
2566        }
2567    
2568        public Set<Entry<DK,DV>> entrySet()
2569        {
2570          if (entries == null)
2571            entries =
2572              new DescendingSet<Entry<DK,DV>>((NavigableSet<Entry<DK,DV>>)
2573                                              map.entrySet());
2574          return entries;
2575        }
2576    
2577        public boolean equals(Object o)
2578        {
2579          return map.equals(o);
2580        }
2581    
2582        public Entry<DK,DV> firstEntry()
2583        {
2584          return map.lastEntry();
2585        }
2586    
2587        public DK firstKey()
2588        {
2589          return map.lastKey();
2590        }
2591    
2592        public Entry<DK,DV> floorEntry(DK key)
2593        {
2594          return map.ceilingEntry(key);
2595        }
2596    
2597        public DK floorKey(DK key)
2598        {
2599          return map.ceilingKey(key);
2600        }
2601    
2602        public DV get(Object key)
2603        {
2604          return map.get(key);
2605        }
2606    
2607        public int hashCode()
2608        {
2609          return map.hashCode();
2610        }
2611    
2612        public SortedMap<DK,DV> headMap(DK toKey)
2613        {
2614          return headMap(toKey, false);
2615        }
2616    
2617        public NavigableMap<DK,DV> headMap(DK toKey, boolean inclusive)
2618        {
2619          return new DescendingMap(map.tailMap(toKey, inclusive));
2620        }
2621    
2622        public Entry<DK,DV> higherEntry(DK key)
2623        {
2624          return map.lowerEntry(key);
2625        }
2626    
2627        public DK higherKey(DK key)
2628        {
2629          return map.lowerKey(key);
2630        }
2631    
2632        public Set<DK> keySet()
2633        {
2634          if (keys == null)
2635            keys = new DescendingSet<DK>(map.navigableKeySet());
2636          return keys;
2637        }
2638    
2639        public boolean isEmpty()
2640        {
2641          return map.isEmpty();
2642        }
2643    
2644        public Entry<DK,DV> lastEntry()
2645        {
2646          return map.firstEntry();
2647        }
2648    
2649        public DK lastKey()
2650        {
2651          return map.firstKey();
2652        }
2653    
2654        public Entry<DK,DV> lowerEntry(DK key)
2655        {
2656          return map.higherEntry(key);
2657        }
2658    
2659        public DK lowerKey(DK key)
2660        {
2661          return map.higherKey(key);
2662        }
2663    
2664        public NavigableSet<DK> navigableKeySet()
2665        {
2666          if (nKeys == null)
2667            nKeys = new DescendingSet<DK>(map.navigableKeySet());
2668          return nKeys;
2669        }
2670    
2671        public Entry<DK,DV> pollFirstEntry()
2672        {
2673          return pollLastEntry();
2674        }
2675    
2676        public Entry<DK,DV> pollLastEntry()
2677        {
2678          return pollFirstEntry();
2679        }
2680    
2681        public DV put(DK key, DV value)
2682        {
2683          return map.put(key, value);
2684        }
2685    
2686        public void putAll(Map<? extends DK, ? extends DV> m)
2687        {
2688          map.putAll(m);
2689        }
2690    
2691        public DV remove(Object key)
2692        {
2693          return map.remove(key);
2694        }
2695    
2696        public int size()
2697        {
2698          return map.size();
2699        }
2700    
2701        public SortedMap<DK,DV> subMap(DK fromKey, DK toKey)
2702        {
2703          return subMap(fromKey, true, toKey, false);
2704        }
2705    
2706        public NavigableMap<DK,DV> subMap(DK fromKey, boolean fromInclusive,
2707                                          DK toKey, boolean toInclusive)
2708        {
2709          return new DescendingMap(map.subMap(fromKey, fromInclusive,
2710                                              toKey, toInclusive));
2711        }
2712    
2713        public SortedMap<DK,DV> tailMap(DK fromKey)
2714        {
2715          return tailMap(fromKey, true);
2716        }
2717    
2718        public NavigableMap<DK,DV> tailMap(DK fromKey, boolean inclusive)
2719        {
2720          return new DescendingMap(map.headMap(fromKey, inclusive));
2721        }
2722    
2723        public String toString()
2724        {
2725          CPStringBuilder r = new CPStringBuilder("{");
2726          final Iterator<Entry<DK,DV>> it = entrySet().iterator();
2727          while (it.hasNext())
2728          {
2729            final Entry<DK,DV> e = it.next();
2730            r.append(e.getKey());
2731            r.append('=');
2732            r.append(e.getValue());
2733            r.append(", ");
2734          }
2735          r.replace(r.length() - 2, r.length(), "}");
2736          return r.toString();
2737        }
2738    
2739        public Collection<DV> values()
2740        {
2741          if (values == null)
2742            // Create an AbstractCollection with custom implementations of those
2743            // methods that can be overriden easily and efficiently.
2744            values = new AbstractCollection()
2745              {
2746                public int size()
2747                {
2748                  return DescendingMap.this.size();
2749                }
2750    
2751                public Iterator<DV> iterator()
2752                {
2753                  return new Iterator<DV>()
2754                    {
2755                      /** The last Entry returned by a next() call. */
2756                      private Entry<DK,DV> last;
2757    
2758                      /** The next entry that should be returned by next(). */
2759                      private Entry<DK,DV> next = firstEntry();
2760    
2761                      public boolean hasNext()
2762                      {
2763                        return next != null;
2764                      }
2765    
2766                      public DV next()
2767                      {
2768                        if (next == null)
2769                          throw new NoSuchElementException();
2770                        last = next;
2771                        next = higherEntry(last.getKey());
2772    
2773                        return last.getValue();
2774                      }
2775    
2776                      public void remove()
2777                      {
2778                        if (last == null)
2779                          throw new IllegalStateException();
2780    
2781                        DescendingMap.this.remove(last.getKey());
2782                        last = null;
2783                      }
2784                    };
2785                }
2786    
2787                public void clear()
2788                {
2789                  DescendingMap.this.clear();
2790                }
2791              };
2792          return values;
2793        }
2794    
2795      } // class DescendingMap
2796    
2797      /**
2798       * Implementation of {@link #keySet()}.
2799       */
2800      private class KeySet
2801        extends AbstractSet<K>
2802      {
2803    
2804        public int size()
2805        {
2806          return size;
2807        }
2808    
2809        public Iterator<K> iterator()
2810        {
2811          return new TreeIterator(KEYS);
2812        }
2813    
2814        public void clear()
2815        {
2816          TreeMap.this.clear();
2817        }
2818    
2819        public boolean contains(Object o)
2820        {
2821          return containsKey(o);
2822        }
2823    
2824        public boolean remove(Object key)
2825        {
2826          Node<K,V> n = getNode((K) key);
2827          if (n == nil)
2828            return false;
2829          removeNode(n);
2830          return true;
2831        }
2832      } // class KeySet
2833    
2834      /**
2835       * Implementation of {@link #navigableKeySet()}.
2836       *
2837       * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
2838       */
2839      private final class NavigableKeySet
2840        extends KeySet
2841        implements NavigableSet<K>
2842      {
2843    
2844        public K ceiling(K k)
2845        {
2846          return ceilingKey(k);
2847        }
2848    
2849        public Comparator<? super K> comparator()
2850        {
2851          return comparator;
2852        }
2853    
2854        public Iterator<K> descendingIterator()
2855        {
2856          return descendingSet().iterator();
2857        }
2858    
2859        public NavigableSet<K> descendingSet()
2860        {
2861          return new DescendingSet<K>(this);
2862        }
2863    
2864        public K first()
2865        {
2866          return firstKey();
2867        }
2868    
2869        public K floor(K k)
2870        {
2871          return floorKey(k);
2872        }
2873    
2874        public SortedSet<K> headSet(K to)
2875        {
2876          return headSet(to, false);
2877        }
2878    
2879        public NavigableSet<K> headSet(K to, boolean inclusive)
2880        {
2881          return headMap(to, inclusive).navigableKeySet();
2882        }
2883    
2884        public K higher(K k)
2885        {
2886          return higherKey(k);
2887        }
2888    
2889        public K last()
2890        {
2891          return lastKey();
2892        }
2893    
2894        public K lower(K k)
2895        {
2896          return lowerKey(k);
2897        }
2898    
2899        public K pollFirst()
2900        {
2901          return pollFirstEntry().getKey();
2902        }
2903    
2904        public K pollLast()
2905        {
2906          return pollLastEntry().getKey();
2907        }
2908    
2909        public SortedSet<K> subSet(K from, K to)
2910        {
2911          return subSet(from, true, to, false);
2912        }
2913    
2914        public NavigableSet<K> subSet(K from, boolean fromInclusive,
2915                                      K to, boolean toInclusive)
2916        {
2917          return subMap(from, fromInclusive,
2918                        to, toInclusive).navigableKeySet();
2919        }
2920    
2921        public SortedSet<K> tailSet(K from)
2922        {
2923          return tailSet(from, true);
2924        }
2925    
2926        public NavigableSet<K> tailSet(K from, boolean inclusive)
2927        {
2928          return tailMap(from, inclusive).navigableKeySet();
2929        }
2930    
2931    
2932      } // class NavigableKeySet
2933    
2934      /**
2935       * Implementation of {@link #descendingSet()} and associated
2936       * derivatives. This class provides a view of the
2937       * original backing set in reverse order, and throws
2938       * {@link IllegalArgumentException} for attempts to
2939       * access beyond that range.
2940       *
2941       * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
2942       */
2943      private static final class DescendingSet<D>
2944        implements NavigableSet<D>
2945      {
2946    
2947        /**
2948         * The backing {@link NavigableSet}.
2949         */
2950        private NavigableSet<D> set;
2951    
2952        /**
2953         * Create a {@link DescendingSet} around the specified
2954         * set.
2955         *
2956         * @param map the set to wrap.
2957         */
2958        public DescendingSet(NavigableSet<D> set)
2959        {
2960          this.set = set;
2961        }
2962    
2963        public boolean add(D e)
2964        {
2965          return set.add(e);
2966        }
2967    
2968        public boolean addAll(Collection<? extends D> c)
2969        {
2970          return set.addAll(c);
2971        }
2972    
2973        public D ceiling(D e)
2974        {
2975          return set.floor(e);
2976        }
2977    
2978        public void clear()
2979        {
2980          set.clear();
2981        }
2982    
2983        public Comparator<? super D> comparator()
2984        {
2985          return Collections.reverseOrder(set.comparator());
2986        }
2987    
2988        public boolean contains(Object o)
2989        {
2990          return set.contains(o);
2991        }
2992    
2993        public boolean containsAll(Collection<?> c)
2994        {
2995          return set.containsAll(c);
2996        }
2997    
2998        public Iterator<D> descendingIterator()
2999        {
3000          return descendingSet().iterator();
3001        }
3002    
3003        public NavigableSet<D> descendingSet()
3004        {
3005          return set;
3006        }
3007    
3008        public boolean equals(Object o)
3009        {
3010          return set.equals(o);
3011        }
3012    
3013        public D first()
3014        {
3015          return set.last();
3016        }
3017    
3018        public D floor(D e)
3019        {
3020          return set.ceiling(e);
3021        }
3022    
3023        public int hashCode()
3024        {
3025          return set.hashCode();
3026        }
3027    
3028        public SortedSet<D> headSet(D to)
3029        {
3030          return headSet(to, false);
3031        }
3032    
3033        public NavigableSet<D> headSet(D to, boolean inclusive)
3034        {
3035          return new DescendingSet(set.tailSet(to, inclusive));
3036        }
3037    
3038        public D higher(D e)
3039        {
3040          return set.lower(e);
3041        }
3042    
3043        public boolean isEmpty()
3044        {
3045          return set.isEmpty();
3046        }
3047    
3048        public Iterator<D> iterator()
3049        {
3050          return new Iterator<D>()
3051            {
3052    
3053              /** The last element returned by a next() call. */
3054              private D last;
3055    
3056              /** The next element that should be returned by next(). */
3057              private D next = first();
3058    
3059              public boolean hasNext()
3060              {
3061                return next != null;
3062              }
3063    
3064              public D next()
3065              {
3066                if (next == null)
3067                  throw new NoSuchElementException();
3068                last = next;
3069                next = higher(last);
3070    
3071                return last;
3072              }
3073    
3074              public void remove()
3075              {
3076                if (last == null)
3077                  throw new IllegalStateException();
3078    
3079                DescendingSet.this.remove(last);
3080                last = null;
3081              }
3082            };
3083        }
3084    
3085        public D last()
3086        {
3087          return set.first();
3088        }
3089    
3090        public D lower(D e)
3091        {
3092          return set.higher(e);
3093        }
3094    
3095        public D pollFirst()
3096        {
3097          return set.pollLast();
3098        }
3099    
3100        public D pollLast()
3101        {
3102          return set.pollFirst();
3103        }
3104    
3105        public boolean remove(Object o)
3106        {
3107          return set.remove(o);
3108        }
3109    
3110        public boolean removeAll(Collection<?> c)
3111        {
3112          return set.removeAll(c);
3113        }
3114    
3115        public boolean retainAll(Collection<?> c)
3116        {
3117          return set.retainAll(c);
3118        }
3119    
3120        public int size()
3121        {
3122          return set.size();
3123        }
3124    
3125        public SortedSet<D> subSet(D from, D to)
3126        {
3127          return subSet(from, true, to, false);
3128        }
3129    
3130        public NavigableSet<D> subSet(D from, boolean fromInclusive,
3131                                      D to, boolean toInclusive)
3132        {
3133          return new DescendingSet(set.subSet(from, fromInclusive,
3134                                              to, toInclusive));
3135        }
3136    
3137        public SortedSet<D> tailSet(D from)
3138        {
3139          return tailSet(from, true);
3140        }
3141    
3142        public NavigableSet<D> tailSet(D from, boolean inclusive)
3143        {
3144          return new DescendingSet(set.headSet(from, inclusive));
3145        }
3146    
3147        public Object[] toArray()
3148        {
3149          D[] array = (D[]) set.toArray();
3150          Arrays.sort(array, comparator());
3151          return array;
3152        }
3153    
3154        public <T> T[] toArray(T[] a)
3155        {
3156          T[] array = set.toArray(a);
3157          Arrays.sort(array, (Comparator<? super T>) comparator());
3158          return array;
3159        }
3160    
3161        public String toString()
3162        {
3163          CPStringBuilder r = new CPStringBuilder("[");
3164          final Iterator<D> it = iterator();
3165          while (it.hasNext())
3166          {
3167            final D o = it.next();
3168            if (o == this)
3169              r.append("<this>");
3170            else
3171              r.append(o);
3172            r.append(", ");
3173          }
3174          r.replace(r.length() - 2, r.length(), "]");
3175          return r.toString();
3176        }
3177    
3178      } // class DescendingSet
3179    
3180      private class EntrySet
3181        extends AbstractSet<Entry<K,V>>
3182      {
3183        public int size()
3184        {
3185          return size;
3186        }
3187    
3188        public Iterator<Map.Entry<K,V>> iterator()
3189        {
3190          return new TreeIterator(ENTRIES);
3191        }
3192    
3193        public void clear()
3194        {
3195          TreeMap.this.clear();
3196        }
3197    
3198        public boolean contains(Object o)
3199        {
3200          if (! (o instanceof Map.Entry))
3201            return false;
3202          Map.Entry<K,V> me = (Map.Entry<K,V>) o;
3203          Node<K,V> n = getNode(me.getKey());
3204          return n != nil && AbstractSet.equals(me.getValue(), n.value);
3205        }
3206    
3207        public boolean remove(Object o)
3208        {
3209          if (! (o instanceof Map.Entry))
3210            return false;
3211          Map.Entry<K,V> me = (Map.Entry<K,V>) o;
3212          Node<K,V> n = getNode(me.getKey());
3213          if (n != nil && AbstractSet.equals(me.getValue(), n.value))
3214            {
3215              removeNode(n);
3216              return true;
3217            }
3218          return false;
3219        }
3220      }
3221    
3222      private final class NavigableEntrySet
3223        extends EntrySet
3224        implements NavigableSet<Entry<K,V>>
3225      {
3226    
3227        public Entry<K,V> ceiling(Entry<K,V> e)
3228        {
3229          return ceilingEntry(e.getKey());
3230        }
3231    
3232        public Comparator<? super Entry<K,V>> comparator()
3233        {
3234          return new Comparator<Entry<K,V>>()
3235            {
3236              public int compare(Entry<K,V> t1, Entry<K,V> t2)
3237              {
3238                return comparator.compare(t1.getKey(), t2.getKey());
3239              }
3240            };
3241        }
3242    
3243        public Iterator<Entry<K,V>> descendingIterator()
3244        {
3245          return descendingSet().iterator();
3246        }
3247    
3248        public NavigableSet<Entry<K,V>> descendingSet()
3249        {
3250          return new DescendingSet(this);
3251        }
3252    
3253        public Entry<K,V> first()
3254        {
3255          return firstEntry();
3256        }
3257    
3258        public Entry<K,V> floor(Entry<K,V> e)
3259        {
3260          return floorEntry(e.getKey());
3261        }
3262    
3263        public SortedSet<Entry<K,V>> headSet(Entry<K,V> to)
3264        {
3265          return headSet(to, false);
3266        }
3267    
3268        public NavigableSet<Entry<K,V>> headSet(Entry<K,V> to, boolean inclusive)
3269        {
3270          return (NavigableSet<Entry<K,V>>) headMap(to.getKey(), inclusive).entrySet();
3271        }
3272    
3273        public Entry<K,V> higher(Entry<K,V> e)
3274        {
3275          return higherEntry(e.getKey());
3276        }
3277    
3278        public Entry<K,V> last()
3279        {
3280          return lastEntry();
3281        }
3282    
3283        public Entry<K,V> lower(Entry<K,V> e)
3284        {
3285          return lowerEntry(e.getKey());
3286        }
3287    
3288        public Entry<K,V> pollFirst()
3289        {
3290          return pollFirstEntry();
3291        }
3292    
3293        public Entry<K,V> pollLast()
3294        {
3295          return pollLastEntry();
3296        }
3297    
3298        public SortedSet<Entry<K,V>> subSet(Entry<K,V> from, Entry<K,V> to)
3299        {
3300          return subSet(from, true, to, false);
3301        }
3302    
3303        public NavigableSet<Entry<K,V>> subSet(Entry<K,V> from, boolean fromInclusive,
3304                                               Entry<K,V> to, boolean toInclusive)
3305        {
3306          return (NavigableSet<Entry<K,V>>) subMap(from.getKey(), fromInclusive,
3307                                                   to.getKey(), toInclusive).entrySet();
3308        }
3309    
3310        public SortedSet<Entry<K,V>> tailSet(Entry<K,V> from)
3311        {
3312          return tailSet(from, true);
3313        }
3314    
3315        public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive)
3316        {
3317          return (NavigableSet<Entry<K,V>>) tailMap(from.getKey(), inclusive).navigableKeySet();
3318        }
3319    
3320      } // class NavigableEntrySet
3321    
3322    } // class TreeMap