ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/ArrayDeque.java
Revision: 1.7
Committed: Tue Apr 26 19:54:03 2005 UTC (19 years, 1 month ago) by jsr166
Branch: MAIN
Changes since 1.6: +11 -9 lines
Log Message:
doc fixes

File Contents

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