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 remove method, the |
28 |
< |
* iterator will generally throw a {@link ConcurrentModificationException}. |
29 |
< |
* Thus, in the face of concurrent modification, the iterator fails quickly |
30 |
< |
* and cleanly, rather than risking arbitrary, non-deterministic behavior at |
31 |
< |
* an undetermined time in the future. |
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. |
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> |
53 |
|
implements Deque<E>, Cloneable, Serializable |
54 |
|
{ |
55 |
|
/** |
56 |
< |
* The array in which the elements of in the deque are stored. |
56 |
> |
* The array in which the elements of the deque are stored. |
57 |
|
* 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 |
90 |
|
* |
91 |
|
* @param numElements the number of elements to hold. |
92 |
|
*/ |
93 |
< |
private void allocateElements(int numElements) { |
93 |
> |
private void allocateElements(int numElements) { |
94 |
|
int initialCapacity = MIN_INITIAL_CAPACITY; |
95 |
|
// Find the best power of two to hold elements. |
96 |
|
// Tests "<=" because arrays aren't kept full. |
114 |
|
* when head and tail have wrapped around to become equal. |
115 |
|
*/ |
116 |
|
private void doubleCapacity() { |
117 |
< |
assert head == tail; |
117 |
> |
assert head == tail; |
118 |
|
int p = head; |
119 |
|
int n = elements.length; |
120 |
|
int r = n - p; // number of elements to the right of p |
130 |
|
} |
131 |
|
|
132 |
|
/** |
133 |
< |
* Copy the elements from our element array into the specified array, |
133 |
> |
* Copies the elements from our element array into the specified array, |
134 |
|
* 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 |
|
* |
148 |
|
} |
149 |
|
|
150 |
|
/** |
151 |
< |
* Constructs an empty array deque with the an initial capacity |
151 |
> |
* Constructs an empty array deque with an initial capacity |
152 |
|
* sufficient to hold 16 elements. |
153 |
|
*/ |
154 |
|
public ArrayDeque() { |
185 |
|
// terms of these. |
186 |
|
|
187 |
|
/** |
188 |
< |
* Inserts the specified element to the front this deque. |
188 |
> |
* Inserts the specified element at the front of this deque. |
189 |
|
* |
190 |
|
* @param e the element to insert |
191 |
|
* @throws NullPointerException if <tt>e</tt> is null |
194 |
|
if (e == null) |
195 |
|
throw new NullPointerException(); |
196 |
|
elements[head = (head - 1) & (elements.length - 1)] = e; |
197 |
< |
if (head == tail) |
197 |
> |
if (head == tail) |
198 |
|
doubleCapacity(); |
199 |
|
} |
200 |
|
|
201 |
|
/** |
202 |
< |
* Inserts the specified element to the end this deque. |
202 |
> |
* Inserts the specified element at the end of this deque. |
203 |
|
* This method is equivalent to {@link Collection#add} and |
204 |
|
* {@link #push}. |
205 |
|
* |
243 |
|
E result = elements[t]; |
244 |
|
if (result == null) |
245 |
|
return null; |
246 |
< |
elements[t] = null; |
246 |
> |
elements[t] = null; |
247 |
|
tail = t; |
248 |
|
return result; |
249 |
|
} |
250 |
|
|
251 |
|
/** |
252 |
< |
* Inserts the specified element to the front this deque. |
252 |
> |
* Inserts the specified element at the front of this deque. |
253 |
|
* |
254 |
|
* @param e the element to insert |
255 |
|
* @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst}) |
261 |
|
} |
262 |
|
|
263 |
|
/** |
264 |
< |
* Inserts the specified element to the end this deque. |
264 |
> |
* Inserts the specified element at the end of this deque. |
265 |
|
* |
266 |
|
* @param e the element to insert |
267 |
|
* @return <tt>true</tt> (as per the spec for {@link Deque#offerLast}) |
326 |
|
|
327 |
|
/** |
328 |
|
* Retrieves, but does not remove, the first element of this |
329 |
< |
* deque. This method differs from the <tt>peek</tt> method only |
329 |
> |
* deque. This method differs from the <tt>peekFirst</tt> method only |
330 |
|
* in that it throws an exception if this deque is empty. |
331 |
|
* |
332 |
|
* @return the first element of this deque |
341 |
|
|
342 |
|
/** |
343 |
|
* Retrieves, but does not remove, the last element of this |
344 |
< |
* deque. This method differs from the <tt>peek</tt> method only |
344 |
> |
* deque. This method differs from the <tt>peekLast</tt> method only |
345 |
|
* in that it throws an exception if this deque is empty. |
346 |
|
* |
347 |
|
* @return the last element of this deque |
356 |
|
|
357 |
|
/** |
358 |
|
* Removes the first occurrence of the specified element in this |
359 |
< |
* deque (when traversing the deque from head to tail). If the deque |
360 |
< |
* does not contain the element, it is unchanged. |
359 |
> |
* 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 |
|
* |
364 |
< |
* @param e element to be removed from this deque, if present |
364 |
> |
* @param o element to be removed from this deque, if present |
365 |
|
* @return <tt>true</tt> if the deque contained the specified element |
366 |
|
*/ |
367 |
< |
public boolean removeFirstOccurrence(Object e) { |
368 |
< |
if (e == null) |
367 |
> |
public boolean removeFirstOccurrence(Object o) { |
368 |
> |
if (o == null) |
369 |
|
return false; |
370 |
|
int mask = elements.length - 1; |
371 |
|
int i = head; |
372 |
|
E x; |
373 |
|
while ( (x = elements[i]) != null) { |
374 |
< |
if (e.equals(x)) { |
374 |
> |
if (o.equals(x)) { |
375 |
|
delete(i); |
376 |
|
return true; |
377 |
|
} |
382 |
|
|
383 |
|
/** |
384 |
|
* Removes the last occurrence of the specified element in this |
385 |
< |
* deque (when traversing the deque from head to tail). If the deque |
385 |
> |
* 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 |
|
* does not contain the element, it is unchanged. |
389 |
|
* |
390 |
< |
* @param e element to be removed from this deque, if present |
390 |
> |
* @param o element to be removed from this deque, if present |
391 |
|
* @return <tt>true</tt> if the deque contained the specified element |
392 |
|
*/ |
393 |
< |
public boolean removeLastOccurrence(Object e) { |
394 |
< |
if (e == null) |
393 |
> |
public boolean removeLastOccurrence(Object o) { |
394 |
> |
if (o == null) |
395 |
|
return false; |
396 |
|
int mask = elements.length - 1; |
397 |
|
int i = (tail - 1) & mask; |
398 |
|
E x; |
399 |
|
while ( (x = elements[i]) != null) { |
400 |
< |
if (e.equals(x)) { |
400 |
> |
if (o.equals(x)) { |
401 |
|
delete(i); |
402 |
|
return true; |
403 |
|
} |
409 |
|
// *** Queue methods *** |
410 |
|
|
411 |
|
/** |
412 |
< |
* Inserts the specified element to the end of this deque. |
412 |
> |
* Inserts the specified element at the end of this deque. |
413 |
|
* |
414 |
|
* <p>This method is equivalent to {@link #offerLast}. |
415 |
|
* |
422 |
|
} |
423 |
|
|
424 |
|
/** |
425 |
< |
* Inserts the specified element to the end of this deque. |
425 |
> |
* Inserts the specified element at the end of this deque. |
426 |
|
* |
427 |
|
* <p>This method is equivalent to {@link #addLast}. |
428 |
|
* |
495 |
|
|
496 |
|
/** |
497 |
|
* Pushes an element onto the stack represented by this deque. In other |
498 |
< |
* words, inserts the element to the front this deque. |
498 |
> |
* words, inserts the element at the front of this deque. |
499 |
|
* |
500 |
|
* <p>This method is equivalent to {@link #addFirst}. |
501 |
|
* |
521 |
|
} |
522 |
|
|
523 |
|
/** |
524 |
< |
* Remove the element at the specified position in the elements array, |
524 |
> |
* Removes the element at the specified position in the elements array, |
525 |
|
* adjusting head, tail, and size as necessary. This can result in |
526 |
|
* motion of elements backwards or forwards in the array. |
527 |
|
* |
528 |
< |
* <p>This method is called delete rather than remove to emphasize |
528 |
> |
* <p>This method is called delete rather than remove to emphasize |
529 |
|
* that its semantics differ from those of List.remove(int). |
530 |
< |
* |
530 |
> |
* |
531 |
|
* @return true if elements moved backwards |
532 |
|
*/ |
533 |
|
private boolean delete(int i) { |
559 |
|
} |
560 |
|
|
561 |
|
/** |
562 |
< |
* Returns <tt>true</tt> if this collection contains no elements.<p> |
562 |
> |
* Returns <tt>true</tt> if this deque contains no elements.<p> |
563 |
|
* |
564 |
< |
* @return <tt>true</tt> if this collection contains no elements. |
564 |
> |
* @return <tt>true</tt> if this deque contains no elements. |
565 |
|
*/ |
566 |
|
public boolean isEmpty() { |
567 |
|
return head == tail; |
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 |
< |
* |
575 |
> |
* |
576 |
|
* @return an <tt>Iterator</tt> over the elements in this deque |
577 |
|
*/ |
578 |
|
public Iterator<E> iterator() { |
660 |
|
|
661 |
|
/** |
662 |
|
* Removes all of the elements from this deque. |
663 |
+ |
* The deque will be empty after this call returns. |
664 |
|
*/ |
665 |
|
public void clear() { |
666 |
|
int h = head; |
677 |
|
} |
678 |
|
|
679 |
|
/** |
680 |
< |
* Returns an array containing all of the elements in this list |
680 |
> |
* Returns an array containing all of the elements in this deque |
681 |
|
* in the correct order. |
682 |
|
* |
683 |
< |
* @return an array containing all of the elements in this list |
683 |
> |
* @return an array containing all of the elements in this deque |
684 |
|
* in the correct order |
685 |
|
*/ |
686 |
|
public Object[] toArray() { |
724 |
|
* @return a copy of this deque |
725 |
|
*/ |
726 |
|
public ArrayDeque<E> clone() { |
727 |
< |
try { |
727 |
> |
try { |
728 |
|
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 |
< |
} catch (CloneNotSupportedException e) { |
734 |
> |
} catch (CloneNotSupportedException e) { |
735 |
|
throw new AssertionError(); |
736 |
|
} |
737 |
|
} |