Array implementation for Lightweight Collections. Pure Java implementation only.
This is part of an incremental review. Not likely to land until other parts are reviewed.
Development moved to bikeshed to prevent interfering with other GWT development
Review at http://gwt-code-reviews.appspot.com/232801
Review by: fabbott@google.com
git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@7801 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/bikeshed/src/com/google/gwt/collections/Array.java b/bikeshed/src/com/google/gwt/collections/Array.java
new file mode 100644
index 0000000..f6cded1
--- /dev/null
+++ b/bikeshed/src/com/google/gwt/collections/Array.java
@@ -0,0 +1,34 @@
+/*
+ * Copyright 2009 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.collections;
+
+/**
+ * The root Array type that provides read-access to an array that might still
+ * be mutable by another actor.
+ *
+ * @param <E> The type stored in the array elements
+ */
+public abstract class Array<E> {
+
+ Array() {
+ }
+
+ @ConstantTime
+ public abstract E get(int index);
+
+ @ConstantTime
+ public abstract int size();
+}
diff --git a/bikeshed/src/com/google/gwt/collections/Assertions.java b/bikeshed/src/com/google/gwt/collections/Assertions.java
new file mode 100644
index 0000000..1a34e8d
--- /dev/null
+++ b/bikeshed/src/com/google/gwt/collections/Assertions.java
@@ -0,0 +1,32 @@
+/*
+ * Copyright 2009 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.collections;
+
+/**
+ * Shared assertions and related messages.
+ */
+class Assertions {
+
+ static void assertIndexInRange(int index, int minInclusive, int maxExclusive) {
+ assert (index >= minInclusive && index < maxExclusive) : "Index " + index
+ + " was not in the acceptable range [" + minInclusive + ", " + maxExclusive + ")";
+ }
+
+ static void assertNotNull(Object ref) {
+ assert (ref != null) : "A null reference is not allowed here";
+ }
+
+}
diff --git a/bikeshed/src/com/google/gwt/collections/CollectionFactory.java b/bikeshed/src/com/google/gwt/collections/CollectionFactory.java
new file mode 100644
index 0000000..c98e743
--- /dev/null
+++ b/bikeshed/src/com/google/gwt/collections/CollectionFactory.java
@@ -0,0 +1,27 @@
+/*
+ * Copyright 2009 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.collections;
+
+/**
+ * Made to be switched out using super source even while Collections itself isn't.
+ */
+public class CollectionFactory {
+
+ public static <E> MutableArray<E> createMutableArray() {
+ return new MutableArray<E>();
+ }
+
+}
diff --git a/bikeshed/src/com/google/gwt/collections/Collections.gwt.xml b/bikeshed/src/com/google/gwt/collections/Collections.gwt.xml
new file mode 100644
index 0000000..a91449d
--- /dev/null
+++ b/bikeshed/src/com/google/gwt/collections/Collections.gwt.xml
@@ -0,0 +1,19 @@
+<!--
+ Copyright 2010 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.
+-->
+<module>
+ <inherits name='com.google.gwt.user.User'/>
+ <source path="" />
+</module>
diff --git a/bikeshed/src/com/google/gwt/collections/ConstantTime.java b/bikeshed/src/com/google/gwt/collections/ConstantTime.java
new file mode 100644
index 0000000..60a6d54
--- /dev/null
+++ b/bikeshed/src/com/google/gwt/collections/ConstantTime.java
@@ -0,0 +1,23 @@
+/*
+ * Copyright 2009 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.collections;
+
+/**
+ * Specifies that an operation will occur in amortized constant time.
+ */
+public @interface ConstantTime {
+
+}
diff --git a/bikeshed/src/com/google/gwt/collections/LinearTime.java b/bikeshed/src/com/google/gwt/collections/LinearTime.java
new file mode 100644
index 0000000..379868a
--- /dev/null
+++ b/bikeshed/src/com/google/gwt/collections/LinearTime.java
@@ -0,0 +1,23 @@
+/*
+ * Copyright 2009 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.collections;
+
+/**
+ * Specifies that an operation will occur in amortized linear time.
+ */
+public @interface LinearTime {
+
+}
diff --git a/bikeshed/src/com/google/gwt/collections/MutableArray.java b/bikeshed/src/com/google/gwt/collections/MutableArray.java
new file mode 100644
index 0000000..3201458
--- /dev/null
+++ b/bikeshed/src/com/google/gwt/collections/MutableArray.java
@@ -0,0 +1,141 @@
+/*
+ * Copyright 2009 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.collections;
+
+/**
+ * An array whose content and length can change over time.
+ *
+ * @param <E> The type stored in the array elements
+ */
+public class MutableArray<E> extends Array<E> {
+
+ // The elements in the array
+ private E[] elems;
+
+ // Tracks when this array is frozen (for assertion enforcement only)
+ private boolean frozen;
+
+ /**
+ * Can only be constructed via {@link CollectionFactory}.
+ */
+ MutableArray() {
+ }
+
+ @ConstantTime
+ public void add(E elem) {
+ insert(size(), elem);
+ }
+
+ @ConstantTime
+ public void clear() {
+ elems = null;
+ }
+
+ @Override
+ @ConstantTime
+ public E get(int index) {
+ Assertions.assertIndexInRange(index, 0, size());
+ if (elems != null) {
+ return elems[index];
+ } else {
+ return null;
+ }
+ }
+
+ /**
+ * Inserts {@code element} before the element residing at {@code index}.
+ *
+ * @param index in the range [0, this.size()], inclusive; if index is equal
+ * to the array's current size, the result is equivalent to calling
+ * {@link #add(Object)}
+ * @param elem the element to insert or {@code null}
+ */
+ @SuppressWarnings("unchecked")
+ @LinearTime
+ public void insert(int index, E elem) {
+ Assertions.assertIndexInRange(index, 0, size() + 1);
+
+ // TODO benchmark to see if we need to grow smartly (2x size?)
+ // TODO benchmark to see if we need to consider single element arrays separately
+ if (elems != null) {
+ int oldLen = elems.length;
+ E[] newElems = (E[]) new Object[oldLen + 1];
+ System.arraycopy(elems, 0, newElems, 0, index);
+ System.arraycopy(elems, index, newElems, index + 1, oldLen - index);
+ newElems[index] = elem;
+ elems = newElems;
+ } else {
+ elems = (E[]) (new Object[] {elem});
+ }
+ }
+
+ /**
+ * Removes the element at the specified index.
+ */
+ @SuppressWarnings("unchecked")
+ @LinearTime
+ public void remove(int index) {
+ Assertions.assertIndexInRange(index, 0, size());
+ if (elems != null && elems.length >= 1) {
+ // TODO: replace with splice using JSNI
+ int oldLen = elems.length;
+ E[] newElems = (E[]) new Object[oldLen - 1];
+ System.arraycopy(elems, 0, newElems, 0, index);
+ System.arraycopy(elems, index + 1, newElems, index, oldLen - index - 1);
+ elems = newElems;
+ } else if (elems.length == 1) {
+ elems = null;
+ } else {
+ assert false : "index " + index + " in range [0, " + size() + "), but remove(int) failed";
+ }
+ }
+
+ /**
+ * Replaces the element at the specified index.
+ *
+ * @param index in the range [0, this.size()), exclusive
+ * @param elem the element to insert or {@code null}
+ */
+ @ConstantTime
+ public void set(int index, E elem) {
+ Assertions.assertIndexInRange(index, 0, size());
+ if (elems != null) {
+ elems[index] = elem;
+ } else {
+ assert false : "index " + index + " in range [0, " + size() + "), but set(int,E) failed";
+ }
+ }
+
+ @Override
+ @ConstantTime
+ public int size() {
+ if (elems != null) {
+ return elems.length;
+ } else {
+ return 0;
+ }
+ }
+
+ // Only meant to be called from within Assertions
+ boolean isFrozen() {
+ return frozen;
+ }
+
+ // Only meant to be called from within Assertions
+ void markFrozen() {
+ frozen = true;
+ }
+}
diff --git a/bikeshed/test/com/google/gwt/collections/ObjectArrayTest.java b/bikeshed/test/com/google/gwt/collections/ObjectArrayTest.java
new file mode 100644
index 0000000..9eafda3
--- /dev/null
+++ b/bikeshed/test/com/google/gwt/collections/ObjectArrayTest.java
@@ -0,0 +1,269 @@
+/*
+ * Copyright 2009 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.collections;
+
+import static com.google.gwt.collections.CollectionFactory.createMutableArray;
+
+import com.google.gwt.junit.client.GWTTestCase;
+
+/**
+ * Tests immutable and mutable arrays.
+ */
+public class ObjectArrayTest extends GWTTestCase {
+
+ boolean assertionsEnabled;
+
+ public void gwtSetUp() {
+ assertionsEnabled = this.getClass().desiredAssertionStatus();
+ }
+
+ @Override
+ public String getModuleName() {
+ return null;
+ }
+
+ public void testClear() {
+ {
+ // Clear an empty array
+ MutableArray<Object> b = createMutableArray();
+ b.clear();
+ assertEquals(0, b.size());
+ }
+
+ {
+ // Clear a non-empty array
+ MutableArray<Object> b = createMutableArray();
+ b.add("string");
+ b.add(false);
+ b.add(3);
+ b.clear();
+ assertEquals(0, b.size());
+ }
+ }
+
+ public void testInsertAtBeginning() {
+ final int N = 10;
+ MutableArray<Integer> b = createMutableArray();
+
+ for (int i = 0; i < N; ++i) {
+ b.insert(0, i);
+ }
+
+ for (int i = 0; i < N; ++i) {
+ assertEquals(N - i - 1, b.get(i).intValue());
+ }
+ }
+
+ public void testInsertAtEnd() {
+ final int N = 10;
+ MutableArray<Integer> b = createMutableArray();
+
+ for (int i = 0; i < N; ++i) {
+ b.insert(b.size(), i);
+ }
+
+ for (int i = 0; i < N; ++i) {
+ assertEquals(i, b.get(i).intValue());
+ }
+ }
+
+ public void testInsertInMiddle() {
+ final int N = 10;
+ MutableArray<Integer> b = createMutableArray();
+
+ // Fill the array with 0..(N-1)
+ for (int i = 0; i < N; ++i) {
+ b.insert(b.size(), i);
+ }
+
+ // Double each number by inserting.
+ for (int i = 0; i < N; ++i) {
+ b.insert(i * 2, i);
+ }
+
+ for (int i = 0, j = 0; i < 2 * N; i += 2, ++j) {
+ assertEquals(j, b.get(i).intValue());
+ assertEquals(j, b.get(i + 1).intValue());
+ }
+ }
+
+ public void testSingleElementNull() {
+ MutableArray<String> b = createMutableArray();
+ b.add(null);
+
+ assertEquals(null, b.get(0));
+ }
+
+ public void testMultiElementArrayManipulations() {
+ MutableArray<String> b = createMutableArray();
+ b.add("apple");
+ b.add("banana");
+ b.add("coconut");
+ b.add(null);
+ b.add("donut");
+
+ // On mutable array, get() in order
+ assertEquals("apple", b.get(0));
+ assertEquals("banana", b.get(1));
+ assertEquals("coconut", b.get(2));
+ assertEquals(null, b.get(3));
+ assertEquals("donut", b.get(4));
+
+ // On mutable array, get() in non-sequential order
+ assertEquals("coconut", b.get(2));
+ assertEquals("apple", b.get(0));
+ assertEquals("donut", b.get(4));
+ assertEquals("banana", b.get(1));
+ assertEquals(null, b.get(3));
+
+ // Try a set() call, too
+ b.set(3, "eclair");
+ assertEquals("eclair", b.get(3));
+ }
+
+ public void testRemove() {
+ MutableArray<Integer> b = createMutableArray();
+
+ b.add(1);
+ b.add(2);
+ b.add(3);
+ b.add(4);
+ b.add(5);
+
+ // Remove from the middle to make 1,2,4,5
+ b.remove(2);
+ assertEquals(4, b.size());
+ assertEquals(1, b.get(0).intValue());
+ assertEquals(5, b.get(3).intValue());
+
+ // Remove from the beginning to make 2,4,5
+ b.remove(0);
+ assertEquals(3, b.size());
+ assertEquals(2, b.get(0).intValue());
+ assertEquals(5, b.get(2).intValue());
+
+ // Remove from the end to make 2,4
+ b.remove(b.size() - 1);
+ assertEquals(2, b.size());
+ assertEquals(2, b.get(0).intValue());
+ assertEquals(4, b.get(1).intValue());
+ }
+
+ public void testSingleElementAddAndRemove() {
+ MutableArray<String> a = createMutableArray();
+
+ a.add("foo");
+
+ assertEquals(1, a.size());
+ assertEquals("foo", a.get(0));
+
+ a.remove(0);
+
+ assertEquals(0, a.size());
+
+ a.add("bar");
+
+ assertEquals(1, a.size());
+ assertEquals("bar", a.get(0));
+}
+
+ public void testSingletonArrayCreationAndRetrieval() throws Exception {
+ final int C = 2112;
+ MutableArray<Integer> b = createMutableArray();
+ b.add(C);
+ assertEquals(C, b.get(0).intValue());
+
+ Array<Integer> a = b;
+ assertEquals(1, a.size());
+
+ assertEquals((Integer) 2112, a.get(0));
+ }
+
+ public void testSingletonArrayInvalidIndex() throws Exception {
+ MutableArray<Boolean> b = createMutableArray();
+ b.add(false);
+ Array<Boolean> a = b;
+
+ assertEquals((Boolean) false, a.get(0));
+
+ // Do not test undefined behavior without assertions
+ if (!assertionsEnabled) {
+ return;
+ }
+
+ try {
+ a.get(1);
+ fail("That should have failed");
+ } catch (AssertionError e) {
+ assertEquals(("Index " + 1 + " was not in the acceptable range [" + 0 + ", " + 1 + ")"),
+ e.getMessage());
+ }
+ }
+
+ public void testSingletonArrayManipulations() {
+ MutableArray<String> b = createMutableArray();
+ b.add("diva");
+ b.set(0, "avid");
+ assertEquals(1, b.size());
+ assertEquals("avid", b.get(0));
+ }
+
+ public void testThatEmptyArraysHaveHaveNoValidIndices() throws Exception {
+ {
+ // Do not test undefined behavior without assertions
+ if (!assertionsEnabled) {
+ return;
+ }
+ // Tests get().
+ MutableArray<String> b = createMutableArray();
+ Array<String> a = b;
+ // Iterate i through the various likely errors states.
+ for (int i = -1; i < 4; ++i) {
+ try {
+ a.get(i);
+ fail("Should have triggered an assertion");
+ } catch (AssertionError e) {
+ // Good
+ assertEquals(("Index " + i + " was not in the acceptable range [" + 0 + ", "
+ + 0 + ")"), e.getMessage());
+ }
+ }
+ }
+
+ {
+ // Tests set().
+ MutableArray<String> b = createMutableArray();
+ // Iterate i through the various likely errors states.
+ for (int i = -1; i < 4; ++i) {
+ try {
+ b.set(i, "random string");
+ fail("Should have triggered an assertion");
+ } catch (AssertionError e) {
+ // Good
+ assertEquals(("Index " + i + " was not in the acceptable range [" + 0 + ", "
+ + 0 + ")"), e.getMessage());
+ }
+ }
+ }
+ }
+
+ public void testThatEmptyArraysHaveSizeZero() {
+ MutableArray<String> b = createMutableArray();
+ Array<String> a = b;
+ assertEquals(0, a.size());
+ }
+
+}
