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