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

Comparing jsr166/src/jsr166x/ArrayDeque.java (file contents):
Revision 1.1 by dl, Sun Dec 5 21:15:30 2004 UTC vs.
Revision 1.10 by jsr166, Sat Dec 29 23:55:19 2012 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/licenses/publicdomain.
3 > * as explained at http://creativecommons.org/publicdomain/zero/1.0/.
4   */
5  
6   package jsr166x;    // XXX This belongs in java.util!!! XXX
# Line 13 | Line 13 | import java.io.*;
13   * usage.  They are not thread-safe; in the absence of external
14   * synchronization, they do not support concurrent access by multiple threads.
15   * Null elements are prohibited.  This class is likely to be faster than
16 < * {@link Stack} when used as as a stack, and faster than {@link LinkedList}
16 > * {@link Stack} when used as a stack, and faster than {@link LinkedList}
17   * when used as a queue.
18   *
19   * <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
# Line 34 | Line 34 | import java.io.*;
34   * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
35   * as it is, generally speaking, impossible to make any hard guarantees in the
36   * presence of unsynchronized concurrent modification.  Fail-fast iterators
37 < * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
37 > * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
38   * Therefore, it would be wrong to write a program that depended on this
39   * exception for its correctness: <i>the fail-fast behavior of iterators
40   * should be used only to detect bugs.</i>
# Line 86 | Line 86 | public class ArrayDeque<E> extends Abstr
86      // ******  Array allocation and resizing utilities ******
87  
88      /**
89 <     * Allocate empty array to hold the given number of elements.
89 >     * Allocates empty array to hold the given number of elements.
90       *
91 <     * @param numElements  the number of elements to hold.
91 >     * @param numElements  the number of elements to hold
92       */
93 <    private void allocateElements(int numElements) {  
93 >    private void allocateElements(int numElements) {
94          int initialCapacity = MIN_INITIAL_CAPACITY;
95          // Find the best power of two to hold elements.
96          // Tests "<=" because arrays aren't kept full.
# Line 110 | Line 110 | public class ArrayDeque<E> extends Abstr
110      }
111  
112      /**
113 <     * Double the capacity of this deque.  Call only when full, i.e.,
113 >     * Doubles the capacity of this deque.  Call only when full, i.e.,
114       * when head and tail have wrapped around to become equal.
115       */
116      private void doubleCapacity() {
117 <        assert head == tail;
117 >        assert head == tail;
118          int p = head;
119          int n = elements.length;
120          int r = n - p; // number of elements to the right of p
# Line 130 | Line 130 | public class ArrayDeque<E> extends Abstr
130      }
131  
132      /**
133 <     * Copy the elements from our element array into the specified array,
133 >     * Copies the elements from our element array into the specified array,
134       * in order (from first to last element in the deque).  It is assumed
135       * that the array is large enough to hold all elements in the deque.
136       *
# Line 194 | Line 194 | public class ArrayDeque<E> extends Abstr
194          if (e == null)
195              throw new NullPointerException();
196          elements[head = (head - 1) & (elements.length - 1)] = e;
197 <        if (head == tail)
197 >        if (head == tail)
198              doubleCapacity();
199      }
200  
# Line 243 | Line 243 | public class ArrayDeque<E> extends Abstr
243          E result = elements[t];
244          if (result == null)
245              return null;
246 <        elements[t] = null;
246 >        elements[t] = null;
247          tail = t;
248          return result;
249      }
# Line 332 | Line 332 | public class ArrayDeque<E> extends Abstr
332       * @return the first element of this deque
333       * @throws NoSuchElementException if this deque is empty
334       */
335 <    public E firstElement() {
335 >    public E getFirst() {
336          E x = elements[head];
337          if (x == null)
338              throw new NoSuchElementException();
# Line 347 | Line 347 | public class ArrayDeque<E> extends Abstr
347       * @return the last element of this deque
348       * @throws NoSuchElementException if this deque is empty
349       */
350 <    public E lastElement() {
350 >    public E getLast() {
351          E x = elements[(tail - 1) & (elements.length - 1)];
352          if (x == null)
353              throw new NoSuchElementException();
# Line 478 | Line 478 | public class ArrayDeque<E> extends Abstr
478       * this deque.  This method differs from the <tt>peek</tt> method only in
479       * that it throws an exception if this deque is empty.
480       *
481 <     * <p>This method is equivalent to {@link #firstElement}
481 >     * <p>This method is equivalent to {@link #getFirst}
482       *
483       * @return the head of the queue represented by this deque
484       * @throws NoSuchElementException if this deque is empty
485       */
486      public E element() {
487 <        return firstElement();
487 >        return getFirst();
488      }
489  
490      // *** Stack methods ***
# Line 504 | Line 504 | public class ArrayDeque<E> extends Abstr
504  
505      /**
506       * Pops an element from the stack represented by this deque.  In other
507 <     * words, removes and returns the the first element of this deque.
507 >     * words, removes and returns the first element of this deque.
508       *
509       * <p>This method is equivalent to {@link #removeFirst()}.
510       *
# Line 517 | Line 517 | public class ArrayDeque<E> extends Abstr
517      }
518  
519      /**
520 <     * Remove the element at the specified position in the elements array,
520 >     * Removes the element at the specified position in the elements array,
521       * adjusting head, tail, and size as necessary.  This can result in
522       * motion of elements backwards or forwards in the array.
523       *
524       * <p>This method is called delete rather than remove to emphasize the
525       * that that its semantics differ from those of List.remove(int).
526 <     *
526 >     *
527       * @return true if elements moved backwards
528       */
529      private boolean delete(int i) {
# Line 555 | Line 555 | public class ArrayDeque<E> extends Abstr
555      }
556  
557      /**
558 <     * Returns <tt>true</tt> if this collection contains no elements.<p>
558 >     * Returns <tt>true</tt> if this collection contains no elements.
559       *
560 <     * @return <tt>true</tt> if this collection contains no elements.
560 >     * @return <tt>true</tt> if this collection contains no elements
561       */
562      public boolean isEmpty() {
563          return head == tail;
# Line 568 | Line 568 | public class ArrayDeque<E> extends Abstr
568       * will be ordered from first (head) to last (tail).  This is the same
569       * order that elements would be dequeued (via successive calls to
570       * {@link #remove} or popped (via successive calls to {@link #pop}).
571 <     *
571 >     *
572       * @return an <tt>Iterator</tt> over the elements in this deque
573       */
574      public Iterator<E> iterator() {
# Line 667 | Line 667 | public class ArrayDeque<E> extends Abstr
667              do {
668                  elements[i] = null;
669                  i = (i + 1) & mask;
670 <            } while(i != t);
670 >            } while (i != t);
671          }
672      }
673  
# Line 676 | Line 676 | public class ArrayDeque<E> extends Abstr
676       * in the correct order.
677       *
678       * @return an array containing all of the elements in this list
679 <     *         in the correct order
679 >     *         in the correct order
680       */
681      public Object[] toArray() {
682 <        return copyElements(new Object[size()]);
682 >        return copyElements(new Object[size()]);
683      }
684  
685      /**
# Line 694 | Line 694 | public class ArrayDeque<E> extends Abstr
694       * immediately following the end of the collection is set to <tt>null</tt>.
695       *
696       * @param a the array into which the elements of the deque are to
697 <     *          be stored, if it is big enough; otherwise, a new array of the
698 <     *          same runtime type is allocated for this purpose
697 >     *          be stored, if it is big enough; otherwise, a new array of the
698 >     *          same runtime type is allocated for this purpose
699       * @return an array containing the elements of the deque
700       * @throws ArrayStoreException if the runtime type of a is not a supertype
701       *         of the runtime type of every element in this deque
# Line 705 | Line 705 | public class ArrayDeque<E> extends Abstr
705          if (a.length < size)
706              a = (T[])java.lang.reflect.Array.newInstance(
707                      a.getClass().getComponentType(), size);
708 <        copyElements(a);
708 >        copyElements(a);
709          if (a.length > size)
710              a[size] = null;
711          return a;
# Line 719 | Line 719 | public class ArrayDeque<E> extends Abstr
719       * @return a copy of this deque
720       */
721      public ArrayDeque<E> clone() {
722 <        try {
722 >        try {
723              ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
724              // These two lines are currently faster than cloning the array:
725              result.elements = (E[]) new Object[elements.length];
726              System.arraycopy(elements, 0, result.elements, 0, elements.length);
727              return result;
728  
729 <        } catch (CloneNotSupportedException e) {
729 >        } catch (CloneNotSupportedException e) {
730              throw new AssertionError();
731          }
732      }
# Line 737 | Line 737 | public class ArrayDeque<E> extends Abstr
737      private static final long serialVersionUID = 2340985798034038923L;
738  
739      /**
740 <     * Serialize this deque.
740 >     * Serializes this deque.
741       *
742       * @serialData The current size (<tt>int</tt>) of the deque,
743       * followed by all of its elements (each an object reference) in
# Line 760 | Line 760 | public class ArrayDeque<E> extends Abstr
760      }
761  
762      /**
763 <     * Deserialize this deque.
763 >     * Deserializes this deque.
764       */
765      private void readObject(ObjectInputStream s)
766              throws IOException, ClassNotFoundException {

Diff Legend

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