obtained gcc-4.6.4.tar.bz2 from upstream website;upstream

verified gcc-4.6.4.tar.bz2.sig;
imported gcc-4.6.4 source tree from verified upstream tarball.

downloading a git-generated archive based on the 'upstream' tag
should provide you with a source tree that is binary identical
to the one extracted from the above tarball.

if you have obtained the source via the command 'git clone',
however, do note that line-endings of files in your working
directory might differ from line-endings of the respective
files in the upstream repository.

1 files changed, 3322 insertions, 0 deletions

diff --git a/libjava/classpath/java/util/TreeMap.java b/libjava/classpath/java/util/TreeMap.java
new file mode 100644
index 000000000..87c532fc1
--- /dev/null
+++ b/libjava/classpath/java/util/TreeMap.java
@@ -0,0 +1,3322 @@
+/* TreeMap.java -- a class providing a basic Red-Black Tree data structure,
+   mapping Object --> Object
+   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006  Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301 USA.
+
+Linking this library statically or dynamically with other modules is
+making a combined work based on this library.  Thus, the terms and
+conditions of the GNU General Public License cover the whole
+combination.
+
+As a special exception, the copyright holders of this library give you
+permission to link this library with independent modules to produce an
+executable, regardless of the license terms of these independent
+modules, and to copy and distribute the resulting executable under
+terms of your choice, provided that you also meet, for each linked
+independent module, the terms and conditions of the license of that
+module.  An independent module is a module which is not derived from
+or based on this library.  If you modify this library, you may extend
+this exception to your version of the library, but you are not
+obligated to do so.  If you do not wish to do so, delete this
+exception statement from your version. */
+
+
+package java.util;
+
+import gnu.java.lang.CPStringBuilder;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+
+/**
+ * This class provides a red-black tree implementation of the SortedMap
+ * interface.  Elements in the Map will be sorted by either a user-provided
+ * Comparator object, or by the natural ordering of the keys.
+ *
+ * The algorithms are adopted from Corman, Leiserson, and Rivest's
+ * <i>Introduction to Algorithms.</i>  TreeMap guarantees O(log n)
+ * insertion and deletion of elements.  That being said, there is a large
+ * enough constant coefficient in front of that "log n" (overhead involved
+ * in keeping the tree balanced), that TreeMap may not be the best choice
+ * for small collections. If something is already sorted, you may want to
+ * just use a LinkedHashMap to maintain the order while providing O(1) access.
+ *
+ * TreeMap is a part of the JDK1.2 Collections API.  Null keys are allowed
+ * only if a Comparator is used which can deal with them; natural ordering
+ * cannot cope with null.  Null values are always allowed. Note that the
+ * ordering must be <i>consistent with equals</i> to correctly implement
+ * the Map interface. If this condition is violated, the map is still
+ * well-behaved, but you may have suprising results when comparing it to
+ * other maps.<p>
+ *
+ * This implementation is not synchronized. If you need to share this between
+ * multiple threads, do something like:<br>
+ * <code>SortedMap m
+ *       = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
+ *
+ * The iterators are <i>fail-fast</i>, meaning that any structural
+ * modification, except for <code>remove()</code> called on the iterator
+ * itself, cause the iterator to throw a
+ * <code>ConcurrentModificationException</code> rather than exhibit
+ * non-deterministic behavior.
+ *
+ * @author Jon Zeppieri
+ * @author Bryce McKinlay
+ * @author Eric Blake (ebb9@email.byu.edu)
+ * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
+ * @see Map
+ * @see HashMap
+ * @see Hashtable
+ * @see LinkedHashMap
+ * @see Comparable
+ * @see Comparator
+ * @see Collection
+ * @see Collections#synchronizedSortedMap(SortedMap)
+ * @since 1.2
+ * @status updated to 1.6
+ */
+public class TreeMap<K, V> extends AbstractMap<K, V>
+  implements NavigableMap<K, V>, Cloneable, Serializable
+{
+  // Implementation note:
+  // A red-black tree is a binary search tree with the additional properties
+  // that all paths to a leaf node visit the same number of black nodes,
+  // and no red node has red children. To avoid some null-pointer checks,
+  // we use the special node nil which is always black, has no relatives,
+  // and has key and value of null (but is not equal to a mapping of null).
+
+  /**
+   * Compatible with JDK 1.2.
+   */
+  private static final long serialVersionUID = 919286545866124006L;
+
+  /**
+   * Color status of a node. Package visible for use by nested classes.
+   */
+  static final int RED = -1,
+                   BLACK = 1;
+
+  /**
+   * Sentinal node, used to avoid null checks for corner cases and make the
+   * delete rebalance code simpler. The rebalance code must never assign
+   * the parent, left, or right of nil, but may safely reassign the color
+   * to be black. This object must never be used as a key in a TreeMap, or
+   * it will break bounds checking of a SubMap.
+   */
+  static final Node nil = new Node(null, null, BLACK);
+  static
+    {
+      // Nil is self-referential, so we must initialize it after creation.
+      nil.parent = nil;
+      nil.left = nil;
+      nil.right = nil;
+    }
+
+  /**
+   * The root node of this TreeMap.
+   */
+  private transient Node root;
+
+  /**
+   * The size of this TreeMap. Package visible for use by nested classes.
+   */
+  transient int size;
+
+  /**
+   * The cache for {@link #entrySet()}.
+   */
+  private transient Set<Map.Entry<K,V>> entries;
+
+  /**
+   * The cache for {@link #descendingMap()}.
+   */
+  private transient NavigableMap<K,V> descendingMap;
+
+  /**
+   * The cache for {@link #navigableKeySet()}.
+   */
+  private transient NavigableSet<K> nKeys;
+
+  /**
+   * Counts the number of modifications this TreeMap has undergone, used
+   * by Iterators to know when to throw ConcurrentModificationExceptions.
+   * Package visible for use by nested classes.
+   */
+  transient int modCount;
+
+  /**
+   * This TreeMap's comparator, or null for natural ordering.
+   * Package visible for use by nested classes.
+   * @serial the comparator ordering this tree, or null
+   */
+  final Comparator<? super K> comparator;
+
+  /**
+   * Class to represent an entry in the tree. Holds a single key-value pair,
+   * plus pointers to parent and child nodes.
+   *
+   * @author Eric Blake (ebb9@email.byu.edu)
+   */
+  private static final class Node<K, V> extends AbstractMap.SimpleEntry<K, V>
+  {
+    // All fields package visible for use by nested classes.
+    /** The color of this node. */
+    int color;
+
+    /** The left child node. */
+    Node<K, V> left = nil;
+    /** The right child node. */
+    Node<K, V> right = nil;
+    /** The parent node. */
+    Node<K, V> parent = nil;
+
+    /**
+     * Simple constructor.
+     * @param key the key
+     * @param value the value
+     */
+    Node(K key, V value, int color)
+    {
+      super(key, value);
+      this.color = color;
+    }
+  }
+
+  /**
+   * Instantiate a new TreeMap with no elements, using the keys' natural
+   * ordering to sort. All entries in the map must have a key which implements
+   * Comparable, and which are <i>mutually comparable</i>, otherwise map
+   * operations may throw a {@link ClassCastException}. Attempts to use
+   * a null key will throw a {@link NullPointerException}.
+   *
+   * @see Comparable
+   */
+  public TreeMap()
+  {
+    this((Comparator) null);
+  }
+
+  /**
+   * Instantiate a new TreeMap with no elements, using the provided comparator
+   * to sort. All entries in the map must have keys which are mutually
+   * comparable by the Comparator, otherwise map operations may throw a
+   * {@link ClassCastException}.
+   *
+   * @param c the sort order for the keys of this map, or null
+   *        for the natural order
+   */
+  public TreeMap(Comparator<? super K> c)
+  {
+    comparator = c;
+    fabricateTree(0);
+  }
+
+  /**
+   * Instantiate a new TreeMap, initializing it with all of the elements in
+   * the provided Map.  The elements will be sorted using the natural
+   * ordering of the keys. This algorithm runs in n*log(n) time. All entries
+   * in the map must have keys which implement Comparable and are mutually
+   * comparable, otherwise map operations may throw a
+   * {@link ClassCastException}.
+   *
+   * @param map a Map, whose entries will be put into this TreeMap
+   * @throws ClassCastException if the keys in the provided Map are not
+   *         comparable
+   * @throws NullPointerException if map is null
+   * @see Comparable
+   */
+  public TreeMap(Map<? extends K, ? extends V> map)
+  {
+    this((Comparator) null);
+    putAll(map);
+  }
+
+  /**
+   * Instantiate a new TreeMap, initializing it with all of the elements in
+   * the provided SortedMap.  The elements will be sorted using the same
+   * comparator as in the provided SortedMap. This runs in linear time.
+   *
+   * @param sm a SortedMap, whose entries will be put into this TreeMap
+   * @throws NullPointerException if sm is null
+   */
+  public TreeMap(SortedMap<K, ? extends V> sm)
+  {
+    this(sm.comparator());
+    int pos = sm.size();
+    Iterator itr = sm.entrySet().iterator();
+
+    fabricateTree(pos);
+    Node node = firstNode();
+
+    while (--pos >= 0)
+      {
+        Map.Entry me = (Map.Entry) itr.next();
+        node.key = me.getKey();
+        node.value = me.getValue();
+        node = successor(node);
+      }
+  }
+
+  /**
+   * Clears the Map so it has no keys. This is O(1).
+   */
+  public void clear()
+  {
+    if (size > 0)
+      {
+        modCount++;
+        root = nil;
+        size = 0;
+      }
+  }
+
+  /**
+   * Returns a shallow clone of this TreeMap. The Map itself is cloned,
+   * but its contents are not.
+   *
+   * @return the clone
+   */
+  public Object clone()
+  {
+    TreeMap copy = null;
+    try
+      {
+        copy = (TreeMap) super.clone();
+      }
+    catch (CloneNotSupportedException x)
+      {
+      }
+    copy.entries = null;
+    copy.fabricateTree(size);
+
+    Node node = firstNode();
+    Node cnode = copy.firstNode();
+
+    while (node != nil)
+      {
+        cnode.key = node.key;
+        cnode.value = node.value;
+        node = successor(node);
+        cnode = copy.successor(cnode);
+      }
+    return copy;
+  }
+
+  /**
+   * Return the comparator used to sort this map, or null if it is by
+   * natural order.
+   *
+   * @return the map's comparator
+   */
+  public Comparator<? super K> comparator()
+  {
+    return comparator;
+  }
+
+  /**
+   * Returns true if the map contains a mapping for the given key.
+   *
+   * @param key the key to look for
+   * @return true if the key has a mapping
+   * @throws ClassCastException if key is not comparable to map elements
+   * @throws NullPointerException if key is null and the comparator is not
+   *         tolerant of nulls
+   */
+  public boolean containsKey(Object key)
+  {
+    return getNode((K) key) != nil;
+  }
+
+  /**
+   * Returns true if the map contains at least one mapping to the given value.
+   * This requires linear time.
+   *
+   * @param value the value to look for
+   * @return true if the value appears in a mapping
+   */
+  public boolean containsValue(Object value)
+  {
+    Node node = firstNode();
+    while (node != nil)
+      {
+        if (equals(value, node.value))
+          return true;
+        node = successor(node);
+      }
+    return false;
+  }
+
+  /**
+   * Returns a "set view" of this TreeMap's entries. The set is backed by
+   * the TreeMap, so changes in one show up in the other.  The set supports
+   * element removal, but not element addition.<p>
+   *
+   * Note that the iterators for all three views, from keySet(), entrySet(),
+   * and values(), traverse the TreeMap in sorted sequence.
+   *
+   * @return a set view of the entries
+   * @see #keySet()
+   * @see #values()
+   * @see Map.Entry
+   */
+  public Set<Map.Entry<K,V>> entrySet()
+  {
+    if (entries == null)
+      // Create an AbstractSet with custom implementations of those methods
+      // that can be overriden easily and efficiently.
+      entries = new NavigableEntrySet();
+    return entries;
+  }
+
+  /**
+   * Returns the first (lowest) key in the map.
+   *
+   * @return the first key
+   * @throws NoSuchElementException if the map is empty
+   */
+  public K firstKey()
+  {
+    if (root == nil)
+      throw new NoSuchElementException();
+    return firstNode().key;
+  }
+
+  /**
+   * Return the value in this TreeMap associated with the supplied key,
+   * or <code>null</code> if the key maps to nothing.  NOTE: Since the value
+   * could also be null, you must use containsKey to see if this key
+   * actually maps to something.
+   *
+   * @param key the key for which to fetch an associated value
+   * @return what the key maps to, if present
+   * @throws ClassCastException if key is not comparable to elements in the map
+   * @throws NullPointerException if key is null but the comparator does not
+   *         tolerate nulls
+   * @see #put(Object, Object)
+   * @see #containsKey(Object)
+   */
+  public V get(Object key)
+  {
+    // Exploit fact that nil.value == null.
+    return getNode((K) key).value;
+  }
+
+  /**
+   * Returns a view of this Map including all entries with keys less than
+   * <code>toKey</code>. The returned map is backed by the original, so changes
+   * in one appear in the other. The submap will throw an
+   * {@link IllegalArgumentException} for any attempt to access or add an
+   * element beyond the specified cutoff. The returned map does not include
+   * the endpoint; if you want inclusion, pass the successor element
+   * or call <code>headMap(toKey, true)</code>.  This is equivalent to
+   * calling <code>headMap(toKey, false)</code>.
+   *
+   * @param toKey the (exclusive) cutoff point
+   * @return a view of the map less than the cutoff
+   * @throws ClassCastException if <code>toKey</code> is not compatible with
+   *         the comparator (or is not Comparable, for natural ordering)
+   * @throws NullPointerException if toKey is null, but the comparator does not
+   *         tolerate null elements
+   */
+  public SortedMap<K, V> headMap(K toKey)
+  {
+    return headMap(toKey, false);
+  }
+
+  /**
+   * Returns a view of this Map including all entries with keys less than
+   * (or equal to, if <code>inclusive</code> is true) <code>toKey</code>.
+   * The returned map is backed by the original, so changes in one appear
+   * in the other. The submap will throw an {@link IllegalArgumentException}
+   * for any attempt to access or add an element beyond the specified cutoff.
+   *
+   * @param toKey the cutoff point
+   * @param inclusive true if the cutoff point should be included.
+   * @return a view of the map less than (or equal to, if <code>inclusive</code>
+   *         is true) the cutoff.
+   * @throws ClassCastException if <code>toKey</code> is not compatible with
+   *         the comparator (or is not Comparable, for natural ordering)
+   * @throws NullPointerException if toKey is null, but the comparator does not
+   *         tolerate null elements
+   */
+  public NavigableMap<K, V> headMap(K toKey, boolean inclusive)
+  {
+    return new SubMap((K)(Object)nil, inclusive
+                      ? successor(getNode(toKey)).key : toKey);
+  }
+
+  /**
+   * Returns a "set view" of this TreeMap's keys. The set is backed by the
+   * TreeMap, so changes in one show up in the other.  The set supports
+   * element removal, but not element addition.
+   *
+   * @return a set view of the keys
+   * @see #values()
+   * @see #entrySet()
+   */
+  public Set<K> keySet()
+  {
+    if (keys == null)
+      // Create an AbstractSet with custom implementations of those methods
+      // that can be overriden easily and efficiently.
+      keys = new KeySet();
+    return keys;
+  }
+
+  /**
+   * Returns the last (highest) key in the map.
+   *
+   * @return the last key
+   * @throws NoSuchElementException if the map is empty
+   */
+  public K lastKey()
+  {
+    if (root == nil)
+      throw new NoSuchElementException("empty");
+    return lastNode().key;
+  }
+
+  /**
+   * Puts the supplied value into the Map, mapped by the supplied key.
+   * The value may be retrieved by any object which <code>equals()</code>
+   * this key. NOTE: Since the prior value could also be null, you must
+   * first use containsKey if you want to see if you are replacing the
+   * key's mapping.
+   *
+   * @param key the key used to locate the value
+   * @param value the value to be stored in the Map
+   * @return the prior mapping of the key, or null if there was none
+   * @throws ClassCastException if key is not comparable to current map keys
+   * @throws NullPointerException if key is null, but the comparator does
+   *         not tolerate nulls
+   * @see #get(Object)
+   * @see Object#equals(Object)
+   */
+  public V put(K key, V value)
+  {
+    Node<K,V> current = root;
+    Node<K,V> parent = nil;
+    int comparison = 0;
+
+    // Find new node's parent.
+    while (current != nil)
+      {
+        parent = current;
+        comparison = compare(key, current.key);
+        if (comparison > 0)
+          current = current.right;
+        else if (comparison < 0)
+          current = current.left;
+        else // Key already in tree.
+          return current.setValue(value);
+      }
+
+    // Set up new node.
+    Node n = new Node(key, value, RED);
+    n.parent = parent;
+
+    // Insert node in tree.
+    modCount++;
+    size++;
+    if (parent == nil)
+      {
+        // Special case inserting into an empty tree.
+        root = n;
+        return null;
+      }
+    if (comparison > 0)
+      parent.right = n;
+    else
+      parent.left = n;
+
+    // Rebalance after insert.
+    insertFixup(n);
+    return null;
+  }
+
+  /**
+   * Copies all elements of the given map into this TreeMap.  If this map
+   * already has a mapping for a key, the new mapping replaces the current
+   * one.
+   *
+   * @param m the map to be added
+   * @throws ClassCastException if a key in m is not comparable with keys
+   *         in the map
+   * @throws NullPointerException if a key in m is null, and the comparator
+   *         does not tolerate nulls
+   */
+  public void putAll(Map<? extends K, ? extends V> m)
+  {
+    Iterator itr = m.entrySet().iterator();
+    int pos = m.size();
+    while (--pos >= 0)
+      {
+        Map.Entry<K,V> e = (Map.Entry<K,V>) itr.next();
+        put(e.getKey(), e.getValue());
+      }
+  }
+
+  /**
+   * Removes from the TreeMap and returns the value which is mapped by the
+   * supplied key. If the key maps to nothing, then the TreeMap remains
+   * unchanged, and <code>null</code> is returned. NOTE: Since the value
+   * could also be null, you must use containsKey to see if you are
+   * actually removing a mapping.
+   *
+   * @param key the key used to locate the value to remove
+   * @return whatever the key mapped to, if present
+   * @throws ClassCastException if key is not comparable to current map keys
+   * @throws NullPointerException if key is null, but the comparator does
+   *         not tolerate nulls
+   */
+  public V remove(Object key)
+  {
+    Node<K, V> n = getNode((K)key);
+    if (n == nil)
+      return null;
+    // Note: removeNode can alter the contents of n, so save value now.
+    V result = n.value;
+    removeNode(n);
+    return result;
+  }
+
+  /**
+   * Returns the number of key-value mappings currently in this Map.
+   *
+   * @return the size
+   */
+  public int size()
+  {
+    return size;
+  }
+
+  /**
+   * Returns a view of this Map including all entries with keys greater or
+   * equal to <code>fromKey</code> and less than <code>toKey</code> (a
+   * half-open interval). The returned map is backed by the original, so
+   * changes in one appear in the other. The submap will throw an
+   * {@link IllegalArgumentException} for any attempt to access or add an
+   * element beyond the specified cutoffs. The returned map includes the low
+   * endpoint but not the high; if you want to reverse this behavior on
+   * either end, pass in the successor element or call
+   * {@link #subMap(K,boolean,K,boolean)}.  This call is equivalent to
+   * <code>subMap(fromKey, true, toKey, false)</code>.
+   *
+   * @param fromKey the (inclusive) low cutoff point
+   * @param toKey the (exclusive) high cutoff point
+   * @return a view of the map between the cutoffs
+   * @throws ClassCastException if either cutoff is not compatible with
+   *         the comparator (or is not Comparable, for natural ordering)
+   * @throws NullPointerException if fromKey or toKey is null, but the
+   *         comparator does not tolerate null elements
+   * @throws IllegalArgumentException if fromKey is greater than toKey
+   */
+  public SortedMap<K, V> subMap(K fromKey, K toKey)
+  {
+    return subMap(fromKey, true, toKey, false);
+  }
+
+  /**
+   * Returns a view of this Map including all entries with keys greater (or
+   * equal to, if <code>fromInclusive</code> is true) <code>fromKey</code> and
+   * less than (or equal to, if <code>toInclusive</code> is true)
+   * <code>toKey</code>. The returned map is backed by the original, so
+   * changes in one appear in the other. The submap will throw an
+   * {@link IllegalArgumentException} for any attempt to access or add an
+   * element beyond the specified cutoffs.
+   *
+   * @param fromKey the low cutoff point
+   * @param fromInclusive true if the low cutoff point should be included.
+   * @param toKey the high cutoff point
+   * @param toInclusive true if the high cutoff point should be included.
+   * @return a view of the map for the specified range.
+   * @throws ClassCastException if either cutoff is not compatible with
+   *         the comparator (or is not Comparable, for natural ordering)
+   * @throws NullPointerException if fromKey or toKey is null, but the
+   *         comparator does not tolerate null elements
+   * @throws IllegalArgumentException if fromKey is greater than toKey
+   */
+  public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive,
+                                   K toKey, boolean toInclusive)
+  {
+    return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key,
+                      toInclusive ? successor(getNode(toKey)).key : toKey);
+  }
+
+  /**
+   * Returns a view of this Map including all entries with keys greater or
+   * equal to <code>fromKey</code>. The returned map is backed by the
+   * original, so changes in one appear in the other. The submap will throw an
+   * {@link IllegalArgumentException} for any attempt to access or add an
+   * element beyond the specified cutoff. The returned map includes the
+   * endpoint; if you want to exclude it, pass in the successor element.
+   * This is equivalent to calling <code>tailMap(fromKey, true)</code>.
+   *
+   * @param fromKey the (inclusive) low cutoff point
+   * @return a view of the map above the cutoff
+   * @throws ClassCastException if <code>fromKey</code> is not compatible with
+   *         the comparator (or is not Comparable, for natural ordering)
+   * @throws NullPointerException if fromKey is null, but the comparator
+   *         does not tolerate null elements
+   */
+  public SortedMap<K, V> tailMap(K fromKey)
+  {
+    return tailMap(fromKey, true);
+  }
+
+  /**
+   * Returns a view of this Map including all entries with keys greater or
+   * equal to <code>fromKey</code>. The returned map is backed by the
+   * original, so changes in one appear in the other. The submap will throw an
+   * {@link IllegalArgumentException} for any attempt to access or add an
+   * element beyond the specified cutoff. The returned map includes the
+   * endpoint; if you want to exclude it, pass in the successor element.
+   *
+   * @param fromKey the low cutoff point
+   * @param inclusive true if the cutoff point should be included.
+   * @return a view of the map above the cutoff
+   * @throws ClassCastException if <code>fromKey</code> is not compatible with
+   *         the comparator (or is not Comparable, for natural ordering)
+   * @throws NullPointerException if fromKey is null, but the comparator
+   *         does not tolerate null elements
+   */
+  public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive)
+  {
+    return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key,
+                      (K)(Object)nil);
+  }
+
+  /**
+   * Returns a "collection view" (or "bag view") of this TreeMap's values.
+   * The collection is backed by the TreeMap, so changes in one show up
+   * in the other.  The collection supports element removal, but not element
+   * addition.
+   *
+   * @return a bag view of the values
+   * @see #keySet()
+   * @see #entrySet()
+   */
+  public Collection<V> values()
+  {
+    if (values == null)
+      // We don't bother overriding many of the optional methods, as doing so
+      // wouldn't provide any significant performance advantage.
+      values = new AbstractCollection<V>()
+      {
+        public int size()
+        {
+          return size;
+        }
+
+        public Iterator<V> iterator()
+        {
+          return new TreeIterator(VALUES);
+        }
+
+        public void clear()
+        {
+          TreeMap.this.clear();
+        }
+      };
+    return values;
+  }
+
+  /**
+   * Compares two elements by the set comparator, or by natural ordering.
+   * Package visible for use by nested classes.
+   *
+   * @param o1 the first object
+   * @param o2 the second object
+   * @throws ClassCastException if o1 and o2 are not mutually comparable,
+   *         or are not Comparable with natural ordering
+   * @throws NullPointerException if o1 or o2 is null with natural ordering
+   */
+  final int compare(K o1, K o2)
+  {
+    return (comparator == null
+            ? ((Comparable) o1).compareTo(o2)
+            : comparator.compare(o1, o2));
+  }
+
+  /**
+   * Maintain red-black balance after deleting a node.
+   *
+   * @param node the child of the node just deleted, possibly nil
+   * @param parent the parent of the node just deleted, never nil
+   */
+  private void deleteFixup(Node<K,V> node, Node<K,V> parent)
+  {
+    // if (parent == nil)
+    //   throw new InternalError();
+    // If a black node has been removed, we need to rebalance to avoid
+    // violating the "same number of black nodes on any path" rule. If
+    // node is red, we can simply recolor it black and all is well.
+    while (node != root && node.color == BLACK)
+      {
+        if (node == parent.left)
+          {
+            // Rebalance left side.
+            Node<K,V> sibling = parent.right;
+            // if (sibling == nil)
+            //   throw new InternalError();
+            if (sibling.color == RED)
+              {
+                // Case 1: Sibling is red.
+                // Recolor sibling and parent, and rotate parent left.
+                sibling.color = BLACK;
+                parent.color = RED;
+                rotateLeft(parent);
+                sibling = parent.right;
+              }
+
+            if (sibling.left.color == BLACK && sibling.right.color == BLACK)
+              {
+                // Case 2: Sibling has no red children.
+                // Recolor sibling, and move to parent.
+                sibling.color = RED;
+                node = parent;
+                parent = parent.parent;
+              }
+            else
+              {
+                if (sibling.right.color == BLACK)
+                  {
+                    // Case 3: Sibling has red left child.
+                    // Recolor sibling and left child, rotate sibling right.
+                    sibling.left.color = BLACK;
+                    sibling.color = RED;
+                    rotateRight(sibling);
+                    sibling = parent.right;
+                  }
+                // Case 4: Sibling has red right child. Recolor sibling,
+                // right child, and parent, and rotate parent left.
+                sibling.color = parent.color;
+                parent.color = BLACK;
+                sibling.right.color = BLACK;
+                rotateLeft(parent);
+                node = root; // Finished.
+              }
+          }
+        else
+          {
+            // Symmetric "mirror" of left-side case.
+            Node<K,V> sibling = parent.left;
+            // if (sibling == nil)
+            //   throw new InternalError();
+            if (sibling.color == RED)
+              {
+                // Case 1: Sibling is red.
+                // Recolor sibling and parent, and rotate parent right.
+                sibling.color = BLACK;
+                parent.color = RED;
+                rotateRight(parent);
+                sibling = parent.left;
+              }
+
+            if (sibling.right.color == BLACK && sibling.left.color == BLACK)
+              {
+                // Case 2: Sibling has no red children.
+                // Recolor sibling, and move to parent.
+                sibling.color = RED;
+                node = parent;
+                parent = parent.parent;
+              }
+            else
+              {
+                if (sibling.left.color == BLACK)
+                  {
+                    // Case 3: Sibling has red right child.
+                    // Recolor sibling and right child, rotate sibling left.
+                    sibling.right.color = BLACK;
+                    sibling.color = RED;
+                    rotateLeft(sibling);
+                    sibling = parent.left;
+                  }
+                // Case 4: Sibling has red left child. Recolor sibling,
+                // left child, and parent, and rotate parent right.
+                sibling.color = parent.color;
+                parent.color = BLACK;
+                sibling.left.color = BLACK;
+                rotateRight(parent);
+                node = root; // Finished.
+              }
+          }
+      }
+    node.color = BLACK;
+  }
+
+  /**
+   * Construct a perfectly balanced tree consisting of n "blank" nodes. This
+   * permits a tree to be generated from pre-sorted input in linear time.
+   *
+   * @param count the number of blank nodes, non-negative
+   */
+  private void fabricateTree(final int count)
+  {
+    if (count == 0)
+      {
+        root = nil;
+        size = 0;
+        return;
+      }
+
+    // We color every row of nodes black, except for the overflow nodes.
+    // I believe that this is the optimal arrangement. We construct the tree
+    // in place by temporarily linking each node to the next node in the row,
+    // then updating those links to the children when working on the next row.
+
+    // Make the root node.
+    root = new Node(null, null, BLACK);
+    size = count;
+    Node row = root;
+    int rowsize;
+
+    // Fill each row that is completely full of nodes.
+    for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1)
+      {
+        Node parent = row;
+        Node last = null;
+        for (int i = 0; i < rowsize; i += 2)
+          {
+            Node left = new Node(null, null, BLACK);
+            Node right = new Node(null, null, BLACK);
+            left.parent = parent;
+            left.right = right;
+            right.parent = parent;
+            parent.left = left;
+            Node next = parent.right;
+            parent.right = right;
+            parent = next;
+            if (last != null)
+              last.right = left;
+            last = right;
+          }
+        row = row.left;
+      }
+
+    // Now do the partial final row in red.
+    int overflow = count - rowsize;
+    Node parent = row;
+    int i;
+    for (i = 0; i < overflow; i += 2)
+      {
+        Node left = new Node(null, null, RED);
+        Node right = new Node(null, null, RED);
+        left.parent = parent;
+        right.parent = parent;
+        parent.left = left;
+        Node next = parent.right;
+        parent.right = right;
+        parent = next;
+      }
+    // Add a lone left node if necessary.
+    if (i - overflow == 0)
+      {
+        Node left = new Node(null, null, RED);
+        left.parent = parent;
+        parent.left = left;
+        parent = parent.right;
+        left.parent.right = nil;
+      }
+    // Unlink the remaining nodes of the previous row.
+    while (parent != nil)
+      {
+        Node next = parent.right;
+        parent.right = nil;
+        parent = next;
+      }
+  }
+
+  /**
+   * Returns the first sorted node in the map, or nil if empty. Package
+   * visible for use by nested classes.
+   *
+   * @return the first node
+   */
+  final Node<K, V> firstNode()
+  {
+    // Exploit fact that nil.left == nil.
+    Node node = root;
+    while (node.left != nil)
+      node = node.left;
+    return node;
+  }
+
+  /**
+   * Return the TreeMap.Node associated with key, or the nil node if no such
+   * node exists in the tree. Package visible for use by nested classes.
+   *
+   * @param key the key to search for
+   * @return the node where the key is found, or nil
+   */
+  final Node<K, V> getNode(K key)
+  {
+    Node<K,V> current = root;
+    while (current != nil)
+      {
+        int comparison = compare(key, current.key);
+        if (comparison > 0)
+          current = current.right;
+        else if (comparison < 0)
+          current = current.left;
+        else
+          return current;
+      }
+    return current;
+  }
+
+  /**
+   * Find the "highest" node which is &lt; key. If key is nil, return last
+   * node. Package visible for use by nested classes.
+   *
+   * @param key the upper bound, exclusive
+   * @return the previous node
+   */
+  final Node<K,V> highestLessThan(K key)
+  {
+    return highestLessThan(key, false);
+  }
+
+  /**
+   * Find the "highest" node which is &lt; (or equal to,
+   * if <code>equal</code> is true) key. If key is nil,
+   * return last node. Package visible for use by nested
+   * classes.
+   *
+   * @param key the upper bound, exclusive
+   * @param equal true if the key should be returned if found.
+   * @return the previous node
+   */
+  final Node<K,V> highestLessThan(K key, boolean equal)
+  {
+    if (key == nil)
+      return lastNode();
+
+    Node<K,V> last = nil;
+    Node<K,V> current = root;
+    int comparison = 0;
+
+    while (current != nil)
+      {
+        last = current;
+        comparison = compare(key, current.key);
+        if (comparison > 0)
+          current = current.right;
+        else if (comparison < 0)
+          current = current.left;
+        else // Exact match.
+          return (equal ? last : predecessor(last));
+      }
+    return comparison < 0 ? predecessor(last) : last;
+  }
+
+  /**
+   * Maintain red-black balance after inserting a new node.
+   *
+   * @param n the newly inserted node
+   */
+  private void insertFixup(Node<K,V> n)
+  {
+    // Only need to rebalance when parent is a RED node, and while at least
+    // 2 levels deep into the tree (ie: node has a grandparent). Remember
+    // that nil.color == BLACK.
+    while (n.parent.color == RED && n.parent.parent != nil)
+      {
+        if (n.parent == n.parent.parent.left)
+          {
+            Node uncle = n.parent.parent.right;
+            // Uncle may be nil, in which case it is BLACK.
+            if (uncle.color == RED)
+              {
+                // Case 1. Uncle is RED: Change colors of parent, uncle,
+                // and grandparent, and move n to grandparent.
+                n.parent.color = BLACK;
+                uncle.color = BLACK;
+                uncle.parent.color = RED;
+                n = uncle.parent;
+              }
+            else
+              {
+                if (n == n.parent.right)
+                  {
+                    // Case 2. Uncle is BLACK and x is right child.
+                    // Move n to parent, and rotate n left.
+                    n = n.parent;
+                    rotateLeft(n);
+                  }
+                // Case 3. Uncle is BLACK and x is left child.
+                // Recolor parent, grandparent, and rotate grandparent right.
+                n.parent.color = BLACK;
+                n.parent.parent.color = RED;
+                rotateRight(n.parent.parent);
+              }
+          }
+        else
+          {
+            // Mirror image of above code.
+            Node uncle = n.parent.parent.left;
+            // Uncle may be nil, in which case it is BLACK.
+            if (uncle.color == RED)
+              {
+                // Case 1. Uncle is RED: Change colors of parent, uncle,
+                // and grandparent, and move n to grandparent.
+                n.parent.color = BLACK;
+                uncle.color = BLACK;
+                uncle.parent.color = RED;
+                n = uncle.parent;
+              }
+            else
+              {
+                if (n == n.parent.left)
+                {
+                    // Case 2. Uncle is BLACK and x is left child.
+                    // Move n to parent, and rotate n right.
+                    n = n.parent;
+                    rotateRight(n);
+                  }
+                // Case 3. Uncle is BLACK and x is right child.
+                // Recolor parent, grandparent, and rotate grandparent left.
+                n.parent.color = BLACK;
+                n.parent.parent.color = RED;
+                rotateLeft(n.parent.parent);
+              }
+          }
+      }
+    root.color = BLACK;
+  }
+
+  /**
+   * Returns the last sorted node in the map, or nil if empty.
+   *
+   * @return the last node
+   */
+  private Node<K,V> lastNode()
+  {
+    // Exploit fact that nil.right == nil.
+    Node node = root;
+    while (node.right != nil)
+      node = node.right;
+    return node;
+  }
+
+  /**
+   * Find the "lowest" node which is &gt;= key. If key is nil, return either
+   * nil or the first node, depending on the parameter first.  Package visible
+   * for use by nested classes.
+   *
+   * @param key the lower bound, inclusive
+   * @param first true to return the first element instead of nil for nil key
+   * @return the next node
+   */
+  final Node<K,V> lowestGreaterThan(K key, boolean first)
+  {
+    return lowestGreaterThan(key, first, true);
+  }
+
+  /**
+   * Find the "lowest" node which is &gt; (or equal to, if <code>equal</code>
+   * is true) key. If key is nil, return either nil or the first node, depending
+   * on the parameter first.  Package visible for use by nested classes.
+   *
+   * @param key the lower bound, inclusive
+   * @param first true to return the first element instead of nil for nil key
+   * @param equal true if the key should be returned if found.
+   * @return the next node
+   */
+  final Node<K,V> lowestGreaterThan(K key, boolean first, boolean equal)
+  {
+    if (key == nil)
+      return first ? firstNode() : nil;
+
+    Node<K,V> last = nil;
+    Node<K,V> current = root;
+    int comparison = 0;
+
+    while (current != nil)
+      {
+        last = current;
+        comparison = compare(key, current.key);
+        if (comparison > 0)
+          current = current.right;
+        else if (comparison < 0)
+          current = current.left;
+        else
+          return (equal ? current : successor(current));
+      }
+    return comparison > 0 ? successor(last) : last;
+  }
+
+  /**
+   * Return the node preceding the given one, or nil if there isn't one.
+   *
+   * @param node the current node, not nil
+   * @return the prior node in sorted order
+   */
+  private Node<K,V> predecessor(Node<K,V> node)
+  {
+    if (node.left != nil)
+      {
+        node = node.left;
+        while (node.right != nil)
+          node = node.right;
+        return node;
+      }
+
+    Node parent = node.parent;
+    // Exploit fact that nil.left == nil and node is non-nil.
+    while (node == parent.left)
+      {
+        node = parent;
+        parent = node.parent;
+      }
+    return parent;
+  }
+
+  /**
+   * Construct a tree from sorted keys in linear time. Package visible for
+   * use by TreeSet.
+   *
+   * @param s the stream to read from
+   * @param count the number of keys to read
+   * @param readValues true to read values, false to insert "" as the value
+   * @throws ClassNotFoundException if the underlying stream fails
+   * @throws IOException if the underlying stream fails
+   * @see #readObject(ObjectInputStream)
+   * @see TreeSet#readObject(ObjectInputStream)
+   */
+  final void putFromObjStream(ObjectInputStream s, int count,
+                              boolean readValues)
+    throws IOException, ClassNotFoundException
+  {
+    fabricateTree(count);
+    Node node = firstNode();
+
+    while (--count >= 0)
+      {
+        node.key = s.readObject();
+        node.value = readValues ? s.readObject() : "";
+        node = successor(node);
+      }
+  }
+
+  /**
+   * Construct a tree from sorted keys in linear time, with values of "".
+   * Package visible for use by TreeSet, which uses a value type of String.
+   *
+   * @param keys the iterator over the sorted keys
+   * @param count the number of nodes to insert
+   * @see TreeSet#TreeSet(SortedSet)
+   */
+  final void putKeysLinear(Iterator<K> keys, int count)
+  {
+    fabricateTree(count);
+    Node<K,V> node = firstNode();
+
+    while (--count >= 0)
+      {
+        node.key = keys.next();
+        node.value = (V) "";
+        node = successor(node);
+      }
+  }
+
+  /**
+   * Deserializes this object from the given stream.
+   *
+   * @param s the stream to read from
+   * @throws ClassNotFoundException if the underlying stream fails
+   * @throws IOException if the underlying stream fails
+   * @serialData the <i>size</i> (int), followed by key (Object) and value
+   *             (Object) pairs in sorted order
+   */
+  private void readObject(ObjectInputStream s)
+    throws IOException, ClassNotFoundException
+  {
+    s.defaultReadObject();
+    int size = s.readInt();
+    putFromObjStream(s, size, true);
+  }
+
+  /**
+   * Remove node from tree. This will increment modCount and decrement size.
+   * Node must exist in the tree. Package visible for use by nested classes.
+   *
+   * @param node the node to remove
+   */
+  final void removeNode(Node<K,V> node)
+  {
+    Node<K,V> splice;
+    Node<K,V> child;
+
+    modCount++;
+    size--;
+
+    // Find splice, the node at the position to actually remove from the tree.
+    if (node.left == nil)
+      {
+        // Node to be deleted has 0 or 1 children.
+        splice = node;
+        child = node.right;
+      }
+    else if (node.right == nil)
+      {
+        // Node to be deleted has 1 child.
+        splice = node;
+        child = node.left;
+      }
+    else
+      {
+        // Node has 2 children. Splice is node's predecessor, and we swap
+        // its contents into node.
+        splice = node.left;
+        while (splice.right != nil)
+          splice = splice.right;
+        child = splice.left;
+        node.key = splice.key;
+        node.value = splice.value;
+      }
+
+    // Unlink splice from the tree.
+    Node parent = splice.parent;
+    if (child != nil)
+      child.parent = parent;
+    if (parent == nil)
+      {
+        // Special case for 0 or 1 node remaining.
+        root = child;
+        return;
+      }
+    if (splice == parent.left)
+      parent.left = child;
+    else
+      parent.right = child;
+
+    if (splice.color == BLACK)
+      deleteFixup(child, parent);
+  }
+
+  /**
+   * Rotate node n to the left.
+   *
+   * @param node the node to rotate
+   */
+  private void rotateLeft(Node<K,V> node)
+  {
+    Node child = node.right;
+    // if (node == nil || child == nil)
+    //   throw new InternalError();
+
+    // Establish node.right link.
+    node.right = child.left;
+    if (child.left != nil)
+      child.left.parent = node;
+
+    // Establish child->parent link.
+    child.parent = node.parent;
+    if (node.parent != nil)
+      {
+        if (node == node.parent.left)
+          node.parent.left = child;
+        else
+          node.parent.right = child;
+      }
+    else
+      root = child;
+
+    // Link n and child.
+    child.left = node;
+    node.parent = child;
+  }
+
+  /**
+   * Rotate node n to the right.
+   *
+   * @param node the node to rotate
+   */
+  private void rotateRight(Node<K,V> node)
+  {
+    Node child = node.left;
+    // if (node == nil || child == nil)
+    //   throw new InternalError();
+
+    // Establish node.left link.
+    node.left = child.right;
+    if (child.right != nil)
+      child.right.parent = node;
+
+    // Establish child->parent link.
+    child.parent = node.parent;
+    if (node.parent != nil)
+      {
+        if (node == node.parent.right)
+          node.parent.right = child;
+        else
+          node.parent.left = child;
+      }
+    else
+      root = child;
+
+    // Link n and child.
+    child.right = node;
+    node.parent = child;
+  }
+
+  /**
+   * Return the node following the given one, or nil if there isn't one.
+   * Package visible for use by nested classes.
+   *
+   * @param node the current node, not nil
+   * @return the next node in sorted order
+   */
+  final Node<K,V> successor(Node<K,V> node)
+  {
+    if (node.right != nil)
+      {
+        node = node.right;
+        while (node.left != nil)
+          node = node.left;
+        return node;
+      }
+
+    Node<K,V> parent = node.parent;
+    // Exploit fact that nil.right == nil and node is non-nil.
+    while (node == parent.right)
+      {
+        node = parent;
+        parent = parent.parent;
+      }
+    return parent;
+  }
+
+  /**
+   * Serializes this object to the given stream.
+   *
+   * @param s the stream to write to
+   * @throws IOException if the underlying stream fails
+   * @serialData the <i>size</i> (int), followed by key (Object) and value
+   *             (Object) pairs in sorted order
+   */
+  private void writeObject(ObjectOutputStream s) throws IOException
+  {
+    s.defaultWriteObject();
+
+    Node node = firstNode();
+    s.writeInt(size);
+    while (node != nil)
+      {
+        s.writeObject(node.key);
+        s.writeObject(node.value);
+        node = successor(node);
+      }
+  }
+
+  /**
+   * Iterate over TreeMap's entries. This implementation is parameterized
+   * to give a sequential view of keys, values, or entries.
+   *
+   * @author Eric Blake (ebb9@email.byu.edu)
+   */
+  private final class TreeIterator implements Iterator
+  {
+    /**
+     * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
+     * or {@link #ENTRIES}.
+     */
+    private final int type;
+    /** The number of modifications to the backing Map that we know about. */
+    private int knownMod = modCount;
+    /** The last Entry returned by a next() call. */
+    private Node last;
+    /** The next entry that should be returned by next(). */
+    private Node next;
+    /**
+     * The last node visible to this iterator. This is used when iterating
+     * on a SubMap.
+     */
+    private final Node max;
+
+    /**
+     * Construct a new TreeIterator with the supplied type.
+     * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
+     */
+    TreeIterator(int type)
+    {
+      this(type, firstNode(), nil);
+    }
+
+    /**
+     * Construct a new TreeIterator with the supplied type. Iteration will
+     * be from "first" (inclusive) to "max" (exclusive).
+     *
+     * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
+     * @param first where to start iteration, nil for empty iterator
+     * @param max the cutoff for iteration, nil for all remaining nodes
+     */
+    TreeIterator(int type, Node first, Node max)
+    {
+      this.type = type;
+      this.next = first;
+      this.max = max;
+    }
+
+    /**
+     * Returns true if the Iterator has more elements.
+     * @return true if there are more elements
+     */
+    public boolean hasNext()
+    {
+      return next != max;
+    }
+
+    /**
+     * Returns the next element in the Iterator's sequential view.
+     * @return the next element
+     * @throws ConcurrentModificationException if the TreeMap was modified
+     * @throws NoSuchElementException if there is none
+     */
+    public Object next()
+    {
+      if (knownMod != modCount)
+        throw new ConcurrentModificationException();
+      if (next == max)
+        throw new NoSuchElementException();
+      last = next;
+      next = successor(last);
+
+      if (type == VALUES)
+        return last.value;
+      else if (type == KEYS)
+        return last.key;
+      return last;
+    }
+
+    /**
+     * Removes from the backing TreeMap the last element which was fetched
+     * with the <code>next()</code> method.
+     * @throws ConcurrentModificationException if the TreeMap was modified
+     * @throws IllegalStateException if called when there is no last element
+     */
+    public void remove()
+    {
+      if (last == null)
+        throw new IllegalStateException();
+      if (knownMod != modCount)
+        throw new ConcurrentModificationException();
+
+      removeNode(last);
+      last = null;
+      knownMod++;
+    }
+  } // class TreeIterator
+
+  /**
+   * Implementation of {@link #subMap(Object, Object)} and other map
+   * ranges. This class provides a view of a portion of the original backing
+   * map, and throws {@link IllegalArgumentException} for attempts to
+   * access beyond that range.
+   *
+   * @author Eric Blake (ebb9@email.byu.edu)
+   */
+  private final class SubMap
+    extends AbstractMap<K,V>
+    implements NavigableMap<K,V>
+  {
+    /**
+     * The lower range of this view, inclusive, or nil for unbounded.
+     * Package visible for use by nested classes.
+     */
+    final K minKey;
+
+    /**
+     * The upper range of this view, exclusive, or nil for unbounded.
+     * Package visible for use by nested classes.
+     */
+    final K maxKey;
+
+    /**
+     * The cache for {@link #entrySet()}.
+     */
+    private Set<Map.Entry<K,V>> entries;
+
+    /**
+     * The cache for {@link #descendingMap()}.
+     */
+    private NavigableMap<K,V> descendingMap;
+
+    /**
+     * The cache for {@link #navigableKeySet()}.
+     */
+    private NavigableSet<K> nKeys;
+
+    /**
+     * Create a SubMap representing the elements between minKey (inclusive)
+     * and maxKey (exclusive). If minKey is nil, SubMap has no lower bound
+     * (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap).
+     *
+     * @param minKey the lower bound
+     * @param maxKey the upper bound
+     * @throws IllegalArgumentException if minKey &gt; maxKey
+     */
+    SubMap(K minKey, K maxKey)
+    {
+      if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)
+        throw new IllegalArgumentException("fromKey > toKey");
+      this.minKey = minKey;
+      this.maxKey = maxKey;
+    }
+
+    /**
+     * Check if "key" is in within the range bounds for this SubMap. The
+     * lower ("from") SubMap range is inclusive, and the upper ("to") bound
+     * is exclusive. Package visible for use by nested classes.
+     *
+     * @param key the key to check
+     * @return true if the key is in range
+     */
+    boolean keyInRange(K key)
+    {
+      return ((minKey == nil || compare(key, minKey) >= 0)
+              && (maxKey == nil || compare(key, maxKey) < 0));
+    }
+
+    public Entry<K,V> ceilingEntry(K key)
+    {
+      Entry<K,V> n = TreeMap.this.ceilingEntry(key);
+      if (n != null && keyInRange(n.getKey()))
+        return n;
+      return null;
+    }
+
+    public K ceilingKey(K key)
+    {
+      K found = TreeMap.this.ceilingKey(key);
+      if (keyInRange(found))
+        return found;
+      else
+        return null;
+    }
+
+    public NavigableSet<K> descendingKeySet()
+    {
+      return descendingMap().navigableKeySet();
+    }
+
+    public NavigableMap<K,V> descendingMap()
+    {
+      if (descendingMap == null)
+        descendingMap = new DescendingMap(this);
+      return descendingMap;
+    }
+
+    public void clear()
+    {
+      Node next = lowestGreaterThan(minKey, true);
+      Node max = lowestGreaterThan(maxKey, false);
+      while (next != max)
+        {
+          Node current = next;
+          next = successor(current);
+          removeNode(current);
+        }
+    }
+
+    public Comparator<? super K> comparator()
+    {
+      return comparator;
+    }
+
+    public boolean containsKey(Object key)
+    {
+      return keyInRange((K) key) && TreeMap.this.containsKey(key);
+    }
+
+    public boolean containsValue(Object value)
+    {
+      Node node = lowestGreaterThan(minKey, true);
+      Node max = lowestGreaterThan(maxKey, false);
+      while (node != max)
+        {
+          if (equals(value, node.getValue()))
+            return true;
+          node = successor(node);
+        }
+      return false;
+    }
+
+    public Set<Map.Entry<K,V>> entrySet()
+    {
+      if (entries == null)
+        // Create an AbstractSet with custom implementations of those methods
+        // that can be overriden easily and efficiently.
+        entries = new SubMap.NavigableEntrySet();
+      return entries;
+    }
+
+    public Entry<K,V> firstEntry()
+    {
+      Node<K,V> node = lowestGreaterThan(minKey, true);
+      if (node == nil || ! keyInRange(node.key))
+        return null;
+      return node;
+    }
+
+    public K firstKey()
+    {
+      Entry<K,V> e = firstEntry();
+      if (e == null)
+        throw new NoSuchElementException();
+      return e.getKey();
+    }
+
+    public Entry<K,V> floorEntry(K key)
+    {
+      Entry<K,V> n = TreeMap.this.floorEntry(key);
+      if (n != null && keyInRange(n.getKey()))
+        return n;
+      return null;
+    }
+
+    public K floorKey(K key)
+    {
+      K found = TreeMap.this.floorKey(key);
+      if (keyInRange(found))
+        return found;
+      else
+        return null;
+    }
+
+    public V get(Object key)
+    {
+      if (keyInRange((K) key))
+        return TreeMap.this.get(key);
+      return null;
+    }
+
+    public SortedMap<K,V> headMap(K toKey)
+    {
+      return headMap(toKey, false);
+    }
+
+    public NavigableMap<K,V> headMap(K toKey, boolean inclusive)
+    {
+      if (!keyInRange(toKey))
+        throw new IllegalArgumentException("Key outside submap range");
+      return new SubMap(minKey, (inclusive ?
+                                 successor(getNode(toKey)).key : toKey));
+    }
+
+    public Set<K> keySet()
+    {
+      if (this.keys == null)
+        // Create an AbstractSet with custom implementations of those methods
+        // that can be overriden easily and efficiently.
+        this.keys = new SubMap.KeySet();
+      return this.keys;
+    }
+
+    public Entry<K,V> higherEntry(K key)
+    {
+      Entry<K,V> n = TreeMap.this.higherEntry(key);
+      if (n != null && keyInRange(n.getKey()))
+        return n;
+      return null;
+    }
+
+    public K higherKey(K key)
+    {
+      K found = TreeMap.this.higherKey(key);
+      if (keyInRange(found))
+        return found;
+      else
+        return null;
+    }
+
+    public Entry<K,V> lastEntry()
+    {
+      return lowerEntry(maxKey);
+    }
+
+    public K lastKey()
+    {
+      Entry<K,V> e = lastEntry();
+      if (e == null)
+        throw new NoSuchElementException();
+      return e.getKey();
+    }
+
+    public Entry<K,V> lowerEntry(K key)
+    {
+      Entry<K,V> n = TreeMap.this.lowerEntry(key);
+      if (n != null && keyInRange(n.getKey()))
+        return n;
+      return null;
+    }
+
+    public K lowerKey(K key)
+    {
+      K found = TreeMap.this.lowerKey(key);
+      if (keyInRange(found))
+        return found;
+      else
+        return null;
+    }
+
+    public NavigableSet<K> navigableKeySet()
+    {
+      if (this.nKeys == null)
+        // Create an AbstractSet with custom implementations of those methods
+        // that can be overriden easily and efficiently.
+        this.nKeys = new SubMap.NavigableKeySet();
+      return this.nKeys;
+    }
+
+    public Entry<K,V> pollFirstEntry()
+    {
+      Entry<K,V> e = firstEntry();
+      if (e != null)
+        removeNode((Node<K,V>) e);
+      return e;
+    }
+
+    public Entry<K,V> pollLastEntry()
+    {
+      Entry<K,V> e = lastEntry();
+      if (e != null)
+        removeNode((Node<K,V>) e);
+      return e;
+    }
+
+    public V put(K key, V value)
+    {
+      if (! keyInRange(key))
+        throw new IllegalArgumentException("Key outside range");
+      return TreeMap.this.put(key, value);
+    }
+
+    public V remove(Object key)
+    {
+      if (keyInRange((K)key))
+        return TreeMap.this.remove(key);
+      return null;
+    }
+
+    public int size()
+    {
+      Node node = lowestGreaterThan(minKey, true);
+      Node max = lowestGreaterThan(maxKey, false);
+      int count = 0;
+      while (node != max)
+        {
+          count++;
+          node = successor(node);
+        }
+      return count;
+    }
+
+    public SortedMap<K,V> subMap(K fromKey, K toKey)
+    {
+      return subMap(fromKey, true, toKey, false);
+    }
+
+    public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
+                                    K toKey, boolean toInclusive)
+    {
+      if (! keyInRange(fromKey) || ! keyInRange(toKey))
+        throw new IllegalArgumentException("key outside range");
+      return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key,
+                        toInclusive ? successor(getNode(toKey)).key : toKey);
+    }
+
+    public SortedMap<K, V> tailMap(K fromKey)
+    {
+      return tailMap(fromKey, true);
+    }
+
+    public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
+    {
+      if (! keyInRange(fromKey))
+        throw new IllegalArgumentException("key outside range");
+      return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key,
+                        maxKey);
+    }
+
+    public Collection<V> values()
+    {
+      if (this.values == null)
+        // Create an AbstractCollection with custom implementations of those
+        // methods that can be overriden easily and efficiently.
+        this.values = new AbstractCollection()
+        {
+          public int size()
+          {
+            return SubMap.this.size();
+          }
+
+          public Iterator<V> iterator()
+          {
+            Node first = lowestGreaterThan(minKey, true);
+            Node max = lowestGreaterThan(maxKey, false);
+            return new TreeIterator(VALUES, first, max);
+          }
+
+          public void clear()
+          {
+            SubMap.this.clear();
+          }
+        };
+      return this.values;
+    }
+
+    private class KeySet
+      extends AbstractSet<K>
+    {
+      public int size()
+      {
+        return SubMap.this.size();
+      }
+
+      public Iterator<K> iterator()
+      {
+        Node first = lowestGreaterThan(minKey, true);
+        Node max = lowestGreaterThan(maxKey, false);
+        return new TreeIterator(KEYS, first, max);
+      }
+
+      public void clear()
+      {
+        SubMap.this.clear();
+      }
+
+      public boolean contains(Object o)
+      {
+        if (! keyInRange((K) o))
+          return false;
+        return getNode((K) o) != nil;
+      }
+
+      public boolean remove(Object o)
+      {
+        if (! keyInRange((K) o))
+          return false;
+        Node n = getNode((K) o);
+        if (n != nil)
+          {
+            removeNode(n);
+            return true;
+          }
+        return false;
+      }
+
+    } // class SubMap.KeySet
+
+    private final class NavigableKeySet
+      extends KeySet
+      implements NavigableSet<K>
+    {
+
+      public K ceiling(K k)
+      {
+        return SubMap.this.ceilingKey(k);
+      }
+
+      public Comparator<? super K> comparator()
+      {
+        return comparator;
+      }
+
+      public Iterator<K> descendingIterator()
+      {
+        return descendingSet().iterator();
+      }
+
+      public NavigableSet<K> descendingSet()
+      {
+        return new DescendingSet(this);
+      }
+
+      public K first()
+      {
+        return SubMap.this.firstKey();
+      }
+
+      public K floor(K k)
+      {
+        return SubMap.this.floorKey(k);
+      }
+
+      public SortedSet<K> headSet(K to)
+      {
+        return headSet(to, false);
+      }
+
+      public NavigableSet<K> headSet(K to, boolean inclusive)
+      {
+        return SubMap.this.headMap(to, inclusive).navigableKeySet();
+      }
+
+      public K higher(K k)
+      {
+        return SubMap.this.higherKey(k);
+      }
+
+      public K last()
+      {
+        return SubMap.this.lastKey();
+      }
+
+      public K lower(K k)
+      {
+        return SubMap.this.lowerKey(k);
+      }
+
+      public K pollFirst()
+      {
+        return SubMap.this.pollFirstEntry().getKey();
+      }
+
+      public K pollLast()
+      {
+        return SubMap.this.pollLastEntry().getKey();
+      }
+
+      public SortedSet<K> subSet(K from, K to)
+      {
+        return subSet(from, true, to, false);
+      }
+
+      public NavigableSet<K> subSet(K from, boolean fromInclusive,
+                                    K to, boolean toInclusive)
+      {
+        return SubMap.this.subMap(from, fromInclusive,
+                                  to, toInclusive).navigableKeySet();
+      }
+
+      public SortedSet<K> tailSet(K from)
+      {
+        return tailSet(from, true);
+      }
+
+      public NavigableSet<K> tailSet(K from, boolean inclusive)
+      {
+        return SubMap.this.tailMap(from, inclusive).navigableKeySet();
+      }
+
+  } // class SubMap.NavigableKeySet
+
+  /**
+   * Implementation of {@link #entrySet()}.
+   */
+  private class EntrySet
+    extends AbstractSet<Entry<K,V>>
+  {
+
+    public int size()
+    {
+      return SubMap.this.size();
+    }
+
+    public Iterator<Map.Entry<K,V>> iterator()
+    {
+      Node first = lowestGreaterThan(minKey, true);
+      Node max = lowestGreaterThan(maxKey, false);
+      return new TreeIterator(ENTRIES, first, max);
+    }
+
+    public void clear()
+    {
+      SubMap.this.clear();
+    }
+
+    public boolean contains(Object o)
+    {
+      if (! (o instanceof Map.Entry))
+        return false;
+      Map.Entry<K,V> me = (Map.Entry<K,V>) o;
+      K key = me.getKey();
+      if (! keyInRange(key))
+        return false;
+      Node<K,V> n = getNode(key);
+      return n != nil && AbstractSet.equals(me.getValue(), n.value);
+    }
+
+    public boolean remove(Object o)
+    {
+      if (! (o instanceof Map.Entry))
+        return false;
+      Map.Entry<K,V> me = (Map.Entry<K,V>) o;
+      K key = me.getKey();
+      if (! keyInRange(key))
+        return false;
+      Node<K,V> n = getNode(key);
+      if (n != nil && AbstractSet.equals(me.getValue(), n.value))
+        {
+          removeNode(n);
+          return true;
+        }
+      return false;
+    }
+  } // class SubMap.EntrySet
+
+    private final class NavigableEntrySet
+      extends EntrySet
+      implements NavigableSet<Entry<K,V>>
+    {
+
+      public Entry<K,V> ceiling(Entry<K,V> e)
+      {
+        return SubMap.this.ceilingEntry(e.getKey());
+      }
+
+      public Comparator<? super Entry<K,V>> comparator()
+      {
+        return new Comparator<Entry<K,V>>()
+          {
+            public int compare(Entry<K,V> t1, Entry<K,V> t2)
+              {
+                return comparator.compare(t1.getKey(), t2.getKey());
+              }
+          };
+      }
+
+      public Iterator<Entry<K,V>> descendingIterator()
+      {
+        return descendingSet().iterator();
+      }
+
+      public NavigableSet<Entry<K,V>> descendingSet()
+      {
+        return new DescendingSet(this);
+      }
+
+      public Entry<K,V> first()
+      {
+        return SubMap.this.firstEntry();
+      }
+
+      public Entry<K,V> floor(Entry<K,V> e)
+      {
+        return SubMap.this.floorEntry(e.getKey());
+      }
+
+      public SortedSet<Entry<K,V>> headSet(Entry<K,V> to)
+      {
+        return headSet(to, false);
+      }
+
+      public NavigableSet<Entry<K,V>> headSet(Entry<K,V> to, boolean inclusive)
+      {
+        return (NavigableSet<Entry<K,V>>)
+          SubMap.this.headMap(to.getKey(), inclusive).entrySet();
+      }
+
+      public Entry<K,V> higher(Entry<K,V> e)
+      {
+        return SubMap.this.higherEntry(e.getKey());
+      }
+
+      public Entry<K,V> last()
+      {
+        return SubMap.this.lastEntry();
+      }
+
+      public Entry<K,V> lower(Entry<K,V> e)
+      {
+        return SubMap.this.lowerEntry(e.getKey());
+      }
+
+      public Entry<K,V> pollFirst()
+      {
+        return SubMap.this.pollFirstEntry();
+      }
+
+      public Entry<K,V> pollLast()
+      {
+        return SubMap.this.pollLastEntry();
+      }
+
+      public SortedSet<Entry<K,V>> subSet(Entry<K,V> from, Entry<K,V> to)
+      {
+        return subSet(from, true, to, false);
+      }
+
+      public NavigableSet<Entry<K,V>> subSet(Entry<K,V> from, boolean fromInclusive,
+                                             Entry<K,V> to, boolean toInclusive)
+      {
+        return (NavigableSet<Entry<K,V>>)
+          SubMap.this.subMap(from.getKey(), fromInclusive,
+                             to.getKey(), toInclusive).entrySet();
+      }
+
+      public SortedSet<Entry<K,V>> tailSet(Entry<K,V> from)
+      {
+        return tailSet(from, true);
+      }
+
+      public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive)
+      {
+        return (NavigableSet<Entry<K,V>>)
+          SubMap.this.tailMap(from.getKey(), inclusive).navigableKeySet();
+      }
+
+  } // class SubMap.NavigableEntrySet
+
+} // class SubMap
+
+  /**
+   * Returns the entry associated with the least or lowest key
+   * that is greater than or equal to the specified key, or
+   * <code>null</code> if there is no such key.
+   *
+   * @param key the key relative to the returned entry.
+   * @return the entry with the least key greater than or equal
+   *         to the given key, or <code>null</code> if there is
+   *         no such key.
+   * @throws ClassCastException if the specified key can not
+   *                            be compared with those in the map.
+   * @throws NullPointerException if the key is <code>null</code>
+   *                              and this map either uses natural
+   *                              ordering or a comparator that does
+   *                              not permit null keys.
+   * @since 1.6
+   */
+  public Entry<K,V> ceilingEntry(K key)
+  {
+    Node<K,V> n = lowestGreaterThan(key, false);
+    return (n == nil) ? null : n;
+  }
+
+  /**
+   * Returns the the least or lowest key that is greater than
+   * or equal to the specified key, or <code>null</code> if
+   * there is no such key.
+   *
+   * @param key the key relative to the returned entry.
+   * @return the least key greater than or equal to the given key,
+   *         or <code>null</code> if there is no such key.
+   * @throws ClassCastException if the specified key can not
+   *                            be compared with those in the map.
+   * @throws NullPointerException if the key is <code>null</code>
+   *                              and this map either uses natural
+   *                              ordering or a comparator that does
+   *                              not permit null keys.
+   * @since 1.6
+   */
+  public K ceilingKey(K key)
+  {
+    Entry<K,V> e = ceilingEntry(key);
+    return (e == null) ? null : e.getKey();
+  }
+
+  /**
+   * Returns a reverse ordered {@link NavigableSet} view of this
+   * map's keys. The set is backed by the {@link TreeMap}, so changes
+   * in one show up in the other.  The set supports element removal,
+   * but not element addition.
+   *
+   * @return a reverse ordered set view of the keys.
+   * @since 1.6
+   * @see #descendingMap()
+   */
+  public NavigableSet<K> descendingKeySet()
+  {
+    return descendingMap().navigableKeySet();
+  }
+
+  /**
+   * Returns a view of the map in reverse order.  The descending map
+   * is backed by the original map, so that changes affect both maps.
+   * Any changes occurring to either map while an iteration is taking
+   * place (with the exception of a {@link Iterator#remove()} operation)
+   * result in undefined behaviour from the iteration.  The ordering
+   * of the descending map is the same as for a map with a
+   * {@link Comparator} given by {@link Collections#reverseOrder()},
+   * and calling {@link #descendingMap()} on the descending map itself
+   * results in a view equivalent to the original map.
+   *
+   * @return a reverse order view of the map.
+   * @since 1.6
+   */
+  public NavigableMap<K,V> descendingMap()
+  {
+    if (descendingMap == null)
+      descendingMap = new DescendingMap<K,V>(this);
+    return descendingMap;
+  }
+
+  /**
+   * Returns the entry associated with the least or lowest key
+   * in the map, or <code>null</code> if the map is empty.
+   *
+   * @return the lowest entry, or <code>null</code> if the map
+   *         is empty.
+   * @since 1.6
+   */
+  public Entry<K,V> firstEntry()
+  {
+    Node<K,V> n = firstNode();
+    return (n == nil) ? null : n;
+  }
+
+  /**
+   * Returns the entry associated with the greatest or highest key
+   * that is less than or equal to the specified key, or
+   * <code>null</code> if there is no such key.
+   *
+   * @param key the key relative to the returned entry.
+   * @return the entry with the greatest key less than or equal
+   *         to the given key, or <code>null</code> if there is
+   *         no such key.
+   * @throws ClassCastException if the specified key can not
+   *                            be compared with those in the map.
+   * @throws NullPointerException if the key is <code>null</code>
+   *                              and this map either uses natural
+   *                              ordering or a comparator that does
+   *                              not permit null keys.
+   * @since 1.6
+   */
+  public Entry<K,V> floorEntry(K key)
+  {
+    Node<K,V> n = highestLessThan(key, true);
+    return (n == nil) ? null : n;
+  }
+
+  /**
+   * Returns the the greatest or highest key that is less than
+   * or equal to the specified key, or <code>null</code> if
+   * there is no such key.
+   *
+   * @param key the key relative to the returned entry.
+   * @return the greatest key less than or equal to the given key,
+   *         or <code>null</code> if there is no such key.
+   * @throws ClassCastException if the specified key can not
+   *                            be compared with those in the map.
+   * @throws NullPointerException if the key is <code>null</code>
+   *                              and this map either uses natural
+   *                              ordering or a comparator that does
+   *                              not permit null keys.
+   * @since 1.6
+   */
+  public K floorKey(K key)
+  {
+    Entry<K,V> e = floorEntry(key);
+    return (e == null) ? null : e.getKey();
+  }
+
+  /**
+   * Returns the entry associated with the least or lowest key
+   * that is strictly greater than the specified key, or
+   * <code>null</code> if there is no such key.
+   *
+   * @param key the key relative to the returned entry.
+   * @return the entry with the least key greater than
+   *         the given key, or <code>null</code> if there is
+   *         no such key.
+   * @throws ClassCastException if the specified key can not
+   *                            be compared with those in the map.
+   * @throws NullPointerException if the key is <code>null</code>
+   *                              and this map either uses natural
+   *                              ordering or a comparator that does
+   *                              not permit null keys.
+   * @since 1.6
+   */
+  public Entry<K,V> higherEntry(K key)
+  {
+    Node<K,V> n = lowestGreaterThan(key, false, false);
+    return (n == nil) ? null : n;
+  }
+
+  /**
+   * Returns the the least or lowest key that is strictly
+   * greater than the specified key, or <code>null</code> if
+   * there is no such key.
+   *
+   * @param key the key relative to the returned entry.
+   * @return the least key greater than the given key,
+   *         or <code>null</code> if there is no such key.
+   * @throws ClassCastException if the specified key can not
+   *                            be compared with those in the map.
+   * @throws NullPointerException if the key is <code>null</code>
+   *                              and this map either uses natural
+   *                              ordering or a comparator that does
+   *                              not permit null keys.
+   * @since 1.6
+   */
+  public K higherKey(K key)
+  {
+    Entry<K,V> e = higherEntry(key);
+    return (e == null) ? null : e.getKey();
+  }
+
+  /**
+   * Returns the entry associated with the greatest or highest key
+   * in the map, or <code>null</code> if the map is empty.
+   *
+   * @return the highest entry, or <code>null</code> if the map
+   *         is empty.
+   * @since 1.6
+   */
+  public Entry<K,V> lastEntry()
+  {
+    Node<K,V> n = lastNode();
+    return (n == nil) ? null : n;
+  }
+
+  /**
+   * Returns the entry associated with the greatest or highest key
+   * that is strictly less than the specified key, or
+   * <code>null</code> if there is no such key.
+   *
+   * @param key the key relative to the returned entry.
+   * @return the entry with the greatest key less than
+   *         the given key, or <code>null</code> if there is
+   *         no such key.
+   * @throws ClassCastException if the specified key can not
+   *                            be compared with those in the map.
+   * @throws NullPointerException if the key is <code>null</code>
+   *                              and this map either uses natural
+   *                              ordering or a comparator that does
+   *                              not permit null keys.
+   * @since 1.6
+   */
+  public Entry<K,V> lowerEntry(K key)
+  {
+    Node<K,V> n = highestLessThan(key);
+    return (n == nil) ? null : n;
+  }
+
+  /**
+   * Returns the the greatest or highest key that is strictly
+   * less than the specified key, or <code>null</code> if
+   * there is no such key.
+   *
+   * @param key the key relative to the returned entry.
+   * @return the greatest key less than the given key,
+   *         or <code>null</code> if there is no such key.
+   * @throws ClassCastException if the specified key can not
+   *                            be compared with those in the map.
+   * @throws NullPointerException if the key is <code>null</code>
+   *                              and this map either uses natural
+   *                              ordering or a comparator that does
+   *                              not permit null keys.
+   * @since 1.6
+   */
+  public K lowerKey(K key)
+  {
+    Entry<K,V> e = lowerEntry(key);
+    return (e == null) ? null : e.getKey();
+  }
+
+  /**
+   * Returns a {@link NavigableSet} view of this map's keys. The set is
+   * backed by the {@link TreeMap}, so changes in one show up in the other.
+   * Any changes occurring to either while an iteration is taking
+   * place (with the exception of a {@link Iterator#remove()} operation)
+   * result in undefined behaviour from the iteration.  The ordering
+   * The set supports element removal, but not element addition.
+   *
+   * @return a {@link NavigableSet} view of the keys.
+   * @since 1.6
+   */
+  public NavigableSet<K> navigableKeySet()
+  {
+    if (nKeys == null)
+      nKeys = new NavigableKeySet();
+    return nKeys;
+  }
+
+  /**
+   * Removes and returns the entry associated with the least
+   * or lowest key in the map, or <code>null</code> if the map
+   * is empty.
+   *
+   * @return the removed first entry, or <code>null</code> if the
+   *         map is empty.
+   * @since 1.6
+   */
+  public Entry<K,V> pollFirstEntry()
+  {
+    Entry<K,V> e = firstEntry();
+    if (e != null)
+      removeNode((Node<K,V>)e);
+    return e;
+  }
+
+  /**
+   * Removes and returns the entry associated with the greatest
+   * or highest key in the map, or <code>null</code> if the map
+   * is empty.
+   *
+   * @return the removed last entry, or <code>null</code> if the
+   *         map is empty.
+   * @since 1.6
+   */
+  public Entry<K,V> pollLastEntry()
+  {
+    Entry<K,V> e = lastEntry();
+    if (e != null)
+      removeNode((Node<K,V>)e);
+    return e;
+  }
+
+  /**
+   * Implementation of {@link #descendingMap()} and associated
+   * derivatives. This class provides a view of the
+   * original backing map in reverse order, and throws
+   * {@link IllegalArgumentException} for attempts to
+   * access beyond that range.
+   *
+   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
+   */
+  private static final class DescendingMap<DK,DV>
+    implements NavigableMap<DK,DV>
+  {
+
+    /**
+     * The cache for {@link #entrySet()}.
+     */
+    private Set<Map.Entry<DK,DV>> entries;
+
+    /**
+     * The cache for {@link #keySet()}.
+     */
+    private Set<DK> keys;
+
+    /**
+     * The cache for {@link #navigableKeySet()}.
+     */
+    private NavigableSet<DK> nKeys;
+
+    /**
+     * The cache for {@link #values()}.
+     */
+    private Collection<DV> values;
+
+    /**
+     * The backing {@link NavigableMap}.
+     */
+    private NavigableMap<DK,DV> map;
+
+    /**
+     * Create a {@link DescendingMap} around the specified
+     * map.
+     *
+     * @param map the map to wrap.
+     */
+    public DescendingMap(NavigableMap<DK,DV> map)
+    {
+      this.map = map;
+    }
+
+    public Map.Entry<DK,DV> ceilingEntry(DK key)
+    {
+      return map.floorEntry(key);
+    }
+
+    public DK ceilingKey(DK key)
+    {
+      return map.floorKey(key);
+    }
+
+    public void clear()
+    {
+      map.clear();
+    }
+
+    public Comparator<? super DK> comparator()
+    {
+      return Collections.reverseOrder(map.comparator());
+    }
+
+    public boolean containsKey(Object o)
+    {
+      return map.containsKey(o);
+    }
+
+    public boolean containsValue(Object o)
+    {
+      return map.containsValue(o);
+    }
+
+    public NavigableSet<DK> descendingKeySet()
+    {
+      return descendingMap().navigableKeySet();
+    }
+
+    public NavigableMap<DK,DV> descendingMap()
+    {
+      return map;
+    }
+
+    public Set<Entry<DK,DV>> entrySet()
+    {
+      if (entries == null)
+        entries =
+          new DescendingSet<Entry<DK,DV>>((NavigableSet<Entry<DK,DV>>)
+                                          map.entrySet());
+      return entries;
+    }
+
+    public boolean equals(Object o)
+    {
+      return map.equals(o);
+    }
+
+    public Entry<DK,DV> firstEntry()
+    {
+      return map.lastEntry();
+    }
+
+    public DK firstKey()
+    {
+      return map.lastKey();
+    }
+
+    public Entry<DK,DV> floorEntry(DK key)
+    {
+      return map.ceilingEntry(key);
+    }
+
+    public DK floorKey(DK key)
+    {
+      return map.ceilingKey(key);
+    }
+
+    public DV get(Object key)
+    {
+      return map.get(key);
+    }
+
+    public int hashCode()
+    {
+      return map.hashCode();
+    }
+
+    public SortedMap<DK,DV> headMap(DK toKey)
+    {
+      return headMap(toKey, false);
+    }
+
+    public NavigableMap<DK,DV> headMap(DK toKey, boolean inclusive)
+    {
+      return new DescendingMap(map.tailMap(toKey, inclusive));
+    }
+
+    public Entry<DK,DV> higherEntry(DK key)
+    {
+      return map.lowerEntry(key);
+    }
+
+    public DK higherKey(DK key)
+    {
+      return map.lowerKey(key);
+    }
+
+    public Set<DK> keySet()
+    {
+      if (keys == null)
+        keys = new DescendingSet<DK>(map.navigableKeySet());
+      return keys;
+    }
+
+    public boolean isEmpty()
+    {
+      return map.isEmpty();
+    }
+
+    public Entry<DK,DV> lastEntry()
+    {
+      return map.firstEntry();
+    }
+
+    public DK lastKey()
+    {
+      return map.firstKey();
+    }
+
+    public Entry<DK,DV> lowerEntry(DK key)
+    {
+      return map.higherEntry(key);
+    }
+
+    public DK lowerKey(DK key)
+    {
+      return map.higherKey(key);
+    }
+
+    public NavigableSet<DK> navigableKeySet()
+    {
+      if (nKeys == null)
+        nKeys = new DescendingSet<DK>(map.navigableKeySet());
+      return nKeys;
+    }
+
+    public Entry<DK,DV> pollFirstEntry()
+    {
+      return pollLastEntry();
+    }
+
+    public Entry<DK,DV> pollLastEntry()
+    {
+      return pollFirstEntry();
+    }
+
+    public DV put(DK key, DV value)
+    {
+      return map.put(key, value);
+    }
+
+    public void putAll(Map<? extends DK, ? extends DV> m)
+    {
+      map.putAll(m);
+    }
+
+    public DV remove(Object key)
+    {
+      return map.remove(key);
+    }
+
+    public int size()
+    {
+      return map.size();
+    }
+
+    public SortedMap<DK,DV> subMap(DK fromKey, DK toKey)
+    {
+      return subMap(fromKey, true, toKey, false);
+    }
+
+    public NavigableMap<DK,DV> subMap(DK fromKey, boolean fromInclusive,
+                                      DK toKey, boolean toInclusive)
+    {
+      return new DescendingMap(map.subMap(fromKey, fromInclusive,
+                                          toKey, toInclusive));
+    }
+
+    public SortedMap<DK,DV> tailMap(DK fromKey)
+    {
+      return tailMap(fromKey, true);
+    }
+
+    public NavigableMap<DK,DV> tailMap(DK fromKey, boolean inclusive)
+    {
+      return new DescendingMap(map.headMap(fromKey, inclusive));
+    }
+
+    public String toString()
+    {
+      CPStringBuilder r = new CPStringBuilder("{");
+      final Iterator<Entry<DK,DV>> it = entrySet().iterator();
+      while (it.hasNext())
+      {
+        final Entry<DK,DV> e = it.next();
+        r.append(e.getKey());
+        r.append('=');
+        r.append(e.getValue());
+        r.append(", ");
+      }
+      r.replace(r.length() - 2, r.length(), "}");
+      return r.toString();
+    }
+
+    public Collection<DV> values()
+    {
+      if (values == null)
+        // Create an AbstractCollection with custom implementations of those
+        // methods that can be overriden easily and efficiently.
+        values = new AbstractCollection()
+          {
+            public int size()
+            {
+              return DescendingMap.this.size();
+            }
+
+            public Iterator<DV> iterator()
+            {
+              return new Iterator<DV>()
+                {
+                  /** The last Entry returned by a next() call. */
+                  private Entry<DK,DV> last;
+
+                  /** The next entry that should be returned by next(). */
+                  private Entry<DK,DV> next = firstEntry();
+
+                  public boolean hasNext()
+                  {
+                    return next != null;
+                  }
+
+                  public DV next()
+                  {
+                    if (next == null)
+                      throw new NoSuchElementException();
+                    last = next;
+                    next = higherEntry(last.getKey());
+
+                    return last.getValue();
+                  }
+
+                  public void remove()
+                  {
+                    if (last == null)
+                      throw new IllegalStateException();
+
+                    DescendingMap.this.remove(last.getKey());
+                    last = null;
+                  }
+                };
+            }
+
+            public void clear()
+            {
+              DescendingMap.this.clear();
+            }
+          };
+      return values;
+    }
+
+  } // class DescendingMap
+
+  /**
+   * Implementation of {@link #keySet()}.
+   */
+  private class KeySet
+    extends AbstractSet<K>
+  {
+
+    public int size()
+    {
+      return size;
+    }
+
+    public Iterator<K> iterator()
+    {
+      return new TreeIterator(KEYS);
+    }
+
+    public void clear()
+    {
+      TreeMap.this.clear();
+    }
+
+    public boolean contains(Object o)
+    {
+      return containsKey(o);
+    }
+
+    public boolean remove(Object key)
+    {
+      Node<K,V> n = getNode((K) key);
+      if (n == nil)
+        return false;
+      removeNode(n);
+      return true;
+    }
+  } // class KeySet
+
+  /**
+   * Implementation of {@link #navigableKeySet()}.
+   *
+   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
+   */
+  private final class NavigableKeySet
+    extends KeySet
+    implements NavigableSet<K>
+  {
+
+    public K ceiling(K k)
+    {
+      return ceilingKey(k);
+    }
+
+    public Comparator<? super K> comparator()
+    {
+      return comparator;
+    }
+
+    public Iterator<K> descendingIterator()
+    {
+      return descendingSet().iterator();
+    }
+
+    public NavigableSet<K> descendingSet()
+    {
+      return new DescendingSet<K>(this);
+    }
+
+    public K first()
+    {
+      return firstKey();
+    }
+
+    public K floor(K k)
+    {
+      return floorKey(k);
+    }
+
+    public SortedSet<K> headSet(K to)
+    {
+      return headSet(to, false);
+    }
+
+    public NavigableSet<K> headSet(K to, boolean inclusive)
+    {
+      return headMap(to, inclusive).navigableKeySet();
+    }
+
+    public K higher(K k)
+    {
+      return higherKey(k);
+    }
+
+    public K last()
+    {
+      return lastKey();
+    }
+
+    public K lower(K k)
+    {
+      return lowerKey(k);
+    }
+
+    public K pollFirst()
+    {
+      return pollFirstEntry().getKey();
+    }
+
+    public K pollLast()
+    {
+      return pollLastEntry().getKey();
+    }
+
+    public SortedSet<K> subSet(K from, K to)
+    {
+      return subSet(from, true, to, false);
+    }
+
+    public NavigableSet<K> subSet(K from, boolean fromInclusive,
+                                  K to, boolean toInclusive)
+    {
+      return subMap(from, fromInclusive,
+                    to, toInclusive).navigableKeySet();
+    }
+
+    public SortedSet<K> tailSet(K from)
+    {
+      return tailSet(from, true);
+    }
+
+    public NavigableSet<K> tailSet(K from, boolean inclusive)
+    {
+      return tailMap(from, inclusive).navigableKeySet();
+    }
+
+
+  } // class NavigableKeySet
+
+  /**
+   * Implementation of {@link #descendingSet()} and associated
+   * derivatives. This class provides a view of the
+   * original backing set in reverse order, and throws
+   * {@link IllegalArgumentException} for attempts to
+   * access beyond that range.
+   *
+   * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
+   */
+  private static final class DescendingSet<D>
+    implements NavigableSet<D>
+  {
+
+    /**
+     * The backing {@link NavigableSet}.
+     */
+    private NavigableSet<D> set;
+
+    /**
+     * Create a {@link DescendingSet} around the specified
+     * set.
+     *
+     * @param map the set to wrap.
+     */
+    public DescendingSet(NavigableSet<D> set)
+    {
+      this.set = set;
+    }
+
+    public boolean add(D e)
+    {
+      return set.add(e);
+    }
+
+    public boolean addAll(Collection<? extends D> c)
+    {
+      return set.addAll(c);
+    }
+
+    public D ceiling(D e)
+    {
+      return set.floor(e);
+    }
+
+    public void clear()
+    {
+      set.clear();
+    }
+
+    public Comparator<? super D> comparator()
+    {
+      return Collections.reverseOrder(set.comparator());
+    }
+
+    public boolean contains(Object o)
+    {
+      return set.contains(o);
+    }
+
+    public boolean containsAll(Collection<?> c)
+    {
+      return set.containsAll(c);
+    }
+
+    public Iterator<D> descendingIterator()
+    {
+      return descendingSet().iterator();
+    }
+
+    public NavigableSet<D> descendingSet()
+    {
+      return set;
+    }
+
+    public boolean equals(Object o)
+    {
+      return set.equals(o);
+    }
+
+    public D first()
+    {
+      return set.last();
+    }
+
+    public D floor(D e)
+    {
+      return set.ceiling(e);
+    }
+
+    public int hashCode()
+    {
+      return set.hashCode();
+    }
+
+    public SortedSet<D> headSet(D to)
+    {
+      return headSet(to, false);
+    }
+
+    public NavigableSet<D> headSet(D to, boolean inclusive)
+    {
+      return new DescendingSet(set.tailSet(to, inclusive));
+    }
+
+    public D higher(D e)
+    {
+      return set.lower(e);
+    }
+
+    public boolean isEmpty()
+    {
+      return set.isEmpty();
+    }
+
+    public Iterator<D> iterator()
+    {
+      return new Iterator<D>()
+        {
+
+          /** The last element returned by a next() call. */
+          private D last;
+
+          /** The next element that should be returned by next(). */
+          private D next = first();
+
+          public boolean hasNext()
+          {
+            return next != null;
+          }
+
+          public D next()
+          {
+            if (next == null)
+              throw new NoSuchElementException();
+            last = next;
+            next = higher(last);
+
+            return last;
+          }
+
+          public void remove()
+          {
+            if (last == null)
+              throw new IllegalStateException();
+
+            DescendingSet.this.remove(last);
+            last = null;
+          }
+        };
+    }
+
+    public D last()
+    {
+      return set.first();
+    }
+
+    public D lower(D e)
+    {
+      return set.higher(e);
+    }
+
+    public D pollFirst()
+    {
+      return set.pollLast();
+    }
+
+    public D pollLast()
+    {
+      return set.pollFirst();
+    }
+
+    public boolean remove(Object o)
+    {
+      return set.remove(o);
+    }
+
+    public boolean removeAll(Collection<?> c)
+    {
+      return set.removeAll(c);
+    }
+
+    public boolean retainAll(Collection<?> c)
+    {
+      return set.retainAll(c);
+    }
+
+    public int size()
+    {
+      return set.size();
+    }
+
+    public SortedSet<D> subSet(D from, D to)
+    {
+      return subSet(from, true, to, false);
+    }
+
+    public NavigableSet<D> subSet(D from, boolean fromInclusive,
+                                  D to, boolean toInclusive)
+    {
+      return new DescendingSet(set.subSet(from, fromInclusive,
+                                          to, toInclusive));
+    }
+
+    public SortedSet<D> tailSet(D from)
+    {
+      return tailSet(from, true);
+    }
+
+    public NavigableSet<D> tailSet(D from, boolean inclusive)
+    {
+      return new DescendingSet(set.headSet(from, inclusive));
+    }
+
+    public Object[] toArray()
+    {
+      D[] array = (D[]) set.toArray();
+      Arrays.sort(array, comparator());
+      return array;
+    }
+
+    public <T> T[] toArray(T[] a)
+    {
+      T[] array = set.toArray(a);
+      Arrays.sort(array, (Comparator<? super T>) comparator());
+      return array;
+    }
+
+    public String toString()
+    {
+      CPStringBuilder r = new CPStringBuilder("[");
+      final Iterator<D> it = iterator();
+      while (it.hasNext())
+      {
+        final D o = it.next();
+        if (o == this)
+          r.append("<this>");
+        else
+          r.append(o);
+        r.append(", ");
+      }
+      r.replace(r.length() - 2, r.length(), "]");
+      return r.toString();
+    }
+
+  } // class DescendingSet
+
+  private class EntrySet
+    extends AbstractSet<Entry<K,V>>
+  {
+    public int size()
+    {
+      return size;
+    }
+
+    public Iterator<Map.Entry<K,V>> iterator()
+    {
+      return new TreeIterator(ENTRIES);
+    }
+
+    public void clear()
+    {
+      TreeMap.this.clear();
+    }
+
+    public boolean contains(Object o)
+    {
+      if (! (o instanceof Map.Entry))
+        return false;
+      Map.Entry<K,V> me = (Map.Entry<K,V>) o;
+      Node<K,V> n = getNode(me.getKey());
+      return n != nil && AbstractSet.equals(me.getValue(), n.value);
+    }
+
+    public boolean remove(Object o)
+    {
+      if (! (o instanceof Map.Entry))
+        return false;
+      Map.Entry<K,V> me = (Map.Entry<K,V>) o;
+      Node<K,V> n = getNode(me.getKey());
+      if (n != nil && AbstractSet.equals(me.getValue(), n.value))
+        {
+          removeNode(n);
+          return true;
+        }
+      return false;
+    }
+  }
+
+  private final class NavigableEntrySet
+    extends EntrySet
+    implements NavigableSet<Entry<K,V>>
+  {
+
+    public Entry<K,V> ceiling(Entry<K,V> e)
+    {
+      return ceilingEntry(e.getKey());
+    }
+
+    public Comparator<? super Entry<K,V>> comparator()
+    {
+      return new Comparator<Entry<K,V>>()
+        {
+          public int compare(Entry<K,V> t1, Entry<K,V> t2)
+          {
+            return comparator.compare(t1.getKey(), t2.getKey());
+          }
+        };
+    }
+
+    public Iterator<Entry<K,V>> descendingIterator()
+    {
+      return descendingSet().iterator();
+    }
+
+    public NavigableSet<Entry<K,V>> descendingSet()
+    {
+      return new DescendingSet(this);
+    }
+
+    public Entry<K,V> first()
+    {
+      return firstEntry();
+    }
+
+    public Entry<K,V> floor(Entry<K,V> e)
+    {
+      return floorEntry(e.getKey());
+    }
+
+    public SortedSet<Entry<K,V>> headSet(Entry<K,V> to)
+    {
+      return headSet(to, false);
+    }
+
+    public NavigableSet<Entry<K,V>> headSet(Entry<K,V> to, boolean inclusive)
+    {
+      return (NavigableSet<Entry<K,V>>) headMap(to.getKey(), inclusive).entrySet();
+    }
+
+    public Entry<K,V> higher(Entry<K,V> e)
+    {
+      return higherEntry(e.getKey());
+    }
+
+    public Entry<K,V> last()
+    {
+      return lastEntry();
+    }
+
+    public Entry<K,V> lower(Entry<K,V> e)
+    {
+      return lowerEntry(e.getKey());
+    }
+
+    public Entry<K,V> pollFirst()
+    {
+      return pollFirstEntry();
+    }
+
+    public Entry<K,V> pollLast()
+    {
+      return pollLastEntry();
+    }
+
+    public SortedSet<Entry<K,V>> subSet(Entry<K,V> from, Entry<K,V> to)
+    {
+      return subSet(from, true, to, false);
+    }
+
+    public NavigableSet<Entry<K,V>> subSet(Entry<K,V> from, boolean fromInclusive,
+                                           Entry<K,V> to, boolean toInclusive)
+    {
+      return (NavigableSet<Entry<K,V>>) subMap(from.getKey(), fromInclusive,
+                                               to.getKey(), toInclusive).entrySet();
+    }
+
+    public SortedSet<Entry<K,V>> tailSet(Entry<K,V> from)
+    {
+      return tailSet(from, true);
+    }
+
+    public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive)
+    {
+      return (NavigableSet<Entry<K,V>>) tailMap(from.getKey(), inclusive).navigableKeySet();
+    }
+
+  } // class NavigableEntrySet
+
+} // class TreeMap