add FixedSizeArrayStack

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);