ArrayList implemented using JavaScript sparse arrays for good insertion/deletion performance at either end. This code also makes ArrayList the primary list type, with Vector delegating to list.
git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@379 8db76d5a-ed1c-0410-87a9-c151d255dfc7
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 62c923c..18e6415 100644
--- a/user/super/com/google/gwt/emul/java/util/ArrayList.java
+++ b/user/super/com/google/gwt/emul/java/util/ArrayList.java
@@ -15,88 +15,261 @@
*/
package java.util;
-/**
- * Implements a list backed by an array.
- */
-public class ArrayList extends AbstractList implements List, RandomAccess,
- Cloneable {
+import com.google.gwt.core.client.JavaScriptObject;
- private Vector vec;
+/**
+ * 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.
+ * </p>
+ * <p>
+ * <b>Dual endedness</b> For increased performance, this implementation supports
+ * constant time insertion and deletion from either end.
+ * </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.
+ */
+ JavaScriptObject array;
+ /**
+ * This field holds the last populated index of the array and is not private
+ * to avoid Eclipse warnings.
+ */
+ int endIndex;
+ /**
+ * This field holds the first populated index of the array and is not private
+ * to avoid Eclipse warnings.
+ */
+ int startIndex;
public ArrayList() {
- vec = new Vector();
+ initArray();
}
public ArrayList(Collection c) {
- vec = new Vector();
+ initArray();
addAll(c);
}
- public void add(int index, Object o) {
- vec.add(index, o);
- }
+ 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;
+ }
+ 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++;
+ }-*/;
public boolean add(Object o) {
- return vec.add(o);
+ add(size(),o);
+ return true;
}
-
- public boolean addAll(Collection c) {
- return vec.addAll(c);
- }
-
- public boolean addAll(int index, Collection c) {
- return vec.addAll(index, c);
- }
-
+
public void clear() {
- vec.clear();
+ setSize(0);
}
-
+
public Object clone() {
return new ArrayList(this);
}
- public boolean contains(Object elem) {
- return vec.contains(elem);
+ 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 int indexOf(Object o) {
+ return indexOf(o, 0);
}
- public Object get(int index) {
- return vec.get(index);
- }
-
- public int indexOf(Object elem) {
- return vec.indexOf(elem);
- }
-
- public boolean isEmpty() {
- return (vec.size() == 0);
- }
-
- public Iterator iterator() {
- return vec.iterator();
- }
+ public native boolean isEmpty() /*-{
+ return (this.@java.util.ArrayList::endIndex == this.@java.util.ArrayList::startIndex);
+ }-*/;
public int lastIndexOf(Object o) {
- return vec.lastIndexOf(o);
+ return lastIndexOf(o, size() - 1);
}
public Object remove(int index) {
- return vec.remove(index);
+ Object old = get(index);
+ removeRange(index,index + 1);
+ return old;
+ }
+
+ public boolean remove(Object o) {
+ int i = indexOf(o);
+ if (i == -1) {
+ return false;
+ }
+ remove(i);
+ return true;
}
- public Object set(int index, Object elem) {
- return vec.set(index, elem);
- }
+ 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 int size() {
- return vec.size();
+ 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);
}
+
+ /**
+ * 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;
+ }
+ --i;
+ }
+ return -1;
+ }-*/;
- public Object[] toArray() {
- return vec.toArray();
- }
+ /**
+ * This function sets the size of the array, and is used in 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 removeRange(int fromIndex, int endIndex) {
- vec.removeRange(fromIndex, endIndex);
- }
-}
+ // 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;
+ }-*/;
+}
\ No newline at end of file
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 cc0e218..774ad4f 100644
--- a/user/super/com/google/gwt/emul/java/util/Vector.java
+++ b/user/super/com/google/gwt/emul/java/util/Vector.java
@@ -16,70 +16,54 @@
package java.util;
/**
- * Differences 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 Vector class.
- * </p>
- * <p>
- * <b>Range checking</b> For increased performance, this implementation does
- * not check for index validity.
- * </p>
+ * 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, Cloneable,
- RandomAccess {
+public class Vector extends AbstractList implements List, RandomAccess,
+ Cloneable {
- protected static boolean equals(Object a, Object b) {
- return (a == null ? b == null : a.equals(b));
- }
+ private ArrayList arrayList;
public Vector() {
- initArray();
+ arrayList = new ArrayList();
}
public Vector(Collection c) {
- initArray();
+ arrayList = new ArrayList();
addAll(c);
}
- public native void add(int index, Object o) /*-{
- var a = this.array;
- this.array = a.slice(0, index).concat(o, a.slice(index));
- }-*/;
+ public void add(int index, Object o) {
+ arrayList.add(index, o);
+ }
- public native boolean add(Object o) /*-{
- var a = this.array;
- a[a.length] = o;
- return true;
- }-*/;
+ public boolean add(Object o) {
+ return arrayList.add(o);
+ }
public boolean addAll(Collection c) {
- return super.addAll(c);
+ return arrayList.addAll(c);
}
public boolean addAll(int index, Collection c) {
- return super.addAll(index, c);
+ return arrayList.addAll(index, c);
}
public void addElement(Object o) {
add(o);
}
- public native void clear() /*-{
- this.array.length = 0;
- }-*/;
+ public void clear() {
+ arrayList.clear();
+ }
public Object clone() {
return new Vector(this);
}
- public boolean contains(Object o) {
- return (indexOf(o) != -1);
- }
-
- public boolean containsAll(Collection c) {
- return super.containsAll(c);
+ public boolean contains(Object elem) {
+ return arrayList.contains(elem);
}
public void copyInto(Object[] objs) {
@@ -88,95 +72,58 @@
while (++i < n) {
objs[i] = get(i);
}
- }
-
+ }
+
public Object elementAt(int index) {
return get(index);
}
- public boolean equals(Object o) {
- return super.equals(o);
- }
-
public Object firstElement() {
return get(0);
}
public Object get(int index) {
- if ((index < 0) || (index >= size())) {
- throw new NoSuchElementException();
- }
- return _get(index);
+ return arrayList.get(index);
}
- public int hashCode() {
- return super.hashCode();
+ public int indexOf(Object elem) {
+ return arrayList.indexOf(elem);
}
- public int indexOf(Object o) {
- return indexOf(o, 0);
+ public int indexOf(Object elem, int index) {
+ return arrayList.indexOf(elem, index);
}
- public native int indexOf(Object o, int startIndex) /*-{
- var a = this.array;
- var i = startIndex-1;
- var n = a.length;
- while (++i < n) {
- if (@java.util.Vector::equals(Ljava/lang/Object;Ljava/lang/Object;)(a[i],o))
- return i;
- }
- return -1;
- }-*/;
-
public void insertElementAt(Object o, int index) {
add(index, o);
}
- public native boolean isEmpty() /*-{
- return (this.array.length == 0);
- }-*/;
+ public boolean isEmpty() {
+ return (arrayList.size() == 0);
+ }
+
+ public Iterator iterator() {
+ return arrayList.iterator();
+ }
public Object lastElement() {
if (isEmpty()) {
- throw new NoSuchElementException("last");
+ throw new IndexOutOfBoundsException("last");
} else {
return get(size() - 1);
}
}
public int lastIndexOf(Object o) {
- return lastIndexOf(o, size() - 1);
+ return arrayList.lastIndexOf(o);
}
- public native int lastIndexOf(Object o, int startIndex) /*-{
- var a = this.array;
- var i = startIndex;
- while (i >= 0) {
- if (@java.util.Vector::equals(Ljava/lang/Object;Ljava/lang/Object;)(a[i],o))
- return i;
- --i;
- }
- return -1;
- }-*/;
-
- public native Object remove(int index) /*-{
- var a = this.array;
- var old = a[index];
- this.array = a.slice(0, index).concat(a.slice(index+1));
- return old;
- }-*/;
-
- public boolean remove(Object o) {
- int i = indexOf(o);
- if (i == -1) {
- return false;
- }
- remove(i);
- return true;
+ public int lastIndexOf(Object o, int index) {
+ return arrayList.lastIndexOf(o, index);
}
- public boolean removeAll(Collection c) {
- return super.removeAll(c);
+ public Object remove(int index) {
+ return arrayList.remove(index);
}
public void removeAllElements() {
@@ -191,60 +138,27 @@
remove(index);
}
- public boolean retainAll(Collection c) {
- return super.retainAll(c);
+ public Object set(int index, Object elem) {
+ return arrayList.set(index, elem);
}
- public native Object set(int index, Object o) /*-{
- var a = this.array;
- var old = a[index];
- a[index] = o;
- return old;
- }-*/;
-
public void setElementAt(Object o, int index) {
set(index, o);
}
- public native void setSize(int newSize) /*-{
- // Make sure to null-fill any newly created slots (otherwise,
- // get() can return 'undefined').
- for (var i = this.array.length; i < newSize; ++i)
- this.array[i] = null;
+ public void setSize(int size) {
+ arrayList.setSize(size);
+ }
- // Also make sure to clean up orphaned slots (or we'll end up
- // leaving garbage uncollected).
- for (var i = this.array.length - 1; i >= newSize; --i)
- delete this.array[i];
-
- this.array.length = newSize;
- }-*/;
-
- public native int size() /*-{
- return this.array.length;
- }-*/;
+ public int size() {
+ return arrayList.size();
+ }
public Object[] toArray() {
- return super.toArray();
+ return arrayList.toArray();
}
- public String toString() {
- return super.toString();
+ protected void removeRange(int fromIndex, int endIndex) {
+ arrayList.removeRange(fromIndex, endIndex);
}
-
- protected native void removeRange(int fromIndex, int endIndex) /*-{
- var a = this.array;
- this.array = a.slice(0, fromIndex).concat(a.slice(endIndex));
- }-*/;
-
- // CHECKSTYLE_OFF: Underscore prefix is an old convention that could be cleaned up.
- private native Object _get(int index) /*-{
- return this.array[index];
- }-*/;
- // CHECKSTYLE_ON
-
- private native void initArray() /*-{
- this.array = new Array();
- }-*/;
-
}
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 b99b7ae..328456d 100644
--- a/user/test/com/google/gwt/emultest/java/util/ArrayListTest.java
+++ b/user/test/com/google/gwt/emultest/java/util/ArrayListTest.java
@@ -1,12 +1,30 @@
-// Copyright 2006 Google Inc. All Rights Reserved.
+/*
+ * 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 com.google.gwt.core.client.GWT;
+
import org.apache.commons.collections.TestArrayList;
import java.util.ArrayList;
import java.util.List;
-/** Tests ArrayList, and, by extention AbstractList */
+/** Tests ArrayList, and, by extension AbstractList. Uses inheritance to
+ * inherit all of Apache's TestList and TestCollection. */
public class ArrayListTest extends TestArrayList {
public ArrayListTest() {
}
@@ -15,4 +33,47 @@
return new ArrayList();
}
+ public void testAddWatch() {
+ ArrayList s = new ArrayList();
+ s.add("watch");
+ assertEquals(s.get(0), "watch");
+ }
+
+
+ public void testRemoveRange() {
+ if (GWT.isScript()) {
+ ArrayList l = new ArrayList();
+ for (int i = 0; i < 10; i++) {
+ l.add(new Integer(i));
+ }
+ verifyRemoveRangeWorks(l);
+ }
+ }
+
+ 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");
+ }
+ }-*/;
+
}
