Skip to main content
summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBrian Vosburgh2015-07-18 01:39:46 +0000
committerBrian Vosburgh2015-07-18 01:39:46 +0000
commitb1367d0c6f9e86cb4cf7e938cec7a02f93c99225 (patch)
treef3e3b9fd8a3105c3cdaedf8c9699f0b263e43428
parent2ddc9199acb072cc5d44b7cc784f39db18e975d1 (diff)
downloadwebtools.dali-b1367d0c6f9e86cb4cf7e938cec7a02f93c99225.tar.gz
webtools.dali-b1367d0c6f9e86cb4cf7e938cec7a02f93c99225.tar.xz
webtools.dali-b1367d0c6f9e86cb4cf7e938cec7a02f93c99225.zip
add FixedSizeArrayStack
-rw-r--r--common/plugins/org.eclipse.jpt.common.utility/src/org/eclipse/jpt/common/utility/internal/collection/ArrayStack.java1
-rw-r--r--common/plugins/org.eclipse.jpt.common.utility/src/org/eclipse/jpt/common/utility/internal/collection/FixedSizeArrayStack.java164
-rw-r--r--common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/ArrayStackTests.java39
-rw-r--r--common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/FixedSizeArrayStackTests.java140
-rw-r--r--common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/JptCommonUtilityCollectionTests.java1
5 files changed, 345 insertions, 0 deletions
diff --git a/common/plugins/org.eclipse.jpt.common.utility/src/org/eclipse/jpt/common/utility/internal/collection/ArrayStack.java b/common/plugins/org.eclipse.jpt.common.utility/src/org/eclipse/jpt/common/utility/internal/collection/ArrayStack.java
index fe1ca5aa65..1a51a188dc 100644
--- a/common/plugins/org.eclipse.jpt.common.utility/src/org/eclipse/jpt/common/utility/internal/collection/ArrayStack.java
+++ b/common/plugins/org.eclipse.jpt.common.utility/src/org/eclipse/jpt/common/utility/internal/collection/ArrayStack.java
@@ -18,6 +18,7 @@ import org.eclipse.jpt.common.utility.collection.Stack;
/**
* Resizable-array LIFO implementation of the {@link Stack} interface.
* @param <E> the type of elements maintained by the stack
+ * @see FixedSizeArrayStack
*/
public class ArrayStack<E>
implements Stack<E>, Cloneable, Serializable
diff --git a/common/plugins/org.eclipse.jpt.common.utility/src/org/eclipse/jpt/common/utility/internal/collection/FixedSizeArrayStack.java b/common/plugins/org.eclipse.jpt.common.utility/src/org/eclipse/jpt/common/utility/internal/collection/FixedSizeArrayStack.java
new file mode 100644
index 0000000000..ffc9ae1998
--- /dev/null
+++ b/common/plugins/org.eclipse.jpt.common.utility/src/org/eclipse/jpt/common/utility/internal/collection/FixedSizeArrayStack.java
@@ -0,0 +1,164 @@
+/*******************************************************************************
+ * Copyright (c) 2015 Oracle. All rights reserved.
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0, which accompanies this distribution
+ * and is available at http://www.eclipse.org/legal/epl-v10.html.
+ *
+ * Contributors:
+ * Oracle - initial API and implementation
+ ******************************************************************************/
+package org.eclipse.jpt.common.utility.internal.collection;
+
+import java.io.Serializable;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.EmptyStackException;
+import org.eclipse.jpt.common.utility.collection.Stack;
+import org.eclipse.jpt.common.utility.internal.ObjectTools;
+
+/**
+ * Fixed-size array LIFO implementation of the {@link Stack} interface.
+ * This implementation will throw an exception if its capacity is exceeded.
+ * @param <E> the type of elements maintained by the stack
+ * @see ArrayStack
+ */
+public class FixedSizeArrayStack<E>
+ implements Stack<E>, Cloneable, Serializable
+{
+ private E[] elements;
+
+ /** The index of where the next "pushed" element will go. */
+ private int next = 0;
+
+ private int size = 0;
+
+ private static final long serialVersionUID = 1L;
+
+
+ // ********** constructors **********
+
+ /**
+ * Construct an empty stack with the specified capacity.
+ */
+ @SuppressWarnings("unchecked")
+ public FixedSizeArrayStack(int capacity) {
+ super();
+ if (capacity < 0) {
+ throw new IllegalArgumentException("Illegal capacity: " + capacity); //$NON-NLS-1$
+ }
+ this.elements = (E[]) new Object[capacity];
+ }
+
+ /**
+ * Construct a stack containing the elements of the specified
+ * collection. The stack will pop its elements in reverse of the
+ * order they are returned by the collection's iterator (i.e. the
+ * last element returned by the collection's iterator will be the
+ * first element returned by {@link #pop()}; the first, last.).
+ */
+ @SuppressWarnings("unchecked")
+ public FixedSizeArrayStack(Collection<? extends E> c) {
+ super();
+ int len = c.size();
+ this.elements = (E[]) c.toArray(new Object[len]);
+ this.size = len;
+ // next stays at zero
+ }
+
+
+ // ********** Stack implementation **********
+
+ public void push(E element) {
+ if (this.isFull()) {
+ throw new IllegalStateException("Stack is full."); //$NON-NLS-1$
+ }
+ this.elements[this.next] = element;
+ if (++this.next == this.elements.length) {
+ this.next = 0;
+ }
+ this.size++;
+ }
+
+ public E pop() {
+ if (this.size == 0) {
+ throw new EmptyStackException();
+ }
+ int index = this.next;
+ if (index == 0) {
+ index = this.elements.length;
+ }
+ index--;
+ E element = this.elements[index];
+ this.elements[index] = null; // allow GC to work
+ this.next = index;
+ this.size--;
+ return element;
+ }
+
+ public E peek() {
+ if (this.size == 0) {
+ throw new EmptyStackException();
+ }
+ int index = this.next;
+ if (index == 0) {
+ index = this.elements.length;
+ }
+ index--;
+ return this.elements[index];
+ }
+
+ public boolean isEmpty() {
+ return this.size == 0;
+ }
+
+ /**
+ * Return whether the stack is full,
+ * as its capacity is fixed.
+ */
+ public boolean isFull() {
+ return this.size == this.elements.length;
+ }
+
+
+ // ********** standard methods **********
+
+ @Override
+ public FixedSizeArrayStack<E> clone() {
+ int len = this.elements.length;
+ FixedSizeArrayStack<E> clone = new FixedSizeArrayStack<E>(len);
+ System.arraycopy(this.elements, 0, clone.elements, 0, len);
+ clone.next = this.next;
+ clone.size = this.size;
+ return clone;
+ }
+
+ /**
+ * Print the elements in the order in which they are "pushed" on to
+ * the stack (as opposed to the order in which they will be "popped"
+ * off of the stack).
+ */
+ @Override
+ public String toString() {
+ return Arrays.toString(this.copyElements());
+ }
+
+ private Object[] copyElements() {
+ if (this.size == 0) {
+ return ObjectTools.EMPTY_OBJECT_ARRAY;
+ }
+ Object[] result = new Object[this.size];
+ if (this.next >= this.size) {
+ // elements are contiguous, but not to end of array
+ System.arraycopy(this.elements, (this.next - this.size), result, 0, this.size);
+ } else if (this.next == 0) {
+ // elements are contiguous to end of array
+ System.arraycopy(this.elements, (this.elements.length - this.size), result, 0, this.size);
+ } else {
+ // elements wrap past end of array
+ int fragmentSize = this.size - this.next;
+ System.arraycopy(this.elements, (this.elements.length - fragmentSize), result, 0, fragmentSize);
+ System.arraycopy(this.elements, 0, result, fragmentSize, (this.size - fragmentSize));
+ }
+ return result;
+ }
+}
diff --git a/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/ArrayStackTests.java b/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/ArrayStackTests.java
index e10a1439dd..8ccda03520 100644
--- a/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/ArrayStackTests.java
+++ b/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/ArrayStackTests.java
@@ -9,6 +9,7 @@
******************************************************************************/
package org.eclipse.jpt.common.utility.tests.internal.collection;
+import java.util.ArrayList;
import org.eclipse.jpt.common.utility.collection.Stack;
import org.eclipse.jpt.common.utility.internal.collection.ArrayStack;
import org.eclipse.jpt.common.utility.tests.internal.TestTools;
@@ -26,6 +27,44 @@ public class ArrayStackTests
return new ArrayStack<String>();
}
+ public void testCollectionConstructor() {
+ ArrayList<String> c = new ArrayList<String>();
+ c.add("first");
+ c.add("second");
+ c.add("third");
+ c.add("fourth");
+ c.add("fifth");
+ c.add("sixth");
+ c.add("seventh");
+ c.add("eighth");
+ c.add("ninth");
+ c.add("tenth"); // force some free space
+ Stack<String> stack = new ArrayStack<String>(c);
+
+ assertFalse(stack.isEmpty());
+ assertEquals("tenth", stack.peek());
+ stack.push("eleventh");
+ stack.push("twelfth");
+
+ assertEquals("twelfth", stack.peek());
+ assertEquals("twelfth", stack.pop());
+ assertEquals("eleventh", stack.pop());
+ assertEquals("tenth", stack.peek());
+ assertEquals("tenth", stack.pop());
+ assertEquals("ninth", stack.pop());
+ assertFalse(stack.isEmpty());
+ assertEquals("eighth", stack.peek());
+ assertEquals("eighth", stack.pop());
+ assertEquals("seventh", stack.pop());
+ assertEquals("sixth", stack.pop());
+ assertEquals("fifth", stack.pop());
+ assertEquals("fourth", stack.pop());
+ assertEquals("third", stack.pop());
+ assertEquals("second", stack.pop());
+ assertEquals("first", stack.pop());
+ assertTrue(stack.isEmpty());
+ }
+
public void testSerialization_fullArray() throws Exception {
Stack<String> stack = new ArrayStack<String>(3);
stack.push("first");
diff --git a/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/FixedSizeArrayStackTests.java b/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/FixedSizeArrayStackTests.java
new file mode 100644
index 0000000000..2778fa48a8
--- /dev/null
+++ b/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/FixedSizeArrayStackTests.java
@@ -0,0 +1,140 @@
+/*******************************************************************************
+ * Copyright (c) 2015 Oracle. All rights reserved.
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0, which accompanies this distribution
+ * and is available at http://www.eclipse.org/legal/epl-v10.html.
+ *
+ * Contributors:
+ * Oracle - initial API and implementation
+ ******************************************************************************/
+package org.eclipse.jpt.common.utility.tests.internal.collection;
+
+import java.util.ArrayList;
+import org.eclipse.jpt.common.utility.collection.Stack;
+import org.eclipse.jpt.common.utility.internal.collection.FixedSizeArrayStack;
+import org.eclipse.jpt.common.utility.tests.internal.TestTools;
+
+@SuppressWarnings("nls")
+public class FixedSizeArrayStackTests
+ extends StackTests
+{
+ public FixedSizeArrayStackTests(String name) {
+ super(name);
+ }
+
+ @Override
+ FixedSizeArrayStack<String> buildStack() {
+ return new FixedSizeArrayStack<String>(10);
+ }
+
+ public void testCollectionConstructor() {
+ ArrayList<String> c = new ArrayList<String>();
+ c.add("first");
+ c.add("second");
+ c.add("third");
+ c.add("fourth");
+ c.add("fifth");
+ c.add("sixth");
+ c.add("seventh");
+ c.add("eighth");
+ c.add("ninth");
+ c.add("tenth");
+ Stack<String> stack = new FixedSizeArrayStack<String>(c);
+
+ assertFalse(stack.isEmpty());
+ assertEquals("tenth", stack.peek());
+ assertEquals("tenth", stack.pop());
+ assertEquals("ninth", stack.pop());
+ assertFalse(stack.isEmpty());
+ assertEquals("eighth", stack.peek());
+ assertEquals("eighth", stack.pop());
+ assertEquals("seventh", stack.pop());
+ assertEquals("sixth", stack.pop());
+ assertEquals("fifth", stack.pop());
+ assertEquals("fourth", stack.pop());
+ assertEquals("third", stack.pop());
+ assertEquals("second", stack.pop());
+ assertEquals("first", stack.pop());
+ assertTrue(stack.isEmpty());
+ }
+
+ public void testIsFull() {
+ FixedSizeArrayStack<String> stack = this.buildStack();
+ assertFalse(stack.isFull());
+ stack.push("first");
+ assertFalse(stack.isFull());
+ stack.push("second");
+ assertFalse(stack.isFull());
+ stack.push("third");
+ stack.push("fourth");
+ stack.push("fifth");
+ stack.push("sixth");
+ stack.push("seventh");
+ stack.push("eighth");
+ stack.push("ninth");
+ stack.push("tenth");
+ assertTrue(stack.isFull());
+
+ stack.pop();
+ assertFalse(stack.isEmpty());
+ stack.pop();
+ stack.pop();
+ stack.pop();
+ stack.pop();
+ stack.pop();
+ stack.pop();
+ stack.pop();
+ assertFalse(stack.isFull());
+ }
+
+ public void testArrayCapacityExceeded() {
+ Stack<String> stack = this.buildStack();
+ assertTrue(stack.isEmpty());
+ stack.push("first");
+ assertFalse(stack.isEmpty());
+ stack.push("second");
+ assertFalse(stack.isEmpty());
+ stack.push("third");
+ stack.push("fourth");
+ stack.push("fifth");
+ stack.push("sixth");
+ stack.push("seventh");
+ stack.push("eighth");
+ stack.push("ninth");
+ stack.push("tenth");
+
+ boolean exCaught = false;
+ try {
+ stack.push("eleventh");
+ fail("bogus");
+ } catch (IllegalStateException ex) {
+ exCaught = true;
+ }
+ assertTrue(exCaught);
+
+ assertFalse(stack.isEmpty());
+ assertEquals("tenth", stack.peek());
+ assertEquals("tenth", stack.pop());
+ assertEquals("ninth", stack.pop());
+ assertFalse(stack.isEmpty());
+ assertEquals("eighth", stack.peek());
+ assertEquals("eighth", stack.pop());
+ assertEquals("seventh", stack.pop());
+ assertEquals("sixth", stack.pop());
+ assertEquals("fifth", stack.pop());
+ assertEquals("fourth", stack.pop());
+ assertEquals("third", stack.pop());
+ assertEquals("second", stack.pop());
+ assertEquals("first", stack.pop());
+ assertTrue(stack.isEmpty());
+ }
+
+ public void testSerialization_fullArray() throws Exception {
+ Stack<String> stack = new FixedSizeArrayStack<String>(3);
+ stack.push("first");
+ stack.push("second");
+ stack.push("third");
+
+ this.verifyClone(stack, TestTools.serialize(stack));
+ }
+}
diff --git a/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/JptCommonUtilityCollectionTests.java b/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/JptCommonUtilityCollectionTests.java
index 3dbef231a3..b4125019e2 100644
--- a/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/JptCommonUtilityCollectionTests.java
+++ b/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/JptCommonUtilityCollectionTests.java
@@ -25,6 +25,7 @@ public class JptCommonUtilityCollectionTests {
suite.addTestSuite(BagTests.class);
suite.addTestSuite(CollectionToolsTests.class);
suite.addTestSuite(FixedSizeArrayQueueTests.class);
+ suite.addTestSuite(FixedSizeArrayStackTests.class);
suite.addTestSuite(HashBagTests.class);
suite.addTestSuite(IdentityHashBagTests.class);
suite.addTestSuite(IdentityHashSetTests.class);

Back to the top