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.21 by dl, Fri Sep 16 23:17:05 2005 UTC vs.
Revision 1.36 by jsr166, Fri Dec 2 15:51:56 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 65 | Line 63 | public class ArrayDeque<E> extends Abstr
63       * other.  We also guarantee that all array cells not holding
64       * deque elements are always null.
65       */
66 <    private transient E[] elements;
66 >    private transient Object[] elements;
67  
68      /**
69       * The index of the element at the head of the deque (which is the
# Line 109 | Line 107 | public class ArrayDeque<E> extends Abstr
107              if (initialCapacity < 0)   // Too many elements, must back off
108                  initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
109          }
110 <        elements = (E[]) new Object[initialCapacity];
110 >        elements = new Object[initialCapacity];
111      }
112  
113      /**
# Line 127 | Line 125 | public class ArrayDeque<E> extends Abstr
125          Object[] a = new Object[newCapacity];
126          System.arraycopy(elements, p, a, 0, r);
127          System.arraycopy(elements, 0, a, r, p);
128 <        elements = (E[])a;
128 >        elements = a;
129          head = 0;
130          tail = n;
131      }
# Line 155 | Line 153 | public class ArrayDeque<E> extends Abstr
153       * sufficient to hold 16 elements.
154       */
155      public ArrayDeque() {
156 <        elements = (E[]) new Object[16];
156 >        elements = new Object[16];
157      }
158  
159      /**
# Line 263 | Line 261 | public class ArrayDeque<E> extends Abstr
261  
262      public E pollFirst() {
263          int h = head;
264 <        E result = elements[h]; // Element is null if deque empty
264 >        @SuppressWarnings("unchecked") E result = (E) elements[h];
265 >        // Element is null if deque empty
266          if (result == null)
267              return null;
268          elements[h] = null;     // Must null out slot
# Line 273 | Line 272 | public class ArrayDeque<E> extends Abstr
272  
273      public E pollLast() {
274          int t = (tail - 1) & (elements.length - 1);
275 <        E result = elements[t];
275 >        @SuppressWarnings("unchecked") E result = (E) elements[t];
276          if (result == null)
277              return null;
278          elements[t] = null;
# Line 285 | Line 284 | public class ArrayDeque<E> extends Abstr
284       * @throws NoSuchElementException {@inheritDoc}
285       */
286      public E getFirst() {
287 <        E x = elements[head];
288 <        if (x == null)
287 >        @SuppressWarnings("unchecked") E result = (E) elements[head];
288 >        if (result == null)
289              throw new NoSuchElementException();
290 <        return x;
290 >        return result;
291      }
292  
293      /**
294       * @throws NoSuchElementException {@inheritDoc}
295       */
296      public E getLast() {
297 <        E x = elements[(tail - 1) & (elements.length - 1)];
298 <        if (x == null)
297 >        @SuppressWarnings("unchecked")
298 >        E result = (E) elements[(tail - 1) & (elements.length - 1)];
299 >        if (result == null)
300              throw new NoSuchElementException();
301 <        return x;
301 >        return result;
302      }
303  
304 +    @SuppressWarnings("unchecked")
305      public E peekFirst() {
306 <        return elements[head]; // elements[head] is null if deque empty
306 >        // elements[head] is null if deque empty
307 >        return (E) elements[head];
308      }
309  
310 +    @SuppressWarnings("unchecked")
311      public E peekLast() {
312 <        return elements[(tail - 1) & (elements.length - 1)];
312 >        return (E) elements[(tail - 1) & (elements.length - 1)];
313      }
314  
315      /**
# Line 326 | Line 329 | public class ArrayDeque<E> extends Abstr
329              return false;
330          int mask = elements.length - 1;
331          int i = head;
332 <        E x;
332 >        Object x;
333          while ( (x = elements[i]) != null) {
334              if (o.equals(x)) {
335                  delete(i);
# Line 354 | Line 357 | public class ArrayDeque<E> extends Abstr
357              return false;
358          int mask = elements.length - 1;
359          int i = (tail - 1) & mask;
360 <        E x;
360 >        Object x;
361          while ( (x = elements[i]) != null) {
362              if (o.equals(x)) {
363                  delete(i);
# Line 479 | Line 482 | public class ArrayDeque<E> extends Abstr
482          return removeFirst();
483      }
484  
485 +    private void checkInvariants() {
486 +        assert elements[tail] == null;
487 +        assert head == tail ? elements[head] == null :
488 +            (elements[head] != null &&
489 +             elements[(tail - 1) & (elements.length - 1)] != null);
490 +        assert elements[(head - 1) & (elements.length - 1)] == null;
491 +    }
492 +
493      /**
494       * Removes the element at the specified position in the elements array,
495       * adjusting head and tail as necessary.  This can result in motion of
# Line 490 | Line 501 | public class ArrayDeque<E> extends Abstr
501       * @return true if elements moved backwards
502       */
503      private boolean delete(int i) {
504 <        int mask = elements.length - 1;
505 <        int front = (i - head) & mask;
506 <        int back  = (tail - i) & mask;
507 <
508 <        // Invariant: head <= i < tail mod circularity
509 <        if (front >= ((tail - head) & mask))
510 <            throw new ConcurrentModificationException();
511 <
512 <        // Optimize for least element motion
513 <        if (front < back) {
514 <            if (head <= i) {
515 <                System.arraycopy(elements, head, elements, head + 1, front);
516 <            } else { // Wrap around
517 <                elements[0] = elements[mask];
518 <                System.arraycopy(elements, 0, elements, 1, i);
519 <                System.arraycopy(elements, head, elements, head + 1, mask - head);
520 <            }
521 <            elements[head] = null;
522 <            head = (head + 1) & mask;
504 >        checkInvariants();
505 >        final Object[] elements = this.elements;
506 >        final int mask = elements.length - 1;
507 >        final int h = head;
508 >        final int t = tail;
509 >        final int front = (i - h) & mask;
510 >        final int back  = (t - i) & mask;
511 >
512 >        // Invariant: head <= i < tail mod circularity
513 >        if (front >= ((t - h) & mask))
514 >            throw new ConcurrentModificationException();
515 >
516 >        // Optimize for least element motion
517 >        if (front < back) {
518 >            if (h <= i) {
519 >                System.arraycopy(elements, h, elements, h + 1, front);
520 >            } else { // Wrap around
521 >                System.arraycopy(elements, 0, elements, 1, i);
522 >                elements[0] = elements[mask];
523 >                System.arraycopy(elements, h, elements, h + 1, mask - h);
524 >            }
525 >            elements[h] = null;
526 >            head = (h + 1) & mask;
527              return false;
528 <        } else {
529 <            int t = tail;
530 <            tail = (tail - 1) & mask;
531 <            if (i < t) { // Copy the null tail as well
532 <                System.arraycopy(elements, i + 1, elements, i, back);
533 <            } else {     // Wrap around
534 <                elements[mask] = elements[0];
535 <                System.arraycopy(elements, i + 1, elements, i, mask - i);
536 <                System.arraycopy(elements, 1, elements, 0, t);
537 <            }
528 >        } else {
529 >            if (i < t) { // Copy the null tail as well
530 >                System.arraycopy(elements, i + 1, elements, i, back);
531 >                tail = t - 1;
532 >            } else { // Wrap around
533 >                System.arraycopy(elements, i + 1, elements, i, mask - i);
534 >                elements[mask] = elements[0];
535 >                System.arraycopy(elements, 1, elements, 0, t);
536 >                tail = (t - 1) & mask;
537 >            }
538              return true;
539 <        }
539 >        }
540      }
541  
542      // *** Collection Methods ***
# Line 583 | Line 598 | public class ArrayDeque<E> extends Abstr
598          }
599  
600          public E next() {
586 –            E result;
601              if (cursor == fence)
602                  throw new NoSuchElementException();
603 +            @SuppressWarnings("unchecked") E result = (E) elements[cursor];
604              // This check doesn't catch all possible comodifications,
605              // but does catch the ones that corrupt traversal
606 <            if (tail != fence || (result = elements[cursor]) == null)
606 >            if (tail != fence || result == null)
607                  throw new ConcurrentModificationException();
608              lastRet = cursor;
609              cursor = (cursor + 1) & (elements.length - 1);
# Line 598 | Line 613 | public class ArrayDeque<E> extends Abstr
613          public void remove() {
614              if (lastRet < 0)
615                  throw new IllegalStateException();
616 <            if (delete(lastRet)) // if left-shifted, undo increment in next()
616 >            if (delete(lastRet)) { // if left-shifted, undo increment in next()
617                  cursor = (cursor - 1) & (elements.length - 1);
618 +                fence = tail;
619 +            }
620              lastRet = -1;
604 –            fence = tail;
621          }
622      }
623  
608 –
624      private class DescendingIterator implements Iterator<E> {
625          /*
626           * This class is nearly a mirror-image of DeqIterator, using
627 <         * (tail-1) instead of head for initial cursor, (head-1)
628 <         * 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.
627 >         * tail instead of head for initial cursor, and head instead of
628 >         * tail for fence.
629           */
630 <        private int cursor = (tail - 1) & (elements.length - 1);
631 <        private int fence =  (head - 1) & (elements.length - 1);
632 <        private int lastRet = elements.length;
630 >        private int cursor = tail;
631 >        private int fence = head;
632 >        private int lastRet = -1;
633  
634          public boolean hasNext() {
635              return cursor != fence;
636          }
637  
638          public E next() {
626 –            E result;
639              if (cursor == fence)
640                  throw new NoSuchElementException();
641 <            if (((head - 1) & (elements.length - 1)) != fence ||
642 <                (result = elements[cursor]) == null)
641 >            cursor = (cursor - 1) & (elements.length - 1);
642 >            @SuppressWarnings("unchecked") E result = (E) elements[cursor];
643 >            if (head != fence || result == null)
644                  throw new ConcurrentModificationException();
645              lastRet = cursor;
633 –            cursor = (cursor - 1) & (elements.length - 1);
646              return result;
647          }
648  
649          public void remove() {
650 <            if (lastRet >= elements.length)
650 >            if (lastRet < 0)
651                  throw new IllegalStateException();
652 <            if (!delete(lastRet))
652 >            if (!delete(lastRet)) {
653                  cursor = (cursor + 1) & (elements.length - 1);
654 <            lastRet = elements.length;
655 <            fence = (head - 1) & (elements.length - 1);
654 >                fence = head;
655 >            }
656 >            lastRet = -1;
657          }
658      }
659  
# Line 657 | Line 670 | public class ArrayDeque<E> extends Abstr
670              return false;
671          int mask = elements.length - 1;
672          int i = head;
673 <        E x;
673 >        Object x;
674          while ( (x = elements[i]) != null) {
675              if (o.equals(x))
676                  return true;
# Line 715 | Line 728 | public class ArrayDeque<E> extends Abstr
728       * @return an array containing all of the elements in this deque
729       */
730      public Object[] toArray() {
731 <        return copyElements(new Object[size()]);
731 >        return copyElements(new Object[size()]);
732      }
733  
734      /**
# Line 740 | Line 753 | public class ArrayDeque<E> extends Abstr
753       * The following code can be used to dump the deque into a newly
754       * allocated array of <tt>String</tt>:
755       *
756 <     * <pre>
744 <     *     String[] y = x.toArray(new String[0]);</pre>
756 >     *  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
757       *
758       * Note that <tt>toArray(new Object[0])</tt> is identical in function to
759       * <tt>toArray()</tt>.
# Line 755 | Line 767 | public class ArrayDeque<E> extends Abstr
767       *         this deque
768       * @throws NullPointerException if the specified array is null
769       */
770 +    @SuppressWarnings("unchecked")
771      public <T> T[] toArray(T[] a) {
772          int size = size();
773          if (a.length < size)
774              a = (T[])java.lang.reflect.Array.newInstance(
775                      a.getClass().getComponentType(), size);
776 <        copyElements(a);
776 >        copyElements(a);
777          if (a.length > size)
778              a[size] = null;
779          return a;
# Line 775 | Line 788 | public class ArrayDeque<E> extends Abstr
788       */
789      public ArrayDeque<E> clone() {
790          try {
791 +            @SuppressWarnings("unchecked")
792              ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
793 <            // 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);
793 >            result.elements = Arrays.copyOf(elements, elements.length);
794              return result;
783 –
795          } catch (CloneNotSupportedException e) {
796              throw new AssertionError();
797          }
# Line 798 | Line 809 | public class ArrayDeque<E> extends Abstr
809       * followed by all of its elements (each an object reference) in
810       * first-to-last order.
811       */
812 <    private void writeObject(ObjectOutputStream s) throws IOException {
812 >    private void writeObject(java.io.ObjectOutputStream s)
813 >            throws java.io.IOException {
814          s.defaultWriteObject();
815  
816          // Write out size
# Line 813 | Line 825 | public class ArrayDeque<E> extends Abstr
825      /**
826       * Deserialize this deque.
827       */
828 <    private void readObject(ObjectInputStream s)
829 <            throws IOException, ClassNotFoundException {
828 >    private void readObject(java.io.ObjectInputStream s)
829 >            throws java.io.IOException, ClassNotFoundException {
830          s.defaultReadObject();
831  
832          // Read in size and allocate array
# Line 825 | Line 837 | public class ArrayDeque<E> extends Abstr
837  
838          // Read in all elements in the proper order.
839          for (int i = 0; i < size; i++)
840 <            elements[i] = (E)s.readObject();
829 <
840 >            elements[i] = s.readObject();
841      }
842   }

Diff Legend

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