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.47 by dl, Sun Feb 17 23:36:16 2013 UTC vs.
Revision 1.54 by dl, Wed Mar 27 23:09:34 2013 UTC

# Line 19 | Line 19 | import java.util.stream.Streams;
19   * when used as a queue.
20   *
21   * <p>Most {@code ArrayDeque} operations run in amortized constant time.
22 < * Exceptions include {@link #remove(Object) remove}, {@link
23 < * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
24 < * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
25 < * iterator.remove()}, and the bulk operations, all of which run in linear
26 < * time.
22 > * Exceptions include
23 > * {@link #remove(Object) remove},
24 > * {@link #removeFirstOccurrence removeFirstOccurrence},
25 > * {@link #removeLastOccurrence removeLastOccurrence},
26 > * {@link #contains contains},
27 > * {@link #iterator iterator.remove()},
28 > * and the bulk operations, all of which run in linear time.
29   *
30 < * <p>The iterators returned by this class's {@code iterator} method are
31 < * <i>fail-fast</i>: If the deque is modified at any time after the iterator
32 < * is created, in any way except through the iterator's own {@code remove}
33 < * method, the iterator will generally throw a {@link
30 > * <p>The iterators returned by this class's {@link #iterator() iterator}
31 > * method are <em>fail-fast</em>: If the deque is modified at any time after
32 > * the iterator is created, in any way except through the iterator's own
33 > * {@code remove} method, the iterator will generally throw a {@link
34   * ConcurrentModificationException}.  Thus, in the face of concurrent
35   * modification, the iterator fails quickly and cleanly, rather than risking
36   * arbitrary, non-deterministic behavior at an undetermined time in the
# Line 135 | Line 137 | public class ArrayDeque<E> extends Abstr
137      }
138  
139      /**
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 –    /**
140       * Constructs an empty array deque with an initial capacity
141       * sufficient to hold 16 elements.
142       */
# Line 629 | Line 613 | public class ArrayDeque<E> extends Abstr
613          }
614      }
615  
616 +    /**
617 +     * This class is nearly a mirror-image of DeqIterator, using tail
618 +     * instead of head for initial cursor, and head instead of tail
619 +     * for fence.
620 +     */
621      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 –         */
622          private int cursor = tail;
623          private int fence = head;
624          private int lastRet = -1;
# Line 737 | Line 721 | public class ArrayDeque<E> extends Abstr
721       * @return an array containing all of the elements in this deque
722       */
723      public Object[] toArray() {
724 <        return copyElements(new Object[size()]);
724 >        final int head = this.head;
725 >        final int tail = this.tail;
726 >        boolean wrap = (tail < head);
727 >        int end = wrap ? tail + elements.length : tail;
728 >        Object[] a = Arrays.copyOfRange(elements, head, end);
729 >        if (wrap)
730 >            System.arraycopy(elements, 0, a, elements.length - head, tail);
731 >        return a;
732      }
733  
734      /**
# Line 778 | Line 769 | public class ArrayDeque<E> extends Abstr
769       */
770      @SuppressWarnings("unchecked")
771      public <T> T[] toArray(T[] a) {
772 <        int size = size();
773 <        if (a.length < size)
774 <            a = (T[])java.lang.reflect.Array.newInstance(
775 <                    a.getClass().getComponentType(), size);
776 <        copyElements(a);
777 <        if (a.length > size)
778 <            a[size] = null;
772 >        final int head = this.head;
773 >        final int tail = this.tail;
774 >        boolean wrap = (tail < head);
775 >        int size = (tail - head) + (wrap ? elements.length : 0);
776 >        int firstLeg = size - (wrap ? tail : 0);
777 >        int len = a.length;
778 >        if (size > len) {
779 >            a = (T[]) Arrays.copyOfRange(elements, head, head + size,
780 >                                         a.getClass());
781 >        } else {
782 >            System.arraycopy(elements, head, a, 0, firstLeg);
783 >            if (size < len)
784 >                a[size] = null;
785 >        }
786 >        if (wrap)
787 >            System.arraycopy(elements, 0, a, firstLeg, tail);
788          return a;
789      }
790  
# Line 846 | Line 846 | public class ArrayDeque<E> extends Abstr
846              elements[i] = s.readObject();
847      }
848  
849 <    Spliterator<E> spliterator() {
849 >    public Spliterator<E> spliterator() {
850          return new DeqSpliterator<E>(this, -1, -1);
851      }
852  
853 –    public Stream<E> stream() {
854 –        return Streams.stream(spliterator());
855 –    }
856 –
857 –    public Stream<E> parallelStream() {
858 –        return Streams.parallelStream(spliterator());
859 –    }
860 –
853      static final class DeqSpliterator<E> implements Spliterator<E> {
854          private final ArrayDeque<E> deq;
855          private int fence;  // -1 until first use
856          private int index;  // current index, modified on traverse/split
857 <        
858 <        /** Create new spliterator covering the given array and range */
857 >
858 >        /** Creates new spliterator covering the given array and range */
859          DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
860              this.deq = deq;
861              this.index = origin;
# Line 879 | Line 871 | public class ArrayDeque<E> extends Abstr
871              return t;
872          }
873  
874 <        public DeqSpliterator<E> trySplit() {
874 >        public Spliterator<E> trySplit() {
875              int t = getFence(), h = index, n = deq.elements.length;
876              if (h != t && ((h + 1) & (n - 1)) != t) {
877                  if (h > t)
# Line 890 | Line 882 | public class ArrayDeque<E> extends Abstr
882              return null;
883          }
884  
885 <        public void forEach(Consumer<? super E> consumer) {
885 >        public void forEachRemaining(Consumer<? super E> consumer) {
886              if (consumer == null)
887                  throw new NullPointerException();
888              Object[] a = deq.elements;
# Line 930 | Line 922 | public class ArrayDeque<E> extends Abstr
922  
923          @Override
924          public int characteristics() {
925 <            return Spliterator.ORDERED | Spliterator.SIZED |
925 >            return Spliterator.ORDERED | Spliterator.SIZED |
926                  Spliterator.NONNULL | Spliterator.SUBSIZED;
927          }
928      }

Diff Legend

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