Fix warnings in TreeMap and TreeSet.

2013-02-17  Andrew John Hughes  <gnu_andrew@member.fsf.org>

	Fix warnings.
	* java/util/TreeMap.java:
	(nil): Add type parameters.
	(root): Likewise.
	(left): Don't set to nil here.
	(right): Likewise.
	(parent): Likewise.
	(Node(K,V,int)): Set left, right and parent
	here using correctly typed nil.
	(TreeMap()): Cast Comparator with type parameters.
	(TreeMap(Map)): Likewise.
	(TreeMap(SortedMap)): Remove unused variable.  Use
	for-each loop and typed nil.
	(clone()): Separate cast and cloning.  Add type
	parameters to node and cnode.
	(containsKey(Object)): Cast key.
	(containsvalue()): Add type parameters to node.
	(get(Object)): Cast key.
	(headMap(K,boolean)): Likewise.
	(put(K,V)): Cast nil before assigning to parent.
	Add type parameters to n.
	(putAll(Map)): Rewrite using for-each loop.
	(remove(Object)): Cast key.
	(tailMap(K,boolean)): Likewise.
	(values()): Add type parameter to iterator.
	(compare(K,K)): Suppress warnings.
	(fabricateTree(int)): Use typed nil.
	Add type parameters to root, row, parent, last,
	left, right and next.
	(firstNode()): Add type parameters to node.
	(highestLessThan(K,boolean)): Use typed nil.
	(insertFixup(Node)): Add type parameters to
	uncle.
	(lastNode()): Add type parameters to node.
	(lowestGreaterThan(K,boolean,boolean)):
	Use typed nil.
	(predecessor(Node)): Add type parameters to
	parent.
	(putFromObjStream(ObjectInputStream,int,V)):
	Pass value with type rather than using String.
	Add type parameter to node.
	(putKeysLinear(Iterator,int,V)): Pass in value
	rather than using empty string.
	(readObject(ObjectInputStream)): Call putFromObjStream
	with null rather than true.
	(removeNode(Node)): Add type parameters to parent.
	(rotateLeft(Node)): Add type parameters to child.
	(rotateRight(Node)): Likewise.
	(writeObject(ObjectOutputStream)): Add type parameters
	to node.
	(TreeIterator): Add type parameter.
	(TreeIterator.last): Likewise.
	(TreeIterator.next): Likewise.
	(TreeIterator.max): Likewise.
	(TreeIterator.TreeIterator(int)): Cast nil.
	(TreeIterator.TreeIterator(int,Node,Node)): Add type
	parameters.
	(TreeIterator.next()): Suppress warnings and cast to
	correct type.
	(descendingMap()): Add type parameters.
	(clear()): Add type parameters to next, max and current.
	(SubMap.containsKey(Object)): Fix casting of key.
	(SubMap.containsValue(Object)): Add type parameters to
	node and max.
	(SubMap.get(Object)): Fix casting of key.
	(SubMap.remove(Object)): Likewise.
	(SubMap.size()): Add type parameters to node and max.
	(SubMap.values()): Add type parameter to AbstractCollection,
	first, max and TreeIterator.
	(SubMap.KeySet.iterator()): Add type parameters to first and
	max.
	(SubMap.KeySet.contains(Object)): Fix casting of key.
	(SubMap.KeySet.remove(Object)): Likewise.
	(SubMap.NavigableKeySet.descendingSet()): Add type parameter
	to DescendingSet.
	(SubMap.EntrySet.iterator()): Add type parameters to first
	and max.
	(SubMap.EntrySet.contains(Object)): Fix casting of entry.
	(SubMap.EntrySet.remove(Object)): Likewise.
	(SubMap.NavigableEntrySet.descendingSet()): Add type
	parameter to DescendingSet.
	(SubMap.NavigableEntrySet.tailSet(Entry,boolean)): Return
	entry set, not key set.
	(DescendingMap.headMap(DK,boolean)): Add type parameters.
	(DescendingMap.subMap(DK,boolean,DK,boolean)): Likewise.
	(DescendingMap.tailMap(Dk,boolean)): Likewise.
	(DescendingMap.values()): Add type parameter to
	AbstractCollection.
	(KeySet.iterator()): Add type parameter to TreeIterator.
	(KeySet.remove(Object)): Fix casting of key.
	(NavigableKeySet.headSet(D,boolean)): Add type parameter.
	(NavigableKeySet.subSet(D,boolean,D,boolean)): Likewise.
	(NavigableKeySet.tailSet(D,boolean)): Likewise.
	(NavigableKeySet.toArray()): Suppress warnings on cast.
	(NavigableKeySet.toArray(T[])): Likewise.
	(EntrySet.iterator()): Add type parameter to TreeIterator.
	(EntrySet.contains(Object)): Fix casting of entry.
	(EntrySet.remove(Object)): Likewise.
	(NavigableEntrySet.descendingSet()): Add type
	parameter to DescendingSet.
	(NavigableEntrySet.tailSet(Entry,boolean)): Return
	entry set, not key set.
	* java/util/TreeSet.java:
	(TreeSet(SortedSet)): Explicitly pass empty String to
	putKeysLinear as it no longer defaults to this.
	(readObject(ObjectInputStream)): Pass empty String rather
	than false, which will in turn make "" == null return false
	in putFromObjStream.

Signed-off-by: Andrew John Hughes <gnu_andrew@member.fsf.org>

3 files changed, 264 insertions, 134 deletions

diff --git a/ChangeLog b/ChangeLog
index e26f6277e..02335d2d1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,114 @@
+2013-02-17  Andrew John Hughes  <gnu_andrew@member.fsf.org>
+
+	Fix warnings.
+	* java/util/TreeMap.java:
+	(nil): Add type parameters.
+	(root): Likewise.
+	(left): Don't set to nil here.
+	(right): Likewise.
+	(parent): Likewise.
+	(Node(K,V,int)): Set left, right and parent
+	here using correctly typed nil.
+	(TreeMap()): Cast Comparator with type parameters.
+	(TreeMap(Map)): Likewise.
+	(TreeMap(SortedMap)): Remove unused variable.  Use
+	for-each loop and typed nil.
+	(clone()): Separate cast and cloning.  Add type
+	parameters to node and cnode.
+	(containsKey(Object)): Cast key.
+	(containsvalue()): Add type parameters to node.
+	(get(Object)): Cast key.
+	(headMap(K,boolean)): Likewise.
+	(put(K,V)): Cast nil before assigning to parent.
+	Add type parameters to n.
+	(putAll(Map)): Rewrite using for-each loop.
+	(remove(Object)): Cast key.
+	(tailMap(K,boolean)): Likewise.
+	(values()): Add type parameter to iterator.
+	(compare(K,K)): Suppress warnings.
+	(fabricateTree(int)): Use typed nil.
+	Add type parameters to root, row, parent, last,
+	left, right and next.
+	(firstNode()): Add type parameters to node.
+	(highestLessThan(K,boolean)): Use typed nil.
+	(insertFixup(Node)): Add type parameters to
+	uncle.
+	(lastNode()): Add type parameters to node.
+	(lowestGreaterThan(K,boolean,boolean)):
+	Use typed nil.
+	(predecessor(Node)): Add type parameters to
+	parent.
+	(putFromObjStream(ObjectInputStream,int,V)):
+	Pass value with type rather than using String.
+	Add type parameter to node.
+	(putKeysLinear(Iterator,int,V)): Pass in value
+	rather than using empty string.
+	(readObject(ObjectInputStream)): Call putFromObjStream
+	with null rather than true.
+	(removeNode(Node)): Add type parameters to parent.
+	(rotateLeft(Node)): Add type parameters to child.
+	(rotateRight(Node)): Likewise.
+	(writeObject(ObjectOutputStream)): Add type parameters
+	to node.
+	(TreeIterator): Add type parameter.
+	(TreeIterator.last): Likewise.
+	(TreeIterator.next): Likewise.
+	(TreeIterator.max): Likewise.
+	(TreeIterator.TreeIterator(int)): Cast nil.
+	(TreeIterator.TreeIterator(int,Node,Node)): Add type
+	parameters.
+	(TreeIterator.next()): Suppress warnings and cast to
+	correct type.
+	(descendingMap()): Add type parameters.
+	(clear()): Add type parameters to next, max and current.
+	(SubMap.containsKey(Object)): Fix casting of key.
+	(SubMap.containsValue(Object)): Add type parameters to
+	node and max.
+	(SubMap.get(Object)): Fix casting of key.
+	(SubMap.remove(Object)): Likewise.
+	(SubMap.size()): Add type parameters to node and max.
+	(SubMap.values()): Add type parameter to AbstractCollection,
+	first, max and TreeIterator.
+	(SubMap.KeySet.iterator()): Add type parameters to first and
+	max.
+	(SubMap.KeySet.contains(Object)): Fix casting of key.
+	(SubMap.KeySet.remove(Object)): Likewise.
+	(SubMap.NavigableKeySet.descendingSet()): Add type parameter
+	to DescendingSet.
+	(SubMap.EntrySet.iterator()): Add type parameters to first
+	and max.
+	(SubMap.EntrySet.contains(Object)): Fix casting of entry.
+	(SubMap.EntrySet.remove(Object)): Likewise.
+	(SubMap.NavigableEntrySet.descendingSet()): Add type
+	parameter to DescendingSet.
+	(SubMap.NavigableEntrySet.tailSet(Entry,boolean)): Return
+	entry set, not key set.
+	(DescendingMap.headMap(DK,boolean)): Add type parameters.
+	(DescendingMap.subMap(DK,boolean,DK,boolean)): Likewise.
+	(DescendingMap.tailMap(Dk,boolean)): Likewise.
+	(DescendingMap.values()): Add type parameter to
+	AbstractCollection.
+	(KeySet.iterator()): Add type parameter to TreeIterator.
+	(KeySet.remove(Object)): Fix casting of key.
+	(NavigableKeySet.headSet(D,boolean)): Add type parameter.
+	(NavigableKeySet.subSet(D,boolean,D,boolean)): Likewise.
+	(NavigableKeySet.tailSet(D,boolean)): Likewise.
+	(NavigableKeySet.toArray()): Suppress warnings on cast.
+	(NavigableKeySet.toArray(T[])): Likewise.
+	(EntrySet.iterator()): Add type parameter to TreeIterator.
+	(EntrySet.contains(Object)): Fix casting of entry.
+	(EntrySet.remove(Object)): Likewise.
+	(NavigableEntrySet.descendingSet()): Add type
+	parameter to DescendingSet.
+	(NavigableEntrySet.tailSet(Entry,boolean)): Return
+	entry set, not key set.
+	* java/util/TreeSet.java:
+	(TreeSet(SortedSet)): Explicitly pass empty String to
+	putKeysLinear as it no longer defaults to this.
+	(readObject(ObjectInputStream)): Pass empty String rather
+	than false, which will in turn make "" == null return false
+	in putFromObjStream.
+
 2013-03-12  Pekka Enberg <penberg@kernel.org>
 
 	* autogen.sh:
diff --git a/java/util/TreeMap.java b/java/util/TreeMap.java
index 87c532fc1..8617f7e3f 100644
--- a/java/util/TreeMap.java
+++ b/java/util/TreeMap.java
@@ -121,7 +121,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    * 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 final Node<Object,Object> nil = new Node<Object,Object>(null, null, BLACK);
   static
     {
       // Nil is self-referential, so we must initialize it after creation.
@@ -133,7 +133,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
   /**
    * The root node of this TreeMap.
    */
-  private transient Node root;
+  private transient Node<K,V> root;
 
   /**
    * The size of this TreeMap. Package visible for use by nested classes.
@@ -182,11 +182,11 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     int color;
 
     /** The left child node. */
-    Node<K, V> left = nil;
+    Node<K, V> left;
     /** The right child node. */
-    Node<K, V> right = nil;
+    Node<K, V> right;
     /** The parent node. */
-    Node<K, V> parent = nil;
+    Node<K, V> parent;
 
     /**
      * Simple constructor.
@@ -196,6 +196,8 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     Node(K key, V value, int color)
     {
       super(key, value);
+      @SuppressWarnings("unchecked") Node<K,V> typedNil = (Node<K,V>) nil;
+      parent = left = right = typedNil;
       this.color = color;
     }
   }
@@ -211,7 +213,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   public TreeMap()
   {
-    this((Comparator) null);
+    this((Comparator<? super K>) null);
   }
 
   /**
@@ -245,7 +247,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   public TreeMap(Map<? extends K, ? extends V> map)
   {
-    this((Comparator) null);
+    this((Comparator<? super K>) null);
     putAll(map);
   }
 
@@ -260,15 +262,12 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
   public TreeMap(SortedMap<K, ? extends V> sm)
   {
     this(sm.comparator());
-    int pos = sm.size();
-    Iterator itr = sm.entrySet().iterator();
 
-    fabricateTree(pos);
-    Node node = firstNode();
+    fabricateTree(sm.size());
+    Node<K,V> node = firstNode();
 
-    while (--pos >= 0)
+    for (Map.Entry<K,? extends V> me : sm.entrySet())
       {
-        Map.Entry me = (Map.Entry) itr.next();
         node.key = me.getKey();
         node.value = me.getValue();
         node = successor(node);
@@ -283,7 +282,9 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     if (size > 0)
       {
         modCount++;
-        root = nil;
+	@SuppressWarnings("unchecked")
+	  Node<K,V> typedNil = (Node<K,V>) nil;
+        root = typedNil;
         size = 0;
       }
   }
@@ -296,19 +297,21 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   public Object clone()
   {
-    TreeMap copy = null;
+    Object clone = null;
     try
       {
-        copy = (TreeMap) super.clone();
+	clone = super.clone();
       }
     catch (CloneNotSupportedException x)
       {
       }
+    @SuppressWarnings("unchecked")
+      TreeMap<K,V> copy = (TreeMap<K,V>) clone;
     copy.entries = null;
     copy.fabricateTree(size);
 
-    Node node = firstNode();
-    Node cnode = copy.firstNode();
+    Node<K,V> node = firstNode();
+    Node<K,V> cnode = copy.firstNode();
 
     while (node != nil)
       {
@@ -342,7 +345,8 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   public boolean containsKey(Object key)
   {
-    return getNode((K) key) != nil;
+    @SuppressWarnings("unchecked") K k = (K) key;
+    return getNode(k) != nil;
   }
 
   /**
@@ -354,7 +358,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   public boolean containsValue(Object value)
   {
-    Node node = firstNode();
+    Node<K,V> node = firstNode();
     while (node != nil)
       {
         if (equals(value, node.value))
@@ -415,8 +419,9 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   public V get(Object key)
   {
+    @SuppressWarnings("unchecked") K k = (K) key;
     // Exploit fact that nil.value == null.
-    return getNode((K) key).value;
+    return getNode(k).value;
   }
 
   /**
@@ -459,7 +464,8 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   public NavigableMap<K, V> headMap(K toKey, boolean inclusive)
   {
-    return new SubMap((K)(Object)nil, inclusive
+    @SuppressWarnings("unchecked") K nilKey = (K) nil;
+    return new SubMap(nilKey, inclusive
                       ? successor(getNode(toKey)).key : toKey);
   }
 
@@ -513,7 +519,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
   public V put(K key, V value)
   {
     Node<K,V> current = root;
-    Node<K,V> parent = nil;
+    @SuppressWarnings("unchecked") Node<K,V> parent = (Node<K,V>) nil;
     int comparison = 0;
 
     // Find new node's parent.
@@ -530,7 +536,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
       }
 
     // Set up new node.
-    Node n = new Node(key, value, RED);
+    Node<K,V> n = new Node<K,V>(key, value, RED);
     n.parent = parent;
 
     // Insert node in tree.
@@ -565,13 +571,8 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   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());
-      }
+    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
+      put(e.getKey(), e.getValue());
   }
 
   /**
@@ -589,7 +590,8 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   public V remove(Object key)
   {
-    Node<K, V> n = getNode((K)key);
+    @SuppressWarnings("unchecked") K k = (K) key;
+    Node<K, V> n = getNode(k);
     if (n == nil)
       return null;
     // Note: removeNode can alter the contents of n, so save value now.
@@ -700,8 +702,9 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive)
   {
+    @SuppressWarnings("unchecked") K nilKey = (K) nil;
     return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key,
-                      (K)(Object)nil);
+                      nilKey);
   }
 
   /**
@@ -728,7 +731,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
         public Iterator<V> iterator()
         {
-          return new TreeIterator(VALUES);
+          return new TreeIterator<V>(VALUES);
         }
 
         public void clear()
@@ -749,13 +752,13 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    *         or are not Comparable with natural ordering
    * @throws NullPointerException if o1 or o2 is null with natural ordering
    */
+  @SuppressWarnings("unchecked")
   final int compare(K o1, K o2)
   {
     return (comparator == null
-            ? ((Comparable) o1).compareTo(o2)
+            ? ((Comparable<? super K>) o1).compareTo(o2)
             : comparator.compare(o1, o2));
   }
-
   /**
    * Maintain red-black balance after deleting a node.
    *
@@ -873,7 +876,9 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
   {
     if (count == 0)
       {
-        root = nil;
+	@SuppressWarnings("unchecked")
+	  Node<K,V> typedNil = (Node<K,V>) nil;
+        root = typedNil;
         size = 0;
         return;
       }
@@ -884,25 +889,25 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     // then updating those links to the children when working on the next row.
 
     // Make the root node.
-    root = new Node(null, null, BLACK);
+    root = new Node<K,V>(null, null, BLACK);
     size = count;
-    Node row = root;
+    Node<K,V> 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;
+        Node<K,V> parent = row;
+        Node<K,V> last = null;
         for (int i = 0; i < rowsize; i += 2)
           {
-            Node left = new Node(null, null, BLACK);
-            Node right = new Node(null, null, BLACK);
+            Node<K,V> left = new Node<K,V>(null, null, BLACK);
+            Node<K,V> right = new Node<K,V>(null, null, BLACK);
             left.parent = parent;
             left.right = right;
             right.parent = parent;
             parent.left = left;
-            Node next = parent.right;
+            Node<K,V> next = parent.right;
             parent.right = right;
             parent = next;
             if (last != null)
@@ -914,33 +919,34 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
     // Now do the partial final row in red.
     int overflow = count - rowsize;
-    Node parent = row;
+    Node<K,V> 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);
+        Node<K,V> left = new Node<K,V>(null, null, RED);
+        Node<K,V> right = new Node<K,V>(null, null, RED);
         left.parent = parent;
         right.parent = parent;
         parent.left = left;
-        Node next = parent.right;
+        Node<K,V> next = parent.right;
         parent.right = right;
         parent = next;
       }
+    @SuppressWarnings("unchecked") Node<K,V> nilNode = (Node<K,V>) nil;
     // Add a lone left node if necessary.
     if (i - overflow == 0)
       {
-        Node left = new Node(null, null, RED);
+        Node<K,V> left = new Node<K,V>(null, null, RED);
         left.parent = parent;
         parent.left = left;
         parent = parent.right;
-        left.parent.right = nil;
+        left.parent.right = nilNode;
       }
     // Unlink the remaining nodes of the previous row.
     while (parent != nil)
       {
-        Node next = parent.right;
-        parent.right = nil;
+        Node<K,V> next = parent.right;
+        parent.right = nilNode;
         parent = next;
       }
   }
@@ -954,7 +960,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
   final Node<K, V> firstNode()
   {
     // Exploit fact that nil.left == nil.
-    Node node = root;
+    Node<K,V> node = root;
     while (node.left != nil)
       node = node.left;
     return node;
@@ -1010,7 +1016,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     if (key == nil)
       return lastNode();
 
-    Node<K,V> last = nil;
+    @SuppressWarnings("unchecked") Node<K,V> last = (Node<K,V>) nil;
     Node<K,V> current = root;
     int comparison = 0;
 
@@ -1042,7 +1048,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
       {
         if (n.parent == n.parent.parent.left)
           {
-            Node uncle = n.parent.parent.right;
+	    Node<K,V> uncle = n.parent.parent.right;
             // Uncle may be nil, in which case it is BLACK.
             if (uncle.color == RED)
               {
@@ -1072,7 +1078,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
         else
           {
             // Mirror image of above code.
-            Node uncle = n.parent.parent.left;
+            Node<K,V> uncle = n.parent.parent.left;
             // Uncle may be nil, in which case it is BLACK.
             if (uncle.color == RED)
               {
@@ -1111,7 +1117,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
   private Node<K,V> lastNode()
   {
     // Exploit fact that nil.right == nil.
-    Node node = root;
+    Node<K,V> node = root;
     while (node.right != nil)
       node = node.right;
     return node;
@@ -1143,10 +1149,12 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   final Node<K,V> lowestGreaterThan(K key, boolean first, boolean equal)
   {
+    @SuppressWarnings("unchecked") Node<K,V> nilNode = (Node<K,V>) nil;
+
     if (key == nil)
-      return first ? firstNode() : nil;
+	return first ? firstNode() : nilNode;
 
-    Node<K,V> last = nil;
+    Node<K,V> last = nilNode;
     Node<K,V> current = root;
     int comparison = 0;
 
@@ -1180,7 +1188,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
         return node;
       }
 
-    Node parent = node.parent;
+    Node<K,V> parent = node.parent;
     // Exploit fact that nil.left == nil and node is non-nil.
     while (node == parent.left)
       {
@@ -1196,36 +1204,38 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    *
    * @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
+   * @param readValues null to read values, non-null to insert itself as the value
    * @throws ClassNotFoundException if the underlying stream fails
    * @throws IOException if the underlying stream fails
    * @see #readObject(ObjectInputStream)
    * @see TreeSet#readObject(ObjectInputStream)
    */
+  @SuppressWarnings("unchecked")
   final void putFromObjStream(ObjectInputStream s, int count,
-                              boolean readValues)
+                              V readValues)
     throws IOException, ClassNotFoundException
   {
     fabricateTree(count);
-    Node node = firstNode();
+    Node<K,V> node = firstNode();
 
     while (--count >= 0)
       {
-        node.key = s.readObject();
-        node.value = readValues ? s.readObject() : "";
+        node.key = (K) s.readObject();
+        node.value = (readValues == null) ? (V) s.readObject() : readValues;
         node = successor(node);
       }
   }
 
   /**
-   * Construct a tree from sorted keys in linear time, with values of "".
+   * Construct a tree from sorted keys in linear time, with the given value.
    * 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
+   * @param value the value to use.
    * @see TreeSet#TreeSet(SortedSet)
    */
-  final void putKeysLinear(Iterator<K> keys, int count)
+  final void putKeysLinear(Iterator<K> keys, int count, V value)
   {
     fabricateTree(count);
     Node<K,V> node = firstNode();
@@ -1233,7 +1243,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     while (--count >= 0)
       {
         node.key = keys.next();
-        node.value = (V) "";
+        node.value = value;
         node = successor(node);
       }
   }
@@ -1252,7 +1262,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
   {
     s.defaultReadObject();
     int size = s.readInt();
-    putFromObjStream(s, size, true);
+    putFromObjStream(s, size, null);
   }
 
   /**
@@ -1295,7 +1305,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
       }
 
     // Unlink splice from the tree.
-    Node parent = splice.parent;
+    Node<K,V> parent = splice.parent;
     if (child != nil)
       child.parent = parent;
     if (parent == nil)
@@ -1320,7 +1330,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   private void rotateLeft(Node<K,V> node)
   {
-    Node child = node.right;
+    Node<K,V> child = node.right;
     // if (node == nil || child == nil)
     //   throw new InternalError();
 
@@ -1353,7 +1363,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    */
   private void rotateRight(Node<K,V> node)
   {
-    Node child = node.left;
+    Node<K,V> child = node.left;
     // if (node == nil || child == nil)
     //   throw new InternalError();
 
@@ -1418,7 +1428,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
   {
     s.defaultWriteObject();
 
-    Node node = firstNode();
+    Node<K,V> node = firstNode();
     s.writeInt(size);
     while (node != nil)
       {
@@ -1434,7 +1444,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
    *
    * @author Eric Blake (ebb9@email.byu.edu)
    */
-  private final class TreeIterator implements Iterator
+  private final class TreeIterator<T> implements Iterator<T>
   {
     /**
      * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
@@ -1444,22 +1454,23 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     /** 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;
+    private Node<K,V> last;
     /** The next entry that should be returned by next(). */
-    private Node next;
+    private Node<K,V> next;
     /**
      * The last node visible to this iterator. This is used when iterating
      * on a SubMap.
      */
-    private final Node max;
+    private final Node<K,V> max;
 
     /**
      * Construct a new TreeIterator with the supplied type.
      * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
      */
+    @SuppressWarnings("unchecked")
     TreeIterator(int type)
     {
-      this(type, firstNode(), nil);
+      this(type, firstNode(), (Node<K,V>) nil);
     }
 
     /**
@@ -1470,7 +1481,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
      * @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)
+    TreeIterator(int type, Node<K,V> first, Node<K,V> max)
     {
       this.type = type;
       this.next = first;
@@ -1492,7 +1503,8 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
      * @throws ConcurrentModificationException if the TreeMap was modified
      * @throws NoSuchElementException if there is none
      */
-    public Object next()
+    @SuppressWarnings("unchecked")
+    public T next()
     {
       if (knownMod != modCount)
         throw new ConcurrentModificationException();
@@ -1502,10 +1514,10 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
       next = successor(last);
 
       if (type == VALUES)
-        return last.value;
+        return (T) last.value;
       else if (type == KEYS)
-        return last.key;
-      return last;
+        return (T) last.key;
+      return (T) last;
     }
 
     /**
@@ -1622,17 +1634,17 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     public NavigableMap<K,V> descendingMap()
     {
       if (descendingMap == null)
-        descendingMap = new DescendingMap(this);
+        descendingMap = new DescendingMap<K,V>(this);
       return descendingMap;
     }
 
     public void clear()
     {
-      Node next = lowestGreaterThan(minKey, true);
-      Node max = lowestGreaterThan(maxKey, false);
+      Node<K,V> next = lowestGreaterThan(minKey, true);
+      Node<K,V> max = lowestGreaterThan(maxKey, false);
       while (next != max)
         {
-          Node current = next;
+          Node<K,V> current = next;
           next = successor(current);
           removeNode(current);
         }
@@ -1645,13 +1657,14 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
     public boolean containsKey(Object key)
     {
-      return keyInRange((K) key) && TreeMap.this.containsKey(key);
+      @SuppressWarnings("unchecked") K typedKey = (K) key;
+      return keyInRange(typedKey) && TreeMap.this.containsKey(typedKey);
     }
 
     public boolean containsValue(Object value)
     {
-      Node node = lowestGreaterThan(minKey, true);
-      Node max = lowestGreaterThan(maxKey, false);
+      Node<K,V> node = lowestGreaterThan(minKey, true);
+      Node<K,V> max = lowestGreaterThan(maxKey, false);
       while (node != max)
         {
           if (equals(value, node.getValue()))
@@ -1705,8 +1718,9 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
     public V get(Object key)
     {
-      if (keyInRange((K) key))
-        return TreeMap.this.get(key);
+      @SuppressWarnings("unchecked") K typedKey = (K) key;
+      if (keyInRange(typedKey))
+        return TreeMap.this.get(typedKey);
       return null;
     }
 
@@ -1813,15 +1827,16 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
     public V remove(Object key)
     {
-      if (keyInRange((K)key))
+      @SuppressWarnings("unchecked") K typedKey = (K) key;
+      if (keyInRange(typedKey))
         return TreeMap.this.remove(key);
       return null;
     }
 
     public int size()
     {
-      Node node = lowestGreaterThan(minKey, true);
-      Node max = lowestGreaterThan(maxKey, false);
+      Node<K,V> node = lowestGreaterThan(minKey, true);
+      Node<K,V> max = lowestGreaterThan(maxKey, false);
       int count = 0;
       while (node != max)
         {
@@ -1863,7 +1878,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
       if (this.values == null)
         // Create an AbstractCollection with custom implementations of those
         // methods that can be overriden easily and efficiently.
-        this.values = new AbstractCollection()
+        this.values = new AbstractCollection<V>()
         {
           public int size()
           {
@@ -1872,9 +1887,9 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
           public Iterator<V> iterator()
           {
-            Node first = lowestGreaterThan(minKey, true);
-            Node max = lowestGreaterThan(maxKey, false);
-            return new TreeIterator(VALUES, first, max);
+            Node<K,V> first = lowestGreaterThan(minKey, true);
+            Node<K,V> max = lowestGreaterThan(maxKey, false);
+            return new TreeIterator<V>(VALUES, first, max);
           }
 
           public void clear()
@@ -1895,9 +1910,9 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
       public Iterator<K> iterator()
       {
-        Node first = lowestGreaterThan(minKey, true);
-        Node max = lowestGreaterThan(maxKey, false);
-        return new TreeIterator(KEYS, first, max);
+        Node<K,V> first = lowestGreaterThan(minKey, true);
+        Node<K,V> max = lowestGreaterThan(maxKey, false);
+        return new TreeIterator<K>(KEYS, first, max);
       }
 
       public void clear()
@@ -1907,16 +1922,18 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
       public boolean contains(Object o)
       {
-        if (! keyInRange((K) o))
+	@SuppressWarnings("unchecked") K key = (K) o;
+        if (! keyInRange(key))
           return false;
-        return getNode((K) o) != nil;
+        return getNode(key) != nil;
       }
 
       public boolean remove(Object o)
       {
-        if (! keyInRange((K) o))
+	@SuppressWarnings("unchecked") K key = (K) o;
+        if (! keyInRange(key))
           return false;
-        Node n = getNode((K) o);
+        Node<K,V> n = getNode(key);
         if (n != nil)
           {
             removeNode(n);
@@ -1949,7 +1966,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
       public NavigableSet<K> descendingSet()
       {
-        return new DescendingSet(this);
+        return new DescendingSet<K>(this);
       }
 
       public K first()
@@ -2035,9 +2052,9 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
     public Iterator<Map.Entry<K,V>> iterator()
     {
-      Node first = lowestGreaterThan(minKey, true);
-      Node max = lowestGreaterThan(maxKey, false);
-      return new TreeIterator(ENTRIES, first, max);
+      Node<K,V> first = lowestGreaterThan(minKey, true);
+      Node<K,V> max = lowestGreaterThan(maxKey, false);
+      return new TreeIterator<Map.Entry<K,V>>(ENTRIES, first, max);
     }
 
     public void clear()
@@ -2049,7 +2066,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     {
       if (! (o instanceof Map.Entry))
         return false;
-      Map.Entry<K,V> me = (Map.Entry<K,V>) o;
+      @SuppressWarnings("unchecked") Map.Entry<K,V> me = (Map.Entry<K,V>) o;
       K key = me.getKey();
       if (! keyInRange(key))
         return false;
@@ -2061,7 +2078,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     {
       if (! (o instanceof Map.Entry))
         return false;
-      Map.Entry<K,V> me = (Map.Entry<K,V>) o;
+      @SuppressWarnings("unchecked") Map.Entry<K,V> me = (Map.Entry<K,V>) o;
       K key = me.getKey();
       if (! keyInRange(key))
         return false;
@@ -2103,7 +2120,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
       public NavigableSet<Entry<K,V>> descendingSet()
       {
-        return new DescendingSet(this);
+        return new DescendingSet<Entry<K,V>>(this);
       }
 
       public Entry<K,V> first()
@@ -2173,7 +2190,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
       public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive)
       {
         return (NavigableSet<Entry<K,V>>)
-          SubMap.this.tailMap(from.getKey(), inclusive).navigableKeySet();
+          SubMap.this.tailMap(from.getKey(), inclusive).entrySet();
       }
 
   } // class SubMap.NavigableEntrySet
@@ -2616,7 +2633,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
     public NavigableMap<DK,DV> headMap(DK toKey, boolean inclusive)
     {
-      return new DescendingMap(map.tailMap(toKey, inclusive));
+      return new DescendingMap<DK,DV>(map.tailMap(toKey, inclusive));
     }
 
     public Entry<DK,DV> higherEntry(DK key)
@@ -2706,8 +2723,8 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     public NavigableMap<DK,DV> subMap(DK fromKey, boolean fromInclusive,
                                       DK toKey, boolean toInclusive)
     {
-      return new DescendingMap(map.subMap(fromKey, fromInclusive,
-                                          toKey, toInclusive));
+      return new DescendingMap<DK,DV>(map.subMap(fromKey, fromInclusive,
+						 toKey, toInclusive));
     }
 
     public SortedMap<DK,DV> tailMap(DK fromKey)
@@ -2717,7 +2734,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
     public NavigableMap<DK,DV> tailMap(DK fromKey, boolean inclusive)
     {
-      return new DescendingMap(map.headMap(fromKey, inclusive));
+      return new DescendingMap<DK,DV>(map.headMap(fromKey, inclusive));
     }
 
     public String toString()
@@ -2741,7 +2758,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
       if (values == null)
         // Create an AbstractCollection with custom implementations of those
         // methods that can be overriden easily and efficiently.
-        values = new AbstractCollection()
+        values = new AbstractCollection<DV>()
           {
             public int size()
             {
@@ -2808,7 +2825,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
     public Iterator<K> iterator()
     {
-      return new TreeIterator(KEYS);
+      return new TreeIterator<K>(KEYS);
     }
 
     public void clear()
@@ -2823,7 +2840,8 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
     public boolean remove(Object key)
     {
-      Node<K,V> n = getNode((K) key);
+      @SuppressWarnings("unchecked") K typedKey = (K) key;
+      Node<K,V> n = getNode(typedKey);
       if (n == nil)
         return false;
       removeNode(n);
@@ -3032,7 +3050,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
     public NavigableSet<D> headSet(D to, boolean inclusive)
     {
-      return new DescendingSet(set.tailSet(to, inclusive));
+      return new DescendingSet<D>(set.tailSet(to, inclusive));
     }
 
     public D higher(D e)
@@ -3130,8 +3148,8 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     public NavigableSet<D> subSet(D from, boolean fromInclusive,
                                   D to, boolean toInclusive)
     {
-      return new DescendingSet(set.subSet(from, fromInclusive,
-                                          to, toInclusive));
+      return new DescendingSet<D>(set.subSet(from, fromInclusive,
+					     to, toInclusive));
     }
 
     public SortedSet<D> tailSet(D from)
@@ -3141,12 +3159,12 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
     public NavigableSet<D> tailSet(D from, boolean inclusive)
     {
-      return new DescendingSet(set.headSet(from, inclusive));
+      return new DescendingSet<D>(set.headSet(from, inclusive));
     }
 
     public Object[] toArray()
     {
-      D[] array = (D[]) set.toArray();
+      @SuppressWarnings("unchecked") D[] array = (D[]) set.toArray();
       Arrays.sort(array, comparator());
       return array;
     }
@@ -3154,7 +3172,8 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     public <T> T[] toArray(T[] a)
     {
       T[] array = set.toArray(a);
-      Arrays.sort(array, (Comparator<? super T>) comparator());
+      @SuppressWarnings("unchecked") D[] ourArray = (D[]) array;
+      Arrays.sort(ourArray, comparator());
       return array;
     }
 
@@ -3187,7 +3206,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
     public Iterator<Map.Entry<K,V>> iterator()
     {
-      return new TreeIterator(ENTRIES);
+      return new TreeIterator<Map.Entry<K,V>>(ENTRIES);
     }
 
     public void clear()
@@ -3199,7 +3218,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     {
       if (! (o instanceof Map.Entry))
         return false;
-      Map.Entry<K,V> me = (Map.Entry<K,V>) o;
+      @SuppressWarnings("unchecked") 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);
     }
@@ -3208,7 +3227,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
     {
       if (! (o instanceof Map.Entry))
         return false;
-      Map.Entry<K,V> me = (Map.Entry<K,V>) o;
+      @SuppressWarnings("unchecked") 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))
         {
@@ -3247,7 +3266,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
     public NavigableSet<Entry<K,V>> descendingSet()
     {
-      return new DescendingSet(this);
+      return new DescendingSet<Entry<K,V>>(this);
     }
 
     public Entry<K,V> first()
@@ -3314,7 +3333,7 @@ public class TreeMap<K, V> extends AbstractMap<K, V>
 
     public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive)
     {
-      return (NavigableSet<Entry<K,V>>) tailMap(from.getKey(), inclusive).navigableKeySet();
+      return (NavigableSet<Entry<K,V>>) tailMap(from.getKey(), inclusive).entrySet();
     }
 
   } // class NavigableEntrySet
diff --git a/java/util/TreeSet.java b/java/util/TreeSet.java
index 06f4fa5b3..4ab21bfcf 100644
--- a/java/util/TreeSet.java
+++ b/java/util/TreeSet.java
@@ -154,7 +154,7 @@ public class TreeSet<T> extends AbstractSet<T>
     map = new TreeMap<T, String>
       ((Comparator<? super T>)sortedSet.comparator());
     itr = ((SortedSet<T>) sortedSet).iterator();
-    ((TreeMap<T, String>) map).putKeysLinear(itr, sortedSet.size());
+    ((TreeMap<T, String>) map).putKeysLinear(itr, sortedSet.size(), "");
   }
 
   /**
@@ -489,7 +489,7 @@ public class TreeSet<T> extends AbstractSet<T>
     Comparator<? super T> comparator = (Comparator<? super T>) s.readObject();
     int size = s.readInt();
     map = new TreeMap<T, String>(comparator);
-    ((TreeMap<T, String>) map).putFromObjStream(s, size, false);
+    ((TreeMap<T, String>) map).putFromObjStream(s, size, "");
   }
 
   /**