lib/classpath/external/jsr166/java/util/ArrayDeque.java

   1 /*
   2  * Written by Josh Bloch of Google Inc. and released to the public domain,
   3  * as explained at http://creativecommons.org/licenses/publicdomain.
   4  */
   5
   6 package java.util;
   7 import java.io.*;
   8
   9 /**
  10  * Resizable-array implementation of the {@link Deque} interface.  Array
  11  * deques have no capacity restrictions; they grow as necessary to support
  12  * usage.  They are not thread-safe; in the absence of external
  13  * synchronization, they do not support concurrent access by multiple threads.
  14  * Null elements are prohibited.  This class is likely to be faster than
  15  * {@link Stack} when used as a stack, and faster than {@link LinkedList}
  16  * when used as a queue.
  17  *
  18  * <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
  19  * Exceptions include {@link #remove(Object) remove}, {@link
  20  * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
  21  * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
  22  * iterator.remove()}, and the bulk operations, all of which run in linear
  23  * time.
  24  *
  25  * <p>The iterators returned by this class's <tt>iterator</tt> method are
  26  * <i>fail-fast</i>: If the deque is modified at any time after the iterator
  27  * is created, in any way except through the iterator's own <tt>remove</tt>
  28  * method, the iterator will generally throw a {@link
  29  * ConcurrentModificationException}.  Thus, in the face of concurrent
  30  * modification, the iterator fails quickly and cleanly, rather than risking
  31  * arbitrary, non-deterministic behavior at an undetermined time in the
  32  * future.
  33  *
  34  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  35  * as it is, generally speaking, impossible to make any hard guarantees in the
  36  * presence of unsynchronized concurrent modification.  Fail-fast iterators
  37  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
  38  * Therefore, it would be wrong to write a program that depended on this
  39  * exception for its correctness: <i>the fail-fast behavior of iterators
  40  * should be used only to detect bugs.</i>
  41  *
  42  * <p>This class and its iterator implement all of the
  43  * <em>optional</em> methods of the {@link Collection} and {@link
  44  * Iterator} interfaces.
  45  *
  46  * <p>This class is a member of the
  47  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  48  * Java Collections Framework</a>.
  49  *
  50  * @author  Josh Bloch and Doug Lea
  51  * @since   1.6
  52  * @param <E> the type of elements held in this collection
  53  */
  54 public class ArrayDeque<E> extends AbstractCollection<E>
  55                            implements Deque<E>, Cloneable, Serializable
  56 {
  57     /**
  58      * The array in which the elements of the deque are stored.
  59      * The capacity of the deque is the length of this array, which is
  60      * always a power of two. The array is never allowed to become
  61      * full, except transiently within an addX method where it is
  62      * resized (see doubleCapacity) immediately upon becoming full,
  63      * thus avoiding head and tail wrapping around to equal each
  64      * other.  We also guarantee that all array cells not holding
  65      * deque elements are always null.
  66      */
  67     private transient E[] elements;
  68
  69     /**
  70      * The index of the element at the head of the deque (which is the
  71      * element that would be removed by remove() or pop()); or an
  72      * arbitrary number equal to tail if the deque is empty.
  73      */
  74     private transient int head;
  75
  76     /**
  77      * The index at which the next element would be added to the tail
  78      * of the deque (via addLast(E), add(E), or push(E)).
  79      */
  80     private transient int tail;
  81
  82     /**
  83      * The minimum capacity that we'll use for a newly created deque.
  84      * Must be a power of 2.
  85      */
  86     private static final int MIN_INITIAL_CAPACITY = 8;
  87
  88     // ******  Array allocation and resizing utilities ******
  89
  90     /**
  91      * Allocate empty array to hold the given number of elements.
  92      *
  93      * @param numElements  the number of elements to hold
  94      */
  95     private void allocateElements(int numElements) {
  96         int initialCapacity = MIN_INITIAL_CAPACITY;
  97         // Find the best power of two to hold elements.
  98         // Tests "<=" because arrays aren't kept full.
  99         if (numElements >= initialCapacity) {
 100             initialCapacity = numElements;
 101             initialCapacity |= (initialCapacity >>>  1);
 102             initialCapacity |= (initialCapacity >>>  2);
 103             initialCapacity |= (initialCapacity >>>  4);
 104             initialCapacity |= (initialCapacity >>>  8);
 105             initialCapacity |= (initialCapacity >>> 16);
 106             initialCapacity++;
 107
 108             if (initialCapacity < 0)   // Too many elements, must back off
 109                 initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
 110         }
 111         elements = (E[]) new Object[initialCapacity];
 112     }
 113
 114     /**
 115      * Double the capacity of this deque.  Call only when full, i.e.,
 116      * when head and tail have wrapped around to become equal.
 117      */
 118     private void doubleCapacity() {
 119         assert head == tail;
 120         int p = head;
 121         int n = elements.length;
 122         int r = n - p; // number of elements to the right of p
 123         int newCapacity = n << 1;
 124         if (newCapacity < 0)
 125             throw new IllegalStateException("Sorry, deque too big");
 126         Object[] a = new Object[newCapacity];
 127         System.arraycopy(elements, p, a, 0, r);
 128         System.arraycopy(elements, 0, a, r, p);
 129         elements = (E[])a;
 130         head = 0;
 131         tail = n;
 132     }
 133
 134     /**
 135      * Copies the elements from our element array into the specified array,
 136      * in order (from first to last element in the deque).  It is assumed
 137      * that the array is large enough to hold all elements in the deque.
 138      *
 139      * @return its argument
 140      */
 141     private <T> T[] copyElements(T[] a) {
 142         if (head < tail) {
 143             System.arraycopy(elements, head, a, 0, size());
 144         } else if (head > tail) {
 145             int headPortionLen = elements.length - head;
 146             System.arraycopy(elements, head, a, 0, headPortionLen);
 147             System.arraycopy(elements, 0, a, headPortionLen, tail);
 148         }
 149         return a;
 150     }
 151
 152     /**
 153      * Constructs an empty array deque with an initial capacity
 154      * sufficient to hold 16 elements.
 155      */
 156     public ArrayDeque() {
 157         elements = (E[]) new Object[16];
 158     }
 159
 160     /**
 161      * Constructs an empty array deque with an initial capacity
 162      * sufficient to hold the specified number of elements.
 163      *
 164      * @param numElements  lower bound on initial capacity of the deque
 165      */
 166     public ArrayDeque(int numElements) {
 167         allocateElements(numElements);
 168     }
 169
 170     /**
 171      * Constructs a deque containing the elements of the specified
 172      * collection, in the order they are returned by the collection's
 173      * iterator.  (The first element returned by the collection's
 174      * iterator becomes the first element, or <i>front</i> of the
 175      * deque.)
 176      *
 177      * @param c the collection whose elements are to be placed into the deque
 178      * @throws NullPointerException if the specified collection is null
 179      */
 180     public ArrayDeque(Collection<? extends E> c) {
 181         allocateElements(c.size());
 182         addAll(c);
 183     }
 184
 185     // The main insertion and extraction methods are addFirst,
 186     // addLast, pollFirst, pollLast. The other methods are defined in
 187     // terms of these.
 188
 189     /**
 190      * Inserts the specified element at the front of this deque.
 191      *
 192      * @param e the element to add
 193      * @throws NullPointerException if the specified element is null
 194      */
 195     public void addFirst(E e) {
 196         if (e == null)
 197             throw new NullPointerException();
 198         elements[head = (head - 1) & (elements.length - 1)] = e;
 199         if (head == tail)
 200             doubleCapacity();
 201     }
 202
 203     /**
 204      * Inserts the specified element at the end of this deque.
 205      *
 206      * <p>This method is equivalent to {@link #add}.
 207      *
 208      * @param e the element to add
 209      * @throws NullPointerException if the specified element is null
 210      */
 211     public void addLast(E e) {
 212         if (e == null)
 213             throw new NullPointerException();
 214         elements[tail] = e;
 215         if ( (tail = (tail + 1) & (elements.length - 1)) == head)
 216             doubleCapacity();
 217     }
 218
 219     /**
 220      * Inserts the specified element at the front of this deque.
 221      *
 222      * @param e the element to add
 223      * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
 224      * @throws NullPointerException if the specified element is null
 225      */
 226     public boolean offerFirst(E e) {
 227         addFirst(e);
 228         return true;
 229     }
 230
 231     /**
 232      * Inserts the specified element at the end of this deque.
 233      *
 234      * @param e the element to add
 235      * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
 236      * @throws NullPointerException if the specified element is null
 237      */
 238     public boolean offerLast(E e) {
 239         addLast(e);
 240         return true;
 241     }
 242
 243     /**
 244      * @throws NoSuchElementException {@inheritDoc}
 245      */
 246     public E removeFirst() {
 247         E x = pollFirst();
 248         if (x == null)
 249             throw new NoSuchElementException();
 250         return x;
 251     }
 252
 253     /**
 254      * @throws NoSuchElementException {@inheritDoc}
 255      */
 256     public E removeLast() {
 257         E x = pollLast();
 258         if (x == null)
 259             throw new NoSuchElementException();
 260         return x;
 261     }
 262
 263     public E pollFirst() {
 264         int h = head;
 265         E result = elements[h]; // Element is null if deque empty
 266         if (result == null)
 267             return null;
 268         elements[h] = null;     // Must null out slot
 269         head = (h + 1) & (elements.length - 1);
 270         return result;
 271     }
 272
 273     public E pollLast() {
 274         int t = (tail - 1) & (elements.length - 1);
 275         E result = elements[t];
 276         if (result == null)
 277             return null;
 278         elements[t] = null;
 279         tail = t;
 280         return result;
 281     }
 282
 283     /**
 284      * @throws NoSuchElementException {@inheritDoc}
 285      */
 286     public E getFirst() {
 287         E x = elements[head];
 288         if (x == null)
 289             throw new NoSuchElementException();
 290         return x;
 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)
 299             throw new NoSuchElementException();
 300         return x;
 301     }
 302
 303     public E peekFirst() {
 304         return elements[head]; // elements[head] is null if deque empty
 305     }
 306
 307     public E peekLast() {
 308         return elements[(tail - 1) & (elements.length - 1)];
 309     }
 310
 311     /**
 312      * Removes the first occurrence of the specified element in this
 313      * deque (when traversing the deque from head to tail).
 314      * If the deque does not contain the element, it is unchanged.
 315      * More formally, removes the first element <tt>e</tt> such that
 316      * <tt>o.equals(e)</tt> (if such an element exists).
 317      * Returns <tt>true</tt> if this deque contained the specified element
 318      * (or equivalently, if this deque changed as a result of the call).
 319      *
 320      * @param o element to be removed from this deque, if present
 321      * @return <tt>true</tt> if the deque contained the specified element
 322      */
 323     public boolean removeFirstOccurrence(Object o) {
 324         if (o == null)
 325             return false;
 326         int mask = elements.length - 1;
 327         int i = head;
 328         E x;
 329         while ( (x = elements[i]) != null) {
 330             if (o.equals(x)) {
 331                 delete(i);
 332                 return true;
 333             }
 334             i = (i + 1) & mask;
 335         }
 336         return false;
 337     }
 338
 339     /**
 340      * Removes the last occurrence of the specified element in this
 341      * deque (when traversing the deque from head to tail).
 342      * If the deque does not contain the element, it is unchanged.
 343      * More formally, removes the last element <tt>e</tt> such that
 344      * <tt>o.equals(e)</tt> (if such an element exists).
 345      * Returns <tt>true</tt> if this deque contained the specified element
 346      * (or equivalently, if this deque changed as a result of the call).
 347      *
 348      * @param o element to be removed from this deque, if present
 349      * @return <tt>true</tt> if the deque contained the specified element
 350      */
 351     public boolean removeLastOccurrence(Object o) {
 352         if (o == null)
 353             return false;
 354         int mask = elements.length - 1;
 355         int i = (tail - 1) & mask;
 356         E x;
 357         while ( (x = elements[i]) != null) {
 358             if (o.equals(x)) {
 359                 delete(i);
 360                 return true;
 361             }
 362             i = (i - 1) & mask;
 363         }
 364         return false;
 365     }
 366
 367     // *** Queue methods ***
 368
 369     /**
 370      * Inserts the specified element at the end of this deque.
 371      *
 372      * <p>This method is equivalent to {@link #addLast}.
 373      *
 374      * @param e the element to add
 375      * @return <tt>true</tt> (as specified by {@link Collection#add})
 376      * @throws NullPointerException if the specified element is null
 377      */
 378     public boolean add(E e) {
 379         addLast(e);
 380         return true;
 381     }
 382
 383     /**
 384      * Inserts the specified element at the end of this deque.
 385      *
 386      * <p>This method is equivalent to {@link #offerLast}.
 387      *
 388      * @param e the element to add
 389      * @return <tt>true</tt> (as specified by {@link Queue#offer})
 390      * @throws NullPointerException if the specified element is null
 391      */
 392     public boolean offer(E e) {
 393         return offerLast(e);
 394     }
 395
 396     /**
 397      * Retrieves and removes the head of the queue represented by this deque.
 398      *
 399      * This method differs from {@link #poll poll} only in that it throws an
 400      * exception if this deque is empty.
 401      *
 402      * <p>This method is equivalent to {@link #removeFirst}.
 403      *
 404      * @return the head of the queue represented by this deque
 405      * @throws NoSuchElementException {@inheritDoc}
 406      */
 407     public E remove() {
 408         return removeFirst();
 409     }
 410
 411     /**
 412      * Retrieves and removes the head of the queue represented by this deque
 413      * (in other words, the first element of this deque), or returns
 414      * <tt>null</tt> if this deque is empty.
 415      *
 416      * <p>This method is equivalent to {@link #pollFirst}.
 417      *
 418      * @return the head of the queue represented by this deque, or
 419      *         <tt>null</tt> if this deque is empty
 420      */
 421     public E poll() {
 422         return pollFirst();
 423     }
 424
 425     /**
 426      * Retrieves, but does not remove, the head of the queue represented by
 427      * this deque.  This method differs from {@link #peek peek} only in
 428      * that it throws an exception if this deque is empty.
 429      *
 430      * <p>This method is equivalent to {@link #getFirst}.
 431      *
 432      * @return the head of the queue represented by this deque
 433      * @throws NoSuchElementException {@inheritDoc}
 434      */
 435     public E element() {
 436         return getFirst();
 437     }
 438
 439     /**
 440      * Retrieves, but does not remove, the head of the queue represented by
 441      * this deque, or returns <tt>null</tt> if this deque is empty.
 442      *
 443      * <p>This method is equivalent to {@link #peekFirst}.
 444      *
 445      * @return the head of the queue represented by this deque, or
 446      *         <tt>null</tt> if this deque is empty
 447      */
 448     public E peek() {
 449         return peekFirst();
 450     }
 451
 452     // *** Stack methods ***
 453
 454     /**
 455      * Pushes an element onto the stack represented by this deque.  In other
 456      * words, inserts the element at the front of this deque.
 457      *
 458      * <p>This method is equivalent to {@link #addFirst}.
 459      *
 460      * @param e the element to push
 461      * @throws NullPointerException if the specified element is null
 462      */
 463     public void push(E e) {
 464         addFirst(e);
 465     }
 466
 467     /**
 468      * Pops an element from the stack represented by this deque.  In other
 469      * words, removes and returns the first element of this deque.
 470      *
 471      * <p>This method is equivalent to {@link #removeFirst()}.
 472      *
 473      * @return the element at the front of this deque (which is the top
 474      *         of the stack represented by this deque)
 475      * @throws NoSuchElementException {@inheritDoc}
 476      */
 477     public E pop() {
 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
 492      * elements backwards or forwards in the array.
 493      *
 494      * <p>This method is called delete rather than remove to emphasize
 495      * that its semantics differ from those of {@link List#remove(int)}.
 496      *
 497      * @return true if elements moved backwards
 498      */
 499     private boolean delete(int i) {
 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         }
 536     }
 537
 538     // *** Collection Methods ***
 539
 540     /**
 541      * Returns the number of elements in this deque.
 542      *
 543      * @return the number of elements in this deque
 544      */
 545     public int size() {
 546         return (tail - head) & (elements.length - 1);
 547     }
 548
 549     /**
 550      * Returns <tt>true</tt> if this deque contains no elements.
 551      *
 552      * @return <tt>true</tt> if this deque contains no elements
 553      */
 554     public boolean isEmpty() {
 555         return head == tail;
 556     }
 557
 558     /**
 559      * Returns an iterator over the elements in this deque.  The elements
 560      * will be ordered from first (head) to last (tail).  This is the same
 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 iterator over the elements in this deque
 565      */
 566     public Iterator<E> iterator() {
 567         return new DeqIterator();
 568     }
 569
 570     public Iterator<E> descendingIterator() {
 571         return new DescendingIterator();
 572     }
 573
 574     private class DeqIterator implements Iterator<E> {
 575         /**
 576          * Index of element to be returned by subsequent call to next.
 577          */
 578         private int cursor = head;
 579
 580         /**
 581          * Tail recorded at construction (also in remove), to stop
 582          * iterator and also to check for comodification.
 583          */
 584         private int fence = tail;
 585
 586         /**
 587          * Index of element returned by most recent call to next.
 588          * Reset to -1 if element is deleted by a call to remove.
 589          */
 590         private int lastRet = -1;
 591
 592         public boolean hasNext() {
 593             return cursor != fence;
 594         }
 595
 596         public E next() {
 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 == null)
 603                 throw new ConcurrentModificationException();
 604             lastRet = cursor;
 605             cursor = (cursor + 1) & (elements.length - 1);
 606             return result;
 607         }
 608
 609         public void remove() {
 610             if (lastRet < 0)
 611                 throw new IllegalStateException();
 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;
 617         }
 618     }
 619
 620     private class DescendingIterator implements Iterator<E> {
 621         /*
 622          * This class is nearly a mirror-image of DeqIterator, using
 623          * tail instead of head for initial cursor, and head instead of
 624          * tail for fence.
 625          */
 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() {
 635             if (cursor == fence)
 636                 throw new NoSuchElementException();
 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;
 642             return result;
 643         }
 644
 645         public void remove() {
 646             if (lastRet < 0)
 647                 throw new IllegalStateException();
 648             if (!delete(lastRet)) {
 649                 cursor = (cursor + 1) & (elements.length - 1);
 650                 fence = head;
 651             }
 652             lastRet = -1;
 653         }
 654     }
 655
 656     /**
 657      * Returns <tt>true</tt> if this deque contains the specified element.
 658      * More formally, returns <tt>true</tt> if and only if this deque contains
 659      * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
 660      *
 661      * @param o object to be checked for containment in this deque
 662      * @return <tt>true</tt> if this deque contains the specified element
 663      */
 664     public boolean contains(Object o) {
 665         if (o == null)
 666             return false;
 667         int mask = elements.length - 1;
 668         int i = head;
 669         E x;
 670         while ( (x = elements[i]) != null) {
 671             if (o.equals(x))
 672                 return true;
 673             i = (i + 1) & mask;
 674         }
 675         return false;
 676     }
 677
 678     /**
 679      * Removes a single instance of the specified element from this deque.
 680      * If the deque does not contain the element, it is unchanged.
 681      * More formally, removes the first element <tt>e</tt> such that
 682      * <tt>o.equals(e)</tt> (if such an element exists).
 683      * Returns <tt>true</tt> if this deque contained the specified element
 684      * (or equivalently, if this deque changed as a result of the call).
 685      *
 686      * <p>This method is equivalent to {@link #removeFirstOccurrence}.
 687      *
 688      * @param o element to be removed from this deque, if present
 689      * @return <tt>true</tt> if this deque contained the specified element
 690      */
 691     public boolean remove(Object o) {
 692         return removeFirstOccurrence(o);
 693     }
 694
 695     /**
 696      * Removes all of the elements from this deque.
 697      * The deque will be empty after this call returns.
 698      */
 699     public void clear() {
 700         int h = head;
 701         int t = tail;
 702         if (h != t) { // clear all cells
 703             head = tail = 0;
 704             int i = h;
 705             int mask = elements.length - 1;
 706             do {
 707                 elements[i] = null;
 708                 i = (i + 1) & mask;
 709             } while (i != t);
 710         }
 711     }
 712
 713     /**
 714      * Returns an array containing all of the elements in this deque
 715      * in proper sequence (from first to last element).
 716      *
 717      * <p>The returned array will be "safe" in that no references to it are
 718      * maintained by this deque.  (In other words, this method must allocate
 719      * a new array).  The caller is thus free to modify the returned array.
 720      *
 721      * <p>This method acts as bridge between array-based and collection-based
 722      * APIs.
 723      *
 724      * @return an array containing all of the elements in this deque
 725      */
 726     public Object[] toArray() {
 727         return copyElements(new Object[size()]);
 728     }
 729
 730     /**
 731      * Returns an array containing all of the elements in this deque in
 732      * proper sequence (from first to last element); the runtime type of the
 733      * returned array is that of the specified array.  If the deque fits in
 734      * the specified array, it is returned therein.  Otherwise, a new array
 735      * is allocated with the runtime type of the specified array and the
 736      * size of this deque.
 737      *
 738      * <p>If this deque fits in the specified array with room to spare
 739      * (i.e., the array has more elements than this deque), the element in
 740      * the array immediately following the end of the deque is set to
 741      * <tt>null</tt>.
 742      *
 743      * <p>Like the {@link #toArray()} method, this method acts as bridge between
 744      * array-based and collection-based APIs.  Further, this method allows
 745      * precise control over the runtime type of the output array, and may,
 746      * under certain circumstances, be used to save allocation costs.
 747      *
 748      * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
 749      * The following code can be used to dump the deque into a newly
 750      * allocated array of <tt>String</tt>:
 751      *
 752      * <pre>
 753      *     String[] y = x.toArray(new String[0]);</pre>
 754      *
 755      * Note that <tt>toArray(new Object[0])</tt> is identical in function to
 756      * <tt>toArray()</tt>.
 757      *
 758      * @param a the array into which the elements of the deque are to
 759      *          be stored, if it is big enough; otherwise, a new array of the
 760      *          same runtime type is allocated for this purpose
 761      * @return an array containing all of the elements in this deque
 762      * @throws ArrayStoreException if the runtime type of the specified array
 763      *         is not a supertype of the runtime type of every element in
 764      *         this deque
 765      * @throws NullPointerException if the specified array is null
 766      */
 767     public <T> T[] toArray(T[] a) {
 768         int size = size();
 769         if (a.length < size)
 770             a = (T[])java.lang.reflect.Array.newInstance(
 771                     a.getClass().getComponentType(), size);
 772         copyElements(a);
 773         if (a.length > size)
 774             a[size] = null;
 775         return a;
 776     }
 777
 778     // *** Object methods ***
 779
 780     /**
 781      * Returns a copy of this deque.
 782      *
 783      * @return a copy of this deque
 784      */
 785     public ArrayDeque<E> clone() {
 786         try {
 787             ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
 788             // Classpath local: we don't have Arrays.copyOf yet.
 789             // result.elements = Arrays.copyOf(elements, elements.length);
 790             result.elements = elements.clone();
 791             return result;
 792
 793         } catch (CloneNotSupportedException e) {
 794             throw new AssertionError();
 795         }
 796     }
 797
 798     /**
 799      * Appease the serialization gods.
 800      */
 801     private static final long serialVersionUID = 2340985798034038923L;
 802
 803     /**
 804      * Serialize this deque.
 805      *
 806      * @serialData The current size (<tt>int</tt>) of the deque,
 807      * followed by all of its elements (each an object reference) in
 808      * first-to-last order.
 809      */
 810     private void writeObject(ObjectOutputStream s) throws IOException {
 811         s.defaultWriteObject();
 812
 813         // Write out size
 814         s.writeInt(size());
 815
 816         // Write out elements in order.
 817         int mask = elements.length - 1;
 818         for (int i = head; i != tail; i = (i + 1) & mask)
 819             s.writeObject(elements[i]);
 820     }
 821
 822     /**
 823      * Deserialize this deque.
 824      */
 825     private void readObject(ObjectInputStream s)
 826             throws IOException, ClassNotFoundException {
 827         s.defaultReadObject();
 828
 829         // Read in size and allocate array
 830         int size = s.readInt();
 831         allocateElements(size);
 832         head = 0;
 833         tail = size;
 834
 835         // Read in all elements in the proper order.
 836         for (int i = 0; i < size; i++)
 837             elements[i] = (E)s.readObject();
 838     }
 839 }