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.12 by jsr166, Tue May 17 16:14:34 2005 UTC vs.
Revision 1.24 by dl, Sat Sep 17 13:21:19 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 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 487 | Line 490 | public class ArrayDeque<E> extends Abstr
490       * @return true if elements moved backwards
491       */
492      private boolean delete(int i) {
493 <        int mask = elements.length - 1;
493 >        final E[] elements = this.elements;
494 >        final int mask = elements.length - 1;
495 >        final int h = head;
496 >        final int t = tail;
497 >        final int front = (i - h) & mask;
498 >        final int back  = (t - i) & mask;
499  
500          // Invariant: head <= i < tail mod circularity
501 <        if (((i - head) & mask) >= ((tail - head) & mask))
501 >        if (front >= ((t - h) & mask))
502              throw new ConcurrentModificationException();
503  
504 <        // Case 1: Deque doesn't wrap
505 <        // Case 2: Deque does wrap and removed element is in the head portion
506 <        if (i >= head) {
507 <            System.arraycopy(elements, head, elements, head + 1, i - head);
508 <            elements[head] = null;
509 <            head = (head + 1) & mask;
510 <            return false;
511 <        }
512 <
513 <        // Case 3: Deque wraps and removed element is in the tail portion
514 <        tail--;
515 <        System.arraycopy(elements, i + 1, elements, i, tail - i);
516 <        elements[tail] = null;
517 <        return true;
504 >        // Optimize for least element motion
505 >        if (front < back) {
506 >            if (h <= i) {
507 >                System.arraycopy(elements, h, elements, h + 1, front);
508 >            } else { // Wrap around
509 >                System.arraycopy(elements, 0, elements, 1, i);
510 >                elements[0] = elements[mask];
511 >                System.arraycopy(elements, h, elements, h + 1, mask - h);
512 >            }
513 >            elements[h] = null;
514 >            head = (h + 1) & mask;
515 >            return false;
516 >        } else {
517 >            if (i < t) { // Copy the null tail as well
518 >                System.arraycopy(elements, i + 1, elements, i, back);
519 >                tail = t - 1;
520 >            } else { // Wrap around
521 >                System.arraycopy(elements, i + 1, elements, i, mask - i);
522 >                elements[mask] = elements[0];
523 >                System.arraycopy(elements, 1, elements, 0, t);
524 >                tail = (t - 1) & mask;
525 >            }
526 >            return true;
527 >        }
528      }
529  
530      // *** Collection Methods ***
# Line 535 | Line 553 | public class ArrayDeque<E> extends Abstr
553       * order that elements would be dequeued (via successive calls to
554       * {@link #remove} or popped (via successive calls to {@link #pop}).
555       *
556 <     * @return an <tt>Iterator</tt> over the elements in this deque
556 >     * @return an iterator over the elements in this deque
557       */
558      public Iterator<E> iterator() {
559          return new DeqIterator();
560      }
561  
562 +    public Iterator<E> descendingIterator() {
563 +        return new DescendingIterator();
564 +    }
565 +
566      private class DeqIterator implements Iterator<E> {
567          /**
568           * Index of element to be returned by subsequent call to next.
# Line 579 | Line 601 | public class ArrayDeque<E> extends Abstr
601          public void remove() {
602              if (lastRet < 0)
603                  throw new IllegalStateException();
604 <            if (delete(lastRet))
605 <                cursor--;
604 >            if (delete(lastRet)) // if left-shifted, undo increment in next()
605 >                cursor = (cursor - 1) & (elements.length - 1);
606              lastRet = -1;
607              fence = tail;
608          }
609      }
610  
611 +
612 +    private class DescendingIterator implements Iterator<E> {
613 +        /*
614 +         * This class is nearly a mirror-image of DeqIterator, using
615 +         * (tail-1) instead of head for initial cursor, (head-1)
616 +         * instead of tail for fence, and elements.length instead of -1
617 +         * for sentinel. It shares the same structure, but not many
618 +         * actual lines of code.
619 +         */
620 +        private int cursor = (tail - 1) & (elements.length - 1);
621 +        private int fence =  (head - 1) & (elements.length - 1);
622 +        private int lastRet = elements.length;
623 +
624 +        public boolean hasNext() {
625 +            return cursor != fence;
626 +        }
627 +
628 +        public E next() {
629 +            E result;
630 +            if (cursor == fence)
631 +                throw new NoSuchElementException();
632 +            if (((head - 1) & (elements.length - 1)) != fence ||
633 +                (result = elements[cursor]) == null)
634 +                throw new ConcurrentModificationException();
635 +            lastRet = cursor;
636 +            cursor = (cursor - 1) & (elements.length - 1);
637 +            return result;
638 +        }
639 +
640 +        public void remove() {
641 +            if (lastRet >= elements.length)
642 +                throw new IllegalStateException();
643 +            if (!delete(lastRet))
644 +                cursor = (cursor + 1) & (elements.length - 1);
645 +            lastRet = elements.length;
646 +            fence = (head - 1) & (elements.length - 1);
647 +        }
648 +    }
649 +
650      /**
651       * Returns <tt>true</tt> if this deque contains the specified element.
652       * More formally, returns <tt>true</tt> if and only if this deque contains
# Line 650 | Line 711 | public class ArrayDeque<E> extends Abstr
711       * <p>The returned array will be "safe" in that no references to it are
712       * maintained by this deque.  (In other words, this method must allocate
713       * a new array).  The caller is thus free to modify the returned array.
714 <     *
714 >     *
715       * <p>This method acts as bridge between array-based and collection-based
716       * APIs.
717       *
# Line 744 | Line 805 | public class ArrayDeque<E> extends Abstr
805          s.defaultWriteObject();
806  
807          // Write out size
808 <        int size = size();
748 <        s.writeInt(size);
808 >        s.writeInt(size());
809  
810          // Write out elements in order.
751 –        int i = head;
811          int mask = elements.length - 1;
812 <        for (int j = 0; j < size; j++) {
812 >        for (int i = head; i != tail; i = (i + 1) & mask)
813              s.writeObject(elements[i]);
755 –            i = (i + 1) & mask;
756 –        }
814      }
815  
816      /**

Diff Legend

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