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