ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/ArrayDeque.java
(Generate patch)

Comparing jsr166/src/main/java/util/ArrayDeque.java (file contents):
Revision 1.48 by jsr166, Mon Feb 18 01:30:23 2013 UTC vs.
Revision 1.55 by jsr166, Thu May 2 06:02:17 2013 UTC

# Line 7 | Line 7 | package java.util;
7   import java.io.Serializable;
8   import java.util.function.Consumer;
9   import java.util.stream.Stream;
10 – import java.util.stream.Streams;
10  
11   /**
12   * Resizable-array implementation of the {@link Deque} interface.  Array
# Line 19 | Line 18 | import java.util.stream.Streams;
18   * when used as a queue.
19   *
20   * <p>Most {@code ArrayDeque} operations run in amortized constant time.
21 < * Exceptions include {@link #remove(Object) remove}, {@link
22 < * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
23 < * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
24 < * iterator.remove()}, and the bulk operations, all of which run in linear
25 < * time.
21 > * Exceptions include
22 > * {@link #remove(Object) remove},
23 > * {@link #removeFirstOccurrence removeFirstOccurrence},
24 > * {@link #removeLastOccurrence removeLastOccurrence},
25 > * {@link #contains contains},
26 > * {@link #iterator iterator.remove()},
27 > * and the bulk operations, all of which run in linear time.
28   *
29 < * <p>The iterators returned by this class's {@code iterator} method are
30 < * <i>fail-fast</i>: If the deque is modified at any time after the iterator
31 < * is created, in any way except through the iterator's own {@code remove}
32 < * method, the iterator will generally throw a {@link
29 > * <p>The iterators returned by this class's {@link #iterator() iterator}
30 > * method are <em>fail-fast</em>: If the deque is modified at any time after
31 > * the iterator is created, in any way except through the iterator's own
32 > * {@code remove} method, the iterator will generally throw a {@link
33   * ConcurrentModificationException}.  Thus, in the face of concurrent
34   * modification, the iterator fails quickly and cleanly, rather than risking
35   * arbitrary, non-deterministic behavior at an undetermined time in the
# Line 135 | Line 136 | public class ArrayDeque<E> extends Abstr
136      }
137  
138      /**
138 –     * Copies the elements from our element array into the specified array,
139 –     * in order (from first to last element in the deque).  It is assumed
140 –     * that the array is large enough to hold all elements in the deque.
141 –     *
142 –     * @return its argument
143 –     */
144 –    private <T> T[] copyElements(T[] a) {
145 –        if (head < tail) {
146 –            System.arraycopy(elements, head, a, 0, size());
147 –        } else if (head > tail) {
148 –            int headPortionLen = elements.length - head;
149 –            System.arraycopy(elements, head, a, 0, headPortionLen);
150 –            System.arraycopy(elements, 0, a, headPortionLen, tail);
151 –        }
152 –        return a;
153 –    }
154 –
155 –    /**
139       * Constructs an empty array deque with an initial capacity
140       * sufficient to hold 16 elements.
141       */
# Line 629 | Line 612 | public class ArrayDeque<E> extends Abstr
612          }
613      }
614  
615 +    /**
616 +     * This class is nearly a mirror-image of DeqIterator, using tail
617 +     * instead of head for initial cursor, and head instead of tail
618 +     * for fence.
619 +     */
620      private class DescendingIterator implements Iterator<E> {
633 –        /*
634 –         * This class is nearly a mirror-image of DeqIterator, using
635 –         * tail instead of head for initial cursor, and head instead of
636 –         * tail for fence.
637 –         */
621          private int cursor = tail;
622          private int fence = head;
623          private int lastRet = -1;
# Line 737 | Line 720 | public class ArrayDeque<E> extends Abstr
720       * @return an array containing all of the elements in this deque
721       */
722      public Object[] toArray() {
723 <        return copyElements(new Object[size()]);
723 >        final int head = this.head;
724 >        final int tail = this.tail;
725 >        boolean wrap = (tail < head);
726 >        int end = wrap ? tail + elements.length : tail;
727 >        Object[] a = Arrays.copyOfRange(elements, head, end);
728 >        if (wrap)
729 >            System.arraycopy(elements, 0, a, elements.length - head, tail);
730 >        return a;
731      }
732  
733      /**
# Line 778 | Line 768 | public class ArrayDeque<E> extends Abstr
768       */
769      @SuppressWarnings("unchecked")
770      public <T> T[] toArray(T[] a) {
771 <        int size = size();
772 <        if (a.length < size)
773 <            a = (T[])java.lang.reflect.Array.newInstance(
774 <                    a.getClass().getComponentType(), size);
775 <        copyElements(a);
776 <        if (a.length > size)
777 <            a[size] = null;
771 >        final int head = this.head;
772 >        final int tail = this.tail;
773 >        boolean wrap = (tail < head);
774 >        int size = (tail - head) + (wrap ? elements.length : 0);
775 >        int firstLeg = size - (wrap ? tail : 0);
776 >        int len = a.length;
777 >        if (size > len) {
778 >            a = (T[]) Arrays.copyOfRange(elements, head, head + size,
779 >                                         a.getClass());
780 >        } else {
781 >            System.arraycopy(elements, head, a, 0, firstLeg);
782 >            if (size < len)
783 >                a[size] = null;
784 >        }
785 >        if (wrap)
786 >            System.arraycopy(elements, 0, a, firstLeg, tail);
787          return a;
788      }
789  
# Line 846 | Line 845 | public class ArrayDeque<E> extends Abstr
845              elements[i] = s.readObject();
846      }
847  
848 <    Spliterator<E> spliterator() {
848 >    public Spliterator<E> spliterator() {
849          return new DeqSpliterator<E>(this, -1, -1);
850      }
851  
853 –    public Stream<E> stream() {
854 –        return Streams.stream(spliterator());
855 –    }
856 –
857 –    public Stream<E> parallelStream() {
858 –        return Streams.parallelStream(spliterator());
859 –    }
860 –
852      static final class DeqSpliterator<E> implements Spliterator<E> {
853          private final ArrayDeque<E> deq;
854          private int fence;  // -1 until first use
855          private int index;  // current index, modified on traverse/split
856  
857 <        /** Create new spliterator covering the given array and range */
857 >        /** Creates new spliterator covering the given array and range */
858          DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
859              this.deq = deq;
860              this.index = origin;
# Line 879 | Line 870 | public class ArrayDeque<E> extends Abstr
870              return t;
871          }
872  
873 <        public DeqSpliterator<E> trySplit() {
873 >        public Spliterator<E> trySplit() {
874              int t = getFence(), h = index, n = deq.elements.length;
875              if (h != t && ((h + 1) & (n - 1)) != t) {
876                  if (h > t)
# Line 890 | Line 881 | public class ArrayDeque<E> extends Abstr
881              return null;
882          }
883  
884 <        public void forEach(Consumer<? super E> consumer) {
884 >        public void forEachRemaining(Consumer<? super E> consumer) {
885              if (consumer == null)
886                  throw new NullPointerException();
887              Object[] a = deq.elements;

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines