Implemented LinkedList, with test code.
Patch by: jat (+me)
Review by: me
git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@2333 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/user/super/com/google/gwt/emul/java/util/AbstractList.java b/user/super/com/google/gwt/emul/java/util/AbstractList.java
index 78e13a8..4290f58 100644
--- a/user/super/com/google/gwt/emul/java/util/AbstractList.java
+++ b/user/super/com/google/gwt/emul/java/util/AbstractList.java
@@ -73,7 +73,7 @@
private ListIteratorImpl(int start) {
int size = AbstractList.this.size();
if (start < 0 || start > size) {
- AbstractList.this.indexOutOfBounds(start);
+ indexOutOfBounds(start, size);
}
i = start;
}
@@ -110,6 +110,19 @@
}
}
+ protected static void checkIndex(int index, int size) {
+ if (index < 0 || index >= size) {
+ indexOutOfBounds(index, size);
+ }
+ }
+
+ /**
+ * Throws an <code>indexOutOfBoundsException</code>.
+ */
+ protected static void indexOutOfBounds(int index, int size) {
+ throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
+ }
+
protected AbstractList() {
}
@@ -225,14 +238,6 @@
throw new UnsupportedOperationException("subList");
}
- /**
- * Throws an <code>indexOutOfBoundsException</code>.
- */
- protected void indexOutOfBounds(int i) {
- throw new IndexOutOfBoundsException("Index: " + i + ", Size: "
- + this.size());
- }
-
protected void removeRange(int fromIndex, int endIndex) {
ListIterator<E> iter = listIterator(fromIndex);
for (int i = fromIndex; i < endIndex; ++i) {
diff --git a/user/super/com/google/gwt/emul/java/util/ArrayList.java b/user/super/com/google/gwt/emul/java/util/ArrayList.java
index aaac930..10c2ad8 100644
--- a/user/super/com/google/gwt/emul/java/util/ArrayList.java
+++ b/user/super/com/google/gwt/emul/java/util/ArrayList.java
@@ -45,10 +45,6 @@
array.splice(index, 0, o);
}-*/;
- private static boolean equals(Object a, Object b) {
- return a == b || (a != null && a.equals(b));
- }
-
private static native <E> E getImpl(JavaScriptObject array, int index) /*-{
return array[index];
}-*/;
@@ -91,25 +87,26 @@
* There is no speed advantage to pre-allocating array sizes in JavaScript.
* This constructor is only present for compatibility with the JRE.
*/
+ @SuppressWarnings("unused")
public ArrayList(int ignoredInitialCapacity) {
}
@Override
- public void add(int index, E o) {
- if (index < 0 || index > size) {
- indexOutOfBounds(index);
- }
- addImpl(array, index, o);
- ++size;
- }
-
- @Override
public boolean add(E o) {
setImpl(array, size++, o);
return true;
}
@Override
+ public void add(int index, E o) {
+ if (index < 0 || index > size) {
+ indexOutOfBounds(index, size);
+ }
+ addImpl(array, index, o);
+ ++size;
+ }
+
+ @Override
public boolean addAll(Collection<? extends E> c) {
Iterator<? extends E> iter = c.iterator();
boolean changed = iter.hasNext();
@@ -135,11 +132,9 @@
@Override
public E get(int index) {
- if (index < 0 || index >= size) {
- indexOutOfBounds(index);
- }
+ checkIndex(index, size);
// implicit type arg not inferred (as of JDK 1.5.0_07)
- return ArrayList.<E>getImpl(array, index);
+ return ArrayList.<E> getImpl(array, index);
}
@Override
@@ -187,12 +182,6 @@
return size;
}
- @Override
- public List<E> subList(int fromIndex, int toIndex) {
- // TODO(jat): implement
- throw new UnsupportedOperationException("subList not implemented");
- }
-
/*
* Faster than the iterator-based implementation in AbstractCollection.
*/
@@ -203,7 +192,7 @@
}
for (int i = 0; i < size; ++i) {
// implicit type arg not inferred (as of JDK 1.5.0_07)
- a[i] = ArrayList.<T>getImpl(array, i);
+ a[i] = ArrayList.<T> getImpl(array, i);
}
if (a.length > size) {
a[size] = null;
@@ -212,18 +201,17 @@
}
/**
- * Currently ignored.
+ * Does nothing.
*/
public void trimToSize() {
- // TODO(jat): implement
}
protected int indexOf(Object o, int index) {
if (index < 0) {
- indexOutOfBounds(index);
+ indexOutOfBounds(index, size);
}
for (; index < size; ++index) {
- if (equals(o, getImpl(array, index))) {
+ if (Utility.equalsWithNullCheck(o, getImpl(array, index))) {
return index;
}
}
@@ -232,10 +220,10 @@
protected int lastIndexOf(Object o, int index) {
if (index >= size) {
- indexOutOfBounds(index);
+ indexOutOfBounds(index, size);
}
for (; index >= 0; --index) {
- if (equals(o, getImpl(array, index))) {
+ if (Utility.equalsWithNullCheck(o, getImpl(array, index))) {
return index;
}
}
@@ -244,11 +232,9 @@
@Override
protected void removeRange(int fromIndex, int endIndex) {
- if (fromIndex < 0 || fromIndex >= size) {
- indexOutOfBounds(fromIndex);
- }
+ checkIndex(fromIndex, size);
if (endIndex < fromIndex || endIndex > size) {
- indexOutOfBounds(endIndex);
+ indexOutOfBounds(endIndex, size);
}
int count = endIndex - fromIndex;
removeRangeImpl(array, fromIndex, count);
@@ -260,7 +246,7 @@
*/
protected void setSize(int newSize) {
if (newSize < 0) {
- indexOutOfBounds(newSize);
+ indexOutOfBounds(newSize, size);
}
setSizeImpl(array, newSize);
// null fill any new slots if size < newSize
@@ -271,6 +257,12 @@
size = newSize;
}
+ @SuppressWarnings("unused")
+ List<E> subListUnimplemented(int fromIndex, int toIndex) {
+ // TODO(jat): implement
+ throw new UnsupportedOperationException("subList not implemented");
+ }
+
private void clearImpl() {
array = JavaScriptObject.createArray();
size = 0;
diff --git a/user/super/com/google/gwt/emul/java/util/LinkedList.java b/user/super/com/google/gwt/emul/java/util/LinkedList.java
index e0ea1c8..b4d36f3 100644
--- a/user/super/com/google/gwt/emul/java/util/LinkedList.java
+++ b/user/super/com/google/gwt/emul/java/util/LinkedList.java
@@ -1,5 +1,5 @@
/*
- * Copyright 2007 Google Inc.
+ * Copyright 2008 Google Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License"); you may not
* use this file except in compliance with the License. You may obtain a copy of
@@ -25,11 +25,165 @@
* @param <E> element type.
*/
public class LinkedList<E> extends AbstractSequentialList<E> implements
- List<E>, Queue<E>, Cloneable, Serializable {
+ List<E>, Queue<E>, Serializable {
+ /*
+ * This implementation uses a doubly-linked circular list with a header node.
+ */
+
+ /**
+ * Implementation of ListIterator for linked lists.
+ */
+ private final class ListIteratorImpl implements ListIterator<E> {
+
+ /**
+ * The index to the current position.
+ */
+ protected int currentIndex;
+
+ /**
+ * Current node, to be returned from next.
+ */
+ protected Node<E> currentNode;
+
+ /**
+ * The last node returned from next/previous, or null if deleted or never
+ * called.
+ */
+ protected Node<E> lastNode = null;
+
+ /**
+ * @param index from the beginning of the list (0 = first node)
+ * @param startNode the initial current node
+ */
+ public ListIteratorImpl(int index, Node<E> startNode) {
+ currentNode = startNode;
+ currentIndex = index;
+ }
+
+ public void add(E o) {
+ addBefore(o, currentNode);
+ ++currentIndex;
+ lastNode = null;
+ }
+
+ public boolean hasNext() {
+ return currentNode != header;
+ }
+
+ public boolean hasPrevious() {
+ return currentNode.prev != header;
+ }
+
+ public E next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ lastNode = currentNode;
+ currentNode = currentNode.next;
+ ++currentIndex;
+ return lastNode.value;
+ }
+
+ public int nextIndex() {
+ return currentIndex;
+ }
+
+ public E previous() {
+ if (!hasPrevious()) {
+ throw new NoSuchElementException();
+ }
+ lastNode = currentNode = currentNode.prev;
+ --currentIndex;
+ return lastNode.value;
+ }
+
+ public int previousIndex() {
+ return currentIndex - 1;
+ }
+
+ public void remove() {
+ verifyCurrentElement();
+ if (currentNode == lastNode) {
+ // We just did a previous().
+ currentNode = lastNode.next;
+ } else {
+ // We just did a next().
+ --currentIndex;
+ }
+ lastNode.remove();
+ lastNode = null;
+ --size;
+ }
+
+ public void set(E o) {
+ verifyCurrentElement();
+ lastNode.value = o;
+ }
+
+ protected void verifyCurrentElement() {
+ if (lastNode == null) {
+ throw new IllegalStateException();
+ }
+ }
+ }
+
+ /**
+ * Internal class representing a doubly-linked list node.
+ *
+ * @param <E> element type
+ */
+ private static class Node<E> {
+ public Node<E> next;
+ public Node<E> prev;
+ public E value;
+
+ public Node() {
+ next = prev = this;
+ }
+
+ public Node(E value) {
+ this.value = value;
+ }
+
+ /**
+ * Construct a node containing a value and add it before the specified node.
+ *
+ * @param value
+ * @param nextNode
+ */
+ public Node(E value, Node<E> nextNode) {
+ this(value);
+ this.next = nextNode;
+ this.prev = nextNode.prev;
+ nextNode.prev.next = this;
+ nextNode.prev = this;
+ }
+
+ /**
+ * Remove this node from any list it is in, leaving it with circular
+ * references to itself.
+ */
+ public void remove() {
+ this.next.prev = this.prev;
+ this.prev.next = this.next;
+ this.next = this.prev = this;
+ }
+ }
+
+ /**
+ * Header node - header.next is the first element of the list, and header.prev
+ * is the last element of the list. If the list is empty, the header node will
+ * point to itself.
+ */
+ private Node<E> header;
+
+ /**
+ * Number of nodes currently present in the list.
+ */
+ private int size;
public LinkedList() {
- // TODO(jat): implement
- throw new UnsupportedOperationException("LinkedList unsupported");
+ clear();
}
public LinkedList(Collection<? extends E> c) {
@@ -39,38 +193,24 @@
@Override
public boolean add(E o) {
- // TODO(jat): implement
- return false;
- }
-
- @Override
- public boolean addAll(Collection<? extends E> c) {
- // TODO(jat): implement
- return false;
+ addLast(o);
+ return true;
}
public void addFirst(E o) {
- // TODO(jat): implement
+ new Node<E>(o, header.next);
+ ++size;
}
public void addLast(E o) {
- // TODO(jat): implement
+ new Node<E>(o, header);
+ ++size;
}
@Override
public void clear() {
- // TODO(jat): implement
- }
-
- public Object clone() {
- // TODO(jat): implement
- return null;
- }
-
- @Override
- public boolean contains(Object o) {
- // TODO(jat): implement
- return false;
+ header = new Node<E>();
+ size = 0;
}
public E element() {
@@ -78,31 +218,36 @@
}
public E getFirst() {
- // TODO(jat): implement
- return null;
+ throwEmptyException();
+ return header.next.value;
}
public E getLast() {
- // TODO(jat): implement
- return null;
+ throwEmptyException();
+ return header.prev.value;
}
@Override
- public int indexOf(Object o) {
- // TODO(jat): implement
- return 0;
- }
+ public ListIterator<E> listIterator(final int index) {
+ if (index < 0 || index > size) {
+ indexOutOfBounds(index, size);
+ }
- @Override
- public int lastIndexOf(Object o) {
- // TODO(jat): implement
- return 0;
- }
+ Node<E> node;
+ // start from the nearest end of the list
+ if (index >= size >> 1) {
+ node = header;
+ for (int i = size; i > index; --i) {
+ node = node.prev;
+ }
+ } else {
+ node = header.next;
+ for (int i = 0; i < index; ++i) {
+ node = node.next;
+ }
+ }
- @Override
- public ListIterator<E> listIterator(int index) {
- // TODO(jat): implement
- return null;
+ return new ListIteratorImpl(index, node);
}
public boolean offer(E o) {
@@ -110,7 +255,7 @@
}
public E peek() {
- if (size() == 0) {
+ if (size == 0) {
return null;
} else {
return getFirst();
@@ -118,7 +263,7 @@
}
public E poll() {
- if (size() == 0) {
+ if (size == 0) {
return null;
} else {
return removeFirst();
@@ -130,37 +275,43 @@
}
public E removeFirst() {
- // TODO(jat): implement
- return null;
+ throwEmptyException();
+ --size;
+ Node<E> node = header.next;
+ node.remove();
+ return node.value;
}
public E removeLast() {
- // TODO(jat): implement
- return null;
+ throwEmptyException();
+ --size;
+ Node<E> node = header.prev;
+ node.remove();
+ return node.value;
}
@Override
public int size() {
+ return size;
+ }
+
+ @SuppressWarnings("unused")
+ List<E> subListUnimplemented(final int fromIndex, final int toIndex) {
// TODO(jat): implement
- return 0;
+ throw new UnsupportedOperationException("subList not implemented");
}
- @Override
- public List<E> subList(int fromIndex, int toIndex) {
- // TODO Auto-generated method stub
- return null;
+ private void addBefore(E o, Node<E> target) {
+ new Node<E>(o, target);
+ ++size;
}
- @Override
- public Object[] toArray() {
- // TODO(jat): implement
- return null;
+ /**
+ * Throw an exception if the list is empty.
+ */
+ private void throwEmptyException() {
+ if (size == 0) {
+ throw new NoSuchElementException();
+ }
}
-
- @Override
- public <T> T[] toArray(T[] a) {
- // TODO(jat): implement
- return null;
- }
-
}
diff --git a/user/test/com/google/gwt/emultest/EmulSuite.java b/user/test/com/google/gwt/emultest/EmulSuite.java
index 462edbb..1f6ab21 100644
--- a/user/test/com/google/gwt/emultest/EmulSuite.java
+++ b/user/test/com/google/gwt/emultest/EmulSuite.java
@@ -39,6 +39,7 @@
import com.google.gwt.emultest.java.util.HashMapTest;
import com.google.gwt.emultest.java.util.HashSetTest;
import com.google.gwt.emultest.java.util.IdentityHashMapTest;
+import com.google.gwt.emultest.java.util.LinkedListTest;
import com.google.gwt.emultest.java.util.StackTest;
import com.google.gwt.junit.tools.GWTTestSuite;
@@ -79,6 +80,7 @@
suite.addTestSuite(HashMapTest.class);
suite.addTestSuite(HashSetTest.class);
suite.addTestSuite(IdentityHashMapTest.class);
+ suite.addTestSuite(LinkedListTest.class);
suite.addTestSuite(StackTest.class);
suite.addTest(TreeMapSuite.suite());
// $JUnit-END$
diff --git a/user/test/com/google/gwt/emultest/java/util/ArrayListTest.java b/user/test/com/google/gwt/emultest/java/util/ArrayListTest.java
index 7ab0b19..65fb249 100644
--- a/user/test/com/google/gwt/emultest/java/util/ArrayListTest.java
+++ b/user/test/com/google/gwt/emultest/java/util/ArrayListTest.java
@@ -1,221 +1,73 @@
-/*
- * Copyright 2006 Google Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License"); you may not
- * use this file except in compliance with the License. You may obtain a copy of
- * the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
- * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
- * License for the specific language governing permissions and limitations under
- * the License.
- */
-
-package com.google.gwt.emultest.java.util;
-
-import org.apache.commons.collections.TestArrayList;
-
-import java.util.ArrayList;
-import java.util.List;
-import java.util.ListIterator;
-
-/**
- * Tests ArrayList, and, by extension AbstractList. Uses inheritance to inherit
- * all of Apache's TestList and TestCollection.
- */
-public class ArrayListTest extends TestArrayList {
-
- private static final class ArrayListWithRemoveRange extends ArrayList {
- public void removeRange(int fromIndex, int toIndex) {
- super.removeRange(fromIndex, toIndex);
- }
- }
-
- public ArrayListTest() {
- }
-
- public void testAddWatch() {
- ArrayList s = new ArrayList();
- s.add("watch");
- assertEquals(s.get(0), "watch");
- }
-
- public void testListIteratorAddInSeveralPositions() {
- ArrayList l = new ArrayList();
- ListIterator i = l.listIterator();
- l.add(new Integer(0));
- for (int n = 2; n < 5; n += 2) {
- l.add(new Integer(n));
- }
- i = l.listIterator();
- i.next();
- i.add(new Integer(1));
- i.next();
- i.next();
- i.previous();
- i.add(new Integer(3));
- i.next();
- i.add(new Integer(5));
- i.add(new Integer(6));
- for (int n = 0; n < 6; n++) {
- assertEquals(new Integer(n), l.get(n));
- }
- }
-
- public void testListIteratorCreateInvalid() {
- ArrayList l = new ArrayList();
- l.add(new Integer(1));
- l.listIterator(0);
- try {
- l.listIterator(1);
- } catch (IndexOutOfBoundsException e) {
- // expected
- }
- try {
- l.listIterator(-1);
- } catch (IndexOutOfBoundsException e) {
- // expected
- }
- }
-
- public void testListIteratorHasNextHasPreviousAndIndexes() {
- List l = new ArrayList();
- ListIterator i = l.listIterator();
- assertFalse(i.hasNext());
- assertFalse(i.hasPrevious());
- i.add(new Integer(1));
- assertEquals(1, i.nextIndex());
- assertEquals(0, i.previousIndex());
- i = l.listIterator();
- assertEquals(0, i.nextIndex());
- assertEquals(-1, i.previousIndex());
- assertTrue(i.hasNext());
- assertFalse(i.hasPrevious());
- i.next();
- assertEquals(1, i.nextIndex());
- assertEquals(0, i.previousIndex());
- assertFalse(i.hasNext());
- assertTrue(i.hasPrevious());
- }
-
- public void testListIteratorSetInSeveralPositions() {
- ArrayList l = new ArrayList();
- for (int n = 0; n < 5; n += 2) {
- l.add(new Integer(n));
- }
- l.listIterator();
- for (int n = 0; n < 3; n++) {
- l.set(n, new Integer(n));
- }
- for (int n = 0; n < 3; n++) {
- assertEquals(new Integer(n), l.get(n));
- }
- }
-
- public void testRemoveRange() {
- ArrayListWithRemoveRange l = new ArrayListWithRemoveRange();
- for (int i = 0; i < 10; i++) {
- l.add(new Integer(i));
- }
- try {
- l.removeRange(-1, 1);
- fail();
- } catch (IndexOutOfBoundsException expected) {
- }
-
- try {
- l.removeRange(2, 1);
- fail();
- } catch (IndexOutOfBoundsException expected) {
- }
-
- try {
- l.removeRange(2, 11);
- fail();
- } catch (IndexOutOfBoundsException expected) {
- }
-
- l.removeRange(3, 5);
- assertEquals(8, l.size());
- for (int i = 0; i < 3; i++) {
- Integer elem = (Integer) l.get(i);
- assertEquals(i, elem.intValue());
- }
- for (int i = 3; i < 8; i++) {
- Integer elem = (Integer) l.get(i);
- assertEquals(i + 2, elem.intValue());
- }
- }
-
- public void testToArray() {
- ArrayList l = new ArrayList();
- for (int i = 0; i < 10; i++) {
- l.add(new Integer(i));
- }
-
- {
- Object[] objArray = l.toArray();
- assertEquals(10, objArray.length);
- for (int i = 0; i < 10; i++) {
- Integer elem = (Integer) objArray[i];
- assertEquals(i, elem.intValue());
- }
- // should not cause ArrayStore
- objArray[0] = new Object();
- }
-
- {
- Integer[] firstArray = new Integer[13];
- firstArray[10] = new Integer(10);
- firstArray[11] = new Integer(11);
- firstArray[12] = new Integer(12);
- Integer[] intArray = (Integer[]) l.toArray(firstArray);
- assertTrue(firstArray == intArray);
- assertEquals(13, intArray.length);
- for (int i = 0; i < 13; i++) {
- if (i == 10) {
- assertNull(intArray[i]);
- } else {
- Integer elem = intArray[i];
- assertEquals(i, elem.intValue());
- }
- }
- try {
- Object[] objArray = noOptimizeFalse() ? new Object[1] : intArray;
- assertTrue(objArray instanceof Integer[]);
- objArray[0] = new Object();
- fail("expected ArrayStoreException");
- } catch (ArrayStoreException e) {
- }
- }
-
- {
- Integer[] firstArray = new Integer[0];
- Integer[] intArray = (Integer[]) l.toArray(firstArray);
- assertFalse(firstArray == intArray);
- assertEquals(10, intArray.length);
- for (int i = 0; i < 10; i++) {
- Integer elem = intArray[i];
- assertEquals(i, elem.intValue());
- }
- try {
- Object[] objArray = noOptimizeFalse() ? new Object[1] : intArray;
- assertTrue(objArray instanceof Integer[]);
- objArray[0] = new Object();
- fail("expected ArrayStoreException");
- } catch (ArrayStoreException e) {
- }
- }
- }
-
- protected List makeEmptyList() {
- return new ArrayList();
- }
-
- private static native boolean noOptimizeFalse() /*-{
- return false;
- }-*/;
-}
+/*
+ * Copyright 2008 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.emultest.java.util;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Tests ArrayList class (and by extension, AbstractList).
+ */
+@SuppressWarnings("unchecked")
+public class ArrayListTest extends ListTestBase {
+
+ private static final class ArrayListWithRemoveRange extends ArrayList {
+ @Override
+ public void removeRange(int fromIndex, int toIndex) {
+ super.removeRange(fromIndex, toIndex);
+ }
+ }
+
+ public void testRemoveRange() {
+ ArrayListWithRemoveRange l = new ArrayListWithRemoveRange();
+ for (int i = 0; i < 10; i++) {
+ l.add(new Integer(i));
+ }
+ try {
+ l.removeRange(-1, 1);
+ fail();
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ try {
+ l.removeRange(2, 1);
+ fail();
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ try {
+ l.removeRange(2, 11);
+ fail();
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ l.removeRange(3, 5);
+ assertEquals(8, l.size());
+ for (int i = 0; i < 3; i++) {
+ Integer elem = (Integer) l.get(i);
+ assertEquals(i, elem.intValue());
+ }
+ for (int i = 3; i < 8; i++) {
+ Integer elem = (Integer) l.get(i);
+ assertEquals(i + 2, elem.intValue());
+ }
+ }
+
+ @Override
+ protected List makeEmptyList() {
+ return new ArrayList();
+ }
+}
diff --git a/user/test/com/google/gwt/emultest/java/util/LinkedListTest.java b/user/test/com/google/gwt/emultest/java/util/LinkedListTest.java
new file mode 100644
index 0000000..8662f09
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/java/util/LinkedListTest.java
@@ -0,0 +1,122 @@
+/*
+ * Copyright 2008 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.emultest.java.util;
+
+import java.util.LinkedList;
+import java.util.List;
+import java.util.NoSuchElementException;
+
+/**
+ * Test LinkedList class.
+ */
+@SuppressWarnings("unchecked")
+public class LinkedListTest extends ListTestBase {
+
+ private static final class LinkedListWithRemoveRange extends LinkedList {
+ @Override
+ public void removeRange(int fromIndex, int toIndex) {
+ super.removeRange(fromIndex, toIndex);
+ }
+ }
+
+ public void testAddFirst() {
+ // TODO(jat): implement
+ }
+
+ public void testAddLast() {
+ // TODO(jat): implement
+ }
+
+ public void testElement() {
+ // TODO(jat): implement
+ }
+
+ public void testGetFirst() {
+ // TODO(jat): implement
+ }
+
+ public void testGetLast() {
+ // TODO(jat): implement
+ }
+
+ public void testOffer() {
+ // TODO(jat): implement
+ }
+
+ public void testPeek() {
+ // TODO(jat): implement
+ }
+
+ public void testPoll() {
+ // TODO(jat): implement
+ }
+
+ public void testRemove() {
+ // TODO(jat): implement
+ }
+
+ public void testRemoveFirst() {
+ // TODO(jat): implement
+ }
+
+ public void testRemoveLast() {
+ // TODO(jat): implement
+ }
+
+ public void testRemoveRange() {
+ LinkedListWithRemoveRange l = new LinkedListWithRemoveRange();
+ for (int i = 0; i < 10; i++) {
+ l.add(new Integer(i));
+ }
+ try {
+ l.removeRange(-1, 1);
+ fail();
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ try {
+ l.removeRange(2, 11);
+ fail();
+ } catch (NoSuchElementException expected) {
+ }
+
+ assertEquals(2, l.size());
+ for (int i = 0; i < 2; i++) {
+ Integer elem = (Integer) l.get(i);
+ assertEquals(i, elem.intValue());
+ }
+
+ for (int i = 2; i < 10; i++) {
+ l.add(new Integer(i));
+ }
+
+ l.removeRange(3, 5);
+ assertEquals(8, l.size());
+ for (int i = 0; i < 3; i++) {
+ Integer elem = (Integer) l.get(i);
+ assertEquals(i, elem.intValue());
+ }
+ for (int i = 3; i < 8; i++) {
+ Integer elem = (Integer) l.get(i);
+ assertEquals(i + 2, elem.intValue());
+ }
+ }
+
+ @Override
+ protected List makeEmptyList() {
+ return new LinkedList();
+ }
+}
diff --git a/user/test/com/google/gwt/emultest/java/util/ListTestBase.java b/user/test/com/google/gwt/emultest/java/util/ListTestBase.java
new file mode 100644
index 0000000..756ca47
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/java/util/ListTestBase.java
@@ -0,0 +1,174 @@
+/*
+ * Copyright 2008 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.emultest.java.util;
+
+import org.apache.commons.collections.TestArrayList;
+
+import java.util.List;
+import java.util.ListIterator;
+
+/**
+ * Tests List, and, by extension AbstractList. Uses inheritance to inherit all
+ * of Apache's TestList and TestCollection.
+ */
+@SuppressWarnings("unchecked")
+public abstract class ListTestBase extends TestArrayList {
+
+ private static volatile boolean NO_OPTIMIZE_FALSE = false;
+
+ public void testAddWatch() {
+ List s = makeEmptyList();
+ s.add("watch");
+ assertEquals(s.get(0), "watch");
+ }
+
+ public void testListIteratorAddInSeveralPositions() {
+ List l = makeEmptyList();
+ ListIterator i = l.listIterator();
+ l.add(new Integer(0));
+ for (int n = 2; n < 5; n += 2) {
+ l.add(new Integer(n));
+ }
+ i = l.listIterator();
+ i.next();
+ i.add(new Integer(1));
+ i.next();
+ i.next();
+ i.previous();
+ i.add(new Integer(3));
+ i.next();
+ i.add(new Integer(5));
+ i.add(new Integer(6));
+ for (int n = 0; n < 6; n++) {
+ assertEquals(new Integer(n), l.get(n));
+ }
+ }
+
+ public void testListIteratorCreateInvalid() {
+ List l = makeEmptyList();
+ l.add(new Integer(1));
+ l.listIterator(0);
+ try {
+ l.listIterator(1);
+ } catch (IndexOutOfBoundsException e) {
+ // expected
+ }
+ try {
+ l.listIterator(-1);
+ } catch (IndexOutOfBoundsException e) {
+ // expected
+ }
+ }
+
+ public void testListIteratorHasNextHasPreviousAndIndexes() {
+ List l = makeEmptyList();
+ ListIterator i = l.listIterator();
+ assertFalse(i.hasNext());
+ assertFalse(i.hasPrevious());
+ i.add(new Integer(1));
+ assertEquals(1, i.nextIndex());
+ assertEquals(0, i.previousIndex());
+ i = l.listIterator();
+ assertEquals(0, i.nextIndex());
+ assertEquals(-1, i.previousIndex());
+ assertTrue(i.hasNext());
+ assertFalse(i.hasPrevious());
+ i.next();
+ assertEquals(1, i.nextIndex());
+ assertEquals(0, i.previousIndex());
+ assertFalse(i.hasNext());
+ assertTrue(i.hasPrevious());
+ }
+
+ public void testListIteratorSetInSeveralPositions() {
+ List l = makeEmptyList();
+ for (int n = 0; n < 5; n += 2) {
+ l.add(new Integer(n));
+ }
+ l.listIterator();
+ for (int n = 0; n < 3; n++) {
+ l.set(n, new Integer(n));
+ }
+ for (int n = 0; n < 3; n++) {
+ assertEquals(new Integer(n), l.get(n));
+ }
+ }
+
+ public void testListIteratorRemove() {
+ // TODO(jat): implement
+ }
+
+ public void testToArray() {
+ List l = makeEmptyList();
+ for (int i = 0; i < 10; i++) {
+ l.add(new Integer(i));
+ }
+
+ {
+ Object[] objArray = l.toArray();
+ assertEquals(10, objArray.length);
+ for (int i = 0; i < 10; i++) {
+ Integer elem = (Integer) objArray[i];
+ assertEquals(i, elem.intValue());
+ }
+ // should not cause ArrayStore
+ objArray[0] = new Object();
+ }
+
+ {
+ Integer[] firstArray = new Integer[13];
+ firstArray[10] = new Integer(10);
+ firstArray[11] = new Integer(11);
+ firstArray[12] = new Integer(12);
+ Integer[] intArray = (Integer[]) l.toArray(firstArray);
+ assertTrue(firstArray == intArray);
+ assertEquals(13, intArray.length);
+ for (int i = 0; i < 13; i++) {
+ if (i == 10) {
+ assertNull(intArray[i]);
+ } else {
+ Integer elem = intArray[i];
+ assertEquals(i, elem.intValue());
+ }
+ }
+ try {
+ Object[] objArray = NO_OPTIMIZE_FALSE ? new Object[1] : intArray;
+ assertTrue(objArray instanceof Integer[]);
+ objArray[0] = new Object();
+ fail("expected ArrayStoreException");
+ } catch (ArrayStoreException e) {
+ }
+ }
+
+ {
+ Integer[] firstArray = new Integer[0];
+ Integer[] intArray = (Integer[]) l.toArray(firstArray);
+ assertFalse(firstArray == intArray);
+ assertEquals(10, intArray.length);
+ for (int i = 0; i < 10; i++) {
+ Integer elem = intArray[i];
+ assertEquals(i, elem.intValue());
+ }
+ try {
+ Object[] objArray = NO_OPTIMIZE_FALSE ? new Object[1] : intArray;
+ assertTrue(objArray instanceof Integer[]);
+ objArray[0] = new Object();
+ fail("expected ArrayStoreException");
+ } catch (ArrayStoreException e) {
+ }
+ }
+ }
+}
diff --git a/user/test/org/apache/commons/collections/TestArrayList.java b/user/test/org/apache/commons/collections/TestArrayList.java
index 2e3ddb1..07ff0ab 100644
--- a/user/test/org/apache/commons/collections/TestArrayList.java
+++ b/user/test/org/apache/commons/collections/TestArrayList.java
@@ -13,8 +13,9 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
+// MODIFIED BY GOOGLE
package org.apache.commons.collections;
- import java.util.ArrayList;
+ import java.util.List;
/**
* @author <a href="mailto:jvanzyl@apache.org">Jason van Zyl</a>
@@ -24,8 +25,8 @@
{
-
- protected ArrayList list = (ArrayList)makeEmptyList();
+ // GOOGLE
+ protected List list = makeEmptyList();
public void testNewArrayList()
