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.36 by jsr166, Fri Dec 2 15:51:56 2011 UTC vs.
Revision 1.43 by jsr166, Wed Jan 16 21:25:33 2013 UTC

# Line 1 | Line 1
1   /*
2 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 + *
4 + * This code is free software; you can redistribute it and/or modify it
5 + * under the terms of the GNU General Public License version 2 only, as
6 + * published by the Free Software Foundation.  Oracle designates this
7 + * particular file as subject to the "Classpath" exception as provided
8 + * by Oracle in the LICENSE file that accompanied this code.
9 + *
10 + * This code is distributed in the hope that it will be useful, but WITHOUT
11 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 + * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
13 + * version 2 for more details (a copy is included in the LICENSE file that
14 + * accompanied this code).
15 + *
16 + * You should have received a copy of the GNU General Public License version
17 + * 2 along with this work; if not, write to the Free Software Foundation,
18 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 + *
20 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 + * or visit www.oracle.com if you need additional information or have any
22 + * questions.
23 + */
24 +
25 + /*
26 + * This file is available under and governed by the GNU General Public
27 + * License version 2 only, as published by the Free Software Foundation.
28 + * However, the following notice accompanied the original version of this
29 + * file:
30 + *
31   * Written by Josh Bloch of Google Inc. and released to the public domain,
32   * as explained at http://creativecommons.org/publicdomain/zero/1.0/.
33   */
34  
35   package java.util;
36 + import java.util.Spliterator;
37 + import java.util.stream.Stream;
38 + import java.util.stream.Streams;
39 + import java.util.function.Block;
40  
41   /**
42   * Resizable-array implementation of the {@link Deque} interface.  Array
# Line 14 | Line 47 | package java.util;
47   * {@link Stack} when used as a stack, and faster than {@link LinkedList}
48   * when used as a queue.
49   *
50 < * <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
50 > * <p>Most {@code ArrayDeque} operations run in amortized constant time.
51   * Exceptions include {@link #remove(Object) remove}, {@link
52   * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
53   * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
54   * iterator.remove()}, and the bulk operations, all of which run in linear
55   * time.
56   *
57 < * <p>The iterators returned by this class's <tt>iterator</tt> method are
57 > * <p>The iterators returned by this class's {@code iterator} method are
58   * <i>fail-fast</i>: If the deque is modified at any time after the iterator
59 < * is created, in any way except through the iterator's own <tt>remove</tt>
59 > * is created, in any way except through the iterator's own {@code remove}
60   * method, the iterator will generally throw a {@link
61   * ConcurrentModificationException}.  Thus, in the face of concurrent
62   * modification, the iterator fails quickly and cleanly, rather than risking
# Line 33 | Line 66 | package java.util;
66   * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
67   * as it is, generally speaking, impossible to make any hard guarantees in the
68   * presence of unsynchronized concurrent modification.  Fail-fast iterators
69 < * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
69 > * throw {@code ConcurrentModificationException} on a best-effort basis.
70   * Therefore, it would be wrong to write a program that depended on this
71   * exception for its correctness: <i>the fail-fast behavior of iterators
72   * should be used only to detect bugs.</i>
# Line 63 | Line 96 | public class ArrayDeque<E> extends Abstr
96       * other.  We also guarantee that all array cells not holding
97       * deque elements are always null.
98       */
99 <    private transient Object[] elements;
99 >    transient Object[] elements; // non-private to simplify nested class access
100  
101      /**
102       * The index of the element at the head of the deque (which is the
103       * element that would be removed by remove() or pop()); or an
104       * arbitrary number equal to tail if the deque is empty.
105       */
106 <    private transient int head;
106 >    transient int head;
107  
108      /**
109       * The index at which the next element would be added to the tail
110       * of the deque (via addLast(E), add(E), or push(E)).
111       */
112 <    private transient int tail;
112 >    transient int tail;
113  
114      /**
115       * The minimum capacity that we'll use for a newly created deque.
# Line 87 | Line 120 | public class ArrayDeque<E> extends Abstr
120      // ******  Array allocation and resizing utilities ******
121  
122      /**
123 <     * Allocate empty array to hold the given number of elements.
123 >     * Allocates empty array to hold the given number of elements.
124       *
125       * @param numElements  the number of elements to hold
126       */
# Line 111 | Line 144 | public class ArrayDeque<E> extends Abstr
144      }
145  
146      /**
147 <     * Double the capacity of this deque.  Call only when full, i.e.,
147 >     * Doubles the capacity of this deque.  Call only when full, i.e.,
148       * when head and tail have wrapped around to become equal.
149       */
150      private void doubleCapacity() {
# Line 219 | Line 252 | public class ArrayDeque<E> extends Abstr
252       * Inserts the specified element at the front of this deque.
253       *
254       * @param e the element to add
255 <     * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
255 >     * @return {@code true} (as specified by {@link Deque#offerFirst})
256       * @throws NullPointerException if the specified element is null
257       */
258      public boolean offerFirst(E e) {
# Line 231 | Line 264 | public class ArrayDeque<E> extends Abstr
264       * Inserts the specified element at the end of this deque.
265       *
266       * @param e the element to add
267 <     * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
267 >     * @return {@code true} (as specified by {@link Deque#offerLast})
268       * @throws NullPointerException if the specified element is null
269       */
270      public boolean offerLast(E e) {
# Line 261 | Line 294 | public class ArrayDeque<E> extends Abstr
294  
295      public E pollFirst() {
296          int h = head;
297 <        @SuppressWarnings("unchecked") E result = (E) elements[h];
297 >        @SuppressWarnings("unchecked")
298 >        E result = (E) elements[h];
299          // Element is null if deque empty
300          if (result == null)
301              return null;
# Line 272 | Line 306 | public class ArrayDeque<E> extends Abstr
306  
307      public E pollLast() {
308          int t = (tail - 1) & (elements.length - 1);
309 <        @SuppressWarnings("unchecked") E result = (E) elements[t];
309 >        @SuppressWarnings("unchecked")
310 >        E result = (E) elements[t];
311          if (result == null)
312              return null;
313          elements[t] = null;
# Line 284 | Line 319 | public class ArrayDeque<E> extends Abstr
319       * @throws NoSuchElementException {@inheritDoc}
320       */
321      public E getFirst() {
322 <        @SuppressWarnings("unchecked") E result = (E) elements[head];
322 >        @SuppressWarnings("unchecked")
323 >        E result = (E) elements[head];
324          if (result == null)
325              throw new NoSuchElementException();
326          return result;
# Line 316 | Line 352 | public class ArrayDeque<E> extends Abstr
352       * Removes the first 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 first 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 first 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 removeFirstOccurrence(Object o) {
364          if (o == null)
# Line 344 | Line 380 | public class ArrayDeque<E> extends Abstr
380       * Removes the last occurrence of the specified element in this
381       * deque (when traversing the deque from head to tail).
382       * If the deque does not contain the element, it is unchanged.
383 <     * More formally, removes the last element <tt>e</tt> such that
384 <     * <tt>o.equals(e)</tt> (if such an element exists).
385 <     * Returns <tt>true</tt> if this deque contained the specified element
383 >     * More formally, removes the last element {@code e} such that
384 >     * {@code o.equals(e)} (if such an element exists).
385 >     * Returns {@code true} if this deque contained the specified element
386       * (or equivalently, if this deque changed as a result of the call).
387       *
388       * @param o element to be removed from this deque, if present
389 <     * @return <tt>true</tt> if the deque contained the specified element
389 >     * @return {@code true} if the deque contained the specified element
390       */
391      public boolean removeLastOccurrence(Object o) {
392          if (o == null)
# Line 376 | Line 412 | public class ArrayDeque<E> extends Abstr
412       * <p>This method is equivalent to {@link #addLast}.
413       *
414       * @param e the element to add
415 <     * @return <tt>true</tt> (as specified by {@link Collection#add})
415 >     * @return {@code true} (as specified by {@link Collection#add})
416       * @throws NullPointerException if the specified element is null
417       */
418      public boolean add(E e) {
# Line 390 | Line 426 | public class ArrayDeque<E> extends Abstr
426       * <p>This method is equivalent to {@link #offerLast}.
427       *
428       * @param e the element to add
429 <     * @return <tt>true</tt> (as specified by {@link Queue#offer})
429 >     * @return {@code true} (as specified by {@link Queue#offer})
430       * @throws NullPointerException if the specified element is null
431       */
432      public boolean offer(E e) {
# Line 415 | Line 451 | public class ArrayDeque<E> extends Abstr
451      /**
452       * Retrieves and removes the head of the queue represented by this deque
453       * (in other words, the first element of this deque), or returns
454 <     * <tt>null</tt> if this deque is empty.
454 >     * {@code null} if this deque is empty.
455       *
456       * <p>This method is equivalent to {@link #pollFirst}.
457       *
458       * @return the head of the queue represented by this deque, or
459 <     *         <tt>null</tt> if this deque is empty
459 >     *         {@code null} if this deque is empty
460       */
461      public E poll() {
462          return pollFirst();
# Line 442 | Line 478 | public class ArrayDeque<E> extends Abstr
478  
479      /**
480       * Retrieves, but does not remove, the head of the queue represented by
481 <     * this deque, or returns <tt>null</tt> if this deque is empty.
481 >     * this deque, or returns {@code null} if this deque is empty.
482       *
483       * <p>This method is equivalent to {@link #peekFirst}.
484       *
485       * @return the head of the queue represented by this deque, or
486 <     *         <tt>null</tt> if this deque is empty
486 >     *         {@code null} if this deque is empty
487       */
488      public E peek() {
489          return peekFirst();
# Line 551 | Line 587 | public class ArrayDeque<E> extends Abstr
587      }
588  
589      /**
590 <     * Returns <tt>true</tt> if this deque contains no elements.
590 >     * Returns {@code true} if this deque contains no elements.
591       *
592 <     * @return <tt>true</tt> if this deque contains no elements
592 >     * @return {@code true} if this deque contains no elements
593       */
594      public boolean isEmpty() {
595          return head == tail;
# Line 600 | Line 636 | public class ArrayDeque<E> extends Abstr
636          public E next() {
637              if (cursor == fence)
638                  throw new NoSuchElementException();
639 <            @SuppressWarnings("unchecked") E result = (E) elements[cursor];
639 >            @SuppressWarnings("unchecked")
640 >            E result = (E) elements[cursor];
641              // This check doesn't catch all possible comodifications,
642              // but does catch the ones that corrupt traversal
643              if (tail != fence || result == null)
# Line 639 | Line 676 | public class ArrayDeque<E> extends Abstr
676              if (cursor == fence)
677                  throw new NoSuchElementException();
678              cursor = (cursor - 1) & (elements.length - 1);
679 <            @SuppressWarnings("unchecked") E result = (E) elements[cursor];
679 >            @SuppressWarnings("unchecked")
680 >            E result = (E) elements[cursor];
681              if (head != fence || result == null)
682                  throw new ConcurrentModificationException();
683              lastRet = cursor;
# Line 658 | Line 696 | public class ArrayDeque<E> extends Abstr
696      }
697  
698      /**
699 <     * Returns <tt>true</tt> if this deque contains the specified element.
700 <     * More formally, returns <tt>true</tt> if and only if this deque contains
701 <     * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
699 >     * Returns {@code true} if this deque contains the specified element.
700 >     * More formally, returns {@code true} if and only if this deque contains
701 >     * at least one element {@code e} such that {@code o.equals(e)}.
702       *
703       * @param o object to be checked for containment in this deque
704 <     * @return <tt>true</tt> if this deque contains the specified element
704 >     * @return {@code true} if this deque contains the specified element
705       */
706      public boolean contains(Object o) {
707          if (o == null)
# Line 682 | Line 720 | public class ArrayDeque<E> extends Abstr
720      /**
721       * Removes a single instance of the specified element from this deque.
722       * If the deque does not contain the element, it is unchanged.
723 <     * More formally, removes the first element <tt>e</tt> such that
724 <     * <tt>o.equals(e)</tt> (if such an element exists).
725 <     * Returns <tt>true</tt> if this deque contained the specified element
723 >     * More formally, removes the first element {@code e} such that
724 >     * {@code o.equals(e)} (if such an element exists).
725 >     * Returns {@code true} if this deque contained the specified element
726       * (or equivalently, if this deque changed as a result of the call).
727       *
728       * <p>This method is equivalent to {@link #removeFirstOccurrence}.
729       *
730       * @param o element to be removed from this deque, if present
731 <     * @return <tt>true</tt> if this deque contained the specified element
731 >     * @return {@code true} if this deque contained the specified element
732       */
733      public boolean remove(Object o) {
734          return removeFirstOccurrence(o);
# Line 742 | Line 780 | public class ArrayDeque<E> extends Abstr
780       * <p>If this deque fits in the specified array with room to spare
781       * (i.e., the array has more elements than this deque), the element in
782       * the array immediately following the end of the deque is set to
783 <     * <tt>null</tt>.
783 >     * {@code null}.
784       *
785       * <p>Like the {@link #toArray()} method, this method acts as bridge between
786       * array-based and collection-based APIs.  Further, this method allows
787       * precise control over the runtime type of the output array, and may,
788       * under certain circumstances, be used to save allocation costs.
789       *
790 <     * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
790 >     * <p>Suppose {@code x} is a deque known to contain only strings.
791       * The following code can be used to dump the deque into a newly
792 <     * allocated array of <tt>String</tt>:
792 >     * allocated array of {@code String}:
793       *
794       *  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
795       *
796 <     * Note that <tt>toArray(new Object[0])</tt> is identical in function to
797 <     * <tt>toArray()</tt>.
796 >     * Note that {@code toArray(new Object[0])} is identical in function to
797 >     * {@code toArray()}.
798       *
799       * @param a the array into which the elements of the deque are to
800       *          be stored, if it is big enough; otherwise, a new array of the
# Line 797 | Line 835 | public class ArrayDeque<E> extends Abstr
835          }
836      }
837  
800    /**
801     * Appease the serialization gods.
802     */
838      private static final long serialVersionUID = 2340985798034038923L;
839  
840      /**
841 <     * Serialize this deque.
841 >     * Saves this deque to a stream (that is, serializes it).
842       *
843 <     * @serialData The current size (<tt>int</tt>) of the deque,
843 >     * @serialData The current size ({@code int}) of the deque,
844       * followed by all of its elements (each an object reference) in
845       * first-to-last order.
846       */
# Line 823 | Line 858 | public class ArrayDeque<E> extends Abstr
858      }
859  
860      /**
861 <     * Deserialize this deque.
861 >     * Reconstitutes this deque from a stream (that is, deserializes it).
862       */
863      private void readObject(java.io.ObjectInputStream s)
864              throws java.io.IOException, ClassNotFoundException {
# Line 839 | Line 874 | public class ArrayDeque<E> extends Abstr
874          for (int i = 0; i < size; i++)
875              elements[i] = s.readObject();
876      }
877 +
878 +    public Stream<E> stream() {
879 +        int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
880 +        return Streams.stream
881 +            (() -> new DeqSpliterator<E>(this, head, tail), flags);
882 +    }
883 +    public Stream<E> parallelStream() {
884 +        int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
885 +        return Streams.parallelStream
886 +            (() -> new DeqSpliterator<E>(this, head, tail), flags);
887 +    }
888 +
889 +
890 +    static final class DeqSpliterator<E> implements Spliterator<E>, Iterator<E> {
891 +        private final ArrayDeque<E> deq;
892 +        private final Object[] array;
893 +        private final int fence;  // initially tail
894 +        private int index;        // current index, modified on traverse/split
895 +
896 +        /** Create new spliterator covering the given array and range */
897 +        DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
898 +            this.deq = deq; this.array = deq.elements;
899 +            this.index = origin; this.fence = fence;
900 +        }
901 +
902 +        public DeqSpliterator<E> trySplit() {
903 +            int n = array.length;
904 +            int h = index, t = fence;
905 +            if (h != t && ((h + 1) & (n - 1)) != t) {
906 +                if (h > t)
907 +                    t += n;
908 +                int m = ((h + t) >>> 1) & (n - 1);
909 +                return new DeqSpliterator<E>(deq, h, index = m);
910 +            }
911 +            return null;
912 +        }
913 +
914 +        @SuppressWarnings("unchecked")
915 +        public void forEach(Block<? super E> block) {
916 +            if (block == null)
917 +                throw new NullPointerException();
918 +            Object[] a = array;
919 +            if (a != deq.elements)
920 +                throw new ConcurrentModificationException();
921 +            int m = a.length - 1, f = fence, i = index;
922 +            index = f;
923 +            while (i != f) {
924 +                Object e = a[i];
925 +                if (e == null)
926 +                    throw new ConcurrentModificationException();
927 +                block.accept((E)e);
928 +                i = (i + 1) & m;
929 +            }
930 +        }
931 +
932 +        @SuppressWarnings("unchecked")
933 +        public boolean tryAdvance(Block<? super E> block) {
934 +            if (block == null)
935 +                throw new NullPointerException();
936 +            Object[] a = array;
937 +            if (a != deq.elements)
938 +                throw new ConcurrentModificationException();
939 +            int m = a.length - 1, i = index;
940 +            if (i != fence) {
941 +                Object e = a[i];
942 +                if (e == null)
943 +                    throw new ConcurrentModificationException();
944 +                block.accept((E)e);
945 +                index = (i + 1) & m;
946 +                return true;
947 +            }
948 +            return false;
949 +        }
950 +
951 +        // Iterator support
952 +        public Iterator<E> iterator() {
953 +            return this;
954 +        }
955 +
956 +        public boolean hasNext() {
957 +            return index >= 0 && index != fence;
958 +        }
959 +
960 +        @SuppressWarnings("unchecked")
961 +            public E next() {
962 +            if (index < 0 || index == fence)
963 +                throw new NoSuchElementException();
964 +            Object[] a = array;
965 +            if (a != deq.elements)
966 +                throw new ConcurrentModificationException();
967 +            Object e = a[index];
968 +            if (e == null)
969 +                throw new ConcurrentModificationException();
970 +            index = (index + 1) & (a.length - 1);
971 +            return (E) e;
972 +        }
973 +
974 +        public void remove() { throw new UnsupportedOperationException(); }
975 +
976 +        // Other spliterator methods
977 +        public long estimateSize() {
978 +            int n = fence - index;
979 +            if (n < 0)
980 +                n += array.length;
981 +            return (long)n;
982 +        }
983 +        public boolean hasExactSize() { return true; }
984 +        public boolean hasExactSplits() { return true; }
985 +    }
986 +
987   }

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines