Add tests for TreeMap and TreeSet, change TreeSet.add implementation to be
more efficient, fix integer overflow in AbstractSet.hashCode.
Patch by: jat
Review by: scottb (desk review)
git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@2938 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/user/super/com/google/gwt/emul/java/util/AbstractSet.java b/user/super/com/google/gwt/emul/java/util/AbstractSet.java
index fde5328..dc30516 100644
--- a/user/super/com/google/gwt/emul/java/util/AbstractSet.java
+++ b/user/super/com/google/gwt/emul/java/util/AbstractSet.java
@@ -58,6 +58,8 @@
E next = iter.next();
if (next != null) {
hashCode += next.hashCode();
+ // handle int overflow by coercing to int
+ hashCode = ~~hashCode;
}
}
return hashCode;
diff --git a/user/super/com/google/gwt/emul/java/util/TreeSet.java b/user/super/com/google/gwt/emul/java/util/TreeSet.java
index afeaa98..b4bce7f 100644
--- a/user/super/com/google/gwt/emul/java/util/TreeSet.java
+++ b/user/super/com/google/gwt/emul/java/util/TreeSet.java
@@ -63,13 +63,8 @@
@Override
public boolean add(E o) {
- if (map.containsKey(o)) {
- // must not change map for equal keys
- return false;
- }
// Use "this" as a convenient non-null value to store in the map
- map.put(o, o);
- return true;
+ return map.put(o, this) == null;
}
@Override
diff --git a/user/test/com/google/gwt/emultest/java/util/TreeMapTest.java b/user/test/com/google/gwt/emultest/java/util/TreeMapTest.java
index 50ba8b5..9e3e0f0 100644
--- a/user/test/com/google/gwt/emultest/java/util/TreeMapTest.java
+++ b/user/test/com/google/gwt/emultest/java/util/TreeMapTest.java
@@ -20,7 +20,9 @@
import org.apache.commons.collections.TestMap;
+import java.util.ArrayList;
import java.util.Collection;
+import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
@@ -132,6 +134,12 @@
assertEquals(expected.values().toArray(), actual.values().toArray());
}
+ // Use JSNI to call a special method on our implementation of TreeMap.
+ @SuppressWarnings("unchecked") // raw Map
+ private static native void callAssertCorrectness(Map map) /*-{
+ map.@java.util.TreeMap::assertCorrectness()();
+ }-*/;
+
/**
* Create the expected return of toString for a Map containing only the passed
* key and value.
@@ -155,6 +163,7 @@
private boolean isPutSupported = true;
private boolean isRemoveSupported = true;
+ @Override
public String getModuleName() {
return "com.google.gwt.emultest.EmulSuite";
}
@@ -893,6 +902,29 @@
assertEquals(1, keySet.size());
}
+ public void testKeySetIteratorRemove() {
+ Map<K, V> map = makeFullMap();
+ resetFull();
+ ArrayList<K> keys = new ArrayList<K>();
+ for (Object key : getSampleKeys()) {
+ keys.add((K) key);
+ }
+ Comparator<? super K> cmp = ((TreeMap<K, V>) map).comparator();
+ if (cmp != null) {
+ Collections.sort(keys, cmp);
+ } else {
+ Collections.sort(keys);
+ }
+ Iterator<K> it = map.keySet().iterator();
+ for (K key : keys) {
+ assertTrue(it.hasNext());
+ K rem = it.next();
+ it.remove();
+ assertEquals(key, rem);
+ }
+ assertEquals(0, map.size());
+ }
+
/**
* Test method for 'java.util.SortedMap.lastKey()'.
*
@@ -1810,6 +1842,11 @@
protected abstract Object getConflictingValue();
+ @Override
+ protected void gwtSetUp() throws Exception {
+ setComparator(null);
+ }
+
protected boolean isNaturalOrder() {
return comparator == null;
}
@@ -1825,8 +1862,12 @@
}
@Override
- protected void gwtSetUp() throws Exception {
- setComparator(null);
+ protected void verifyMap() {
+ if (GWT.isScript()) {
+ // Verify red-black correctness in our implementation
+ callAssertCorrectness(map);
+ }
+ super.verifyMap();
}
Map<K, V> createMap() {
diff --git a/user/test/com/google/gwt/emultest/java/util/TreeSetIntegerTest.java b/user/test/com/google/gwt/emultest/java/util/TreeSetIntegerTest.java
index 96e04a1..e74c783 100644
--- a/user/test/com/google/gwt/emultest/java/util/TreeSetIntegerTest.java
+++ b/user/test/com/google/gwt/emultest/java/util/TreeSetIntegerTest.java
@@ -15,11 +15,75 @@
*/
package com.google.gwt.emultest.java.util;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.TreeSet;
+
/**
- * Tests <code>TreeMap</code> with a <code>Comparator</code>.
+ * Tests <code>TreeSet</code> with a <code>Comparator</code>.
*/
public class TreeSetIntegerTest extends TreeSetTest<Integer> {
+ /**
+ * Used to test updating a set to make sure it doesn't replace
+ * an equal value.
+ */
+ private static class Record {
+ public int key;
+ public int extra;
+
+ public Record(int key, int extra) {
+ this.key = key;
+ this.extra = extra;
+ }
+ }
+
+ private static class RecordCompare implements Comparator<Record> {
+ // Handle nulls as less than any other key
+ public int compare(Record r1, Record r2) {
+ if (r1 == null) {
+ return r2 == null ? 0 : -1;
+ }
+ if (r2 == null) {
+ return 1;
+ }
+ return r1.key - r2.key;
+ }
+ }
+
+ /**
+ * Verify nulls are handled properly.
+ */
+ public void testAdd_null() {
+ TreeSet<Record> set = new TreeSet<Record>(new RecordCompare());
+ set.add(new Record(10, 1));
+ set.add(new Record(2, 2));
+ set.add(null);
+ set.add(new Record(7, 7));
+ Iterator<Record> it = set.iterator();
+ assertTrue(it.hasNext());
+ assertNull(it.next());
+ assertTrue(it.hasNext());
+ assertEquals(2, it.next().key);
+ assertTrue(it.hasNext());
+ assertEquals(7, it.next().key);
+ assertTrue(it.hasNext());
+ assertEquals(10, it.next().key);
+ assertFalse(it.hasNext());
+ }
+
+ /**
+ * Verify that Set.add doesn't replace an existing entry that compares equal.
+ */
+ public void testAdd_overwrite() {
+ TreeSet<Record> set = new TreeSet<Record>(new RecordCompare());
+ assertTrue(set.add(new Record(1, 1)));
+ assertTrue(set.add(new Record(2, 2)));
+ assertFalse(set.add(new Record(1, -1)));
+ Record first = set.first();
+ assertEquals(1, first.extra);
+ }
+
@Override
Integer getGreaterThanMaximumKey() {
return Integer.MAX_VALUE;
