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.17 by dl, Thu Sep 15 16:55:24 2005 UTC vs.
Revision 1.30 by jsr166, Sun May 18 23:47:55 2008 UTC

# Line 4 | Line 4
4   */
5  
6   package java.util;
7 – import java.util.*; // for javadoc (till 6280605 is fixed)
7   import java.io.*;
8  
9   /**
# Line 45 | Line 44 | import java.io.*;
44   * Iterator} interfaces.
45   *
46   * <p>This class is a member of the
47 < * <a href="{@docRoot}/../guide/collections/index.html">
47 > * <a href="{@docRoot}/../technotes/guides/collections/index.html">
48   * Java Collections Framework</a>.
49   *
50   * @author  Josh Bloch and Doug Lea
# Line 479 | Line 478 | public class ArrayDeque<E> extends Abstr
478          return removeFirst();
479      }
480  
481 +    private void checkInvariants() {
482 +        assert elements[tail] == null;
483 +        assert head == tail ? elements[head] == null :
484 +            (elements[head] != null &&
485 +             elements[(tail - 1) & (elements.length - 1)] != null);
486 +        assert elements[(head - 1) & (elements.length - 1)] == null;
487 +    }
488 +
489      /**
490       * Removes the element at the specified position in the elements array,
491       * adjusting head and tail as necessary.  This can result in motion of
# Line 490 | Line 497 | public class ArrayDeque<E> extends Abstr
497       * @return true if elements moved backwards
498       */
499      private boolean delete(int i) {
500 <        int mask = elements.length - 1;
501 <
502 <        // Invariant: head <= i < tail mod circularity
503 <        if (((i - head) & mask) >= ((tail - head) & mask))
504 <            throw new ConcurrentModificationException();
505 <
506 <        // Case 1: Deque doesn't wrap
507 <        // Case 2: Deque does wrap and removed element is in the head portion
508 <        if (i >= head) {
509 <            System.arraycopy(elements, head, elements, head + 1, i - head);
510 <            elements[head] = null;
511 <            head = (head + 1) & mask;
500 >        checkInvariants();
501 >        final E[] elements = this.elements;
502 >        final int mask = elements.length - 1;
503 >        final int h = head;
504 >        final int t = tail;
505 >        final int front = (i - h) & mask;
506 >        final int back  = (t - i) & mask;
507 >
508 >        // Invariant: head <= i < tail mod circularity
509 >        if (front >= ((t - h) & mask))
510 >            throw new ConcurrentModificationException();
511 >
512 >        // Optimize for least element motion
513 >        if (front < back) {
514 >            if (h <= i) {
515 >                System.arraycopy(elements, h, elements, h + 1, front);
516 >            } else { // Wrap around
517 >                System.arraycopy(elements, 0, elements, 1, i);
518 >                elements[0] = elements[mask];
519 >                System.arraycopy(elements, h, elements, h + 1, mask - h);
520 >            }
521 >            elements[h] = null;
522 >            head = (h + 1) & mask;
523              return false;
524 +        } else {
525 +            if (i < t) { // Copy the null tail as well
526 +                System.arraycopy(elements, i + 1, elements, i, back);
527 +                tail = t - 1;
528 +            } else { // Wrap around
529 +                System.arraycopy(elements, i + 1, elements, i, mask - i);
530 +                elements[mask] = elements[0];
531 +                System.arraycopy(elements, 1, elements, 0, t);
532 +                tail = (t - 1) & mask;
533 +            }
534 +            return true;
535          }
507 –
508 –        // Case 3: Deque wraps and removed element is in the tail portion
509 –        tail--;
510 –        System.arraycopy(elements, i + 1, elements, i, tail - i);
511 –        elements[tail] = null;
512 –        return true;
536      }
537  
538      // *** Collection Methods ***
# Line 538 | Line 561 | public class ArrayDeque<E> extends Abstr
561       * order that elements would be dequeued (via successive calls to
562       * {@link #remove} or popped (via successive calls to {@link #pop}).
563       *
564 <     * @return an <tt>Iterator</tt> over the elements in this deque
564 >     * @return an iterator over the elements in this deque
565       */
566      public Iterator<E> iterator() {
567          return new DeqIterator();
568      }
569  
547 –    /**
548 –     * Returns an iterator over the elements in this deque in reverse
549 –     * sequential order.  The elements will be returned in order from
550 –     * last (tail) to first (head).
551 –     *
552 –     * @return an iterator over the elements in this deque in reverse
553 –     * sequence
554 –     */
570      public Iterator<E> descendingIterator() {
571          return new DescendingIterator();
572      }
# Line 579 | Line 594 | public class ArrayDeque<E> extends Abstr
594          }
595  
596          public E next() {
582 –            E result;
597              if (cursor == fence)
598                  throw new NoSuchElementException();
599 +            E result = elements[cursor];
600              // This check doesn't catch all possible comodifications,
601              // but does catch the ones that corrupt traversal
602 <            if (tail != fence || (result = elements[cursor]) == null)
602 >            if (tail != fence || result == null)
603                  throw new ConcurrentModificationException();
604              lastRet = cursor;
605              cursor = (cursor + 1) & (elements.length - 1);
# Line 594 | Line 609 | public class ArrayDeque<E> extends Abstr
609          public void remove() {
610              if (lastRet < 0)
611                  throw new IllegalStateException();
612 <            if (delete(lastRet)) // if left-shifted, undo increment in next()
612 >            if (delete(lastRet)) { // if left-shifted, undo increment in next()
613                  cursor = (cursor - 1) & (elements.length - 1);
614 +                fence = tail;
615 +            }
616              lastRet = -1;
600 –            fence = tail;
617          }
618      }
619  
604 –
620      private class DescendingIterator implements Iterator<E> {
621 <        /*
621 >        /*
622           * This class is nearly a mirror-image of DeqIterator, using
623 <         * (tail-1) instead of head for initial cursor, (head-1)
624 <         * instead of tail for fence, and elements.length instead of -1
610 <         * for sentinel. It shares the same structure, but not many
611 <         * actual lines of code.
623 >         * tail instead of head for initial cursor, and head instead of
624 >         * tail for fence.
625           */
626 <        private int cursor = (tail - 1) & (elements.length - 1);
627 <        private int fence =  (head - 1) & (elements.length - 1);
628 <        private int lastRet = elements.length;
626 >        private int cursor = tail;
627 >        private int fence = head;
628 >        private int lastRet = -1;
629  
630          public boolean hasNext() {
631              return cursor != fence;
632          }
633  
634          public E next() {
622 –            E result;
635              if (cursor == fence)
636                  throw new NoSuchElementException();
637 <            if (((head - 1) & (elements.length - 1)) != fence ||
638 <                (result = elements[cursor]) == null)
637 >            cursor = (cursor - 1) & (elements.length - 1);
638 >            E result = elements[cursor];
639 >            if (head != fence || result == null)
640                  throw new ConcurrentModificationException();
641              lastRet = cursor;
629 –            cursor = (cursor - 1) & (elements.length - 1);
642              return result;
643          }
644  
645          public void remove() {
646 <            if (lastRet >= elements.length)
646 >            if (lastRet < 0)
647                  throw new IllegalStateException();
648 <            if (!delete(lastRet))
648 >            if (!delete(lastRet)) {
649                  cursor = (cursor + 1) & (elements.length - 1);
650 <            lastRet = elements.length;
651 <            fence = (head - 1) & (elements.length - 1);
650 >                fence = head;
651 >            }
652 >            lastRet = -1;
653          }
654      }
655  
# Line 711 | Line 724 | public class ArrayDeque<E> extends Abstr
724       * @return an array containing all of the elements in this deque
725       */
726      public Object[] toArray() {
727 <        return copyElements(new Object[size()]);
727 >        return copyElements(new Object[size()]);
728      }
729  
730      /**
# Line 756 | Line 769 | public class ArrayDeque<E> extends Abstr
769          if (a.length < size)
770              a = (T[])java.lang.reflect.Array.newInstance(
771                      a.getClass().getComponentType(), size);
772 <        copyElements(a);
772 >        copyElements(a);
773          if (a.length > size)
774              a[size] = null;
775          return a;
# Line 772 | Line 785 | public class ArrayDeque<E> extends Abstr
785      public ArrayDeque<E> clone() {
786          try {
787              ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
788 <            // These two lines are currently faster than cloning the array:
776 <            result.elements = (E[]) new Object[elements.length];
777 <            System.arraycopy(elements, 0, result.elements, 0, elements.length);
788 >            result.elements = Arrays.copyOf(elements, elements.length);
789              return result;
790  
791          } catch (CloneNotSupportedException e) {
# Line 798 | Line 809 | public class ArrayDeque<E> extends Abstr
809          s.defaultWriteObject();
810  
811          // Write out size
812 <        int size = size();
802 <        s.writeInt(size);
812 >        s.writeInt(size());
813  
814          // Write out elements in order.
805 –        int i = head;
815          int mask = elements.length - 1;
816 <        for (int j = 0; j < size; j++) {
816 >        for (int i = head; i != tail; i = (i + 1) & mask)
817              s.writeObject(elements[i]);
809 –            i = (i + 1) & mask;
810 –        }
818      }
819  
820      /**
# Line 826 | Line 833 | public class ArrayDeque<E> extends Abstr
833          // Read in all elements in the proper order.
834          for (int i = 0; i < size; i++)
835              elements[i] = (E)s.readObject();
829 –
836      }
837   }

Diff Legend

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