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