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.61 by jsr166, Wed Dec 31 07:54:13 2014 UTC

# Line 4 | Line 4
4   */
5  
6   package java.util;
7 +
8   import java.io.Serializable;
9   import java.util.function.Consumer;
10   import java.util.stream.Stream;
10 – import java.util.stream.Streams;
11  
12   /**
13   * Resizable-array implementation of the {@link Deque} interface.  Array
# 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 52 | Line 54 | import java.util.stream.Streams;
54   *
55   * @author  Josh Bloch and Doug Lea
56   * @since   1.6
57 < * @param <E> the type of elements held in this collection
57 > * @param <E> the type of elements held in this deque
58   */
59   public class ArrayDeque<E> extends AbstractCollection<E>
60                             implements Deque<E>, Cloneable, Serializable
# 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 332 | Line 316 | public class ArrayDeque<E> extends Abstr
316       * @return {@code true} if the deque contained the specified element
317       */
318      public boolean removeFirstOccurrence(Object o) {
319 <        if (o == null)
320 <            return false;
321 <        int mask = elements.length - 1;
322 <        int i = head;
323 <        Object x;
324 <        while ( (x = elements[i]) != null) {
325 <            if (o.equals(x)) {
326 <                delete(i);
343 <                return true;
319 >        if (o != null) {
320 >            int mask = elements.length - 1;
321 >            int i = head;
322 >            for (Object x; (x = elements[i]) != null; i = (i + 1) & mask) {
323 >                if (o.equals(x)) {
324 >                    delete(i);
325 >                    return true;
326 >                }
327              }
345 –            i = (i + 1) & mask;
328          }
329          return false;
330      }
# Line 360 | Line 342 | public class ArrayDeque<E> extends Abstr
342       * @return {@code true} if the deque contained the specified element
343       */
344      public boolean removeLastOccurrence(Object o) {
345 <        if (o == null)
346 <            return false;
347 <        int mask = elements.length - 1;
348 <        int i = (tail - 1) & mask;
349 <        Object x;
350 <        while ( (x = elements[i]) != null) {
351 <            if (o.equals(x)) {
352 <                delete(i);
371 <                return true;
345 >        if (o != null) {
346 >            int mask = elements.length - 1;
347 >            int i = (tail - 1) & mask;
348 >            for (Object x; (x = elements[i]) != null; i = (i - 1) & mask) {
349 >                if (o.equals(x)) {
350 >                    delete(i);
351 >                    return true;
352 >                }
353              }
373 –            i = (i - 1) & mask;
354          }
355          return false;
356      }
# Line 629 | Line 609 | public class ArrayDeque<E> extends Abstr
609          }
610      }
611  
612 +    /**
613 +     * This class is nearly a mirror-image of DeqIterator, using tail
614 +     * instead of head for initial cursor, and head instead of tail
615 +     * for fence.
616 +     */
617      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 –         */
618          private int cursor = tail;
619          private int fence = head;
620          private int lastRet = -1;
# Line 675 | Line 655 | public class ArrayDeque<E> extends Abstr
655       * @return {@code true} if this deque contains the specified element
656       */
657      public boolean contains(Object o) {
658 <        if (o == null)
659 <            return false;
660 <        int mask = elements.length - 1;
661 <        int i = head;
662 <        Object x;
663 <        while ( (x = elements[i]) != null) {
664 <            if (o.equals(x))
685 <                return true;
686 <            i = (i + 1) & mask;
658 >        if (o != null) {
659 >            int mask = elements.length - 1;
660 >            int i = head;
661 >            for (Object x; (x = elements[i]) != null; i = (i + 1) & mask) {
662 >                if (o.equals(x))
663 >                    return true;
664 >            }
665          }
666          return false;
667      }
# Line 737 | Line 715 | public class ArrayDeque<E> extends Abstr
715       * @return an array containing all of the elements in this deque
716       */
717      public Object[] toArray() {
718 <        return copyElements(new Object[size()]);
718 >        final int head = this.head;
719 >        final int tail = this.tail;
720 >        boolean wrap = (tail < head);
721 >        int end = wrap ? tail + elements.length : tail;
722 >        Object[] a = Arrays.copyOfRange(elements, head, end);
723 >        if (wrap)
724 >            System.arraycopy(elements, 0, a, elements.length - head, tail);
725 >        return a;
726      }
727  
728      /**
# Line 778 | Line 763 | public class ArrayDeque<E> extends Abstr
763       */
764      @SuppressWarnings("unchecked")
765      public <T> T[] toArray(T[] a) {
766 <        int size = size();
767 <        if (a.length < size)
768 <            a = (T[])java.lang.reflect.Array.newInstance(
769 <                    a.getClass().getComponentType(), size);
770 <        copyElements(a);
771 <        if (a.length > size)
772 <            a[size] = null;
766 >        final int head = this.head;
767 >        final int tail = this.tail;
768 >        boolean wrap = (tail < head);
769 >        int size = (tail - head) + (wrap ? elements.length : 0);
770 >        int firstLeg = size - (wrap ? tail : 0);
771 >        int len = a.length;
772 >        if (size > len) {
773 >            a = (T[]) Arrays.copyOfRange(elements, head, head + size,
774 >                                         a.getClass());
775 >        } else {
776 >            System.arraycopy(elements, head, a, 0, firstLeg);
777 >            if (size < len)
778 >                a[size] = null;
779 >        }
780 >        if (wrap)
781 >            System.arraycopy(elements, 0, a, firstLeg, tail);
782          return a;
783      }
784  
# Line 811 | Line 805 | public class ArrayDeque<E> extends Abstr
805      /**
806       * Saves this deque to a stream (that is, serializes it).
807       *
808 +     * @param s the stream
809 +     * @throws java.io.IOException if an I/O error occurs
810       * @serialData The current size ({@code int}) of the deque,
811       * followed by all of its elements (each an object reference) in
812       * first-to-last order.
# Line 830 | Line 826 | public class ArrayDeque<E> extends Abstr
826  
827      /**
828       * Reconstitutes this deque from a stream (that is, deserializes it).
829 +     * @param s the stream
830 +     * @throws ClassNotFoundException if the class of a serialized object
831 +     *         could not be found
832 +     * @throws java.io.IOException if an I/O error occurs
833       */
834      private void readObject(java.io.ObjectInputStream s)
835              throws java.io.IOException, ClassNotFoundException {
# 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