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.19 by dl, Fri Sep 16 11:15:41 2005 UTC vs.
Revision 1.32 by jsr166, Wed Jun 8 00:21:52 2011 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 java.util;
7 – import java.util.*; // for javadoc (till 6280605 is fixed)
8 – import java.io.*;
7  
8   /**
9   * Resizable-array implementation of the {@link Deque} interface.  Array
# Line 45 | Line 43 | import java.io.*;
43   * Iterator} interfaces.
44   *
45   * <p>This class is a member of the
46 < * <a href="{@docRoot}/../guide/collections/index.html">
46 > * <a href="{@docRoot}/../technotes/guides/collections/index.html">
47   * Java Collections Framework</a>.
48   *
49   * @author  Josh Bloch and Doug Lea
# Line 53 | Line 51 | import java.io.*;
51   * @param <E> the type of elements held in this collection
52   */
53   public class ArrayDeque<E> extends AbstractCollection<E>
54 <                           implements Deque<E>, Cloneable, Serializable
54 >                           implements Deque<E>, Cloneable, java.io.Serializable
55   {
56      /**
57       * The array in which the elements of the deque are stored.
# Line 479 | Line 477 | public class ArrayDeque<E> extends Abstr
477          return removeFirst();
478      }
479  
480 +    private void checkInvariants() {
481 +        assert elements[tail] == null;
482 +        assert head == tail ? elements[head] == null :
483 +            (elements[head] != null &&
484 +             elements[(tail - 1) & (elements.length - 1)] != null);
485 +        assert elements[(head - 1) & (elements.length - 1)] == null;
486 +    }
487 +
488      /**
489       * Removes the element at the specified position in the elements array,
490       * adjusting head and tail as necessary.  This can result in motion of
# Line 490 | Line 496 | public class ArrayDeque<E> extends Abstr
496       * @return true if elements moved backwards
497       */
498      private boolean delete(int i) {
499 <        int mask = elements.length - 1;
500 <
501 <        // Invariant: head <= i < tail mod circularity
502 <        if (((i - head) & mask) >= ((tail - head) & mask))
503 <            throw new ConcurrentModificationException();
504 <
505 <        // Case 1: Deque doesn't wrap
506 <        // Case 2: Deque does wrap and removed element is in the head portion
507 <        if (i >= head) {
508 <            System.arraycopy(elements, head, elements, head + 1, i - head);
509 <            elements[head] = null;
510 <            head = (head + 1) & mask;
499 >        checkInvariants();
500 >        final E[] elements = this.elements;
501 >        final int mask = elements.length - 1;
502 >        final int h = head;
503 >        final int t = tail;
504 >        final int front = (i - h) & mask;
505 >        final int back  = (t - i) & mask;
506 >
507 >        // Invariant: head <= i < tail mod circularity
508 >        if (front >= ((t - h) & mask))
509 >            throw new ConcurrentModificationException();
510 >
511 >        // Optimize for least element motion
512 >        if (front < back) {
513 >            if (h <= i) {
514 >                System.arraycopy(elements, h, elements, h + 1, front);
515 >            } else { // Wrap around
516 >                System.arraycopy(elements, 0, elements, 1, i);
517 >                elements[0] = elements[mask];
518 >                System.arraycopy(elements, h, elements, h + 1, mask - h);
519 >            }
520 >            elements[h] = null;
521 >            head = (h + 1) & mask;
522              return false;
523 +        } else {
524 +            if (i < t) { // Copy the null tail as well
525 +                System.arraycopy(elements, i + 1, elements, i, back);
526 +                tail = t - 1;
527 +            } else { // Wrap around
528 +                System.arraycopy(elements, i + 1, elements, i, mask - i);
529 +                elements[mask] = elements[0];
530 +                System.arraycopy(elements, 1, elements, 0, t);
531 +                tail = (t - 1) & mask;
532 +            }
533 +            return true;
534          }
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;
535      }
536  
537      // *** Collection Methods ***
# Line 571 | Line 593 | public class ArrayDeque<E> extends Abstr
593          }
594  
595          public E next() {
574 –            E result;
596              if (cursor == fence)
597                  throw new NoSuchElementException();
598 +            E result = elements[cursor];
599              // This check doesn't catch all possible comodifications,
600              // but does catch the ones that corrupt traversal
601 <            if (tail != fence || (result = elements[cursor]) == null)
601 >            if (tail != fence || result == null)
602                  throw new ConcurrentModificationException();
603              lastRet = cursor;
604              cursor = (cursor + 1) & (elements.length - 1);
# Line 586 | Line 608 | public class ArrayDeque<E> extends Abstr
608          public void remove() {
609              if (lastRet < 0)
610                  throw new IllegalStateException();
611 <            if (delete(lastRet)) // if left-shifted, undo increment in next()
611 >            if (delete(lastRet)) { // if left-shifted, undo increment in next()
612                  cursor = (cursor - 1) & (elements.length - 1);
613 +                fence = tail;
614 +            }
615              lastRet = -1;
592 –            fence = tail;
616          }
617      }
618  
596 –
619      private class DescendingIterator implements Iterator<E> {
620          /*
621           * This class is nearly a mirror-image of DeqIterator, using
622 <         * (tail-1) instead of head for initial cursor, (head-1)
623 <         * 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.
622 >         * tail instead of head for initial cursor, and head instead of
623 >         * tail for fence.
624           */
625 <        private int cursor = (tail - 1) & (elements.length - 1);
626 <        private int fence =  (head - 1) & (elements.length - 1);
627 <        private int lastRet = elements.length;
625 >        private int cursor = tail;
626 >        private int fence = head;
627 >        private int lastRet = -1;
628  
629          public boolean hasNext() {
630              return cursor != fence;
631          }
632  
633          public E next() {
614 –            E result;
634              if (cursor == fence)
635                  throw new NoSuchElementException();
636 <            if (((head - 1) & (elements.length - 1)) != fence ||
637 <                (result = elements[cursor]) == null)
636 >            cursor = (cursor - 1) & (elements.length - 1);
637 >            E result = elements[cursor];
638 >            if (head != fence || result == null)
639                  throw new ConcurrentModificationException();
640              lastRet = cursor;
621 –            cursor = (cursor - 1) & (elements.length - 1);
641              return result;
642          }
643  
644          public void remove() {
645 <            if (lastRet >= elements.length)
645 >            if (lastRet < 0)
646                  throw new IllegalStateException();
647 <            if (!delete(lastRet))
647 >            if (!delete(lastRet)) {
648                  cursor = (cursor + 1) & (elements.length - 1);
649 <            lastRet = elements.length;
650 <            fence = (head - 1) & (elements.length - 1);
649 >                fence = head;
650 >            }
651 >            lastRet = -1;
652          }
653      }
654  
# Line 703 | Line 723 | public class ArrayDeque<E> extends Abstr
723       * @return an array containing all of the elements in this deque
724       */
725      public Object[] toArray() {
726 <        return copyElements(new Object[size()]);
726 >        return copyElements(new Object[size()]);
727      }
728  
729      /**
# Line 748 | Line 768 | public class ArrayDeque<E> extends Abstr
768          if (a.length < size)
769              a = (T[])java.lang.reflect.Array.newInstance(
770                      a.getClass().getComponentType(), size);
771 <        copyElements(a);
771 >        copyElements(a);
772          if (a.length > size)
773              a[size] = null;
774          return a;
# Line 764 | Line 784 | public class ArrayDeque<E> extends Abstr
784      public ArrayDeque<E> clone() {
785          try {
786              ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
787 <            // These two lines are currently faster than cloning the array:
768 <            result.elements = (E[]) new Object[elements.length];
769 <            System.arraycopy(elements, 0, result.elements, 0, elements.length);
787 >            result.elements = Arrays.copyOf(elements, elements.length);
788              return result;
789  
790          } catch (CloneNotSupportedException e) {
# Line 786 | Line 804 | public class ArrayDeque<E> extends Abstr
804       * followed by all of its elements (each an object reference) in
805       * first-to-last order.
806       */
807 <    private void writeObject(ObjectOutputStream s) throws IOException {
807 >    private void writeObject(java.io.ObjectOutputStream s)
808 >            throws java.io.IOException {
809          s.defaultWriteObject();
810  
811          // Write out size
# Line 801 | Line 820 | public class ArrayDeque<E> extends Abstr
820      /**
821       * Deserialize this deque.
822       */
823 <    private void readObject(ObjectInputStream s)
824 <            throws IOException, ClassNotFoundException {
823 >    private void readObject(java.io.ObjectInputStream s)
824 >            throws java.io.IOException, ClassNotFoundException {
825          s.defaultReadObject();
826  
827          // Read in size and allocate array
# Line 814 | 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();
817 –
836      }
837   }

Diff Legend

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