libjava/classpath/ChangeLog.gcj:

2007-05-31  Matthias Klose  <doko@ubuntu.com>

        * javax/management/NotificationBroadcasterSupport.java
        (getNotificationInfo): Add cast.
        * native/jni/qt-peer/Makefile.am (AM_CXXFLAGS): Add libstdc++ include
        directories.
        * native/jni/qt-peer/Makefile.in: Regenerate.

libjava/ChangeLog:

2007-06-03  Matthias Klose  <doko@ubuntu.com>

        * java/io/natFileWin32.cc (setFilePermissions): New (stub only).
        _access: Handle EXEC query, stub only.

2007-06-03  Matthias Klose  <doko@ubuntu.com>

        Merged from classpath:
        * gnu/java/nio/SelectorProviderImpl.java: Whitespace merge.
        * java/lang/System.java(inheritedChannel): New.
        * java/lang/Character.java: Remove stray`;'.
        * java/net/MulticastSocket.java: Merged.
        * java/text/DateFormatSymbols.java(getInstance): New, comment updates.
        * java/text/Collator.java(getInstance): Merged.
        * java/util/Calendar.java: New attributes ALL_STYLES, SHORT, LONG.
        getDisplayName, getDisplayNames: New.
        * java/util/logging/Logger.java: Merged.
        * Regenerate .class and .h files.

2007-06-03  Matthias Klose  <doko@ubuntu.com>

        * java/io/File.java: Merge with classpath-0.95, new method
        setFilePermissions, new attribute EXEC.
        * java/io/natFilePosix.cc (setFilePermissions): New.
        _access: Handle EXEC query.
        * classpath/lib/java/io/File.class, java/io/File.h: Regenerate.

2007-06-03  Matthias Klose  <doko@ubuntu.com>

        Imported GNU Classpath 0.95.

        * classpath/Makefile.in,
        classpath/native/jni/midi-dssi/Makefile.in,
        classpath/native/jni/classpath/Makefile.in,
        classpath/native/jni/Makefile.in,
        classpath/native/jni/gconf-peer/Makefile.in,
        classpath/native/jni/java-io/Makefile.in,
        classpath/native/jni/native-lib/Makefile.in,
        classpath/native/jni/java-util/Makefile.in,
        classpath/native/jni/midi-alsa/Makefile.in,
        classpath/native/jni/java-lang/Makefile.in,
        classpath/native/jni/java-nio/Makefile.in,
        classpath/native/jni/java-net/Makefile.in,
        classpath/native/jni/xmlj/Makefile.in,
        classpath/native/jni/qt-peer/Makefile.in,
        classpath/native/jni/gtk-peer/Makefile.in,
        classpath/native/Makefile.in, classpath/native/jawt/Makefile.in,
        classpath/native/fdlibm/Makefile.in,
        classpath/native/plugin/Makefile.in,
        classpath/resource/Makefile.in, classpath/scripts/Makefile.in,
        classpath/tools/Makefile.in, classpath/doc/Makefile.in,
        classpath/doc/api/Makefile.in, classpath/lib/Makefile.in,
        classpath/external/Makefile.in, classpath/external/jsr166/Makefile.in,
        classpath/external/sax/Makefile.in,
        classpath/external/w3c_dom/Makefile.in,
        classpath/external/relaxngDatatype/Makefile.in,
        classpath/include/Makefile.in,
        classpath/examples/Makefile.in: Regenerate.
        * classpath/config.guess, classpath/config.sub,
        classpath/ltmain.sh : Update.
        * classpath/configure, classpath/depcomp, classpath/missing,
        classpath/aclocal.m4, classpath/install-sh: Regenerate.

        * gnu/classpath/Configuration.java (CLASSPATH_VERSION): Now 0.95.
        * sources.am: Regenerate.
        * Makefile.in: Regenerate.

        * Update the .class files and generated CNI header files, add new
        .class and generated CNI header files.
        * Remove generated files for removed java source files:
        classpath/gnu/java/net/BASE64.java,
        classpath/gnu/java/security/util/Base64.java,
        classpath/gnu/java/awt/peer/gtk/GThreadMutex.java,
        classpath/gnu/java/awt/peer/gtk/GThreadNativeMethodRunner.java,
        classpath/gnu/java/awt/font/autofit/Scaler.java,
        classpath/gnu/classpath/jdwp/util/Value.java,
        classpath/gnu/javax/net/ssl/Base64.java.
        * Remove empty directories.

        * Makefile.am(nat_source_files): Add natVMOperatingSystemMXBeanImpl.cc.
        * java/lang/Class.java(setAccessible): Merge from classpath.
        * java/util/Locale.java: Remove.
        * gnu/java/lang/management/VMOperatingSystemMXBeanImpl.java,
        gnu/java/lang/management/natVMOperatingSystemMXBeanImpl.cc: New.
        * gcj/javaprims.h: Update class declarations.
        * scripts/classes.pl: Update usage.
        * HACKING: Mention to build all peers.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@125302 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 1755 insertions, 215 deletions

diff --git a/libjava/classpath/java/util/TreeMap.java b/libjava/classpath/java/util/TreeMap.java
index 88abce10d8d..f54cbc336ec 100644
--- a/libjava/classpath/java/util/TreeMap.java
+++ b/libjava/classpath/java/util/TreeMap.java
@@ -1,6 +1,6 @@
 /* TreeMap.java -- a class providing a basic Red-Black Tree data structure,
    mapping Object --> Object
-   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005  Free Software Foundation, Inc.
+   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006  Free Software Foundation, Inc.
 
 This file is part of GNU Classpath.
 
@@ -79,6 +79,7 @@ import java.io.Serializable;
  * @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
@@ -88,10 +89,10 @@ import java.io.Serializable;
  * @see Collection
  * @see Collections#synchronizedSortedMap(SortedMap)
  * @since 1.2
- * @status updated to 1.4
+ * @status updated to 1.6
  */
 public class TreeMap<K, V> extends AbstractMap<K, V>
-  implements SortedMap<K, V>, Cloneable, Serializable
+  implements NavigableMap<K, V>, Cloneable, Serializable
 {
   // Implementation note:
   // A red-black tree is a binary search tree with the additional properties
@@ -143,6 +144,16 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
   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.
@@ -369,46 +380,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     if (entries == null)
       // Create an AbstractSet with custom implementations of those methods
       // that can be overriden easily and efficiently.
-      entries = new AbstractSet<Map.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;
-        }
-      };
+      entries = new NavigableEntrySet();
     return entries;
   }
 
@@ -451,7 +423,9 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    * 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.
+   * 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
@@ -462,7 +436,29 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   public SortedMap<K, V> headMap(K toKey)
   {
-    return new SubMap((K)(Object)nil, 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);
   }
 
   /**
@@ -479,37 +475,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     if (keys == null)
       // Create an AbstractSet with custom implementations of those methods
       // that can be overriden easily and efficiently.
-      keys = new 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;
-        }
-      };
+      keys = new KeySet();
     return keys;
   }
 
@@ -648,7 +614,9 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    * {@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.
+   * 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
@@ -661,7 +629,34 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   public SortedMap<K, V> subMap(K fromKey, K toKey)
   {
-    return new SubMap(fromKey, 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);
   }
 
   /**
@@ -671,6 +666,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    * {@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
@@ -681,7 +677,29 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   public SortedMap<K, V> tailMap(K fromKey)
   {
-    return new SubMap(fromKey, (K)(Object)nil);
+    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);
   }
 
   /**
@@ -972,6 +990,21 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   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();
 
@@ -988,9 +1021,9 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
         else if (comparison < 0)
           current = current.left;
         else // Exact match.
-          return predecessor(last);
+          return (equal ? last : predecessor(last));
       }
-    return comparison <= 0 ? predecessor(last) : last;
+    return comparison < 0 ? predecessor(last) : last;
   }
 
   /**
@@ -1084,8 +1117,8 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
   /**
    * 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.
+   * 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
@@ -1093,6 +1126,21 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   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;
 
@@ -1109,7 +1157,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
         else if (comparison < 0)
           current = current.left;
         else
-          return current;
+          return (equal ? current : successor(current));
       }
     return comparison > 0 ? successor(last) : last;
   }
@@ -1409,11 +1457,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
      */
     TreeIterator(int type)
     {
-      // FIXME gcj cannot handle this. Bug java/4695
-      // this(type, firstNode(), nil);
-      this.type = type;
-      this.next = firstNode();
-      this.max = nil;
+      this(type, firstNode(), nil);
     }
 
     /**
@@ -1489,26 +1533,36 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    *
    * @author Eric Blake (ebb9@email.byu.edu)
    */
-  private final class SubMap<SK extends K,SV extends V>
-    extends AbstractMap<SK,SV>
-    implements SortedMap<SK,SV>
+  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 SK minKey;
+    final K minKey;
 
     /**
      * The upper range of this view, exclusive, or nil for unbounded.
      * Package visible for use by nested classes.
      */
-    final SK maxKey;
+    final K maxKey;
 
     /**
      * The cache for {@link #entrySet()}.
      */
-    private Set<Map.Entry<SK,SV>> entries;
+    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)
@@ -1519,9 +1573,9 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
      * @param maxKey the upper bound
      * @throws IllegalArgumentException if minKey &gt; maxKey
      */
-    SubMap(SK minKey, SK maxKey)
+    SubMap(K minKey, K maxKey)
     {
-      if (minKey != nil && maxKey != nil && compare((K) minKey, (K) maxKey) > 0)
+      if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)
         throw new IllegalArgumentException("fromKey > toKey");
       this.minKey = minKey;
       this.maxKey = maxKey;
@@ -1535,12 +1589,41 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
      * @param key the key to check
      * @return true if the key is in range
      */
-    boolean keyInRange(SK key)
+    boolean keyInRange(K key)
     {
-      return ((minKey == nil || compare((K) key, (K) minKey) >= 0)
-              && (maxKey == nil || compare((K) key, (K) maxKey) < 0));
+      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);
@@ -1553,14 +1636,14 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
         }
     }
 
-    public Comparator<? super SK> comparator()
+    public Comparator<? super K> comparator()
     {
       return comparator;
     }
 
     public boolean containsKey(Object key)
     {
-      return keyInRange((SK) key) && TreeMap.this.containsKey(key);
+      return keyInRange((K) key) && TreeMap.this.containsKey(key);
     }
 
     public boolean containsValue(Object value)
@@ -1576,150 +1659,160 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
       return false;
     }
 
-    public Set<Map.Entry<SK,SV>> entrySet()
+    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 AbstractSet<Map.Entry<SK,SV>>()
-        {
-          public int size()
-          {
-            return SubMap.this.size();
-          }
-
-          public Iterator<Map.Entry<SK,SV>> 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<SK,SV> me = (Map.Entry<SK,SV>) o;
-            SK key = me.getKey();
-            if (! keyInRange(key))
-              return false;
-            Node<K,V> n = getNode((K) key);
-            return n != nil && AbstractSet.equals(me.getValue(), n.value);
-          }
-
-          public boolean remove(Object o)
-          {
-            if (! (o instanceof Map.Entry))
-              return false;
-            Map.Entry<SK,SV> me = (Map.Entry<SK,SV>) o;
-            SK key = me.getKey();
-            if (! keyInRange(key))
-              return false;
-            Node<K,V> n = getNode((K) key);
-            if (n != nil && AbstractSet.equals(me.getValue(), n.value))
-              {
-                removeNode(n);
-                return true;
-              }
-            return false;
-          }
-        };
+        entries = new SubMap.NavigableEntrySet();
       return entries;
     }
 
-    public SK firstKey()
+    public Entry<K,V> firstEntry()
     {
-      Node<SK,SV> node = (Node<SK,SV>) lowestGreaterThan(minKey, true);
+      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 node.key;
+      return e.getKey();
     }
 
-    public SV get(Object key)
+    public Entry<K,V> floorEntry(K key)
     {
-      if (keyInRange((SK) key))
-        return (SV) TreeMap.this.get(key);
+      Entry<K,V> n = TreeMap.this.floorEntry(key);
+      if (n != null && keyInRange(n.getKey()))
+	return n;
       return null;
     }
 
-    public SortedMap<SK,SV> headMap(SK toKey)
+    public K floorKey(K key)
     {
-      if (! keyInRange(toKey))
-        throw new IllegalArgumentException("key outside range");
-      return new SubMap(minKey, toKey);
+      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 Set<SK> keySet()
+    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 AbstractSet()
-        {
-          public int size()
-          {
-            return SubMap.this.size();
-          }
-
-          public Iterator<SK> iterator()
-          {
-            Node first = lowestGreaterThan(minKey, true);
-            Node max = lowestGreaterThan(maxKey, false);
-            return new TreeIterator(KEYS, first, max);
-          }
+        this.keys = new SubMap.KeySet();
+      return this.keys;
+    }
 
-          public void clear()
-          {
-            SubMap.this.clear();
-          }
+    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 boolean contains(Object o)
-          {
-            if (! keyInRange((SK) o))
-              return false;
-            return getNode((K) o) != nil;
-          }
+    public K higherKey(K key)
+    {
+      K found = TreeMap.this.higherKey(key);
+      if (keyInRange(found))
+	return found;
+      else
+	return null;
+    }
 
-          public boolean remove(Object o)
-          {
-            if (! keyInRange((SK) o))
-              return false;
-            Node n = getNode((K) o);
-            if (n != nil)
-              {
-                removeNode(n);
-                return true;
-              }
-            return false;
-          }
-        };
-      return this.keys;
+    public Entry<K,V> lastEntry()
+    {
+      return lowerEntry(maxKey);
     }
 
-    public SK lastKey()
+    public K lastKey()
     {
-      Node<SK,SV> node = (Node<SK,SV>) highestLessThan(maxKey);
-      if (node == nil || ! keyInRange(node.key))
+      Entry<K,V> e = lastEntry();
+      if (e == null)
         throw new NoSuchElementException();
-      return (SK) node.key;
+      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 SV put(SK key, SV value)
+    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 (SV) TreeMap.this.put(key, value);
+      return TreeMap.this.put(key, value);
     }
 
-    public SV remove(Object key)
+    public V remove(Object key)
     {
-      if (keyInRange((SK)key))
-        return (SV) TreeMap.this.remove(key);
+      if (keyInRange((K)key))
+        return TreeMap.this.remove(key);
       return null;
     }
 
@@ -1736,21 +1829,34 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
       return count;
     }
 
-    public SortedMap<SK, SV> subMap(SK fromKey, SK toKey)
+    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(fromKey, toKey);
+      return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key, 
+			toInclusive ? successor(getNode(toKey)).key : toKey);
     }
 
-    public SortedMap<SK, SV> tailMap(SK fromKey)
+    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(fromKey, maxKey);
+      return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key,
+			maxKey);
     }
 
-    public Collection<SV> values()
+    public Collection<V> values()
     {
       if (this.values == null)
         // Create an AbstractCollection with custom implementations of those
@@ -1762,7 +1868,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
             return SubMap.this.size();
           }
 
-          public Iterator<SV> iterator()
+          public Iterator<V> iterator()
           {
             Node first = lowestGreaterThan(minKey, true);
             Node max = lowestGreaterThan(maxKey, false);
@@ -1776,5 +1882,1439 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
         };
       return this.values;
     }
-  } // class SubMap  
+    
+    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()
+    {
+      StringBuilder r = new StringBuilder("{");
+      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 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()
+	    {
+	      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()
+    {
+      StringBuilder r = new StringBuilder("[");
+      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