diff options
author | Brian Vosburgh | 2015-07-21 17:37:05 +0000 |
---|---|---|
committer | Brian Vosburgh | 2015-07-21 18:17:08 +0000 |
commit | f3527a8debc90335c4fdd0f426174b0e9bb57621 (patch) | |
tree | dd422ef8c1d6bac4bdc455a22aa3733f72168379 | |
parent | 46385b4d5995580ff5fedd27b15ec7683bfca7fa (diff) | |
download | webtools.dali-f3527a8debc90335c4fdd0f426174b0e9bb57621.tar.gz webtools.dali-f3527a8debc90335c4fdd0f426174b0e9bb57621.tar.xz webtools.dali-f3527a8debc90335c4fdd0f426174b0e9bb57621.zip |
rework LinkedQueue
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); + } } |