Rewrite of ArrayList.java
- Optimized ArrayList for the same operations the JRE version is optimized for
- Made the code simpler; removed as much JSNI as possible
- Some consistency stuff in AbstractList
- Added common functions to create a JS object/array on JavaScriptObject; using those from HashMap.java
- Also privitized HashMap & ArrayLists's clear implementation
Review by: knorton
git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@1212 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/user/src/com/google/gwt/core/client/JavaScriptObject.java b/user/src/com/google/gwt/core/client/JavaScriptObject.java
index abbb960..bd55e8d 100644
--- a/user/src/com/google/gwt/core/client/JavaScriptObject.java
+++ b/user/src/com/google/gwt/core/client/JavaScriptObject.java
@@ -29,6 +29,20 @@
*/
public class JavaScriptObject {
+ /**
+ * Returns a new array.
+ */
+ public static native JavaScriptObject createArray() /*-{
+ return [];
+ }-*/;
+
+ /**
+ * Returns a new object.
+ */
+ public static native JavaScriptObject createObject() /*-{
+ return {};
+ }-*/;
+
private static native boolean equalsImpl(JavaScriptObject o,
JavaScriptObject other) /*-{
return o === other;
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 cf3b05a..b810725 100644
--- a/user/super/com/google/gwt/emul/java/util/AbstractList.java
+++ b/user/super/com/google/gwt/emul/java/util/AbstractList.java
@@ -30,14 +30,14 @@
int i = 0, last = -1;
public boolean hasNext() {
- return i < size();
+ return i < AbstractList.this.size();
}
public Object next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
- return get(last = i++);
+ return AbstractList.this.get(last = i++);
}
public void remove() {
@@ -68,8 +68,7 @@
private ListIteratorImpl(int start) {
int size = AbstractList.this.size();
if (start < 0 || start > size) {
- throw new IndexOutOfBoundsException("Size: " + AbstractList.this.size()
- + " Index: " + i);
+ AbstractList.this.indexOutOfBounds(start);
}
i = start;
}
@@ -91,7 +90,7 @@
if (!hasPrevious()) {
throw new NoSuchElementException();
}
- return get(last = --i);
+ return AbstractList.this.get(last = --i);
}
public int previousIndex() {
@@ -208,6 +207,14 @@
throw new UnsupportedOperationException("set");
}
+ /**
+ * 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 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 0d11e3c..a01dc07 100644
--- a/user/super/com/google/gwt/emul/java/util/ArrayList.java
+++ b/user/super/com/google/gwt/emul/java/util/ArrayList.java
@@ -18,110 +18,103 @@
import com.google.gwt.core.client.JavaScriptObject;
/**
- * See Sun's JDK 1.4 documentation for documentation.
+ * See Sun's JDK 1.4 documentation for documentation.
*
- * Differences between this implementation and JDK 1.4 <code>ArrayList</code>
- * include capacity management and range checking.
- * <p>
- * <b>Capacity</b> There is no speed advantage to pre-allocating array sizes in
- * JavaScript, so this implementation does not include any of the capacity and
- * "growth increment" concepts in the standard ArrayList class. Although
- * <code>ArrayList(int)</code> accepts a value for the intitial capacity of
- * the array, this constructor simply delegates to <code>ArrayList()</code>.
- * It is only present for compatibility with JDK 1.4's API.
- * </p>
- * <p>
- * <b>Dual endedness</b> For increased performance, this implementation supports
- * constant time insertion and deletion from either end.
+ * This implementation differs from JDK 1.4 <code>ArrayList</code> in terms of
+ * capacity management. There is no speed advantage to pre-allocating array
+ * sizes in JavaScript, so this implementation does not include any of the
+ * capacity and "growth increment" concepts in the standard ArrayList class.
+ * Although <code>ArrayList(int)</code> accepts a value for the intitial
+ * capacity of the array, this constructor simply delegates to
+ * <code>ArrayList()</code>. It is only present for compatibility with JDK
+ * 1.4's API.
* </p>
*/
public class ArrayList extends AbstractList implements List, Cloneable,
RandomAccess {
- /*
- * Implementation notes:
- * Currently if one uses an ArrayList as a ring buffer, adding from one end,
- * and deleting from the other, the indexes will increase (or decrease)
- * without ever being normalized. Back of the envelope calculations
- * indicate that at 30 indexes per second, it will take a year of solid run
- * time to chew through the billion indexes needed to get into trouble.
- * Given that it seemed better not to rebalance than to charge everyone the
- * extra code size the rebalancing code would represent.
- */
- protected static boolean equals(Object a, Object b) {
- return (a == null ? b == null : a.equals(b));
- }
- /**
- * This field holds the javascript array, and is not private to avoid Eclipse
- * warnings.
+ private static native void addImpl(JavaScriptObject array, int index, Object o) /*-{
+ array.splice(index, 0, o);
+ }-*/;
+
+ private static boolean equals(Object a, Object b) {
+ return a == b || (a != null && a.equals(b));
+ }
+
+ private static native Object getImpl(JavaScriptObject array, int index) /*-{
+ return array[index];
+ }-*/;
+
+ private static native void removeRangeImpl(JavaScriptObject array, int index,
+ int count) /*-{
+ array.splice(index, count);
+ }-*/;
+
+ private static native void setImpl(JavaScriptObject array, int index, Object o) /*-{
+ array[index] = o;
+ }-*/;
+
+ private static native void setSizeImpl(JavaScriptObject array, int newSize) /*-{
+ array.length = newSize;
+ }-*/;
+
+ /**
+ * This field holds a JavaScript array.
*/
- transient JavaScriptObject array;
- /**
- * This field holds the last populated index of the array and is not private
- * to avoid Eclipse warnings.
+ private transient JavaScriptObject array;
+
+ /**
+ * The size of the array.
*/
- int endIndex;
- /**
- * This field holds the first populated index of the array and is not private
- * to avoid Eclipse warnings.
- */
- int startIndex;
+ private int size;
+
+ {
+ clearImpl();
+ }
public ArrayList() {
- initArray();
}
public ArrayList(Collection c) {
- initArray();
addAll(c);
}
/**
- * There is no speed advantage to pre-allocating array sizes in JavaScript,
- * so the <code>intialCapacity</code> parameter is ignored. This constructor is
+ * There is no speed advantage to pre-allocating array sizes in JavaScript, so
+ * the <code>intialCapacity</code> parameter is ignored. This constructor is
* only present for compatibility with JDK 1.4's API.
*/
public ArrayList(int initialCapacity) {
// initialCapacity is ignored in JS implementation; this constructor is
// present for JDK 1.4 compatibility
- this();
}
- public native void add(int index, Object o) /*-{
- var array = this.@java.util.ArrayList::array;
- var endIndex = this.@java.util.ArrayList::endIndex;
- var startIndex = this.@java.util.ArrayList::startIndex;
- // This if is not an else if to call attention to the early return.
- if (index + startIndex == endIndex) {
- // If we are at the end simply set the next element to hold the value.
- array[endIndex] = o;
- this.@java.util.ArrayList::endIndex++;
- return;
+ public void add(int index, Object o) {
+ if (index < 0 || index > size) {
+ indexOutOfBounds(index);
}
- if (index == 0) {
- // If we are adding at the beginning, simply set the new element, and
- // move the beginning back.
- array[--this.@java.util.ArrayList::startIndex] = o;
- return;
- }
-
- // Somewhere in the middle, so do range checking and the splice.
- // Range checking, must be more permissive since one can add off the end.
- this.@java.util.ArrayList::verifyIndexOneExtra(I)(index);
- array.splice(index + startIndex, 0, o);
- // The end of the array moved forward if we got here so record that.
- this.@java.util.ArrayList::endIndex++;
- }-*/;
+ addImpl(array, index, o);
+ ++size;
+ }
public boolean add(Object o) {
- add(size(),o);
+ setImpl(array, size++, o);
return true;
}
-
- public void clear() {
- setSize(0);
+
+ public boolean addAll(Collection c) {
+ Iterator iter = c.iterator();
+ boolean changed = iter.hasNext();
+ while (iter.hasNext()) {
+ setImpl(array, size++, iter.next());
+ }
+ return changed;
}
-
+
+ public void clear() {
+ clearImpl();
+ }
+
public Object clone() {
return new ArrayList(this);
}
@@ -129,30 +122,32 @@
public boolean contains(Object o) {
return (indexOf(o) != -1);
}
-
- public native Object get(int index) /*-{
- this.@java.util.ArrayList::verifyIndex(I)(index);
- var startIndex = this.@java.util.ArrayList::startIndex;
- return this.@java.util.ArrayList::array[index + startIndex];
- }-*/;
-
+
+ public Object get(int index) {
+ if (index < 0 || index >= size) {
+ indexOutOfBounds(index);
+ }
+ return getImpl(array, index);
+ }
+
public int indexOf(Object o) {
return indexOf(o, 0);
}
- public native boolean isEmpty() /*-{
- return (this.@java.util.ArrayList::endIndex == this.@java.util.ArrayList::startIndex);
- }-*/;
+ public boolean isEmpty() {
+ return size == 0;
+ }
public int lastIndexOf(Object o) {
- return lastIndexOf(o, size() - 1);
+ return lastIndexOf(o, size() - 1);
}
public Object remove(int index) {
- Object old = get(index);
- removeRange(index,index + 1);
- return old;
- }
+ Object previous = get(index);
+ removeRangeImpl(array, index, 1);
+ --size;
+ return previous;
+ }
public boolean remove(Object o) {
int i = indexOf(o);
@@ -163,127 +158,70 @@
return true;
}
- public native Object set(int index, Object o) /*-{
- this.@java.util.ArrayList::verifyIndex(I)(index);
- var array = this.@java.util.ArrayList::array;
- var startIndex = this.@java.util.ArrayList::startIndex;
- var old = array[index + startIndex];
- array[index + startIndex] = o;
- return old;
- }-*/;
-
- public native int size() /*-{
- return this.@java.util.ArrayList::endIndex - this.@java.util.ArrayList::startIndex;
- }-*/;
-
- protected native void removeRange(int fromIndex, int toIndex) /*-{
- this.@java.util.ArrayList::verifyIndexOneExtra(I)(fromIndex);
- this.@java.util.ArrayList::verifyIndexOneExtra(I)(toIndex);
- var array = this.@java.util.ArrayList::array;
- var startIndex = this.@java.util.ArrayList::startIndex;
- var endIndex = this.@java.util.ArrayList::endIndex;
- if (fromIndex == 0) {
- // Chop off the beginning.
- for (var i = startIndex; i < (toIndex + startIndex); i++) {
- delete array[i];
- }
- this.@java.util.ArrayList::startIndex += (toIndex - fromIndex);
- } else if (toIndex + startIndex == endIndex) {
- // Chop off the end.
- for (var i = (fromIndex + startIndex); i < endIndex; i++) {
- delete array[i];
- }
- this.@java.util.ArrayList::endIndex = (fromIndex + startIndex);
- } else {
- // Splice from the middle.
- var numToRemove = toIndex - fromIndex;
- array.splice(fromIndex + startIndex, numToRemove);
- this.@java.util.ArrayList::endIndex -= numToRemove;
- }
- }-*/;
-
- native int indexOf(Object o, int index) /*-{
- var array = this.@java.util.ArrayList::array;
- var startIndex = this.@java.util.ArrayList::startIndex;
- var i = index + startIndex;
- var endIndex = this.@java.util.ArrayList::endIndex;
- while (i < endIndex) {
- if (@java.util.ArrayList::equals(Ljava/lang/Object;Ljava/lang/Object;)(array[i],o)) {
- return i - startIndex;
- }
- ++i;
- }
- return -1;
- }-*/;
-
- /**
- * Throws an <code>indexOutOfBoundsException</code>, and is not
- * private to avoid eclipse warnings.
- */
- void indexOutOfBounds(int i) {
- throw new IndexOutOfBoundsException("Size: " + this.size() + " Index: " + i);
+ public Object set(int index, Object o) {
+ Object previous = get(index);
+ setImpl(array, index, o);
+ return previous;
}
-
- /**
- * Computes the last index of an element given an offset, and is
- * not private to avoid eclipse warnings.
- */
- native int lastIndexOf(Object o, int index) /*-{
- var array = this.@java.util.ArrayList::array;
- var startIndex = this.@java.util.ArrayList::startIndex;
- var i = index + startIndex;
- while (i >= startIndex) {
- if (@java.util.ArrayList::equals(Ljava/lang/Object;Ljava/lang/Object;)(array[i],o)) {
- return i - startIndex;
+
+ public int size() {
+ return size;
+ }
+
+ protected int indexOf(Object o, int index) {
+ if (index < 0) {
+ indexOutOfBounds(index);
+ }
+ for (; index < size; ++index) {
+ if (equals(o, getImpl(array, index))) {
+ return index;
}
- --i;
}
return -1;
- }-*/;
+ }
+
+ protected int lastIndexOf(Object o, int index) {
+ if (index >= size) {
+ indexOutOfBounds(index);
+ }
+ for (; index >= 0; --index) {
+ if (equals(o, getImpl(array, index))) {
+ return index;
+ }
+ }
+ return -1;
+ }
+
+ protected void removeRange(int fromIndex, int endIndex) {
+ if (fromIndex < 0 || fromIndex >= size) {
+ indexOutOfBounds(fromIndex);
+ }
+ if (endIndex < fromIndex || endIndex > size) {
+ indexOutOfBounds(endIndex);
+ }
+ int count = endIndex - fromIndex;
+ removeRangeImpl(array, fromIndex, count);
+ size -= count;
+ }
/**
- * This function sets the size of the array, and is used in Vector.
+ * This function sets the size of the array, and is used by Vector.
*/
- native void setSize(int newSize) /*-{
- // Make sure to null fill any newly created slots (otherwise,
- // get() can return 'undefined').
- var endIndex = this.@java.util.ArrayList::endIndex;
- var startIndex = this.@java.util.ArrayList::startIndex;
- var array = this.@java.util.ArrayList::array;
- var newEnd = newSize + startIndex;
- for (var i = endIndex; i < newEnd; ++i) {
- array[i] = null;
+ protected void setSize(int newSize) {
+ if (newSize < 0) {
+ indexOutOfBounds(newSize);
}
+ setSizeImpl(array, newSize);
+ // null fill any new slots if size < newSize
+ for (; size < newSize; ++size) {
+ setImpl(array, size, null);
+ }
+ // assignment necessary when size > newSize
+ size = newSize;
+ }
- // Also make sure to clean up orphaned slots (or we'll end up
- // leaving garbage uncollected).
- for (var i = endIndex - 1; i >= newEnd; --i) {
- delete array[i];
- }
- this.@java.util.ArrayList::endIndex = newEnd;
- }-*/;
-
- native void verifyIndex(int index) /*-{
- var endIndex = this.@java.util.ArrayList::endIndex;
- var startIndex = this.@java.util.ArrayList::startIndex;
- if (index < 0 || index + startIndex >= endIndex) {
- this.@java.util.ArrayList::indexOutOfBounds(I)(index);
- }
- }-*/;
-
- native void verifyIndexOneExtra(int index) /*-{
- var endIndex = this.@java.util.ArrayList::endIndex;
- var startIndex = this.@java.util.ArrayList::startIndex;
- if (index < 0 || index + startIndex > endIndex) {
- this.@java.util.ArrayList::indexOutOfBounds(I)(index);
- }
- }-*/;
-
- private native void initArray() /*-{
- this.@java.util.ArrayList::array = new Array();
- var HALFWAY_INDEX = 1000000000; // Halfway through the address space
- // Javascript arrays are sparse, so this wastes no space
- this.@java.util.ArrayList::startIndex = HALFWAY_INDEX;
- this.@java.util.ArrayList::endIndex = HALFWAY_INDEX;
- }-*/;
+ private void clearImpl() {
+ array = JavaScriptObject.createArray();
+ size = 0;
+ }
}
diff --git a/user/super/com/google/gwt/emul/java/util/HashMap.java b/user/super/com/google/gwt/emul/java/util/HashMap.java
index 13ab2ad..d79bbc9 100644
--- a/user/super/com/google/gwt/emul/java/util/HashMap.java
+++ b/user/super/com/google/gwt/emul/java/util/HashMap.java
@@ -250,24 +250,6 @@
}-*/;
/**
- * Returns a new array.
- *
- * TODO: move this to JavaScriptObject?
- */
- private static native JavaScriptObject createArray() /*-{
- return [];
- }-*/;
-
- /**
- * Returns a new object.
- *
- * TODO: move this to JavaScriptObject?
- */
- private static native JavaScriptObject createObject() /*-{
- return {};
- }-*/;
-
- /**
* Returns <code>undefined</code>. This is technically a violation of the
* JSNI contract, so we have to be very careful how we use the result.
*/
@@ -417,7 +399,7 @@
private transient JavaScriptObject stringMap;
{
- clear();
+ clearImpl();
}
public HashMap() {
@@ -441,10 +423,7 @@
}
public void clear() {
- hashCodeMap = createArray();
- stringMap = createObject();
- nullSlot = UNDEFINED;
- size = 0;
+ clearImpl();
}
public Object clone() {
@@ -540,4 +519,11 @@
return size;
}
+ private void clearImpl() {
+ hashCodeMap = JavaScriptObject.createArray();
+ stringMap = JavaScriptObject.createObject();
+ nullSlot = UNDEFINED;
+ size = 0;
+ }
+
}
diff --git a/user/super/com/google/gwt/emul/java/util/Vector.java b/user/super/com/google/gwt/emul/java/util/Vector.java
index 65234e6..d4015b5 100644
--- a/user/super/com/google/gwt/emul/java/util/Vector.java
+++ b/user/super/com/google/gwt/emul/java/util/Vector.java
@@ -18,7 +18,6 @@
/**
* To keep performance characteristics in line with Java community expectations,
* <code>Vector</code> is a wrapper around <code>ArrayList</code>.
- *
*/
public class Vector extends AbstractList implements List, RandomAccess,
Cloneable {
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 8672a86..524a143 100644
--- a/user/test/com/google/gwt/emultest/java/util/ArrayListTest.java
+++ b/user/test/com/google/gwt/emultest/java/util/ArrayListTest.java
@@ -16,17 +16,24 @@
package com.google.gwt.emultest.java.util;
-import com.google.gwt.core.client.GWT;
-
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. */
+/**
+ * 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() {
}
@@ -61,45 +68,45 @@
public void testListIteratorCreateInvalid() {
ArrayList l = new ArrayList();
l.add(new Integer(1));
- ListIterator i = l.listIterator(0);
+ l.listIterator(0);
try {
- i = l.listIterator(1);
+ l.listIterator(1);
} catch (IndexOutOfBoundsException e) {
// expected
}
try {
- i = l.listIterator(-1);
+ 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(1, i.nextIndex());
assertEquals(0, i.previousIndex());
i = l.listIterator();
- assertEquals(0,i.nextIndex());
+ assertEquals(0, i.nextIndex());
assertEquals(-1, i.previousIndex());
assertTrue(i.hasNext());
assertFalse(i.hasPrevious());
i.next();
- assertEquals(1,i.nextIndex());
+ assertEquals(1, i.nextIndex());
assertEquals(0, i.previousIndex());
assertFalse(i.hasNext());
- assertTrue(i.hasPrevious());
+ assertTrue(i.hasPrevious());
}
-
+
public void testListIteratorSetInSeveralPositions() {
ArrayList l = new ArrayList();
for (int n = 0; n < 5; n += 2) {
l.add(new Integer(n));
}
- ListIterator i = l.listIterator();
+ l.listIterator();
for (int n = 0; n < 3; n++) {
l.set(n, new Integer(n));
}
@@ -107,44 +114,43 @@
assertEquals(new Integer(n), l.get(n));
}
}
-
+
public void testRemoveRange() {
- if (GWT.isScript()) {
- ArrayList l = new ArrayList();
- for (int i = 0; i < 10; i++) {
- l.add(new Integer(i));
- }
- verifyRemoveRangeWorks(l);
+ 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());
}
}
-
+
protected List makeEmptyList() {
return new ArrayList();
}
-
- private native void verifyRemoveRangeWorks(ArrayList l) /*-{
- var startIndex = l.@java.util.ArrayList::startIndex;
- var endIndex = l.@java.util.ArrayList::endIndex;
- var array = l.@java.util.ArrayList::array;
- l.@java.util.ArrayList::removeRange(II)(0,2);
- if (array[startIndex] !== undefined) {
- @junit.framework.Assert::fail(Ljava/lang/String;)("startIndex should be empty");
- }
- if (array[startIndex + 1] !== undefined) {
- @junit.framework.Assert::fail(Ljava/lang/String;)("startIndex + 1 should be empty");
- }
- if (array[startIndex + 2] === undefined) {
- @junit.framework.Assert::fail(Ljava/lang/String;)("startIndex + 2 should not be empty");
- }
- l.@java.util.ArrayList::removeRange(II)(6,8);
- if (array[endIndex - 3] === undefined) {
- @junit.framework.Assert::fail(Ljava/lang/String;)("endIndex - 3 should not be empty");
- }
- if (array[endIndex - 2] !== undefined) {
- @junit.framework.Assert::fail(Ljava/lang/String;)("endIndex - 2 should be empty");
- }
- if (array[endIndex - 1] !== undefined) {
- @junit.framework.Assert::fail(Ljava/lang/String;)("endIndex - 1 should be empty");
- }
- }-*/;
}
