1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.  Oracle designates this
   7  * particular file as subject to the "Classpath" exception as provided
   8  * by Oracle in the LICENSE file that accompanied this code.
   9  *
  10  * This code is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * version 2 for more details (a copy is included in the LICENSE file that
  14  * accompanied this code).
  15  *
  16  * You should have received a copy of the GNU General Public License version
  17  * 2 along with this work; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  19  *
  20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  21  * or visit www.oracle.com if you need additional information or have any
  22  * questions.
  23  */
  24 
  25 /*
  26  * This file is available under and governed by the GNU General Public
  27  * License version 2 only, as published by the Free Software Foundation.
  28  * However, the following notice accompanied the original version of this
  29  * file:
  30  *
  31  * Written by Josh Bloch of Google Inc. and released to the public domain,
  32  * as explained at http://creativecommons.org/publicdomain/zero/1.0/.
  33  */
  34 
  35 package java.util;
  36 import java.io.*;
  37 
  38 /**
  39  * Resizable-array implementation of the {@link Deque} interface.  Array
  40  * deques have no capacity restrictions; they grow as necessary to support
  41  * usage.  They are not thread-safe; in the absence of external
  42  * synchronization, they do not support concurrent access by multiple threads.
  43  * Null elements are prohibited.  This class is likely to be faster than
  44  * {@link Stack} when used as a stack, and faster than {@link LinkedList}
  45  * when used as a queue.
  46  *
  47  * <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
  48  * Exceptions include {@link #remove(Object) remove}, {@link
  49  * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
  50  * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
  51  * iterator.remove()}, and the bulk operations, all of which run in linear
  52  * time.
  53  *
  54  * <p>The iterators returned by this class's <tt>iterator</tt> method are
  55  * <i>fail-fast</i>: If the deque is modified at any time after the iterator
  56  * is created, in any way except through the iterator's own <tt>remove</tt>
  57  * method, the iterator will generally throw a {@link
  58  * ConcurrentModificationException}.  Thus, in the face of concurrent
  59  * modification, the iterator fails quickly and cleanly, rather than risking
  60  * arbitrary, non-deterministic behavior at an undetermined time in the
  61  * future.
  62  *
  63  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  64  * as it is, generally speaking, impossible to make any hard guarantees in the
  65  * presence of unsynchronized concurrent modification.  Fail-fast iterators
  66  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
  67  * Therefore, it would be wrong to write a program that depended on this
  68  * exception for its correctness: <i>the fail-fast behavior of iterators
  69  * should be used only to detect bugs.</i>
  70  *
  71  * <p>This class and its iterator implement all of the
  72  * <em>optional</em> methods of the {@link Collection} and {@link
  73  * Iterator} interfaces.
  74  *
  75  * <p>This class is a member of the
  76  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  77  * Java Collections Framework</a>.
  78  *
  79  * @author  Josh Bloch and Doug Lea
  80  * @since   1.6
  81  * @param <E> the type of elements held in this collection
  82  */
  83 public class ArrayDeque<E> extends AbstractCollection<E>
  84                            implements Deque<E>, Cloneable, Serializable
  85 {
  86     /**
  87      * The array in which the elements of the deque are stored.
  88      * The capacity of the deque is the length of this array, which is
  89      * always a power of two. The array is never allowed to become
  90      * full, except transiently within an addX method where it is
  91      * resized (see doubleCapacity) immediately upon becoming full,
  92      * thus avoiding head and tail wrapping around to equal each
  93      * other.  We also guarantee that all array cells not holding
  94      * deque elements are always null.
  95      */
  96     private transient E[] elements;
  97 
  98     /**
  99      * The index of the element at the head of the deque (which is the
 100      * element that would be removed by remove() or pop()); or an
 101      * arbitrary number equal to tail if the deque is empty.
 102      */
 103     private transient int head;
 104 
 105     /**
 106      * The index at which the next element would be added to the tail
 107      * of the deque (via addLast(E), add(E), or push(E)).
 108      */
 109     private transient int tail;
 110 
 111     /**
 112      * The minimum capacity that we'll use for a newly created deque.
 113      * Must be a power of 2.
 114      */
 115     private static final int MIN_INITIAL_CAPACITY = 8;
 116 
 117     // ******  Array allocation and resizing utilities ******
 118 
 119     /**
 120      * Allocate empty array to hold the given number of elements.
 121      *
 122      * @param numElements  the number of elements to hold
 123      */

 124     private void allocateElements(int numElements) {
 125         int initialCapacity = MIN_INITIAL_CAPACITY;
 126         // Find the best power of two to hold elements.
 127         // Tests "<=" because arrays aren't kept full.
 128         if (numElements >= initialCapacity) {
 129             initialCapacity = numElements;
 130             initialCapacity |= (initialCapacity >>>  1);
 131             initialCapacity |= (initialCapacity >>>  2);
 132             initialCapacity |= (initialCapacity >>>  4);
 133             initialCapacity |= (initialCapacity >>>  8);
 134             initialCapacity |= (initialCapacity >>> 16);
 135             initialCapacity++;
 136 
 137             if (initialCapacity < 0)   // Too many elements, must back off
 138                 initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
 139         }
 140         elements = (E[]) new Object[initialCapacity];
 141     }
 142 
 143     /**
 144      * Double the capacity of this deque.  Call only when full, i.e.,
 145      * when head and tail have wrapped around to become equal.
 146      */
 147     private void doubleCapacity() {
 148         assert head == tail;
 149         int p = head;
 150         int n = elements.length;
 151         int r = n - p; // number of elements to the right of p
 152         int newCapacity = n << 1;
 153         if (newCapacity < 0)
 154             throw new IllegalStateException("Sorry, deque too big");
 155         Object[] a = new Object[newCapacity];

 156         System.arraycopy(elements, p, a, 0, r);
 157         System.arraycopy(elements, 0, a, r, p);
 158         elements = (E[])a;
 159         head = 0;
 160         tail = n;
 161     }
 162 
 163     /**
 164      * Copies the elements from our element array into the specified array,
 165      * in order (from first to last element in the deque).  It is assumed
 166      * that the array is large enough to hold all elements in the deque.
 167      *
 168      * @return its argument
 169      */
 170     private <T> T[] copyElements(T[] a) {
 171         if (head < tail) {
 172             System.arraycopy(elements, head, a, 0, size());
 173         } else if (head > tail) {
 174             int headPortionLen = elements.length - head;
 175             System.arraycopy(elements, head, a, 0, headPortionLen);
 176             System.arraycopy(elements, 0, a, headPortionLen, tail);
 177         }
 178         return a;
 179     }
 180 
 181     /**
 182      * Constructs an empty array deque with an initial capacity
 183      * sufficient to hold 16 elements.
 184      */

 185     public ArrayDeque() {
 186         elements = (E[]) new Object[16];
 187     }
 188 
 189     /**
 190      * Constructs an empty array deque with an initial capacity
 191      * sufficient to hold the specified number of elements.
 192      *
 193      * @param numElements  lower bound on initial capacity of the deque
 194      */
 195     public ArrayDeque(int numElements) {
 196         allocateElements(numElements);
 197     }
 198 
 199     /**
 200      * Constructs a deque containing the elements of the specified
 201      * collection, in the order they are returned by the collection's
 202      * iterator.  (The first element returned by the collection's
 203      * iterator becomes the first element, or <i>front</i> of the
 204      * deque.)
 205      *
 206      * @param c the collection whose elements are to be placed into the deque
 207      * @throws NullPointerException if the specified collection is null
 208      */
 209     public ArrayDeque(Collection<? extends E> c) {
 210         allocateElements(c.size());
 211         addAll(c);
 212     }
 213 
 214     // The main insertion and extraction methods are addFirst,
 215     // addLast, pollFirst, pollLast. The other methods are defined in
 216     // terms of these.
 217 
 218     /**
 219      * Inserts the specified element at the front of this deque.
 220      *
 221      * @param e the element to add
 222      * @throws NullPointerException if the specified element is null
 223      */
 224     public void addFirst(E e) {
 225         if (e == null)
 226             throw new NullPointerException();
 227         elements[head = (head - 1) & (elements.length - 1)] = e;
 228         if (head == tail)
 229             doubleCapacity();
 230     }
 231 
 232     /**
 233      * Inserts the specified element at the end of this deque.
 234      *
 235      * <p>This method is equivalent to {@link #add}.
 236      *
 237      * @param e the element to add
 238      * @throws NullPointerException if the specified element is null
 239      */
 240     public void addLast(E e) {
 241         if (e == null)
 242             throw new NullPointerException();
 243         elements[tail] = e;
 244         if ( (tail = (tail + 1) & (elements.length - 1)) == head)
 245             doubleCapacity();
 246     }
 247 
 248     /**
 249      * Inserts the specified element at the front of this deque.
 250      *
 251      * @param e the element to add
 252      * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
 253      * @throws NullPointerException if the specified element is null
 254      */
 255     public boolean offerFirst(E e) {
 256         addFirst(e);
 257         return true;
 258     }
 259 
 260     /**
 261      * Inserts the specified element at the end of this deque.
 262      *
 263      * @param e the element to add
 264      * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
 265      * @throws NullPointerException if the specified element is null
 266      */
 267     public boolean offerLast(E e) {
 268         addLast(e);
 269         return true;
 270     }
 271 
 272     /**
 273      * @throws NoSuchElementException {@inheritDoc}
 274      */
 275     public E removeFirst() {
 276         E x = pollFirst();
 277         if (x == null)
 278             throw new NoSuchElementException();
 279         return x;
 280     }
 281 
 282     /**
 283      * @throws NoSuchElementException {@inheritDoc}
 284      */
 285     public E removeLast() {
 286         E x = pollLast();
 287         if (x == null)
 288             throw new NoSuchElementException();
 289         return x;
 290     }
 291 
 292     public E pollFirst() {
 293         int h = head;
 294         E result = elements[h]; // Element is null if deque empty
 295         if (result == null)
 296             return null;
 297         elements[h] = null;     // Must null out slot
 298         head = (h + 1) & (elements.length - 1);
 299         return result;
 300     }
 301 
 302     public E pollLast() {
 303         int t = (tail - 1) & (elements.length - 1);
 304         E result = elements[t];
 305         if (result == null)
 306             return null;
 307         elements[t] = null;
 308         tail = t;
 309         return result;
 310     }
 311 
 312     /**
 313      * @throws NoSuchElementException {@inheritDoc}
 314      */
 315     public E getFirst() {
 316         E x = elements[head];
 317         if (x == null)
 318             throw new NoSuchElementException();
 319         return x;
 320     }
 321 
 322     /**
 323      * @throws NoSuchElementException {@inheritDoc}
 324      */
 325     public E getLast() {
 326         E x = elements[(tail - 1) & (elements.length - 1)];
 327         if (x == null)
 328             throw new NoSuchElementException();
 329         return x;
 330     }
 331 
 332     public E peekFirst() {
 333         return elements[head]; // elements[head] is null if deque empty
 334     }
 335 
 336     public E peekLast() {
 337         return elements[(tail - 1) & (elements.length - 1)];
 338     }
 339 
 340     /**
 341      * Removes the first occurrence of the specified element in this
 342      * deque (when traversing the deque from head to tail).
 343      * If the deque does not contain the element, it is unchanged.
 344      * More formally, removes the first element <tt>e</tt> such that
 345      * <tt>o.equals(e)</tt> (if such an element exists).
 346      * Returns <tt>true</tt> if this deque contained the specified element
 347      * (or equivalently, if this deque changed as a result of the call).
 348      *
 349      * @param o element to be removed from this deque, if present
 350      * @return <tt>true</tt> if the deque contained the specified element
 351      */
 352     public boolean removeFirstOccurrence(Object o) {
 353         if (o == null)
 354             return false;
 355         int mask = elements.length - 1;
 356         int i = head;
 357         E x;
 358         while ( (x = elements[i]) != null) {
 359             if (o.equals(x)) {
 360                 delete(i);
 361                 return true;
 362             }
 363             i = (i + 1) & mask;
 364         }
 365         return false;
 366     }
 367 
 368     /**
 369      * Removes the last occurrence of the specified element in this
 370      * deque (when traversing the deque from head to tail).
 371      * If the deque does not contain the element, it is unchanged.
 372      * More formally, removes the last element <tt>e</tt> such that
 373      * <tt>o.equals(e)</tt> (if such an element exists).
 374      * Returns <tt>true</tt> if this deque contained the specified element
 375      * (or equivalently, if this deque changed as a result of the call).
 376      *
 377      * @param o element to be removed from this deque, if present
 378      * @return <tt>true</tt> if the deque contained the specified element
 379      */
 380     public boolean removeLastOccurrence(Object o) {
 381         if (o == null)
 382             return false;
 383         int mask = elements.length - 1;
 384         int i = (tail - 1) & mask;
 385         E x;
 386         while ( (x = elements[i]) != null) {
 387             if (o.equals(x)) {
 388                 delete(i);
 389                 return true;
 390             }
 391             i = (i - 1) & mask;
 392         }
 393         return false;
 394     }
 395 
 396     // *** Queue methods ***
 397 
 398     /**
 399      * Inserts the specified element at the end of this deque.
 400      *
 401      * <p>This method is equivalent to {@link #addLast}.
 402      *
 403      * @param e the element to add
 404      * @return <tt>true</tt> (as specified by {@link Collection#add})
 405      * @throws NullPointerException if the specified element is null
 406      */
 407     public boolean add(E e) {
 408         addLast(e);
 409         return true;
 410     }
 411 
 412     /**
 413      * Inserts the specified element at the end of this deque.
 414      *
 415      * <p>This method is equivalent to {@link #offerLast}.
 416      *
 417      * @param e the element to add
 418      * @return <tt>true</tt> (as specified by {@link Queue#offer})
 419      * @throws NullPointerException if the specified element is null
 420      */
 421     public boolean offer(E e) {
 422         return offerLast(e);
 423     }
 424 
 425     /**
 426      * Retrieves and removes the head of the queue represented by this deque.
 427      *
 428      * This method differs from {@link #poll poll} only in that it throws an
 429      * exception if this deque is empty.
 430      *
 431      * <p>This method is equivalent to {@link #removeFirst}.
 432      *
 433      * @return the head of the queue represented by this deque
 434      * @throws NoSuchElementException {@inheritDoc}
 435      */
 436     public E remove() {
 437         return removeFirst();
 438     }
 439 
 440     /**
 441      * Retrieves and removes the head of the queue represented by this deque
 442      * (in other words, the first element of this deque), or returns
 443      * <tt>null</tt> if this deque is empty.
 444      *
 445      * <p>This method is equivalent to {@link #pollFirst}.
 446      *
 447      * @return the head of the queue represented by this deque, or
 448      *         <tt>null</tt> if this deque is empty
 449      */
 450     public E poll() {
 451         return pollFirst();
 452     }
 453 
 454     /**
 455      * Retrieves, but does not remove, the head of the queue represented by
 456      * this deque.  This method differs from {@link #peek peek} only in
 457      * that it throws an exception if this deque is empty.
 458      *
 459      * <p>This method is equivalent to {@link #getFirst}.
 460      *
 461      * @return the head of the queue represented by this deque
 462      * @throws NoSuchElementException {@inheritDoc}
 463      */
 464     public E element() {
 465         return getFirst();
 466     }
 467 
 468     /**
 469      * Retrieves, but does not remove, the head of the queue represented by
 470      * this deque, or returns <tt>null</tt> if this deque is empty.
 471      *
 472      * <p>This method is equivalent to {@link #peekFirst}.
 473      *
 474      * @return the head of the queue represented by this deque, or
 475      *         <tt>null</tt> if this deque is empty
 476      */
 477     public E peek() {
 478         return peekFirst();
 479     }
 480 
 481     // *** Stack methods ***
 482 
 483     /**
 484      * Pushes an element onto the stack represented by this deque.  In other
 485      * words, inserts the element at the front of this deque.
 486      *
 487      * <p>This method is equivalent to {@link #addFirst}.
 488      *
 489      * @param e the element to push
 490      * @throws NullPointerException if the specified element is null
 491      */
 492     public void push(E e) {
 493         addFirst(e);
 494     }
 495 
 496     /**
 497      * Pops an element from the stack represented by this deque.  In other
 498      * words, removes and returns the first element of this deque.
 499      *
 500      * <p>This method is equivalent to {@link #removeFirst()}.
 501      *
 502      * @return the element at the front of this deque (which is the top
 503      *         of the stack represented by this deque)
 504      * @throws NoSuchElementException {@inheritDoc}
 505      */
 506     public E pop() {
 507         return removeFirst();
 508     }
 509 
 510     private void checkInvariants() {
 511         assert elements[tail] == null;
 512         assert head == tail ? elements[head] == null :
 513             (elements[head] != null &&
 514              elements[(tail - 1) & (elements.length - 1)] != null);
 515         assert elements[(head - 1) & (elements.length - 1)] == null;
 516     }
 517 
 518     /**
 519      * Removes the element at the specified position in the elements array,
 520      * adjusting head and tail as necessary.  This can result in motion of
 521      * elements backwards or forwards in the array.
 522      *
 523      * <p>This method is called delete rather than remove to emphasize
 524      * that its semantics differ from those of {@link List#remove(int)}.
 525      *
 526      * @return true if elements moved backwards
 527      */
 528     private boolean delete(int i) {
 529         checkInvariants();
 530         final E[] elements = this.elements;
 531         final int mask = elements.length - 1;
 532         final int h = head;
 533         final int t = tail;
 534         final int front = (i - h) & mask;
 535         final int back  = (t - i) & mask;
 536 
 537         // Invariant: head <= i < tail mod circularity
 538         if (front >= ((t - h) & mask))
 539             throw new ConcurrentModificationException();
 540 
 541         // Optimize for least element motion
 542         if (front < back) {
 543             if (h <= i) {
 544                 System.arraycopy(elements, h, elements, h + 1, front);
 545             } else { // Wrap around
 546                 System.arraycopy(elements, 0, elements, 1, i);
 547                 elements[0] = elements[mask];
 548                 System.arraycopy(elements, h, elements, h + 1, mask - h);
 549             }
 550             elements[h] = null;
 551             head = (h + 1) & mask;
 552             return false;
 553         } else {
 554             if (i < t) { // Copy the null tail as well
 555                 System.arraycopy(elements, i + 1, elements, i, back);
 556                 tail = t - 1;
 557             } else { // Wrap around
 558                 System.arraycopy(elements, i + 1, elements, i, mask - i);
 559                 elements[mask] = elements[0];
 560                 System.arraycopy(elements, 1, elements, 0, t);
 561                 tail = (t - 1) & mask;
 562             }
 563             return true;
 564         }
 565     }
 566 
 567     // *** Collection Methods ***
 568 
 569     /**
 570      * Returns the number of elements in this deque.
 571      *
 572      * @return the number of elements in this deque
 573      */
 574     public int size() {
 575         return (tail - head) & (elements.length - 1);
 576     }
 577 
 578     /**
 579      * Returns <tt>true</tt> if this deque contains no elements.
 580      *
 581      * @return <tt>true</tt> if this deque contains no elements
 582      */
 583     public boolean isEmpty() {
 584         return head == tail;
 585     }
 586 
 587     /**
 588      * Returns an iterator over the elements in this deque.  The elements
 589      * will be ordered from first (head) to last (tail).  This is the same
 590      * order that elements would be dequeued (via successive calls to
 591      * {@link #remove} or popped (via successive calls to {@link #pop}).
 592      *
 593      * @return an iterator over the elements in this deque
 594      */
 595     public Iterator<E> iterator() {
 596         return new DeqIterator();
 597     }
 598 
 599     public Iterator<E> descendingIterator() {
 600         return new DescendingIterator();
 601     }
 602 
 603     private class DeqIterator implements Iterator<E> {
 604         /**
 605          * Index of element to be returned by subsequent call to next.
 606          */
 607         private int cursor = head;
 608 
 609         /**
 610          * Tail recorded at construction (also in remove), to stop
 611          * iterator and also to check for comodification.
 612          */
 613         private int fence = tail;
 614 
 615         /**
 616          * Index of element returned by most recent call to next.
 617          * Reset to -1 if element is deleted by a call to remove.
 618          */
 619         private int lastRet = -1;
 620 
 621         public boolean hasNext() {
 622             return cursor != fence;
 623         }
 624 
 625         public E next() {
 626             if (cursor == fence)
 627                 throw new NoSuchElementException();
 628             E result = elements[cursor];
 629             // This check doesn't catch all possible comodifications,
 630             // but does catch the ones that corrupt traversal
 631             if (tail != fence || result == null)
 632                 throw new ConcurrentModificationException();
 633             lastRet = cursor;
 634             cursor = (cursor + 1) & (elements.length - 1);
 635             return result;
 636         }
 637 
 638         public void remove() {
 639             if (lastRet < 0)
 640                 throw new IllegalStateException();
 641             if (delete(lastRet)) { // if left-shifted, undo increment in next()
 642                 cursor = (cursor - 1) & (elements.length - 1);
 643                 fence = tail;
 644             }
 645             lastRet = -1;
 646         }
 647     }
 648 
 649     private class DescendingIterator implements Iterator<E> {
 650         /*
 651          * This class is nearly a mirror-image of DeqIterator, using
 652          * tail instead of head for initial cursor, and head instead of
 653          * tail for fence.
 654          */
 655         private int cursor = tail;
 656         private int fence = head;
 657         private int lastRet = -1;
 658 
 659         public boolean hasNext() {
 660             return cursor != fence;
 661         }
 662 
 663         public E next() {
 664             if (cursor == fence)
 665                 throw new NoSuchElementException();
 666             cursor = (cursor - 1) & (elements.length - 1);
 667             E result = elements[cursor];
 668             if (head != fence || result == null)
 669                 throw new ConcurrentModificationException();
 670             lastRet = cursor;
 671             return result;
 672         }
 673 
 674         public void remove() {
 675             if (lastRet < 0)
 676                 throw new IllegalStateException();
 677             if (!delete(lastRet)) {
 678                 cursor = (cursor + 1) & (elements.length - 1);
 679                 fence = head;
 680             }
 681             lastRet = -1;
 682         }
 683     }
 684 
 685     /**
 686      * Returns <tt>true</tt> if this deque contains the specified element.
 687      * More formally, returns <tt>true</tt> if and only if this deque contains
 688      * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
 689      *
 690      * @param o object to be checked for containment in this deque
 691      * @return <tt>true</tt> if this deque contains the specified element
 692      */
 693     public boolean contains(Object o) {
 694         if (o == null)
 695             return false;
 696         int mask = elements.length - 1;
 697         int i = head;
 698         E x;
 699         while ( (x = elements[i]) != null) {
 700             if (o.equals(x))
 701                 return true;
 702             i = (i + 1) & mask;
 703         }
 704         return false;
 705     }
 706 
 707     /**
 708      * Removes a single instance of the specified element from this deque.
 709      * If the deque does not contain the element, it is unchanged.
 710      * More formally, removes the first element <tt>e</tt> such that
 711      * <tt>o.equals(e)</tt> (if such an element exists).
 712      * Returns <tt>true</tt> if this deque contained the specified element
 713      * (or equivalently, if this deque changed as a result of the call).
 714      *
 715      * <p>This method is equivalent to {@link #removeFirstOccurrence}.
 716      *
 717      * @param o element to be removed from this deque, if present
 718      * @return <tt>true</tt> if this deque contained the specified element
 719      */
 720     public boolean remove(Object o) {
 721         return removeFirstOccurrence(o);
 722     }
 723 
 724     /**
 725      * Removes all of the elements from this deque.
 726      * The deque will be empty after this call returns.
 727      */
 728     public void clear() {
 729         int h = head;
 730         int t = tail;
 731         if (h != t) { // clear all cells
 732             head = tail = 0;
 733             int i = h;
 734             int mask = elements.length - 1;
 735             do {
 736                 elements[i] = null;
 737                 i = (i + 1) & mask;
 738             } while (i != t);
 739         }
 740     }
 741 
 742     /**
 743      * Returns an array containing all of the elements in this deque
 744      * in proper sequence (from first to last element).
 745      *
 746      * <p>The returned array will be "safe" in that no references to it are
 747      * maintained by this deque.  (In other words, this method must allocate
 748      * a new array).  The caller is thus free to modify the returned array.
 749      *
 750      * <p>This method acts as bridge between array-based and collection-based
 751      * APIs.
 752      *
 753      * @return an array containing all of the elements in this deque
 754      */
 755     public Object[] toArray() {
 756         return copyElements(new Object[size()]);
 757     }
 758 
 759     /**
 760      * Returns an array containing all of the elements in this deque in
 761      * proper sequence (from first to last element); the runtime type of the
 762      * returned array is that of the specified array.  If the deque fits in
 763      * the specified array, it is returned therein.  Otherwise, a new array
 764      * is allocated with the runtime type of the specified array and the
 765      * size of this deque.
 766      *
 767      * <p>If this deque fits in the specified array with room to spare
 768      * (i.e., the array has more elements than this deque), the element in
 769      * the array immediately following the end of the deque is set to
 770      * <tt>null</tt>.
 771      *
 772      * <p>Like the {@link #toArray()} method, this method acts as bridge between
 773      * array-based and collection-based APIs.  Further, this method allows
 774      * precise control over the runtime type of the output array, and may,
 775      * under certain circumstances, be used to save allocation costs.
 776      *
 777      * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
 778      * The following code can be used to dump the deque into a newly
 779      * allocated array of <tt>String</tt>:
 780      *
 781      * <pre>
 782      *     String[] y = x.toArray(new String[0]);</pre>
 783      *
 784      * Note that <tt>toArray(new Object[0])</tt> is identical in function to
 785      * <tt>toArray()</tt>.
 786      *
 787      * @param a the array into which the elements of the deque are to
 788      *          be stored, if it is big enough; otherwise, a new array of the
 789      *          same runtime type is allocated for this purpose
 790      * @return an array containing all of the elements in this deque
 791      * @throws ArrayStoreException if the runtime type of the specified array
 792      *         is not a supertype of the runtime type of every element in
 793      *         this deque
 794      * @throws NullPointerException if the specified array is null
 795      */

 796     public <T> T[] toArray(T[] a) {
 797         int size = size();
 798         if (a.length < size)
 799             a = (T[])java.lang.reflect.Array.newInstance(
 800                     a.getClass().getComponentType(), size);
 801         copyElements(a);
 802         if (a.length > size)
 803             a[size] = null;
 804         return a;
 805     }
 806 
 807     // *** Object methods ***
 808 
 809     /**
 810      * Returns a copy of this deque.
 811      *
 812      * @return a copy of this deque
 813      */
 814     public ArrayDeque<E> clone() {
 815         try {
 816             @SuppressWarnings("unchecked")
 817                 ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
 818             result.elements = Arrays.copyOf(elements, elements.length);
 819             return result;
 820 
 821         } catch (CloneNotSupportedException e) {
 822             throw new AssertionError();
 823         }
 824     }
 825 
 826     /**
 827      * Appease the serialization gods.
 828      */
 829     private static final long serialVersionUID = 2340985798034038923L;
 830 
 831     /**
 832      * Serialize this deque.
 833      *
 834      * @serialData The current size (<tt>int</tt>) of the deque,
 835      * followed by all of its elements (each an object reference) in
 836      * first-to-last order.
 837      */
 838     private void writeObject(ObjectOutputStream s) throws IOException {
 839         s.defaultWriteObject();
 840 
 841         // Write out size
 842         s.writeInt(size());
 843 
 844         // Write out elements in order.
 845         int mask = elements.length - 1;
 846         for (int i = head; i != tail; i = (i + 1) & mask)
 847             s.writeObject(elements[i]);
 848     }
 849 
 850     /**
 851      * Deserialize this deque.
 852      */
 853     @SuppressWarnings("unchecked")
 854     private void readObject(ObjectInputStream s)
 855             throws IOException, ClassNotFoundException {
 856         s.defaultReadObject();
 857 
 858         // Read in size and allocate array
 859         int size = s.readInt();
 860         allocateElements(size);
 861         head = 0;
 862         tail = size;
 863 
 864         // Read in all elements in the proper order.
 865         for (int i = 0; i < size; i++)
 866             elements[i] = (E)s.readObject();
 867     }
 868 }
--- EOF ---