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;
+ }
+}
