Implementes TreeSet; for real dawg.
Patch by: jat
Review by: scottb
git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@2929 8db76d5a-ed1c-0410-87a9-c151d255dfc7
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 8ad65c5..afeaa98 100644
--- a/user/super/com/google/gwt/emul/java/util/TreeSet.java
+++ b/user/super/com/google/gwt/emul/java/util/TreeSet.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
@@ -24,66 +24,100 @@
*/
public class TreeSet<E> extends AbstractSet<E> implements SortedSet<E> {
+ /**
+ * TreeSet is stored as a TreeMap of the requested type to null Objects.
+ */
+ private SortedMap<E, Object> map;
+
public TreeSet() {
- // TODO(jat): implement
- throw new UnsupportedOperationException("TreeSet not implemented");
+ map = new TreeMap<E, Object>();
}
public TreeSet(Collection<? extends E> c) {
- // TODO(jat): implement
- throw new UnsupportedOperationException("TreeSet not implemented");
+ this();
+ addAll(c);
}
public TreeSet(Comparator<? super E> c) {
- // TODO(jat): implement
- throw new UnsupportedOperationException("TreeSet not implemented");
+ if (c == null) {
+ map = new TreeMap<E, Object>();
+ } else {
+ map = new TreeMap<E, Object>(c);
+ }
}
public TreeSet(SortedSet<E> s) {
- // TODO(jat): implement
- throw new UnsupportedOperationException("TreeSet not implemented");
+ this(s.comparator());
+ // TODO(jat): more efficient implementation
+ addAll(s);
+ }
+
+ /**
+ * Used to wrap subset maps in a new TreeSet.
+ *
+ * @param map map to use for backing store
+ */
+ private TreeSet(SortedMap<E, Object> map) {
+ this.map = map;
+ }
+
+ @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;
+ }
+
+ @Override
+ public void clear() {
+ map.clear();
}
public Comparator<? super E> comparator() {
- // TODO(jat): implement
- return null;
+ return map.comparator();
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ return map.containsKey(o);
}
public E first() {
- // TODO(jat): implement
- return null;
+ return map.firstKey();
}
public SortedSet<E> headSet(E toElement) {
- // TODO(jat): implement
- return null;
+ return new TreeSet<E>(map.headMap(toElement));
}
@Override
public Iterator<E> iterator() {
- // TODO(jat): implement
- return null;
+ return map.keySet().iterator();
}
public E last() {
- // TODO(jat): implement
- return null;
+ return map.lastKey();
+ }
+
+ @Override
+ public boolean remove(Object o) {
+ return map.remove(o) != null;
}
@Override
public int size() {
- // TODO(jat): implement
- return 0;
+ return map.size();
}
public SortedSet<E> subSet(E fromElement, E toElement) {
- // TODO(jat): implement
- return null;
+ return new TreeSet<E>(map.subMap(fromElement, toElement));
}
public SortedSet<E> tailSet(E fromElement) {
- // TODO(jat): implement
- return null;
+ return new TreeSet<E>(map.tailMap(fromElement));
}
-
}
diff --git a/user/test/com/google/gwt/emultest/EmulSuite.java b/user/test/com/google/gwt/emultest/EmulSuite.java
index 612e8f8..6e412d3 100644
--- a/user/test/com/google/gwt/emultest/EmulSuite.java
+++ b/user/test/com/google/gwt/emultest/EmulSuite.java
@@ -91,6 +91,7 @@
suite.addTestSuite(SqlTimeTest.class);
suite.addTestSuite(SqlTimestampTest.class);
suite.addTest(TreeMapSuiteSub.suite());
+ suite.addTest(TreeSetSuiteSub.suite());
// $JUnit-END$
return suite;
diff --git a/user/test/com/google/gwt/emultest/TreeSetSuiteSub.java b/user/test/com/google/gwt/emultest/TreeSetSuiteSub.java
new file mode 100644
index 0000000..a7cf7d1
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/TreeSetSuiteSub.java
@@ -0,0 +1,34 @@
+/*
+ * 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.TreeSetIntegerTest;
+import com.google.gwt.emultest.java.util.TreeSetIntegerWithComparatorTest;
+import com.google.gwt.junit.tools.GWTTestSuite;
+
+import junit.framework.Test;
+
+/**
+ * Tests <code>TreeSet</code>.
+ */
+public class TreeSetSuiteSub {
+ public static Test suite() {
+ GWTTestSuite suite = new GWTTestSuite("Tests for com.google.gwt.emul.java.util.TreeSet");
+ suite.addTestSuite(TreeSetIntegerTest.class);
+ suite.addTestSuite(TreeSetIntegerWithComparatorTest.class);
+ return suite;
+ }
+}
diff --git a/user/test/com/google/gwt/emultest/java/util/TreeSetIntegerTest.java b/user/test/com/google/gwt/emultest/java/util/TreeSetIntegerTest.java
new file mode 100644
index 0000000..96e04a1
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/java/util/TreeSetIntegerTest.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;
+
+/**
+ * Tests <code>TreeMap</code> with a <code>Comparator</code>.
+ */
+public class TreeSetIntegerTest extends TreeSetTest<Integer> {
+
+ @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
+ protected Object getConflictingKey() {
+ return "key";
+ }
+
+ @Override
+ protected Object getConflictingValue() {
+ return "value";
+ }
+}
diff --git a/user/test/com/google/gwt/emultest/java/util/TreeSetIntegerWithComparatorTest.java b/user/test/com/google/gwt/emultest/java/util/TreeSetIntegerWithComparatorTest.java
new file mode 100644
index 0000000..142c023
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/java/util/TreeSetIntegerWithComparatorTest.java
@@ -0,0 +1,46 @@
+/*
+ * 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.Set;
+import java.util.SortedSet;
+
+/**
+ * Tests <code>TreeMap</code> with a <code>Comparator</code>.
+ */
+public class TreeSetIntegerWithComparatorTest extends TreeSetIntegerTest {
+ @Override
+ protected SortedSet<Integer> createSortedSet() {
+ 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.createSortedSet();
+ }
+
+ @Override
+ protected Set<Integer> makeEmptySet() {
+ return createSortedSet();
+ }
+}
diff --git a/user/test/com/google/gwt/emultest/java/util/TreeSetTest.java b/user/test/com/google/gwt/emultest/java/util/TreeSetTest.java
new file mode 100644
index 0000000..7d64188
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/java/util/TreeSetTest.java
@@ -0,0 +1,1137 @@
+/*
+ * 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.TestSet;
+
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.SortedSet;
+import java.util.TreeSet;
+
+/**
+ * Tests <code>TreeSet</code>.
+ *
+ * @param <E> The key type for the underlying TreeSet
+ *
+ * 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 TreeSetTest<E extends Comparable<E>> extends TestSet {
+
+ /**
+ * Verify a Set is explicitly and implicitly empty.
+ *
+ * @param set
+ */
+ private static <E> void _assertEmpty(Set<E> set) {
+ assertNotNull(set);
+ assertTrue(set.isEmpty());
+ assertEquals(0, set.size());
+ }
+
+ /**
+ * Verify that two Collections are deeply equivalent. Some of the Sets that
+ * need to be verified do not implement a sensible equals method
+ * (TreeSet.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 SortedMaps are deeply equivalent.
+ *
+ * @param expected
+ * @param actual
+ */
+ private static <E> void _assertEquals(SortedSet<E> expected,
+ SortedSet<E> actual) {
+ _assertEquals((Set<E>) expected, (Set<E>) actual);
+
+ // verify the order of the associated collections
+ assertEquals(expected.toArray(), actual.toArray());
+ }
+
+ /**
+ * comparator used when creating the SortedSet.
+ */
+ private Comparator<E> comparator = null;
+
+ private boolean isAddSupported = true;
+ private boolean isClearSupported = true;
+ private boolean isNullKeySupported = true;
+ private boolean isPutAllSupported = true;
+ private boolean isRemoveSupported = true;
+
+ public TreeSetTest() {
+ super("TreeSetTest");
+ }
+
+ @Override
+ public String getModuleName() {
+ return "com.google.gwt.emultest.EmulSuite";
+ }
+
+ /**
+ * Test method for 'java.util.Set.add(Object)'.
+ *
+ * @see java.util.Set#put(Object)
+ */
+ public void testAdd() {
+ // The _throwsUnsupportedOperationException version of this test will
+ // verify that the method is not supported.
+ if (isAddSupported) {
+ Set<E> set = createSet();
+ assertTrue(set.add(getKeys()[0]));
+ assertFalse(set.isEmpty());
+ assertEquals(1, set.size());
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.add(Object)'.
+ *
+ * @see java.util.Set#add(Object)
+ */
+ public void testAdd_entries3() {
+ // The _throwsUnsupportedOperationException version of this test will
+ // verify that the method is not supported.
+ if (isAddSupported) {
+ // populate the set
+ Set<E> set = createSet();
+ set.add(getKeys()[0]);
+ set.add(getKeys()[1]);
+ set.add(getKeys()[2]);
+
+ // test contents
+ assertFalse(set.isEmpty());
+ assertEquals(3, set.size());
+ Collection<E> keys = set;
+ // test contains all keys
+ assertTrue(keys.contains(getKeys()[0]));
+ assertTrue(keys.contains(getKeys()[1]));
+ assertTrue(keys.contains(getKeys()[2]));
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.add(Object)'.
+ *
+ * @see java.util.Set#add(Object)
+ */
+ public void testAdd_replace() {
+ // The _throwsUnsupportedOperationException version of this test will
+ // verify that the method is not supported.
+ if (isAddSupported) {
+ Set<E> set = createSet();
+ assertTrue(set.add(getKeys()[0]));
+ assertFalse(set.isEmpty());
+ assertEquals(1, set.size());
+
+ assertFalse(set.add(getKeys()[0]));
+ assertEquals(1, set.size());
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.add(Object)'.
+ *
+ * @see java.util.Set#add(Object)
+ */
+ @SuppressWarnings("unchecked")
+ public void testAdd_throwsClassCastException_key() {
+ // The _throwsUnsupportedOperationException version of this test will
+ // verify that the method is not supported.
+ if (isAddSupported) {
+ Set<E> set = createSet();
+ set.add(getKeys()[0]);
+ try {
+ Set untypedSet = set;
+ untypedSet.add(getConflictingKey());
+ assertTrue("CCE expected in hosted mode", GWT.isScript());
+ } catch (ClassCastException e) {
+ // expected outcome
+ }
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.add(Object)'.
+ *
+ * @see java.util.Set#add(Object)
+ */
+ @SuppressWarnings("unchecked")
+ public void testAdd_throwsClassCastException_value() {
+ // The _throwsUnsupportedOperationException version of this test will
+ // verify that the method is not supported.
+ if (isAddSupported) {
+ Set<E> set = createSet();
+ set.add(getKeys()[0]);
+
+ Set untypedSet = set;
+ untypedSet.add(getKeys()[1]);
+ // 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.Set.add(Object)'.
+ *
+ * @see java.util.Set#add(Object)
+ */
+ public void testAdd_throwsUnsupportedOperationException() {
+ if (!isAddSupported) {
+ Set<E> set = createSet();
+ try {
+ set.add(getKeys()[0]);
+ fail("expected exception");
+ } catch (UnsupportedOperationException e) {
+ // expected outcome
+ }
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.addAll(Map)'.
+ *
+ * @see java.util.Set#addAll(Map)
+ */
+ public void testAddAll() {
+ // The _throwsUnsupportedOperationException version of this test will
+ // verify that the method is not supported.
+ if (isPutAllSupported) {
+ Set<E> sourceSet = createSet();
+ sourceSet.add(getKeys()[0]);
+ sourceSet.add(getKeys()[1]);
+ sourceSet.add(getKeys()[2]);
+
+ Set<E> destSet = createSet();
+ destSet.addAll(sourceSet);
+ // Make sure that the data is copied correctly
+ _assertEquals(sourceSet, destSet);
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.addAll(Map)'.
+ *
+ * @see java.util.Set#addAll(Map)
+ */
+ public void testAddAll_addEntries() {
+ // The _throwsUnsupportedOperationException version of this test will
+ // verify that the method is not supported.
+ if (isPutAllSupported) {
+ Set<E> sourceMap = createSet();
+ sourceMap.add(getKeys()[0]);
+
+ Set<E> destSet = createSet();
+ destSet.addAll(sourceMap);
+ // Verify that entries get added.
+ sourceMap.add(getKeys()[1]);
+ destSet.addAll(sourceMap);
+ _assertEquals(sourceMap, destSet);
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.addAll(Map)'.
+ *
+ * @see java.util.Set#addAll(Map)
+ */
+ public void testAddAll_emptyMap() {
+ // The _throwsUnsupportedOperationException version of this test will
+ // verify that the method is not supported.
+ if (isPutAllSupported) {
+ Set<E> sourceSet = createSet();
+ sourceSet.add(getKeys()[0]);
+
+ Set<E> destSet = createSet();
+ destSet.addAll(sourceSet);
+ // Verify that putting an empty set does not clear.
+ destSet.addAll(createSet());
+ _assertEquals(sourceSet, destSet);
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.addAll(Map)'.
+ *
+ * @see java.util.Set#addAll(Map)
+ */
+ public void testAddAll_overwrite() {
+ // The _throwsUnsupportedOperationException version of this test will
+ // verify that the method is not supported.
+ if (isPutAllSupported) {
+ Set<E> sourceSet = createSet();
+ sourceSet.add(getKeys()[0]);
+
+ Set<E> destSet = createSet();
+ destSet.addAll(sourceSet);
+ // Verify that entries get replaced.
+ sourceSet.add(getKeys()[0]);
+ destSet.addAll(sourceSet);
+ _assertEquals(sourceSet, destSet);
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.addAll(Map)'.
+ *
+ * @see java.util.Set#addAll(Map)
+ */
+ public void testAddAll_self() {
+ // The _throwsUnsupportedOperationException version of this test will
+ // verify that the method is not supported.
+ if (isPutAllSupported) {
+ Set<E> sourceSet = createSet();
+ sourceSet.add(getKeys()[0]);
+ sourceSet.addAll(sourceSet);
+ // verify putAll with self succeeds and has no effect.
+ assertEquals(1, sourceSet.size());
+ assertEquals(getKeys()[0], sourceSet.iterator().next());
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.addAll(Map)'.
+ *
+ * @see java.util.Set#addAll(Map)
+ */
+ @SuppressWarnings("unchecked")
+ public void testAddAll_throwsClassCastException() {
+ // The _throwsUnsupportedOperationException version of this test will
+ // verify that the method is not supported.
+ if (isPutAllSupported) {
+ Set sourceSet = createSet();
+ sourceSet.add(getConflictingKey());
+
+ Set<E> destSet = createSet();
+ destSet.add(getKeys()[0]);
+ try {
+ destSet.addAll(sourceSet);
+ assertTrue("CCE expected in hosted mode", GWT.isScript());
+ } catch (ClassCastException e) {
+ // expected outcome
+ }
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.addAll(Map)'.
+ *
+ * @see java.util.Set#addAll(Map)
+ */
+ public void testAddAll_throwsNullPointerException() {
+ // The _throwsUnsupportedOperationException version of this test will
+ // verify that the method is not supported.
+ if (isPutAllSupported) {
+ Set<E> set = createSet();
+ try {
+ set.addAll((Set<E>) 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.Set.addAll(Map)'.
+ *
+ * @see java.util.Set#addAll(Map)
+ */
+ public void testAddAll_throwsUnsupportedOperationException() {
+ Set<E> set = createSet();
+ if (!isPutAllSupported) {
+ try {
+ set.addAll(createSet());
+ fail("expected exception");
+ } catch (UnsupportedOperationException e) {
+ // expected outcome
+ }
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.clear()'.
+ *
+ * @see java.util.Set#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.
+ Set<E> set = createSet();
+ set.add(getKeys()[0]);
+ assertFalse(set.isEmpty());
+ set.clear();
+ _assertEmpty(set);
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.clear()'.
+ *
+ * @see java.util.Set#clear()
+ */
+ public void testClear_throwsUnsupportedOperationException() {
+ Set<E> set = createSet();
+ if (!isClearSupported) {
+ try {
+ set.clear();
+ fail("expected exception");
+ } catch (UnsupportedOperationException e) {
+ // expected outcome
+ }
+ }
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.comparator()'.
+ *
+ * @see java.util.SortedSet#comparator()
+ */
+ public void testComparator() {
+ SortedSet<E> sortedSet = createSortedSet();
+ if (isNaturalOrder()) {
+ assertEquals(null, sortedSet.comparator());
+ } else {
+ assertEquals(getComparator(), sortedSet.comparator());
+ }
+ }
+
+ /**
+ * Test method for default constructor.
+ *
+ * @see java.util.TreeSet#TreeSet()
+ */
+ public void testConstructor() {
+ TreeSet<E> treeSet = new TreeSet<E>();
+ _assertEmpty(treeSet);
+ }
+
+ /**
+ * Test method for 'java.util.TreeSet.TreeSet(Comparator)'.
+ *
+ * @see java.util.TreeSet#TreeSet(Comparator)
+ */
+ public void testConstructor_comparator() {
+ TreeSet<E> TreeSet = new TreeSet<E>(getComparator());
+ _assertEmpty(TreeSet);
+ if (isNaturalOrder()) {
+ assertNull(TreeSet.comparator());
+ } else {
+ assertSame(getComparator(), TreeSet.comparator());
+ }
+ }
+
+ /**
+ * Test method for 'java.util.TreeSet.TreeSet(Set)'.
+ *
+ * @see java.util.TreeSet#TreeSet(Set)
+ */
+ public void testConstructor_Set() {
+ // The source set should be just a Map. Not a sorted set.
+ Set<E> sourceMap = new HashSet<E>();
+
+ // populate the source set
+ sourceMap.add(getKeys()[0]);
+ sourceMap.add(getKeys()[1]);
+ sourceMap.add(getKeys()[2]);
+
+ TreeSet<E> copyConstructed = new TreeSet<E>(sourceMap);
+ _assertEquals(sourceMap, copyConstructed);
+ }
+
+ /**
+ * Test method for 'java.util.TreeSet.TreeSet(Set)'.
+ *
+ * @see java.util.TreeSet#TreeSet(Set)
+ */
+ @SuppressWarnings("unchecked")
+ public void testConstructor_Set_throwsClassCastException() {
+ Set sourceSet = createSet();
+ sourceSet.add(getConflictingKey());
+ new TreeSet<E>(sourceSet);
+
+ // This does not fail as might be expected.
+ // TODO I don't know of any case where this could happen.
+ // try {
+ // new TreeSet<E, V>(sourceMap);
+ // fail("expected exception");
+ // } catch (ClassCastException e) {
+ // // expected outcome
+ // }
+ }
+
+ /**
+ * Test method for 'java.util.TreeSet.TreeSet(Set)'.
+ *
+ * @see java.util.TreeSet#TreeSet(Set)
+ */
+ public void testConstructor_Set_throwsNullPointerException() {
+ try {
+ new TreeSet<E>((Set<E>) 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.TreeSet.TreeSet(SortedSet).
+ *
+ * @see java.util.TreeSet#TreeSet(SortedSet)
+ */
+ public void testConstructor_SortedMap_throwsNullPointerException() {
+ try {
+ new TreeSet<E>((SortedSet<E>) 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.TreeSet.TreeSet(SortedSet)'.
+ *
+ * @see java.util.TreeSet#TreeSet(SortedSet)
+ */
+ public void testConstructor_SortedSet() {
+ SortedSet<E> sourceMap = new TreeSet<E>();
+ _assertEmpty(sourceMap);
+
+ // populate the source set
+ sourceMap.add(getKeys()[0]);
+ sourceMap.add(getKeys()[1]);
+ sourceMap.add(getKeys()[2]);
+
+ TreeSet<E> copyConstructed = new TreeSet<E>(sourceMap);
+ _assertEquals(sourceMap, copyConstructed);
+ }
+
+ /**
+ * Test method for 'java.util.Set.contains(Object)'. *
+ *
+ * @see java.util.Set#contains(Object)
+ */
+ public void testContains() {
+ Set<E> set = createSet();
+ assertFalse(set.contains(getKeys()[0]));
+ assertTrue(set.add(getKeys()[0]));
+ assertEquals(1, set.size());
+ assertTrue(set.contains(getKeys()[0]));
+ assertFalse(set.contains(getKeys()[1]));
+ }
+
+ /**
+ * Test method for 'java.util.Set.contains(Object)'.
+ *
+ * @see java.util.Set#contains(Object)
+ */
+ public void testContains_throwsClassCastException() {
+ Set<E> set = createSet();
+ set.add(getKeys()[0]);
+ try {
+ set.contains(getConflictingKey());
+ assertTrue("CCE expected in hosted mode", GWT.isScript());
+ } catch (ClassCastException e) {
+ // expected outcome
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.contains(Object)'.
+ *
+ * @see java.util.Set#contains(Object)
+ */
+ public void testContains_throwsNullPointerException() {
+ Set<E> set = createSet();
+ if (isNaturalOrder() && !isNullKeySupported) {
+ try {
+ set.contains(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.Object.equals(Object)'.
+ *
+ * @see java.util.Set#equals(Object)
+ */
+ public void testEquals() {
+ Set<E> set0 = createSet();
+ Set<E> set1 = createSet();
+ assertTrue(set0.equals(set1));
+ set0.add(getKeys()[0]);
+ set1.add(getKeys()[0]);
+ assertTrue(set0.equals(set0));
+ assertTrue(set0.equals(set1));
+ set0.add(getKeys()[1]);
+ assertFalse(set0.equals(set1));
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.first()'.
+ *
+ * @see java.util.SortedSet#first()
+ */
+ public void testFirst() {
+ SortedSet<E> sortedSet = createSortedSet();
+ // test with a single entry set
+ sortedSet.add(getKeys()[0]);
+ assertEquals(getKeys()[0], sortedSet.first());
+ // is it consistent with other methods
+ assertEquals(sortedSet.toArray()[0], sortedSet.first());
+ assertEquals(getKeys()[0], sortedSet.last());
+ assertEquals(sortedSet.last(), sortedSet.first());
+
+ // test with two entry set
+ sortedSet.add(getKeys()[1]);
+ assertEquals(getKeys()[0], sortedSet.first());
+ assertFalse(getKeys()[1].equals(sortedSet.first()));
+ // is it consistent with other methods
+ assertEquals(sortedSet.toArray()[0], sortedSet.first());
+ assertFalse(getKeys()[0].equals(sortedSet.last()));
+ assertFalse(sortedSet.last().equals(sortedSet.first()));
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.first()'.
+ *
+ * @see java.util.SortedSet#first()
+ */
+ public void testFirstKey_throwsNoSuchElementException() {
+ SortedSet<E> SortedSet = createSortedSet();
+ // test with no entries
+ try {
+ SortedSet.first();
+ fail("expected exception");
+ } catch (NoSuchElementException e) {
+ // expected outcome
+ }
+ }
+
+ /**
+ * Test method for 'java.lang.Object.hashCode()'.
+ *
+ * @see java.util.Set#hashCode()
+ */
+ public void testHashCode() {
+ Set<E> set0 = createSet();
+ Set<E> set1 = createSet();
+
+ int hashCode0 = set0.hashCode();
+ int hashCode1 = set1.hashCode();
+ assertTrue("empty maps have different hash codes", hashCode0 == hashCode1);
+
+ // Check that hashCode changes
+ set0.add(getKeys()[0]);
+ hashCode0 = set0.hashCode();
+ assertTrue("hash code didn't change", hashCode0 != hashCode1);
+
+ Set<String> set2 = new TreeSet<String>();
+ set2.add("");
+ Set<Integer> set3 = new TreeSet<Integer>();
+ set3.add(0);
+ int hashCode2 = set2.hashCode();
+ int hashCode3 = set3.hashCode();
+ assertEquals("empty string/0 hash codes not the same", hashCode2, hashCode3);
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.headSet(Object, Object)'.
+ *
+ * @see java.util.SortedSet#headSet(Object)
+ */
+ @SuppressWarnings("unchecked")
+ public void testHeadMap_throwsClassCastException() {
+ SortedSet SortedSet = createSortedSet();
+ SortedSet.add(getKeys()[0]);
+ if (isNaturalOrder()) {
+ // TODO Why does this succeed with natural ordering when subSet doesn't?
+ SortedSet.headSet(getConflictingKey());
+ } else {
+ try {
+ SortedSet.headSet(getConflictingKey());
+ assertTrue("CCE expected in hosted mode", GWT.isScript());
+ } catch (ClassCastException e) {
+ // expected outcome
+ }
+ }
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.headSet(Object)'.
+ *
+ * @see java.util.SortedSet#headSet(Object)
+ */
+ public void testHeadSet() {
+ // test with no entries
+ assertNotNull(createSortedSet().headSet(getKeys()[0]));
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.headSet(Object)'.
+ *
+ * @see java.util.SortedSet#headSet(Object)
+ */
+ public void testHeadSet_entries0_size() {
+ // test with no entries
+ assertEquals(0, createSortedSet().headSet(getKeys()[0]).size());
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.headSet(Object)'.
+ *
+ * @see java.util.SortedSet#headSet(Object)
+ */
+ public void testHeadSet_entries1() {
+ SortedSet<E> SortedSet = createSortedSet();
+ // test with a single entry set
+ SortedSet.add(getKeys()[0]);
+ assertEquals(0, SortedSet.headSet(getKeys()[0]).size());
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.headSet(Object)'.
+ *
+ * @see java.util.SortedSet#headSet(Object)
+ */
+ public void testHeadSet_entries2() {
+ SortedSet<E> SortedSet = createSortedSet();
+ // test with two entry set
+ SortedSet.add(getKeys()[0]);
+ SortedSet.add(getKeys()[1]);
+ assertEquals(0, SortedSet.headSet(getKeys()[0]).size());
+ assertEquals(1, SortedSet.headSet(getKeys()[1]).size());
+ assertEquals(getKeys()[0], SortedSet.tailSet(getKeys()[0]).toArray()[0]);
+ }
+
+ /**
+ * Test method for 'java.util.Set.isEmpty()'. *
+ *
+ * @see java.util.Set#isEmpty()
+ *
+ */
+ public void testIsEmpty() {
+ Set<E> sourceSet = createSet();
+ Set<E> destSet = createSet();
+
+ destSet.addAll(sourceSet);
+ assertTrue(destSet.isEmpty());
+
+ destSet.add(getKeys()[0]);
+ assertFalse(destSet.isEmpty());
+
+ destSet.remove(getKeys()[0]);
+ assertTrue(destSet.isEmpty());
+ assertEquals(destSet.size(), 0);
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.last()'.
+ *
+ * @see java.util.SortedSet#last()
+ */
+ public void testLastKey() {
+ SortedSet<E> sortedSet = createSortedSet();
+
+ // test with a single entry set
+ sortedSet.add(getKeys()[0]);
+ assertEquals(getKeys()[0], sortedSet.last());
+ // is it consistent with other methods
+ assertEquals(sortedSet.toArray()[0], sortedSet.last());
+ assertEquals(getKeys()[0], sortedSet.first());
+ assertEquals(sortedSet.first(), sortedSet.last());
+
+ // test with two entry set
+ sortedSet.add(getKeys()[1]);
+ assertEquals(getKeys()[1], sortedSet.last());
+ assertFalse(getKeys()[0].equals(sortedSet.last()));
+ // is it consistent with other methods
+ assertEquals(sortedSet.toArray()[1], sortedSet.last());
+ assertEquals(getKeys()[0], sortedSet.first());
+ assertFalse(sortedSet.first().equals(sortedSet.last()));
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.last()'.
+ *
+ * @see java.util.SortedSet#last()
+ */
+ public void testLastKey_throwsNoSuchElementException() {
+ SortedSet<E> SortedSet = createSortedSet();
+ // test with no entries
+ try {
+ SortedSet.last();
+ fail("expected exception");
+ } catch (NoSuchElementException e) {
+ // expected outcome
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.remove(Object)'.
+ *
+ * @see java.util.Set#remove(Object)
+ */
+ public void testRemove() {
+ // The _throwsUnsupportedOperationException version of this test will
+ // verify that the method is not supported.
+ if (isRemoveSupported) {
+ Set<E> set = createSet();
+
+ assertFalse(set.remove(getKeys()[0]));
+ assertTrue(set.add(getKeys()[0]));
+ assertTrue(set.remove(getKeys()[0]));
+ assertFalse(set.remove(getKeys()[0]));
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.remove(Object)'.
+ *
+ * @see java.util.Set#remove(Object)
+ */
+ public void testRemove_throwsClassCastException() {
+ // The _throwsUnsupportedOperationException version of this test will
+ // verify that the method is not supported.
+ if (isRemoveSupported) {
+ Set<E> set = createSet();
+ set.add(getKeys()[0]);
+ try {
+ set.remove(getConflictingKey());
+ assertTrue("CCE expected in hosted mode", GWT.isScript());
+ } catch (ClassCastException e) {
+ // expected outcome
+ }
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.remove(Object)'.
+ *
+ * @see java.util.Set#remove(Object)
+ */
+ public void testRemove_throwsUnsupportedOperationException() {
+ Set<E> set = createSet();
+ if (!isRemoveSupported) {
+ try {
+ set.remove(getKeys()[0]);
+ fail("expected exception");
+ } catch (UnsupportedOperationException e) {
+ // expected outcome
+ }
+ }
+ }
+
+ /**
+ * Test method for 'java.util.Set.size()'.
+ *
+ * @see java.util.Set#size()
+ */
+ public void testSize() {
+ Set<E> set = createSet();
+
+ // Test size behavior on add
+ set.add(getKeys()[0]);
+ assertEquals(1, set.size());
+ set.add(getKeys()[1]);
+ assertEquals(2, set.size());
+ set.add(getKeys()[2]);
+ assertEquals(3, set.size());
+
+ // Test size behavior on remove
+ set.remove(getKeys()[0]);
+ assertEquals(2, set.size());
+ set.remove(getKeys()[1]);
+ assertEquals(1, set.size());
+ set.remove(getKeys()[2]);
+ assertEquals(0, set.size());
+
+ // Test size behavior on putAll
+ set.add(getKeys()[0]);
+ set.add(getKeys()[1]);
+ set.add(getKeys()[2]);
+ assertEquals(3, set.size());
+
+ // Test size behavior on clear
+ set.clear();
+ _assertEmpty(set);
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.subSet(Object, Object)'.
+ *
+ * @see java.util.SortedSet#subSet(Object, Object)
+ */
+ @SuppressWarnings("unchecked")
+ public void testSubMap_throwsClassCastException() {
+ SortedSet SortedSet = createSortedSet();
+ SortedSet.add(getKeys()[0]);
+ try {
+ SortedSet.subSet(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 {
+ SortedSet.subSet(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.SortedSet.subSet(Object, Object)'.
+ *
+ * @see java.util.SortedSet#subSet(Object, Object)
+ */
+ public void testSubMap_throwsIllegalArgumentException() {
+ SortedSet<E> SortedSet = createSortedSet();
+ try {
+ SortedSet.subSet(getGreaterThanMaximumKey(), getLessThanMinimumKey());
+ fail("expected exception");
+ } catch (IllegalArgumentException e) {
+ // from key is greater than the to key
+ // expected outcome
+ }
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.subSet(Object, Object)'.
+ *
+ * @see java.util.SortedSet#subSet(Object, Object)
+ */
+ public void testSubSet() {
+ SortedSet<E> sortedSet = createSortedSet();
+ // test with no entries
+ assertEquals(0, sortedSet.subSet(getKeys()[0], getKeys()[0]).size());
+
+ // test with a single entry set
+ sortedSet.add(getKeys()[0]);
+ assertEquals(0, sortedSet.subSet(getKeys()[0], getKeys()[0]).size());
+ // bounded by a "wide" range
+ assertEquals(1, sortedSet.subSet(getLessThanMinimumKey(),
+ getGreaterThanMaximumKey()).size());
+
+ // test with two entry set
+ sortedSet.add(getKeys()[1]);
+ assertEquals(1, sortedSet.subSet(getKeys()[0], getKeys()[1]).size());
+ assertEquals(getKeys()[0],
+ sortedSet.subSet(getKeys()[0], getKeys()[1]).toArray()[0]);
+ // bounded by a "wide" range
+ SortedSet<E> subSet = sortedSet.subSet(getLessThanMinimumKey(),
+ getGreaterThanMaximumKey());
+ assertEquals(2, subSet.size());
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.tailSet(Object)'.
+ *
+ * @see java.util.SortedSet#tailSet(Object)
+ */
+ public void testTailSet_entries0() {
+ // test with no entries
+ Set<E> tailSet = createSortedSet().tailSet(getKeys()[0]);
+ assertNotNull(tailSet);
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.tailSet(Object)'.
+ *
+ * @see java.util.SortedSet#tailSet(Object)
+ */
+ public void testTailSet_entries0_size() {
+ // test with no entries
+ Set<E> tailSet = createSortedSet().tailSet(getKeys()[0]);
+ assertNotNull(tailSet);
+ assertEquals(0, tailSet.size());
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.tailSet(Object)'.
+ *
+ * @see java.util.SortedSet#tailSet(Object)
+ */
+ public void testTailSet_entries1_size_keyValue() {
+ SortedSet<E> sortedSet = createSortedSet();
+ // test with a single entry set
+ sortedSet.add(getKeys()[0]);
+ Set<E> tailSet = sortedSet.tailSet(getKeys()[0]);
+ assertEquals(1, tailSet.size());
+ assertEquals(getKeys()[0], tailSet.toArray()[0]);
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.tailSet(Object)'.
+ *
+ * @see java.util.SortedSet#tailSet(Object)
+ */
+ public void testTailSet_entries2_size_keyValue() {
+ SortedSet<E> sortedSet = createSortedSet();
+ // test with two entry set
+ sortedSet.add(getKeys()[0]);
+ Set<E> tailSet = sortedSet.tailSet(getKeys()[0]);
+ assertEquals(1, tailSet.size());
+ sortedSet.add(getKeys()[1]);
+ tailSet = sortedSet.tailSet(getKeys()[1]);
+ assertEquals(1, tailSet.size());
+ tailSet = sortedSet.tailSet(getKeys()[0]);
+ assertEquals(2, tailSet.size());
+ assertEquals(getKeys()[0], tailSet.toArray()[0]);
+ assertEquals(getKeys()[1], tailSet.toArray()[1]);
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.tailSet(Object, Object)'.
+ *
+ * @see java.util.SortedSet#tailSet(Object)
+ */
+ @SuppressWarnings("unchecked")
+ public void testTailSet_throwsClassCastException() {
+ SortedSet SortedSet = createSortedSet();
+ SortedSet.add(getKeys()[0]);
+ if (isNaturalOrder()) {
+ // TODO Why does this succeed with natural ordering when subSet doesn't?
+ SortedSet.tailSet(getConflictingKey());
+ } else {
+ try {
+ SortedSet.tailSet(getConflictingKey());
+ assertTrue("CCE expected in hosted mode", GWT.isScript());
+ } catch (ClassCastException e) {
+ // expected outcome
+ }
+ }
+ }
+
+ /**
+ * Test method for 'java.util.SortedSet.tailSet(Object, Object)'.
+ *
+ * @see java.util.SortedSet#tailSet(Object)
+ */
+ public void testTailSet_throwsIllegalArgumentException() {
+ // TODO I don't know of any case where this could happen.
+ }
+
+ protected Comparator<E> getComparator() {
+ return comparator;
+ }
+
+ protected abstract Object getConflictingKey();
+
+ protected abstract Object getConflictingValue();
+
+ @Override
+ protected Object[] getFullElements() {
+ return getKeys();
+ }
+
+ @Override
+ protected Object[] getOtherElements() {
+ return getKeys2();
+ }
+
+ @Override
+ protected void gwtSetUp() throws Exception {
+ setComparator(null);
+ }
+
+ protected boolean isNaturalOrder() {
+ return comparator == null;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ protected Set makeEmptySet() {
+ return createTreeSet();
+ }
+
+ protected void setComparator(Comparator<E> comparator) {
+ this.comparator = comparator;
+ }
+
+ Set<E> createSet() {
+ return createSortedSet();
+ }
+
+ SortedSet<E> createSortedSet() {
+ SortedSet<E> set = createTreeSet();
+ return set;
+ }
+
+ TreeSet<E> createTreeSet() {
+ if (isNaturalOrder()) {
+ return new TreeSet<E>();
+ } else {
+ return new TreeSet<E>(getComparator());
+ }
+ }
+
+ abstract E getGreaterThanMaximumKey();
+
+ abstract E[] getKeys();
+
+ abstract E[] getKeys2();
+
+ abstract E getLessThanMinimumKey();
+}
