--- jsr166/src/main/java/util/ArrayDeque.java 2013/01/16 21:25:33 1.43
+++ jsr166/src/main/java/util/ArrayDeque.java 2015/09/18 02:06:44 1.69
@@ -1,42 +1,12 @@
/*
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation. Oracle designates this
- * particular file as subject to the "Classpath" exception as provided
- * by Oracle in the LICENSE file that accompanied this code.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-
-/*
- * This file is available under and governed by the GNU General Public
- * License version 2 only, as published by the Free Software Foundation.
- * However, the following notice accompanied the original version of this
- * file:
- *
* Written by Josh Bloch of Google Inc. and released to the public domain,
* as explained at http://creativecommons.org/publicdomain/zero/1.0/.
*/
package java.util;
-import java.util.Spliterator;
-import java.util.stream.Stream;
-import java.util.stream.Streams;
-import java.util.function.Block;
+
+import java.io.Serializable;
+import java.util.function.Consumer;
/**
* Resizable-array implementation of the {@link Deque} interface. Array
@@ -48,16 +18,18 @@ import java.util.function.Block;
* when used as a queue.
*
*
Most {@code ArrayDeque} operations run in amortized constant time.
- * Exceptions include {@link #remove(Object) remove}, {@link
- * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
- * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
- * iterator.remove()}, and the bulk operations, all of which run in linear
- * time.
- *
- *
The iterators returned by this class's {@code iterator} method are
- * fail-fast: If the deque is modified at any time after the iterator
- * is created, in any way except through the iterator's own {@code remove}
- * method, the iterator will generally throw a {@link
+ * Exceptions include
+ * {@link #remove(Object) remove},
+ * {@link #removeFirstOccurrence removeFirstOccurrence},
+ * {@link #removeLastOccurrence removeLastOccurrence},
+ * {@link #contains contains},
+ * {@link #iterator iterator.remove()},
+ * and the bulk operations, all of which run in linear time.
+ *
+ *
The iterators returned by this class's {@link #iterator() iterator}
+ * method are fail-fast: If the deque is modified at any time after
+ * the iterator is created, in any way except through the iterator's own
+ * {@code remove} method, the iterator will generally throw a {@link
* ConcurrentModificationException}. Thus, in the face of concurrent
* modification, the iterator fails quickly and cleanly, rather than risking
* arbitrary, non-deterministic behavior at an undetermined time in the
@@ -81,10 +53,10 @@ import java.util.function.Block;
*
* @author Josh Bloch and Doug Lea
* @since 1.6
- * @param the type of elements held in this collection
+ * @param the type of elements held in this deque
*/
public class ArrayDeque extends AbstractCollection
- implements Deque, Cloneable, java.io.Serializable
+ implements Deque, Cloneable, Serializable
{
/**
* The array in which the elements of the deque are stored.
@@ -164,24 +136,6 @@ public class ArrayDeque extends Abstr
}
/**
- * Copies the elements from our element array into the specified array,
- * in order (from first to last element in the deque). It is assumed
- * that the array is large enough to hold all elements in the deque.
- *
- * @return its argument
- */
- private T[] copyElements(T[] a) {
- if (head < tail) {
- System.arraycopy(elements, head, a, 0, size());
- } else if (head > tail) {
- int headPortionLen = elements.length - head;
- System.arraycopy(elements, head, a, 0, headPortionLen);
- System.arraycopy(elements, 0, a, headPortionLen, tail);
- }
- return a;
- }
-
- /**
* Constructs an empty array deque with an initial capacity
* sufficient to hold 16 elements.
*/
@@ -293,25 +247,27 @@ public class ArrayDeque extends Abstr
}
public E pollFirst() {
- int h = head;
+ final Object[] elements = this.elements;
+ final int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
- if (result == null)
- return null;
- elements[h] = null; // Must null out slot
- head = (h + 1) & (elements.length - 1);
+ if (result != null) {
+ elements[h] = null; // Must null out slot
+ head = (h + 1) & (elements.length - 1);
+ }
return result;
}
public E pollLast() {
- int t = (tail - 1) & (elements.length - 1);
+ final Object[] elements = this.elements;
+ final int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
- if (result == null)
- return null;
- elements[t] = null;
- tail = t;
+ if (result != null) {
+ elements[t] = null;
+ tail = t;
+ }
return result;
}
@@ -361,17 +317,15 @@ public class ArrayDeque extends Abstr
* @return {@code true} if the deque contained the specified element
*/
public boolean removeFirstOccurrence(Object o) {
- if (o == null)
- return false;
- int mask = elements.length - 1;
- int i = head;
- Object x;
- while ( (x = elements[i]) != null) {
- if (o.equals(x)) {
- delete(i);
- return true;
+ if (o != null) {
+ int mask = elements.length - 1;
+ int i = head;
+ for (Object x; (x = elements[i]) != null; i = (i + 1) & mask) {
+ if (o.equals(x)) {
+ delete(i);
+ return true;
+ }
}
- i = (i + 1) & mask;
}
return false;
}
@@ -389,17 +343,15 @@ public class ArrayDeque extends Abstr
* @return {@code true} if the deque contained the specified element
*/
public boolean removeLastOccurrence(Object o) {
- if (o == null)
- return false;
- int mask = elements.length - 1;
- int i = (tail - 1) & mask;
- Object x;
- while ( (x = elements[i]) != null) {
- if (o.equals(x)) {
- delete(i);
- return true;
+ if (o != null) {
+ int mask = elements.length - 1;
+ int i = (tail - 1) & mask;
+ for (Object x; (x = elements[i]) != null; i = (i - 1) & mask) {
+ if (o.equals(x)) {
+ delete(i);
+ return true;
+ }
}
- i = (i - 1) & mask;
}
return false;
}
@@ -656,14 +608,28 @@ public class ArrayDeque extends Abstr
}
lastRet = -1;
}
+
+ public void forEachRemaining(Consumer super E> action) {
+ Objects.requireNonNull(action);
+ Object[] a = elements;
+ int m = a.length - 1, f = fence, i = cursor;
+ cursor = f;
+ while (i != f) {
+ @SuppressWarnings("unchecked") E e = (E)a[i];
+ i = (i + 1) & m;
+ if (e == null)
+ throw new ConcurrentModificationException();
+ action.accept(e);
+ }
+ }
}
+ /**
+ * This class is nearly a mirror-image of DeqIterator, using tail
+ * instead of head for initial cursor, and head instead of tail
+ * for fence.
+ */
private class DescendingIterator implements Iterator {
- /*
- * This class is nearly a mirror-image of DeqIterator, using
- * tail instead of head for initial cursor, and head instead of
- * tail for fence.
- */
private int cursor = tail;
private int fence = head;
private int lastRet = -1;
@@ -704,15 +670,13 @@ public class ArrayDeque extends Abstr
* @return {@code true} if this deque contains the specified element
*/
public boolean contains(Object o) {
- if (o == null)
- return false;
- int mask = elements.length - 1;
- int i = head;
- Object x;
- while ( (x = elements[i]) != null) {
- if (o.equals(x))
- return true;
- i = (i + 1) & mask;
+ if (o != null) {
+ int mask = elements.length - 1;
+ int i = head;
+ for (Object x; (x = elements[i]) != null; i = (i + 1) & mask) {
+ if (o.equals(x))
+ return true;
+ }
}
return false;
}
@@ -725,7 +689,7 @@ public class ArrayDeque extends Abstr
* Returns {@code true} if this deque contained the specified element
* (or equivalently, if this deque changed as a result of the call).
*
- * This method is equivalent to {@link #removeFirstOccurrence}.
+ *
This method is equivalent to {@link #removeFirstOccurrence(Object)}.
*
* @param o element to be removed from this deque, if present
* @return {@code true} if this deque contained the specified element
@@ -766,7 +730,14 @@ public class ArrayDeque extends Abstr
* @return an array containing all of the elements in this deque
*/
public Object[] toArray() {
- return copyElements(new Object[size()]);
+ final int head = this.head;
+ final int tail = this.tail;
+ boolean wrap = (tail < head);
+ int end = wrap ? tail + elements.length : tail;
+ Object[] a = Arrays.copyOfRange(elements, head, end);
+ if (wrap)
+ System.arraycopy(elements, 0, a, elements.length - head, tail);
+ return a;
}
/**
@@ -791,7 +762,7 @@ public class ArrayDeque extends Abstr
* The following code can be used to dump the deque into a newly
* allocated array of {@code String}:
*
- * {@code String[] y = x.toArray(new String[0]);}
+ * {@code String[] y = x.toArray(new String[0]);}
*
* Note that {@code toArray(new Object[0])} is identical in function to
* {@code toArray()}.
@@ -807,13 +778,22 @@ public class ArrayDeque extends Abstr
*/
@SuppressWarnings("unchecked")
public T[] toArray(T[] a) {
- int size = size();
- if (a.length < size)
- a = (T[])java.lang.reflect.Array.newInstance(
- a.getClass().getComponentType(), size);
- copyElements(a);
- if (a.length > size)
- a[size] = null;
+ final int head = this.head;
+ final int tail = this.tail;
+ boolean wrap = (tail < head);
+ int size = (tail - head) + (wrap ? elements.length : 0);
+ int firstLeg = size - (wrap ? tail : 0);
+ int len = a.length;
+ if (size > len) {
+ a = (T[]) Arrays.copyOfRange(elements, head, head + size,
+ a.getClass());
+ } else {
+ System.arraycopy(elements, head, a, 0, firstLeg);
+ if (size < len)
+ a[size] = null;
+ }
+ if (wrap)
+ System.arraycopy(elements, 0, a, firstLeg, tail);
return a;
}
@@ -840,6 +820,8 @@ public class ArrayDeque extends Abstr
/**
* Saves this deque to a stream (that is, serializes it).
*
+ * @param s the stream
+ * @throws java.io.IOException if an I/O error occurs
* @serialData The current size ({@code int}) of the deque,
* followed by all of its elements (each an object reference) in
* first-to-last order.
@@ -859,6 +841,10 @@ public class ArrayDeque extends Abstr
/**
* Reconstitutes this deque from a stream (that is, deserializes it).
+ * @param s the stream
+ * @throws ClassNotFoundException if the class of a serialized object
+ * could not be found
+ * @throws java.io.IOException if an I/O error occurs
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
@@ -875,113 +861,98 @@ public class ArrayDeque extends Abstr
elements[i] = s.readObject();
}
- public Stream stream() {
- int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
- return Streams.stream
- (() -> new DeqSpliterator(this, head, tail), flags);
- }
- public Stream parallelStream() {
- int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
- return Streams.parallelStream
- (() -> new DeqSpliterator(this, head, tail), flags);
+ /**
+ * Creates a late-binding
+ * and fail-fast {@link Spliterator} over the elements in this
+ * deque.
+ *
+ * The {@code Spliterator} reports {@link Spliterator#SIZED},
+ * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
+ * {@link Spliterator#NONNULL}. Overriding implementations should document
+ * the reporting of additional characteristic values.
+ *
+ * @return a {@code Spliterator} over the elements in this deque
+ * @since 1.8
+ */
+ public Spliterator spliterator() {
+ return new DeqSpliterator<>(this, -1, -1);
}
-
- static final class DeqSpliterator implements Spliterator, Iterator {
+ static final class DeqSpliterator implements Spliterator {
private final ArrayDeque deq;
- private final Object[] array;
- private final int fence; // initially tail
- private int index; // current index, modified on traverse/split
+ private int fence; // -1 until first use
+ private int index; // current index, modified on traverse/split
- /** Create new spliterator covering the given array and range */
+ /** Creates new spliterator covering the given array and range */
DeqSpliterator(ArrayDeque deq, int origin, int fence) {
- this.deq = deq; this.array = deq.elements;
- this.index = origin; this.fence = fence;
+ this.deq = deq;
+ this.index = origin;
+ this.fence = fence;
}
- public DeqSpliterator trySplit() {
- int n = array.length;
- int h = index, t = fence;
+ private int getFence() { // force initialization
+ int t;
+ if ((t = fence) < 0) {
+ t = fence = deq.tail;
+ index = deq.head;
+ }
+ return t;
+ }
+
+ public Spliterator trySplit() {
+ int t = getFence(), h = index, n = deq.elements.length;
if (h != t && ((h + 1) & (n - 1)) != t) {
if (h > t)
t += n;
int m = ((h + t) >>> 1) & (n - 1);
- return new DeqSpliterator(deq, h, index = m);
+ return new DeqSpliterator<>(deq, h, index = m);
}
return null;
}
- @SuppressWarnings("unchecked")
- public void forEach(Block super E> block) {
- if (block == null)
+ public void forEachRemaining(Consumer super E> consumer) {
+ if (consumer == null)
throw new NullPointerException();
- Object[] a = array;
- if (a != deq.elements)
- throw new ConcurrentModificationException();
- int m = a.length - 1, f = fence, i = index;
+ Object[] a = deq.elements;
+ int m = a.length - 1, f = getFence(), i = index;
index = f;
while (i != f) {
- Object e = a[i];
+ @SuppressWarnings("unchecked") E e = (E)a[i];
+ i = (i + 1) & m;
if (e == null)
throw new ConcurrentModificationException();
- block.accept((E)e);
- i = (i + 1) & m;
+ consumer.accept(e);
}
}
- @SuppressWarnings("unchecked")
- public boolean tryAdvance(Block super E> block) {
- if (block == null)
+ public boolean tryAdvance(Consumer super E> consumer) {
+ if (consumer == null)
throw new NullPointerException();
- Object[] a = array;
- if (a != deq.elements)
- throw new ConcurrentModificationException();
- int m = a.length - 1, i = index;
- if (i != fence) {
- Object e = a[i];
+ Object[] a = deq.elements;
+ int m = a.length - 1, f = getFence(), i = index;
+ if (i != f) {
+ @SuppressWarnings("unchecked") E e = (E)a[i];
+ index = (i + 1) & m;
if (e == null)
throw new ConcurrentModificationException();
- block.accept((E)e);
- index = (i + 1) & m;
+ consumer.accept(e);
return true;
}
return false;
}
- // Iterator support
- public Iterator iterator() {
- return this;
- }
-
- public boolean hasNext() {
- return index >= 0 && index != fence;
- }
-
- @SuppressWarnings("unchecked")
- public E next() {
- if (index < 0 || index == fence)
- throw new NoSuchElementException();
- Object[] a = array;
- if (a != deq.elements)
- throw new ConcurrentModificationException();
- Object e = a[index];
- if (e == null)
- throw new ConcurrentModificationException();
- index = (index + 1) & (a.length - 1);
- return (E) e;
- }
-
- public void remove() { throw new UnsupportedOperationException(); }
-
- // Other spliterator methods
public long estimateSize() {
- int n = fence - index;
+ int n = getFence() - index;
if (n < 0)
- n += array.length;
- return (long)n;
+ n += deq.elements.length;
+ return (long) n;
+ }
+
+ @Override
+ public int characteristics() {
+ return Spliterator.ORDERED | Spliterator.SIZED |
+ Spliterator.NONNULL | Spliterator.SUBSIZED;
}
- public boolean hasExactSize() { return true; }
- public boolean hasExactSplits() { return true; }
}
}