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