--- jsr166/src/main/java/util/ArrayDeque.java	2013/02/11 07:42:43	1.46
+++ jsr166/src/main/java/util/ArrayDeque.java	2013/03/27 23:09:34	1.54
@@ -1,14 +1,13 @@
 /*
- * Written by Doug Lea with assistance from members of JCP JSR-166
- * Expert Group and released to the public domain, as explained at
- * http://creativecommons.org/publicdomain/zero/1.0/
+ * 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.io.Serializable;
+import java.util.function.Consumer;
 import java.util.stream.Stream;
 import java.util.stream.Streams;
-import java.util.function.Consumer;
 
 /**
  * Resizable-array implementation of the {@link Deque} interface.  Array
@@ -20,16 +19,18 @@ import java.util.function.Consumer;
  * when used as a queue.
  *
  * <p>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.
+ * 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.
  *
- * <p>The iterators returned by this class's {@code iterator} method are
- * <i>fail-fast</i>: 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
+ * <p>The iterators returned by this class's {@link #iterator() iterator}
+ * method are <em>fail-fast</em>: 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
@@ -56,7 +57,7 @@ import java.util.function.Consumer;
  * @param <E> the type of elements held in this collection
  */
 public class ArrayDeque<E> extends AbstractCollection<E>
-                           implements Deque<E>, Cloneable, java.io.Serializable
+                           implements Deque<E>, Cloneable, Serializable
 {
     /**
      * The array in which the elements of the deque are stored.
@@ -136,24 +137,6 @@ public class ArrayDeque<E> 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> 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.
      */
@@ -630,12 +613,12 @@ public class ArrayDeque<E> extends Abstr
         }
     }
 
+    /**
+     * 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<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 int cursor = tail;
         private int fence = head;
         private int lastRet = -1;
@@ -738,7 +721,14 @@ public class ArrayDeque<E> 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;
     }
 
     /**
@@ -779,13 +769,22 @@ public class ArrayDeque<E> extends Abstr
      */
     @SuppressWarnings("unchecked")
     public <T> 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;
     }
 
@@ -847,80 +846,85 @@ public class ArrayDeque<E> extends Abstr
             elements[i] = s.readObject();
     }
 
-    public Stream<E> stream() {
-        int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
-        return Streams.stream
-            (() -> new DeqSpliterator<E>(this, head, tail), flags);
-    }
-    public Stream<E> parallelStream() {
-        int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
-        return Streams.parallelStream
-            (() -> new DeqSpliterator<E>(this, head, tail), flags);
+    public Spliterator<E> spliterator() {
+        return new DeqSpliterator<E>(this, -1, -1);
     }
 
-
     static final class DeqSpliterator<E> implements Spliterator<E> {
         private final ArrayDeque<E> deq;
-        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<E> deq, int origin, int fence) {
-            this.deq = deq; this.index = origin; this.fence = fence;
+            this.deq = deq;
+            this.index = origin;
+            this.fence = fence;
         }
 
-        public DeqSpliterator<E> trySplit() {
-            int n = deq.elements.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<E> 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<E>(deq, h, index = m);
+                return new DeqSpliterator<>(deq, h, index = m);
             }
             return null;
         }
 
-        public void forEach(Consumer<? super E> block) {
-            if (block == null)
+        public void forEachRemaining(Consumer<? super E> consumer) {
+            if (consumer == null)
                 throw new NullPointerException();
             Object[] a = deq.elements;
-            int m = a.length - 1, f = fence, i = index;
+            int m = a.length - 1, f = getFence(), i = index;
             index = f;
             while (i != f) {
                 @SuppressWarnings("unchecked") E e = (E)a[i];
                 i = (i + 1) & m;
                 if (e == null)
                     throw new ConcurrentModificationException();
-                block.accept(e);
+                consumer.accept(e);
             }
         }
 
-        public boolean tryAdvance(Consumer<? super E> block) {
-            if (block == null)
+        public boolean tryAdvance(Consumer<? super E> consumer) {
+            if (consumer == null)
                 throw new NullPointerException();
             Object[] a = deq.elements;
-            int m = a.length - 1, i = index;
+            int m = a.length - 1, f = getFence(), i = index;
             if (i != fence) {
                 @SuppressWarnings("unchecked") E e = (E)a[i];
                 index = (i + 1) & m;
                 if (e == null)
                     throw new ConcurrentModificationException();
-                block.accept(e);
+                consumer.accept(e);
                 return true;
             }
             return false;
         }
 
-        // Other spliterator methods
         public long estimateSize() {
-            int n = fence - index;
+            int n = getFence() - index;
             if (n < 0)
                 n += deq.elements.length;
-            return (long)n;
+            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; }
     }
 
 }