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 8 // BEGIN android-note 9 // removed link to collections framework docs 10 // END android-note 11 12 import java.io.*; 13 14 /** 15 * Resizable-array implementation of the {@link Deque} interface. Array 16 * deques have no capacity restrictions; they grow as necessary to support 17 * usage. They are not thread-safe; in the absence of external 18 * synchronization, they do not support concurrent access by multiple threads. 19 * Null elements are prohibited. This class is likely to be faster than 20 * {@link Stack} when used as a stack, and faster than {@link LinkedList} 21 * when used as a queue. 22 * 23 * <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time. 24 * Exceptions include {@link #remove(Object) remove}, {@link 25 * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence 26 * removeLastOccurrence}, {@link #contains contains}, {@link #iterator 27 * iterator.remove()}, and the bulk operations, all of which run in linear 28 * time. 29 * 30 * <p>The iterators returned by this class's <tt>iterator</tt> method are 31 * <i>fail-fast</i>: If the deque is modified at any time after the iterator 32 * is created, in any way except through the iterator's own <tt>remove</tt> 33 * method, the iterator will generally throw a {@link 34 * ConcurrentModificationException}. Thus, in the face of concurrent 35 * modification, the iterator fails quickly and cleanly, rather than risking 36 * arbitrary, non-deterministic behavior at an undetermined time in the 37 * future. 38 * 39 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 40 * as it is, generally speaking, impossible to make any hard guarantees in the 41 * presence of unsynchronized concurrent modification. Fail-fast iterators 42 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 43 * Therefore, it would be wrong to write a program that depended on this 44 * exception for its correctness: <i>the fail-fast behavior of iterators 45 * should be used only to detect bugs.</i> 46 * 47 * <p>This class and its iterator implement all of the 48 * <em>optional</em> methods of the {@link Collection} and {@link 49 * Iterator} interfaces. 50 * 51 * @author Josh Bloch and Doug Lea 52 * @since 1.6 53 * @param <E> the type of elements held in this collection 54 */ 55 public class ArrayDeque<E> extends AbstractCollection<E> 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 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 */ allocateElements(int numElements)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 */ doubleCapacity()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 */ copyElements(T[] a)142 private <T> T[] copyElements(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 */ ArrayDeque()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 */ ArrayDeque(int numElements)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 */ ArrayDeque(Collection<? extends E> c)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 */ addFirst(E e)196 public void addFirst(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 */ addLast(E e)212 public void addLast(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 */ offerFirst(E e)227 public boolean offerFirst(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 */ offerLast(E e)239 public boolean offerLast(E e) { 240 addLast(e); 241 return true; 242 } 243 244 /** 245 * @throws NoSuchElementException {@inheritDoc} 246 */ removeFirst()247 public E removeFirst() { 248 E x = pollFirst(); 249 if (x == null) 250 throw new NoSuchElementException(); 251 return x; 252 } 253 254 /** 255 * @throws NoSuchElementException {@inheritDoc} 256 */ removeLast()257 public E removeLast() { 258 E x = pollLast(); 259 if (x == null) 260 throw new NoSuchElementException(); 261 return x; 262 } 263 pollFirst()264 public E pollFirst() { 265 int h = head; 266 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 pollLast()274 public E pollLast() { 275 int t = (tail - 1) & (elements.length - 1); 276 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 */ getFirst()287 public E getFirst() { 288 E x = elements[head]; 289 if (x == null) 290 throw new NoSuchElementException(); 291 return x; 292 } 293 294 /** 295 * @throws NoSuchElementException {@inheritDoc} 296 */ getLast()297 public E getLast() { 298 E x = elements[(tail - 1) & (elements.length - 1)]; 299 if (x == null) 300 throw new NoSuchElementException(); 301 return x; 302 } 303 peekFirst()304 public E peekFirst() { 305 return elements[head]; // elements[head] is null if deque empty 306 } 307 peekLast()308 public 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 */ removeFirstOccurrence(Object o)324 public boolean removeFirstOccurrence(Object o) { 325 if (o == null) 326 return false; 327 int mask = elements.length - 1; 328 int i = head; 329 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 */ removeLastOccurrence(Object o)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 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 */ add(E e)379 public boolean add(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 */ offer(E e)393 public boolean offer(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 */ remove()408 public 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 */ poll()422 public 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 */ element()436 public 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 */ peek()449 public 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 */ push(E e)464 public void push(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 */ pop()478 public E pop() { 479 return removeFirst(); 480 } 481 checkInvariants()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 */ delete(int i)500 private boolean delete(int i) { 501 checkInvariants(); 502 final 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 */ size()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 */ isEmpty()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 */ iterator()567 public Iterator<E> iterator() { 568 return new DeqIterator(); 569 } 570 descendingIterator()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 hasNext()593 public boolean hasNext() { 594 return cursor != fence; 595 } 596 next()597 public E next() { 598 if (cursor == fence) 599 throw new NoSuchElementException(); 600 E result = elements[cursor]; 601 // This check doesn't catch all possible comodifications, 602 // but does catch the ones that corrupt traversal 603 if (tail != fence || result == null) 604 throw new ConcurrentModificationException(); 605 lastRet = cursor; 606 cursor = (cursor + 1) & (elements.length - 1); 607 return result; 608 } 609 remove()610 public void remove() { 611 if (lastRet < 0) 612 throw new IllegalStateException(); 613 if (delete(lastRet)) { // if left-shifted, undo increment in next() 614 cursor = (cursor - 1) & (elements.length - 1); 615 fence = tail; 616 } 617 lastRet = -1; 618 } 619 } 620 621 private class DescendingIterator implements Iterator<E> { 622 /* 623 * This class is nearly a mirror-image of DeqIterator, using 624 * tail instead of head for initial cursor, and head instead of 625 * tail for fence. 626 */ 627 private int cursor = tail; 628 private int fence = head; 629 private int lastRet = -1; 630 hasNext()631 public boolean hasNext() { 632 return cursor != fence; 633 } 634 next()635 public E next() { 636 if (cursor == fence) 637 throw new NoSuchElementException(); 638 cursor = (cursor - 1) & (elements.length - 1); 639 E result = elements[cursor]; 640 if (head != fence || result == null) 641 throw new ConcurrentModificationException(); 642 lastRet = cursor; 643 return result; 644 } 645 remove()646 public void remove() { 647 if (lastRet < 0) 648 throw new IllegalStateException(); 649 if (!delete(lastRet)) { 650 cursor = (cursor + 1) & (elements.length - 1); 651 fence = head; 652 } 653 lastRet = -1; 654 } 655 } 656 657 /** 658 * Returns <tt>true</tt> if this deque contains the specified element. 659 * More formally, returns <tt>true</tt> if and only if this deque contains 660 * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>. 661 * 662 * @param o object to be checked for containment in this deque 663 * @return <tt>true</tt> if this deque contains the specified element 664 */ contains(Object o)665 public boolean contains(Object o) { 666 if (o == null) 667 return false; 668 int mask = elements.length - 1; 669 int i = head; 670 E x; 671 while ( (x = elements[i]) != null) { 672 if (o.equals(x)) 673 return true; 674 i = (i + 1) & mask; 675 } 676 return false; 677 } 678 679 /** 680 * Removes a single instance of the specified element from this deque. 681 * If the deque does not contain the element, it is unchanged. 682 * More formally, removes the first element <tt>e</tt> such that 683 * <tt>o.equals(e)</tt> (if such an element exists). 684 * Returns <tt>true</tt> if this deque contained the specified element 685 * (or equivalently, if this deque changed as a result of the call). 686 * 687 * <p>This method is equivalent to {@link #removeFirstOccurrence}. 688 * 689 * @param o element to be removed from this deque, if present 690 * @return <tt>true</tt> if this deque contained the specified element 691 */ remove(Object o)692 public boolean remove(Object o) { 693 return removeFirstOccurrence(o); 694 } 695 696 /** 697 * Removes all of the elements from this deque. 698 * The deque will be empty after this call returns. 699 */ clear()700 public void clear() { 701 int h = head; 702 int t = tail; 703 if (h != t) { // clear all cells 704 head = tail = 0; 705 int i = h; 706 int mask = elements.length - 1; 707 do { 708 elements[i] = null; 709 i = (i + 1) & mask; 710 } while (i != t); 711 } 712 } 713 714 /** 715 * Returns an array containing all of the elements in this deque 716 * in proper sequence (from first to last element). 717 * 718 * <p>The returned array will be "safe" in that no references to it are 719 * maintained by this deque. (In other words, this method must allocate 720 * a new array). The caller is thus free to modify the returned array. 721 * 722 * <p>This method acts as bridge between array-based and collection-based 723 * APIs. 724 * 725 * @return an array containing all of the elements in this deque 726 */ toArray()727 public Object[] toArray() { 728 return copyElements(new Object[size()]); 729 } 730 731 /** 732 * Returns an array containing all of the elements in this deque in 733 * proper sequence (from first to last element); the runtime type of the 734 * returned array is that of the specified array. If the deque fits in 735 * the specified array, it is returned therein. Otherwise, a new array 736 * is allocated with the runtime type of the specified array and the 737 * size of this deque. 738 * 739 * <p>If this deque fits in the specified array with room to spare 740 * (i.e., the array has more elements than this deque), the element in 741 * the array immediately following the end of the deque is set to 742 * <tt>null</tt>. 743 * 744 * <p>Like the {@link #toArray()} method, this method acts as bridge between 745 * array-based and collection-based APIs. Further, this method allows 746 * precise control over the runtime type of the output array, and may, 747 * under certain circumstances, be used to save allocation costs. 748 * 749 * <p>Suppose <tt>x</tt> is a deque known to contain only strings. 750 * The following code can be used to dump the deque into a newly 751 * allocated array of <tt>String</tt>: 752 * 753 * <pre> 754 * String[] y = x.toArray(new String[0]);</pre> 755 * 756 * Note that <tt>toArray(new Object[0])</tt> is identical in function to 757 * <tt>toArray()</tt>. 758 * 759 * @param a the array into which the elements of the deque are to 760 * be stored, if it is big enough; otherwise, a new array of the 761 * same runtime type is allocated for this purpose 762 * @return an array containing all of the elements in this deque 763 * @throws ArrayStoreException if the runtime type of the specified array 764 * is not a supertype of the runtime type of every element in 765 * this deque 766 * @throws NullPointerException if the specified array is null 767 */ toArray(T[] a)768 public <T> T[] toArray(T[] a) { 769 int size = size(); 770 if (a.length < size) 771 a = (T[])java.lang.reflect.Array.newInstance( 772 a.getClass().getComponentType(), size); 773 copyElements(a); 774 if (a.length > size) 775 a[size] = null; 776 return a; 777 } 778 779 // *** Object methods *** 780 781 /** 782 * Returns a copy of this deque. 783 * 784 * @return a copy of this deque 785 */ clone()786 public ArrayDeque<E> clone() { 787 try { 788 ArrayDeque<E> result = (ArrayDeque<E>) super.clone(); 789 result.elements = Arrays.copyOf(elements, elements.length); 790 return result; 791 792 } catch (CloneNotSupportedException e) { 793 throw new AssertionError(); 794 } 795 } 796 797 /** 798 * Appease the serialization gods. 799 */ 800 private static final long serialVersionUID = 2340985798034038923L; 801 802 /** 803 * Serialize this deque. 804 * 805 * @serialData The current size (<tt>int</tt>) of the deque, 806 * followed by all of its elements (each an object reference) in 807 * first-to-last order. 808 */ writeObject(ObjectOutputStream s)809 private void writeObject(ObjectOutputStream s) throws IOException { 810 s.defaultWriteObject(); 811 812 // Write out size 813 s.writeInt(size()); 814 815 // Write out elements in order. 816 int mask = elements.length - 1; 817 for (int i = head; i != tail; i = (i + 1) & mask) 818 s.writeObject(elements[i]); 819 } 820 821 /** 822 * Deserialize this deque. 823 */ readObject(ObjectInputStream s)824 private void readObject(ObjectInputStream s) 825 throws IOException, ClassNotFoundException { 826 s.defaultReadObject(); 827 828 // Read in size and allocate array 829 int size = s.readInt(); 830 allocateElements(size); 831 head = 0; 832 tail = size; 833 834 // Read in all elements in the proper order. 835 for (int i = 0; i < size; i++) 836 elements[i] = (E)s.readObject(); 837 } 838 } 839