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.9 by jsr166, Mon May 16 06:16:12 2005 UTC vs.
Revision 1.19 by dl, Fri Sep 16 11:15:41 2005 UTC

# Line 4 | Line 4
4   */
5  
6   package java.util;
7 + import java.util.*; // for javadoc (till 6280605 is fixed)
8   import java.io.*;
9  
10   /**
# Line 202 | Line 203 | public class ArrayDeque<E> extends Abstr
203  
204      /**
205       * Inserts the specified element at the end of this deque.
206 <     * This method is equivalent to {@link #add} and {@link #push}.
206 >     *
207 >     * <p>This method is equivalent to {@link #add}.
208       *
209       * @param e the element to add
210       * @throws NullPointerException if the specified element is null
# Line 219 | Line 221 | public class ArrayDeque<E> extends Abstr
221       * Inserts the specified element at the front of this deque.
222       *
223       * @param e the element to add
224 <     * @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
224 >     * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
225       * @throws NullPointerException if the specified element is null
226       */
227      public boolean offerFirst(E e) {
# Line 231 | Line 233 | public class ArrayDeque<E> extends Abstr
233       * Inserts the specified element at the end of this deque.
234       *
235       * @param e the element to add
236 <     * @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
236 >     * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
237       * @throws NullPointerException if the specified element is null
238       */
239      public boolean offerLast(E e) {
# Line 313 | Line 315 | public class ArrayDeque<E> extends Abstr
315       * If the deque does not contain the element, it is unchanged.
316       * More formally, removes the first element <tt>e</tt> such that
317       * <tt>o.equals(e)</tt> (if such an element exists).
318 <     * Returns true if this deque contained the specified element (or
319 <     * equivalently, if this deque changed as a result of the call).
318 >     * Returns <tt>true</tt> if this deque contained the specified element
319 >     * (or equivalently, if this deque changed as a result of the call).
320       *
321       * @param o element to be removed from this deque, if present
322       * @return <tt>true</tt> if the deque contained the specified element
# Line 341 | Line 343 | public class ArrayDeque<E> extends Abstr
343       * If the deque does not contain the element, it is unchanged.
344       * More formally, removes the last element <tt>e</tt> such that
345       * <tt>o.equals(e)</tt> (if such an element exists).
346 <     * Returns true if this deque contained the specified element (or
347 <     * equivalently, if this deque changed as a result of the call).
346 >     * Returns <tt>true</tt> if this deque contained the specified element
347 >     * (or equivalently, if this deque changed as a result of the call).
348       *
349       * @param o element to be removed from this deque, if present
350       * @return <tt>true</tt> if the deque contained the specified element
# Line 371 | Line 373 | public class ArrayDeque<E> extends Abstr
373       * <p>This method is equivalent to {@link #addLast}.
374       *
375       * @param e the element to add
376 <     * @return <tt>true</tt> (as per the spec for {@link Collection#add})
376 >     * @return <tt>true</tt> (as specified by {@link Collection#add})
377       * @throws NullPointerException if the specified element is null
378       */
379      public boolean add(E e) {
# Line 385 | Line 387 | public class ArrayDeque<E> extends Abstr
387       * <p>This method is equivalent to {@link #offerLast}.
388       *
389       * @param e the element to add
390 <     * @return <tt>true</tt> (as per the spec for {@link Queue#offer})
390 >     * @return <tt>true</tt> (as specified by {@link Queue#offer})
391       * @throws NullPointerException if the specified element is null
392       */
393      public boolean offer(E e) {
# Line 394 | Line 396 | public class ArrayDeque<E> extends Abstr
396  
397      /**
398       * Retrieves and removes the head of the queue represented by this deque.
399 <     * This method differs from {@link #poll} only in that it throws an
399 >     *
400 >     * This method differs from {@link #poll poll} only in that it throws an
401       * exception if this deque is empty.
402       *
403       * <p>This method is equivalent to {@link #removeFirst}.
# Line 422 | Line 425 | public class ArrayDeque<E> extends Abstr
425  
426      /**
427       * Retrieves, but does not remove, the head of the queue represented by
428 <     * this deque.  This method differs from {@link #peek} only in that it
429 <     * throws an exception if this deque is empty.
428 >     * this deque.  This method differs from {@link #peek peek} only in
429 >     * that it throws an exception if this deque is empty.
430       *
431       * <p>This method is equivalent to {@link #getFirst}.
432       *
# Line 535 | Line 538 | public class ArrayDeque<E> extends Abstr
538       * order that elements would be dequeued (via successive calls to
539       * {@link #remove} or popped (via successive calls to {@link #pop}).
540       *
541 <     * @return an <tt>Iterator</tt> over the elements in this deque
541 >     * @return an iterator over the elements in this deque
542       */
543      public Iterator<E> iterator() {
544          return new DeqIterator();
545      }
546  
547 +    public Iterator<E> descendingIterator() {
548 +        return new DescendingIterator();
549 +    }
550 +
551      private class DeqIterator implements Iterator<E> {
552          /**
553           * Index of element to be returned by subsequent call to next.
# Line 579 | Line 586 | public class ArrayDeque<E> extends Abstr
586          public void remove() {
587              if (lastRet < 0)
588                  throw new IllegalStateException();
589 <            if (delete(lastRet))
590 <                cursor--;
589 >            if (delete(lastRet)) // if left-shifted, undo increment in next()
590 >                cursor = (cursor - 1) & (elements.length - 1);
591              lastRet = -1;
592              fence = tail;
593          }
594      }
595  
596 +
597 +    private class DescendingIterator implements Iterator<E> {
598 +        /*
599 +         * This class is nearly a mirror-image of DeqIterator, using
600 +         * (tail-1) instead of head for initial cursor, (head-1)
601 +         * instead of tail for fence, and elements.length instead of -1
602 +         * for sentinel. It shares the same structure, but not many
603 +         * actual lines of code.
604 +         */
605 +        private int cursor = (tail - 1) & (elements.length - 1);
606 +        private int fence =  (head - 1) & (elements.length - 1);
607 +        private int lastRet = elements.length;
608 +
609 +        public boolean hasNext() {
610 +            return cursor != fence;
611 +        }
612 +
613 +        public E next() {
614 +            E result;
615 +            if (cursor == fence)
616 +                throw new NoSuchElementException();
617 +            if (((head - 1) & (elements.length - 1)) != fence ||
618 +                (result = elements[cursor]) == null)
619 +                throw new ConcurrentModificationException();
620 +            lastRet = cursor;
621 +            cursor = (cursor - 1) & (elements.length - 1);
622 +            return result;
623 +        }
624 +
625 +        public void remove() {
626 +            if (lastRet >= elements.length)
627 +                throw new IllegalStateException();
628 +            if (!delete(lastRet))
629 +                cursor = (cursor + 1) & (elements.length - 1);
630 +            lastRet = elements.length;
631 +            fence = (head - 1) & (elements.length - 1);
632 +        }
633 +    }
634 +
635      /**
636       * Returns <tt>true</tt> if this deque contains the specified element.
637       * More formally, returns <tt>true</tt> if and only if this deque contains
# Line 613 | Line 659 | public class ArrayDeque<E> extends Abstr
659       * If the deque does not contain the element, it is unchanged.
660       * More formally, removes the first element <tt>e</tt> such that
661       * <tt>o.equals(e)</tt> (if such an element exists).
662 <     * Returns true if this deque contained the specified element (or
663 <     * equivalently, if this deque changed as a result of the call).
662 >     * Returns <tt>true</tt> if this deque contained the specified element
663 >     * (or equivalently, if this deque changed as a result of the call).
664       *
665       * <p>This method is equivalent to {@link #removeFirstOccurrence}.
666       *
# Line 645 | Line 691 | public class ArrayDeque<E> extends Abstr
691  
692      /**
693       * Returns an array containing all of the elements in this deque
694 <     * in the correct order.
694 >     * in proper sequence (from first to last element).
695 >     *
696 >     * <p>The returned array will be "safe" in that no references to it are
697 >     * maintained by this deque.  (In other words, this method must allocate
698 >     * a new array).  The caller is thus free to modify the returned array.
699 >     *
700 >     * <p>This method acts as bridge between array-based and collection-based
701 >     * APIs.
702       *
703       * @return an array containing all of the elements in this deque
651 –     *         in the correct order
704       */
705      public Object[] toArray() {
706          return copyElements(new Object[size()]);
707      }
708  
709      /**
710 <     * Returns an array containing all of the elements in this deque in the
711 <     * correct order; the runtime type of the returned array is that of the
712 <     * specified array.  If the deque fits in the specified array, it is
713 <     * returned therein.  Otherwise, a new array is allocated with the runtime
714 <     * type of the specified array and the size of this deque.
715 <     *
716 <     * <p>If the deque fits in the specified array with room to spare (i.e.,
717 <     * the array has more elements than the deque), the element in the array
718 <     * immediately following the end of the collection is set to <tt>null</tt>.
710 >     * Returns an array containing all of the elements in this deque in
711 >     * proper sequence (from first to last element); the runtime type of the
712 >     * returned array is that of the specified array.  If the deque fits in
713 >     * the specified array, it is returned therein.  Otherwise, a new array
714 >     * is allocated with the runtime type of the specified array and the
715 >     * size of this deque.
716 >     *
717 >     * <p>If this deque fits in the specified array with room to spare
718 >     * (i.e., the array has more elements than this deque), the element in
719 >     * the array immediately following the end of the deque is set to
720 >     * <tt>null</tt>.
721 >     *
722 >     * <p>Like the {@link #toArray()} method, this method acts as bridge between
723 >     * array-based and collection-based APIs.  Further, this method allows
724 >     * precise control over the runtime type of the output array, and may,
725 >     * under certain circumstances, be used to save allocation costs.
726 >     *
727 >     * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
728 >     * The following code can be used to dump the deque into a newly
729 >     * allocated array of <tt>String</tt>:
730 >     *
731 >     * <pre>
732 >     *     String[] y = x.toArray(new String[0]);</pre>
733 >     *
734 >     * Note that <tt>toArray(new Object[0])</tt> is identical in function to
735 >     * <tt>toArray()</tt>.
736       *
737       * @param a the array into which the elements of the deque are to
738       *          be stored, if it is big enough; otherwise, a new array of the
739       *          same runtime type is allocated for this purpose
740 <     * @return an array containing the elements of the deque
741 <     * @throws ArrayStoreException if the runtime type of a is not a supertype
742 <     *         of the runtime type of every element in this deque
740 >     * @return an array containing all of the elements in this deque
741 >     * @throws ArrayStoreException if the runtime type of the specified array
742 >     *         is not a supertype of the runtime type of every element in
743 >     *         this deque
744 >     * @throws NullPointerException if the specified array is null
745       */
746      public <T> T[] toArray(T[] a) {
747          int size = size();
# Line 719 | Line 790 | public class ArrayDeque<E> extends Abstr
790          s.defaultWriteObject();
791  
792          // Write out size
793 <        int size = size();
723 <        s.writeInt(size);
793 >        s.writeInt(size());
794  
795          // Write out elements in order.
726 –        int i = head;
796          int mask = elements.length - 1;
797 <        for (int j = 0; j < size; j++) {
797 >        for (int i = head; i != tail; i = (i + 1) & mask)
798              s.writeObject(elements[i]);
730 –            i = (i + 1) & mask;
731 –        }
799      }
800  
801      /**

Diff Legend

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