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"); + } + }-*/; + }