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
005This file is part of GNU Classpath.
006
007GNU Classpath is free software; you can redistribute it and/or modify
008it under the terms of the GNU General Public License as published by
009the Free Software Foundation; either version 2, or (at your option)
010any later version.
011
012GNU Classpath is distributed in the hope that it will be useful, but
013WITHOUT ANY WARRANTY; without even the implied warranty of
014MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
015General Public License for more details.
016
017You should have received a copy of the GNU General Public License
018along with GNU Classpath; see the file COPYING.  If not, write to the
019Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02002110-1301 USA.
021
022Linking this library statically or dynamically with other modules is
023making a combined work based on this library.  Thus, the terms and
024conditions of the GNU General Public License cover the whole
025combination.
026
027As a special exception, the copyright holders of this library give you
028permission to link this library with independent modules to produce an
029executable, regardless of the license terms of these independent
030modules, and to copy and distribute the resulting executable under
031terms of your choice, provided that you also meet, for each linked
032independent module, the terms and conditions of the license of that
033module.  An independent module is a module which is not derived from
034or based on this library.  If you modify this library, you may extend
035this exception to your version of the library, but you are not
036obligated to do so.  If you do not wish to do so, delete this
037exception statement from your version. */
038
039
040package java.util;
041
042import gnu.java.lang.CPStringBuilder;
043
044import java.io.IOException;
045import java.io.ObjectInputStream;
046import java.io.ObjectOutputStream;
047import 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 */
096public 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 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              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