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()