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.35 by jsr166, Fri Dec 2 15:47:22 2011 UTC vs.
Revision 1.46 by jsr166, Mon Feb 11 07:42:43 2013 UTC

# Line 1 | Line 1
1   /*
2 < * Written by Josh Bloch of Google Inc. and released to the public domain,
3 < * as explained at http://creativecommons.org/publicdomain/zero/1.0/.
2 > * Written by Doug Lea with assistance from members of JCP JSR-166
3 > * Expert Group and released to the public domain, as explained at
4 > * http://creativecommons.org/publicdomain/zero/1.0/
5   */
6  
7   package java.util;
8 + import java.util.Spliterator;
9 + import java.util.stream.Stream;
10 + import java.util.stream.Streams;
11 + import java.util.function.Consumer;
12  
13   /**
14   * Resizable-array implementation of the {@link Deque} interface.  Array
# Line 14 | Line 19 | package java.util;
19   * {@link Stack} when used as a stack, and faster than {@link LinkedList}
20   * when used as a queue.
21   *
22 < * <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
22 > * <p>Most {@code ArrayDeque} operations run in amortized constant time.
23   * Exceptions include {@link #remove(Object) remove}, {@link
24   * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
25   * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
26   * iterator.remove()}, and the bulk operations, all of which run in linear
27   * time.
28   *
29 < * <p>The iterators returned by this class's <tt>iterator</tt> method are
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 <tt>remove</tt>
31 > * is created, in any way except through the iterator's own {@code remove}
32   * 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
# Line 33 | Line 38 | package java.util;
38   * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
39   * as it is, generally speaking, impossible to make any hard guarantees in the
40   * presence of unsynchronized concurrent modification.  Fail-fast iterators
41 < * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
41 > * throw {@code ConcurrentModificationException} on a best-effort basis.
42   * Therefore, it would be wrong to write a program that depended on this
43   * exception for its correctness: <i>the fail-fast behavior of iterators
44   * should be used only to detect bugs.</i>
# Line 63 | Line 68 | public class ArrayDeque<E> extends Abstr
68       * other.  We also guarantee that all array cells not holding
69       * deque elements are always null.
70       */
71 <    private transient Object[] elements;
71 >    transient Object[] elements; // non-private to simplify nested class access
72  
73      /**
74       * The index of the element at the head of the deque (which is the
75       * element that would be removed by remove() or pop()); or an
76       * arbitrary number equal to tail if the deque is empty.
77       */
78 <    private transient int head;
78 >    transient int head;
79  
80      /**
81       * The index at which the next element would be added to the tail
82       * of the deque (via addLast(E), add(E), or push(E)).
83       */
84 <    private transient int tail;
84 >    transient int tail;
85  
86      /**
87       * The minimum capacity that we'll use for a newly created deque.
# Line 87 | Line 92 | public class ArrayDeque<E> extends Abstr
92      // ******  Array allocation and resizing utilities ******
93  
94      /**
95 <     * Allocate empty array to hold the given number of elements.
95 >     * Allocates empty array to hold the given number of elements.
96       *
97       * @param numElements  the number of elements to hold
98       */
# Line 111 | Line 116 | public class ArrayDeque<E> extends Abstr
116      }
117  
118      /**
119 <     * Double the capacity of this deque.  Call only when full, i.e.,
119 >     * Doubles the capacity of this deque.  Call only when full, i.e.,
120       * when head and tail have wrapped around to become equal.
121       */
122      private void doubleCapacity() {
# Line 219 | Line 224 | public class ArrayDeque<E> extends Abstr
224       * Inserts the specified element at the front of this deque.
225       *
226       * @param e the element to add
227 <     * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
227 >     * @return {@code true} (as specified by {@link Deque#offerFirst})
228       * @throws NullPointerException if the specified element is null
229       */
230      public boolean offerFirst(E e) {
# Line 231 | Line 236 | public class ArrayDeque<E> extends Abstr
236       * Inserts the specified element at the end of this deque.
237       *
238       * @param e the element to add
239 <     * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
239 >     * @return {@code true} (as specified by {@link Deque#offerLast})
240       * @throws NullPointerException if the specified element is null
241       */
242      public boolean offerLast(E e) {
# Line 261 | Line 266 | public class ArrayDeque<E> extends Abstr
266  
267      public E pollFirst() {
268          int h = head;
269 <        @SuppressWarnings("unchecked") E result = (E) elements[h];
269 >        @SuppressWarnings("unchecked")
270 >        E result = (E) elements[h];
271          // Element is null if deque empty
272          if (result == null)
273              return null;
# Line 272 | Line 278 | public class ArrayDeque<E> extends Abstr
278  
279      public E pollLast() {
280          int t = (tail - 1) & (elements.length - 1);
281 <        @SuppressWarnings("unchecked") E result = (E) elements[t];
281 >        @SuppressWarnings("unchecked")
282 >        E result = (E) elements[t];
283          if (result == null)
284              return null;
285          elements[t] = null;
# Line 284 | Line 291 | public class ArrayDeque<E> extends Abstr
291       * @throws NoSuchElementException {@inheritDoc}
292       */
293      public E getFirst() {
294 <        @SuppressWarnings("unchecked") E result = (E) elements[head];
294 >        @SuppressWarnings("unchecked")
295 >        E result = (E) elements[head];
296          if (result == null)
297              throw new NoSuchElementException();
298          return result;
# Line 316 | Line 324 | public class ArrayDeque<E> extends Abstr
324       * Removes the first occurrence of the specified element in this
325       * deque (when traversing the deque from head to tail).
326       * If the deque does not contain the element, it is unchanged.
327 <     * More formally, removes the first element <tt>e</tt> such that
328 <     * <tt>o.equals(e)</tt> (if such an element exists).
329 <     * Returns <tt>true</tt> if this deque contained the specified element
327 >     * More formally, removes the first element {@code e} such that
328 >     * {@code o.equals(e)} (if such an element exists).
329 >     * Returns {@code true} if this deque contained the specified element
330       * (or equivalently, if this deque changed as a result of the call).
331       *
332       * @param o element to be removed from this deque, if present
333 <     * @return <tt>true</tt> if the deque contained the specified element
333 >     * @return {@code true} if the deque contained the specified element
334       */
335      public boolean removeFirstOccurrence(Object o) {
336          if (o == null)
# Line 344 | Line 352 | public class ArrayDeque<E> extends Abstr
352       * Removes the last occurrence of the specified element in this
353       * deque (when traversing the deque from head to tail).
354       * If the deque does not contain the element, it is unchanged.
355 <     * More formally, removes the last element <tt>e</tt> such that
356 <     * <tt>o.equals(e)</tt> (if such an element exists).
357 <     * Returns <tt>true</tt> if this deque contained the specified element
355 >     * More formally, removes the last element {@code e} such that
356 >     * {@code o.equals(e)} (if such an element exists).
357 >     * Returns {@code true} if this deque contained the specified element
358       * (or equivalently, if this deque changed as a result of the call).
359       *
360       * @param o element to be removed from this deque, if present
361 <     * @return <tt>true</tt> if the deque contained the specified element
361 >     * @return {@code true} if the deque contained the specified element
362       */
363      public boolean removeLastOccurrence(Object o) {
364          if (o == null)
# Line 376 | Line 384 | public class ArrayDeque<E> extends Abstr
384       * <p>This method is equivalent to {@link #addLast}.
385       *
386       * @param e the element to add
387 <     * @return <tt>true</tt> (as specified by {@link Collection#add})
387 >     * @return {@code true} (as specified by {@link Collection#add})
388       * @throws NullPointerException if the specified element is null
389       */
390      public boolean add(E e) {
# Line 390 | Line 398 | public class ArrayDeque<E> extends Abstr
398       * <p>This method is equivalent to {@link #offerLast}.
399       *
400       * @param e the element to add
401 <     * @return <tt>true</tt> (as specified by {@link Queue#offer})
401 >     * @return {@code true} (as specified by {@link Queue#offer})
402       * @throws NullPointerException if the specified element is null
403       */
404      public boolean offer(E e) {
# Line 415 | Line 423 | public class ArrayDeque<E> extends Abstr
423      /**
424       * Retrieves and removes the head of the queue represented by this deque
425       * (in other words, the first element of this deque), or returns
426 <     * <tt>null</tt> if this deque is empty.
426 >     * {@code null} if this deque is empty.
427       *
428       * <p>This method is equivalent to {@link #pollFirst}.
429       *
430       * @return the head of the queue represented by this deque, or
431 <     *         <tt>null</tt> if this deque is empty
431 >     *         {@code null} if this deque is empty
432       */
433      public E poll() {
434          return pollFirst();
# Line 442 | Line 450 | public class ArrayDeque<E> extends Abstr
450  
451      /**
452       * Retrieves, but does not remove, the head of the queue represented by
453 <     * this deque, or returns <tt>null</tt> if this deque is empty.
453 >     * this deque, or returns {@code null} if this deque is empty.
454       *
455       * <p>This method is equivalent to {@link #peekFirst}.
456       *
457       * @return the head of the queue represented by this deque, or
458 <     *         <tt>null</tt> if this deque is empty
458 >     *         {@code null} if this deque is empty
459       */
460      public E peek() {
461          return peekFirst();
# Line 551 | Line 559 | public class ArrayDeque<E> extends Abstr
559      }
560  
561      /**
562 <     * Returns <tt>true</tt> if this deque contains no elements.
562 >     * Returns {@code true} if this deque contains no elements.
563       *
564 <     * @return <tt>true</tt> if this deque contains no elements
564 >     * @return {@code true} if this deque contains no elements
565       */
566      public boolean isEmpty() {
567          return head == tail;
# Line 600 | Line 608 | public class ArrayDeque<E> extends Abstr
608          public E next() {
609              if (cursor == fence)
610                  throw new NoSuchElementException();
611 <            @SuppressWarnings("unchecked") E result = (E) elements[cursor];
611 >            @SuppressWarnings("unchecked")
612 >            E result = (E) elements[cursor];
613              // This check doesn't catch all possible comodifications,
614              // but does catch the ones that corrupt traversal
615              if (tail != fence || result == null)
# Line 639 | Line 648 | public class ArrayDeque<E> extends Abstr
648              if (cursor == fence)
649                  throw new NoSuchElementException();
650              cursor = (cursor - 1) & (elements.length - 1);
651 <            @SuppressWarnings("unchecked") E result = (E) elements[cursor];
651 >            @SuppressWarnings("unchecked")
652 >            E result = (E) elements[cursor];
653              if (head != fence || result == null)
654                  throw new ConcurrentModificationException();
655              lastRet = cursor;
# Line 658 | Line 668 | public class ArrayDeque<E> extends Abstr
668      }
669  
670      /**
671 <     * Returns <tt>true</tt> if this deque contains the specified element.
672 <     * More formally, returns <tt>true</tt> if and only if this deque contains
673 <     * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
671 >     * Returns {@code true} if this deque contains the specified element.
672 >     * More formally, returns {@code true} if and only if this deque contains
673 >     * at least one element {@code e} such that {@code o.equals(e)}.
674       *
675       * @param o object to be checked for containment in this deque
676 <     * @return <tt>true</tt> if this deque contains the specified element
676 >     * @return {@code true} if this deque contains the specified element
677       */
678      public boolean contains(Object o) {
679          if (o == null)
# Line 682 | Line 692 | public class ArrayDeque<E> extends Abstr
692      /**
693       * Removes a single instance of the specified element from this deque.
694       * If the deque does not contain the element, it is unchanged.
695 <     * More formally, removes the first element <tt>e</tt> such that
696 <     * <tt>o.equals(e)</tt> (if such an element exists).
697 <     * Returns <tt>true</tt> if this deque contained the specified element
695 >     * More formally, removes the first element {@code e} such that
696 >     * {@code o.equals(e)} (if such an element exists).
697 >     * Returns {@code true} if this deque contained the specified element
698       * (or equivalently, if this deque changed as a result of the call).
699       *
700 <     * <p>This method is equivalent to {@link #removeFirstOccurrence}.
700 >     * <p>This method is equivalent to {@link #removeFirstOccurrence(Object)}.
701       *
702       * @param o element to be removed from this deque, if present
703 <     * @return <tt>true</tt> if this deque contained the specified element
703 >     * @return {@code true} if this deque contained the specified element
704       */
705      public boolean remove(Object o) {
706          return removeFirstOccurrence(o);
# Line 742 | Line 752 | public class ArrayDeque<E> extends Abstr
752       * <p>If this deque fits in the specified array with room to spare
753       * (i.e., the array has more elements than this deque), the element in
754       * the array immediately following the end of the deque is set to
755 <     * <tt>null</tt>.
755 >     * {@code null}.
756       *
757       * <p>Like the {@link #toArray()} method, this method acts as bridge between
758       * array-based and collection-based APIs.  Further, this method allows
759       * precise control over the runtime type of the output array, and may,
760       * under certain circumstances, be used to save allocation costs.
761       *
762 <     * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
762 >     * <p>Suppose {@code x} is a deque known to contain only strings.
763       * The following code can be used to dump the deque into a newly
764 <     * allocated array of <tt>String</tt>:
764 >     * allocated array of {@code String}:
765       *
766       *  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
767       *
768 <     * Note that <tt>toArray(new Object[0])</tt> is identical in function to
769 <     * <tt>toArray()</tt>.
768 >     * Note that {@code toArray(new Object[0])} is identical in function to
769 >     * {@code toArray()}.
770       *
771       * @param a the array into which the elements of the deque are to
772       *          be stored, if it is big enough; otherwise, a new array of the
# Line 792 | Line 802 | public class ArrayDeque<E> extends Abstr
802              ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
803              result.elements = Arrays.copyOf(elements, elements.length);
804              return result;
795 –
805          } catch (CloneNotSupportedException e) {
806              throw new AssertionError();
807          }
808      }
809  
801 –    /**
802 –     * Appease the serialization gods.
803 –     */
810      private static final long serialVersionUID = 2340985798034038923L;
811  
812      /**
813 <     * Serialize this deque.
813 >     * Saves this deque to a stream (that is, serializes it).
814       *
815 <     * @serialData The current size (<tt>int</tt>) of the deque,
815 >     * @serialData The current size ({@code int}) of the deque,
816       * followed by all of its elements (each an object reference) in
817       * first-to-last order.
818       */
# Line 824 | Line 830 | public class ArrayDeque<E> extends Abstr
830      }
831  
832      /**
833 <     * Deserialize this deque.
833 >     * Reconstitutes this deque from a stream (that is, deserializes it).
834       */
835      private void readObject(java.io.ObjectInputStream s)
836              throws java.io.IOException, ClassNotFoundException {
# Line 840 | Line 846 | public class ArrayDeque<E> extends Abstr
846          for (int i = 0; i < size; i++)
847              elements[i] = s.readObject();
848      }
849 +
850 +    public Stream<E> stream() {
851 +        int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
852 +        return Streams.stream
853 +            (() -> new DeqSpliterator<E>(this, head, tail), flags);
854 +    }
855 +    public Stream<E> parallelStream() {
856 +        int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
857 +        return Streams.parallelStream
858 +            (() -> new DeqSpliterator<E>(this, head, tail), flags);
859 +    }
860 +
861 +
862 +    static final class DeqSpliterator<E> implements Spliterator<E> {
863 +        private final ArrayDeque<E> deq;
864 +        private final int fence;  // initially tail
865 +        private int index;        // current index, modified on traverse/split
866 +
867 +        /** Create new spliterator covering the given array and range */
868 +        DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
869 +            this.deq = deq; this.index = origin; this.fence = fence;
870 +        }
871 +
872 +        public DeqSpliterator<E> trySplit() {
873 +            int n = deq.elements.length;
874 +            int h = index, t = fence;
875 +            if (h != t && ((h + 1) & (n - 1)) != t) {
876 +                if (h > t)
877 +                    t += n;
878 +                int m = ((h + t) >>> 1) & (n - 1);
879 +                return new DeqSpliterator<E>(deq, h, index = m);
880 +            }
881 +            return null;
882 +        }
883 +
884 +        public void forEach(Consumer<? super E> block) {
885 +            if (block == null)
886 +                throw new NullPointerException();
887 +            Object[] a = deq.elements;
888 +            int m = a.length - 1, f = fence, i = index;
889 +            index = f;
890 +            while (i != f) {
891 +                @SuppressWarnings("unchecked") E e = (E)a[i];
892 +                i = (i + 1) & m;
893 +                if (e == null)
894 +                    throw new ConcurrentModificationException();
895 +                block.accept(e);
896 +            }
897 +        }
898 +
899 +        public boolean tryAdvance(Consumer<? super E> block) {
900 +            if (block == null)
901 +                throw new NullPointerException();
902 +            Object[] a = deq.elements;
903 +            int m = a.length - 1, i = index;
904 +            if (i != fence) {
905 +                @SuppressWarnings("unchecked") E e = (E)a[i];
906 +                index = (i + 1) & m;
907 +                if (e == null)
908 +                    throw new ConcurrentModificationException();
909 +                block.accept(e);
910 +                return true;
911 +            }
912 +            return false;
913 +        }
914 +
915 +        // Other spliterator methods
916 +        public long estimateSize() {
917 +            int n = fence - index;
918 +            if (n < 0)
919 +                n += deq.elements.length;
920 +            return (long)n;
921 +        }
922 +        public boolean hasExactSize() { return true; }
923 +        public boolean hasExactSplits() { return true; }
924 +    }
925 +
926   }

Diff Legend

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