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.22 by dl, Fri Sep 16 23:59:27 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 <        int front = (i - head) & mask;
502 <        int back  = (tail - i) & mask;
503 <
504 <        // Invariant: head <= i < tail mod circularity
505 <        if (front >= ((tail - head) & mask))
506 <            throw new ConcurrentModificationException();
507 <
508 <        // Optimize for least element motion
509 <        if (front < back) {
510 <            if (head <= i) {
511 <                System.arraycopy(elements, head, elements, head + 1, front);
512 <            } else { // Wrap around
513 <                System.arraycopy(elements, 0, elements, 1, i);
514 <                elements[0] = elements[mask];
515 <                System.arraycopy(elements, head, elements, head + 1, mask - head);
516 <            }
517 <            elements[head] = null;
518 <            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 <            int t = tail;
526 <            tail = (tail - 1) & mask;
527 <            if (i < t) { // Copy the null tail as well
528 <                System.arraycopy(elements, i + 1, elements, i, back);
529 <            } else {     // Wrap around
530 <                System.arraycopy(elements, i + 1, elements, i, mask - i);
531 <                elements[mask] = elements[0];
532 <                System.arraycopy(elements, 1, elements, 0, t);
533 <            }
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 <        }
535 >        }
536      }
537  
538      // *** Collection Methods ***
# Line 583 | Line 594 | public class ArrayDeque<E> extends Abstr
594          }
595  
596          public E next() {
586 –            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 598 | 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;
604 –            fence = tail;
617          }
618      }
619  
608 –
620      private class DescendingIterator implements Iterator<E> {
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
614 <         * for sentinel. It shares the same structure, but not many
615 <         * 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() {
626 –            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;
633 –            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 715 | 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 760 | 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 776 | 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:
780 <            result.elements = (E[]) new Object[elements.length];
781 <            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 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