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