TreeMap is now implemented. Patch by: jat, rovrevik Review by: scottb git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@2324 8db76d5a-ed1c-0410-87a9-c151d255dfc7

diff --git a/user/super/com/google/gwt/emul/java/util/AbstractMap.java b/user/super/com/google/gwt/emul/java/util/AbstractMap.java
index e85ba13..fffd70b 100644
--- a/user/super/com/google/gwt/emul/java/util/AbstractMap.java
+++ b/user/super/com/google/gwt/emul/java/util/AbstractMap.java

@@ -87,6 +87,7 @@
     int hashCode = 0;
     for (Entry<K, V> entry : entrySet()) {
       hashCode += entry.hashCode();
+      hashCode = ~~hashCode;
     }
     return hashCode;
   }

diff --git a/user/super/com/google/gwt/emul/java/util/TreeMap.java b/user/super/com/google/gwt/emul/java/util/TreeMap.java
index 090016c..bc6c293 100644
--- a/user/super/com/google/gwt/emul/java/util/TreeMap.java
+++ b/user/super/com/google/gwt/emul/java/util/TreeMap.java

@@ -1,5 +1,5 @@
 /*
- * Copyright 2007 Google Inc.
+ * Copyright 2008 Google Inc.
  * 
  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
  * use this file except in compliance with the License. You may obtain a copy of
@@ -15,106 +15,965 @@
  */
 package java.util;
 
-/**
- * Sorted map implementation, guarantees log(n) complexity for containsKey, get,
- * put, and remove. <a
- * href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/TreeMap.html">[Sun
- * docs]</a>
- * 
- * @param <K> key type.
- * @param <V> value type.
- */
-public class TreeMap<K, V> extends AbstractMap<K, V> implements
-    SortedMap<K, V>, Cloneable {
+import java.io.Serializable;
 
+/**
+ * Implements a TreeMap using a red-black tree. This guarantees O(log n)
+ * performance on lookups, inserts, and deletes while maintaining linear
+ * in-order traversal time. Null keys and values are fully supported if the
+ * comparator supports them (the default comparator does not).
+ * 
+ * @param <K> key type
+ * @param <V> value type
+ */
+public class TreeMap<K extends Comparable<K>, V> extends AbstractMap<K, V>
+    implements SortedMap<K, V>, Serializable {
+  /*
+   * Implementation derived from public domain C implementation as of 5
+   * September 2007 at:
+   * http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
+   * written by Julienne Walker.
+   * 
+   * This version does not require a parent pointer kept in each node.
+   */
+
+  /**
+   * An iterator for entries kept in a TreeMap.
+   */
+  private class EntryIterator implements Iterator<Entry<K, V>> {
+
+    // The most recent node returned from next(); null if it hasn't been called
+    // or has been deleted.
+    private Node<K, V> current;
+
+    // Lower, inclusive bound on returned keys.
+    private K fromKey;
+
+    /*
+     * Since we don't keep parent pointers, we maintain our position in the tree
+     * via the stack which would be used for iterative in-order traversal. The
+     * top of the stack is always the next node to visit.
+     */
+    private Stack<Node<K, V>> inorderStack;
+
+    // Upper, exclusive bound on returned keys, or null if there is none --
+    // used for iterators on submaps.
+    private K toKey;
+
+    // The type of range bounds on this iterator.
+    private SubMapType type;
+
+    // true if the iterator hasn't been initialized yet.
+    private boolean uninitialized;
+
+    /**
+     * Create a new iterator with no restrictions on the returned values.
+     */
+    public EntryIterator() {
+      this(SubMapType.All, null, null);
+    }
+
+    /**
+     * Create an iterator which may return only a restricted range.
+     * 
+     * @param fromKey the first key to return in the iterator.
+     * @param toKey the upper bound of keys to return.
+     */
+    public EntryIterator(SubMapType type, K fromKey, K toKey) {
+      inorderStack = new Stack<Node<K, V>>();
+      uninitialized = true;
+      this.type = type;
+      this.fromKey = fromKey;
+      this.toKey = toKey;
+    }
+
+    public boolean hasNext() {
+      if (uninitialized) {
+        initialize();
+      }
+      if (inorderStack.isEmpty()) {
+        return false;
+      }
+      return inRange(inorderStack.peek().key);
+    }
+
+    public Entry<K, V> next() {
+      if (uninitialized) {
+        initialize();
+      }
+      /*
+       * After returning the current node, push the left children of its right
+       * child on the stack.
+       */
+      current = inorderStack.pop();
+      if (current == null || !inRange(current.key)) {
+        throw new NoSuchElementException("No more elements");
+      }
+      pushLeftChildren(current.child[RIGHT]);
+      return current;
+    }
+
+    public void remove() {
+      if (current == null) {
+        throw new IllegalStateException("No current element");
+      }
+      TreeMap.this.remove(current.getKey());
+      current = null;
+    }
+
+    private void initialize() {
+      uninitialized = false;
+      pushLeftChildren(root);
+      current = null;
+      if (type == SubMapType.Tail || type == SubMapType.Range) {
+        // TODO(jat): rewrite this similar to getAdjacentEntry()
+        while (!inorderStack.isEmpty()) {
+          current = inorderStack.pop();
+          if (inRange(current.key)) {
+            // we found the starting point, so push it back on the stack
+            inorderStack.push(current);
+            current = null;
+            break;
+          }
+          pushLeftChildren(current.child[RIGHT]);
+        }
+      }
+    }
+
+    private boolean inRange(K key) {
+      if (type == SubMapType.Head || type == SubMapType.Range) {
+        if (cmp.compare(key, toKey) >= 0) {
+          return false;
+        }
+      }
+      if (type == SubMapType.Tail || type == SubMapType.Range) {
+        if (cmp.compare(key, fromKey) < 0) {
+          return false;
+        }
+      }
+      return true;
+    }
+
+    /**
+     * Follow the left children of the specified node, pushing them on the stack
+     * as we go.
+     * 
+     * @param node parent node to follow left children from.
+     */
+    private void pushLeftChildren(Node<K, V> node) {
+      while (node != null) {
+        inorderStack.push(node);
+        node = node.child[LEFT];
+      }
+    }
+  }
+
+  private final class EntrySet extends AbstractSet<Entry<K, V>> {
+    @Override
+    public void clear() {
+      TreeMap.this.clear();
+    }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public boolean contains(Object o) {
+      if (!(o instanceof Map.Entry)) {
+        return false;
+      }
+      Map.Entry<K, V> entry = (Entry<K, V>) o; // suppress unchecked
+      Entry<K, V> lookupEntry = getEntry(entry.getKey());
+      return lookupEntry != null
+          && Utility.equalsWithNullCheck(lookupEntry.getValue(),
+              entry.getValue());
+    }
+
+    @Override
+    public Iterator<Entry<K, V>> iterator() {
+      return new EntryIterator();
+    }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public boolean remove(Object o) {
+      /*
+       * TODO(jat): is this safe since we can copy a predecessor's data to an
+       * interior node when it is deleted? I think so since we can only go
+       * through the iterator in ascending order, so we will have passed the one
+       * that was copied by the time we can delete a node that will make that
+       * copy.
+       */
+      if (!(o instanceof Map.Entry)) {
+        return false;
+      }
+      Map.Entry<K, V> entry = (Map.Entry<K, V>) o; // suppress unchecked
+      State<V> state = new State<V>();
+      state.matchValue = true;
+      state.value = entry.getValue();
+      return removeWithState(entry.getKey(), state);
+    }
+
+    @Override
+    public int size() {
+      return TreeMap.this.size();
+    }
+  };
+
+  /**
+   * Tree node.
+   * 
+   * @param <K> key type
+   * @param <V> value type
+   */
+  private static class Node<K, V> implements Entry<K, V> {
+    /*
+     * The children are kept in an array to minimize the normal duplication of
+     * code.
+     */
+    protected Node<K, V>[] child;
+    protected boolean isRed;
+    protected K key;
+    protected V value;
+
+    /**
+     * Create a red node.
+     * 
+     * @param key
+     * @param value
+     */
+    public Node(K key, V value) {
+      this(key, value, true);
+    }
+
+    /**
+     * Create a node of the specified color.
+     * 
+     * @param key
+     * @param value
+     * @param isRed true if this should be a red node, false for black
+     */
+    @SuppressWarnings("unchecked")
+    // create array of generic elements
+    public Node(K key, V value, boolean isRed) {
+      this.key = key;
+      this.value = value;
+      child = new Node[2]; // suppress unchecked
+      this.isRed = isRed;
+    }
+
+    @SuppressWarnings("unchecked")
+    // generic cast
+    @Override
+    public boolean equals(Object o) {
+      if (!(o instanceof Node)) {
+        return false;
+      }
+      Node<K, V> other = (Node<K, V>) o; // suppress unchecked
+      return Utility.equalsWithNullCheck(key, other.key)
+          && Utility.equalsWithNullCheck(value, other.value);
+    }
+
+    public K getKey() {
+      return key;
+    }
+
+    public V getValue() {
+      return value;
+    }
+
+    @Override
+    public int hashCode() {
+      int keyHash = (key != null ? key.hashCode() : 0);
+      int valueHash = (value != null ? value.hashCode() : 0);
+      return keyHash ^ valueHash;
+    }
+
+    public V setValue(V value) {
+      V old = this.value;
+      this.value = value;
+      return old;
+    }
+
+    @Override
+    public String toString() {
+      return (isRed ? "R: " : "B: ") + key + "=" + value;
+    }
+  }
+
+  /**
+   * A state object which is passed down the tree for both insert and remove.
+   * All uses make use of the done flag to indicate when no further rebalancing
+   * of the tree is required. Remove methods use the found flag to indicate when
+   * the desired key has been found. value is used both to return the value of a
+   * removed node as well as to pass in a value which must match (used for
+   * entrySet().remove(entry)), and the matchValue flag is used to request this
+   * behavior.
+   * 
+   * @param <V> value type
+   */
+  private static class State<V> {
+    public boolean done;
+    public boolean found;
+    public boolean matchValue;
+    public V value;
+
+    @Override
+    public String toString() {
+      return "State: mv=" + matchValue + " value=" + value + " done=" + done
+          + " found=" + found;
+    }
+  }
+
+  private class SubMap extends AbstractMap<K, V> implements SortedMap<K, V> {
+
+    // valid only if type is Range or Tail
+    public final K fromKey;
+
+    // valid only if type is Range or Head
+    public final K toKey;
+
+    public final SubMapType type;
+
+    SubMap(SubMapType type, K fromKey, K toKey) {
+      switch (type) {
+        case Range:
+          if (cmp.compare(toKey, fromKey) < 0) {
+            throw new IllegalArgumentException("subMap: " + toKey
+                + " less than " + fromKey);
+          }
+          break;
+        case Head:
+          // check key for compatibility with comparator
+          cmp.compare(toKey, toKey);
+          break;
+        case Tail:
+          // check key for compatibility with comparator
+          cmp.compare(fromKey, fromKey);
+          break;
+      }
+      this.type = type;
+      this.fromKey = fromKey;
+      this.toKey = toKey;
+    }
+
+    public Comparator<? super K> comparator() {
+      return TreeMap.this.comparator();
+    }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public boolean containsKey(Object k) {
+      K key = (K) k; // suppress unchecked
+      if (!inRange(key)) {
+        return false;
+      }
+      return TreeMap.this.containsKey(k);
+    }
+
+    @Override
+    public Set<java.util.Map.Entry<K, V>> entrySet() {
+      return new AbstractSet<Entry<K, V>>() {
+
+        @SuppressWarnings("unchecked")
+        @Override
+        public boolean contains(Object o) {
+          if (!(o instanceof Map.Entry)) {
+            return false;
+          }
+          Map.Entry<K, V> entry = (Entry<K, V>) o; // suppress unchecked
+          K key = entry.getKey();
+          if (!inRange(key)) {
+            return false;
+          }
+          Entry<K, V> lookupEntry = getEntry(key);
+          return lookupEntry != null
+              && Utility.equalsWithNullCheck(lookupEntry.getValue(),
+                  entry.getValue());
+        }
+
+        @Override
+        public Iterator<Entry<K, V>> iterator() {
+          return new EntryIterator(type, fromKey, toKey);
+        }
+
+        @SuppressWarnings("unchecked")
+        @Override
+        public boolean remove(Object o) {
+          if (!(o instanceof Map.Entry)) {
+            return false;
+          }
+          Map.Entry<K, V> entry = (Map.Entry<K, V>) o; // suppress unchecked
+          if (!inRange(entry.getKey())) {
+            return false;
+          }
+          State<V> state = new State<V>();
+          state.matchValue = true;
+          state.value = entry.getValue();
+          return removeWithState(entry.getKey(), state);
+        }
+
+        @Override
+        public int size() {
+          // TODO(jat): more efficient way to do this?
+          int n = 0;
+          Iterator<Entry<K, V>> it = iterator();
+          while (it.hasNext()) {
+            it.next();
+            n++;
+          }
+          return n;
+        }
+      };
+    }
+
+    public K firstKey() {
+      Node<K, V> node = getNodeAtOrAfter(fromKey);
+      if (node == null || cmp.compare(node.key, toKey) > 0) {
+        throw new NoSuchElementException();
+      }
+      return node.key;
+    }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public V get(Object k) {
+      K key = (K) k; // suppress unchecked
+      if (!inRange(key)) {
+        return null;
+      }
+      return TreeMap.this.get(key);
+    }
+
+    public SortedMap<K, V> headMap(K toKey) {
+      if (cmp.compare(toKey, this.toKey) > 0) {
+        throw new IllegalArgumentException("subMap: " + toKey
+            + " greater than " + this.toKey);
+      }
+      if (type == SubMapType.Range || type == SubMapType.Tail) {
+        return TreeMap.this.subMap(fromKey, toKey);
+      } else {
+        return TreeMap.this.headMap(toKey);
+      }
+    }
+
+    public K lastKey() {
+      Node<K, V> node = getNodeBefore(toKey);
+      if (node == null || cmp.compare(node.key, fromKey) < 0) {
+        throw new NoSuchElementException();
+      }
+      return node.key;
+    }
+
+    @Override
+    public V put(K key, V value) {
+      if (!inRange(key)) {
+        throw new IllegalArgumentException(key + " outside the range "
+            + fromKey + " to " + toKey);
+      }
+      return TreeMap.this.put(key, value);
+    }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public V remove(Object k) {
+      K key = (K) k; // suppress unchecked
+      if (!inRange(key)) {
+        return null;
+      }
+      return TreeMap.this.remove(key);
+    }
+
+    public SortedMap<K, V> subMap(K newFromKey, K newToKey) {
+      if ((type == SubMapType.Range || type == SubMapType.Tail)
+          && cmp.compare(newFromKey, fromKey) < 0) {
+        throw new IllegalArgumentException("subMap: " + newFromKey
+            + " less than " + fromKey);
+      }
+      if ((type == SubMapType.Range || type == SubMapType.Head)
+          && cmp.compare(newToKey, toKey) > 0) {
+        throw new IllegalArgumentException("subMap: " + newToKey
+            + " greater than " + toKey);
+      }
+      return TreeMap.this.subMap(newFromKey, newToKey);
+    }
+
+    public SortedMap<K, V> tailMap(K fromKey) {
+      if ((type == SubMapType.Range || type == SubMapType.Tail)
+          && cmp.compare(fromKey, this.fromKey) < 0) {
+        throw new IllegalArgumentException("subMap: " + fromKey + " less than "
+            + this.fromKey);
+      }
+      if (type == SubMapType.Range || type == SubMapType.Head) {
+        return TreeMap.this.subMap(fromKey, toKey);
+      } else {
+        return TreeMap.this.tailMap(fromKey);
+      }
+    }
+
+    private boolean inRange(K key) {
+      if (type == SubMapType.Head || type == SubMapType.Range) {
+        if (cmp.compare(key, toKey) >= 0) {
+          return false;
+        }
+      }
+      if (type == SubMapType.Tail || type == SubMapType.Range) {
+        if (cmp.compare(key, fromKey) < 0) {
+          return false;
+        }
+      }
+      return true;
+    }
+  }
+
+  private enum SubMapType {
+    All, Head, Range, Tail,
+  }
+
+  /**
+   * Default comparator, requires the key type implement Comparable. Will fail
+   * on null values.
+   */
+  @SuppressWarnings("unchecked")
+  private static Comparator<?> DEFAULT_COMPARATOR = new Comparator<Comparable>() {
+    public int compare(Comparable a, Comparable b) {
+      // Explicit null check to match JRE specs
+      if (a == null || b == null) {
+        throw new NullPointerException();
+      }
+      return a.compareTo(b);
+    }
+  };
+
+  private static final int LEFT = 0;
+  private static final int RIGHT = 1;
+
+  private static int otherChild(int child) {
+    assert (child == 0 || child == 1);
+    return 1 - child;
+  }
+
+  // The comparator to use.
+  private Comparator<? super K> cmp;
+
+  // The root of the tree.
+  private Node<K, V> root;
+
+  // The number of nodes in the tree.
+  private int size = 0;
+
+  @SuppressWarnings("unchecked")
   public TreeMap() {
-    this(Comparators.natural());
+    this((Comparator<? super K>) DEFAULT_COMPARATOR);
   }
 
   public TreeMap(Comparator<? super K> c) {
-    // TODO(jat): implement
-    throw new UnsupportedOperationException("TreeMap not implemented");
+    root = null;
+    cmp = c;
   }
 
-  public TreeMap(Map<? extends K, ? extends V> m) {
+  public TreeMap(Map<? extends K, ? extends V> map) {
     this();
-    putAll(m);
+    putAll(map);
   }
 
-  public TreeMap(SortedMap<? extends K, ? extends V> m) {
-    // TODO(jat): optimize
-    this((Map<? extends K, ? extends V>) m);
+  @SuppressWarnings("unchecked")
+  public TreeMap(SortedMap<K, ? extends V> map) {
+    cmp = map.comparator();
+    if (cmp == null) {
+      cmp = (Comparator<? super K>) DEFAULT_COMPARATOR;
+    }
+    putAll(map); // TODO(jat): more efficient init from sorted map
   }
 
   @Override
   public void clear() {
-    // TODO(jat): implement
+    root = null;
+    size = 0;
   }
 
   public Comparator<? super K> comparator() {
-    // TODO(jat): implement
-    return null;
+    if (cmp == DEFAULT_COMPARATOR) {
+      return null;
+    }
+    return cmp;
   }
 
+  @SuppressWarnings("unchecked")
   @Override
   public boolean containsKey(Object key) {
-    // TODO(jat): implement
-    return false;
+    return getEntry((K) key) != null; // suppress unchecked cast
   }
 
   @Override
-  public Set<Map.Entry<K, V>> entrySet() {
-    // TODO(jat): implement
-    return null;
+  public Set<Entry<K, V>> entrySet() {
+    return new EntrySet();
   }
 
   public K firstKey() {
-    // TODO(jat): implement
-    return null;
+    if (root == null) {
+      throw new NoSuchElementException();
+    }
+    Node<K, V> node = root;
+    while (node.child[LEFT] != null) {
+      node = node.child[LEFT];
+    }
+    return node.key;
   }
 
+  @SuppressWarnings("unchecked")
   @Override
-  public V get(Object key) {
-    // TODO(jat): implement
-    return null;
+  public V get(Object k) {
+    K key = (K) k; // suppress unchecked
+
+    /*
+     * Don't bother validating the key as getEntry does that internally if the
+     * map is non-empty. This is against the spec but matches JRE 1.5 behavior.
+     */
+
+    Node<K, V> entry = getEntry(key);
+    return entry != null ? entry.getValue() : null;
   }
 
   public SortedMap<K, V> headMap(K toKey) {
-    // TODO(jat): implement
-    return null;
+    return new SubMap(SubMapType.Head, null, toKey);
   }
 
   public K lastKey() {
-    // TODO(jat): implement
-    return null;
+    if (root == null) {
+      throw new NoSuchElementException();
+    }
+    Node<K, V> node = root;
+    while (node.child[RIGHT] != null) {
+      node = node.child[RIGHT];
+    }
+    return node.key;
   }
 
   @Override
   public V put(K key, V value) {
-    // TODO(jat): implement
-    return null;
+    Node<K, V> node = new Node<K, V>(key, value);
+    State<V> state = new State<V>();
+    root = insert(root, node, state);
+    if (!state.found) {
+      ++size;
+    }
+    root.isRed = false;
+    return state.value;
   }
 
-  @Override
-  public V remove(Object key) {
-    // TODO(jat): implement
-    return null;
+  @SuppressWarnings("unchecked")
+  public V remove(Object keyObj) {
+    K key = (K) keyObj; // suppress unchecked cast
+    State<V> state = new State<V>();
+    removeWithState(key, state);
+    return state.value;
   }
 
   @Override
   public int size() {
-    // TODO(jat): implement
-    return 0;
+    return size;
   }
 
-  public SortedMap<K, V> subMap(K fromKey, K toKey) {
-    // TODO(jat): implement
-    return null;
+  public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
+    return new SubMap(SubMapType.Range, fromKey, toKey);
   }
 
   public SortedMap<K, V> tailMap(K fromKey) {
-    // TODO(jat): implement
+    return new SubMap(SubMapType.Tail, fromKey, null);
+  }
+
+  /**
+   * Return the first node which compares equal to or greater than the given
+   * key.
+   * 
+   * @param key the key to search for
+   * @return the next node, or null if there is none.
+   */
+  protected Node<K, V> getNodeAtOrAfter(K key) {
+    if (root == null) {
+      return null;
+    }
+    Node<K, V> foundNode = null;
+    Node<K, V> node = root;
+    while (true) {
+      int c = cmp.compare(key, node.key);
+      if (c == 0) {
+        return node;
+      } else if (c > 0) {
+        node = node.child[RIGHT];
+        if (node == null) {
+          // ran off the tree and we are past this node, so return best one
+          return foundNode;
+        }
+      } else {
+        foundNode = node;
+        Node<K, V> nextNode = node.child[LEFT];
+        if (nextNode == null) {
+          // ran off the tree and we are before this node, so return it
+          return node;
+        }
+        node = nextNode;
+      }
+    }
+  }
+
+  /**
+   * Return the last node which is strictly less than the given key.
+   * 
+   * @param key the key to search for
+   * @return the previous node, or null if there is none.
+   */
+  protected Node<K, V> getNodeBefore(K key) {
+    if (root == null) {
+      return null;
+    }
+    Node<K, V> foundNode = null;
+    Node<K, V> node = root;
+    while (true) {
+      int c = cmp.compare(key, node.key);
+      if (c <= 0) {
+        node = node.child[LEFT];
+        if (node == null) {
+          // ran off the tree and we are past this node, so return best one
+          return foundNode;
+        }
+      } else {
+        foundNode = node;
+        Node<K, V> nextNode = node.child[RIGHT];
+        if (nextNode == null) {
+          // ran off the tree and we are before this node, so return it
+          return node;
+        }
+        node = nextNode;
+      }
+    }
+  }
+
+  /**
+   * Used for testing. Validate that the tree meets all red-black correctness
+   * requirements. These include:
+   * 
+   * <pre>
+   *  - root is black
+   *  - no children of a red node may be red
+   *  - the black height of every path through the three to a leaf is exactly the same
+   * </pre>
+   * 
+   * @throws RuntimeException if any correctness errors are detected.
+   */
+  void assertCorrectness() {
+    assertCorrectness(root, true);
+  }
+
+  /**
+   * Internal helper function for public (@see assertCorrectness()).
+   * 
+   * @param tree the subtree to validate.
+   * @param isRed true if the parent of this node is red.
+   * @return the black height of this subtree.
+   * @throws RuntimeException if this RB-tree is not valid.
+   */
+  private int assertCorrectness(Node<K, V> tree, boolean isRed) {
+    if (tree == null) {
+      return 0;
+    }
+    if (isRed && tree.isRed) {
+      throw new RuntimeException("Two red nodes adjacent");
+    }
+
+    if (tree.child[LEFT] != null
+        && cmp.compare(tree.child[LEFT].key, tree.key) > 0) {
+      throw new RuntimeException("Left child " + tree.child[LEFT]
+          + " larger than " + tree);
+    }
+    if (tree.child[RIGHT] != null
+        && cmp.compare(tree.child[RIGHT].key, tree.key) < 0) {
+      throw new RuntimeException("Right child " + tree.child[RIGHT]
+          + " smaller than " + tree);
+    }
+
+    int leftHeight = assertCorrectness(tree.child[LEFT], tree.isRed);
+    int rightHeight = assertCorrectness(tree.child[RIGHT], tree.isRed);
+    if (leftHeight != 0 && rightHeight != 0 && leftHeight != rightHeight) {
+      throw new RuntimeException("Black heights don't match");
+    }
+    return tree.isRed ? leftHeight : leftHeight + 1;
+  }
+
+  /**
+   * Finds an entry given a key and returns the node.
+   * 
+   * @param key the search key
+   * @return the node matching the key or null
+   */
+  private Node<K, V> getEntry(K key) {
+    Node<K, V> tree = root;
+    while (tree != null) {
+      int c = cmp.compare(key, tree.key);
+      if (c == 0) {
+        return tree;
+      }
+      if (c < 0) {
+        tree = tree.child[LEFT];
+      } else {
+        tree = tree.child[RIGHT];
+      }
+    }
     return null;
   }
 
+  private Node<K, V> insert(Node<K, V> tree, Node<K, V> newNode, State<V> state) {
+    if (tree == null) {
+      return newNode;
+    } else {
+      int c = cmp.compare(tree.key, newNode.key);
+      if (c == 0) {
+        state.value = tree.value;
+        state.found = true;
+        tree.value = newNode.value;
+        return tree;
+      }
+      int childNum = (c > 0) ? 0 : 1;
+      tree.child[childNum] = insert(tree.child[childNum], newNode, state);
+      if (isRed(tree.child[childNum])) {
+        if (isRed(tree.child[otherChild(childNum)])) {
+          // both children are red (nulls are black), make both black and me red
+          tree.isRed = true;
+          tree.child[LEFT].isRed = false;
+          tree.child[RIGHT].isRed = false;
+        } else {
+          // 
+          if (isRed(tree.child[childNum].child[childNum])) {
+            tree = rotateSingle(tree, otherChild(childNum));
+          } else if (isRed(tree.child[childNum].child[otherChild(childNum)])) {
+            tree = rotateDouble(tree, otherChild(childNum));
+          }
+        }
+      }
+    }
+    return tree;
+  }
+
+  /**
+   * Return true if <code>node</code> is red. Note that null pointers are
+   * considered black.
+   */
+  private boolean isRed(Node<K, V> node) {
+    return node != null && node.isRed;
+  }
+
+  private boolean removeWithState(K key, State<V> state) {
+    if (root == null) {
+      return false;
+    }
+    Node<K, V> node;
+    Node<K, V> found = null;
+    Node<K, V> parent = null;
+    Node<K, V> grandparent = null;
+
+    // create a fake tree root to minimize special cases for changing the root
+    Node<K, V> head = new Node<K, V>(null, null);
+    int dir = 1;
+    head.child[RIGHT] = root;
+
+    node = head;
+    while (node.child[dir] != null) {
+      int last = dir;
+      grandparent = parent;
+      parent = node;
+      node = node.child[dir];
+      int c = cmp.compare(node.key, key);
+      dir = c < 0 ? RIGHT : LEFT;
+      if (c == 0 && (!state.matchValue || node.value.equals(state.value))) {
+        found = node;
+      }
+      if (!isRed(node) && !isRed(node.child[dir])) {
+        if (isRed(node.child[otherChild(dir)])) {
+          parent = parent.child[last] = rotateSingle(node, dir);
+        } else if (!isRed(node.child[otherChild(dir)])) {
+          Node<K, V> sibling = parent.child[otherChild(last)];
+          if (sibling != null) {
+            if (!isRed(sibling.child[otherChild(last)]) && !isRed(sibling.child[last])) {
+              parent.isRed = false;
+              sibling.isRed = true;
+              node.isRed = true;
+            } else {
+              int dir2 = grandparent.child[RIGHT] == parent ? RIGHT : LEFT;
+              if (isRed(sibling.child[last])) {
+                grandparent.child[dir2] = rotateDouble(parent, last);
+              } else if (isRed(sibling.child[otherChild(last)])) {
+                grandparent.child[dir2] = rotateSingle(parent, last);
+              }
+              node.isRed = grandparent.child[dir2].isRed = true;
+              grandparent.child[dir2].child[LEFT].isRed = false;
+              grandparent.child[dir2].child[RIGHT].isRed = false;
+            }
+          }
+        }
+      }
+    }
+
+    if (found != null) {
+      if (state != null) {
+        state.found = true;
+        state.value = found.value;
+      }
+      found.key = node.key;
+      found.value = node.value;
+      parent.child[parent.child[RIGHT] == node ? RIGHT : LEFT] = node.child[node.child[LEFT] == null
+          ? RIGHT : LEFT];
+      size--;
+    }
+
+    root = head.child[RIGHT];
+    if (root != null) {
+      root.isRed = false;
+    }
+    return state.found;
+  }
+
+  /**
+   * Perform a double rotation, first rotating the child which will become the
+   * root in the opposite direction, then rotating the root in the specified
+   * direction.
+   * 
+   * <pre>
+   *           A                                               F
+   *         B   C    becomes (with rotateDirection=0)       A   C
+   *        D E F G                                         B E   G
+   *                                                       D
+   * </pre>
+   * 
+   * @param tree root of the subtree to rotate
+   * @param rotateDirection the direction to rotate: 0=left, 1=right
+   * @return the new root of the rotated subtree
+   */
+  private Node<K, V> rotateDouble(Node<K, V> tree, int rotateDirection) {
+    // free the pointer of the new root
+    tree.child[otherChild(rotateDirection)] = rotateSingle(
+        tree.child[otherChild(rotateDirection)], otherChild(rotateDirection));
+    return rotateSingle(tree, rotateDirection);
+  }
+
+  /**
+   * Perform a single rotation, pushing the root of the subtree to the specified
+   * direction.
+   * 
+   * <pre>
+   *      A                                              B
+   *    B   C     becomes (with rotateDirection=1)     D   A
+   *   D E                                              E   C
+   * </pre>
+   * 
+   * @param tree the root of the subtree to rotate
+   * @param rotateDirection the direction to rotate: 0=left rotation, 1=right
+   * @return the new root of the rotated subtree
+   */
+  private Node<K, V> rotateSingle(Node<K, V> tree, int rotateDirection) {
+    Node<K, V> save = tree.child[otherChild(rotateDirection)];
+    tree.child[otherChild(rotateDirection)] = save.child[rotateDirection];
+    save.child[rotateDirection] = tree;
+    tree.isRed = true;
+    save.isRed = false;
+    return save;
+  }
 }

diff --git a/user/test/com/google/gwt/emultest/EmulSuite.java b/user/test/com/google/gwt/emultest/EmulSuite.java
index 002d560..462edbb 100644
--- a/user/test/com/google/gwt/emultest/EmulSuite.java
+++ b/user/test/com/google/gwt/emultest/EmulSuite.java

@@ -80,6 +80,7 @@
     suite.addTestSuite(HashSetTest.class);
     suite.addTestSuite(IdentityHashMapTest.class);
     suite.addTestSuite(StackTest.class);
+    suite.addTest(TreeMapSuite.suite());
     // $JUnit-END$
 
     return suite;

diff --git a/user/test/com/google/gwt/emultest/TreeMapSuite.java b/user/test/com/google/gwt/emultest/TreeMapSuite.java
new file mode 100644
index 0000000..ca4ff4e
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/TreeMapSuite.java

@@ -0,0 +1,38 @@
+/*
+ * Copyright 2008 Google Inc.
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.emultest;
+
+import com.google.gwt.emultest.java.util.TreeMapIntegerDoubleTest;
+import com.google.gwt.emultest.java.util.TreeMapIntegerDoubleWithComparatorTest;
+import com.google.gwt.emultest.java.util.TreeMapStringStringTest;
+import com.google.gwt.emultest.java.util.TreeMapStringStringWithComparatorTest;
+import com.google.gwt.junit.tools.GWTTestSuite;
+
+import junit.framework.Test;
+
+/**
+ * Tests <code>TreeMap</code>.
+ */
+public class TreeMapSuite {
+  public static Test suite() {
+    GWTTestSuite suite = new GWTTestSuite("Tests for com.google.gwt.emul.java.util.TreeMap");
+    suite.addTestSuite(TreeMapStringStringTest.class);
+    suite.addTestSuite(TreeMapStringStringWithComparatorTest.class);
+    suite.addTestSuite(TreeMapIntegerDoubleTest.class);
+    suite.addTestSuite(TreeMapIntegerDoubleWithComparatorTest.class);
+    return suite;
+  }
+}

diff --git a/user/test/com/google/gwt/emultest/java/util/TreeMapIntegerDoubleTest.java b/user/test/com/google/gwt/emultest/java/util/TreeMapIntegerDoubleTest.java
new file mode 100644
index 0000000..9dc4909
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/java/util/TreeMapIntegerDoubleTest.java

@@ -0,0 +1,87 @@
+/*
+ * Copyright 2008 Google Inc.
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.emultest.java.util;
+
+/**
+ * Tests <code>TreeMap</code> with a <code>Comparator</code>.
+ */
+public class TreeMapIntegerDoubleTest extends TreeMapTest<Integer, Double> {
+
+  @Override
+  Integer getGreaterThanMaximumKey() {
+    return Integer.MAX_VALUE;
+  }
+
+  @Override
+  Integer[] getKeys() {
+    return new Integer[] {1, 2, 3, 4};
+  }
+
+  @Override
+  Integer[] getKeys2() {
+    return new Integer[] {5, 6, 7, 8};
+  }
+
+  @Override
+  Integer getLessThanMinimumKey() {
+    return Integer.MIN_VALUE;
+  }
+
+  @Override
+  Double[] getValues() {
+    return new Double[] {0.1, 0.2, 0.3, 0.4};
+  }
+
+  @Override
+  Double[] getValues2() {
+    return new Double[] {1.1, 1.2, 1.3, 1.4};
+  }
+
+  @Override
+  protected Object getConflictingKey() {
+    return "key";
+  }
+
+  @Override
+  protected Object getConflictingValue() {
+    return "value";
+  }
+
+  @Override
+  protected Object[] getOtherKeys() {
+    return getKeys2();
+  }
+
+  @Override
+  protected Object[] getOtherValues() {
+    return getValues2();
+  }
+
+  @Override
+  protected Object[] getSampleKeys() {
+    return getKeys();
+  }
+
+  @Override
+  protected Object[] getSampleValues() {
+    return getValues();
+  }
+
+  @Override
+  protected Object[] getNewSampleValues() {
+    return getValues2();
+  }
+}

diff --git a/user/test/com/google/gwt/emultest/java/util/TreeMapIntegerDoubleWithComparatorTest.java b/user/test/com/google/gwt/emultest/java/util/TreeMapIntegerDoubleWithComparatorTest.java
new file mode 100644
index 0000000..83788f7
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/java/util/TreeMapIntegerDoubleWithComparatorTest.java

@@ -0,0 +1,52 @@
+/*
+ * Copyright 2008 Google Inc.
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.emultest.java.util;
+
+import java.util.Comparator;
+import java.util.Map;
+import java.util.SortedMap;
+
+/**
+ * Tests <code>TreeMap</code> with a <code>Comparator</code>.
+ */
+public class TreeMapIntegerDoubleWithComparatorTest extends
+    TreeMapIntegerDoubleTest {
+  @Override
+  protected SortedMap<Integer, Double> createSortedMap() {
+    setComparator(new Comparator<Integer>() {
+      public int compare(Integer o1, Integer o2) {
+        if (o1 == null) {
+          return o2 == null ? 0 : -1;
+        }
+        if (o2 == null) {
+          return 1;
+        }
+        return o1.compareTo(o2);
+      }
+    });
+    return super.createSortedMap();
+  }
+
+  @Override
+  protected Map<Integer, Double> makeEmptyMap() {
+    return createSortedMap();
+  }
+
+  @Override
+  public boolean useNullKey() {
+    return true;
+  }
+}

diff --git a/user/test/com/google/gwt/emultest/java/util/TreeMapStringStringTest.java b/user/test/com/google/gwt/emultest/java/util/TreeMapStringStringTest.java
new file mode 100644
index 0000000..55a49fc
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/java/util/TreeMapStringStringTest.java

@@ -0,0 +1,68 @@
+/*
+ * Copyright 2008 Google Inc.
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.emultest.java.util;
+
+/**
+ * Tests <code>TreeMap</code> with Strings and the natural comparator.
+ */
+public class TreeMapStringStringTest extends TreeMapTest<String, String> {
+
+  @Override
+  String getGreaterThanMaximumKey() {
+    return "z";
+  }
+
+  @Override
+  String[] getKeys() {
+    return convertToStringArray(getSampleKeys());
+  }
+
+  private String[] convertToStringArray(Object[] objArray) {
+    String[] strArray = new String[objArray.length];
+    System.arraycopy(objArray, 0, strArray, 0, objArray.length);
+    return strArray;
+  }
+
+  @Override
+  String[] getKeys2() {
+    return convertToStringArray(getOtherKeys());
+  }
+
+  @Override
+  String getLessThanMinimumKey() {
+    return "a";
+  }
+
+  @Override
+  String[] getValues() {
+    return convertToStringArray(getSampleValues());
+  }
+
+  @Override
+  String[] getValues2() {
+    return convertToStringArray(getOtherValues());
+  }
+
+  @Override
+  protected Object getConflictingKey() {
+    return new Integer(1);
+  }
+
+  @Override
+  protected Object getConflictingValue() {
+    return new Long(42);
+  }
+}

diff --git a/user/test/com/google/gwt/emultest/java/util/TreeMapStringStringWithComparatorTest.java b/user/test/com/google/gwt/emultest/java/util/TreeMapStringStringWithComparatorTest.java
new file mode 100644
index 0000000..51101e0
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/java/util/TreeMapStringStringWithComparatorTest.java

@@ -0,0 +1,52 @@
+/*
+ * Copyright 2008 Google Inc.
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.emultest.java.util;
+
+import java.util.Comparator;
+import java.util.Map;
+import java.util.SortedMap;
+
+/**
+ * Tests <code>TreeMap</code> with a <code>Comparator</code>.
+ */
+public class TreeMapStringStringWithComparatorTest extends
+    TreeMapStringStringTest {
+  @Override
+  protected SortedMap<String, String> createSortedMap() {
+    setComparator(new Comparator<String>() {
+      public int compare(String o1, String o2) {
+        if (o1 == null) {
+          return o2 == null ? 0 : -1;
+        }
+        if (o2 == null) {
+          return 1;
+        }
+        return o1.compareTo(o2);
+      }
+    });
+    return super.createSortedMap();
+  }
+
+  @Override
+  protected Map<String, String> makeEmptyMap() {
+    return createSortedMap();
+  }
+
+  @Override
+  public boolean useNullKey() {
+    return true;
+  }
+}

diff --git a/user/test/com/google/gwt/emultest/java/util/TreeMapTest.java b/user/test/com/google/gwt/emultest/java/util/TreeMapTest.java
new file mode 100644
index 0000000..7e2d760
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/java/util/TreeMapTest.java

@@ -0,0 +1,1861 @@
+/*
+ * Copyright 2008 Google Inc.
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.emultest.java.util;
+
+import com.google.gwt.core.client.GWT;
+import com.google.gwt.core.client.JavaScriptException;
+
+import org.apache.commons.collections.TestMap;
+
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.TreeMap;
+import java.util.Map.Entry;
+
+/**
+ * Tests <code>TreeMap</code>.
+ * 
+ * @param <K> The key type for the underlying TreeMap
+ * @param <V> The value type for the underlying TreeMap
+ * 
+ * TODO(jat): this whole structure needs work. Ideally we would port a new
+ * Apache collections test to GWT, but that is not an insignificant amount of
+ * work.
+ */
+public abstract class TreeMapTest<K extends Comparable<K>, V> extends TestMap {
+  /**
+   * Verify a Collection is explicitly and implicitly empty.
+   * 
+   * @param collection
+   */
+  @SuppressWarnings("unchecked")
+  private static void _assertEmpty(Collection collection) {
+    assertNotNull(collection);
+    assertTrue(collection.isEmpty());
+    assertEquals(0, collection.size());
+    assertNotNull(collection.iterator());
+    assertFalse(collection.iterator().hasNext());
+  }
+
+  /**
+   * Verify a Map is explicitly and implicitly empty.
+   * 
+   * @param map
+   */
+  private static <K, V> void _assertEmpty(Map<K, V> map) {
+    assertNotNull(map);
+    assertTrue(map.isEmpty());
+    assertEquals(0, map.size());
+
+    _assertEmpty(map.values());
+    _assertEmpty(map.keySet());
+    _assertEmpty(map.entrySet());
+  }
+
+  /**
+   * Verify that two Collections are deeply equivalent. Some of the Sets that
+   * need to be verified do not implement a sensible equals method
+   * (TreeMap.values for example).
+   * 
+   * @param expected
+   * @param actual
+   */
+  private static <T> void _assertEquals(Collection<T> expected,
+      Collection<T> actual) {
+    // verify equivalence using collection interface
+    assertEquals(expected.isEmpty(), actual.isEmpty());
+    assertEquals(expected.size(), actual.size());
+    assertTrue(expected.containsAll(actual));
+    assertTrue(actual.containsAll(expected));
+    for (T expectedValue : expected) {
+      assertTrue(actual.contains(expectedValue));
+    }
+    for (T actualValue : actual) {
+      assertTrue(expected.contains(actualValue));
+    }
+  }
+
+  /**
+   * Verify that two Maps are deeply equivalent.
+   * 
+   * @param expected
+   * @param actual
+   */
+  private static <K, V> void _assertEquals(Map<K, V> expected, Map<K, V> actual) {
+    assertEquals(expected.isEmpty(), actual.isEmpty());
+    assertEquals(expected.size(), actual.size());
+
+    _assertEquals(expected.keySet(), actual.keySet());
+    _assertEquals(expected.entrySet(), actual.entrySet());
+
+    // One might think that the following would true:
+    // assertEquals(expected.values(), actual.values());
+    // The following verifies what i would perceive as a bug in the jre
+    // (rlo). The implementation of the Collection returned by the values method
+    // does not implement equals sensibly.
+    assertFalse(expected.values().equals(actual.values()));
+    _assertEquals(expected.values(), actual.values());
+  }
+
+  /**
+   * Verify that two SortedMaps are deeply equivalent.
+   * 
+   * @param expected
+   * @param actual
+   */
+  private static <K, V> void _assertEquals(SortedMap<K, V> expected,
+      SortedMap<K, V> actual) {
+    _assertEquals((Map<K, V>) expected, (Map<K, V>) actual);
+
+    // verify the order of the associated collections
+    assertEquals(expected.keySet().toArray(), actual.keySet().toArray());
+    assertEquals(expected.entrySet().toArray(), actual.entrySet().toArray());
+    assertEquals(expected.values().toArray(), actual.values().toArray());
+  }
+
+  /**
+   * Create the expected return of toString for a Map containing only the passed
+   * key and value.
+   * 
+   * @param key
+   * @param value
+   * @return
+   */
+  private static <K, V> String makeEntryString(K key, V value) {
+    return "{" + key + "=" + value + "}";
+  }
+
+  /**
+   * comparator used when creating the SortedMap.
+   */
+  private Comparator<K> comparator = null;
+  private boolean isClearSupported = true;
+  private boolean isNullKeySupported = true;
+  private boolean isNullValueSupported = true;
+  private boolean isPutAllSupported = true;
+  private boolean isPutSupported = true;
+  private boolean isRemoveSupported = true;
+
+  public String getModuleName() {
+    return "com.google.gwt.emultest.EmulSuite";
+  }
+
+  /**
+   * Test method for 'java.util.Map.clear()'.
+   * 
+   * @see java.util.Map#clear()
+   */
+  public void testClear() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isClearSupported) {
+      // Execute this test only if supported.
+      Map<K, V> map = createMap();
+      map.put(getKeys()[0], getValues()[0]);
+      assertFalse(map.isEmpty());
+      map.clear();
+      _assertEmpty(map);
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.clear()'.
+   * 
+   * @see java.util.Map#clear()
+   */
+  public void testClear_throwsUnsupportedOperationException() {
+    Map<K, V> map = createMap();
+    if (!isClearSupported) {
+      try {
+        map.clear();
+        fail("expected exception");
+      } catch (UnsupportedOperationException e) {
+        // expected outcome
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.lang.Object.clone()'.
+   */
+  public void testClone() {
+    // Map<K, V> map = createMap();
+    // Check empty clone behavior
+    // TODO (rlo) having .clone() in the code kills the test
+    // SortedMap<K, V> clone = (SortedMap<K, V>)
+    // map.clone();
+    // assertNotNull(clone);
+    // testEquivalent(map, clone);
+    //
+    // // Check non-empty clone behavior
+    // map.put(KEY_1, getValues()[0]);
+    // map.put(KEY_2, getValues()[1]);
+    // map.put(KEY_3, getValues()[2]);
+    // clone = (SortedMap<K, V>) map.clone();
+    // assertNotNull(clone);
+    // testEquivalent(map, clone);
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.comparator()'.
+   * 
+   * @see java.util.SortedMap#comparator()
+   */
+  public void testComparator() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+    if (isNaturalOrder()) {
+      assertEquals(null, sortedMap.comparator());
+    } else {
+      assertEquals(getComparator(), sortedMap.comparator());
+    }
+  }
+
+  /**
+   * Test method for default constructor.
+   * 
+   * @see java.util.TreeMap#TreeMap()
+   */
+  public void testConstructor() {
+    TreeMap<K, V> treeMap = new TreeMap<K, V>();
+    _assertEmpty(treeMap);
+  }
+
+  /**
+   * Test method for 'java.util.TreeMap.TreeMap(Comparator)'.
+   * 
+   * @see java.util.TreeMap#TreeMap(Comparator)
+   */
+  public void testConstructor_comparator() {
+    TreeMap<K, V> treeMap = new TreeMap<K, V>(getComparator());
+    _assertEmpty(treeMap);
+    if (isNaturalOrder()) {
+      assertNull(treeMap.comparator());
+    } else {
+      assertSame(getComparator(), treeMap.comparator());
+    }
+  }
+
+  /**
+   * Test method for 'java.util.TreeMap.TreeMap(Map)'.
+   * 
+   * @see java.util.TreeMap#TreeMap(Map)
+   */
+  public void testConstructor_Map() {
+    // The source map should be just a Map. Not a sorted map.
+    Map<K, V> sourceMap = new HashMap<K, V>();
+
+    // populate the source map
+    sourceMap.put(getKeys()[0], getValues()[0]);
+    sourceMap.put(getKeys()[1], getValues()[1]);
+    sourceMap.put(getKeys()[2], getValues()[2]);
+
+    TreeMap<K, V> copyConstructed = new TreeMap<K, V>(sourceMap);
+    _assertEquals(sourceMap, copyConstructed);
+  }
+
+  /**
+   * Test method for 'java.util.TreeMap.TreeMap(Map)'.
+   * 
+   * @see java.util.TreeMap#TreeMap(Map)
+   */
+  @SuppressWarnings("unchecked")
+  public void testConstructor_Map_throwsClassCastException() {
+    Map sourceMap = createMap();
+    sourceMap.put(getConflictingKey(), getConflictingValue());
+    new TreeMap<K, V>(sourceMap);
+
+    // This does not fail as might be expected.
+    // TODO I don't know of any case where this could happen.
+    // try {
+    // new TreeMap<K, V>(sourceMap);
+    // fail("expected exception");
+    // } catch (ClassCastException e) {
+    // // expected outcome
+    // }
+  }
+
+  /**
+   * Test method for 'java.util.TreeMap.TreeMap(Map)'.
+   * 
+   * @see java.util.TreeMap#TreeMap(Map)
+   */
+  public void testConstructor_Map_throwsNullPointerException() {
+    try {
+      new TreeMap<K, V>((Map<K, V>) null);
+      fail("expected exception");
+    } catch (NullPointerException e) {
+      // expected outcome
+    } catch (JavaScriptException e) {
+      // in web mode we don't actually do null checks, so we get a JS exception
+    }
+  }
+
+  /**
+   * Test method for 'java.util.TreeMap.TreeMap(SortedMap)'.
+   * 
+   * @see java.util.TreeMap#TreeMap(SortedMap)
+   */
+  public void testConstructor_SortedMap() {
+    SortedMap<K, V> sourceMap = new TreeMap<K, V>();
+    _assertEmpty(sourceMap);
+
+    // populate the source map
+    sourceMap.put(getKeys()[0], getValues()[0]);
+    sourceMap.put(getKeys()[1], getValues()[1]);
+    sourceMap.put(getKeys()[2], getValues()[2]);
+
+    TreeMap<K, V> copyConstructed = new TreeMap<K, V>(sourceMap);
+    _assertEquals(sourceMap, copyConstructed);
+  }
+
+  /**
+   * Test method for 'java.util.TreeMap.TreeMap(SortedMap).
+   * 
+   * @see java.util.TreeMap#TreeMap(SortedMap)
+   */
+  public void testConstructor_SortedMap_throwsNullPointerException() {
+    try {
+      new TreeMap<K, V>((SortedMap<K, V>) null);
+      fail("expected exception");
+    } catch (NullPointerException e) {
+      // expected outcome
+    } catch (JavaScriptException e) {
+      // in web mode we don't actually do null checks, so we get a JS exception
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.containsKey(Object)'. *
+   * 
+   * @see java.util.Map#containsKey(Object)
+   */
+  public void testContainsKey() {
+    Map<K, V> map = createMap();
+    assertFalse(map.containsKey(getKeys()[0]));
+    assertNull(map.put(getKeys()[0], getValues()[0]));
+    assertEquals(1, map.keySet().size());
+    assertTrue(map.containsKey(getKeys()[0]));
+    assertFalse(map.containsKey(getKeys()[1]));
+  }
+
+  /**
+   * Test method for 'java.util.Map.containsKey(Object)'.
+   * 
+   * @see java.util.Map#containsKey(Object)
+   */
+  public void testContainsKey_throwsClassCastException() {
+    Map<K, V> map = createMap();
+    map.put(getKeys()[0], getValues()[0]);
+    try {
+      map.containsKey(getConflictingKey());
+      assertTrue("CCE expected in hosted mode", GWT.isScript());
+    } catch (ClassCastException e) {
+      // expected outcome
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.containsKey(Object)'.
+   * 
+   * @see java.util.Map#containsKey(Object)
+   */
+  public void testContainsKey_throwsNullPointerException() {
+    Map<K, V> map = createMap();
+    if (isNaturalOrder() && !isNullKeySupported) {
+      try {
+        map.containsKey(null);
+        fail("expected exception");
+      } catch (NullPointerException e) {
+        // expected outcome
+      } catch (JavaScriptException e) {
+        // in web mode we don't actually do null checks, so we get a JS
+        // exception
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.containsValue(Object)'.
+   * 
+   * @see java.util.Map#containsValue(Object)
+   */
+  public void testContainsValue() {
+    Map<K, V> map = createMap();
+    assertFalse(map.containsValue(getValues()[0]));
+    map.put(getKeys()[0], getValues()[0]);
+    assertEquals(1, map.values().size());
+    assertTrue(map.containsValue(getValues()[0]));
+    assertFalse(map.containsValue(getKeys()[0]));
+    assertFalse(map.containsValue(getValues()[1]));
+    assertFalse(map.containsValue(null));
+    map.put(getKeys()[0], null);
+    assertTrue(map.containsValue(null));
+  }
+
+  /**
+   * Test method for 'java.util.Map.containsValue(Object)'.
+   * 
+   * @see java.util.Map#containsValue(Object)
+   */
+  public void testContainsValue_throwsClassCastExcption() {
+    Map<K, V> map = createMap();
+    map.put(getKeys()[0], getValues()[0]);
+    map.containsValue(getConflictingValue());
+
+    // You might think this should throw an exception here but, no. Makes
+    // sense since the class cast is attributed to comparability of the
+    // keys... generics really have nothing to do with it .
+
+    // try {
+    // map.containsValue(getConflictingValue());
+    // fail("expected exception");
+    // } catch (ClassCastException e) {
+    // // expected outcome
+    // }
+  }
+
+  /**
+   * Test method for 'java.util.Map.containsValue(Object)'.
+   * 
+   * @see java.util.Map#containsValue(Object)
+   */
+  public void testContainsValue_throwsNullPointerException() {
+    Map<K, V> map = createMap();
+    if (!isNullValueSupported) {
+      try {
+        map.containsValue(null);
+        fail("expected exception");
+      } catch (NullPointerException e) {
+        // expected outcome
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.entrySet().remove(Object)'.
+   * 
+   * @see java.util.Map#entrySet()
+   */
+  public void testEntrySet_add_throwsUnsupportedOperationException() {
+    Map<K, V> map = createMap();
+    try {
+      map.entrySet().add(new Entry<K, V>() {
+        public K getKey() {
+          return null;
+        }
+
+        public V getValue() {
+          return null;
+        }
+
+        public V setValue(V value) {
+          return null;
+        }
+      });
+      fail("expected exception");
+    } catch (UnsupportedOperationException e) {
+      // expected outcome
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.entrySet()'.
+   * 
+   * @see java.util.Map#entrySet()
+   */
+  public void testEntrySet_entries0() {
+    Map<K, V> map = createMap();
+    Set<Entry<K, V>> entrySet = map.entrySet();
+    _assertEmpty(entrySet);
+  }
+
+  /**
+   * Test method for 'java.util.Map.entrySet()'.
+   * 
+   * @see java.util.Map#entrySet()
+   */
+  public void testEntrySet_entries1() {
+    Map<K, V> map = createMap();
+    map.put(getKeys()[0], getValues()[0]);
+
+    // Verify the view correctly represents the map
+    Set<Entry<K, V>> entrySet = map.entrySet();
+    assertNotNull(entrySet);
+    Iterator<Entry<K, V>> iter = entrySet.iterator();
+    assertNotNull(iter);
+    assertTrue(iter.hasNext());
+    Entry<K, V> entry = iter.next();
+    assertNotNull(entry);
+
+    assertEquals(entry.getKey(), getKeys()[0]);
+    assertEquals(entry.getValue(), getValues()[0]);
+  }
+
+  /**
+   * Test method for 'java.util.Map.entrySet()'.
+   * 
+   * @see java.util.Map#entrySet()
+   */
+  public void testEntrySet_entries1_view() {
+    Map<K, V> map = createMap();
+    // Get a view of the entry set before modifying the underlying map.
+    Set<Entry<K, V>> entrySet = map.entrySet();
+    map.put(getKeys()[0], getValues()[0]);
+
+    // Verify that the entries view reflects updates to the map.
+    assertEquals(entrySet.iterator().next().getKey(), getKeys()[0]);
+    assertEquals(entrySet.iterator().next().getValue(), getValues()[0]);
+  }
+
+  /**
+   * Test method for 'java.util.Map.entrySet()'.
+   * 
+   * @see java.util.Map#entrySet()
+   */
+  public void testEntrySet_entries1_view_modify() {
+    Map<K, V> map = createMap();
+    Set<Entry<K, V>> entrySet = map.entrySet(); // get view before modification
+    map.put(getKeys()[0], getValues()[0]); // put a value
+    map.put(getKeys()[0], getValues()[1]); // overwrite the value
+
+    // Verify that the entries view reflects updates to the map.
+    assertEquals(entrySet.iterator().next().getKey(), getKeys()[0]);
+    assertEquals(entrySet.iterator().next().getValue(), getValues()[1]);
+
+    // Verify that the entries view is updated on removes to the map.
+    map.remove(getKeys()[0]);
+    _assertEmpty(entrySet);
+  }
+
+  public void testEntrySet_entry_setValue() {
+    Map<K, V> map = createMap();
+    map.put(getKeys()[0], getValues()[0]);
+    map.entrySet().iterator().next().setValue(getValues()[1]);
+    assertTrue(map.containsValue(getValues()[1]));
+  }
+
+  /**
+   * Test method for 'java.util.Map.entrySet().remove(Object)'.
+   * 
+   * @see java.util.Map#entrySet()
+   */
+  public void testEntrySet_remove() {
+    Map<K, V> map = createMap();
+    map.put(getKeys()[0], getValues()[0]);
+
+    Set<Entry<K, V>> entrySet = map.entrySet();
+    assertTrue(entrySet.remove(entrySet.iterator().next()));
+    assertTrue(entrySet.isEmpty());
+    assertEquals(entrySet.size(), map.size());
+  }
+
+  /**
+   * Test method for 'java.util.Map.entrySet().remove(Object)'.
+   * 
+   * @see java.util.Map#entrySet()
+   */
+  public void testEntrySet_remove_equivalentEntry() {
+    Map<K, V> map0 = createMap();
+    map0.put(getKeys()[0], getValues()[0]);
+
+    Map<K, V> map1 = createMap();
+    map1.put(getKeys()[0], getValues()[1]);
+
+    // Verify attempting to remove an equivalent entry from a different map has
+    // no effect.
+    Set<Entry<K, V>> entrySet0 = map0.entrySet();
+    assertFalse(entrySet0.remove(map1.entrySet().iterator().next()));
+    assertFalse(entrySet0.isEmpty());
+    assertEquals(entrySet0.size(), map0.size());
+  }
+
+  /**
+   * Test method for 'java.util.Object.equals(Object)'.
+   * 
+   * @see java.util.Map#equals(Object)
+   */
+  public void testEquals() {
+    Map<K, V> map0 = createMap();
+    Map<K, V> map1 = createMap();
+    assertTrue(map0.equals(map1));
+    map0.put(getKeys()[0], getValues()[0]);
+    map1.put(getKeys()[0], getValues()[0]);
+    assertTrue(map0.equals(map0));
+    assertTrue(map0.equals(map1));
+    map0.put(getKeys()[1], getValues()[1]);
+    assertFalse(map0.equals(map1));
+  }
+
+  /**
+   * Test method for 'java.lang.Object.finalize()'.
+   */
+  public void testFinalize() {
+    // TODO no tests for finalize?
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.firstKey()'.
+   * 
+   * @see java.util.SortedMap#firstKey()
+   */
+  public void testFirstKey() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+    // test with a single entry map
+    sortedMap.put(getKeys()[0], getValues()[0]);
+    assertEquals(getKeys()[0], sortedMap.firstKey());
+    // is it consistent with other methods
+    assertEquals(sortedMap.keySet().toArray()[0], sortedMap.firstKey());
+    assertEquals(getKeys()[0], sortedMap.lastKey());
+    assertEquals(sortedMap.lastKey(), sortedMap.firstKey());
+
+    // test with two entry map
+    sortedMap.put(getKeys()[1], getValues()[1]);
+    assertEquals(getKeys()[0], sortedMap.firstKey());
+    assertFalse(getKeys()[1].equals(sortedMap.firstKey()));
+    // is it consistent with other methods
+    assertEquals(sortedMap.keySet().toArray()[0], sortedMap.firstKey());
+    assertFalse(getKeys()[0].equals(sortedMap.lastKey()));
+    assertFalse(sortedMap.lastKey().equals(sortedMap.firstKey()));
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.firstKey()'.
+   * 
+   * @see java.util.SortedMap#firstKey()
+   */
+  public void testFirstKey_throwsNoSuchElementException() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+    // test with no entries
+    try {
+      sortedMap.firstKey();
+      fail("expected exception");
+    } catch (NoSuchElementException e) {
+      // expected outcome
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.get(Object)'.
+   * 
+   * @see java.util.Map#get(Object)
+   */
+  public void testGet() {
+    Map<K, V> map = createMap();
+    if (useNullKey()) {
+      assertNull(map.get(null));
+    }
+    assertNull(map.get(getKeys()[0]));
+    assertNull(map.put(getKeys()[0], getValues()[0]));
+    assertEquals(getValues()[0], map.get(getKeys()[0]));
+  }
+
+  /**
+   * Test method for 'java.util.Map.get(Object)'.
+   * 
+   * @see java.util.Map#get(Object)
+   */
+  public void testGet_throwsClassCastException() {
+    Map<K, V> map = createMap();
+    map.put(getKeys()[0], getValues()[0]);
+    try {
+      map.get(getConflictingKey());
+      assertTrue("CCE expected in hosted mode", GWT.isScript());
+    } catch (ClassCastException e) {
+      // expected outcome
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.get(Object)'.
+   * 
+   * @see java.util.Map#get(Object)
+   */
+  public void testGet_throwsNullPointerException() {
+    Map<K, V> map = createMap();
+    map.put(getKeys()[0], getValues()[0]);
+    try {
+      map.get(null);
+      assertTrue("expected exception", useNullKey());
+    } catch (NullPointerException e) {
+      assertFalse("unexpected NPE", useNullKey());
+    }
+  }
+
+  /**
+   * Test method for 'java.lang.Object.hashCode()'.
+   * 
+   * @see java.util.Map#hashCode()
+   */
+  public void testHashCode() {
+    Map<K, V> map0 = createMap();
+    Map<K, V> map1 = createMap();
+
+    int hashCode0 = map0.hashCode();
+    int hashCode1 = map1.hashCode();
+    assertTrue("empty maps have different hash codes", hashCode0 == hashCode1);
+
+    // Check that hashCode changes
+    map0.put(getKeys()[0], getValues()[0]);
+    hashCode0 = map0.hashCode();
+    assertTrue("hash code didn't change", hashCode0 != hashCode1);
+
+    // The above is actually not a completely dependable test because hash codes
+    // are funky at the edges. The hash code of an abstract map is determined by
+    // accumulating the hash code of the contained Entry(s). The TreeMap Entry
+    // hash code implementation will always result in 0 if the exclusive or of
+    // the key and value for the Entry is 0.
+
+    Map<String, String> map2 = new TreeMap<String, String>();
+    Map<Integer, Integer> map3 = new TreeMap<Integer, Integer>();
+
+    map2.put("", "");
+
+    map3.put(0, Integer.MIN_VALUE);
+    map3.put(Integer.MIN_VALUE, 0);
+
+    int hashCode2 = map2.hashCode();
+    int hashCode3 = map3.hashCode();
+    assertEquals("empty string/0 hash codes not the same", hashCode2, hashCode3);
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.headMap(Object)'.
+   * 
+   * @see java.util.SortedMap#headMap(Object)
+   */
+  public void testHeadMap() {
+    // test with no entries
+    assertNotNull(createSortedMap().headMap(getKeys()[0]));
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.headMap(Object)'.
+   * 
+   * @see java.util.SortedMap#headMap(Object)
+   */
+  public void testHeadMap_entries0_size() {
+    // test with no entries
+    assertEquals(0, createSortedMap().headMap(getKeys()[0]).size());
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.headMap(Object)'.
+   * 
+   * @see java.util.SortedMap#headMap(Object)
+   */
+  public void testHeadMap_entries1() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+    // test with a single entry map
+    sortedMap.put(getKeys()[0], getValues()[0]);
+    assertEquals(0, sortedMap.headMap(getKeys()[0]).size());
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.headMap(Object)'.
+   * 
+   * @see java.util.SortedMap#headMap(Object)
+   */
+  public void testHeadMap_entries2() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+    // test with two entry map
+    sortedMap.put(getKeys()[0], getValues()[0]);
+    sortedMap.put(getKeys()[1], getValues()[1]);
+    assertEquals(0, sortedMap.headMap(getKeys()[0]).size());
+    assertEquals(1, sortedMap.headMap(getKeys()[1]).size());
+    assertEquals(getKeys()[0],
+        sortedMap.tailMap(getKeys()[0]).keySet().toArray()[0]);
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.headMap(Object, Object)'.
+   * 
+   * @see java.util.SortedMap#headMap(Object)
+   */
+  @SuppressWarnings("unchecked")
+  public void testHeadMap_throwsClassCastException() {
+    SortedMap sortedMap = createSortedMap();
+    sortedMap.put(getKeys()[0], getValues()[0]);
+    if (isNaturalOrder()) {
+      // TODO Why does this succeed with natural ordering when subMap doesn't?
+      sortedMap.headMap(getConflictingKey());
+    } else {
+      try {
+        sortedMap.headMap(getConflictingKey());
+        assertTrue("CCE expected in hosted mode", GWT.isScript());
+      } catch (ClassCastException e) {
+        // expected outcome
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.headMap(Object, Object)'.
+   * 
+   * @see java.util.SortedMap#headMap(Object)
+   */
+  public void testHeadMap_throwsIllegalArgumentException() {
+    // TODO I don't know of any case where this could happen.
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.headMap(Object, Object)'.
+   * 
+   * @see java.util.SortedMap#headMap(Object)
+   */
+  public void testHeadMap_throwsNullPointerException() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+    try {
+      sortedMap.headMap(null);
+      assertTrue(useNullKey() || GWT.isScript());
+    } catch (NullPointerException e) {
+      assertFalse(useNullKey());
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.isEmpty()'. *
+   * 
+   * @see java.util.Map#isEmpty()
+   * 
+   */
+  public void testIsEmpty() {
+    Map<K, V> sourceMap = createMap();
+    Map<K, V> destMap = createMap();
+
+    destMap.putAll(sourceMap);
+    assertTrue(destMap.isEmpty());
+
+    destMap.put(getKeys()[0], getValues()[0]);
+    assertFalse(destMap.isEmpty());
+
+    destMap.remove(getKeys()[0]);
+    assertTrue(destMap.isEmpty());
+    assertEquals(destMap.size(), 0);
+  }
+
+  /**
+   * Test method for 'java.util.Map.keySet()'.
+   * 
+   * @see java.util.Map#clear()
+   */
+  public void testKeySet() {
+    Map<K, V> map = createMap();
+    map.put(getKeys()[0], getValues()[0]);
+    Set<K> keySet = map.keySet();
+    _assertEquals(keySet, keySet);
+  }
+
+  /**
+   * Test method for 'java.util.Map.keySet()'.
+   * 
+   * @see java.util.Map#clear()
+   */
+  public void testKeySet_viewPut() {
+    Map<K, V> map = createMap();
+    map.put(getKeys()[0], getValues()[0]);
+    Set<K> keySet = map.keySet();
+    assertEquals(1, keySet.size());
+    map.put(getKeys()[1], getValues()[1]);
+    assertEquals(2, keySet.size());
+  }
+
+  /**
+   * Test method for 'java.util.Map.keySet()'.
+   * 
+   * @see java.util.Map#clear()
+   */
+  public void testKeySet_viewRemove() {
+    Map<K, V> map = createMap();
+    map.put(getKeys()[0], getValues()[0]);
+    map.put(getKeys()[1], getValues()[1]);
+    Set<K> keySet = map.keySet();
+    assertEquals(2, keySet.size());
+    map.remove(getKeys()[1]);
+    assertEquals(1, keySet.size());
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.lastKey()'.
+   * 
+   * @see java.util.SortedMap#lastKey()
+   */
+  public void testLastKey() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+
+    // test with a single entry map
+    sortedMap.put(getKeys()[0], getValues()[0]);
+    assertEquals(getKeys()[0], sortedMap.lastKey());
+    // is it consistent with other methods
+    assertEquals(sortedMap.keySet().toArray()[0], sortedMap.lastKey());
+    assertEquals(getKeys()[0], sortedMap.firstKey());
+    assertEquals(sortedMap.firstKey(), sortedMap.lastKey());
+
+    // test with two entry map
+    sortedMap.put(getKeys()[1], getValues()[1]);
+    assertEquals(getKeys()[1], sortedMap.lastKey());
+    assertFalse(getKeys()[0].equals(sortedMap.lastKey()));
+    // is it consistent with other methods
+    assertEquals(sortedMap.keySet().toArray()[1], sortedMap.lastKey());
+    assertEquals(getKeys()[0], sortedMap.firstKey());
+    assertFalse(sortedMap.firstKey().equals(sortedMap.lastKey()));
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.lastKey()'.
+   * 
+   * @see java.util.SortedMap#lastKey()
+   */
+  public void testLastKey_throwsNoSuchElementException() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+    // test with no entries
+    try {
+      sortedMap.lastKey();
+      fail("expected exception");
+    } catch (NoSuchElementException e) {
+      // expected outcome
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.put(Object, Object)'.
+   * 
+   * @see java.util.Map#put(Object, Object)
+   */
+  public void testPut() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutSupported) {
+      Map<K, V> map = createMap();
+      assertNull(map.put(getKeys()[0], getValues()[0]));
+      assertFalse(map.isEmpty());
+      assertEquals(1, map.size());
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.put(Object, Object)'.
+   * 
+   * @see java.util.Map#put(Object, Object)
+   */
+  public void testPut_entries3() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutSupported) {
+      // populate the map
+      Map<K, V> map = createMap();
+      map.put(getKeys()[0], getValues()[0]);
+      map.put(getKeys()[1], getValues()[1]);
+      map.put(getKeys()[2], getValues()[2]);
+
+      // test contents
+      assertFalse(map.isEmpty());
+      assertEquals(3, map.size());
+      // test contains all values
+      Collection<V> values = map.values();
+      assertTrue(values.contains(getValues()[0]));
+      assertTrue(values.contains(getValues()[1]));
+      assertTrue(values.contains(getValues()[2]));
+      Collection<K> keys = map.keySet();
+      // test contains all keys
+      assertTrue(keys.contains(getKeys()[0]));
+      assertTrue(keys.contains(getKeys()[1]));
+      assertTrue(keys.contains(getKeys()[2]));
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.put(Object, Object)'. This test shows some
+   * bad behavior of the TreeMap class. A mapping with null key can be put in
+   * but several methods are are unusable afterward.
+   * 
+   * A SortedMap with natural ordering (no comparator) is supposed to throw a
+   * null pointer exception if a null keys are "not supported". For a natural
+   * ordered TreeMap, a null pointer exception is not thrown. But, the map is
+   * left in a state where any other key based methods result in a null pointer
+   * exception.
+   * 
+   * @see java.util.Map#put(Object, Object)
+   */
+  public void testPut_nullKey_poison() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+
+    if (useNullKey()) {
+      assertNull(sortedMap.put(null, getValues()[0]));
+      assertTrue(sortedMap.containsValue(getValues()[0]));
+
+      // the map methods the continue to function
+      sortedMap.containsValue(null);
+      sortedMap.containsValue(getValues()[0]);
+      sortedMap.entrySet();
+      sortedMap.equals(createMap());
+      sortedMap.hashCode();
+      sortedMap.isEmpty();
+      sortedMap.keySet();
+      sortedMap.putAll(createMap());
+      sortedMap.size();
+      sortedMap.values();
+
+      // all of the sorted map methods still function
+      sortedMap.comparator();
+      sortedMap.firstKey();
+      sortedMap.lastKey();
+      sortedMap.subMap(getLessThanMinimumKey(), getGreaterThanMaximumKey());
+      sortedMap.headMap(getLessThanMinimumKey());
+      sortedMap.tailMap(getLessThanMinimumKey());
+    } else {
+      try {
+        assertNull(sortedMap.put(null, getValues()[0]));
+        // note: first null added is not required to throw NPE since no
+        // comparisons are needed
+      } catch (NullPointerException e) {
+        // expected outcome
+      }
+      try {
+        assertNull(sortedMap.put(null, getValues()[1]));
+        fail("expected exception adding second null");
+      } catch (NullPointerException e) {
+        // expected outcome
+      }
+      try {
+        sortedMap.containsKey(null);
+        fail("expected exception on containsKey(null)");
+      } catch (NullPointerException e) {
+        // expected outcome
+      }
+      try {
+        sortedMap.containsKey(getKeys()[0]);
+        fail("expected exception on contains(key)");
+      } catch (NullPointerException e) {
+        // expected outcome
+      }
+      try {
+        sortedMap.get(null);
+        fail("expected exception on get(null)");
+      } catch (NullPointerException e) {
+        // expected outcome
+      }
+      try {
+        sortedMap.get(getKeys()[0]);
+        fail("expected exception on get(key)");
+      } catch (NullPointerException e) {
+        // expected outcome
+      }
+      try {
+        sortedMap.remove(null);
+        fail("expected exception on remove(null)");
+      } catch (NullPointerException e) {
+        // expected outcome
+      }
+      try {
+        sortedMap.remove(getKeys()[0]);
+        fail("expected exception on remove(key)");
+      } catch (NullPointerException e) {
+        // expected outcome
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.put(Object, Object)'.
+   * 
+   * @see java.util.Map#put(Object, Object)
+   */
+  public void testPut_replace() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutSupported) {
+      Map<K, V> map = createMap();
+      assertNull(map.put(getKeys()[0], getValues()[0]));
+      assertFalse(map.isEmpty());
+      assertEquals(1, map.size());
+
+      assertEquals(map.put(getKeys()[0], getValues()[1]), getValues()[0]);
+      assertEquals(1, map.size());
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.put(Object, Object)'.
+   * 
+   * @see java.util.Map#put(Object, Object)
+   */
+  @SuppressWarnings("unchecked")
+  public void testPut_throwsClassCastException_key() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutSupported) {
+      Map<K, V> map = createMap();
+      map.put(getKeys()[0], getValues()[0]);
+      try {
+        Map untypedMap = map;
+        untypedMap.put(getConflictingKey(), getValues()[1]);
+        assertTrue("CCE expected in hosted mode", GWT.isScript());
+      } catch (ClassCastException e) {
+        // expected outcome
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.put(Object, Object)'.
+   * 
+   * @see java.util.Map#put(Object, Object)
+   */
+  @SuppressWarnings("unchecked")
+  public void testPut_throwsClassCastException_value() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutSupported) {
+      Map<K, V> map = createMap();
+      map.put(getKeys()[0], getValues()[0]);
+
+      Map untypedMap = map;
+      untypedMap.put(getKeys()[1], getConflictingValue());
+      // You might think this should throw an exception here but, no. Makes
+      // sense since the class cast is attributed to comparability of the
+      // keys... generics really have nothing to do with it .
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.put(Object, Object)'.
+   * 
+   * @see java.util.Map#put(Object, Object)
+   */
+  public void testPut_throwsIllegalArgumentException() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutSupported) {
+      // TODO I don't know of any case where this could happen.
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.put(Object, Object)'.
+   * 
+   * @see java.util.Map#put(Object, Object)
+   */
+  public void testPut_throwsNullPointerException() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutSupported) {
+      Map<K, V> map;
+      map = createMap();
+
+      try {
+        map.put(null, getValues()[0]);
+        // first put of a null key is not required to NPE since no comparisons
+        // are needed
+      } catch (NullPointerException e) {
+        assertFalse(useNullKey());
+      }
+
+      try {
+        map.put(null, getValues()[0]);
+        assertTrue(useNullKey());
+      } catch (NullPointerException e) {
+        assertFalse(useNullKey());
+      }
+
+      map = createMap();
+      map.put(getKeys()[0], getValues()[0]);
+      try {
+        map.put(null, getValues()[0]);
+        assertTrue(useNullKey());
+      } catch (NullPointerException e) {
+        assertFalse(useNullKey());
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.put(Object, Object)'.
+   * 
+   * @see java.util.Map#put(Object, Object)
+   */
+  public void testPut_throwsUnsupportedOperationException() {
+    if (!isPutSupported) {
+      Map<K, V> map = createMap();
+      try {
+        map.put(getKeys()[0], getValues()[0]);
+        fail("expected exception");
+      } catch (UnsupportedOperationException e) {
+        // expected outcome
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.putAll(Map)'.
+   * 
+   * @see java.util.Map#putAll(Map)
+   */
+  public void testPutAll() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutAllSupported) {
+      Map<K, V> sourceMap = createMap();
+      sourceMap.put(getKeys()[0], getValues()[0]);
+      sourceMap.put(getKeys()[1], getValues()[1]);
+      sourceMap.put(getKeys()[2], getValues()[2]);
+
+      Map<K, V> destMap = createMap();
+      destMap.putAll(sourceMap);
+      // Make sure that the data is copied correctly
+      _assertEquals(sourceMap, destMap);
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.putAll(Map)'.
+   * 
+   * @see java.util.Map#putAll(Map)
+   */
+  public void testPutAll_addEntries() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutAllSupported) {
+      Map<K, V> sourceMap = createMap();
+      sourceMap.put(getKeys()[0], getValues()[0]);
+
+      Map<K, V> destMap = createMap();
+      destMap.putAll(sourceMap);
+      // Verify that entries get added.
+      sourceMap.put(getKeys()[1], getValues()[1]);
+      destMap.putAll(sourceMap);
+      _assertEquals(sourceMap, destMap);
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.putAll(Map)'.
+   * 
+   * @see java.util.Map#putAll(Map)
+   */
+  public void testPutAll_emptyMap() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutAllSupported) {
+      Map<K, V> sourceMap = createMap();
+      sourceMap.put(getKeys()[0], getValues()[0]);
+
+      Map<K, V> destMap = createMap();
+      destMap.putAll(sourceMap);
+      // Verify that putting an empty map does not clear.
+      destMap.putAll(createMap());
+      _assertEquals(sourceMap, destMap);
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.putAll(Map)'.
+   * 
+   * @see java.util.Map#putAll(Map)
+   */
+  public void testPutAll_overwrite() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutAllSupported) {
+      Map<K, V> sourceMap = createMap();
+      sourceMap.put(getKeys()[0], getValues()[0]);
+
+      Map<K, V> destMap = createMap();
+      destMap.putAll(sourceMap);
+      // Verify that entries get replaced.
+      sourceMap.put(getKeys()[0], getValues()[1]);
+      destMap.putAll(sourceMap);
+      _assertEquals(sourceMap, destMap);
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.putAll(Map)'.
+   * 
+   * @see java.util.Map#putAll(Map)
+   */
+  public void testPutAll_self() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutAllSupported) {
+      Map<K, V> sourceMap = createMap();
+      sourceMap.put(getKeys()[0], getValues()[0]);
+      sourceMap.putAll(sourceMap);
+      // verify putAll with self succeeds and has no effect.
+      assertEquals(1, sourceMap.size());
+      assertEquals(getKeys()[0], sourceMap.keySet().iterator().next());
+      assertEquals(getValues()[0], sourceMap.values().iterator().next());
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.putAll(Map)'.
+   * 
+   * @see java.util.Map#putAll(Map)
+   */
+  @SuppressWarnings("unchecked")
+  public void testPutAll_throwsClassCastException() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutAllSupported) {
+      Map sourceMap = createMap();
+      sourceMap.put(getConflictingKey(), getConflictingValue());
+
+      Map<K, V> destMap = createMap();
+      destMap.put(getKeys()[0], getValues()[0]);
+      try {
+        destMap.putAll(sourceMap);
+        assertTrue("CCE expected in hosted mode", GWT.isScript());
+      } catch (ClassCastException e) {
+        // expected outcome
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.putAll(Map)'.
+   * 
+   * @see java.util.Map#putAll(Map)
+   */
+  public void testPutAll_throwsIllegalOperationException() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutAllSupported) {
+      // TODO I don't know of any case where this could happen.
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.putAll(Map)'.
+   * 
+   * @see java.util.Map#putAll(Map)
+   */
+  public void testPutAll_throwsNullPointerException() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isPutAllSupported) {
+      Map<K, V> map = createMap();
+      try {
+        map.putAll((Map<K, V>) null);
+        fail("expected exception");
+      } catch (NullPointerException e) {
+        // expected outcome
+      } catch (JavaScriptException e) {
+        // in web mode we don't actually do null checks, so we get a JS
+        // exception
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.putAll(Map)'.
+   * 
+   * @see java.util.Map#putAll(Map)
+   */
+  public void testPutAll_throwsUnsupportedOperationException() {
+    Map<K, V> map = createMap();
+    if (!isPutAllSupported) {
+      try {
+        map.putAll(createMap());
+        fail("expected exception");
+      } catch (UnsupportedOperationException e) {
+        // expected outcome
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.remove(Object)'.
+   * 
+   * @see java.util.Map#remove(Object)
+   */
+  public void testRemove() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isRemoveSupported) {
+      Map<K, V> map = createMap();
+
+      // null keys are special
+      if (useNullKey()) {
+        assertNull(map.remove(null));
+      }
+
+      assertNull(map.remove(getKeys()[0]));
+      assertNull(map.put(getKeys()[0], getValues()[0]));
+      assertEquals(map.remove(getKeys()[0]), getValues()[0]);
+      assertNull(map.remove(getKeys()[0]));
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.remove(Object)'.
+   * 
+   * @see java.util.Map#remove(Object)
+   */
+  public void testRemove_throwsClassCastException() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isRemoveSupported) {
+      Map<K, V> map = createMap();
+      map.put(getKeys()[0], getValues()[0]);
+      try {
+        map.remove(getConflictingKey());
+        assertTrue("CCE expected in hosted mode", GWT.isScript());
+      } catch (ClassCastException e) {
+        // expected outcome
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.remove(Object)'.
+   * 
+   * @see java.util.Map#remove(Object)
+   */
+  public void testRemove_throwsNullPointerException() {
+    // The _throwsUnsupportedOperationException version of this test will
+    // verify that the method is not supported.
+    if (isRemoveSupported) {
+      Map<K, V> map;
+      map = createMap();
+      // test remove null key with map containing a single null key
+      map.put(null, getValues()[0]);
+      try {
+        map.remove(null);
+        assertTrue(useNullKey());
+      } catch (NullPointerException e) {
+        assertFalse(useNullKey());
+      }
+
+      map = createMap();
+      // test remove null key with map containing a single non-null key
+      map.put(getKeys()[0], getValues()[0]);
+      try {
+        map.remove(null);
+        assertTrue(useNullKey());
+      } catch (NullPointerException e) {
+        assertFalse(useNullKey());
+      } catch (JavaScriptException e) {
+        assertFalse(useNullKey());
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.remove(Object)'.
+   * 
+   * @see java.util.Map#remove(Object)
+   */
+  public void testRemove_throwsUnsupportedOperationException() {
+    Map<K, V> map = createMap();
+    if (!isRemoveSupported) {
+      try {
+        map.remove(getKeys()[0]);
+        fail("expected exception");
+      } catch (UnsupportedOperationException e) {
+        // expected outcome
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.util.Map.size()'.
+   * 
+   * @see java.util.Map#size()
+   */
+  public void testSize() {
+    Map<K, V> map = createMap();
+
+    // Test size behavior on put
+    map.put(getKeys()[0], getValues()[0]);
+    assertEquals(1, map.size());
+    map.put(getKeys()[1], getValues()[1]);
+    assertEquals(2, map.size());
+    map.put(getKeys()[2], getValues()[2]);
+    assertEquals(3, map.size());
+
+    // Test size behavior on remove
+    map.remove(getKeys()[0]);
+    assertEquals(2, map.size());
+    map.remove(getKeys()[1]);
+    assertEquals(1, map.size());
+    map.remove(getKeys()[2]);
+    assertEquals(0, map.size());
+
+    // Test size behavior on putAll
+    map.put(getKeys()[0], getValues()[0]);
+    map.put(getKeys()[1], getValues()[1]);
+    map.put(getKeys()[2], getValues()[2]);
+    assertEquals(3, map.size());
+
+    // Test size behavior on clear
+    map.clear();
+    _assertEmpty(map);
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.subMap(Object, Object)'.
+   * 
+   * @see java.util.SortedMap#subMap(Object, Object)
+   */
+  public void testSubMap() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+    // test with no entries
+    assertEquals(0, sortedMap.subMap(getKeys()[0], getKeys()[0]).size());
+
+    // test with a single entry map
+    sortedMap.put(getKeys()[0], getValues()[0]);
+    assertEquals(0, sortedMap.subMap(getKeys()[0], getKeys()[0]).size());
+    // bounded by a "wide" range
+    assertEquals(1, sortedMap.subMap(getLessThanMinimumKey(),
+        getGreaterThanMaximumKey()).size());
+
+    // test with two entry map
+    sortedMap.put(getKeys()[1], getValues()[1]);
+    assertEquals(1, sortedMap.subMap(getKeys()[0], getKeys()[1]).size());
+    assertEquals(getKeys()[0],
+        sortedMap.subMap(getKeys()[0], getKeys()[1]).keySet().toArray()[0]);
+    // bounded by a "wide" range
+    SortedMap<K, V> subMap = sortedMap.subMap(getLessThanMinimumKey(),
+        getGreaterThanMaximumKey());
+    assertEquals(2, subMap.size());
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.subMap(Object, Object)'.
+   * 
+   * @see java.util.SortedMap#subMap(Object, Object)
+   */
+  @SuppressWarnings("unchecked")
+  public void testSubMap_throwsClassCastException() {
+    SortedMap sortedMap = createSortedMap();
+    sortedMap.put(getKeys()[0], getValues()[0]);
+    try {
+      sortedMap.subMap(getConflictingKey(), getKeys()[0]);
+      assertTrue("CCE expected in hosted mode", GWT.isScript());
+    } catch (IllegalArgumentException e) {
+      // since we can't ensure CCEs in web mode, we may get IAE
+      assertTrue("IllegalArgumentException in hosted mode", GWT.isScript());
+    } catch (ClassCastException e) {
+      // expected outcome
+    }
+    try {
+      sortedMap.subMap(getKeys()[0], getConflictingKey());
+      assertTrue("CCE expected in hosted mode", GWT.isScript());
+    } catch (IllegalArgumentException e) {
+      // since we can't ensure CCEs in web mode, we may get IAE
+      assertTrue("IllegalArgumentException in hosted mode", GWT.isScript());
+    } catch (ClassCastException e) {
+      // expected outcome
+    }
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.subMap(Object, Object)'.
+   * 
+   * @see java.util.SortedMap#subMap(Object, Object)
+   */
+  public void testSubMap_throwsIllegalArgumentException() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+    try {
+      sortedMap.subMap(getGreaterThanMaximumKey(), getLessThanMinimumKey());
+      fail("expected exception");
+    } catch (IllegalArgumentException e) {
+      // from key is greater than the to key
+      // expected outcome
+    }
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.subMap(Object, Object)'.
+   * 
+   * @see java.util.SortedMap#subMap(Object, Object)
+   */
+  public void testSubMap_throwsNullPointerException() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+    try {
+      sortedMap.subMap(null, getLessThanMinimumKey());
+      assertTrue(useNullKey());
+    } catch (NullPointerException e) {
+      assertFalse(useNullKey());
+    } catch (JavaScriptException e) {
+      assertFalse(useNullKey());
+    }
+    try {
+      sortedMap.subMap(null, getGreaterThanMaximumKey());
+      assertTrue(useNullKey());
+    } catch (NullPointerException e) {
+      assertFalse(useNullKey());
+    } catch (JavaScriptException e) {
+      assertFalse(useNullKey());
+    }
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.tailMap(Object)'.
+   * 
+   * @see java.util.SortedMap#tailMap(Object)
+   */
+  public void testTailMap_entries0() {
+    // test with no entries
+    Map<K, V> tailMap = createSortedMap().tailMap(getKeys()[0]);
+    assertNotNull(tailMap);
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.tailMap(Object)'.
+   * 
+   * @see java.util.SortedMap#tailMap(Object)
+   */
+  public void testTailMap_entries0_size() {
+    // test with no entries
+    Map<K, V> tailMap = createSortedMap().tailMap(getKeys()[0]);
+    assertNotNull(tailMap);
+    assertEquals(0, tailMap.size());
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.tailMap(Object)'.
+   * 
+   * @see java.util.SortedMap#tailMap(Object)
+   */
+  public void testTailMap_entries1_size_keyValue() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+    // test with a single entry map
+    sortedMap.put(getKeys()[0], getValues()[0]);
+    Map<K, V> tailMap = sortedMap.tailMap(getKeys()[0]);
+    assertEquals(1, tailMap.size());
+    assertEquals(getKeys()[0], tailMap.keySet().toArray()[0]);
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.tailMap(Object)'.
+   * 
+   * @see java.util.SortedMap#tailMap(Object)
+   */
+  public void testTailMap_entries2_size_keyValue() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+    // test with two entry map
+    sortedMap.put(getKeys()[0], getValues()[0]);
+    Map<K, V> tailMap = sortedMap.tailMap(getKeys()[0]);
+    assertEquals(1, tailMap.size());
+    sortedMap.put(getKeys()[1], getValues()[1]);
+    tailMap = sortedMap.tailMap(getKeys()[1]);
+    assertEquals(1, tailMap.size());
+    tailMap = sortedMap.tailMap(getKeys()[0]);
+    assertEquals(2, tailMap.size());
+    assertEquals(getKeys()[0], tailMap.keySet().toArray()[0]);
+    assertEquals(getKeys()[1], tailMap.keySet().toArray()[1]);
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.tailMap(Object, Object)'.
+   * 
+   * @see java.util.SortedMap#tailMap(Object)
+   */
+  @SuppressWarnings("unchecked")
+  public void testTailMap_throwsClassCastException() {
+    SortedMap sortedMap = createSortedMap();
+    sortedMap.put(getKeys()[0], getValues()[0]);
+    if (isNaturalOrder()) {
+      // TODO Why does this succeed with natural ordering when subMap doesn't?
+      sortedMap.tailMap(getConflictingKey());
+    } else {
+      try {
+        sortedMap.tailMap(getConflictingKey());
+        assertTrue("CCE expected in hosted mode", GWT.isScript());
+      } catch (ClassCastException e) {
+        // expected outcome
+      }
+    }
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.tailMap(Object, Object)'.
+   * 
+   * @see java.util.SortedMap#tailMap(Object)
+   */
+  public void testTailMap_throwsIllegalArgumentException() {
+    // TODO I don't know of any case where this could happen.
+  }
+
+  /**
+   * Test method for 'java.util.SortedMap.tailMap(Object, Object)'.
+   * 
+   * @see java.util.SortedMap#tailMap(Object)
+   */
+  public void testTailMap_throwsNullPointerException() {
+    SortedMap<K, V> sortedMap = createSortedMap();
+    try {
+      sortedMap.tailMap(null);
+      assertTrue(useNullKey());
+    } catch (NullPointerException e) {
+      assertFalse(useNullKey());
+    }
+  }
+
+  /**
+   * Test method for 'java.lang.Object.toString()'.
+   */
+  public void testToString() {
+    Map<K, V> map = createMap();
+    map.put(getKeys()[0], getValues()[0]);
+    String entryString = makeEntryString(getKeys()[0], getValues()[0]);
+    assertEquals(entryString, map.toString());
+  }
+
+  /**
+   * Test method for 'java.util.Map.values()'.
+   * 
+   * @see java.util.Map#values()
+   */
+  public void testValues() {
+    Map<K, V> map = createMap();
+
+    map.put(getKeys()[0], getValues()[0]);
+
+    Collection<V> values = map.values();
+    assertNotNull(values);
+    assertEquals(1, values.size());
+
+    Iterator<V> valueIter = values.iterator();
+    V value = valueIter.next();
+    assertEquals(value, getValues()[0]);
+  }
+
+  /**
+   * Test method for 'java.util.Map.values()'.
+   * 
+   * @see java.util.Map#values()
+   */
+  public void testValues_nullKey() {
+    Map<K, V> map = createMap();
+
+    map.put(getKeys()[0], getValues()[0]);
+
+    Collection<V> values = map.values();
+    assertNotNull(values);
+    assertEquals(1, values.size());
+
+    Iterator<V> valueIter = values.iterator();
+    V value = valueIter.next();
+    assertEquals(value, getValues()[0]);
+  }
+
+  /**
+   * Test method for 'java.util.Map.values()'.
+   * 
+   * @see java.util.Map#values()
+   */
+  public void testValues_viewPut() {
+    Map<K, V> map = createMap();
+
+    map.put(getKeys()[0], getValues()[0]);
+
+    Collection<V> values = map.values();
+    assertNotNull(values);
+    assertEquals(1, values.size());
+
+    map.put(getKeys()[1], getValues()[1]);
+    assertEquals(2, values.size());
+  }
+
+  /**
+   * Test method for 'java.util.Map.values()'.
+   * 
+   * @see java.util.Map#values()
+   */
+  public void testValues_viewRemove() {
+    Map<K, V> map = createMap();
+
+    map.put(getKeys()[0], getValues()[0]);
+    map.put(getKeys()[1], getValues()[1]);
+
+    Collection<V> values = map.values();
+    assertNotNull(values);
+    assertEquals(2, values.size());
+
+    map.remove(getKeys()[1]);
+    assertEquals(1, values.size());
+  }
+
+  @Override
+  public boolean useNullKey() {
+    return false;
+  }
+
+  protected Comparator<K> getComparator() {
+    return comparator;
+  }
+
+  protected abstract Object getConflictingKey();
+
+  protected abstract Object getConflictingValue();
+
+  protected boolean isNaturalOrder() {
+    return comparator == null;
+  }
+
+  @SuppressWarnings("unchecked")
+  @Override
+  protected Map makeEmptyMap() {
+    return createTreeMap();
+  }
+
+  protected void setComparator(Comparator<K> comparator) {
+    this.comparator = comparator;
+  }
+
+  @Override
+  protected void setUp() throws Exception {
+    setComparator(null);
+    super.setUp();
+  }
+
+  Map<K, V> createMap() {
+    return createSortedMap();
+  }
+
+  SortedMap<K, V> createSortedMap() {
+    SortedMap<K, V> map = createTreeMap();
+    return map;
+  }
+
+  TreeMap<K, V> createTreeMap() {
+    if (isNaturalOrder()) {
+      return new TreeMap<K, V>();
+    } else {
+      return new TreeMap<K, V>(getComparator());
+    }
+  }
+
+  abstract K getGreaterThanMaximumKey();
+
+  abstract K[] getKeys();
+
+  abstract K[] getKeys2();
+
+  abstract K getLessThanMinimumKey();
+
+  abstract V[] getValues();
+
+  abstract V[] getValues2();
+}

diff --git a/user/test/org/apache/commons/collections/TestMap.java b/user/test/org/apache/commons/collections/TestMap.java
index 7c7f97e..b679a3d 100644
--- a/user/test/org/apache/commons/collections/TestMap.java
+++ b/user/test/org/apache/commons/collections/TestMap.java

@@ -15,6 +15,8 @@
  */
 package org.apache.commons.collections;
 
+import junit.framework.AssertionFailedError;
+
 import java.util.Collection;
 import java.util.HashMap;
 import java.util.Iterator;
@@ -262,15 +264,20 @@
                            "if either the key or value is null.", 
                            keys[i] == null || values[i] == null);
                 
-                assertTrue("NullPointerException on null key, but " +
-                           "useNullKey is not overridden to return false.", 
-                           keys[i] == null || !useNullKey());
-                
-                assertTrue("NullPointerException on null value, but " +
-                           "useNullValue is not overridden to return false.",
-                           values[i] == null || !useNullValue());
-                
-                assertTrue("Unknown reason for NullPointer.", false);
+                if (keys[i] == null) {
+                  if (useNullKey()) {
+                    throw new Error("NullPointerException on null key, but " +
+                        "useNullKey is not overridden to return false.", exception);
+                  }
+                } else if (values[i] == null) {
+                  if (useNullValue()) {
+                    throw new Error("NullPointerException on null value, but " +
+                        "useNullValue is not overridden to return false.", exception);
+                  }
+                } else {
+                  // Unknown reason for NullPointer.
+                  throw exception;
+                }
             }
         }
         assertEquals("size must reflect number of mappings added.",
@@ -520,35 +527,35 @@
      *  Tests Map.get(Object)
      **/
     public void testMapGet() {
-        resetEmpty();
+      resetEmpty();
 
-        Object[] keys = getSampleKeys();
-        Object[] values = getSampleValues();
+      Object[] keys = getSampleKeys();
+      Object[] values = getSampleValues();
 
-        for (int i = 0; i < keys.length; i++) {
-            assertTrue("Empty map.get() should return null.", 
-		       map.get(keys[i]) == null);
-        }
-        verify();
+      for (int i = 0; i < keys.length; i++) {
+        assertTrue("Empty map.get() should return null.", 
+            map.get(keys[i]) == null);
+      }
+      verify();
 
-        resetFull();
-        for (int i = 0; i < keys.length; i++) {
-	    assertEquals("Full map.get() should return value from mapping.", 
-			 values[i], map.get(keys[i]));
-        }
+      resetFull();
+      for (int i = 0; i < keys.length; i++) {
+        assertEquals("Full map.get() should return value from mapping.", 
+            values[i], map.get(keys[i]));
+      }
     }
 
     /**
      *  Tests Map.hashCode()
      **/
     public void testMapHashCode() {
-        resetEmpty();
-        assertTrue("Empty maps have different hashCodes.", 
-		   map.hashCode() == confirmed.hashCode());
+      resetEmpty();
+      assertTrue("Empty maps have different hashCodes.", 
+          map.hashCode() == confirmed.hashCode());
 
-        resetFull();
-        assertTrue("Equal maps have different hashCodes.", 
-		   map.hashCode() == confirmed.hashCode());
+      resetFull();
+      assertTrue("Equal maps have different hashCodes.", 
+          map.hashCode() == confirmed.hashCode());
     }
 
     /**
@@ -561,131 +568,131 @@
      *  not return null.
      **/
     public void testMapToString() {
-        resetEmpty();
-        assertTrue("Empty map toString() should not return null", 
-                   map.toString() != null);
-        verify();
+      resetEmpty();
+      assertTrue("Empty map toString() should not return null", 
+          map.toString() != null);
+      verify();
 
-        resetFull();
-        assertTrue("Empty map toString() should not return null", 
-                   map.toString() != null);
-        verify();
+      resetFull();
+      assertTrue("Empty map toString() should not return null", 
+          map.toString() != null);
+      verify();
     }
 
 
-     
-    
+
+
 
     /**
      *  Tests Map.put(Object, Object)
      **/
     public void testMapPut() {
-        if (!isAddRemoveModifiable()) return;
+      if (!isAddRemoveModifiable()) return;
 
-        resetEmpty();
+      resetEmpty();
 
-	Object[] keys = getSampleKeys();
-	Object[] values = getSampleValues();
-	Object[] newValues = getNewSampleValues();
+      Object[] keys = getSampleKeys();
+      Object[] values = getSampleValues();
+      Object[] newValues = getNewSampleValues();
 
-        for(int i = 0; i < keys.length; i++) {
-            Object o = map.put(keys[i], values[i]);
-            confirmed.put(keys[i], values[i]);
-            verify();
-	    assertTrue("First map.put should return null", o == null);
-	    assertTrue("Map should contain key after put", 
-		       map.containsKey(keys[i]));
-	    assertTrue("Map should contain value after put", 
-		       map.containsValue(values[i]));
-	}
-	
-	for(int i = 0; i < keys.length; i++) {
-	    Object o = map.put(keys[i], newValues[i]);
-            confirmed.put(keys[i], newValues[i]);
-            verify();
-	    assertEquals("Second map.put should return previous value",
-			 values[i], o);
-	    assertTrue("Map should still contain key after put",
-		       map.containsKey(keys[i]));
-	    assertTrue("Map should contain new value after put",
-		       map.containsValue(newValues[i]));
+      for(int i = 0; i < keys.length; i++) {
+        Object o = map.put(keys[i], values[i]);
+        confirmed.put(keys[i], values[i]);
+        verify();
+        assertTrue("First map.put should return null", o == null);
+        assertTrue("Map should contain key after put", 
+            map.containsKey(keys[i]));
+        assertTrue("Map should contain value after put", 
+            map.containsValue(values[i]));
+      }
 
-	    // if duplicates are allowed, we're not guarunteed that the value
-	    // no longer exists, so don't try checking that.
-	    if(!useDuplicateValues()) {
-		assertTrue("Map should not contain old value after second put",
-			   !map.containsValue(values[i]));
-	    }
-	}
+      for(int i = 0; i < keys.length; i++) {
+        Object o = map.put(keys[i], newValues[i]);
+        confirmed.put(keys[i], newValues[i]);
+        verify();
+        assertEquals("Second map.put should return previous value",
+            values[i], o);
+        assertTrue("Map should still contain key after put",
+            map.containsKey(keys[i]));
+        assertTrue("Map should contain new value after put",
+            map.containsValue(newValues[i]));
+
+        // if duplicates are allowed, we're not guarunteed that the value
+        // no longer exists, so don't try checking that.
+        if(!useDuplicateValues()) {
+          assertTrue("Map should not contain old value after second put",
+              !map.containsValue(values[i]));
+        }
+      }
     }
 
     /**
      *  Tests Map.putAll(Collection)
      **/
     public void testMapPutAll() {
-        if (!isAddRemoveModifiable()) return;
+      if (!isAddRemoveModifiable()) return;
 
-        resetEmpty();
+      resetEmpty();
 
-        Map m2 = makeFullMap();
+      Map m2 = makeFullMap();
 
-        map.putAll(m2);
-        confirmed.putAll(m2);
-        verify();
+      map.putAll(m2);
+      confirmed.putAll(m2);
+      verify();
 
-        resetEmpty();
+      resetEmpty();
 
-	m2 = new HashMap();
-	Object[] keys = getSampleKeys();
-	Object[] values = getSampleValues();
-	for(int i = 0; i < keys.length; i++) {
-	    m2.put(keys[i], values[i]);
-	}
+      m2 = new HashMap();
+      Object[] keys = getSampleKeys();
+      Object[] values = getSampleValues();
+      for(int i = 0; i < keys.length; i++) {
+        m2.put(keys[i], values[i]);
+      }
 
-	map.putAll(m2);
-        confirmed.putAll(m2);
-        verify();
+      map.putAll(m2);
+      confirmed.putAll(m2);
+      verify();
     }
 
     /**
      *  Tests Map.remove(Object)
      **/
     public void testMapRemove() {
-        if (!isAddRemoveModifiable()) return;
+      if (!isAddRemoveModifiable()) return;
 
-        resetEmpty();
+      resetEmpty();
 
-	Object[] keys = getSampleKeys();
-	Object[] values = getSampleValues();
-	for(int i = 0; i < keys.length; i++) {
-	    Object o = map.remove(keys[i]);
-	    assertTrue("First map.remove should return null", o == null);
-	}
+      Object[] keys = getSampleKeys();
+      Object[] values = getSampleValues();
+      for(int i = 0; i < keys.length; i++) {
+        Object o = map.remove(keys[i]);
+        assertTrue("First map.remove should return null", o == null);
+      }
+      verify();
+
+      resetFull();
+
+      for(int i = 0; i < keys.length; i++) {
+        Object o = map.remove(keys[i]);
+        confirmed.remove(keys[i]);
         verify();
 
-        resetFull();
+        assertEquals("map.remove with valid key should return value",
+            values[i], o);
+      }
 
-	for(int i = 0; i < keys.length; i++) {
-	    Object o = map.remove(keys[i]);
-            confirmed.remove(keys[i]);
-            verify();
+      Object[] other = getOtherKeys();
 
-	    assertEquals("map.remove with valid key should return value",
-			 values[i], o);
-	}
-
-        Object[] other = getOtherKeys();
-
-        resetFull();
-        int size = map.size();
-        for (int i = 0; i < other.length; i++) {
-            Object o = map.remove(other[i]);
-            assertEquals("map.remove for nonexistent key should return null",
-                         o, null);
-            assertEquals("map.remove for nonexistent key should not " +
-                         "shrink map", size, map.size());
-        }
-        verify();
+      resetFull();
+      int size = map.size();
+      for (int i = 0; i < other.length; i++) {
+        Object o = map.remove(other[i]);
+        assertEquals("map.remove for nonexistent key should return null",
+            o, null);
+        assertEquals("map.remove for nonexistent key should not " +
+            "shrink map", size, map.size());
+      }
+      verify();
     }
 
 

diff --git a/user/test/org/apache/commons/collections/TestTreeMap.java b/user/test/org/apache/commons/collections/TestTreeMap.java
new file mode 100644
index 0000000..68ff535
--- /dev/null
+++ b/user/test/org/apache/commons/collections/TestTreeMap.java

@@ -0,0 +1,52 @@
+/*
+ * Copyright 1999-2004 The Apache Software Foundation
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ * 
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package org.apache.commons.collections;
+
+import java.util.TreeMap;
+
+/**
+ * @author <a href="mailto:jvanzyl@apache.org">Jason van Zyl</a>
+ * @version $Id: TestTreeMap.java,v 1.6.2.1 2004/05/22 12:14:05 scolebourne Exp $
+ */
+public abstract class TestTreeMap extends TestMap {
+  // public static void main(String args[])
+  // {
+  // String[] testCaseName = { TestTreeMap.class.getName() };
+  // junit.textui.TestRunner.main(testCaseName);
+  // }
+
+  protected TreeMap map = null;
+
+  public void setUp() {
+    map = (TreeMap) makeEmptyMap();
+  }
+
+  public void testNewMap() {
+    assertTrue("New map is empty", map.isEmpty());
+    assertEquals("New map has size zero", map.size(), 0);
+  }
+
+  public void testSearch() {
+    map.put("first", "First Item");
+    map.put("second", "Second Item");
+    assertEquals("Top item is 'Second Item'", map.get("first"), "First Item");
+    assertEquals("Next Item is 'First Item'", map.get("second"), "Second Item");
+  }
+
+  public boolean useNullKey() {
+    return false;
+  }
+}