Skip to main content
summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBrian Vosburgh2015-07-21 17:37:05 +0000
committerBrian Vosburgh2015-07-21 18:17:08 +0000
commitf3527a8debc90335c4fdd0f426174b0e9bb57621 (patch)
treedd422ef8c1d6bac4bdc455a22aa3733f72168379
parent46385b4d5995580ff5fedd27b15ec7683bfca7fa (diff)
downloadwebtools.dali-f3527a8debc90335c4fdd0f426174b0e9bb57621.tar.gz
webtools.dali-f3527a8debc90335c4fdd0f426174b0e9bb57621.tar.xz
webtools.dali-f3527a8debc90335c4fdd0f426174b0e9bb57621.zip
rework LinkedQueue
-rw-r--r--common/plugins/org.eclipse.jpt.common.utility/src/org/eclipse/jpt/common/utility/internal/collection/LinkedQueue.java260
-rw-r--r--common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/LinkedQueueTests.java84
2 files changed, 318 insertions, 26 deletions
diff --git a/common/plugins/org.eclipse.jpt.common.utility/src/org/eclipse/jpt/common/utility/internal/collection/LinkedQueue.java b/common/plugins/org.eclipse.jpt.common.utility/src/org/eclipse/jpt/common/utility/internal/collection/LinkedQueue.java
index 0d77394d17..d52d85d25f 100644
--- a/common/plugins/org.eclipse.jpt.common.utility/src/org/eclipse/jpt/common/utility/internal/collection/LinkedQueue.java
+++ b/common/plugins/org.eclipse.jpt.common.utility/src/org/eclipse/jpt/common/utility/internal/collection/LinkedQueue.java
@@ -1,5 +1,5 @@
/*******************************************************************************
- * Copyright (c) 2009, 2013 Oracle. All rights reserved.
+ * Copyright (c) 2009, 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.
@@ -10,19 +10,22 @@
package org.eclipse.jpt.common.utility.internal.collection;
import java.io.Serializable;
+import java.util.Arrays;
import java.util.Collection;
-import java.util.LinkedList;
+import java.util.NoSuchElementException;
import org.eclipse.jpt.common.utility.collection.Queue;
+import org.eclipse.jpt.common.utility.internal.ObjectTools;
/**
- * Linked list FIFO implementation of the {@link Queue} interface.
+ * Linked FIFO implementation of the {@link Queue} interface.
* @param <E> the type of elements maintained by the queue
- * @see LinkedList
*/
public class LinkedQueue<E>
implements Queue<E>, Cloneable, Serializable
{
- private LinkedList<E> elements;
+ private final NodeFactory<E> nodeFactory;
+ private transient Node<E> head; // next element to dequeue
+ private transient Node<E> tail; // enqueue next element here
private static final long serialVersionUID = 1L;
@@ -30,42 +33,99 @@ public class LinkedQueue<E>
// ********** constructors **********
/**
- * Construct an empty queue.
+ * Construct an empty queue with no node cache.
*/
public LinkedQueue() {
+ this(0);
+ }
+
+ /**
+ * Construct an empty queue with a node cache with the specified size.
+ * Specify a cache size of -1 for an unlimited cache.
+ */
+ public LinkedQueue(int cacheSize) {
+ this(LinkedQueue.<E>buildNodeFactory(cacheSize));
+ this.head = null;
+ }
+
+ private static <E> NodeFactory<E> buildNodeFactory(int cacheSize) {
+ if (cacheSize < -1) {
+ throw new IllegalArgumentException("Cache size must be greater than or equal to -1: " + cacheSize); //$NON-NLS-1$
+ }
+ return (cacheSize == 0) ? SimpleNodeFactory.<E>instance() : new CachingNodeFactory<E>(cacheSize);
+ }
+
+ private LinkedQueue(NodeFactory<E> nodeFactory) {
super();
- this.elements = new LinkedList<E>();
+ this.nodeFactory = nodeFactory;
+ this.head = null;
+ this.tail = null;
}
/**
* Construct a queue containing the elements of the specified
- * collection. The queue will dequeue its elements in the same
+ * collection and no node cache.
+ * The queue will dequeue its elements in the same
* order they are returned by the collection's iterator (i.e. the
* first element returned by the collection's iterator will be the
* first element returned by {@link #dequeue()}).
*/
- public LinkedQueue(Collection<? extends E> c) {
- super();
- this.elements = new LinkedList<E>(c);
+ public LinkedQueue(Collection<? extends E> collection) {
+ this(collection, 0);
+ }
+
+ /**
+ * Construct a queue containing the elements of the specified
+ * collection and a node cache with the specified size.
+ * The queue will dequeue its elements in reverse of the
+ * order they are returned by the collection's iterator (i.e. the
+ * first element returned by the collection's iterator will be the
+ * first element returned by {@link #dequeue()}).
+ * Specify a cache size of -1 for an unlimited cache.
+ */
+ public LinkedQueue(Collection<? extends E> collection, int cacheSize) {
+ this(cacheSize);
+ for (E element : collection) {
+ this.enqueue(element);
+ }
}
// ********** Queue implementation **********
public void enqueue(E element) {
- this.elements.addLast(element);
+ Node<E> newNode = this.nodeFactory.buildNode(element, null);
+ if (this.tail == null) {
+ this.head = newNode; // first node
+ } else {
+ this.tail.next = newNode;
+ }
+ this.tail = newNode;
}
public E dequeue() {
- return this.elements.removeFirst();
+ if (this.head == null) {
+ throw new NoSuchElementException();
+ }
+ Node<E> node = this.head;
+ this.head = node.next;
+ if (this.head == null) {
+ this.tail = null; // last node
+ }
+ E element = node.element;
+ this.nodeFactory.release(node);
+ return element;
}
public E peek() {
- return this.elements.getFirst();
+ if (this.head == null) {
+ throw new NoSuchElementException();
+ }
+ return this.head.element;
}
public boolean isEmpty() {
- return this.elements.isEmpty();
+ return this.head == null;
}
@@ -73,20 +133,170 @@ public class LinkedQueue<E>
@Override
public LinkedQueue<E> clone() {
- try {
- @SuppressWarnings("unchecked")
- LinkedQueue<E> clone = (LinkedQueue<E>) super.clone();
- @SuppressWarnings("unchecked")
- LinkedList<E> list = (LinkedList<E>) this.elements.clone();
- clone.elements = list;
- return clone;
- } catch (CloneNotSupportedException ex) {
- throw new InternalError();
+ LinkedQueue<E> clone = new LinkedQueue<E>(this.nodeFactory.copy());
+ E[] elements = this.buildElements();
+ for (E element : elements) {
+ clone.enqueue(element);
+ }
+ return clone;
+ }
+
+ @SuppressWarnings("unchecked")
+ private E[] buildElements() {
+ int size = this.size();
+ if (size == 0) {
+ return (E[]) ObjectTools.EMPTY_OBJECT_ARRAY;
+ }
+ E[] elements = (E[]) new Object[size];
+ int i = 0;
+ for (Node<E> node = this.head; node != null; node = node.next) {
+ elements[i++] = node.element;
+ }
+ return elements;
+ }
+
+ private int size() {
+ int size = 0;
+ for (Node<E> node = this.head; node != null; node = node.next) {
+ size++;
}
+ return size;
}
@Override
public String toString() {
- return this.elements.toString();
+ return Arrays.toString(this.buildElements());
+ }
+
+
+ // ********** Serializable "implementation" **********
+
+ private void writeObject(java.io.ObjectOutputStream stream) throws java.io.IOException {
+ // write nodeFactory (and any hidden stuff)
+ stream.defaultWriteObject();
+ Object[] elements = this.buildElements();
+ int len = elements.length;
+ stream.writeInt(len);
+ for (Object element : elements) {
+ stream.writeObject(element);
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ private void readObject(java.io.ObjectInputStream stream) throws java.io.IOException, ClassNotFoundException {
+ // read nodeFactory (and any hidden stuff)
+ stream.defaultReadObject();
+ int len = stream.readInt();
+ for (int i = len; i-- > 0; ) {
+ this.enqueue((E) stream.readObject());
+ }
+ }
+
+
+ // ********** Node classes **********
+
+ private static final class Node<E> {
+ E element;
+ Node<E> next;
+
+ Node(E element, Node<E> next) {
+ super();
+ this.element = element;
+ this.next = next;
+ }
+
+ @Override
+ public String toString() {
+ return ObjectTools.toString(this, this.element);
+ }
+ }
+
+ private abstract static class NodeFactory<E> {
+ NodeFactory() {
+ super();
+ }
+
+ Node<E> buildNode(E element, Node<E> next) {
+ return new Node<E>(element, next);
+ }
+
+ abstract void release(Node<E> node);
+
+ abstract NodeFactory<E> copy();
+ }
+
+ private static class SimpleNodeFactory<E>
+ extends NodeFactory<E>
+ implements Serializable
+ {
+ @SuppressWarnings("rawtypes")
+ public static final NodeFactory INSTANCE = new SimpleNodeFactory();
+ @SuppressWarnings("unchecked")
+ public static <E> NodeFactory<E> instance() {
+ return INSTANCE;
+ }
+
+ private SimpleNodeFactory() {
+ super();
+ }
+
+ @Override
+ void release(Node<E> node) {
+ // NOP
+ }
+
+ @Override
+ NodeFactory<E> copy() {
+ return this;
+ }
+
+ private static final long serialVersionUID = 1L;
+ private Object readResolve() {
+ // replace this object with the singleton
+ return INSTANCE;
+ }
+ }
+
+ private static final class CachingNodeFactory<E>
+ extends NodeFactory<E>
+ implements Serializable
+ {
+ private final int maxCacheSize;
+ private transient int cacheSize = 0;
+ private transient Node<E> cacheHead;
+ private static final long serialVersionUID = 1L;
+
+ CachingNodeFactory(int maxCacheSize) {
+ super();
+ this.maxCacheSize = maxCacheSize;
+ }
+
+ @Override
+ Node<E> buildNode(E element, Node<E> next) {
+ if (this.cacheHead == null) {
+ return super.buildNode(element, next);
+ }
+ Node<E> node = this.cacheHead;
+ this.cacheHead = node.next;
+ this.cacheSize--;
+ node.element = element;
+ node.next = next;
+ return node;
+ }
+
+ @Override
+ void release(Node<E> node) {
+ if ((this.maxCacheSize == -1) || (this.cacheSize < this.maxCacheSize)) {
+ node.element = null; // allow GC to work
+ node.next = this.cacheHead;
+ this.cacheHead = node;
+ this.cacheSize++;
+ }
+ }
+
+ @Override
+ NodeFactory<E> copy() {
+ return new CachingNodeFactory<E>(this.maxCacheSize);
+ }
}
}
diff --git a/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/LinkedQueueTests.java b/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/LinkedQueueTests.java
index 4a181feac9..31ec036f8b 100644
--- a/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/LinkedQueueTests.java
+++ b/common/tests/org.eclipse.jpt.common.utility.tests/src/org/eclipse/jpt/common/utility/tests/internal/collection/LinkedQueueTests.java
@@ -1,5 +1,5 @@
/*******************************************************************************
- * Copyright (c) 2012 Oracle. All rights reserved.
+ * Copyright (c) 2012, 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.
@@ -9,9 +9,12 @@
******************************************************************************/
package org.eclipse.jpt.common.utility.tests.internal.collection;
+import java.util.Arrays;
import org.eclipse.jpt.common.utility.collection.Queue;
+import org.eclipse.jpt.common.utility.internal.ObjectTools;
import org.eclipse.jpt.common.utility.internal.collection.LinkedQueue;
+@SuppressWarnings("nls")
public class LinkedQueueTests
extends QueueTests
{
@@ -23,4 +26,83 @@ public class LinkedQueueTests
Queue<String> buildQueue() {
return new LinkedQueue<String>();
}
+
+ public void testSize() {
+ Queue<String> queue = this.buildQueue();
+ String first = "first";
+ String second = "second";
+ String third = "third";
+
+ assertEquals(0, ((Integer) ObjectTools.execute(queue, "size")).intValue());
+ queue.enqueue(first);
+ queue.enqueue(second);
+ assertEquals(2, ((Integer) ObjectTools.execute(queue, "size")).intValue());
+ queue.enqueue(third);
+ assertEquals(3, ((Integer) ObjectTools.execute(queue, "size")).intValue());
+ queue.dequeue();
+ assertEquals(2, ((Integer) ObjectTools.execute(queue, "size")).intValue());
+ queue.dequeue();
+ queue.dequeue();
+ assertEquals(0, ((Integer) ObjectTools.execute(queue, "size")).intValue());
+ }
+
+ public void testBuildElements() {
+ Queue<String> queue = this.buildQueue();
+ String first = "first";
+ String second = "second";
+ String third = "third";
+ queue.enqueue(first);
+ queue.enqueue(second);
+ queue.enqueue(third);
+
+ Object[] elements = new Object[] { first, second, third };
+ assertTrue(Arrays.equals(elements, ((Object[]) ObjectTools.execute(queue, "buildElements"))));
+ }
+
+ public void testNodeCache() {
+ Queue<String> queue = new LinkedQueue<String>(2);
+ String first = "first";
+ String second = "second";
+ String third = "third";
+ String fourth = "fourth";
+ String fifth = "fifth";
+
+ Object factory = ObjectTools.get(queue, "nodeFactory");
+
+ this.verifyNodeCache(0, factory);
+ queue.enqueue(first);
+ this.verifyNodeCache(0, factory);
+ queue.enqueue(second);
+ queue.enqueue(third);
+ queue.enqueue(fourth);
+ queue.enqueue(fifth);
+ this.verifyNodeCache(0, factory);
+ assertNull(ObjectTools.get(factory, "cacheHead"));
+
+ queue.dequeue();
+ this.verifyNodeCache(1, factory);
+ queue.dequeue();
+ this.verifyNodeCache(2, factory);
+ queue.dequeue();
+ this.verifyNodeCache(2, factory);
+ queue.dequeue();
+ this.verifyNodeCache(2, factory);
+ queue.dequeue();
+ this.verifyNodeCache(2, factory);
+ queue.enqueue(first);
+ this.verifyNodeCache(1, factory);
+ queue.enqueue(second);
+ this.verifyNodeCache(0, factory);
+ queue.enqueue(third);
+ this.verifyNodeCache(0, factory);
+ }
+
+ public void verifyNodeCache(int size, Object factory) {
+ assertEquals(size, ((Integer) ObjectTools.get(factory, "cacheSize")).intValue());
+ int nodeCount = 0;
+ for (Object node = ObjectTools.get(factory, "cacheHead"); node != null; node = ObjectTools.get(node, "next")) {
+ nodeCount++;
+ }
+ assertEquals(size, nodeCount);
+ }
}

Back to the top