Created a set of memory-friendly collections specifically for use in the compiler.
The goal is to provide API compatibility with the JRE versions, yet use a lot less memory. I particularly am focusing on optimizing the case of empty and singleton collections, which is an extremely common case in the compiler, and an easy win for memory. Having lots of nodes refer to the single-instance empty set or list takes almost no memory, a default empty ArrayList or HashSet is very expensive by comparison.
Review by: spoon
git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@5149 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/dev/core/build.xml b/dev/core/build.xml
index b13b66d..5f4876a 100755
--- a/dev/core/build.xml
+++ b/dev/core/build.xml
@@ -6,7 +6,7 @@
<property name="alldeps.jar" location="${project.build}/alldeps.jar" />
<fileset id="default.tests" dir="${javac.junit.out}">
- <include name="**/*Test.class" />
+ <include name="**/com/google/**/*Test.class" />
</fileset>
<target name="compile.tests" depends="build" description="Compiles the test code for this project">
diff --git a/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java b/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java
new file mode 100644
index 0000000..c643d9f
--- /dev/null
+++ b/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java
@@ -0,0 +1,816 @@
+/*
+ * Copyright 2009 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.dev.util.collect;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+import java.util.AbstractCollection;
+import java.util.AbstractSet;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * A memory-efficient hash map.
+ *
+ * @param <K> the key type
+ * @param <V> the value type
+ */
+public class HashMap<K, V> implements Map<K, V>, Serializable {
+
+ /**
+ * In the interest of memory-savings, we start with the smallest feasible
+ * power-of-two table size that can hold three items without rehashing. If we
+ * started with a size of 2, we'd have to expand as soon as the second item
+ * was added.
+ */
+ private static final int INITIAL_TABLE_SIZE = 4;
+
+ private class EntryIterator implements Iterator<Entry<K, V>> {
+ private int index = 0;
+ private int last = -1;
+
+ {
+ advanceToItem();
+ }
+
+ public boolean hasNext() {
+ return index < keys.length;
+ }
+
+ public Entry<K, V> next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ last = index;
+ Entry<K, V> toReturn = new HashEntry(index++);
+ advanceToItem();
+ return toReturn;
+ }
+
+ public void remove() {
+ if (last < 0) {
+ throw new IllegalStateException();
+ }
+ internalRemove(last);
+ if (keys[last] != null) {
+ index = last;
+ }
+ last = -1;
+ }
+
+ private void advanceToItem() {
+ for (; index < keys.length; ++index) {
+ if (keys[index] != null) {
+ return;
+ }
+ }
+ }
+ }
+
+ private class EntrySet extends AbstractSet<Entry<K, V>> {
+ @Override
+ public boolean add(Entry<K, V> entry) {
+ boolean result = !HashMap.this.containsKey(entry.getKey());
+ HashMap.this.put(entry.getKey(), entry.getValue());
+ return result;
+ }
+
+ @Override
+ public boolean addAll(Collection<? extends Entry<K, V>> c) {
+ HashMap.this.ensureSizeFor(size() + c.size());
+ return super.addAll(c);
+ }
+
+ @Override
+ public void clear() {
+ HashMap.this.clear();
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ public boolean contains(Object o) {
+ if (!(o instanceof Entry)) {
+ return false;
+ }
+ Entry<K, V> entry = (Entry<K, V>) o;
+ V value = HashMap.this.get(entry.getKey());
+ return HashMap.this.valueEquals(value, entry.getValue());
+ }
+
+ @Override
+ public int hashCode() {
+ return HashMap.this.hashCode();
+ }
+
+ @Override
+ public Iterator<java.util.Map.Entry<K, V>> iterator() {
+ return new EntryIterator();
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ public boolean remove(Object o) {
+ if (!(o instanceof Entry)) {
+ return false;
+ }
+ Entry<K, V> entry = (Entry<K, V>) o;
+ int index = findKey(entry.getKey());
+ if (index >= 0 && valueEquals(values[index], entry.getValue())) {
+ internalRemove(index);
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public boolean removeAll(Collection<?> c) {
+ boolean didRemove = false;
+ for (Object o : c) {
+ didRemove |= remove(o);
+ }
+ return didRemove;
+ }
+
+ @Override
+ public int size() {
+ return HashMap.this.size;
+ }
+ }
+
+ private class HashEntry implements Entry<K, V> {
+ private final int index;
+
+ public HashEntry(int index) {
+ this.index = index;
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ public boolean equals(Object o) {
+ if (!(o instanceof Entry)) {
+ return false;
+ }
+ Entry<K, V> entry = (Entry<K, V>) o;
+ return keyEquals(getKey(), entry.getKey())
+ && valueEquals(getValue(), entry.getValue());
+ }
+
+ @SuppressWarnings("unchecked")
+ public K getKey() {
+ return (K) unmaskNullKey(keys[index]);
+ }
+
+ @SuppressWarnings("unchecked")
+ public V getValue() {
+ return (V) values[index];
+ }
+
+ @Override
+ public int hashCode() {
+ return keyHashCode(getKey()) ^ valueHashCode(getValue());
+ }
+
+ @SuppressWarnings("unchecked")
+ public V setValue(V value) {
+ V previous = (V) values[index];
+ values[index] = value;
+ return previous;
+ }
+
+ @Override
+ public String toString() {
+ return getKey() + "=" + getValue();
+ }
+ }
+
+ private class KeyIterator implements Iterator<K> {
+ private int index = 0;
+ private int last = -1;
+
+ {
+ advanceToItem();
+ }
+
+ public boolean hasNext() {
+ return index < keys.length;
+ }
+
+ @SuppressWarnings("unchecked")
+ public K next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ last = index;
+ Object toReturn = unmaskNullKey(keys[index++]);
+ advanceToItem();
+ return (K) toReturn;
+ }
+
+ public void remove() {
+ if (last < 0) {
+ throw new IllegalStateException();
+ }
+ internalRemove(last);
+ if (keys[last] != null) {
+ index = last;
+ }
+ last = -1;
+ }
+
+ private void advanceToItem() {
+ for (; index < keys.length; ++index) {
+ if (keys[index] != null) {
+ return;
+ }
+ }
+ }
+ }
+
+ private class KeySet extends AbstractSet<K> {
+ @Override
+ public void clear() {
+ HashMap.this.clear();
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ return HashMap.this.containsKey(o);
+ }
+
+ @Override
+ public int hashCode() {
+ int result = 0;
+ for (int i = 0; i < keys.length; ++i) {
+ Object key = keys[i];
+ if (key != null) {
+ result += keyHashCode(unmaskNullKey(key));
+ }
+ }
+ return result;
+ }
+
+ @Override
+ public Iterator<K> iterator() {
+ return new KeyIterator();
+ }
+
+ @Override
+ public boolean remove(Object o) {
+ int index = findKey(o);
+ if (index >= 0) {
+ internalRemove(index);
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public boolean removeAll(Collection<?> c) {
+ boolean didRemove = false;
+ for (Object o : c) {
+ didRemove |= remove(o);
+ }
+ return didRemove;
+ }
+
+ @Override
+ public int size() {
+ return HashMap.this.size;
+ }
+ }
+
+ private class ValueIterator implements Iterator<V> {
+ private int index = 0;
+ private int last = -1;
+
+ {
+ advanceToItem();
+ }
+
+ public boolean hasNext() {
+ return index < keys.length;
+ }
+
+ @SuppressWarnings("unchecked")
+ public V next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ last = index;
+ Object toReturn = values[index++];
+ advanceToItem();
+ return (V) toReturn;
+ }
+
+ public void remove() {
+ if (last < 0) {
+ throw new IllegalStateException();
+ }
+ internalRemove(last);
+ if (keys[last] != null) {
+ index = last;
+ }
+ last = -1;
+ }
+
+ private void advanceToItem() {
+ for (; index < keys.length; ++index) {
+ if (keys[index] != null) {
+ return;
+ }
+ }
+ }
+ }
+
+ private class Values extends AbstractCollection<V> {
+ @Override
+ public void clear() {
+ HashMap.this.clear();
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ return HashMap.this.containsValue(o);
+ }
+
+ @Override
+ public int hashCode() {
+ int result = 0;
+ for (int i = 0; i < keys.length; ++i) {
+ if (keys[i] != null) {
+ result += valueHashCode(values[i]);
+ }
+ }
+ return result;
+ }
+
+ @Override
+ public Iterator<V> iterator() {
+ return new ValueIterator();
+ }
+
+ @Override
+ public boolean remove(Object o) {
+ if (o == null) {
+ for (int i = 0; i < keys.length; ++i) {
+ if (keys[i] != null && values[i] == null) {
+ internalRemove(i);
+ return true;
+ }
+ }
+ } else {
+ for (int i = 0; i < keys.length; ++i) {
+ if (valueEquals(values[i], o)) {
+ internalRemove(i);
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ @Override
+ public boolean removeAll(Collection<?> c) {
+ boolean didRemove = false;
+ for (Object o : c) {
+ didRemove |= remove(o);
+ }
+ return didRemove;
+ }
+
+ @Override
+ public int size() {
+ return HashMap.this.size;
+ }
+ }
+
+ private static final Object NULL_KEY = new Serializable() {
+ Object readResolve() {
+ return NULL_KEY;
+ }
+ };
+
+ private static Object maskNullKey(Object k) {
+ return (k == null) ? NULL_KEY : k;
+ }
+
+ private static Object unmaskNullKey(Object k) {
+ return (k == NULL_KEY) ? null : k;
+ }
+
+ /**
+ * Backing store for all the keys; transient due to custom serialization.
+ * Default access to avoid synthetic accessors from inner classes.
+ */
+ transient Object[] keys;
+
+ /**
+ * Number of pairs in this set; transient due to custom serialization. Default
+ * access to avoid synthetic accessors from inner classes.
+ */
+ transient int size = 0;
+
+ /**
+ * Backing store for all the values; transient due to custom serialization.
+ * Default access to avoid synthetic accessors from inner classes.
+ */
+ transient Object[] values;
+
+ public HashMap() {
+ initTable(INITIAL_TABLE_SIZE);
+ }
+
+ public HashMap(Map<? extends K, ? extends V> m) {
+ int newCapacity = INITIAL_TABLE_SIZE;
+ int expectedSize = m.size();
+ while (newCapacity * 3 < expectedSize * 4) {
+ newCapacity <<= 1;
+ }
+
+ initTable(newCapacity);
+ internalPutAll(m);
+ }
+
+ public void clear() {
+ initTable(INITIAL_TABLE_SIZE);
+ size = 0;
+ }
+
+ public boolean containsKey(Object key) {
+ return findKey(key) >= 0;
+ }
+
+ public boolean containsValue(Object value) {
+ if (value == null) {
+ for (int i = 0; i < keys.length; ++i) {
+ if (keys[i] != null && values[i] == null) {
+ return true;
+ }
+ }
+ } else {
+ for (Object existing : values) {
+ if (valueEquals(existing, value)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ public Set<Entry<K, V>> entrySet() {
+ return new EntrySet();
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ public boolean equals(Object o) {
+ if (!(o instanceof Map)) {
+ return false;
+ }
+ Map<K, V> other = (Map<K, V>) o;
+ return entrySet().equals(other.entrySet());
+ }
+
+ @SuppressWarnings("unchecked")
+ public V get(Object key) {
+ int index = findKey(key);
+ return (index < 0) ? null : (V) values[index];
+ }
+
+ @Override
+ public int hashCode() {
+ int result = 0;
+ for (int i = 0; i < keys.length; ++i) {
+ Object key = keys[i];
+ if (key != null) {
+ result += keyHashCode(unmaskNullKey(key)) ^ valueHashCode(values[i]);
+ }
+ }
+ return result;
+ }
+
+ public boolean isEmpty() {
+ return size == 0;
+ }
+
+ public Set<K> keySet() {
+ return new KeySet();
+ }
+
+ @SuppressWarnings("unchecked")
+ public V put(K key, V value) {
+ ensureSizeFor(size + 1);
+ int index = findKeyOrEmpty(key);
+ if (keys[index] == null) {
+ ++size;
+ keys[index] = maskNullKey(key);
+ values[index] = value;
+ return null;
+ } else {
+ Object previousValue = values[index];
+ values[index] = value;
+ return (V) previousValue;
+ }
+ }
+
+ public void putAll(Map<? extends K, ? extends V> m) {
+ ensureSizeFor(size + m.size());
+ internalPutAll(m);
+ }
+
+ @SuppressWarnings("unchecked")
+ public V remove(Object key) {
+ int index = findKey(key);
+ if (index < 0) {
+ return null;
+ }
+ Object previousValue = values[index];
+ internalRemove(index);
+ return (V) previousValue;
+ }
+
+ public int size() {
+ return size;
+ }
+
+ @Override
+ public String toString() {
+ if (size == 0) {
+ return "{}";
+ }
+ StringBuilder buf = new StringBuilder(32 * size());
+ buf.append('{');
+
+ boolean needComma = false;
+ for (int i = 0; i < keys.length; ++i) {
+ Object key = keys[i];
+ if (key != null) {
+ if (needComma) {
+ buf.append(',').append(' ');
+ }
+ key = unmaskNullKey(key);
+ Object value = values[i];
+ buf.append(key == this ? "(this Map)" : key).append('=').append(
+ value == this ? "(this Map)" : value);
+ needComma = true;
+ }
+ }
+ buf.append('}');
+ return buf.toString();
+ }
+
+ public Collection<V> values() {
+ return new Values();
+ }
+
+ /**
+ * Adapted from {@link org.apache.commons.collections.map.AbstractHashedMap}.
+ */
+ @SuppressWarnings("unchecked")
+ protected void doReadObject(ObjectInputStream in) throws IOException,
+ ClassNotFoundException {
+ int capacity = in.readInt();
+ initTable(capacity);
+ int items = in.readInt();
+ for (int i = 0; i < items; i++) {
+ Object key = in.readObject();
+ Object value = in.readObject();
+ put((K) key, (V) value);
+ }
+ }
+
+ /**
+ * Adapted from {@link org.apache.commons.collections.map.AbstractHashedMap}.
+ */
+ protected void doWriteObject(ObjectOutputStream out) throws IOException {
+ out.writeInt(keys.length);
+ out.writeInt(size);
+ for (int i = 0; i < keys.length; ++i) {
+ Object key = keys[i];
+ if (key != null) {
+ out.writeObject(unmaskNullKey(key));
+ out.writeObject(values[i]);
+ }
+ }
+ }
+
+ /**
+ * Returns whether two keys are equal for the purposes of this set.
+ */
+ protected boolean keyEquals(Object a, Object b) {
+ return (a == null) ? (b == null) : a.equals(b);
+ }
+
+ /**
+ * Returns the hashCode for a key.
+ */
+ protected int keyHashCode(Object k) {
+ return (k == null) ? 0 : k.hashCode();
+ }
+
+ /**
+ * Returns whether two values are equal for the purposes of this set.
+ */
+ protected boolean valueEquals(Object a, Object b) {
+ return (a == null) ? (b == null) : a.equals(b);
+ }
+
+ /**
+ * Returns the hashCode for a value.
+ */
+ protected int valueHashCode(Object v) {
+ return (v == null) ? 0 : v.hashCode();
+ }
+
+ /**
+ * Ensures the map is large enough to contain the specified number of entries.
+ * Default access to avoid synthetic accessors from inner classes.
+ */
+ void ensureSizeFor(int expectedSize) {
+ if (keys.length * 3 >= expectedSize * 4) {
+ return;
+ }
+
+ int newCapacity = keys.length << 1;
+ while (newCapacity * 3 < expectedSize * 4) {
+ newCapacity <<= 1;
+ }
+
+ Object[] oldKeys = keys;
+ Object[] oldValues = values;
+ initTable(newCapacity);
+ for (int i = 0; i < oldKeys.length; ++i) {
+ Object k = oldKeys[i];
+ if (k != null) {
+ int newIndex = getKeyIndex(unmaskNullKey(k));
+ while (keys[newIndex] != null) {
+ if (++newIndex == keys.length) {
+ newIndex = 0;
+ }
+ }
+ keys[newIndex] = k;
+ values[newIndex] = oldValues[i];
+ }
+ }
+ }
+
+ /**
+ * Returns the index in the key table at which a particular key resides, or -1
+ * if the key is not in the table. Default access to avoid synthetic accessors
+ * from inner classes.
+ */
+ int findKey(Object k) {
+ int index = getKeyIndex(k);
+ while (true) {
+ Object existing = keys[index];
+ if (existing == null) {
+ return -1;
+ }
+ if (keyEquals(k, unmaskNullKey(existing))) {
+ return index;
+ }
+ if (++index == keys.length) {
+ index = 0;
+ }
+ }
+ }
+
+ /**
+ * Returns the index in the key table at which a particular key resides, or
+ * the index of an empty slot in the table where this key should be inserted
+ * if it is not already in the table. Default access to avoid synthetic
+ * accessors from inner classes.
+ */
+ int findKeyOrEmpty(Object k) {
+ int index = getKeyIndex(k);
+ while (true) {
+ Object existing = keys[index];
+ if (existing == null) {
+ return index;
+ }
+ if (keyEquals(k, unmaskNullKey(existing))) {
+ return index;
+ }
+ if (++index == keys.length) {
+ index = 0;
+ }
+ }
+ }
+
+ /**
+ * Removes the entry at the specified index, and performs internal management
+ * to make sure we don't wind up with a hole in the table. Default access to
+ * avoid synthetic accessors from inner classes.
+ */
+ void internalRemove(int index) {
+ keys[index] = null;
+ values[index] = null;
+ --size;
+ plugHole(index);
+ }
+
+ private int getKeyIndex(Object k) {
+ int h = keyHashCode(k);
+ // Copied from Apache's AbstractHashedMap; prevents power-of-two collisions.
+ h += ~(h << 9);
+ h ^= (h >>> 14);
+ h += (h << 4);
+ h ^= (h >>> 10);
+ // Power of two trick.
+ return h & (keys.length - 1);
+ }
+
+ private void initTable(int capacity) {
+ keys = new Object[capacity];
+ values = new Object[capacity];
+ }
+
+ private void internalPutAll(Map<? extends K, ? extends V> m) {
+ for (Entry<? extends K, ? extends V> entry : m.entrySet()) {
+ K key = entry.getKey();
+ V value = entry.getValue();
+ int index = findKeyOrEmpty(key);
+ if (keys[index] == null) {
+ ++size;
+ keys[index] = maskNullKey(key);
+ values[index] = value;
+ } else {
+ values[index] = value;
+ }
+ }
+ }
+
+ /**
+ * Tricky, we left a hole in the map, which we have to fill. The only way to
+ * do this is to search forwards through the map shuffling back values that
+ * match this index until we hit a null.
+ */
+ private void plugHole(int hole) {
+ int index = hole + 1;
+ if (index == keys.length) {
+ index = 0;
+ }
+ while (keys[index] != null) {
+ int targetIndex = getKeyIndex(unmaskNullKey(keys[index]));
+ if (hole < index) {
+ /*
+ * "Normal" case, the index is past the hole and the "bad range" is from
+ * hole (exclusive) to index (inclusive).
+ */
+ if (!(hole < targetIndex && targetIndex <= index)) {
+ // Plug it!
+ keys[hole] = keys[index];
+ values[hole] = values[index];
+ keys[index] = null;
+ values[index] = null;
+ hole = index;
+ }
+ } else {
+ /*
+ * "Wrapped" case, the index is before the hole (we've wrapped) and the
+ * "good range" is from index (exclusive) to hole (inclusive).
+ */
+ if (index < targetIndex && targetIndex <= hole) {
+ // Plug it!
+ keys[hole] = keys[index];
+ values[hole] = values[index];
+ keys[index] = null;
+ values[index] = null;
+ hole = index;
+ }
+ }
+ if (++index == keys.length) {
+ index = 0;
+ }
+ }
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException,
+ ClassNotFoundException {
+ in.defaultReadObject();
+ doReadObject(in);
+ }
+
+ private void writeObject(ObjectOutputStream out) throws IOException {
+ out.defaultWriteObject();
+ doWriteObject(out);
+ }
+}
diff --git a/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java b/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java
new file mode 100644
index 0000000..58dcc29
--- /dev/null
+++ b/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java
@@ -0,0 +1,373 @@
+/*
+ * Copyright 2009 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.dev.util.collect;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+import java.util.AbstractSet;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * A memory-efficient hash set.
+ *
+ * @param <E> the element type
+ */
+public class HashSet<E> extends AbstractSet<E> implements Serializable {
+
+ /**
+ * In the interest of memory-savings, we start with the smallest feasible
+ * power-of-two table size that can hold three items without rehashing. If we
+ * started with a size of 2, we'd have to expand as soon as the second item
+ * was added.
+ */
+ private static final int INITIAL_TABLE_SIZE = 4;
+
+ private class SetIterator implements Iterator<E> {
+ private int index = 0;
+ private int last = -1;
+
+ public SetIterator() {
+ advanceToItem();
+ }
+
+ public boolean hasNext() {
+ return index < table.length;
+ }
+
+ @SuppressWarnings("unchecked")
+ public E next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ last = index;
+ E toReturn = (E) unmaskNull(table[index++]);
+ advanceToItem();
+ return toReturn;
+ }
+
+ public void remove() {
+ if (last < 0) {
+ throw new IllegalStateException();
+ }
+ internalRemove(last);
+ if (table[last] != null) {
+ index = last;
+ }
+ last = -1;
+ }
+
+ private void advanceToItem() {
+ for (; index < table.length; ++index) {
+ if (table[index] != null) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static final Object NULL_ITEM = new Serializable() {
+ Object readResolve() {
+ return NULL_ITEM;
+ }
+ };
+
+ private static Object maskNull(Object o) {
+ return (o == null) ? NULL_ITEM : o;
+ }
+
+ private static Object unmaskNull(Object o) {
+ return (o == NULL_ITEM) ? null : o;
+ }
+
+ /**
+ * Number of objects in this set; transient due to custom serialization.
+ * Default access to avoid synthetic accessors from inner classes.
+ */
+ transient int size = 0;
+
+ /**
+ * Backing store for all the objects; transient due to custom serialization.
+ * Default access to avoid synthetic accessors from inner classes.
+ */
+ transient Object[] table;
+
+ public HashSet() {
+ table = new Object[INITIAL_TABLE_SIZE];
+ }
+
+ public HashSet(Collection<? extends E> c) {
+ int newCapacity = INITIAL_TABLE_SIZE;
+ int expectedSize = c.size();
+ while (newCapacity * 3 < expectedSize * 4) {
+ newCapacity <<= 1;
+ }
+
+ table = new Object[newCapacity];
+ super.addAll(c);
+ }
+
+ @Override
+ public boolean add(E e) {
+ ensureSizeFor(size + 1);
+ int index = findOrEmpty(e);
+ if (table[index] == null) {
+ ++size;
+ table[index] = maskNull(e);
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public boolean addAll(Collection<? extends E> c) {
+ ensureSizeFor(size + c.size());
+ return super.addAll(c);
+ }
+
+ @Override
+ public void clear() {
+ table = new Object[INITIAL_TABLE_SIZE];
+ size = 0;
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ return find(o) >= 0;
+ }
+
+ @Override
+ public Iterator<E> iterator() {
+ return new SetIterator();
+ }
+
+ @Override
+ public boolean remove(Object o) {
+ int index = find(o);
+ if (index < 0) {
+ return false;
+ }
+ internalRemove(index);
+ return true;
+ }
+
+ @Override
+ public int size() {
+ return size;
+ }
+
+ /**
+ * Adapted from {@link org.apache.commons.collections.map.AbstractHashedMap}.
+ */
+ @SuppressWarnings("unchecked")
+ protected void doReadObject(ObjectInputStream in) throws IOException,
+ ClassNotFoundException {
+ table = new Object[in.readInt()];
+ int items = in.readInt();
+ for (int i = 0; i < items; i++) {
+ add((E) in.readObject());
+ }
+ }
+
+ /**
+ * Adapted from {@link org.apache.commons.collections.map.AbstractHashedMap}.
+ */
+ protected void doWriteObject(ObjectOutputStream out) throws IOException {
+ out.writeInt(table.length);
+ out.writeInt(size);
+ for (int i = 0; i < table.length; ++i) {
+ Object e = table[i];
+ if (e != null) {
+ out.writeObject(unmaskNull(e));
+ }
+ }
+ }
+
+ /**
+ * Returns whether two items are equal for the purposes of this set.
+ */
+ protected boolean itemEquals(Object a, Object b) {
+ return (a == null) ? (b == null) : a.equals(b);
+ }
+
+ /**
+ * Return the hashCode for an item.
+ */
+ protected int itemHashCode(Object o) {
+ return (o == null) ? 0 : o.hashCode();
+ }
+
+ /**
+ * Works just like {@link #addAll(Collection)}, but for arrays. Used to avoid
+ * having to synthesize a collection in {@link Sets}.
+ */
+ void addAll(E[] elements) {
+ ensureSizeFor(size + elements.length);
+ for (E e : elements) {
+ int index = findOrEmpty(e);
+ if (table[index] == null) {
+ ++size;
+ table[index] = maskNull(e);
+ }
+ }
+ }
+
+ /**
+ * Removes the item at the specified index, and performs internal management
+ * to make sure we don't wind up with a hole in the table. Default access to
+ * avoid synthetic accessors from inner classes.
+ */
+ void internalRemove(int index) {
+ table[index] = null;
+ --size;
+ plugHole(index);
+ }
+
+ /**
+ * Ensures the set is large enough to contain the specified number of entries.
+ */
+ private void ensureSizeFor(int expectedSize) {
+ if (table.length * 3 >= expectedSize * 4) {
+ return;
+ }
+
+ int newCapacity = table.length << 1;
+ while (newCapacity * 3 < expectedSize * 4) {
+ newCapacity <<= 1;
+ }
+
+ Object[] oldTable = table;
+ table = new Object[newCapacity];
+ for (Object o : oldTable) {
+ if (o != null) {
+ int newIndex = getIndex(unmaskNull(o));
+ while (table[newIndex] != null) {
+ if (++newIndex == table.length) {
+ newIndex = 0;
+ }
+ }
+ table[newIndex] = o;
+ }
+ }
+ }
+
+ /**
+ * Returns the index in the table at which a particular item resides, or -1 if
+ * the item is not in the table.
+ */
+ private int find(Object o) {
+ int index = getIndex(o);
+ while (true) {
+ Object existing = table[index];
+ if (existing == null) {
+ return -1;
+ }
+ if (itemEquals(o, unmaskNull(existing))) {
+ return index;
+ }
+ if (++index == table.length) {
+ index = 0;
+ }
+ }
+ }
+
+ /**
+ * Returns the index in the table at which a particular item resides, or the
+ * index of an empty slot in the table where this item should be inserted if
+ * it is not already in the table.
+ */
+ private int findOrEmpty(Object o) {
+ int index = getIndex(o);
+ while (true) {
+ Object existing = table[index];
+ if (existing == null) {
+ return index;
+ }
+ if (itemEquals(o, unmaskNull(existing))) {
+ return index;
+ }
+ if (++index == table.length) {
+ index = 0;
+ }
+ }
+ }
+
+ private int getIndex(Object o) {
+ int h = itemHashCode(o);
+ // Copied from Apache's AbstractHashedMap; prevents power-of-two collisions.
+ h += ~(h << 9);
+ h ^= (h >>> 14);
+ h += (h << 4);
+ h ^= (h >>> 10);
+ // Power of two trick.
+ return h & (table.length - 1);
+ }
+
+ /**
+ * Tricky, we left a hole in the map, which we have to fill. The only way to
+ * do this is to search forwards through the map shuffling back values that
+ * match this index until we hit a null.
+ */
+ private void plugHole(int hole) {
+ int index = hole + 1;
+ if (index == table.length) {
+ index = 0;
+ }
+ while (table[index] != null) {
+ int targetIndex = getIndex(unmaskNull(table[index]));
+ if (hole < index) {
+ /*
+ * "Normal" case, the index is past the hole and the "bad range" is from
+ * hole (exclusive) to index (inclusive).
+ */
+ if (!(hole < targetIndex && targetIndex <= index)) {
+ // Plug it!
+ table[hole] = table[index];
+ table[index] = null;
+ hole = index;
+ }
+ } else {
+ /*
+ * "Wrapped" case, the index is before the hole (we've wrapped) and the
+ * "good range" is from index (exclusive) to hole (inclusive).
+ */
+ if (index < targetIndex && targetIndex <= hole) {
+ // Plug it!
+ table[hole] = table[index];
+ table[index] = null;
+ hole = index;
+ }
+ }
+ if (++index == table.length) {
+ index = 0;
+ }
+ }
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException,
+ ClassNotFoundException {
+ in.defaultReadObject();
+ doReadObject(in);
+ }
+
+ private void writeObject(ObjectOutputStream out) throws IOException {
+ out.defaultWriteObject();
+ doWriteObject(out);
+ }
+}
diff --git a/dev/core/src/com/google/gwt/dev/util/collect/IdentityHashMap.java b/dev/core/src/com/google/gwt/dev/util/collect/IdentityHashMap.java
new file mode 100644
index 0000000..89d690d
--- /dev/null
+++ b/dev/core/src/com/google/gwt/dev/util/collect/IdentityHashMap.java
@@ -0,0 +1,68 @@
+/*
+ * Copyright 2009 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.dev.util.collect;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.util.Map;
+
+/**
+ * A memory-efficient identity hash map.
+ *
+ * @param <K> the key type
+ * @param <V> the value type
+ */
+public class IdentityHashMap<K, V> extends HashMap<K, V> {
+
+ public IdentityHashMap() {
+ }
+
+ public IdentityHashMap(Map<? extends K, ? extends V> m) {
+ super(m);
+ }
+
+ @Override
+ protected boolean keyEquals(Object a, Object b) {
+ return a == b;
+ }
+
+ @Override
+ protected int keyHashCode(Object k) {
+ return System.identityHashCode(k);
+ }
+
+ @Override
+ protected boolean valueEquals(Object a, Object b) {
+ return a == b;
+ }
+
+ @Override
+ protected int valueHashCode(Object k) {
+ return System.identityHashCode(k);
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException,
+ ClassNotFoundException {
+ in.defaultReadObject();
+ doReadObject(in);
+ }
+
+ private void writeObject(ObjectOutputStream out) throws IOException {
+ out.defaultWriteObject();
+ doWriteObject(out);
+ }
+}
diff --git a/dev/core/src/com/google/gwt/dev/util/collect/IdentityHashSet.java b/dev/core/src/com/google/gwt/dev/util/collect/IdentityHashSet.java
new file mode 100644
index 0000000..13b71a8
--- /dev/null
+++ b/dev/core/src/com/google/gwt/dev/util/collect/IdentityHashSet.java
@@ -0,0 +1,56 @@
+/*
+ * Copyright 2009 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.dev.util.collect;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.util.Collection;
+
+/**
+ * A memory-efficient identity hash set.
+ *
+ * @param <E> the element type
+ */
+public class IdentityHashSet<E> extends HashSet<E> {
+ public IdentityHashSet() {
+ }
+
+ public IdentityHashSet(Collection<? extends E> c) {
+ super(c);
+ }
+
+ @Override
+ protected boolean itemEquals(Object a, Object b) {
+ return a == b;
+ }
+
+ @Override
+ protected int itemHashCode(Object o) {
+ return System.identityHashCode(o);
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException,
+ ClassNotFoundException {
+ in.defaultReadObject();
+ doReadObject(in);
+ }
+
+ private void writeObject(ObjectOutputStream out) throws IOException {
+ out.defaultWriteObject();
+ doWriteObject(out);
+ }
+}
diff --git a/dev/core/src/com/google/gwt/dev/util/collect/IdentityMaps.java b/dev/core/src/com/google/gwt/dev/util/collect/IdentityMaps.java
new file mode 100644
index 0000000..dd8d81e
--- /dev/null
+++ b/dev/core/src/com/google/gwt/dev/util/collect/IdentityMaps.java
@@ -0,0 +1,142 @@
+/*
+ * Copyright 2009 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.dev.util.collect;
+
+import java.util.Collections;
+import java.util.Map;
+
+/**
+ * Utility methods for operating on memory-efficient maps. All maps of size 0 or
+ * 1 are assumed to be immutable. All maps of size greater than 1 are assumed to
+ * be mutable.
+ */
+public class IdentityMaps {
+
+ private static final Class<?> MULTI_MAP_CLASS = IdentityHashMap.class;
+
+ private static final Class<?> SINGLETON_MAP_CLASS = IdentitySingletonMap.class;
+
+ public static <K, V> Map<K, V> create() {
+ return Collections.emptyMap();
+ }
+
+ public static <K, V> Map<K, V> create(K key, V value) {
+ return new IdentitySingletonMap<K, V>(key, value);
+ }
+
+ public static <K, V> Map<K, V> normalize(Map<K, V> map) {
+ switch (map.size()) {
+ case 0:
+ return create();
+ case 1: {
+ if (map.getClass() == SINGLETON_MAP_CLASS) {
+ return map;
+ }
+ K key = map.keySet().iterator().next();
+ return create(key, map.get(key));
+ }
+ default:
+ if (map.getClass() == MULTI_MAP_CLASS) {
+ return map;
+ }
+ return new IdentityHashMap<K, V>(map);
+ }
+ }
+
+ public static <K, V> Map<K, V> normalizeUnmodifiable(Map<K, V> map) {
+ if (map.size() < 2) {
+ return normalize(map);
+ } else {
+ // TODO: implement an UnmodifiableIdentityHashMap?
+ return Collections.unmodifiableMap(normalize(map));
+ }
+ }
+
+ public static <K, V> Map<K, V> put(Map<K, V> map, K key, V value) {
+ switch (map.size()) {
+ case 0:
+ // Empty -> Singleton
+ return create(key, value);
+ case 1: {
+ // Singleton -> IdentityHashMap
+ Map<K, V> result = new IdentityHashMap<K, V>();
+ result.put(map.keySet().iterator().next(),
+ map.values().iterator().next());
+ result.put(key, value);
+ return result;
+ }
+ default:
+ // IdentityHashMap
+ map.put(key, value);
+ return map;
+ }
+ }
+
+ public static <K, V> Map<K, V> putAll(Map<K, V> map, Map<K, V> toAdd) {
+ switch (toAdd.size()) {
+ case 0:
+ // No-op.
+ return map;
+ case 1: {
+ // Add one element.
+ K key = toAdd.keySet().iterator().next();
+ return put(map, key, toAdd.get(key));
+ }
+ default:
+ // True list merge, result >= 2.
+ switch (map.size()) {
+ case 0:
+ return new IdentityHashMap<K, V>(toAdd);
+ case 1: {
+ IdentityHashMap<K, V> result = new IdentityHashMap<K, V>();
+ K key = map.keySet().iterator().next();
+ result.put(key, map.get(key));
+ result.putAll(toAdd);
+ return result;
+ }
+ default:
+ map.putAll(toAdd);
+ return map;
+ }
+ }
+ }
+
+ public static <K, V> Map<K, V> remove(Map<K, V> map, K key) {
+ switch (map.size()) {
+ case 0:
+ // Empty
+ return map;
+ case 1:
+ // Singleton -> Empty
+ if (map.containsKey(key)) {
+ return create();
+ }
+ return map;
+ case 2:
+ // IdentityHashMap -> Singleton
+ if (map.containsKey(key)) {
+ map.remove(key);
+ key = map.keySet().iterator().next();
+ return create(key, map.get(key));
+ }
+ return map;
+ default:
+ // IdentityHashMap
+ map.remove(key);
+ return map;
+ }
+ }
+}
diff --git a/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java b/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java
new file mode 100644
index 0000000..6c1f989
--- /dev/null
+++ b/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java
@@ -0,0 +1,122 @@
+/*
+ * Copyright 2009 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.dev.util.collect;
+
+import java.io.Serializable;
+import java.util.AbstractSet;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * Utility methods for operating on memory-efficient identity sets. All sets of
+ * size 0 or 1 are assumed to be immutable. All sets of size greater than 1 are
+ * assumed to be mutable.
+ */
+public class IdentitySets {
+
+ private static class IdentitySingletonSet<T> extends AbstractSet<T> implements
+ Serializable {
+
+ private final T item;
+
+ IdentitySingletonSet(T item) {
+ this.item = item;
+ }
+
+ public boolean contains(Object o) {
+ return o == item;
+ }
+
+ public Iterator<T> iterator() {
+ return new SingletonIterator<T>(item);
+ }
+
+ public int size() {
+ return 1;
+ }
+ }
+
+ private static final class SingletonIterator<T> implements Iterator<T> {
+
+ /**
+ * Sentinel value to mark that this iterator's single item was consumed.
+ */
+ private static final Object EMPTY = new Object();
+
+ private T item;
+
+ SingletonIterator(T item) {
+ this.item = item;
+ }
+
+ public boolean hasNext() {
+ return item != EMPTY;
+ }
+
+ @SuppressWarnings("unchecked")
+ public T next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ T toReturn = item;
+ item = (T) EMPTY;
+ return toReturn;
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ }
+
+ public static <T> Set<T> add(Set<T> set, T toAdd) {
+ switch (set.size()) {
+ case 0:
+ // Empty -> Singleton
+ return new IdentitySingletonSet<T>(toAdd);
+ case 1: {
+ if (set.contains(toAdd)) {
+ return set;
+ }
+ // Singleton -> IdentityHashSet
+ Set<T> result = new IdentityHashSet<T>();
+ result.add(set.iterator().next());
+ result.add(toAdd);
+ return result;
+ }
+ default:
+ // IdentityHashSet
+ set.add(toAdd);
+ return set;
+ }
+ }
+
+ public static <T> Set<T> normalize(Set<T> set) {
+ switch (set.size()) {
+ case 0:
+ return Collections.emptySet();
+ case 1: {
+ if (set.getClass() != IdentitySingletonSet.class) {
+ return new IdentitySingletonSet<T>(set.iterator().next());
+ }
+ return set;
+ }
+ default:
+ return set;
+ }
+ }
+}
diff --git a/dev/core/src/com/google/gwt/dev/util/collect/IdentitySingletonMap.java b/dev/core/src/com/google/gwt/dev/util/collect/IdentitySingletonMap.java
new file mode 100644
index 0000000..b276872
--- /dev/null
+++ b/dev/core/src/com/google/gwt/dev/util/collect/IdentitySingletonMap.java
@@ -0,0 +1,148 @@
+/*
+ * Copyright 2009 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.dev.util.collect;
+
+import java.io.Serializable;
+import java.util.Collection;
+import java.util.Map;
+import java.util.Set;
+
+class IdentitySingletonMap<K, V> implements Map<K, V>, Serializable {
+
+ private class IdentityEntry implements Entry<K, V> {
+
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof Entry)) {
+ return false;
+ }
+ Entry<?, ?> entry = (Entry<?, ?>) o;
+ return key == entry.getKey() && value == entry.getValue();
+ }
+
+ public K getKey() {
+ return key;
+ }
+
+ public V getValue() {
+ return value;
+ }
+
+ @Override
+ public int hashCode() {
+ return System.identityHashCode(key) ^ System.identityHashCode(value);
+ }
+
+ public V setValue(V value) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public String toString() {
+ return key + "=" + value;
+ }
+ }
+
+ /**
+ * The key for the single entry. Default access to avoid synthetic accessors
+ * from inner classes.
+ */
+ final K key;
+
+ /**
+ * The value for the single entry. Default access to avoid synthetic accessors
+ * from inner classes.
+ */
+ final V value;
+
+ public IdentitySingletonMap(K key, V value) {
+ this.key = key;
+ this.value = value;
+ }
+
+ public void clear() {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean containsKey(Object k) {
+ return key == k;
+ }
+
+ public boolean containsValue(Object v) {
+ return value == v;
+ }
+
+ public Set<Entry<K, V>> entrySet() {
+ return Sets.<Entry<K, V>> create(new IdentityEntry());
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ public boolean equals(Object o) {
+ if (!(o instanceof Map)) {
+ return false;
+ }
+ Map<K, V> other = (Map<K, V>) o;
+ return entrySet().equals(other.entrySet());
+ }
+
+ public V get(Object k) {
+ return (key == k) ? value : null;
+ }
+
+ @Override
+ public int hashCode() {
+ return System.identityHashCode(key) ^ System.identityHashCode(value);
+ }
+
+ public boolean isEmpty() {
+ return false;
+ }
+
+ public Set<K> keySet() {
+ return Sets.create(key);
+ }
+
+ public V put(K key, V value) {
+ throw new UnsupportedOperationException();
+ }
+
+ public void putAll(Map<? extends K, ? extends V> m) {
+ throw new UnsupportedOperationException();
+ }
+
+ public V remove(Object key) {
+ throw new UnsupportedOperationException();
+ }
+
+ public int size() {
+ return 1;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder buf = new StringBuilder(32 * size());
+ buf.append('{');
+ buf.append(key == this ? "(this Map)" : key).append('=').append(
+ value == this ? "(this Map)" : value);
+ buf.append('}');
+ return buf.toString();
+ }
+
+ public Collection<V> values() {
+ return Sets.create(value);
+ }
+}
diff --git a/dev/core/src/com/google/gwt/dev/util/collect/Lists.java b/dev/core/src/com/google/gwt/dev/util/collect/Lists.java
new file mode 100644
index 0000000..131163b
--- /dev/null
+++ b/dev/core/src/com/google/gwt/dev/util/collect/Lists.java
@@ -0,0 +1,281 @@
+/*
+ * Copyright 2009 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.dev.util.collect;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+
+/**
+ * Utility methods for operating on memory-efficient lists. All lists of size 0
+ * or 1 are assumed to be immutable. All lists of size greater than 1 are
+ * assumed to be mutable.
+ */
+public class Lists {
+
+ private static final Class<?> MULTI_LIST_CLASS = ArrayList.class;
+ private static final Class<?> SINGLETON_LIST_CLASS = Collections.singletonList(
+ null).getClass();
+
+ public static <T> List<T> add(List<T> list, int index, T toAdd) {
+ switch (list.size()) {
+ case 0:
+ // Empty -> Singleton
+ if (index != 0) {
+ throw newIndexOutOfBounds(list, index);
+ }
+ return Collections.singletonList(toAdd);
+ case 1: {
+ // Singleton -> ArrayList
+ List<T> result = new ArrayList<T>(2);
+ switch (index) {
+ case 0:
+ result.add(toAdd);
+ result.add(list.get(0));
+ return result;
+ case 1:
+ result.add(list.get(0));
+ result.add(toAdd);
+ return result;
+ default:
+ throw newIndexOutOfBounds(list, index);
+ }
+ }
+ default:
+ // ArrayList
+ list.add(index, toAdd);
+ return list;
+ }
+ }
+
+ public static <T> List<T> add(List<T> list, T toAdd) {
+ switch (list.size()) {
+ case 0:
+ // Empty -> Singleton
+ return Collections.singletonList(toAdd);
+ case 1: {
+ // Singleton -> ArrayList
+ List<T> result = new ArrayList<T>(2);
+ result.add(list.get(0));
+ result.add(toAdd);
+ return result;
+ }
+ default:
+ // ArrayList
+ list.add(toAdd);
+ return list;
+ }
+ }
+
+ public static <T> List<T> addAll(List<T> list, int index, List<T> toAdd) {
+ switch (toAdd.size()) {
+ case 0:
+ // No-op.
+ return list;
+ case 1:
+ // Add one element.
+ return add(list, index, toAdd.get(0));
+ default:
+ // True list merge, result >= 2.
+ switch (list.size()) {
+ case 0:
+ if (index != 0) {
+ throw newIndexOutOfBounds(list, index);
+ }
+ return new ArrayList<T>(toAdd);
+ case 1: {
+ List<T> result = new ArrayList<T>(1 + toAdd.size());
+ switch (index) {
+ case 0:
+ result.addAll(toAdd);
+ result.add(list.get(0));
+ return result;
+ case 1:
+ result.add(list.get(0));
+ result.addAll(toAdd);
+ return result;
+ default:
+ throw newIndexOutOfBounds(list, index);
+ }
+ }
+ default:
+ list.addAll(index, toAdd);
+ return list;
+ }
+ }
+ }
+
+ public static <T> List<T> addAll(List<T> list, List<T> toAdd) {
+ switch (toAdd.size()) {
+ case 0:
+ // No-op.
+ return list;
+ case 1:
+ // Add one element.
+ return add(list, toAdd.get(0));
+ default:
+ // True list merge, result >= 2.
+ switch (list.size()) {
+ case 0:
+ return new ArrayList<T>(toAdd);
+ case 1: {
+ List<T> result = new ArrayList<T>(1 + toAdd.size());
+ result.add(list.get(0));
+ result.addAll(toAdd);
+ return result;
+ }
+ default:
+ list.addAll(toAdd);
+ return list;
+ }
+ }
+ }
+
+ public static <T> List<T> addAll(List<T> list, T... toAdd) {
+ switch (toAdd.length) {
+ case 0:
+ // No-op.
+ return list;
+ case 1:
+ // Add one element.
+ return add(list, toAdd[0]);
+ default:
+ // True list merge, result >= 2.
+ switch (list.size()) {
+ case 0:
+ return new ArrayList<T>(Arrays.asList(toAdd));
+ case 1: {
+ List<T> result = new ArrayList<T>(1 + toAdd.length);
+ result.add(list.get(0));
+ result.addAll(Arrays.asList(toAdd));
+ return result;
+ }
+ default:
+ list.addAll(Arrays.asList(toAdd));
+ return list;
+ }
+ }
+ }
+
+ public static <T> List<T> create() {
+ return Collections.emptyList();
+ }
+
+ public static <T> List<T> create(T item) {
+ return Collections.singletonList(item);
+ }
+
+ public static <T> List<T> create(T... items) {
+ switch (items.length) {
+ case 0:
+ return create();
+ case 1:
+ return create(items[0]);
+ default:
+ return new ArrayList<T>(Arrays.asList(items));
+ }
+ }
+
+ public static <T> List<T> normalize(List<T> list) {
+ switch (list.size()) {
+ case 0:
+ return create();
+ case 1: {
+ if (list.getClass() == SINGLETON_LIST_CLASS) {
+ return list;
+ }
+ return create(list.get(0));
+ }
+ default:
+ if (list.getClass() == MULTI_LIST_CLASS) {
+ return list;
+ }
+ return new ArrayList<T>(list);
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ public static <T> List<T> normalizeUnmodifiable(List<T> list) {
+ if (list.size() < 2) {
+ return normalize(list);
+ } else {
+ return (List<T>) Arrays.asList(list.toArray());
+ }
+ }
+
+ public static <T> List<T> remove(List<T> list, int toRemove) {
+ switch (list.size()) {
+ case 0:
+ // Empty
+ throw newIndexOutOfBounds(list, toRemove);
+ case 1:
+ // Singleton -> Empty
+ if (toRemove == 0) {
+ return Collections.emptyList();
+ } else {
+ throw newIndexOutOfBounds(list, toRemove);
+ }
+ case 2:
+ // ArrayList -> Singleton
+ switch (toRemove) {
+ case 0:
+ return Collections.singletonList(list.get(1));
+ case 1:
+ return Collections.singletonList(list.get(0));
+ default:
+ throw newIndexOutOfBounds(list, toRemove);
+ }
+ default:
+ // ArrayList
+ list.remove(toRemove);
+ return list;
+ }
+ }
+
+ public static <T> List<T> set(List<T> list, int index, T e) {
+ switch (list.size()) {
+ case 0:
+ // Empty
+ throw newIndexOutOfBounds(list, index);
+ case 1:
+ // Singleton
+ if (index == 0) {
+ return Collections.singletonList(e);
+ } else {
+ throw newIndexOutOfBounds(list, index);
+ }
+ default:
+ // ArrayList
+ list.set(index, e);
+ return list;
+ }
+ }
+
+ public static <T> List<T> sort(List<T> list, Comparator<? super T> sort) {
+ if (list.size() > 1) {
+ Collections.sort(list, sort);
+ }
+ return list;
+ }
+
+ private static <T> IndexOutOfBoundsException newIndexOutOfBounds(
+ List<T> list, int index) {
+ return new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ + list.size());
+ }
+}
diff --git a/dev/core/src/com/google/gwt/dev/util/collect/Maps.java b/dev/core/src/com/google/gwt/dev/util/collect/Maps.java
new file mode 100644
index 0000000..98fd25e
--- /dev/null
+++ b/dev/core/src/com/google/gwt/dev/util/collect/Maps.java
@@ -0,0 +1,145 @@
+/*
+ * Copyright 2009 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.dev.util.collect;
+
+import java.util.Collections;
+import java.util.Map;
+
+/**
+ * Utility methods for operating on memory-efficient maps. All maps of size 0 or
+ * 1 are assumed to be immutable. All maps of size greater than 1 are assumed to
+ * be mutable.
+ */
+public class Maps {
+
+ private static final Class<?> MULTI_MAP_CLASS = HashMap.class;
+ private static final Class<?> SINGLETON_MAP_CLASS = Collections.singletonMap(
+ null, null).getClass();
+
+ public static <K, V> Map<K, V> create() {
+ return Collections.emptyMap();
+ }
+
+ public static <K, V> Map<K, V> create(K key, V value) {
+ return Collections.singletonMap(key, value);
+ }
+
+ public static <K, V> Map<K, V> normalize(Map<K, V> map) {
+ switch (map.size()) {
+ case 0:
+ return create();
+ case 1: {
+ if (map.getClass() == SINGLETON_MAP_CLASS) {
+ return map;
+ }
+ K key = map.keySet().iterator().next();
+ return create(key, map.get(key));
+ }
+ default:
+ if (map.getClass() == MULTI_MAP_CLASS) {
+ return map;
+ }
+ return new HashMap<K, V>(map);
+ }
+ }
+
+ public static <K, V> Map<K, V> normalizeUnmodifiable(Map<K, V> map) {
+ if (map.size() < 2) {
+ return normalize(map);
+ } else {
+ // TODO: implement an UnmodifiableHashMap?
+ return Collections.unmodifiableMap(normalize(map));
+ }
+ }
+
+ public static <K, V> Map<K, V> put(Map<K, V> map, K key, V value) {
+ switch (map.size()) {
+ case 0:
+ // Empty -> Singleton
+ return Collections.singletonMap(key, value);
+ case 1: {
+ if (map.containsKey(key)) {
+ return create(key, value);
+ }
+ // Singleton -> HashMap
+ Map<K, V> result = new HashMap<K, V>();
+ result.put(map.keySet().iterator().next(),
+ map.values().iterator().next());
+ result.put(key, value);
+ return result;
+ }
+ default:
+ // HashMap
+ map.put(key, value);
+ return map;
+ }
+ }
+
+ public static <K, V> Map<K, V> putAll(Map<K, V> map, Map<K, V> toAdd) {
+ switch (toAdd.size()) {
+ case 0:
+ // No-op.
+ return map;
+ case 1: {
+ // Add one element.
+ K key = toAdd.keySet().iterator().next();
+ return put(map, key, toAdd.get(key));
+ }
+ default:
+ // True list merge, result >= 2.
+ switch (map.size()) {
+ case 0:
+ return new HashMap<K, V>(toAdd);
+ case 1: {
+ HashMap<K, V> result = new HashMap<K, V>();
+ K key = map.keySet().iterator().next();
+ result.put(key, map.get(key));
+ result.putAll(toAdd);
+ return normalize(result);
+ }
+ default:
+ map.putAll(toAdd);
+ return map;
+ }
+ }
+ }
+
+ public static <K, V> Map<K, V> remove(Map<K, V> map, K key) {
+ switch (map.size()) {
+ case 0:
+ // Empty
+ return map;
+ case 1:
+ // Singleton -> Empty
+ if (map.containsKey(key)) {
+ return create();
+ }
+ return map;
+ case 2:
+ // HashMap -> Singleton
+ if (map.containsKey(key)) {
+ map.remove(key);
+ key = map.keySet().iterator().next();
+ return create(key, map.get(key));
+ }
+ return map;
+ default:
+ // IdentityHashMap
+ map.remove(key);
+ return map;
+ }
+ }
+}
diff --git a/dev/core/src/com/google/gwt/dev/util/collect/Sets.java b/dev/core/src/com/google/gwt/dev/util/collect/Sets.java
new file mode 100644
index 0000000..be9006c
--- /dev/null
+++ b/dev/core/src/com/google/gwt/dev/util/collect/Sets.java
@@ -0,0 +1,127 @@
+/*
+ * Copyright 2009 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.dev.util.collect;
+
+import java.util.Collections;
+import java.util.Set;
+
+/**
+ * Utility methods for operating on memory-efficient sets. All sets of size 0 or
+ * 1 are assumed to be immutable. All sets of size greater than 1 are assumed to
+ * be mutable.
+ */
+public class Sets {
+
+ private static final Class<?> MULTI_SET_CLASS = HashSet.class;
+ private static final Class<?> SINGLETON_SET_CLASS = Collections.singleton(
+ null).getClass();
+
+ public static <T> Set<T> add(Set<T> set, T toAdd) {
+ switch (set.size()) {
+ case 0:
+ // Empty -> Singleton
+ return create(toAdd);
+ case 1: {
+ if (set.contains(toAdd)) {
+ return set;
+ }
+ // Singleton -> HashSet
+ Set<T> result = new HashSet<T>();
+ result.add(set.iterator().next());
+ result.add(toAdd);
+ return result;
+ }
+ default:
+ // HashSet
+ set.add(toAdd);
+ return set;
+ }
+ }
+
+ public static <T> Set<T> create() {
+ return Collections.emptySet();
+ }
+
+ public static <T> Set<T> create(T item) {
+ return Collections.singleton(item);
+ }
+
+ public static <T> Set<T> create(T... items) {
+ switch (items.length) {
+ case 0:
+ return create();
+ case 1:
+ return create(items[0]);
+ default:
+ HashSet<T> result = new HashSet<T>();
+ result.addAll(items);
+ return result;
+ }
+ }
+
+ public static <T> Set<T> normalize(Set<T> set) {
+ switch (set.size()) {
+ case 0:
+ return create();
+ case 1: {
+ if (set.getClass() == SINGLETON_SET_CLASS) {
+ return set;
+ }
+ return create(set.iterator().next());
+ }
+ default:
+ if (set.getClass() == MULTI_SET_CLASS) {
+ return set;
+ }
+ HashSet<T> result = new HashSet<T>();
+ result.addAll(set);
+ return result;
+ }
+ }
+
+ public static <T> Set<T> normalizeUnmodifiable(Set<T> set) {
+ if (set.size() < 2) {
+ return normalize(set);
+ } else {
+ // TODO: implement an UnmodifiableHashSet?
+ return Collections.unmodifiableSet(normalize(set));
+ }
+ }
+
+ public static <T> Set<T> remove(Set<T> set, T toRemove) {
+ switch (set.size()) {
+ case 0:
+ // Empty
+ return set;
+ case 1:
+ // Singleton -> Empty
+ if (set.contains(toRemove)) {
+ return create();
+ }
+ return set;
+ case 2:
+ // HashSet -> Singleton
+ if (set.remove(toRemove)) {
+ return create(set.iterator().next());
+ }
+ return set;
+ default:
+ // ArrayList
+ set.remove(toRemove);
+ return set;
+ }
+ }
+}
diff --git a/dev/core/test/com/google/gwt/dev/util/collect/HashMapTest.java b/dev/core/test/com/google/gwt/dev/util/collect/HashMapTest.java
new file mode 100644
index 0000000..6fad6c8
--- /dev/null
+++ b/dev/core/test/com/google/gwt/dev/util/collect/HashMapTest.java
@@ -0,0 +1,55 @@
+/*
+ * Copyright 2009 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.dev.util.collect;
+
+import org.apache.commons.collections.map.AbstractTestIterableMap;
+
+import java.util.Map;
+
+/**
+ * Test for {@link HashMap}.
+ */
+public class HashMapTest extends AbstractTestIterableMap {
+ public HashMapTest(String testName) {
+ super(testName);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public Map makeEmptyMap() {
+ return new HashMap();
+ }
+
+ @Override
+ public void testFailFastEntrySet() {
+ // Does not throw ConcurrentModificationException.
+ }
+
+ @Override
+ public void testFailFastKeySet() {
+ // Does not throw ConcurrentModificationException.
+ }
+
+ @Override
+ public void testFailFastValues() {
+ // Does not throw ConcurrentModificationException.
+ }
+
+ @Override
+ protected boolean skipSerializedCanonicalTests() {
+ return true;
+ }
+}
diff --git a/dev/core/test/com/google/gwt/dev/util/collect/HashSetTest.java b/dev/core/test/com/google/gwt/dev/util/collect/HashSetTest.java
new file mode 100644
index 0000000..0d7309b
--- /dev/null
+++ b/dev/core/test/com/google/gwt/dev/util/collect/HashSetTest.java
@@ -0,0 +1,40 @@
+/*
+ * Copyright 2009 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.dev.util.collect;
+
+import org.apache.commons.collections.set.AbstractTestSet;
+
+import java.util.Set;
+
+/**
+ * Test for {@link HashMap}.
+ */
+public class HashSetTest extends AbstractTestSet {
+ public HashSetTest(String testName) {
+ super(testName);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public Set makeEmptySet() {
+ return new HashSet();
+ }
+
+ @Override
+ protected boolean skipSerializedCanonicalTests() {
+ return true;
+ }
+}
diff --git a/dev/core/test/com/google/gwt/dev/util/collect/IdentityHashMapTest.java b/dev/core/test/com/google/gwt/dev/util/collect/IdentityHashMapTest.java
new file mode 100644
index 0000000..aa4398a
--- /dev/null
+++ b/dev/core/test/com/google/gwt/dev/util/collect/IdentityHashMapTest.java
@@ -0,0 +1,80 @@
+/*
+ * Copyright 2009 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.dev.util.collect;
+
+import junit.framework.Test;
+import junit.framework.TestSuite;
+
+import org.apache.commons.collections.map.TestIdentityMap;
+
+import java.util.Map;
+
+/**
+ * Test for {@link IdentityHashMap}.
+ */
+public class IdentityHashMapTest {
+
+ public static class HashMapExtTest extends HashMapTest {
+ public HashMapExtTest(String testName) {
+ super(testName);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public Map makeConfirmedMap() {
+ return new java.util.IdentityHashMap();
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public Map makeEmptyMap() {
+ return new IdentityHashMap();
+ }
+
+ @Override
+ protected boolean skipSerializedCanonicalTests() {
+ return true;
+ }
+ }
+
+ public static class IdentityMapExtTest extends TestIdentityMap {
+ public static Test suite() {
+ return new TestSuite(IdentityMapExtTest.class);
+ }
+
+ public IdentityMapExtTest(String testName) {
+ super(testName);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public Object makeObject() {
+ return new IdentityHashMap();
+ }
+
+ @Override
+ protected boolean skipSerializedCanonicalTests() {
+ return true;
+ }
+ }
+
+ public static Test suite() {
+ TestSuite suite = new TestSuite(IdentityHashMapTest.class.getName());
+ suite.addTestSuite(IdentityMapExtTest.class);
+ suite.addTestSuite(HashMapExtTest.class);
+ return suite;
+ }
+}
diff --git a/dev/core/test/com/google/gwt/dev/util/collect/IdentityHashSetTest.java b/dev/core/test/com/google/gwt/dev/util/collect/IdentityHashSetTest.java
new file mode 100644
index 0000000..b9fb4ef
--- /dev/null
+++ b/dev/core/test/com/google/gwt/dev/util/collect/IdentityHashSetTest.java
@@ -0,0 +1,99 @@
+/*
+ * Copyright 2009 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.dev.util.collect;
+
+import org.apache.commons.collections.set.AbstractTestSet;
+
+import java.util.AbstractSet;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Set;
+
+/**
+ * Test for {@link HashMap}.
+ */
+public class IdentityHashSetTest extends AbstractTestSet {
+ private static final Float FLOAT_6 = 6.0f;
+ private static final Double DOUBLE_5 = 5.0;
+
+ public IdentityHashSetTest(String testName) {
+ super(testName);
+ }
+
+ @Override
+ public boolean areEqualElementsDistinguishable() {
+ return true;
+ }
+
+ /**
+ * Must use stable identities.
+ */
+ @Override
+ public Object[] getFullNonNullElements() {
+ return new Object[] {
+ "", "One", 2, "Three", 4, "One", DOUBLE_5, FLOAT_6, "Seven", "Eight",
+ "Nine", 10, (short) 11, 12L, "Thirteen", "14", "15", (byte) 16};
+ }
+
+ /**
+ * Must use stable identities.
+ */
+ @Override
+ public Object[] getOtherNonNullElements() {
+ return new Object[] {
+ 0, 0f, 0.0, "Zero", (short) 0, (byte) 0, 0L, '\u0000', "0"};
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public Collection makeConfirmedCollection() {
+ final java.util.IdentityHashMap map = new java.util.IdentityHashMap();
+ return new AbstractSet() {
+ @Override
+ public boolean add(Object e) {
+ return map.put(e, e) == null;
+ }
+
+ @Override
+ public Iterator iterator() {
+ return map.keySet().iterator();
+ }
+
+ @Override
+ public int size() {
+ return map.size();
+ }
+ };
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public Set makeEmptySet() {
+ return new IdentityHashSet();
+ }
+
+ @Override
+ protected boolean skipSerializedCanonicalTests() {
+ return true;
+ }
+
+ /**
+ * This can't possible work due to non-stable identities.
+ */
+ @Override
+ public void testSerializeDeserializeThenCompare() throws Exception {
+ }
+}
diff --git a/dev/core/test/org/apache/commons/collections/AbstractTestObject.java b/dev/core/test/org/apache/commons/collections/AbstractTestObject.java
new file mode 100644
index 0000000..f0bdc20
--- /dev/null
+++ b/dev/core/test/org/apache/commons/collections/AbstractTestObject.java
@@ -0,0 +1,328 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.OutputStream;
+import java.io.Serializable;
+
+/**
+ * Abstract test class for {@link java.lang.Object} methods and contracts.
+ * <p>
+ * To use, simply extend this class, and implement
+ * the {@link #makeObject()} method.
+ * <p>
+ * If your {@link Object} fails one of these tests by design,
+ * you may still use this base set of cases. Simply override the
+ * test case (method) your {@link Object} fails.
+ *
+ * @version $Revision: 646780 $ $Date: 2008-04-10 13:48:07 +0100 (Thu, 10 Apr 2008) $
+ *
+ * @author Rodney Waldhoff
+ * @author Stephen Colebourne
+ * @author Anonymous
+ */
+public abstract class AbstractTestObject extends BulkTest {
+
+ /** Current major release for Collections */
+ public static final int COLLECTIONS_MAJOR_VERSION = 3;
+
+ /**
+ * JUnit constructor.
+ *
+ * @param testName the test class name
+ */
+ public AbstractTestObject(String testName) {
+ super(testName);
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Implement this method to return the object to test.
+ *
+ * @return the object to test
+ */
+ public abstract Object makeObject();
+
+ /**
+ * Override this method if a subclass is testing an object
+ * that cannot serialize an "empty" Collection.
+ * (e.g. Comparators have no contents)
+ *
+ * @return true
+ */
+ public boolean supportsEmptyCollections() {
+ return true;
+ }
+
+ /**
+ * Override this method if a subclass is testing an object
+ * that cannot serialize a "full" Collection.
+ * (e.g. Comparators have no contents)
+ *
+ * @return true
+ */
+ public boolean supportsFullCollections() {
+ return true;
+ }
+
+ /**
+ * Is serialization testing supported.
+ * Default is true.
+ */
+ public boolean isTestSerialization() {
+ return true;
+ }
+
+ /**
+ * Returns true to indicate that the collection supports equals() comparisons.
+ * This implementation returns true;
+ */
+ public boolean isEqualsCheckable() {
+ return true;
+ }
+
+ //-----------------------------------------------------------------------
+ public void testObjectEqualsSelf() {
+ Object obj = makeObject();
+ assertEquals("A Object should equal itself", obj, obj);
+ }
+
+ public void testEqualsNull() {
+ Object obj = makeObject();
+ assertEquals(false, obj.equals(null)); // make sure this doesn't throw NPE either
+ }
+
+ public void testObjectHashCodeEqualsSelfHashCode() {
+ Object obj = makeObject();
+ assertEquals("hashCode should be repeatable", obj.hashCode(), obj.hashCode());
+ }
+
+ public void testObjectHashCodeEqualsContract() {
+ Object obj1 = makeObject();
+ if (obj1.equals(obj1)) {
+ assertEquals(
+ "[1] When two objects are equal, their hashCodes should be also.",
+ obj1.hashCode(), obj1.hashCode());
+ }
+ Object obj2 = makeObject();
+ if (obj1.equals(obj2)) {
+ assertEquals(
+ "[2] When two objects are equal, their hashCodes should be also.",
+ obj1.hashCode(), obj2.hashCode());
+ assertTrue(
+ "When obj1.equals(obj2) is true, then obj2.equals(obj1) should also be true",
+ obj2.equals(obj1));
+ }
+ }
+
+ public void testSerializeDeserializeThenCompare() throws Exception {
+ Object obj = makeObject();
+ if (obj instanceof Serializable && isTestSerialization()) {
+ ByteArrayOutputStream buffer = new ByteArrayOutputStream();
+ ObjectOutputStream out = new ObjectOutputStream(buffer);
+ out.writeObject(obj);
+ out.close();
+
+ ObjectInputStream in = new ObjectInputStream(new ByteArrayInputStream(buffer.toByteArray()));
+ Object dest = in.readObject();
+ in.close();
+ if (isEqualsCheckable()) {
+ assertEquals("obj != deserialize(serialize(obj))", obj, dest);
+ }
+ }
+ }
+
+ /**
+ * Sanity check method, makes sure that any Serializable
+ * class can be serialized and de-serialized in memory,
+ * using the handy makeObject() method
+ *
+ * @throws IOException
+ * @throws ClassNotFoundException
+ */
+ public void testSimpleSerialization() throws Exception {
+ Object o = makeObject();
+ if (o instanceof Serializable && isTestSerialization()) {
+ byte[] objekt = writeExternalFormToBytes((Serializable) o);
+ Object p = readExternalFormFromBytes(objekt);
+ }
+ }
+
+ /**
+ * Tests serialization by comparing against a previously stored version in CVS.
+ * If the test object is serializable, confirm that a canonical form exists.
+ */
+ public void testCanonicalEmptyCollectionExists() {
+ if (supportsEmptyCollections() && isTestSerialization() && !skipSerializedCanonicalTests()) {
+ Object object = makeObject();
+ if (object instanceof Serializable) {
+ String name = getCanonicalEmptyCollectionName(object);
+ assertTrue(
+ "Canonical empty collection (" + name + ") is not in CVS",
+ new File(name).exists());
+ }
+ }
+ }
+
+ /**
+ * Tests serialization by comparing against a previously stored version in CVS.
+ * If the test object is serializable, confirm that a canonical form exists.
+ */
+ public void testCanonicalFullCollectionExists() {
+ if (supportsFullCollections() && isTestSerialization() && !skipSerializedCanonicalTests()) {
+ Object object = makeObject();
+ if (object instanceof Serializable) {
+ String name = getCanonicalFullCollectionName(object);
+ assertTrue(
+ "Canonical full collection (" + name + ") is not in CVS",
+ new File(name).exists());
+ }
+ }
+ }
+
+ // protected implementation
+ //-----------------------------------------------------------------------
+ /**
+ * Get the version of Collections that this object tries to
+ * maintain serialization compatibility with. Defaults to 1, the
+ * earliest Collections version. (Note: some collections did not
+ * even exist in this version).
+ *
+ * This constant makes it possible for TestMap (and other subclasses,
+ * if necessary) to automatically check CVS for a versionX copy of a
+ * Serialized object, so we can make sure that compatibility is maintained.
+ * See, for example, TestMap.getCanonicalFullMapName(Map map).
+ * Subclasses can override this variable, indicating compatibility
+ * with earlier Collections versions.
+ *
+ * @return The version, or <code>null</code> if this object shouldn't be
+ * tested for compatibility with previous versions.
+ */
+ public String getCompatibilityVersion() {
+ return "1";
+ }
+
+ protected String getCanonicalEmptyCollectionName(Object object) {
+ StringBuffer retval = new StringBuffer();
+ retval.append("data/test/");
+ String colName = object.getClass().getName();
+ colName = colName.substring(colName.lastIndexOf(".") + 1, colName.length());
+ retval.append(colName);
+ retval.append(".emptyCollection.version");
+ retval.append(getCompatibilityVersion());
+ retval.append(".obj");
+ return retval.toString();
+ }
+
+ protected String getCanonicalFullCollectionName(Object object) {
+ StringBuffer retval = new StringBuffer();
+ retval.append("data/test/");
+ String colName = object.getClass().getName();
+ colName = colName.substring(colName.lastIndexOf(".") + 1, colName.length());
+ retval.append(colName);
+ retval.append(".fullCollection.version");
+ retval.append(getCompatibilityVersion());
+ retval.append(".obj");
+ return retval.toString();
+ }
+
+ /**
+ * Write a Serializable or Externalizable object as
+ * a file at the given path. NOT USEFUL as part
+ * of a unit test; this is just a utility method
+ * for creating disk-based objects in CVS that can become
+ * the basis for compatibility tests using
+ * readExternalFormFromDisk(String path)
+ *
+ * @param o Object to serialize
+ * @param path path to write the serialized Object
+ * @exception IOException
+ */
+ protected void writeExternalFormToDisk(Serializable o, String path) throws IOException {
+ FileOutputStream fileStream = new FileOutputStream(path);
+ writeExternalFormToStream(o, fileStream);
+ }
+
+ /**
+ * Converts a Serializable or Externalizable object to
+ * bytes. Useful for in-memory tests of serialization
+ *
+ * @param o Object to convert to bytes
+ * @return serialized form of the Object
+ * @exception IOException
+ */
+ protected byte[] writeExternalFormToBytes(Serializable o) throws IOException {
+ ByteArrayOutputStream byteStream = new ByteArrayOutputStream();
+ writeExternalFormToStream(o, byteStream);
+ return byteStream.toByteArray();
+ }
+
+ /**
+ * Reads a Serialized or Externalized Object from disk.
+ * Useful for creating compatibility tests between
+ * different CVS versions of the same class
+ *
+ * @param path path to the serialized Object
+ * @return the Object at the given path
+ * @exception IOException
+ * @exception ClassNotFoundException
+ */
+ protected Object readExternalFormFromDisk(String path) throws IOException, ClassNotFoundException {
+ FileInputStream stream = new FileInputStream(path);
+ return readExternalFormFromStream(stream);
+ }
+
+ /**
+ * Read a Serialized or Externalized Object from bytes.
+ * Useful for verifying serialization in memory.
+ *
+ * @param b byte array containing a serialized Object
+ * @return Object contained in the bytes
+ * @exception IOException
+ * @exception ClassNotFoundException
+ */
+ protected Object readExternalFormFromBytes(byte[] b) throws IOException, ClassNotFoundException {
+ ByteArrayInputStream stream = new ByteArrayInputStream(b);
+ return readExternalFormFromStream(stream);
+ }
+
+ protected boolean skipSerializedCanonicalTests() {
+ return Boolean.getBoolean("org.apache.commons.collections:with-clover");
+ }
+
+ // private implementation
+ //-----------------------------------------------------------------------
+ private Object readExternalFormFromStream(InputStream stream) throws IOException, ClassNotFoundException {
+ ObjectInputStream oStream = new ObjectInputStream(stream);
+ return oStream.readObject();
+ }
+
+ private void writeExternalFormToStream(Serializable o, OutputStream stream) throws IOException {
+ ObjectOutputStream oStream = new ObjectOutputStream(stream);
+ oStream.writeObject(o);
+ }
+
+}
diff --git a/dev/core/test/org/apache/commons/collections/BulkTest.java b/dev/core/test/org/apache/commons/collections/BulkTest.java
new file mode 100644
index 0000000..0d9e1ba
--- /dev/null
+++ b/dev/core/test/org/apache/commons/collections/BulkTest.java
@@ -0,0 +1,462 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.lang.reflect.Constructor;
+import java.lang.reflect.InvocationTargetException;
+import java.lang.reflect.Method;
+import java.lang.reflect.Modifier;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+import junit.framework.TestCase;
+import junit.framework.TestSuite;
+
+/**
+ * A {@link TestCase} that can define both simple and bulk test methods.
+ * <p>
+ * A <I>simple test method</I> is the type of test traditionally
+ * supplied by by {@link TestCase}. To define a simple test, create a public
+ * no-argument method whose name starts with "test". You can specify the
+ * the name of simple test in the constructor of <code>BulkTest</code>;
+ * a subsequent call to {@link TestCase#run} will run that simple test.
+ * <p>
+ * A <I>bulk test method</I>, on the other hand, returns a new instance
+ * of <code>BulkTest</code>, which can itself define new simple and bulk
+ * test methods. By using the {@link #makeSuite} method, you can
+ * automatically create a hierarchal suite of tests and child bulk tests.
+ * <p>
+ * For instance, consider the following two classes:
+ *
+ * <Pre>
+ * public class TestSet extends BulkTest {
+ *
+ * private Set set;
+ *
+ * public TestSet(Set set) {
+ * this.set = set;
+ * }
+ *
+ * public void testContains() {
+ * boolean r = set.contains(set.iterator().next()));
+ * assertTrue("Set should contain first element, r);
+ * }
+ *
+ * public void testClear() {
+ * set.clear();
+ * assertTrue("Set should be empty after clear", set.isEmpty());
+ * }
+ * }
+ *
+ *
+ * public class TestHashMap extends BulkTest {
+ *
+ * private Map makeFullMap() {
+ * HashMap result = new HashMap();
+ * result.put("1", "One");
+ * result.put("2", "Two");
+ * return result;
+ * }
+ *
+ * public void testClear() {
+ * Map map = makeFullMap();
+ * map.clear();
+ * assertTrue("Map empty after clear", map.isEmpty());
+ * }
+ *
+ * public BulkTest bulkTestKeySet() {
+ * return new TestSet(makeFullMap().keySet());
+ * }
+ *
+ * public BulkTest bulkTestEntrySet() {
+ * return new TestSet(makeFullMap().entrySet());
+ * }
+ * }
+ * </Pre>
+ *
+ * In the above examples, <code>TestSet</code> defines two
+ * simple test methods and no bulk test methods; <code>TestHashMap</code>
+ * defines one simple test method and two bulk test methods. When
+ * <code>makeSuite(TestHashMap.class).run</code> is executed,
+ * <I>five</I> simple test methods will be run, in this order:<P>
+ *
+ * <Ol>
+ * <Li>TestHashMap.testClear()
+ * <Li>TestHashMap.bulkTestKeySet().testContains();
+ * <Li>TestHashMap.bulkTestKeySet().testClear();
+ * <Li>TestHashMap.bulkTestEntrySet().testContains();
+ * <Li>TestHashMap.bulkTestEntrySet().testClear();
+ * </Ol>
+ *
+ * In the graphical junit test runners, the tests would be displayed in
+ * the following tree:<P>
+ *
+ * <UL>
+ * <LI>TestHashMap</LI>
+ * <UL>
+ * <LI>testClear
+ * <LI>bulkTestKeySet
+ * <UL>
+ * <LI>testContains
+ * <LI>testClear
+ * </UL>
+ * <LI>bulkTestEntrySet
+ * <UL>
+ * <LI>testContains
+ * <LI>testClear
+ * </UL>
+ * </UL>
+ * </UL>
+ *
+ * A subclass can override a superclass's bulk test by
+ * returning <code>null</code> from the bulk test method. If you only
+ * want to override specific simple tests within a bulk test, use the
+ * {@link #ignoredTests} method.<P>
+ *
+ * Note that if you want to use the bulk test methods, you <I>must</I>
+ * define your <code>suite()</code> method to use {@link #makeSuite}.
+ * The ordinary {@link TestSuite} constructor doesn't know how to
+ * interpret bulk test methods.
+ *
+ * @author Paul Jack
+ * @version $Id: BulkTest.java 646780 2008-04-10 12:48:07Z niallp $
+ */
+public class BulkTest extends TestCase implements Cloneable {
+
+
+ // Note: BulkTest is Cloneable to make it easier to construct
+ // BulkTest instances for simple test methods that are defined in
+ // anonymous inner classes. Basically we don't have to worry about
+ // finding weird constructors. (And even if we found them, technically
+ // it'd be illegal for anyone but the outer class to invoke them).
+ // Given one BulkTest instance, we can just clone it and reset the
+ // method name for every simple test it defines.
+
+
+ /**
+ * The full name of this bulk test instance. This is the full name
+ * that is compared to {@link #ignoredTests} to see if this
+ * test should be ignored. It's also displayed in the text runner
+ * to ease debugging.
+ */
+ String verboseName;
+
+
+ /**
+ * Constructs a new <code>BulkTest</code> instance that will run the
+ * specified simple test.
+ *
+ * @param name the name of the simple test method to run
+ */
+ public BulkTest(String name) {
+ super(name);
+ this.verboseName = getClass().getName();
+ }
+
+
+ /**
+ * Creates a clone of this <code>BulkTest</code>.<P>
+ *
+ * @return a clone of this <code>BulkTest</code>
+ */
+ public Object clone() {
+ try {
+ return super.clone();
+ } catch (CloneNotSupportedException e) {
+ throw new Error(); // should never happen
+ }
+ }
+
+
+ /**
+ * Returns an array of test names to ignore.<P>
+ *
+ * If a test that's defined by this <code>BulkTest</code> or
+ * by one of its bulk test methods has a name that's in the returned
+ * array, then that simple test will not be executed.<P>
+ *
+ * A test's name is formed by taking the class name of the
+ * root <code>BulkTest</code>, eliminating the package name, then
+ * appending the names of any bulk test methods that were invoked
+ * to get to the simple test, and then appending the simple test
+ * method name. The method names are delimited by periods:
+ *
+ * <pre>
+ * TestHashMap.bulkTestEntrySet.testClear
+ * </pre>
+ *
+ * is the name of one of the simple tests defined in the sample classes
+ * described above. If the sample <code>TestHashMap</code> class
+ * included this method:
+ *
+ * <pre>
+ * public String[] ignoredTests() {
+ * return new String[] { "TestHashMap.bulkTestEntrySet.testClear" };
+ * }
+ * </pre>
+ *
+ * then the entry set's clear method wouldn't be tested, but the key
+ * set's clear method would.
+ *
+ * @return an array of the names of tests to ignore, or null if
+ * no tests should be ignored
+ */
+ public String[] ignoredTests() {
+ return null;
+ }
+
+
+ /**
+ * Returns the display name of this <code>BulkTest</code>.
+ *
+ * @return the display name of this <code>BulkTest</code>
+ */
+ public String toString() {
+ return getName() + "(" + verboseName + ") ";
+ }
+
+
+ /**
+ * Returns a {@link TestSuite} for testing all of the simple tests
+ * <I>and</I> all the bulk tests defined by the given class.<P>
+ *
+ * The class is examined for simple and bulk test methods; any child
+ * bulk tests are also examined recursively; and the results are stored
+ * in a hierarchal {@link TestSuite}.<P>
+ *
+ * The given class must be a subclass of <code>BulkTest</code> and must
+ * not be abstract.<P>
+ *
+ * @param c the class to examine for simple and bulk tests
+ * @return a {@link TestSuite} containing all the simple and bulk tests
+ * defined by that class
+ */
+ public static TestSuite makeSuite(Class c) {
+ if (Modifier.isAbstract(c.getModifiers())) {
+ throw new IllegalArgumentException("Class must not be abstract.");
+ }
+ if (!BulkTest.class.isAssignableFrom(c)) {
+ throw new IllegalArgumentException("Class must extend BulkTest.");
+ }
+ return new BulkTestSuiteMaker(c).make();
+ }
+
+}
+
+
+// It was easier to use a separate class to do all the reflection stuff
+// for making the TestSuite instances. Having permanent state around makes
+// it easier to handle the recursion.
+class BulkTestSuiteMaker {
+
+ /** The class that defines simple and bulk tests methods. */
+ private Class startingClass;
+
+ /** List of ignored simple test names. */
+ private List ignored;
+
+ /** The TestSuite we're currently populating. Can change over time. */
+ private TestSuite result;
+
+ /**
+ * The prefix for simple test methods. Used to check if a test is in
+ * the ignored list.
+ */
+ private String prefix;
+
+ /**
+ * Constructor.
+ *
+ * @param startingClass the starting class
+ */
+ public BulkTestSuiteMaker(Class startingClass) {
+ this.startingClass = startingClass;
+ }
+
+ /**
+ * Makes a hierarchal TestSuite based on the starting class.
+ *
+ * @return the hierarchal TestSuite for startingClass
+ */
+ public TestSuite make() {
+ this.result = new TestSuite();
+ this.prefix = getBaseName(startingClass);
+ result.setName(prefix);
+
+ BulkTest bulk = makeFirstTestCase(startingClass);
+ ignored = new ArrayList();
+ String[] s = bulk.ignoredTests();
+ if (s != null) {
+ ignored.addAll(Arrays.asList(s));
+ }
+ make(bulk);
+ return result;
+ }
+
+ /**
+ * Appends all the simple tests and bulk tests defined by the given
+ * instance's class to the current TestSuite.
+ *
+ * @param bulk An instance of the class that defines simple and bulk
+ * tests for us to append
+ */
+ void make(BulkTest bulk) {
+ Class c = bulk.getClass();
+ Method[] all = c.getMethods();
+ for (int i = 0; i < all.length; i++) {
+ if (isTest(all[i])) addTest(bulk, all[i]);
+ if (isBulk(all[i])) addBulk(bulk, all[i]);
+ }
+ }
+
+ /**
+ * Adds the simple test defined by the given method to the TestSuite.
+ *
+ * @param bulk The instance of the class that defined the method
+ * (I know it's weird. But the point is, we can clone the instance
+ * and not have to worry about constructors.)
+ * @param m The simple test method
+ */
+ void addTest(BulkTest bulk, Method m) {
+ BulkTest bulk2 = (BulkTest)bulk.clone();
+ bulk2.setName(m.getName());
+ bulk2.verboseName = prefix + "." + m.getName();
+ if (ignored.contains(bulk2.verboseName)) return;
+ result.addTest(bulk2);
+ }
+
+ /**
+ * Adds a whole new suite of tests that are defined by the result of
+ * the given bulk test method. In other words, the given bulk test
+ * method is invoked, and the resulting BulkTest instance is examined
+ * for yet more simple and bulk tests.
+ *
+ * @param bulk The instance of the class that defined the method
+ * @param m The bulk test method
+ */
+ void addBulk(BulkTest bulk, Method m) {
+ String verboseName = prefix + "." + m.getName();
+ if (ignored.contains(verboseName)) return;
+
+ BulkTest bulk2;
+ try {
+ bulk2 = (BulkTest)m.invoke(bulk, (Object[]) null);
+ if (bulk2 == null) return;
+ } catch (InvocationTargetException ex) {
+ ex.getTargetException().printStackTrace();
+ throw new Error(); // FIXME;
+ } catch (IllegalAccessException ex) {
+ ex.printStackTrace();
+ throw new Error(); // FIXME;
+ }
+
+ // Save current state on the stack.
+ String oldPrefix = prefix;
+ TestSuite oldResult = result;
+
+ prefix = prefix + "." + m.getName();
+ result = new TestSuite();
+ result.setName(m.getName());
+
+ make(bulk2);
+
+ oldResult.addTest(result);
+
+ // Restore the old state
+ prefix = oldPrefix;
+ result = oldResult;
+ }
+
+ /**
+ * Returns the base name of the given class.
+ *
+ * @param c the class
+ * @return the name of that class, minus any package names
+ */
+ private static String getBaseName(Class c) {
+ String name = c.getName();
+ int p = name.lastIndexOf('.');
+ if (p > 0) {
+ name = name.substring(p + 1);
+ }
+ return name;
+ }
+
+
+ // These three methods are used to create a valid BulkTest instance
+ // from a class.
+
+ private static Constructor getTestCaseConstructor(Class c) {
+ try {
+ return c.getConstructor(new Class[] { String.class });
+ } catch (NoSuchMethodException e) {
+ throw new IllegalArgumentException(c + " must provide " +
+ "a (String) constructor");
+ }
+ }
+
+ private static BulkTest makeTestCase(Class c, Method m) {
+ Constructor con = getTestCaseConstructor(c);
+ try {
+ return (BulkTest)con.newInstance(new Object[] {m.getName()});
+ } catch (InvocationTargetException e) {
+ e.printStackTrace();
+ throw new RuntimeException(); // FIXME;
+ } catch (IllegalAccessException e) {
+ throw new Error(); // should never occur
+ } catch (InstantiationException e) {
+ throw new RuntimeException(); // FIXME;
+ }
+ }
+
+ private static BulkTest makeFirstTestCase(Class c) {
+ Method[] all = c.getMethods();
+ for (int i = 0; i < all.length; i++) {
+ if (isTest(all[i])) return makeTestCase(c, all[i]);
+ }
+ throw new IllegalArgumentException(c.getName() + " must provide "
+ + " at least one test method.");
+ }
+
+ /**
+ * Returns true if the given method is a simple test method.
+ */
+ private static boolean isTest(Method m) {
+ if (!m.getName().startsWith("test")) return false;
+ if (m.getReturnType() != Void.TYPE) return false;
+ if (m.getParameterTypes().length != 0) return false;
+ int mods = m.getModifiers();
+ if (Modifier.isStatic(mods)) return false;
+ if (Modifier.isAbstract(mods)) return false;
+ return true;
+ }
+
+ /**
+ * Returns true if the given method is a bulk test method.
+ */
+ private static boolean isBulk(Method m) {
+ if (!m.getName().startsWith("bulkTest")) return false;
+ if (m.getReturnType() != BulkTest.class) return false;
+ if (m.getParameterTypes().length != 0) return false;
+ int mods = m.getModifiers();
+ if (Modifier.isStatic(mods)) return false;
+ if (Modifier.isAbstract(mods)) return false;
+ return true;
+ }
+
+}
diff --git a/dev/core/test/org/apache/commons/collections/collection/AbstractTestCollection.java b/dev/core/test/org/apache/commons/collections/collection/AbstractTestCollection.java
new file mode 100644
index 0000000..1c01b53
--- /dev/null
+++ b/dev/core/test/org/apache/commons/collections/collection/AbstractTestCollection.java
@@ -0,0 +1,1333 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.collection;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+import java.lang.reflect.Array;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.ConcurrentModificationException;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NoSuchElementException;
+
+import org.apache.commons.collections.AbstractTestObject;
+
+/**
+ * Abstract test class for {@link java.util.Collection} methods and contracts.
+ * <p>
+ * You should create a concrete subclass of this class to test any custom
+ * {@link Collection} implementation. At minimum, you'll have to
+ * implement the {@link #makeCollection()} method. You might want to
+ * override some of the additional public methods as well:
+ * <p>
+ * <b>Element Population Methods</b>
+ * <p>
+ * Override these if your collection restricts what kind of elements are
+ * allowed (for instance, if <code>null</code> is not permitted):
+ * <ul>
+ * <li>{@link #getFullElements()}
+ * <li>{@link #getOtherElements()}
+ * </ul>
+ * <p>
+ * <b>Supported Operation Methods</b>
+ * <p>
+ * Override these if your collection doesn't support certain operations:
+ * <ul>
+ * <li>{@link #isAddSupported()}
+ * <li>{@link #isRemoveSupported()}
+ * <li>{@link #areEqualElementsDistinguishable()}
+ * <li>{@link #isNullSupported()}
+ * <li>{@link #isFailFastSupported()}
+ * </ul>
+ * <p>
+ * <b>Fixture Methods</b>
+ * <p>
+ * Fixtures are used to verify that the the operation results in correct state
+ * for the collection. Basically, the operation is performed against your
+ * collection implementation, and an identical operation is performed against a
+ * <i>confirmed</i> collection implementation. A confirmed collection
+ * implementation is something like <code>java.util.ArrayList</code>, which is
+ * known to conform exactly to its collection interface's contract. After the
+ * operation takes place on both your collection implementation and the
+ * confirmed collection implementation, the two collections are compared to see
+ * if their state is identical. The comparison is usually much more involved
+ * than a simple <code>equals</code> test. This verification is used to ensure
+ * proper modifications are made along with ensuring that the collection does
+ * not change when read-only modifications are made.
+ * <p>
+ * The {@link #collection} field holds an instance of your collection
+ * implementation; the {@link #confirmed} field holds an instance of the
+ * confirmed collection implementation. The {@link #resetEmpty()} and
+ * {@link #resetFull()} methods set these fields to empty or full collections,
+ * so that tests can proceed from a known state.
+ * <p>
+ * After a modification operation to both {@link #collection} and
+ * {@link #confirmed}, the {@link #verify()} method is invoked to compare
+ * the results. You may want to override {@link #verify()} to perform
+ * additional verifications. For instance, when testing the collection
+ * views of a map, {@link AbstractTestMap} would override {@link #verify()} to make
+ * sure the map is changed after the collection view is changed.
+ * <p>
+ * If you're extending this class directly, you will have to provide
+ * implementations for the following:
+ * <ul>
+ * <li>{@link #makeConfirmedCollection()}
+ * <li>{@link #makeConfirmedFullCollection()}
+ * </ul>
+ * <p>
+ * Those methods should provide a confirmed collection implementation
+ * that's compatible with your collection implementation.
+ * <p>
+ * If you're extending {@link AbstractTestList}, {@link AbstractTestSet},
+ * or {@link AbstractTestBag}, you probably don't have to worry about the
+ * above methods, because those three classes already override the methods
+ * to provide standard JDK confirmed collections.<P>
+ * <p>
+ * <b>Other notes</b>
+ * <p>
+ * If your {@link Collection} fails one of these tests by design,
+ * you may still use this base set of cases. Simply override the
+ * test case (method) your {@link Collection} fails.
+ *
+ * @version $Revision: 646780 $ $Date: 2008-04-10 13:48:07 +0100 (Thu, 10 Apr 2008) $
+ *
+ * @author Rodney Waldhoff
+ * @author Paul Jack
+ * @author Michael A. Smith
+ * @author Neil O'Toole
+ * @author Stephen Colebourne
+ */
+public abstract class AbstractTestCollection extends AbstractTestObject {
+
+ //
+ // NOTE:
+ //
+ // Collection doesn't define any semantics for equals, and recommends you
+ // use reference-based default behavior of Object.equals. (And a test for
+ // that already exists in AbstractTestObject). Tests for equality of lists, sets
+ // and bags will have to be written in test subclasses. Thus, there is no
+ // tests on Collection.equals nor any for Collection.hashCode.
+ //
+
+
+ // These fields are used by reset() and verify(), and any test
+ // method that tests a modification.
+
+ /**
+ * A collection instance that will be used for testing.
+ */
+ public Collection collection;
+
+ /**
+ * Confirmed collection. This is an instance of a collection that is
+ * confirmed to conform exactly to the java.util.Collection contract.
+ * Modification operations are tested by performing a mod on your
+ * collection, performing the exact same mod on an equivalent confirmed
+ * collection, and then calling verify() to make sure your collection
+ * still matches the confirmed collection.
+ */
+ public Collection confirmed;
+
+ /**
+ * JUnit constructor.
+ *
+ * @param testName the test class name
+ */
+ public AbstractTestCollection(String testName) {
+ super(testName);
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Specifies whether equal elements in the collection are, in fact,
+ * distinguishable with information not readily available. That is, if a
+ * particular value is to be removed from the collection, then there is
+ * one and only one value that can be removed, even if there are other
+ * elements which are equal to it.
+ *
+ * <P>In most collection cases, elements are not distinguishable (equal is
+ * equal), thus this method defaults to return false. In some cases,
+ * however, they are. For example, the collection returned from the map's
+ * values() collection view are backed by the map, so while there may be
+ * two values that are equal, their associated keys are not. Since the
+ * keys are distinguishable, the values are.
+ *
+ * <P>This flag is used to skip some verifications for iterator.remove()
+ * where it is impossible to perform an equivalent modification on the
+ * confirmed collection because it is not possible to determine which
+ * value in the confirmed collection to actually remove. Tests that
+ * override the default (i.e. where equal elements are distinguishable),
+ * should provide additional tests on iterator.remove() to make sure the
+ * proper elements are removed when remove() is called on the iterator.
+ **/
+ public boolean areEqualElementsDistinguishable() {
+ return false;
+ }
+
+ /**
+ * Returns true if the collections produced by
+ * {@link #makeCollection()} and {@link #makeFullCollection()}
+ * support the <code>add</code> and <code>addAll</code>
+ * operations.<P>
+ * Default implementation returns true. Override if your collection
+ * class does not support add or addAll.
+ */
+ public boolean isAddSupported() {
+ return true;
+ }
+
+ /**
+ * Returns true if the collections produced by
+ * {@link #makeCollection()} and {@link #makeFullCollection()}
+ * support the <code>remove</code>, <code>removeAll</code>,
+ * <code>retainAll</code>, <code>clear</code> and
+ * <code>iterator().remove()</code> methods.
+ * Default implementation returns true. Override if your collection
+ * class does not support removal operations.
+ */
+ public boolean isRemoveSupported() {
+ return true;
+ }
+
+ /**
+ * Returns true to indicate that the collection supports holding null.
+ * The default implementation returns true;
+ */
+ public boolean isNullSupported() {
+ return true;
+ }
+
+ /**
+ * Returns true to indicate that the collection supports fail fast iterators.
+ * The default implementation returns true;
+ */
+ public boolean isFailFastSupported() {
+ return false;
+ }
+
+ /**
+ * Returns true to indicate that the collection supports equals() comparisons.
+ * This implementation returns false;
+ */
+ public boolean isEqualsCheckable() {
+ return false;
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Verifies that {@link #collection} and {@link #confirmed} have
+ * identical state.
+ */
+ public void verify() {
+ int confirmedSize = confirmed.size();
+ assertEquals("Collection size should match confirmed collection's",
+ confirmedSize, collection.size());
+ assertEquals("Collection isEmpty() result should match confirmed " +
+ " collection's",
+ confirmed.isEmpty(), collection.isEmpty());
+
+ // verify the collections are the same by attempting to match each
+ // object in the collection and confirmed collection. To account for
+ // duplicates and differing orders, each confirmed element is copied
+ // into an array and a flag is maintained for each element to determine
+ // whether it has been matched once and only once. If all elements in
+ // the confirmed collection are matched once and only once and there
+ // aren't any elements left to be matched in the collection,
+ // verification is a success.
+
+ // copy each collection value into an array
+ Object[] confirmedValues = new Object[confirmedSize];
+
+ Iterator iter;
+
+ iter = confirmed.iterator();
+ int pos = 0;
+ while(iter.hasNext()) {
+ confirmedValues[pos++] = iter.next();
+ }
+
+ // allocate an array of boolean flags for tracking values that have
+ // been matched once and only once.
+ boolean[] matched = new boolean[confirmedSize];
+
+ // now iterate through the values of the collection and try to match
+ // the value with one in the confirmed array.
+ iter = collection.iterator();
+ while(iter.hasNext()) {
+ Object o = iter.next();
+ boolean match = false;
+ for(int i = 0; i < confirmedSize; i++) {
+ if(matched[i]) {
+ // skip values already matched
+ continue;
+ }
+ if(o == confirmedValues[i] ||
+ (o != null && o.equals(confirmedValues[i]))) {
+ // values matched
+ matched[i] = true;
+ match = true;
+ break;
+ }
+ }
+ // no match found!
+ if(!match) {
+ fail("Collection should not contain a value that the " +
+ "confirmed collection does not have: " + o +
+ "\nTest: " + collection + "\nReal: " + confirmed);
+ }
+ }
+
+ // make sure there aren't any unmatched values
+ for(int i = 0; i < confirmedSize; i++) {
+ if(!matched[i]) {
+ // the collection didn't match all the confirmed values
+ fail("Collection should contain all values that are in the confirmed collection" +
+ "\nTest: " + collection + "\nReal: " + confirmed);
+ }
+ }
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Resets the {@link #collection} and {@link #confirmed} fields to empty
+ * collections. Invoke this method before performing a modification
+ * test.
+ */
+ public void resetEmpty() {
+ this.collection = makeCollection();
+ this.confirmed = makeConfirmedCollection();
+ }
+
+ /**
+ * Resets the {@link #collection} and {@link #confirmed} fields to full
+ * collections. Invoke this method before performing a modification
+ * test.
+ */
+ public void resetFull() {
+ this.collection = makeFullCollection();
+ this.confirmed = makeConfirmedFullCollection();
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Returns a confirmed empty collection.
+ * For instance, an {@link java.util.ArrayList} for lists or a
+ * {@link java.util.HashSet} for sets.
+ *
+ * @return a confirmed empty collection
+ */
+ public abstract Collection makeConfirmedCollection();
+
+ /**
+ * Returns a confirmed full collection.
+ * For instance, an {@link java.util.ArrayList} for lists or a
+ * {@link java.util.HashSet} for sets. The returned collection
+ * should contain the elements returned by {@link #getFullElements()}.
+ *
+ * @return a confirmed full collection
+ */
+ public abstract Collection makeConfirmedFullCollection();
+
+ /**
+ * Return a new, empty {@link Collection} to be used for testing.
+ */
+ public abstract Collection makeCollection();
+
+ /**
+ * Returns a full collection to be used for testing. The collection
+ * returned by this method should contain every element returned by
+ * {@link #getFullElements()}. The default implementation, in fact,
+ * simply invokes <code>addAll</code> on an empty collection with
+ * the results of {@link #getFullElements()}. Override this default
+ * if your collection doesn't support addAll.
+ */
+ public Collection makeFullCollection() {
+ Collection c = makeCollection();
+ c.addAll(Arrays.asList(getFullElements()));
+ return c;
+ }
+
+ /**
+ * Returns an empty collection for Object tests.
+ */
+ public Object makeObject() {
+ return makeCollection();
+ }
+
+ /**
+ * Creates a new Map Entry that is independent of the first and the map.
+ */
+ public Map.Entry cloneMapEntry(Map.Entry entry) {
+ HashMap map = new HashMap();
+ map.put(entry.getKey(), entry.getValue());
+ return (Map.Entry) map.entrySet().iterator().next();
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Returns an array of objects that are contained in a collection
+ * produced by {@link #makeFullCollection()}. Every element in the
+ * returned array <I>must</I> be an element in a full collection.<P>
+ * The default implementation returns a heterogenous array of
+ * objects with some duplicates. null is added if allowed.
+ * Override if you require specific testing elements. Note that if you
+ * override {@link #makeFullCollection()}, you <I>must</I> override
+ * this method to reflect the contents of a full collection.
+ */
+ public Object[] getFullElements() {
+ if (isNullSupported()) {
+ ArrayList list = new ArrayList();
+ list.addAll(Arrays.asList(getFullNonNullElements()));
+ list.add(4, null);
+ return list.toArray();
+ } else {
+ return (Object[]) getFullNonNullElements().clone();
+ }
+ }
+
+ /**
+ * Returns an array of elements that are <I>not</I> contained in a
+ * full collection. Every element in the returned array must
+ * not exist in a collection returned by {@link #makeFullCollection()}.
+ * The default implementation returns a heterogenous array of elements
+ * without null. Note that some of the tests add these elements
+ * to an empty or full collection, so if your collection restricts
+ * certain kinds of elements, you should override this method.
+ */
+ public Object[] getOtherElements() {
+ return getOtherNonNullElements();
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Returns a list of elements suitable for return by
+ * {@link #getFullElements()}. The array returned by this method
+ * does not include null, but does include a variety of objects
+ * of different types. Override getFullElements to return
+ * the results of this method if your collection does not support
+ * the null element.
+ */
+ public Object[] getFullNonNullElements() {
+ return new Object[] {
+ new String(""),
+ new String("One"),
+ new Integer(2),
+ "Three",
+ new Integer(4),
+ "One",
+ new Double(5),
+ new Float(6),
+ "Seven",
+ "Eight",
+ new String("Nine"),
+ new Integer(10),
+ new Short((short)11),
+ new Long(12),
+ "Thirteen",
+ "14",
+ "15",
+ new Byte((byte)16)
+ };
+ }
+
+ /**
+ * Returns the default list of objects returned by
+ * {@link #getOtherElements()}. Includes many objects
+ * of different types.
+ */
+ public Object[] getOtherNonNullElements() {
+ return new Object[] {
+ new Integer(0),
+ new Float(0),
+ new Double(0),
+ "Zero",
+ new Short((short)0),
+ new Byte((byte)0),
+ new Long(0),
+ new Character('\u0000'),
+ "0"
+ };
+ }
+
+ /**
+ * Returns a list of string elements suitable for return by
+ * {@link #getFullElements()}. Override getFullElements to return
+ * the results of this method if your collection does not support
+ * heterogenous elements or the null element.
+ */
+ public Object[] getFullNonNullStringElements() {
+ return new Object[] {
+ "If","the","dull","substance","of","my","flesh","were","thought",
+ "Injurious","distance","could","not","stop","my","way",
+ };
+ }
+
+ /**
+ * Returns a list of string elements suitable for return by
+ * {@link #getOtherElements()}. Override getOtherElements to return
+ * the results of this method if your collection does not support
+ * heterogenous elements or the null element.
+ */
+ public Object[] getOtherNonNullStringElements() {
+ return new Object[] {
+ "For","then","despite",/* of */"space","I","would","be","brought",
+ "From","limits","far","remote","where","thou","dost","stay"
+ };
+ }
+
+ // Tests
+ //-----------------------------------------------------------------------
+ /**
+ * Tests {@link Collection#add(Object)}.
+ */
+ public void testCollectionAdd() {
+ if (!isAddSupported()) return;
+
+ Object[] elements = getFullElements();
+ for (int i = 0; i < elements.length; i++) {
+ resetEmpty();
+ boolean r = collection.add(elements[i]);
+ confirmed.add(elements[i]);
+ verify();
+ assertTrue("Empty collection changed after add", r);
+ assertEquals("Collection size is 1 after first add", 1, collection.size());
+ }
+
+ resetEmpty();
+ int size = 0;
+ for (int i = 0; i < elements.length; i++) {
+ boolean r = collection.add(elements[i]);
+ confirmed.add(elements[i]);
+ verify();
+ if (r) size++;
+ assertEquals("Collection size should grow after add",
+ size, collection.size());
+ assertTrue("Collection should contain added element",
+ collection.contains(elements[i]));
+ }
+ }
+
+
+ /**
+ * Tests {@link Collection#addAll(Collection)}.
+ */
+ public void testCollectionAddAll() {
+ if (!isAddSupported()) return;
+
+ resetEmpty();
+ Object[] elements = getFullElements();
+ boolean r = collection.addAll(Arrays.asList(elements));
+ confirmed.addAll(Arrays.asList(elements));
+ verify();
+ assertTrue("Empty collection should change after addAll", r);
+ for (int i = 0; i < elements.length; i++) {
+ assertTrue("Collection should contain added element",
+ collection.contains(elements[i]));
+ }
+
+ resetFull();
+ int size = collection.size();
+ elements = getOtherElements();
+ r = collection.addAll(Arrays.asList(elements));
+ confirmed.addAll(Arrays.asList(elements));
+ verify();
+ assertTrue("Full collection should change after addAll", r);
+ for (int i = 0; i < elements.length; i++) {
+ assertTrue("Full collection should contain added element",
+ collection.contains(elements[i]));
+ }
+ assertEquals("Size should increase after addAll",
+ size + elements.length, collection.size());
+
+ resetFull();
+ size = collection.size();
+ r = collection.addAll(Arrays.asList(getFullElements()));
+ confirmed.addAll(Arrays.asList(getFullElements()));
+ verify();
+ if (r) {
+ assertTrue("Size should increase if addAll returns true",
+ size < collection.size());
+ } else {
+ assertEquals("Size should not change if addAll returns false",
+ size, collection.size());
+ }
+ }
+
+
+ /**
+ * If {@link #isAddSupported()} returns false, tests that add operations
+ * raise <code>UnsupportedOperationException.
+ */
+ public void testUnsupportedAdd() {
+ if (isAddSupported()) return;
+
+ resetEmpty();
+ try {
+ collection.add(new Object());
+ fail("Emtpy collection should not support add.");
+ } catch (UnsupportedOperationException e) {
+ // expected
+ }
+ // make sure things didn't change even if the expected exception was
+ // thrown.
+ verify();
+
+ try {
+ collection.addAll(Arrays.asList(getFullElements()));
+ fail("Emtpy collection should not support addAll.");
+ } catch (UnsupportedOperationException e) {
+ // expected
+ }
+ // make sure things didn't change even if the expected exception was
+ // thrown.
+ verify();
+
+ resetFull();
+ try {
+ collection.add(new Object());
+ fail("Full collection should not support add.");
+ } catch (UnsupportedOperationException e) {
+ // expected
+ }
+ // make sure things didn't change even if the expected exception was
+ // thrown.
+ verify();
+
+ try {
+ collection.addAll(Arrays.asList(getOtherElements()));
+ fail("Full collection should not support addAll.");
+ } catch (UnsupportedOperationException e) {
+ // expected
+ }
+ // make sure things didn't change even if the expected exception was
+ // thrown.
+ verify();
+ }
+
+
+ /**
+ * Test {@link Collection#clear()}.
+ */
+ public void testCollectionClear() {
+ if (!isRemoveSupported()) return;
+
+ resetEmpty();
+ collection.clear(); // just to make sure it doesn't raise anything
+ verify();
+
+ resetFull();
+ collection.clear();
+ confirmed.clear();
+ verify();
+ }
+
+
+ /**
+ * Tests {@link Collection#contains(Object)}.
+ */
+ public void testCollectionContains() {
+ Object[] elements;
+
+ resetEmpty();
+ elements = getFullElements();
+ for(int i = 0; i < elements.length; i++) {
+ assertTrue("Empty collection shouldn't contain element[" + i + "]",
+ !collection.contains(elements[i]));
+ }
+ // make sure calls to "contains" don't change anything
+ verify();
+
+ elements = getOtherElements();
+ for(int i = 0; i < elements.length; i++) {
+ assertTrue("Empty collection shouldn't contain element[" + i + "]",
+ !collection.contains(elements[i]));
+ }
+ // make sure calls to "contains" don't change anything
+ verify();
+
+ resetFull();
+ elements = getFullElements();
+ for(int i = 0; i < elements.length; i++) {
+ assertTrue("Full collection should contain element[" + i + "]",
+ collection.contains(elements[i]));
+ }
+ // make sure calls to "contains" don't change anything
+ verify();
+
+ resetFull();
+ elements = getOtherElements();
+ for(int i = 0; i < elements.length; i++) {
+ assertTrue("Full collection shouldn't contain element",
+ !collection.contains(elements[i]));
+ }
+ }
+
+
+ /**
+ * Tests {@link Collection#containsAll(Collection)}.
+ */
+ public void testCollectionContainsAll() {
+ resetEmpty();
+ Collection col = new HashSet();
+ assertTrue("Every Collection should contain all elements of an " +
+ "empty Collection.", collection.containsAll(col));
+ col.addAll(Arrays.asList(getOtherElements()));
+ assertTrue("Empty Collection shouldn't contain all elements of " +
+ "a non-empty Collection.", !collection.containsAll(col));
+ // make sure calls to "containsAll" don't change anything
+ verify();
+
+ resetFull();
+ assertTrue("Full collection shouldn't contain other elements",
+ !collection.containsAll(col));
+
+ col.clear();
+ col.addAll(Arrays.asList(getFullElements()));
+ assertTrue("Full collection should containAll full elements",
+ collection.containsAll(col));
+ // make sure calls to "containsAll" don't change anything
+ verify();
+
+ int min = (getFullElements().length < 2 ? 0 : 2);
+ int max = (getFullElements().length == 1 ? 1 :
+ (getFullElements().length <= 5 ? getFullElements().length - 1 : 5));
+ col = Arrays.asList(getFullElements()).subList(min, max);
+ assertTrue("Full collection should containAll partial full " +
+ "elements", collection.containsAll(col));
+ assertTrue("Full collection should containAll itself",
+ collection.containsAll(collection));
+ // make sure calls to "containsAll" don't change anything
+ verify();
+
+ col = new ArrayList();
+ col.addAll(Arrays.asList(getFullElements()));
+ col.addAll(Arrays.asList(getFullElements()));
+ assertTrue("Full collection should containAll duplicate full " +
+ "elements", collection.containsAll(col));
+
+ // make sure calls to "containsAll" don't change anything
+ verify();
+ }
+
+ /**
+ * Tests {@link Collection#isEmpty()}.
+ */
+ public void testCollectionIsEmpty() {
+ resetEmpty();
+ assertEquals("New Collection should be empty.",
+ true, collection.isEmpty());
+ // make sure calls to "isEmpty() don't change anything
+ verify();
+
+ resetFull();
+ assertEquals("Full collection shouldn't be empty",
+ false, collection.isEmpty());
+ // make sure calls to "isEmpty() don't change anything
+ verify();
+ }
+
+
+ /**
+ * Tests the read-only functionality of {@link Collection#iterator()}.
+ */
+ public void testCollectionIterator() {
+ resetEmpty();
+ Iterator it1 = collection.iterator();
+ assertEquals("Iterator for empty Collection shouldn't have next.",
+ false, it1.hasNext());
+ try {
+ it1.next();
+ fail("Iterator at end of Collection should throw " +
+ "NoSuchElementException when next is called.");
+ } catch(NoSuchElementException e) {
+ // expected
+ }
+ // make sure nothing has changed after non-modification
+ verify();
+
+ resetFull();
+ it1 = collection.iterator();
+ for (int i = 0; i < collection.size(); i++) {
+ assertTrue("Iterator for full collection should haveNext",
+ it1.hasNext());
+ it1.next();
+ }
+ assertTrue("Iterator should be finished", !it1.hasNext());
+
+ ArrayList list = new ArrayList();
+ it1 = collection.iterator();
+ for (int i = 0; i < collection.size(); i++) {
+ Object next = it1.next();
+ assertTrue("Collection should contain element returned by " +
+ "its iterator", collection.contains(next));
+ list.add(next);
+ }
+ try {
+ it1.next();
+ fail("iterator.next() should raise NoSuchElementException " +
+ "after it finishes");
+ } catch (NoSuchElementException e) {
+ // expected
+ }
+ // make sure nothing has changed after non-modification
+ verify();
+ }
+
+
+ /**
+ * Tests removals from {@link Collection#iterator()}.
+ */
+ public void testCollectionIteratorRemove() {
+ if (!isRemoveSupported()) return;
+
+ resetEmpty();
+ try {
+ collection.iterator().remove();
+ fail("New iterator.remove should raise IllegalState");
+ } catch (IllegalStateException e) {
+ // expected
+ }
+ verify();
+
+ try {
+ Iterator iter = collection.iterator();
+ iter.hasNext();
+ iter.remove();
+ fail("New iterator.remove should raise IllegalState " +
+ "even after hasNext");
+ } catch (IllegalStateException e) {
+ // expected
+ }
+ verify();
+
+ resetFull();
+ int size = collection.size();
+ Iterator iter = collection.iterator();
+ while (iter.hasNext()) {
+ Object o = iter.next();
+ // TreeMap reuses the Map Entry, so the verify below fails
+ // Clone it here if necessary
+ if (o instanceof Map.Entry) {
+ o = cloneMapEntry((Map.Entry) o);
+ }
+ iter.remove();
+
+ // if the elements aren't distinguishable, we can just remove a
+ // matching element from the confirmed collection and verify
+ // contents are still the same. Otherwise, we don't have the
+ // ability to distinguish the elements and determine which to
+ // remove from the confirmed collection (in which case, we don't
+ // verify because we don't know how).
+ //
+ // see areEqualElementsDistinguishable()
+ if(!areEqualElementsDistinguishable()) {
+ confirmed.remove(o);
+ verify();
+ }
+
+ size--;
+ assertEquals("Collection should shrink by one after " +
+ "iterator.remove", size, collection.size());
+ }
+ assertTrue("Collection should be empty after iterator purge",
+ collection.isEmpty());
+
+ resetFull();
+ iter = collection.iterator();
+ iter.next();
+ iter.remove();
+ try {
+ iter.remove();
+ fail("Second iter.remove should raise IllegalState");
+ } catch (IllegalStateException e) {
+ // expected
+ }
+ }
+
+
+ /**
+ * Tests {@link Collection#remove(Object)}.
+ */
+ public void testCollectionRemove() {
+ if (!isRemoveSupported()) return;
+
+ resetEmpty();
+ Object[] elements = getFullElements();
+ for (int i = 0; i < elements.length; i++) {
+ assertTrue("Shouldn't remove nonexistent element",
+ !collection.remove(elements[i]));
+ verify();
+ }
+
+ Object[] other = getOtherElements();
+
+ resetFull();
+ for (int i = 0; i < other.length; i++) {
+ assertTrue("Shouldn't remove nonexistent other element",
+ !collection.remove(other[i]));
+ verify();
+ }
+
+ int size = collection.size();
+ for (int i = 0; i < elements.length; i++) {
+ resetFull();
+ assertTrue("Collection should remove extant element: " + elements[i],
+ collection.remove(elements[i]));
+
+ // if the elements aren't distinguishable, we can just remove a
+ // matching element from the confirmed collection and verify
+ // contents are still the same. Otherwise, we don't have the
+ // ability to distinguish the elements and determine which to
+ // remove from the confirmed collection (in which case, we don't
+ // verify because we don't know how).
+ //
+ // see areEqualElementsDistinguishable()
+ if(!areEqualElementsDistinguishable()) {
+ confirmed.remove(elements[i]);
+ verify();
+ }
+
+ assertEquals("Collection should shrink after remove",
+ size - 1, collection.size());
+ }
+ }
+
+
+ /**
+ * Tests {@link Collection#removeAll(Collection)}.
+ */
+ public void testCollectionRemoveAll() {
+ if (!isRemoveSupported()) return;
+
+ resetEmpty();
+ assertTrue("Emtpy collection removeAll should return false for " +
+ "empty input",
+ !collection.removeAll(Collections.EMPTY_SET));
+ verify();
+
+ assertTrue("Emtpy collection removeAll should return false for " +
+ "nonempty input",
+ !collection.removeAll(new ArrayList(collection)));
+ verify();
+
+ resetFull();
+ assertTrue("Full collection removeAll should return false for " +
+ "empty input",
+ !collection.removeAll(Collections.EMPTY_SET));
+ verify();
+
+ assertTrue("Full collection removeAll should return false for other elements",
+ !collection.removeAll(Arrays.asList(getOtherElements())));
+ verify();
+
+ assertTrue("Full collection removeAll should return true for full elements",
+ collection.removeAll(new HashSet(collection)));
+ confirmed.removeAll(new HashSet(confirmed));
+ verify();
+
+ resetFull();
+ int size = collection.size();
+ int min = (getFullElements().length < 2 ? 0 : 2);
+ int max = (getFullElements().length == 1 ? 1 :
+ (getFullElements().length <= 5 ? getFullElements().length - 1 : 5));
+ Collection all = Arrays.asList(getFullElements()).subList(min, max);
+ assertTrue("Full collection removeAll should work",
+ collection.removeAll(all));
+ confirmed.removeAll(all);
+ verify();
+
+ assertTrue("Collection should shrink after removeAll",
+ collection.size() < size);
+ Iterator iter = all.iterator();
+ while (iter.hasNext()) {
+ assertTrue("Collection shouldn't contain removed element",
+ !collection.contains(iter.next()));
+ }
+ }
+
+
+ /**
+ * Tests {@link Collection#retainAll(Collection)}.
+ */
+ public void testCollectionRetainAll() {
+ if (!isRemoveSupported()) return;
+
+ resetEmpty();
+ List elements = Arrays.asList(getFullElements());
+ List other = Arrays.asList(getOtherElements());
+
+ assertTrue("Empty retainAll() should return false",
+ !collection.retainAll(Collections.EMPTY_SET));
+ verify();
+
+ assertTrue("Empty retainAll() should return false",
+ !collection.retainAll(elements));
+ verify();
+
+ resetFull();
+ assertTrue("Collection should change from retainAll empty",
+ collection.retainAll(Collections.EMPTY_SET));
+ confirmed.retainAll(Collections.EMPTY_SET);
+ verify();
+
+ resetFull();
+ assertTrue("Collection changed from retainAll other",
+ collection.retainAll(other));
+ confirmed.retainAll(other);
+ verify();
+
+ resetFull();
+ int size = collection.size();
+ assertTrue("Collection shouldn't change from retainAll elements",
+ !collection.retainAll(elements));
+ verify();
+ assertEquals("Collection size shouldn't change", size,
+ collection.size());
+
+ if (getFullElements().length > 1) {
+ resetFull();
+ size = collection.size();
+ int min = (getFullElements().length < 2 ? 0 : 2);
+ int max = (getFullElements().length <= 5 ? getFullElements().length - 1 : 5);
+ assertTrue("Collection should changed by partial retainAll",
+ collection.retainAll(elements.subList(min, max)));
+ confirmed.retainAll(elements.subList(min, max));
+ verify();
+
+ Iterator iter = collection.iterator();
+ while (iter.hasNext()) {
+ assertTrue("Collection only contains retained element",
+ elements.subList(min, max).contains(iter.next()));
+ }
+ }
+
+ resetFull();
+ HashSet set = new HashSet(elements);
+ size = collection.size();
+ assertTrue("Collection shouldn't change from retainAll without " +
+ "duplicate elements", !collection.retainAll(set));
+ verify();
+ assertEquals("Collection size didn't change from nonduplicate " +
+ "retainAll", size, collection.size());
+ }
+
+
+ /**
+ * Tests {@link Collection#size()}.
+ */
+ public void testCollectionSize() {
+ resetEmpty();
+ assertEquals("Size of new Collection is 0.", 0, collection.size());
+
+ resetFull();
+ assertTrue("Size of full collection should be greater than zero",
+ collection.size() > 0);
+ }
+
+
+ /**
+ * Tests {@link Collection#toArray()}.
+ */
+ public void testCollectionToArray() {
+ resetEmpty();
+ assertEquals("Empty Collection should return empty array for toArray",
+ 0, collection.toArray().length);
+
+ resetFull();
+ Object[] array = collection.toArray();
+ assertEquals("Full collection toArray should be same size as " +
+ "collection", array.length, collection.size());
+ Object[] confirmedArray = confirmed.toArray();
+ assertEquals("length of array from confirmed collection should " +
+ "match the length of the collection's array",
+ confirmedArray.length, array.length);
+ boolean[] matched = new boolean[array.length];
+
+ for (int i = 0; i < array.length; i++) {
+ assertTrue("Collection should contain element in toArray",
+ collection.contains(array[i]));
+
+ boolean match = false;
+ // find a match in the confirmed array
+ for(int j = 0; j < array.length; j++) {
+ // skip already matched
+ if(matched[j]) continue;
+ if(array[i] == confirmedArray[j] ||
+ (array[i] != null && array[i].equals(confirmedArray[j]))) {
+ matched[j] = true;
+ match = true;
+ break;
+ }
+ }
+ if(!match) {
+ fail("element " + i + " in returned array should be found " +
+ "in the confirmed collection's array");
+ }
+ }
+ for(int i = 0; i < matched.length; i++) {
+ assertEquals("Collection should return all its elements in " +
+ "toArray", true, matched[i]);
+ }
+ }
+
+
+ /**
+ * Tests {@link Collection#toArray(Object[])}.
+ */
+ public void testCollectionToArray2() {
+ resetEmpty();
+ Object[] a = new Object[] { new Object(), null, null };
+ Object[] array = collection.toArray(a);
+ assertEquals("Given array shouldn't shrink", array, a);
+ assertEquals("Last element should be set to null", a[0], null);
+ verify();
+
+ resetFull();
+ try {
+ array = collection.toArray(new Void[0]);
+ fail("toArray(new Void[0]) should raise ArrayStore");
+ } catch (ArrayStoreException e) {
+ // expected
+ }
+ verify();
+
+ try {
+ array = collection.toArray(null);
+ fail("toArray(null) should raise NPE");
+ } catch (NullPointerException e) {
+ // expected
+ }
+ verify();
+
+ array = collection.toArray(new Object[0]);
+ a = collection.toArray();
+ assertEquals("toArrays should be equal",
+ Arrays.asList(array), Arrays.asList(a));
+
+ // Figure out if they're all the same class
+ // TODO: It'd be nicer to detect a common superclass
+ HashSet classes = new HashSet();
+ for (int i = 0; i < array.length; i++) {
+ classes.add((array[i] == null) ? null : array[i].getClass());
+ }
+ if (classes.size() > 1) return;
+
+ Class cl = (Class)classes.iterator().next();
+ if (Map.Entry.class.isAssignableFrom(cl)) { // check needed for protective cases like Predicated/Unmod map entrySet
+ cl = Map.Entry.class;
+ }
+ a = (Object[])Array.newInstance(cl, 0);
+ array = collection.toArray(a);
+ assertEquals("toArray(Object[]) should return correct array type",
+ a.getClass(), array.getClass());
+ assertEquals("type-specific toArrays should be equal",
+ Arrays.asList(array),
+ Arrays.asList(collection.toArray()));
+ verify();
+ }
+
+
+ /**
+ * Tests <code>toString</code> on a collection.
+ */
+ public void testCollectionToString() {
+ resetEmpty();
+ assertTrue("toString shouldn't return null",
+ collection.toString() != null);
+
+ resetFull();
+ assertTrue("toString shouldn't return null",
+ collection.toString() != null);
+ }
+
+
+ /**
+ * If isRemoveSupported() returns false, tests to see that remove
+ * operations raise an UnsupportedOperationException.
+ */
+ public void testUnsupportedRemove() {
+ if (isRemoveSupported()) return;
+
+ resetEmpty();
+ try {
+ collection.clear();
+ fail("clear should raise UnsupportedOperationException");
+ } catch (UnsupportedOperationException e) {
+ // expected
+ }
+ verify();
+
+ try {
+ collection.remove(null);
+ fail("remove should raise UnsupportedOperationException");
+ } catch (UnsupportedOperationException e) {
+ // expected
+ }
+ verify();
+
+ try {
+ collection.removeAll(null);
+ fail("removeAll should raise UnsupportedOperationException");
+ } catch (UnsupportedOperationException e) {
+ // expected
+ }
+ verify();
+
+ try {
+ collection.retainAll(null);
+ fail("removeAll should raise UnsupportedOperationException");
+ } catch (UnsupportedOperationException e) {
+ // expected
+ }
+ verify();
+
+ resetFull();
+ try {
+ Iterator iterator = collection.iterator();
+ iterator.next();
+ iterator.remove();
+ fail("iterator.remove should raise UnsupportedOperationException");
+ } catch (UnsupportedOperationException e) {
+ // expected
+ }
+ verify();
+
+ }
+
+
+ /**
+ * Tests that the collection's iterator is fail-fast.
+ */
+ public void testCollectionIteratorFailFast() {
+ if (!isFailFastSupported()) return;
+
+ if (isAddSupported()) {
+ resetFull();
+ try {
+ Iterator iter = collection.iterator();
+ Object o = getOtherElements()[0];
+ collection.add(o);
+ confirmed.add(o);
+ iter.next();
+ fail("next after add should raise ConcurrentModification");
+ } catch (ConcurrentModificationException e) {
+ // expected
+ }
+ verify();
+
+ resetFull();
+ try {
+ Iterator iter = collection.iterator();
+ collection.addAll(Arrays.asList(getOtherElements()));
+ confirmed.addAll(Arrays.asList(getOtherElements()));
+ iter.next();
+ fail("next after addAll should raise ConcurrentModification");
+ } catch (ConcurrentModificationException e) {
+ // expected
+ }
+ verify();
+ }
+
+ if (!isRemoveSupported()) return;
+
+ resetFull();
+ try {
+ Iterator iter = collection.iterator();
+ collection.clear();
+ iter.next();
+ fail("next after clear should raise ConcurrentModification");
+ } catch (ConcurrentModificationException e) {
+ // expected
+ } catch (NoSuchElementException e) {
+ // (also legal given spec)
+ }
+
+ resetFull();
+ try {
+ Iterator iter = collection.iterator();
+ collection.remove(getFullElements()[0]);
+ iter.next();
+ fail("next after remove should raise ConcurrentModification");
+ } catch (ConcurrentModificationException e) {
+ // expected
+ }
+
+ resetFull();
+ try {
+ Iterator iter = collection.iterator();
+ List sublist = Arrays.asList(getFullElements()).subList(2,5);
+ collection.removeAll(sublist);
+ iter.next();
+ fail("next after removeAll should raise ConcurrentModification");
+ } catch (ConcurrentModificationException e) {
+ // expected
+ }
+
+ resetFull();
+ try {
+ Iterator iter = collection.iterator();
+ List sublist = Arrays.asList(getFullElements()).subList(2,5);
+ collection.retainAll(sublist);
+ iter.next();
+ fail("next after retainAll should raise ConcurrentModification");
+ } catch (ConcurrentModificationException e) {
+ // expected
+ }
+ }
+
+ public void testSerializeDeserializeThenCompare() throws Exception {
+ Object obj = makeCollection();
+ if (obj instanceof Serializable && isTestSerialization()) {
+ ByteArrayOutputStream buffer = new ByteArrayOutputStream();
+ ObjectOutputStream out = new ObjectOutputStream(buffer);
+ out.writeObject(obj);
+ out.close();
+
+ ObjectInputStream in = new ObjectInputStream(new ByteArrayInputStream(buffer.toByteArray()));
+ Object dest = in.readObject();
+ in.close();
+ if (isEqualsCheckable()) {
+ assertEquals("obj != deserialize(serialize(obj)) - EMPTY Collection", obj, dest);
+ }
+ }
+ obj = makeFullCollection();
+ if (obj instanceof Serializable && isTestSerialization()) {
+ ByteArrayOutputStream buffer = new ByteArrayOutputStream();
+ ObjectOutputStream out = new ObjectOutputStream(buffer);
+ out.writeObject(obj);
+ out.close();
+
+ ObjectInputStream in = new ObjectInputStream(new ByteArrayInputStream(buffer.toByteArray()));
+ Object dest = in.readObject();
+ in.close();
+ if (isEqualsCheckable()) {
+ assertEquals("obj != deserialize(serialize(obj)) - FULL Collection", obj, dest);
+ }
+ }
+ }
+
+}
diff --git a/dev/core/test/org/apache/commons/collections/iterators/AbstractTestIterator.java b/dev/core/test/org/apache/commons/collections/iterators/AbstractTestIterator.java
new file mode 100644
index 0000000..9422ad5
--- /dev/null
+++ b/dev/core/test/org/apache/commons/collections/iterators/AbstractTestIterator.java
@@ -0,0 +1,203 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.iterators;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+import org.apache.commons.collections.AbstractTestObject;
+
+/**
+ * Abstract class for testing the Iterator interface.
+ * <p>
+ * This class provides a framework for testing an implementation of Iterator.
+ * Concrete subclasses must provide the iterator to be tested.
+ * They must also specify certain details of how the iterator operates by
+ * overriding the supportsXxx() methods if necessary.
+ *
+ * @since Commons Collections 3.0
+ * @version $Revision: 646780 $ $Date: 2008-04-10 13:48:07 +0100 (Thu, 10 Apr 2008) $
+ *
+ * @author Morgan Delagrange
+ * @author Stephen Colebourne
+ */
+public abstract class AbstractTestIterator extends AbstractTestObject {
+
+ /**
+ * JUnit constructor.
+ *
+ * @param testName the test class name
+ */
+ public AbstractTestIterator(String testName) {
+ super(testName);
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Implement this method to return an iterator over an empty collection.
+ *
+ * @return an empty iterator
+ */
+ public abstract Iterator makeEmptyIterator();
+
+ /**
+ * Implement this method to return an iterator over a collection with elements.
+ *
+ * @return a full iterator
+ */
+ public abstract Iterator makeFullIterator();
+
+ /**
+ * Implements the abstract superclass method to return the full iterator.
+ *
+ * @return a full iterator
+ */
+ public Object makeObject() {
+ return makeFullIterator();
+ }
+
+ /**
+ * Whether or not we are testing an iterator that can be empty.
+ * Default is true.
+ *
+ * @return true if Iterator can be empty
+ */
+ public boolean supportsEmptyIterator() {
+ return true;
+ }
+
+ /**
+ * Whether or not we are testing an iterator that can contain elements.
+ * Default is true.
+ *
+ * @return true if Iterator can be full
+ */
+ public boolean supportsFullIterator() {
+ return true;
+ }
+
+ /**
+ * Whether or not we are testing an iterator that supports remove().
+ * Default is true.
+ *
+ * @return true if Iterator supports remove
+ */
+ public boolean supportsRemove() {
+ return true;
+ }
+
+ /**
+ * Allows subclasses to add complex cross verification
+ */
+ public void verify() {
+ // do nothing
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Test the empty iterator.
+ */
+ public void testEmptyIterator() {
+ if (supportsEmptyIterator() == false) {
+ return;
+ }
+
+ Iterator it = makeEmptyIterator();
+
+ // hasNext() should return false
+ assertEquals("hasNext() should return false for empty iterators", false, it.hasNext());
+
+ // next() should throw a NoSuchElementException
+ try {
+ it.next();
+ fail("NoSuchElementException must be thrown when Iterator is exhausted");
+ } catch (NoSuchElementException e) {
+ }
+ verify();
+
+ assertNotNull(it.toString());
+ }
+
+ /**
+ * Test normal iteration behaviour.
+ */
+ public void testFullIterator() {
+ if (supportsFullIterator() == false) {
+ return;
+ }
+
+ Iterator it = makeFullIterator();
+
+ // hasNext() must be true (ensure makeFullIterator is correct!)
+ assertEquals("hasNext() should return true for at least one element", true, it.hasNext());
+
+ // next() must not throw exception (ensure makeFullIterator is correct!)
+ try {
+ it.next();
+ } catch (NoSuchElementException e) {
+ fail("Full iterators must have at least one element");
+ }
+
+ // iterate through
+ while (it.hasNext()) {
+ it.next();
+ verify();
+ }
+
+ // next() must throw NoSuchElementException now
+ try {
+ it.next();
+ fail("NoSuchElementException must be thrown when Iterator is exhausted");
+ } catch (NoSuchElementException e) {
+ }
+
+ assertNotNull(it.toString());
+ }
+
+ /**
+ * Test remove behaviour.
+ */
+ public void testRemove() {
+ Iterator it = makeFullIterator();
+
+ if (supportsRemove() == false) {
+ // check for UnsupportedOperationException if not supported
+ try {
+ it.remove();
+ } catch (UnsupportedOperationException ex) {}
+ return;
+ }
+
+ // should throw IllegalStateException before next() called
+ try {
+ it.remove();
+ fail();
+ } catch (IllegalStateException ex) {}
+ verify();
+
+ // remove after next should be fine
+ it.next();
+ it.remove();
+
+ // should throw IllegalStateException for second remove()
+ try {
+ it.remove();
+ fail();
+ } catch (IllegalStateException ex) {}
+ }
+
+}
diff --git a/dev/core/test/org/apache/commons/collections/iterators/AbstractTestMapIterator.java b/dev/core/test/org/apache/commons/collections/iterators/AbstractTestMapIterator.java
new file mode 100644
index 0000000..b2acfd1
--- /dev/null
+++ b/dev/core/test/org/apache/commons/collections/iterators/AbstractTestMapIterator.java
@@ -0,0 +1,355 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.iterators;
+
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+import org.apache.commons.collections.MapIterator;
+
+/**
+ * Abstract class for testing the MapIterator interface.
+ * <p>
+ * This class provides a framework for testing an implementation of MapIterator.
+ * Concrete subclasses must provide the list iterator to be tested.
+ * They must also specify certain details of how the list iterator operates by
+ * overriding the supportsXxx() methods if necessary.
+ *
+ * @since Commons Collections 3.0
+ * @version $Revision: 646780 $ $Date: 2008-04-10 13:48:07 +0100 (Thu, 10 Apr 2008) $
+ *
+ * @author Stephen Colebourne
+ */
+public abstract class AbstractTestMapIterator extends AbstractTestIterator {
+
+ /**
+ * JUnit constructor.
+ *
+ * @param testName the test class name
+ */
+ public AbstractTestMapIterator(String testName) {
+ super(testName);
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Implement this method to return a map iterator over an empty map.
+ *
+ * @return an empty iterator
+ */
+ public abstract MapIterator makeEmptyMapIterator();
+
+ /**
+ * Implement this method to return a map iterator over a map with elements.
+ *
+ * @return a full iterator
+ */
+ public abstract MapIterator makeFullMapIterator();
+
+ /**
+ * Implement this method to return the map which contains the same data as the
+ * iterator.
+ *
+ * @return a full map which can be updated
+ */
+ public abstract Map getMap();
+
+ /**
+ * Implement this method to return the confirmed map which contains the same
+ * data as the iterator.
+ *
+ * @return a full map which can be updated
+ */
+ public abstract Map getConfirmedMap();
+
+ /**
+ * Implements the abstract superclass method to return the list iterator.
+ *
+ * @return an empty iterator
+ */
+ public final Iterator makeEmptyIterator() {
+ return makeEmptyMapIterator();
+ }
+
+ /**
+ * Implements the abstract superclass method to return the list iterator.
+ *
+ * @return a full iterator
+ */
+ public final Iterator makeFullIterator() {
+ return makeFullMapIterator();
+ }
+
+ /**
+ * Whether or not we are testing an iterator that supports setValue().
+ * Default is true.
+ *
+ * @return true if Iterator supports set
+ */
+ public boolean supportsSetValue() {
+ return true;
+ }
+
+ /**
+ * Whether the get operation on the map structurally modifies the map,
+ * such as with LRUMap. Default is false.
+ *
+ * @return true if the get method structurally modifies the map
+ */
+ public boolean isGetStructuralModify() {
+ return false;
+ }
+
+ /**
+ * The values to be used in the add and set tests.
+ * Default is two strings.
+ */
+ public Object[] addSetValues() {
+ return new Object[] {"A", "B"};
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Test that the empty list iterator contract is correct.
+ */
+ public void testEmptyMapIterator() {
+ if (supportsEmptyIterator() == false) {
+ return;
+ }
+
+ MapIterator it = makeEmptyMapIterator();
+ Map map = getMap();
+ assertEquals(false, it.hasNext());
+
+ // next() should throw a NoSuchElementException
+ try {
+ it.next();
+ fail();
+ } catch (NoSuchElementException ex) {}
+
+ // getKey() should throw an IllegalStateException
+ try {
+ it.getKey();
+ fail();
+ } catch (IllegalStateException ex) {}
+
+ // getValue() should throw an IllegalStateException
+ try {
+ it.getValue();
+ fail();
+ } catch (IllegalStateException ex) {}
+
+ if (supportsSetValue() == false) {
+ // setValue() should throw an UnsupportedOperationException/IllegalStateException
+ try {
+ it.setValue(addSetValues()[0]);
+ fail();
+ } catch (UnsupportedOperationException ex) {
+ } catch (IllegalStateException ex) {}
+ } else {
+ // setValue() should throw an IllegalStateException
+ try {
+ it.setValue(addSetValues()[0]);
+ fail();
+ } catch (IllegalStateException ex) {}
+ }
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Test that the full list iterator contract is correct.
+ */
+ public void testFullMapIterator() {
+ if (supportsFullIterator() == false) {
+ return;
+ }
+
+ MapIterator it = makeFullMapIterator();
+ Map map = getMap();
+ assertEquals(true, it.hasNext());
+
+ assertEquals(true, it.hasNext());
+ Set set = new HashSet();
+ while (it.hasNext()) {
+ // getKey
+ Object key = it.next();
+ assertSame("it.next() should equals getKey()", key, it.getKey());
+ assertTrue("Key must be in map", map.containsKey(key));
+ assertTrue("Key must be unique", set.add(key));
+
+ // getValue
+ Object value = it.getValue();
+ if (isGetStructuralModify() == false) {
+ assertSame("Value must be mapped to key", map.get(key), value);
+ }
+ assertTrue("Value must be in map", map.containsValue(value));
+
+ verify();
+ }
+ }
+
+ //-----------------------------------------------------------------------
+ public void testMapIteratorSet() {
+ if (supportsFullIterator() == false) {
+ return;
+ }
+
+ Object newValue = addSetValues()[0];
+ Object newValue2 = (addSetValues().length == 1 ? addSetValues()[0] : addSetValues()[1]);
+ MapIterator it = makeFullMapIterator();
+ Map map = getMap();
+ Map confirmed = getConfirmedMap();
+ assertEquals(true, it.hasNext());
+ Object key = it.next();
+ Object value = it.getValue();
+
+ if (supportsSetValue() == false) {
+ try {
+ it.setValue(newValue);
+ fail();
+ } catch (UnsupportedOperationException ex) {}
+ return;
+ }
+ Object old = it.setValue(newValue);
+ confirmed.put(key, newValue);
+ assertSame("Key must not change after setValue", key, it.getKey());
+ assertSame("Value must be changed after setValue", newValue, it.getValue());
+ assertSame("setValue must return old value", value, old);
+ assertEquals("Map must contain key", true, map.containsKey(key));
+ // test against confirmed, as map may contain value twice
+ assertEquals("Map must not contain old value",
+ confirmed.containsValue(old), map.containsValue(old));
+ assertEquals("Map must contain new value", true, map.containsValue(newValue));
+ verify();
+
+ it.setValue(newValue); // same value - should be OK
+ confirmed.put(key, newValue);
+ assertSame("Key must not change after setValue", key, it.getKey());
+ assertSame("Value must be changed after setValue", newValue, it.getValue());
+ verify();
+
+ it.setValue(newValue2); // new value
+ confirmed.put(key, newValue2);
+ assertSame("Key must not change after setValue", key, it.getKey());
+ assertSame("Value must be changed after setValue", newValue2, it.getValue());
+ verify();
+ }
+
+ //-----------------------------------------------------------------------
+ public void testRemove() { // override
+ MapIterator it = makeFullMapIterator();
+ Map map = getMap();
+ Map confirmed = getConfirmedMap();
+ assertEquals(true, it.hasNext());
+ Object key = it.next();
+
+ if (supportsRemove() == false) {
+ try {
+ it.remove();
+ fail();
+ } catch (UnsupportedOperationException ex) {
+ }
+ return;
+ }
+
+ it.remove();
+ confirmed.remove(key);
+ assertEquals(false, map.containsKey(key));
+ verify();
+
+ try {
+ it.remove(); // second remove fails
+ } catch (IllegalStateException ex) {
+ }
+ verify();
+ }
+
+ //-----------------------------------------------------------------------
+ public void testMapIteratorSetRemoveSet() {
+ if (supportsSetValue() == false || supportsRemove() == false) {
+ return;
+ }
+ Object newValue = addSetValues()[0];
+ MapIterator it = makeFullMapIterator();
+ Map map = getMap();
+ Map confirmed = getConfirmedMap();
+
+ assertEquals(true, it.hasNext());
+ Object key = it.next();
+
+ it.setValue(newValue);
+ it.remove();
+ confirmed.remove(key);
+ verify();
+
+ try {
+ it.setValue(newValue);
+ fail();
+ } catch (IllegalStateException ex) {}
+ verify();
+ }
+
+ //-----------------------------------------------------------------------
+ public void testMapIteratorRemoveGetKey() {
+ if (supportsRemove() == false) {
+ return;
+ }
+ MapIterator it = makeFullMapIterator();
+ Map map = getMap();
+ Map confirmed = getConfirmedMap();
+
+ assertEquals(true, it.hasNext());
+ Object key = it.next();
+
+ it.remove();
+ confirmed.remove(key);
+ verify();
+
+ try {
+ it.getKey();
+ fail();
+ } catch (IllegalStateException ex) {}
+ verify();
+ }
+
+ //-----------------------------------------------------------------------
+ public void testMapIteratorRemoveGetValue() {
+ if (supportsRemove() == false) {
+ return;
+ }
+ MapIterator it = makeFullMapIterator();
+ Map map = getMap();
+ Map confirmed = getConfirmedMap();
+
+ assertEquals(true, it.hasNext());
+ Object key = it.next();
+
+ it.remove();
+ confirmed.remove(key);
+ verify();
+
+ try {
+ it.getValue();
+ fail();
+ } catch (IllegalStateException ex) {}
+ verify();
+ }
+
+}
diff --git a/dev/core/test/org/apache/commons/collections/map/AbstractTestIterableMap.java b/dev/core/test/org/apache/commons/collections/map/AbstractTestIterableMap.java
new file mode 100644
index 0000000..bd57fcc
--- /dev/null
+++ b/dev/core/test/org/apache/commons/collections/map/AbstractTestIterableMap.java
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.map;
+
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.Map;
+
+import org.apache.commons.collections.IterableMap;
+import org.apache.commons.collections.BulkTest;
+import org.apache.commons.collections.MapIterator;
+import org.apache.commons.collections.iterators.AbstractTestMapIterator;
+
+/**
+ * Abstract test class for {@link IterableMap} methods and contracts.
+ *
+ * @version $Revision: 646780 $ $Date: 2008-04-10 13:48:07 +0100 (Thu, 10 Apr 2008) $
+ *
+ * @author Stephen Colebourne
+ */
+public abstract class AbstractTestIterableMap extends AbstractTestMap {
+
+ /**
+ * JUnit constructor.
+ *
+ * @param testName the test name
+ */
+ public AbstractTestIterableMap(String testName) {
+ super(testName);
+ }
+
+ //-----------------------------------------------------------------------
+ public void testFailFastEntrySet() {
+ if (isRemoveSupported() == false) return;
+ resetFull();
+ Iterator it = map.entrySet().iterator();
+ Map.Entry val = (Map.Entry) it.next();
+ map.remove(val.getKey());
+ try {
+ it.next();
+ fail();
+ } catch (ConcurrentModificationException ex) {}
+
+ resetFull();
+ it = map.entrySet().iterator();
+ it.next();
+ map.clear();
+ try {
+ it.next();
+ fail();
+ } catch (ConcurrentModificationException ex) {}
+ }
+
+ public void testFailFastKeySet() {
+ if (isRemoveSupported() == false) return;
+ resetFull();
+ Iterator it = map.keySet().iterator();
+ Object val = it.next();
+ map.remove(val);
+ try {
+ it.next();
+ fail();
+ } catch (ConcurrentModificationException ex) {}
+
+ resetFull();
+ it = map.keySet().iterator();
+ it.next();
+ map.clear();
+ try {
+ it.next();
+ fail();
+ } catch (ConcurrentModificationException ex) {}
+ }
+
+ public void testFailFastValues() {
+ if (isRemoveSupported() == false) return;
+ resetFull();
+ Iterator it = map.values().iterator();
+ it.next();
+ map.remove(map.keySet().iterator().next());
+ try {
+ it.next();
+ fail();
+ } catch (ConcurrentModificationException ex) {}
+
+ resetFull();
+ it = map.values().iterator();
+ it.next();
+ map.clear();
+ try {
+ it.next();
+ fail();
+ } catch (ConcurrentModificationException ex) {}
+ }
+
+ //-----------------------------------------------------------------------
+ public BulkTest bulkTestMapIterator() {
+ return new InnerTestMapIterator();
+ }
+
+ public class InnerTestMapIterator extends AbstractTestMapIterator {
+ public InnerTestMapIterator() {
+ super("InnerTestMapIterator");
+ }
+
+ public Object[] addSetValues() {
+ return AbstractTestIterableMap.this.getNewSampleValues();
+ }
+
+ public boolean supportsRemove() {
+ return AbstractTestIterableMap.this.isRemoveSupported();
+ }
+
+ public boolean isGetStructuralModify() {
+ return AbstractTestIterableMap.this.isGetStructuralModify();
+ }
+
+ public boolean supportsSetValue() {
+ return AbstractTestIterableMap.this.isSetValueSupported();
+ }
+
+ public MapIterator makeEmptyMapIterator() {
+ resetEmpty();
+ return ((IterableMap) AbstractTestIterableMap.this.map).mapIterator();
+ }
+
+ public MapIterator makeFullMapIterator() {
+ resetFull();
+ return ((IterableMap) AbstractTestIterableMap.this.map).mapIterator();
+ }
+
+ public Map getMap() {
+ // assumes makeFullMapIterator() called first
+ return AbstractTestIterableMap.this.map;
+ }
+
+ public Map getConfirmedMap() {
+ // assumes makeFullMapIterator() called first
+ return AbstractTestIterableMap.this.confirmed;
+ }
+
+ public void verify() {
+ super.verify();
+ AbstractTestIterableMap.this.verify();
+ }
+ }
+
+// public void testCreate() throws Exception {
+// resetEmpty();
+// writeExternalFormToDisk((Serializable) map, "D:/dev/collections/data/test/HashedMap.emptyCollection.version3.obj");
+// resetFull();
+// writeExternalFormToDisk((Serializable) map, "D:/dev/collections/data/test/HashedMap.fullCollection.version3.obj");
+// }
+}
diff --git a/dev/core/test/org/apache/commons/collections/map/AbstractTestMap.java b/dev/core/test/org/apache/commons/collections/map/AbstractTestMap.java
new file mode 100644
index 0000000..8176900
--- /dev/null
+++ b/dev/core/test/org/apache/commons/collections/map/AbstractTestMap.java
@@ -0,0 +1,1700 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.map;
+
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.commons.collections.AbstractTestObject;
+import org.apache.commons.collections.BulkTest;
+import org.apache.commons.collections.collection.AbstractTestCollection;
+import org.apache.commons.collections.set.AbstractTestSet;
+
+/**
+ * Abstract test class for {@link java.util.Map} methods and contracts.
+ * <p>
+ * The forces at work here are similar to those in {@link AbstractTestCollection}.
+ * If your class implements the full Map interface, including optional
+ * operations, simply extend this class, and implement the
+ * {@link #makeEmptyMap()} method.
+ * <p>
+ * On the other hand, if your map implementation is weird, you may have to
+ * override one or more of the other protected methods. They're described
+ * below.
+ * <p>
+ * <b>Entry Population Methods</b>
+ * <p>
+ * Override these methods if your map requires special entries:
+ *
+ * <ul>
+ * <li>{@link #getSampleKeys()}
+ * <li>{@link #getSampleValues()}
+ * <li>{@link #getNewSampleValues()}
+ * <li>{@link #getOtherKeys()}
+ * <li>{@link #getOtherValues()}
+ * </ul>
+ *
+ * <b>Supported Operation Methods</b>
+ * <p>
+ * Override these methods if your map doesn't support certain operations:
+ *
+ * <ul>
+ * <li> {@link #isPutAddSupported()}
+ * <li> {@link #isPutChangeSupported()}
+ * <li> {@link #isSetValueSupported()}
+ * <li> {@link #isRemoveSupported()}
+ * <li> {@link #isGetStructuralModify()}
+ * <li> {@link #isAllowDuplicateValues()}
+ * <li> {@link #isAllowNullKey()}
+ * <li> {@link #isAllowNullValue()}
+ * </ul>
+ *
+ * <b>Fixture Methods</b>
+ * <p>
+ * For tests on modification operations (puts and removes), fixtures are used
+ * to verify that that operation results in correct state for the map and its
+ * collection views. Basically, the modification is performed against your
+ * map implementation, and an identical modification is performed against
+ * a <I>confirmed</I> map implementation. A confirmed map implementation is
+ * something like <Code>java.util.HashMap</Code>, which is known to conform
+ * exactly to the {@link Map} contract. After the modification takes place
+ * on both your map implementation and the confirmed map implementation, the
+ * two maps are compared to see if their state is identical. The comparison
+ * also compares the collection views to make sure they're still the same.<P>
+ *
+ * The upshot of all that is that <I>any</I> test that modifies the map in
+ * <I>any</I> way will verify that <I>all</I> of the map's state is still
+ * correct, including the state of its collection views. So for instance
+ * if a key is removed by the map's key set's iterator, then the entry set
+ * is checked to make sure the key/value pair no longer appears.<P>
+ *
+ * The {@link #map} field holds an instance of your collection implementation.
+ * The {@link #entrySet}, {@link #keySet} and {@link #values} fields hold
+ * that map's collection views. And the {@link #confirmed} field holds
+ * an instance of the confirmed collection implementation. The
+ * {@link #resetEmpty()} and {@link #resetFull()} methods set these fields to
+ * empty or full maps, so that tests can proceed from a known state.<P>
+ *
+ * After a modification operation to both {@link #map} and {@link #confirmed},
+ * the {@link #verify()} method is invoked to compare the results. The
+ * {@link #verify} method calls separate methods to verify the map and its three
+ * collection views ({@link #verifyMap}, {@link #verifyEntrySet},
+ * {@link #verifyKeySet}, and {@link #verifyValues}). You may want to override
+ * one of the verification methodsto perform additional verifications. For
+ * instance, TestDoubleOrderedMap would want override its
+ * {@link #verifyValues()} method to verify that the values are unique and in
+ * ascending order.<P>
+ *
+ * <b>Other Notes</b>
+ * <p>
+ * If your {@link Map} fails one of these tests by design, you may still use
+ * this base set of cases. Simply override the test case (method) your map
+ * fails and/or the methods that define the assumptions used by the test
+ * cases. For example, if your map does not allow duplicate values, override
+ * {@link #isAllowDuplicateValues()} and have it return <code>false</code>
+ *
+ * @author Michael Smith
+ * @author Rodney Waldhoff
+ * @author Paul Jack
+ * @author Stephen Colebourne
+ * @version $Revision: 646780 $ $Date: 2008-04-10 13:48:07 +0100 (Thu, 10 Apr 2008) $
+ */
+public abstract class AbstractTestMap extends AbstractTestObject {
+
+ /**
+ * JDK1.2 has bugs in null handling of Maps, especially HashMap.Entry.toString
+ * This avoids nulls for JDK1.2
+ */
+ private static final boolean JDK12;
+ static {
+ String str = System.getProperty("java.version");
+ JDK12 = str.startsWith("1.2");
+ }
+
+ // These instance variables are initialized with the reset method.
+ // Tests for map methods that alter the map (put, putAll, remove)
+ // first call reset() to create the map and its views; then perform
+ // the modification on the map; perform the same modification on the
+ // confirmed; and then call verify() to ensure that the map is equal
+ // to the confirmed, that the already-constructed collection views
+ // are still equal to the confirmed's collection views.
+
+
+ /** Map created by reset(). */
+ protected Map map;
+
+ /** Entry set of map created by reset(). */
+ protected Set entrySet;
+
+ /** Key set of map created by reset(). */
+ protected Set keySet;
+
+ /** Values collection of map created by reset(). */
+ protected Collection values;
+
+ /** HashMap created by reset(). */
+ protected Map confirmed;
+
+ /**
+ * JUnit constructor.
+ *
+ * @param testName the test name
+ */
+ public AbstractTestMap(String testName) {
+ super(testName);
+ }
+
+ /**
+ * Returns true if the maps produced by
+ * {@link #makeEmptyMap()} and {@link #makeFullMap()}
+ * support the <code>put</code> and <code>putAll</code> operations
+ * adding new mappings.
+ * <p>
+ * Default implementation returns true.
+ * Override if your collection class does not support put adding.
+ */
+ public boolean isPutAddSupported() {
+ return true;
+ }
+
+ /**
+ * Returns true if the maps produced by
+ * {@link #makeEmptyMap()} and {@link #makeFullMap()}
+ * support the <code>put</code> and <code>putAll</code> operations
+ * changing existing mappings.
+ * <p>
+ * Default implementation returns true.
+ * Override if your collection class does not support put changing.
+ */
+ public boolean isPutChangeSupported() {
+ return true;
+ }
+
+ /**
+ * Returns true if the maps produced by
+ * {@link #makeEmptyMap()} and {@link #makeFullMap()}
+ * support the <code>setValue</code> operation on entrySet entries.
+ * <p>
+ * Default implementation returns isPutChangeSupported().
+ * Override if your collection class does not support setValue but does
+ * support put changing.
+ */
+ public boolean isSetValueSupported() {
+ return isPutChangeSupported();
+ }
+
+ /**
+ * Returns true if the maps produced by
+ * {@link #makeEmptyMap()} and {@link #makeFullMap()}
+ * support the <code>remove</code> and <code>clear</code> operations.
+ * <p>
+ * Default implementation returns true.
+ * Override if your collection class does not support removal operations.
+ */
+ public boolean isRemoveSupported() {
+ return true;
+ }
+
+ /**
+ * Returns true if the maps produced by
+ * {@link #makeEmptyMap()} and {@link #makeFullMap()}
+ * can cause structural modification on a get(). The example is LRUMap.
+ * <p>
+ * Default implementation returns false.
+ * Override if your map class structurally modifies on get.
+ */
+ public boolean isGetStructuralModify() {
+ return false;
+ }
+
+ /**
+ * Returns whether the sub map views of SortedMap are serializable.
+ * If the class being tested is based around a TreeMap then you should
+ * override and return false as TreeMap has a bug in deserialization.
+ *
+ * @return false
+ */
+ public boolean isSubMapViewsSerializable() {
+ return true;
+ }
+
+ /**
+ * Returns true if the maps produced by
+ * {@link #makeEmptyMap()} and {@link #makeFullMap()}
+ * supports null keys.
+ * <p>
+ * Default implementation returns true.
+ * Override if your collection class does not support null keys.
+ */
+ public boolean isAllowNullKey() {
+ return true;
+ }
+
+ /**
+ * Returns true if the maps produced by
+ * {@link #makeEmptyMap()} and {@link #makeFullMap()}
+ * supports null values.
+ * <p>
+ * Default implementation returns true.
+ * Override if your collection class does not support null values.
+ */
+ public boolean isAllowNullValue() {
+ return true;
+ }
+
+ /**
+ * Returns true if the maps produced by
+ * {@link #makeEmptyMap()} and {@link #makeFullMap()}
+ * supports duplicate values.
+ * <p>
+ * Default implementation returns true.
+ * Override if your collection class does not support duplicate values.
+ */
+ public boolean isAllowDuplicateValues() {
+ return true;
+ }
+
+ /**
+ * Returns the set of keys in the mappings used to test the map. This
+ * method must return an array with the same length as {@link
+ * #getSampleValues()} and all array elements must be different. The
+ * default implementation constructs a set of String keys, and includes a
+ * single null key if {@link #isAllowNullKey()} returns <code>true</code>.
+ */
+ public Object[] getSampleKeys() {
+ Object[] result = new Object[] {
+ "blah", "foo", "bar", "baz", "tmp", "gosh", "golly", "gee",
+ "hello", "goodbye", "we'll", "see", "you", "all", "again",
+ "key",
+ "key2",
+ (isAllowNullKey() && !JDK12) ? null : "nonnullkey"
+ };
+ return result;
+ }
+
+
+ public Object[] getOtherKeys() {
+ return getOtherNonNullStringElements();
+ }
+
+ public Object[] getOtherValues() {
+ return getOtherNonNullStringElements();
+ }
+
+ /**
+ * Returns a list of string elements suitable for return by
+ * {@link #getOtherKeys()} or {@link #getOtherValues}.
+ *
+ * <p>Override getOtherElements to returnthe results of this method if your
+ * collection does not support heterogenous elements or the null element.
+ * </p>
+ */
+ public Object[] getOtherNonNullStringElements() {
+ return new Object[] {
+ "For","then","despite",/* of */"space","I","would","be","brought",
+ "From","limits","far","remote","where","thou","dost","stay"
+ };
+ }
+
+ /**
+ * Returns the set of values in the mappings used to test the map. This
+ * method must return an array with the same length as
+ * {@link #getSampleKeys()}. The default implementation constructs a set of
+ * String values and includes a single null value if
+ * {@link #isAllowNullValue()} returns <code>true</code>, and includes
+ * two values that are the same if {@link #isAllowDuplicateValues()} returns
+ * <code>true</code>.
+ */
+ public Object[] getSampleValues() {
+ Object[] result = new Object[] {
+ "blahv", "foov", "barv", "bazv", "tmpv", "goshv", "gollyv", "geev",
+ "hellov", "goodbyev", "we'llv", "seev", "youv", "allv", "againv",
+ (isAllowNullValue() && !JDK12) ? null : "nonnullvalue",
+ "value",
+ (isAllowDuplicateValues()) ? "value" : "value2",
+ };
+ return result;
+ }
+
+ /**
+ * Returns a the set of values that can be used to replace the values
+ * returned from {@link #getSampleValues()}. This method must return an
+ * array with the same length as {@link #getSampleValues()}. The values
+ * returned from this method should not be the same as those returned from
+ * {@link #getSampleValues()}. The default implementation constructs a
+ * set of String values and includes a single null value if
+ * {@link #isAllowNullValue()} returns <code>true</code>, and includes two values
+ * that are the same if {@link #isAllowDuplicateValues()} returns
+ * <code>true</code>.
+ */
+ public Object[] getNewSampleValues() {
+ Object[] result = new Object[] {
+ (isAllowNullValue() && !JDK12 && isAllowDuplicateValues()) ? null : "newnonnullvalue",
+ "newvalue",
+ (isAllowDuplicateValues()) ? "newvalue" : "newvalue2",
+ "newblahv", "newfoov", "newbarv", "newbazv", "newtmpv", "newgoshv",
+ "newgollyv", "newgeev", "newhellov", "newgoodbyev", "newwe'llv",
+ "newseev", "newyouv", "newallv", "newagainv",
+ };
+ return result;
+ }
+
+ /**
+ * Helper method to add all the mappings described by
+ * {@link #getSampleKeys()} and {@link #getSampleValues()}.
+ */
+ public void addSampleMappings(Map m) {
+
+ Object[] keys = getSampleKeys();
+ Object[] values = getSampleValues();
+
+ for(int i = 0; i < keys.length; i++) {
+ try {
+ m.put(keys[i], values[i]);
+ } catch (NullPointerException exception) {
+ assertTrue("NullPointerException only allowed to be thrown " +
+ "if either the key or value is null.",
+ keys[i] == null || values[i] == null);
+
+ assertTrue("NullPointerException on null key, but " +
+ "isAllowNullKey is not overridden to return false.",
+ keys[i] == null || !isAllowNullKey());
+
+ assertTrue("NullPointerException on null value, but " +
+ "isAllowNullValue is not overridden to return false.",
+ values[i] == null || !isAllowNullValue());
+
+ assertTrue("Unknown reason for NullPointer.", false);
+ }
+ }
+ assertEquals("size must reflect number of mappings added.",
+ keys.length, m.size());
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Return a new, empty {@link Map} to be used for testing.
+ *
+ * @return the map to be tested
+ */
+ public abstract Map makeEmptyMap();
+
+ /**
+ * Return a new, populated map. The mappings in the map should match the
+ * keys and values returned from {@link #getSampleKeys()} and
+ * {@link #getSampleValues()}. The default implementation uses makeEmptyMap()
+ * and calls {@link #addSampleMappings} to add all the mappings to the
+ * map.
+ *
+ * @return the map to be tested
+ */
+ public Map makeFullMap() {
+ Map m = makeEmptyMap();
+ addSampleMappings(m);
+ return m;
+ }
+
+ /**
+ * Implements the superclass method to return the map to be tested.
+ *
+ * @return the map to be tested
+ */
+ public Object makeObject() {
+ return makeEmptyMap();
+ }
+
+ /**
+ * Override to return a map other than HashMap as the confirmed map.
+ *
+ * @return a map that is known to be valid
+ */
+ public Map makeConfirmedMap() {
+ return new HashMap();
+ }
+
+ /**
+ * Creates a new Map Entry that is independent of the first and the map.
+ */
+ public Map.Entry cloneMapEntry(Map.Entry entry) {
+ HashMap map = new HashMap();
+ map.put(entry.getKey(), entry.getValue());
+ return (Map.Entry) map.entrySet().iterator().next();
+ }
+
+ /**
+ * Gets the compatability version, needed for package access.
+ */
+ public String getCompatibilityVersion() {
+ return super.getCompatibilityVersion();
+ }
+ //-----------------------------------------------------------------------
+ /**
+ * Test to ensure the test setup is working properly. This method checks
+ * to ensure that the getSampleKeys and getSampleValues methods are
+ * returning results that look appropriate. That is, they both return a
+ * non-null array of equal length. The keys array must not have any
+ * duplicate values, and may only contain a (single) null key if
+ * isNullKeySupported() returns true. The values array must only have a null
+ * value if useNullValue() is true and may only have duplicate values if
+ * isAllowDuplicateValues() returns true.
+ */
+ public void testSampleMappings() {
+ Object[] keys = getSampleKeys();
+ Object[] values = getSampleValues();
+ Object[] newValues = getNewSampleValues();
+
+ assertTrue("failure in test: Must have keys returned from " +
+ "getSampleKeys.", keys != null);
+
+ assertTrue("failure in test: Must have values returned from " +
+ "getSampleValues.", values != null);
+
+ // verify keys and values have equivalent lengths (in case getSampleX are
+ // overridden)
+ assertEquals("failure in test: not the same number of sample " +
+ "keys and values.", keys.length, values.length);
+
+ assertEquals("failure in test: not the same number of values and new values.",
+ values.length, newValues.length);
+
+ // verify there aren't duplicate keys, and check values
+ for(int i = 0; i < keys.length - 1; i++) {
+ for(int j = i + 1; j < keys.length; j++) {
+ assertTrue("failure in test: duplicate null keys.",
+ (keys[i] != null || keys[j] != null));
+ assertTrue("failure in test: duplicate non-null key.",
+ (keys[i] == null || keys[j] == null ||
+ (!keys[i].equals(keys[j]) &&
+ !keys[j].equals(keys[i]))));
+ }
+ assertTrue("failure in test: found null key, but isNullKeySupported " +
+ "is false.", keys[i] != null || isAllowNullKey());
+ assertTrue("failure in test: found null value, but isNullValueSupported " +
+ "is false.", values[i] != null || isAllowNullValue());
+ assertTrue("failure in test: found null new value, but isNullValueSupported " +
+ "is false.", newValues[i] != null || isAllowNullValue());
+ assertTrue("failure in test: values should not be the same as new value",
+ values[i] != newValues[i] &&
+ (values[i] == null || !values[i].equals(newValues[i])));
+ }
+ }
+
+ // tests begin here. Each test adds a little bit of tested functionality.
+ // Many methods assume previous methods passed. That is, they do not
+ // exhaustively recheck things that have already been checked in a previous
+ // test methods.
+
+ /**
+ * Test to ensure that makeEmptyMap and makeFull returns a new non-null
+ * map with each invocation.
+ */
+ public void testMakeMap() {
+ Map em = makeEmptyMap();
+ assertTrue("failure in test: makeEmptyMap must return a non-null map.",
+ em != null);
+
+ Map em2 = makeEmptyMap();
+ assertTrue("failure in test: makeEmptyMap must return a non-null map.",
+ em != null);
+
+ assertTrue("failure in test: makeEmptyMap must return a new map " +
+ "with each invocation.", em != em2);
+
+ Map fm = makeFullMap();
+ assertTrue("failure in test: makeFullMap must return a non-null map.",
+ fm != null);
+
+ Map fm2 = makeFullMap();
+ assertTrue("failure in test: makeFullMap must return a non-null map.",
+ fm != null);
+
+ assertTrue("failure in test: makeFullMap must return a new map " +
+ "with each invocation.", fm != fm2);
+ }
+
+ /**
+ * Tests Map.isEmpty()
+ */
+ public void testMapIsEmpty() {
+ resetEmpty();
+ assertEquals("Map.isEmpty() should return true with an empty map",
+ true, map.isEmpty());
+ verify();
+
+ resetFull();
+ assertEquals("Map.isEmpty() should return false with a non-empty map",
+ false, map.isEmpty());
+ verify();
+ }
+
+ /**
+ * Tests Map.size()
+ */
+ public void testMapSize() {
+ resetEmpty();
+ assertEquals("Map.size() should be 0 with an empty map",
+ 0, map.size());
+ verify();
+
+ resetFull();
+ assertEquals("Map.size() should equal the number of entries " +
+ "in the map", getSampleKeys().length, map.size());
+ verify();
+ }
+
+ /**
+ * Tests {@link Map#clear()}. If the map {@link #isRemoveSupported()}
+ * can add and remove elements}, then {@link Map#size()} and
+ * {@link Map#isEmpty()} are used to ensure that map has no elements after
+ * a call to clear. If the map does not support adding and removing
+ * elements, this method checks to ensure clear throws an
+ * UnsupportedOperationException.
+ */
+ public void testMapClear() {
+ if (!isRemoveSupported()) {
+ try {
+ resetFull();
+ map.clear();
+ fail("Expected UnsupportedOperationException on clear");
+ } catch (UnsupportedOperationException ex) {}
+ return;
+ }
+
+ resetEmpty();
+ map.clear();
+ confirmed.clear();
+ verify();
+
+ resetFull();
+ map.clear();
+ confirmed.clear();
+ verify();
+ }
+
+
+ /**
+ * Tests Map.containsKey(Object) by verifying it returns false for all
+ * sample keys on a map created using an empty map and returns true for
+ * all sample keys returned on a full map.
+ */
+ public void testMapContainsKey() {
+ Object[] keys = getSampleKeys();
+
+ resetEmpty();
+ for(int i = 0; i < keys.length; i++) {
+ assertTrue("Map must not contain key when map is empty",
+ !map.containsKey(keys[i]));
+ }
+ verify();
+
+ resetFull();
+ for(int i = 0; i < keys.length; i++) {
+ assertTrue("Map must contain key for a mapping in the map. " +
+ "Missing: " + keys[i], map.containsKey(keys[i]));
+ }
+ verify();
+ }
+
+ /**
+ * Tests Map.containsValue(Object) by verifying it returns false for all
+ * sample values on an empty map and returns true for all sample values on
+ * a full map.
+ */
+ public void testMapContainsValue() {
+ Object[] values = getSampleValues();
+
+ resetEmpty();
+ for(int i = 0; i < values.length; i++) {
+ assertTrue("Empty map must not contain value",
+ !map.containsValue(values[i]));
+ }
+ verify();
+
+ resetFull();
+ for(int i = 0; i < values.length; i++) {
+ assertTrue("Map must contain value for a mapping in the map.",
+ map.containsValue(values[i]));
+ }
+ verify();
+ }
+
+
+ /**
+ * Tests Map.equals(Object)
+ */
+ public void testMapEquals() {
+ resetEmpty();
+ assertTrue("Empty maps unequal.", map.equals(confirmed));
+ verify();
+
+ resetFull();
+ assertTrue("Full maps unequal.", map.equals(confirmed));
+ verify();
+
+ resetFull();
+ // modify the HashMap created from the full map and make sure this
+ // change results in map.equals() to return false.
+ Iterator iter = confirmed.keySet().iterator();
+ iter.next();
+ iter.remove();
+ assertTrue("Different maps equal.", !map.equals(confirmed));
+
+ resetFull();
+ assertTrue("equals(null) returned true.", !map.equals(null));
+ assertTrue("equals(new Object()) returned true.",
+ !map.equals(new Object()));
+ verify();
+ }
+
+
+ /**
+ * Tests Map.get(Object)
+ */
+ public void testMapGet() {
+ resetEmpty();
+
+ 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();
+
+ 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());
+
+ resetFull();
+ assertTrue("Equal maps have different hashCodes.",
+ map.hashCode() == confirmed.hashCode());
+ }
+
+ /**
+ * Tests Map.toString(). Since the format of the string returned by the
+ * toString() method is not defined in the Map interface, there is no
+ * common way to test the results of the toString() method. Thereforce,
+ * it is encouraged that Map implementations override this test with one
+ * that checks the format matches any format defined in its API. This
+ * default implementation just verifies that the toString() method does
+ * not return null.
+ */
+ public void testMapToString() {
+ 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();
+ }
+
+
+ /**
+ * Compare the current serialized form of the Map
+ * against the canonical version in CVS.
+ */
+ public void testEmptyMapCompatibility() throws Exception {
+ /**
+ * Create canonical objects with this code
+ Map map = makeEmptyMap();
+ if (!(map instanceof Serializable)) return;
+
+ writeExternalFormToDisk((Serializable) map, getCanonicalEmptyCollectionName(map));
+ */
+
+ // test to make sure the canonical form has been preserved
+ Map map = makeEmptyMap();
+ if (map instanceof Serializable && !skipSerializedCanonicalTests() && isTestSerialization()) {
+ Map map2 = (Map) readExternalFormFromDisk(getCanonicalEmptyCollectionName(map));
+ assertEquals("Map is empty", 0, map2.size());
+ }
+ }
+
+ /**
+ * Compare the current serialized form of the Map
+ * against the canonical version in CVS.
+ */
+ public void testFullMapCompatibility() throws Exception {
+ /**
+ * Create canonical objects with this code
+ Map map = makeFullMap();
+ if (!(map instanceof Serializable)) return;
+
+ writeExternalFormToDisk((Serializable) map, getCanonicalFullCollectionName(map));
+ */
+
+ // test to make sure the canonical form has been preserved
+ Map map = makeFullMap();
+ if (map instanceof Serializable && !skipSerializedCanonicalTests() && isTestSerialization()) {
+ Map map2 = (Map) readExternalFormFromDisk(getCanonicalFullCollectionName(map));
+ assertEquals("Map is the right size", getSampleKeys().length, map2.size());
+ }
+ }
+
+ /**
+ * Tests Map.put(Object, Object)
+ */
+ public void testMapPut() {
+ resetEmpty();
+ Object[] keys = getSampleKeys();
+ Object[] values = getSampleValues();
+ Object[] newValues = getNewSampleValues();
+
+ if (isPutAddSupported()) {
+ 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 (isPutChangeSupported()) {
+ for (int i = 0; i < keys.length; i++) {
+ Object o = map.put(keys[i], newValues[i]);
+ confirmed.put(keys[i], newValues[i]);
+ verify();
+ assertEquals("Map.put should return previous value when changed",
+ values[i], o);
+ assertTrue("Map should still contain key after put when changed",
+ map.containsKey(keys[i]));
+ assertTrue("Map should contain new value after put when changed",
+ map.containsValue(newValues[i]));
+
+ // if duplicates are allowed, we're not guaranteed that the value
+ // no longer exists, so don't try checking that.
+ if (!isAllowDuplicateValues()) {
+ assertTrue("Map should not contain old value after put when changed",
+ !map.containsValue(values[i]));
+ }
+ }
+ } else {
+ try {
+ // two possible exception here, either valid
+ map.put(keys[0], newValues[0]);
+ fail("Expected IllegalArgumentException or UnsupportedOperationException on put (change)");
+ } catch (IllegalArgumentException ex) {
+ } catch (UnsupportedOperationException ex) {}
+ }
+
+ } else if (isPutChangeSupported()) {
+ resetEmpty();
+ try {
+ map.put(keys[0], values[0]);
+ fail("Expected UnsupportedOperationException or IllegalArgumentException on put (add) when fixed size");
+ } catch (IllegalArgumentException ex) {
+ } catch (UnsupportedOperationException ex) {
+ }
+
+ resetFull();
+ int i = 0;
+ for (Iterator it = map.keySet().iterator(); it.hasNext() && i < newValues.length; i++) {
+ Object key = it.next();
+ Object o = map.put(key, newValues[i]);
+ Object value = confirmed.put(key, newValues[i]);
+ verify();
+ assertEquals("Map.put should return previous value when changed",
+ value, o);
+ assertTrue("Map should still contain key after put when changed",
+ map.containsKey(key));
+ assertTrue("Map should contain new value after put when changed",
+ map.containsValue(newValues[i]));
+
+ // if duplicates are allowed, we're not guaranteed that the value
+ // no longer exists, so don't try checking that.
+ if (!isAllowDuplicateValues()) {
+ assertTrue("Map should not contain old value after put when changed",
+ !map.containsValue(values[i]));
+ }
+ }
+ } else {
+ try {
+ map.put(keys[0], values[0]);
+ fail("Expected UnsupportedOperationException on put (add)");
+ } catch (UnsupportedOperationException ex) {}
+ }
+ }
+
+ /**
+ * Tests Map.put(null, value)
+ */
+ public void testMapPutNullKey() {
+ resetFull();
+ Object[] values = getSampleValues();
+
+ if (isPutAddSupported()) {
+ if (isAllowNullKey()) {
+ map.put(null, values[0]);
+ } else {
+ try {
+ map.put(null, values[0]);
+ fail("put(null, value) should throw NPE/IAE");
+ } catch (NullPointerException ex) {
+ } catch (IllegalArgumentException ex) {}
+ }
+ }
+ }
+
+ /**
+ * Tests Map.put(null, value)
+ */
+ public void testMapPutNullValue() {
+ resetFull();
+ Object[] keys = getSampleKeys();
+
+ if (isPutAddSupported()) {
+ if (isAllowNullValue()) {
+ map.put(keys[0], null);
+ } else {
+ try {
+ map.put(keys[0], null);
+ fail("put(key, null) should throw NPE/IAE");
+ } catch (NullPointerException ex) {
+ } catch (IllegalArgumentException ex) {}
+ }
+ }
+ }
+
+ /**
+ * Tests Map.putAll(map)
+ */
+ public void testMapPutAll() {
+ if (!isPutAddSupported()) {
+ if (!isPutChangeSupported()) {
+ Map temp = makeFullMap();
+ resetEmpty();
+ try {
+ map.putAll(temp);
+ fail("Expected UnsupportedOperationException on putAll");
+ } catch (UnsupportedOperationException ex) {}
+ }
+ return;
+ }
+
+ // check putAll OK adding empty map to empty map
+ resetEmpty();
+ assertEquals(0, map.size());
+ map.putAll(new HashMap());
+ assertEquals(0, map.size());
+
+ // check putAll OK adding empty map to non-empty map
+ resetFull();
+ int size = map.size();
+ map.putAll(new HashMap());
+ assertEquals(size, map.size());
+
+ // check putAll OK adding non-empty map to empty map
+ resetEmpty();
+ Map m2 = makeFullMap();
+ map.putAll(m2);
+ confirmed.putAll(m2);
+ verify();
+
+ // check putAll OK adding non-empty JDK map to empty map
+ resetEmpty();
+ m2 = makeConfirmedMap();
+ 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();
+
+ // check putAll OK adding non-empty JDK map to non-empty map
+ resetEmpty();
+ m2 = makeConfirmedMap();
+ map.put(keys[0], values[0]);
+ confirmed.put(keys[0], values[0]);
+ verify();
+ for(int i = 1; i < keys.length; i++) {
+ m2.put(keys[i], values[i]);
+ }
+ map.putAll(m2);
+ confirmed.putAll(m2);
+ verify();
+ }
+
+ /**
+ * Tests Map.remove(Object)
+ */
+ public void testMapRemove() {
+ if (!isRemoveSupported()) {
+ try {
+ resetFull();
+ map.remove(map.keySet().iterator().next());
+ fail("Expected UnsupportedOperationException on remove");
+ } catch (UnsupportedOperationException ex) {}
+ return;
+ }
+
+ 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);
+ }
+ verify();
+
+ resetFull();
+
+ for(int i = 0; i < keys.length; i++) {
+ Object o = map.remove(keys[i]);
+ confirmed.remove(keys[i]);
+ verify();
+
+ 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();
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Tests that the {@link Map#values} collection is backed by
+ * the underlying map for clear().
+ */
+ public void testValuesClearChangesMap() {
+ if (!isRemoveSupported()) return;
+
+ // clear values, reflected in map
+ resetFull();
+ Collection values = map.values();
+ assertTrue(map.size() > 0);
+ assertTrue(values.size() > 0);
+ values.clear();
+ assertTrue(map.size() == 0);
+ assertTrue(values.size() == 0);
+
+ // clear map, reflected in values
+ resetFull();
+ values = map.values();
+ assertTrue(map.size() > 0);
+ assertTrue(values.size() > 0);
+ map.clear();
+ assertTrue(map.size() == 0);
+ assertTrue(values.size() == 0);
+ }
+
+ /**
+ * Tests that the {@link Map#keySet} collection is backed by
+ * the underlying map for clear().
+ */
+ public void testKeySetClearChangesMap() {
+ if (!isRemoveSupported()) return;
+
+ // clear values, reflected in map
+ resetFull();
+ Set keySet = map.keySet();
+ assertTrue(map.size() > 0);
+ assertTrue(keySet.size() > 0);
+ keySet.clear();
+ assertTrue(map.size() == 0);
+ assertTrue(keySet.size() == 0);
+
+ // clear map, reflected in values
+ resetFull();
+ keySet = map.keySet();
+ assertTrue(map.size() > 0);
+ assertTrue(keySet.size() > 0);
+ map.clear();
+ assertTrue(map.size() == 0);
+ assertTrue(keySet.size() == 0);
+ }
+
+ /**
+ * Tests that the {@link Map#entrySet()} collection is backed by
+ * the underlying map for clear().
+ */
+ public void testEntrySetClearChangesMap() {
+ if (!isRemoveSupported()) return;
+
+ // clear values, reflected in map
+ resetFull();
+ Set entrySet = map.entrySet();
+ assertTrue(map.size() > 0);
+ assertTrue(entrySet.size() > 0);
+ entrySet.clear();
+ assertTrue(map.size() == 0);
+ assertTrue(entrySet.size() == 0);
+
+ // clear map, reflected in values
+ resetFull();
+ entrySet = map.entrySet();
+ assertTrue(map.size() > 0);
+ assertTrue(entrySet.size() > 0);
+ map.clear();
+ assertTrue(map.size() == 0);
+ assertTrue(entrySet.size() == 0);
+ }
+
+ //-----------------------------------------------------------------------
+ public void testEntrySetContains1() {
+ resetFull();
+ Set entrySet = map.entrySet();
+ Map.Entry entry = (Map.Entry) entrySet.iterator().next();
+ assertEquals(true, entrySet.contains(entry));
+ }
+ public void testEntrySetContains2() {
+ resetFull();
+ Set entrySet = map.entrySet();
+ Map.Entry entry = (Map.Entry) entrySet.iterator().next();
+ Map.Entry test = cloneMapEntry(entry);
+ assertEquals(true, entrySet.contains(test));
+ }
+ public void testEntrySetContains3() {
+ resetFull();
+ Set entrySet = map.entrySet();
+ Map.Entry entry = (Map.Entry) entrySet.iterator().next();
+ HashMap temp = new HashMap();
+ temp.put(entry.getKey(), "A VERY DIFFERENT VALUE");
+ Map.Entry test = (Map.Entry) temp.entrySet().iterator().next();
+ assertEquals(false, entrySet.contains(test));
+ }
+
+ public void testEntrySetRemove1() {
+ if (!isRemoveSupported()) return;
+ resetFull();
+ int size = map.size();
+ Set entrySet = map.entrySet();
+ Map.Entry entry = (Map.Entry) entrySet.iterator().next();
+ Object key = entry.getKey();
+
+ assertEquals(true, entrySet.remove(entry));
+ assertEquals(false, map.containsKey(key));
+ assertEquals(size - 1, map.size());
+ }
+ public void testEntrySetRemove2() {
+ if (!isRemoveSupported()) return;
+ resetFull();
+ int size = map.size();
+ Set entrySet = map.entrySet();
+ Map.Entry entry = (Map.Entry) entrySet.iterator().next();
+ Object key = entry.getKey();
+ Map.Entry test = cloneMapEntry(entry);
+
+ assertEquals(true, entrySet.remove(test));
+ assertEquals(false, map.containsKey(key));
+ assertEquals(size - 1, map.size());
+ }
+ public void testEntrySetRemove3() {
+ if (!isRemoveSupported()) return;
+ resetFull();
+ int size = map.size();
+ Set entrySet = map.entrySet();
+ Map.Entry entry = (Map.Entry) entrySet.iterator().next();
+ Object key = entry.getKey();
+ HashMap temp = new HashMap();
+ temp.put(entry.getKey(), "A VERY DIFFERENT VALUE");
+ Map.Entry test = (Map.Entry) temp.entrySet().iterator().next();
+
+ assertEquals(false, entrySet.remove(test));
+ assertEquals(true, map.containsKey(key));
+ assertEquals(size, map.size());
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Tests that the {@link Map#values} collection is backed by
+ * the underlying map by removing from the values collection
+ * and testing if the value was removed from the map.
+ * <p>
+ * We should really test the "vice versa" case--that values removed
+ * from the map are removed from the values collection--also,
+ * but that's a more difficult test to construct (lacking a
+ * "removeValue" method.)
+ * </p>
+ * <p>
+ * See bug <a href="http://issues.apache.org/bugzilla/show_bug.cgi?id=9573">
+ * 9573</a>.
+ * </p>
+ */
+ public void testValuesRemoveChangesMap() {
+ resetFull();
+ Object[] sampleValues = getSampleValues();
+ Collection values = map.values();
+ for (int i = 0; i < sampleValues.length; i++) {
+ if (map.containsValue(sampleValues[i])) {
+ int j = 0; // loop counter prevents infinite loops when remove is broken
+ while (values.contains(sampleValues[i]) && j < 10000) {
+ try {
+ values.remove(sampleValues[i]);
+ } catch (UnsupportedOperationException e) {
+ // if values.remove is unsupported, just skip this test
+ return;
+ }
+ j++;
+ }
+ assertTrue("values().remove(obj) is broken", j < 10000);
+ assertTrue(
+ "Value should have been removed from the underlying map.",
+ !map.containsValue(sampleValues[i]));
+ }
+ }
+ }
+
+ /**
+ * Tests that the {@link Map#keySet} set is backed by
+ * the underlying map by removing from the keySet set
+ * and testing if the key was removed from the map.
+ */
+ public void testKeySetRemoveChangesMap() {
+ resetFull();
+ Object[] sampleKeys = getSampleKeys();
+ Set keys = map.keySet();
+ for (int i = 0; i < sampleKeys.length; i++) {
+ try {
+ keys.remove(sampleKeys[i]);
+ } catch (UnsupportedOperationException e) {
+ // if key.remove is unsupported, just skip this test
+ return;
+ }
+ assertTrue(
+ "Key should have been removed from the underlying map.",
+ !map.containsKey(sampleKeys[i]));
+ }
+ }
+
+ // TODO: Need:
+ // testValuesRemovedFromEntrySetAreRemovedFromMap
+ // same for EntrySet/KeySet/values's
+ // Iterator.remove, removeAll, retainAll
+
+
+ /**
+ * Utility methods to create an array of Map.Entry objects
+ * out of the given key and value arrays.<P>
+ *
+ * @param keys the array of keys
+ * @param values the array of values
+ * @return an array of Map.Entry of those keys to those values
+ */
+ private Map.Entry[] makeEntryArray(Object[] keys, Object[] values) {
+ Map.Entry[] result = new Map.Entry[keys.length];
+ for (int i = 0; i < keys.length; i++) {
+ Map map = makeConfirmedMap();
+ map.put(keys[i], values[i]);
+ result[i] = (Map.Entry) map.entrySet().iterator().next();
+ }
+ return result;
+ }
+
+
+ /**
+ * Bulk test {@link Map#entrySet()}. This method runs through all of
+ * the tests in {@link AbstractTestSet}.
+ * After modification operations, {@link #verify()} is invoked to ensure
+ * that the map and the other collection views are still valid.
+ *
+ * @return a {@link AbstractTestSet} instance for testing the map's entry set
+ */
+ public BulkTest bulkTestMapEntrySet() {
+ return new TestMapEntrySet();
+ }
+
+ public class TestMapEntrySet extends AbstractTestSet {
+ public TestMapEntrySet() {
+ super("MapEntrySet");
+ }
+
+ // Have to implement manually; entrySet doesn't support addAll
+ public Object[] getFullElements() {
+ Object[] k = getSampleKeys();
+ Object[] v = getSampleValues();
+ return makeEntryArray(k, v);
+ }
+
+ // Have to implement manually; entrySet doesn't support addAll
+ public Object[] getOtherElements() {
+ Object[] k = getOtherKeys();
+ Object[] v = getOtherValues();
+ return makeEntryArray(k, v);
+ }
+
+ public Set makeEmptySet() {
+ return makeEmptyMap().entrySet();
+ }
+
+ public Set makeFullSet() {
+ return makeFullMap().entrySet();
+ }
+
+ public boolean isAddSupported() {
+ // Collection views don't support add operations.
+ return false;
+ }
+ public boolean isRemoveSupported() {
+ // Entry set should only support remove if map does
+ return AbstractTestMap.this.isRemoveSupported();
+ }
+ public boolean isGetStructuralModify() {
+ return AbstractTestMap.this.isGetStructuralModify();
+ }
+ public boolean isTestSerialization() {
+ return false;
+ }
+
+ public void resetFull() {
+ AbstractTestMap.this.resetFull();
+ collection = map.entrySet();
+ TestMapEntrySet.this.confirmed = AbstractTestMap.this.confirmed.entrySet();
+ }
+
+ public void resetEmpty() {
+ AbstractTestMap.this.resetEmpty();
+ collection = map.entrySet();
+ TestMapEntrySet.this.confirmed = AbstractTestMap.this.confirmed.entrySet();
+ }
+
+ public void testMapEntrySetIteratorEntry() {
+ resetFull();
+ Iterator it = collection.iterator();
+ int count = 0;
+ while (it.hasNext()) {
+ Map.Entry entry = (Map.Entry) it.next();
+ assertEquals(true, AbstractTestMap.this.map.containsKey(entry.getKey()));
+ assertEquals(true, AbstractTestMap.this.map.containsValue(entry.getValue()));
+ if (isGetStructuralModify() == false) {
+ assertEquals(AbstractTestMap.this.map.get(entry.getKey()), entry.getValue());
+ }
+ count++;
+ }
+ assertEquals(collection.size(), count);
+ }
+
+ public void testMapEntrySetIteratorEntrySetValue() {
+ Object key1 = getSampleKeys()[0];
+ Object key2 = (getSampleKeys().length ==1 ? getSampleKeys()[0] : getSampleKeys()[1]);
+ Object newValue1 = getNewSampleValues()[0];
+ Object newValue2 = (getNewSampleValues().length ==1 ? getNewSampleValues()[0] : getNewSampleValues()[1]);
+
+ resetFull();
+ // explicitly get entries as sample values/keys are connected for some maps
+ // such as BeanMap
+ Iterator it = TestMapEntrySet.this.collection.iterator();
+ Map.Entry entry1 = getEntry(it, key1);
+ it = TestMapEntrySet.this.collection.iterator();
+ Map.Entry entry2 = getEntry(it, key2);
+ Iterator itConfirmed = TestMapEntrySet.this.confirmed.iterator();
+ Map.Entry entryConfirmed1 = getEntry(itConfirmed, key1);
+ itConfirmed = TestMapEntrySet.this.confirmed.iterator();
+ Map.Entry entryConfirmed2 = getEntry(itConfirmed, key2);
+ verify();
+
+ if (isSetValueSupported() == false) {
+ try {
+ entry1.setValue(newValue1);
+ } catch (UnsupportedOperationException ex) {
+ }
+ return;
+ }
+
+ entry1.setValue(newValue1);
+ entryConfirmed1.setValue(newValue1);
+ assertEquals(newValue1, entry1.getValue());
+ assertEquals(true, AbstractTestMap.this.map.containsKey(entry1.getKey()));
+ assertEquals(true, AbstractTestMap.this.map.containsValue(newValue1));
+ assertEquals(newValue1, AbstractTestMap.this.map.get(entry1.getKey()));
+ verify();
+
+ entry1.setValue(newValue1);
+ entryConfirmed1.setValue(newValue1);
+ assertEquals(newValue1, entry1.getValue());
+ assertEquals(true, AbstractTestMap.this.map.containsKey(entry1.getKey()));
+ assertEquals(true, AbstractTestMap.this.map.containsValue(newValue1));
+ assertEquals(newValue1, AbstractTestMap.this.map.get(entry1.getKey()));
+ verify();
+
+ entry2.setValue(newValue2);
+ entryConfirmed2.setValue(newValue2);
+ assertEquals(newValue2, entry2.getValue());
+ assertEquals(true, AbstractTestMap.this.map.containsKey(entry2.getKey()));
+ assertEquals(true, AbstractTestMap.this.map.containsValue(newValue2));
+ assertEquals(newValue2, AbstractTestMap.this.map.get(entry2.getKey()));
+ verify();
+ }
+
+ public Map.Entry getEntry(Iterator itConfirmed, Object key) {
+ Map.Entry entry = null;
+ while (itConfirmed.hasNext()) {
+ Map.Entry temp = (Map.Entry) itConfirmed.next();
+ if (temp.getKey() == null) {
+ if (key == null) {
+ entry = temp;
+ break;
+ }
+ } else if (temp.getKey().equals(key)) {
+ entry = temp;
+ break;
+ }
+ }
+ assertNotNull("No matching entry in map for key '" + key + "'", entry);
+ return entry;
+ }
+
+ public void testMapEntrySetRemoveNonMapEntry() {
+ if (isRemoveSupported() == false) return;
+ resetFull();
+ assertEquals(false, getSet().remove(null));
+ assertEquals(false, getSet().remove(new Object()));
+ }
+
+ public void verify() {
+ super.verify();
+ AbstractTestMap.this.verify();
+ }
+ }
+
+
+ /**
+ * Bulk test {@link Map#keySet()}. This method runs through all of
+ * the tests in {@link AbstractTestSet}.
+ * After modification operations, {@link #verify()} is invoked to ensure
+ * that the map and the other collection views are still valid.
+ *
+ * @return a {@link AbstractTestSet} instance for testing the map's key set
+ */
+ public BulkTest bulkTestMapKeySet() {
+ return new TestMapKeySet();
+ }
+
+ public class TestMapKeySet extends AbstractTestSet {
+ public TestMapKeySet() {
+ super("");
+ }
+ public Object[] getFullElements() {
+ return getSampleKeys();
+ }
+
+ public Object[] getOtherElements() {
+ return getOtherKeys();
+ }
+
+ public Set makeEmptySet() {
+ return makeEmptyMap().keySet();
+ }
+
+ public Set makeFullSet() {
+ return makeFullMap().keySet();
+ }
+
+ public boolean isNullSupported() {
+ return AbstractTestMap.this.isAllowNullKey();
+ }
+ public boolean isAddSupported() {
+ return false;
+ }
+ public boolean isRemoveSupported() {
+ return AbstractTestMap.this.isRemoveSupported();
+ }
+ public boolean isTestSerialization() {
+ return false;
+ }
+
+ public void resetEmpty() {
+ AbstractTestMap.this.resetEmpty();
+ collection = map.keySet();
+ TestMapKeySet.this.confirmed = AbstractTestMap.this.confirmed.keySet();
+ }
+
+ public void resetFull() {
+ AbstractTestMap.this.resetFull();
+ collection = map.keySet();
+ TestMapKeySet.this.confirmed = AbstractTestMap.this.confirmed.keySet();
+ }
+
+ public void verify() {
+ super.verify();
+ AbstractTestMap.this.verify();
+ }
+ }
+
+
+ /**
+ * Bulk test {@link Map#values()}. This method runs through all of
+ * the tests in {@link AbstractTestCollection}.
+ * After modification operations, {@link #verify()} is invoked to ensure
+ * that the map and the other collection views are still valid.
+ *
+ * @return a {@link AbstractTestCollection} instance for testing the map's
+ * values collection
+ */
+ public BulkTest bulkTestMapValues() {
+ return new TestMapValues();
+ }
+
+ public class TestMapValues extends AbstractTestCollection {
+ public TestMapValues() {
+ super("");
+ }
+
+ public Object[] getFullElements() {
+ return getSampleValues();
+ }
+
+ public Object[] getOtherElements() {
+ return getOtherValues();
+ }
+
+ public Collection makeCollection() {
+ return makeEmptyMap().values();
+ }
+
+ public Collection makeFullCollection() {
+ return makeFullMap().values();
+ }
+
+ public boolean isNullSupported() {
+ return AbstractTestMap.this.isAllowNullKey();
+ }
+ public boolean isAddSupported() {
+ return false;
+ }
+ public boolean isRemoveSupported() {
+ return AbstractTestMap.this.isRemoveSupported();
+ }
+ public boolean isTestSerialization() {
+ return false;
+ }
+
+ public boolean areEqualElementsDistinguishable() {
+ // equal values are associated with different keys, so they are
+ // distinguishable.
+ return true;
+ }
+
+ public Collection makeConfirmedCollection() {
+ // never gets called, reset methods are overridden
+ return null;
+ }
+
+ public Collection makeConfirmedFullCollection() {
+ // never gets called, reset methods are overridden
+ return null;
+ }
+
+ public void resetFull() {
+ AbstractTestMap.this.resetFull();
+ collection = map.values();
+ TestMapValues.this.confirmed = AbstractTestMap.this.confirmed.values();
+ }
+
+ public void resetEmpty() {
+ AbstractTestMap.this.resetEmpty();
+ collection = map.values();
+ TestMapValues.this.confirmed = AbstractTestMap.this.confirmed.values();
+ }
+
+ public void verify() {
+ super.verify();
+ AbstractTestMap.this.verify();
+ }
+
+ // TODO: should test that a remove on the values collection view
+ // removes the proper mapping and not just any mapping that may have
+ // the value equal to the value returned from the values iterator.
+ }
+
+
+ /**
+ * Resets the {@link #map}, {@link #entrySet}, {@link #keySet},
+ * {@link #values} and {@link #confirmed} fields to empty.
+ */
+ public void resetEmpty() {
+ this.map = makeEmptyMap();
+ views();
+ this.confirmed = makeConfirmedMap();
+ }
+
+ /**
+ * Resets the {@link #map}, {@link #entrySet}, {@link #keySet},
+ * {@link #values} and {@link #confirmed} fields to full.
+ */
+ public void resetFull() {
+ this.map = makeFullMap();
+ views();
+ this.confirmed = makeConfirmedMap();
+ Object[] k = getSampleKeys();
+ Object[] v = getSampleValues();
+ for (int i = 0; i < k.length; i++) {
+ confirmed.put(k[i], v[i]);
+ }
+ }
+
+
+ /**
+ * Resets the collection view fields.
+ */
+ private void views() {
+ this.keySet = map.keySet();
+ this.values = map.values();
+ this.entrySet = map.entrySet();
+ }
+
+
+ /**
+ * Verifies that {@link #map} is still equal to {@link #confirmed}.
+ * This method checks that the map is equal to the HashMap,
+ * <I>and</I> that the map's collection views are still equal to
+ * the HashMap's collection views. An <Code>equals</Code> test
+ * is done on the maps and their collection views; their size and
+ * <Code>isEmpty</Code> results are compared; their hashCodes are
+ * compared; and <Code>containsAll</Code> tests are run on the
+ * collection views.
+ */
+ public void verify() {
+ verifyMap();
+ verifyEntrySet();
+ verifyKeySet();
+ verifyValues();
+ }
+
+ public void verifyMap() {
+ int size = confirmed.size();
+ boolean empty = confirmed.isEmpty();
+ assertEquals("Map should be same size as HashMap",
+ size, map.size());
+ assertEquals("Map should be empty if HashMap is",
+ empty, map.isEmpty());
+ assertEquals("hashCodes should be the same",
+ confirmed.hashCode(), map.hashCode());
+ // this fails for LRUMap because confirmed.equals() somehow modifies
+ // map, causing concurrent modification exceptions.
+ //assertEquals("Map should still equal HashMap", confirmed, map);
+ // this works though and performs the same verification:
+ assertTrue("Map should still equal HashMap", map.equals(confirmed));
+ // TODO: this should really be reexamined to figure out why LRU map
+ // behaves like it does (the equals shouldn't modify since all accesses
+ // by the confirmed collection should be through an iterator, thus not
+ // causing LRUMap to change).
+ }
+
+ public void verifyEntrySet() {
+ int size = confirmed.size();
+ boolean empty = confirmed.isEmpty();
+ assertEquals("entrySet should be same size as HashMap's" +
+ "\nTest: " + entrySet + "\nReal: " + confirmed.entrySet(),
+ size, entrySet.size());
+ assertEquals("entrySet should be empty if HashMap is" +
+ "\nTest: " + entrySet + "\nReal: " + confirmed.entrySet(),
+ empty, entrySet.isEmpty());
+ assertTrue("entrySet should contain all HashMap's elements" +
+ "\nTest: " + entrySet + "\nReal: " + confirmed.entrySet(),
+ entrySet.containsAll(confirmed.entrySet()));
+ assertEquals("entrySet hashCodes should be the same" +
+ "\nTest: " + entrySet + "\nReal: " + confirmed.entrySet(),
+ confirmed.entrySet().hashCode(), entrySet.hashCode());
+ assertEquals("Map's entry set should still equal HashMap's",
+ confirmed.entrySet(), entrySet);
+ }
+
+ public void verifyKeySet() {
+ int size = confirmed.size();
+ boolean empty = confirmed.isEmpty();
+ assertEquals("keySet should be same size as HashMap's" +
+ "\nTest: " + keySet + "\nReal: " + confirmed.keySet(),
+ size, keySet.size());
+ assertEquals("keySet should be empty if HashMap is" +
+ "\nTest: " + keySet + "\nReal: " + confirmed.keySet(),
+ empty, keySet.isEmpty());
+ assertTrue("keySet should contain all HashMap's elements" +
+ "\nTest: " + keySet + "\nReal: " + confirmed.keySet(),
+ keySet.containsAll(confirmed.keySet()));
+ assertEquals("keySet hashCodes should be the same" +
+ "\nTest: " + keySet + "\nReal: " + confirmed.keySet(),
+ confirmed.keySet().hashCode(), keySet.hashCode());
+ assertEquals("Map's key set should still equal HashMap's",
+ confirmed.keySet(), keySet);
+ }
+
+ public void verifyValues() {
+ List known = new ArrayList(confirmed.values());
+ List test = new ArrayList(values);
+
+ int size = confirmed.size();
+ boolean empty = confirmed.isEmpty();
+ assertEquals("values should be same size as HashMap's" +
+ "\nTest: " + test + "\nReal: " + known,
+ size, values.size());
+ assertEquals("values should be empty if HashMap is" +
+ "\nTest: " + test + "\nReal: " + known,
+ empty, values.isEmpty());
+ assertTrue("values should contain all HashMap's elements" +
+ "\nTest: " + test + "\nReal: " + known,
+ test.containsAll(known));
+ assertTrue("values should contain all HashMap's elements" +
+ "\nTest: " + test + "\nReal: " + known,
+ known.containsAll(test));
+ // originally coded to use a HashBag, but now separate jar so...
+ for (Iterator it = known.iterator(); it.hasNext();) {
+ boolean removed = test.remove(it.next());
+ assertTrue("Map's values should still equal HashMap's", removed);
+ }
+ assertTrue("Map's values should still equal HashMap's", test.isEmpty());
+ }
+
+
+ /**
+ * Erases any leftover instance variables by setting them to null.
+ */
+ public void tearDown() throws Exception {
+ map = null;
+ keySet = null;
+ entrySet = null;
+ values = null;
+ confirmed = null;
+ }
+
+}
diff --git a/dev/core/test/org/apache/commons/collections/map/TestIdentityMap.java b/dev/core/test/org/apache/commons/collections/map/TestIdentityMap.java
new file mode 100644
index 0000000..ed4b725
--- /dev/null
+++ b/dev/core/test/org/apache/commons/collections/map/TestIdentityMap.java
@@ -0,0 +1,146 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.map;
+
+import java.io.IOException;
+import java.io.Serializable;
+import java.util.Iterator;
+import java.util.Map;
+
+import junit.framework.Test;
+import junit.framework.TestSuite;
+import junit.textui.TestRunner;
+
+import org.apache.commons.collections.AbstractTestObject;
+import org.apache.commons.collections.IterableMap;
+
+/**
+ * JUnit tests.
+ *
+ * @version $Revision: 646780 $ $Date: 2008-04-10 13:48:07 +0100 (Thu, 10 Apr 2008) $
+ *
+ * @author Stephen Colebourne
+ */
+public class TestIdentityMap extends AbstractTestObject {
+
+ private static final Integer I1A = new Integer(1);
+ private static final Integer I1B = new Integer(1);
+ private static final Integer I2A = new Integer(2);
+ private static final Integer I2B = new Integer(2);
+
+ public TestIdentityMap(String testName) {
+ super(testName);
+ }
+
+ public static void main(String[] args) {
+ TestRunner.run(suite());
+ }
+
+ public static Test suite() {
+ return new TestSuite(TestIdentityMap.class);
+// return BulkTest.makeSuite(TestIdentityMap.class); // causes race condition!
+ }
+
+ public Object makeObject() {
+ return new IdentityMap();
+ }
+
+ public String getCompatibilityVersion() {
+ return "3";
+ }
+
+ //-----------------------------------------------------------------------
+ public void testBasics() {
+ IterableMap map = new IdentityMap();
+ assertEquals(0, map.size());
+
+ map.put(I1A, I2A);
+ assertEquals(1, map.size());
+ assertSame(I2A, map.get(I1A));
+ assertSame(null, map.get(I1B));
+ assertEquals(true, map.containsKey(I1A));
+ assertEquals(false, map.containsKey(I1B));
+ assertEquals(true, map.containsValue(I2A));
+ assertEquals(false, map.containsValue(I2B));
+
+ map.put(I1A, I2B);
+ assertEquals(1, map.size());
+ assertSame(I2B, map.get(I1A));
+ assertSame(null, map.get(I1B));
+ assertEquals(true, map.containsKey(I1A));
+ assertEquals(false, map.containsKey(I1B));
+ assertEquals(false, map.containsValue(I2A));
+ assertEquals(true, map.containsValue(I2B));
+
+ map.put(I1B, I2B);
+ assertEquals(2, map.size());
+ assertSame(I2B, map.get(I1A));
+ assertSame(I2B, map.get(I1B));
+ assertEquals(true, map.containsKey(I1A));
+ assertEquals(true, map.containsKey(I1B));
+ assertEquals(false, map.containsValue(I2A));
+ assertEquals(true, map.containsValue(I2B));
+ }
+
+ //-----------------------------------------------------------------------
+ public void testHashEntry() {
+ IterableMap map = new IdentityMap();
+
+ map.put(I1A, I2A);
+ map.put(I1B, I2A);
+
+ Map.Entry entry1 = (Map.Entry) map.entrySet().iterator().next();
+ Iterator it = map.entrySet().iterator();
+ Map.Entry entry2 = (Map.Entry) it.next();
+ Map.Entry entry3 = (Map.Entry) it.next();
+
+ assertEquals(true, entry1.equals(entry2));
+ assertEquals(true, entry2.equals(entry1));
+ assertEquals(false, entry1.equals(entry3));
+ }
+
+ /**
+ * Compare the current serialized form of the Map
+ * against the canonical version in CVS.
+ */
+ public void testEmptyMapCompatibility() throws IOException, ClassNotFoundException {
+ // test to make sure the canonical form has been preserved
+ Map map = (Map) makeObject();
+ if (map instanceof Serializable && !skipSerializedCanonicalTests()) {
+ Map map2 = (Map) readExternalFormFromDisk(getCanonicalEmptyCollectionName(map));
+ assertEquals("Map is empty", 0, map2.size());
+ }
+ }
+
+ public void testClone() {
+ IdentityMap map = new IdentityMap(10);
+ map.put("1", "1");
+ Map cloned = (Map) map.clone();
+ assertEquals(map.size(), cloned.size());
+ assertSame(map.get("1"), cloned.get("1"));
+ }
+
+// public void testCreate() throws Exception {
+// Map map = new IdentityMap();
+// writeExternalFormToDisk((java.io.Serializable) map, "D:/dev/collections/data/test/IdentityMap.emptyCollection.version3.obj");
+// map = new IdentityMap();
+// map.put(I1A, I2A);
+// map.put(I1B, I2A);
+// map.put(I2A, I2B);
+// writeExternalFormToDisk((java.io.Serializable) map, "D:/dev/collections/data/test/IdentityMap.fullCollection.version3.obj");
+// }
+}
diff --git a/dev/core/test/org/apache/commons/collections/set/AbstractTestSet.java b/dev/core/test/org/apache/commons/collections/set/AbstractTestSet.java
new file mode 100644
index 0000000..34d7330
--- /dev/null
+++ b/dev/core/test/org/apache/commons/collections/set/AbstractTestSet.java
@@ -0,0 +1,195 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.set;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+
+import org.apache.commons.collections.collection.AbstractTestCollection;
+
+/**
+ * Abstract test class for {@link Set} methods and contracts.
+ * <p>
+ * Since {@link Set} doesn't stipulate much new behavior that isn't already
+ * found in {@link Collection}, this class basically just adds tests for
+ * {@link Set#equals} and {@link Set#hashCode()} along with an updated
+ * {@link #verify()} that ensures elements do not appear more than once in the
+ * set.
+ * <p>
+ * To use, subclass and override the {@link #makeEmptySet()}
+ * method. You may have to override other protected methods if your
+ * set is not modifiable, or if your set restricts what kinds of
+ * elements may be added; see {@link AbstractTestCollection} for more details.
+ *
+ * @since Commons Collections 3.0
+ * @version $Revision: 646780 $ $Date: 2008-04-10 13:48:07 +0100 (Thu, 10 Apr 2008) $
+ *
+ * @author Paul Jack
+ */
+public abstract class AbstractTestSet extends AbstractTestCollection {
+
+ /**
+ * JUnit constructor.
+ *
+ * @param name name for test
+ */
+ public AbstractTestSet(String name) {
+ super(name);
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Provides additional verifications for sets.
+ */
+ public void verify() {
+ super.verify();
+
+ assertEquals("Sets should be equal", confirmed, collection);
+ assertEquals("Sets should have equal hashCodes",
+ confirmed.hashCode(), collection.hashCode());
+ Collection set = makeConfirmedCollection();
+ Iterator iterator = collection.iterator();
+ while (iterator.hasNext()) {
+ assertTrue("Set.iterator should only return unique elements",
+ set.add(iterator.next()));
+ }
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Set equals method is defined.
+ */
+ public boolean isEqualsCheckable() {
+ return true;
+ }
+
+ /**
+ * Returns an empty Set for use in modification testing.
+ *
+ * @return a confirmed empty collection
+ */
+ public Collection makeConfirmedCollection() {
+ return new HashSet();
+ }
+
+ /**
+ * Returns a full Set for use in modification testing.
+ *
+ * @return a confirmed full collection
+ */
+ public Collection makeConfirmedFullCollection() {
+ Collection set = makeConfirmedCollection();
+ set.addAll(Arrays.asList(getFullElements()));
+ return set;
+ }
+
+ /**
+ * Makes an empty set. The returned set should have no elements.
+ *
+ * @return an empty set
+ */
+ public abstract Set makeEmptySet();
+
+ /**
+ * Makes a full set by first creating an empty set and then adding
+ * all the elements returned by {@link #getFullElements()}.
+ *
+ * Override if your set does not support the add operation.
+ *
+ * @return a full set
+ */
+ public Set makeFullSet() {
+ Set set = makeEmptySet();
+ set.addAll(Arrays.asList(getFullElements()));
+ return set;
+ }
+
+ /**
+ * Makes an empty collection by invoking {@link #makeEmptySet()}.
+ *
+ * @return an empty collection
+ */
+ public final Collection makeCollection() {
+ return makeEmptySet();
+ }
+
+ /**
+ * Makes a full collection by invoking {@link #makeFullSet()}.
+ *
+ * @return a full collection
+ */
+ public final Collection makeFullCollection() {
+ return makeFullSet();
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Return the {@link AbstractTestCollection#collection} fixture, but cast as a Set.
+ */
+ public Set getSet() {
+ return (Set)collection;
+ }
+
+ /**
+ * Return the {@link AbstractTestCollection#confirmed} fixture, but cast as a Set.
+ */
+ public Set getConfirmedSet() {
+ return (Set)confirmed;
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Tests {@link Set#equals(Object)}.
+ */
+ public void testSetEquals() {
+ resetEmpty();
+ assertEquals("Empty sets should be equal",
+ getSet(), getConfirmedSet());
+ verify();
+
+ Collection set2 = makeConfirmedCollection();
+ set2.add("foo");
+ assertTrue("Empty set shouldn't equal nonempty set",
+ !getSet().equals(set2));
+
+ resetFull();
+ assertEquals("Full sets should be equal", getSet(), getConfirmedSet());
+ verify();
+
+ set2.clear();
+ set2.addAll(Arrays.asList(getOtherElements()));
+ assertTrue("Sets with different contents shouldn't be equal",
+ !getSet().equals(set2));
+ }
+
+ /**
+ * Tests {@link Set#hashCode()}.
+ */
+ public void testSetHashCode() {
+ resetEmpty();
+ assertEquals("Empty sets have equal hashCodes",
+ getSet().hashCode(), getConfirmedSet().hashCode());
+
+ resetFull();
+ assertEquals("Equal sets have equal hashCodes",
+ getSet().hashCode(), getConfirmedSet().hashCode());
+ }
+
+}
