33 |
|
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed |
34 |
|
* as it is, generally speaking, impossible to make any hard guarantees in the |
35 |
|
* presence of unsynchronized concurrent modification. Fail-fast iterators |
36 |
< |
* throw <tt>ConcurrentModificationException</tt> on a best-effort basis. |
36 |
> |
* throw <tt>ConcurrentModificationException</tt> on a best-effort basis. |
37 |
|
* Therefore, it would be wrong to write a program that depended on this |
38 |
|
* exception for its correctness: <i>the fail-fast behavior of iterators |
39 |
|
* should be used only to detect bugs.</i> |
52 |
|
implements Deque<E>, Cloneable, Serializable |
53 |
|
{ |
54 |
|
/** |
55 |
< |
* The array in which the elements of in the deque are stored. |
55 |
> |
* The array in which the elements of the deque are stored. |
56 |
|
* The capacity of the deque is the length of this array, which is |
57 |
|
* always a power of two. The array is never allowed to become |
58 |
|
* full, except transiently within an addX method where it is |
89 |
|
* |
90 |
|
* @param numElements the number of elements to hold. |
91 |
|
*/ |
92 |
< |
private void allocateElements(int numElements) { |
92 |
> |
private void allocateElements(int numElements) { |
93 |
|
int initialCapacity = MIN_INITIAL_CAPACITY; |
94 |
|
// Find the best power of two to hold elements. |
95 |
|
// Tests "<=" because arrays aren't kept full. |
113 |
|
* when head and tail have wrapped around to become equal. |
114 |
|
*/ |
115 |
|
private void doubleCapacity() { |
116 |
< |
assert head == tail; |
116 |
> |
assert head == tail; |
117 |
|
int p = head; |
118 |
|
int n = elements.length; |
119 |
|
int r = n - p; // number of elements to the right of p |
147 |
|
} |
148 |
|
|
149 |
|
/** |
150 |
< |
* Constructs an empty array deque with the an initial capacity |
150 |
> |
* Constructs an empty array deque with an initial capacity |
151 |
|
* sufficient to hold 16 elements. |
152 |
|
*/ |
153 |
|
public ArrayDeque() { |
184 |
|
// terms of these. |
185 |
|
|
186 |
|
/** |
187 |
< |
* Inserts the specified element to the front this deque. |
187 |
> |
* Inserts the specified element at the front of this deque. |
188 |
|
* |
189 |
|
* @param e the element to insert |
190 |
|
* @throws NullPointerException if <tt>e</tt> is null |
193 |
|
if (e == null) |
194 |
|
throw new NullPointerException(); |
195 |
|
elements[head = (head - 1) & (elements.length - 1)] = e; |
196 |
< |
if (head == tail) |
196 |
> |
if (head == tail) |
197 |
|
doubleCapacity(); |
198 |
|
} |
199 |
|
|
200 |
|
/** |
201 |
< |
* Inserts the specified element to the end this deque. |
201 |
> |
* Inserts the specified element at the end of this deque. |
202 |
|
* This method is equivalent to {@link Collection#add} and |
203 |
|
* {@link #push}. |
204 |
|
* |
242 |
|
E result = elements[t]; |
243 |
|
if (result == null) |
244 |
|
return null; |
245 |
< |
elements[t] = null; |
245 |
> |
elements[t] = null; |
246 |
|
tail = t; |
247 |
|
return result; |
248 |
|
} |
249 |
|
|
250 |
|
/** |
251 |
< |
* Inserts the specified element to the front this deque. |
251 |
> |
* Inserts the specified element at the front of this deque. |
252 |
|
* |
253 |
|
* @param e the element to insert |
254 |
|
* @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst}) |
260 |
|
} |
261 |
|
|
262 |
|
/** |
263 |
< |
* Inserts the specified element to the end this deque. |
263 |
> |
* Inserts the specified element at the end of this deque. |
264 |
|
* |
265 |
|
* @param e the element to insert |
266 |
|
* @return <tt>true</tt> (as per the spec for {@link Deque#offerLast}) |
325 |
|
|
326 |
|
/** |
327 |
|
* Retrieves, but does not remove, the first element of this |
328 |
< |
* deque. This method differs from the <tt>peek</tt> method only |
328 |
> |
* deque. This method differs from the <tt>peekFirst</tt> method only |
329 |
|
* in that it throws an exception if this deque is empty. |
330 |
|
* |
331 |
|
* @return the first element of this deque |
340 |
|
|
341 |
|
/** |
342 |
|
* Retrieves, but does not remove, the last element of this |
343 |
< |
* deque. This method differs from the <tt>peek</tt> method only |
343 |
> |
* deque. This method differs from the <tt>peekLast</tt> method only |
344 |
|
* in that it throws an exception if this deque is empty. |
345 |
|
* |
346 |
|
* @return the last element of this deque |
355 |
|
|
356 |
|
/** |
357 |
|
* Removes the first occurrence of the specified element in this |
358 |
< |
* deque (when traversing the deque from head to tail). If the deque |
359 |
< |
* does not contain the element, it is unchanged. |
358 |
> |
* deque (when traversing the deque from head to tail). More |
359 |
> |
* formally, removes the first element e such that (o==null ? |
360 |
> |
* e==null : o.equals(e)). If the deque does not contain the |
361 |
> |
* element, it is unchanged. |
362 |
|
* |
363 |
< |
* @param e element to be removed from this deque, if present |
363 |
> |
* @param o element to be removed from this deque, if present |
364 |
|
* @return <tt>true</tt> if the deque contained the specified element |
365 |
|
*/ |
366 |
< |
public boolean removeFirstOccurrence(Object e) { |
367 |
< |
if (e == null) |
366 |
> |
public boolean removeFirstOccurrence(Object o) { |
367 |
> |
if (o == null) |
368 |
|
return false; |
369 |
|
int mask = elements.length - 1; |
370 |
|
int i = head; |
371 |
|
E x; |
372 |
|
while ( (x = elements[i]) != null) { |
373 |
< |
if (e.equals(x)) { |
373 |
> |
if (o.equals(x)) { |
374 |
|
delete(i); |
375 |
|
return true; |
376 |
|
} |
381 |
|
|
382 |
|
/** |
383 |
|
* Removes the last occurrence of the specified element in this |
384 |
< |
* deque (when traversing the deque from head to tail). If the deque |
384 |
> |
* deque (when traversing the deque from head to tail). More |
385 |
> |
* formally, removes the last element e such that (o==null ? |
386 |
> |
* e==null : o.equals(e)). If the deque |
387 |
|
* does not contain the element, it is unchanged. |
388 |
|
* |
389 |
< |
* @param e element to be removed from this deque, if present |
389 |
> |
* @param o element to be removed from this deque, if present |
390 |
|
* @return <tt>true</tt> if the deque contained the specified element |
391 |
|
*/ |
392 |
< |
public boolean removeLastOccurrence(Object e) { |
393 |
< |
if (e == null) |
392 |
> |
public boolean removeLastOccurrence(Object o) { |
393 |
> |
if (o == null) |
394 |
|
return false; |
395 |
|
int mask = elements.length - 1; |
396 |
|
int i = (tail - 1) & mask; |
397 |
|
E x; |
398 |
|
while ( (x = elements[i]) != null) { |
399 |
< |
if (e.equals(x)) { |
399 |
> |
if (o.equals(x)) { |
400 |
|
delete(i); |
401 |
|
return true; |
402 |
|
} |
408 |
|
// *** Queue methods *** |
409 |
|
|
410 |
|
/** |
411 |
< |
* Inserts the specified element to the end of this deque. |
411 |
> |
* Inserts the specified element at the end of this deque. |
412 |
|
* |
413 |
|
* <p>This method is equivalent to {@link #offerLast}. |
414 |
|
* |
421 |
|
} |
422 |
|
|
423 |
|
/** |
424 |
< |
* Inserts the specified element to the end of this deque. |
424 |
> |
* Inserts the specified element at the end of this deque. |
425 |
|
* |
426 |
|
* <p>This method is equivalent to {@link #addLast}. |
427 |
|
* |
494 |
|
|
495 |
|
/** |
496 |
|
* Pushes an element onto the stack represented by this deque. In other |
497 |
< |
* words, inserts the element to the front this deque. |
497 |
> |
* words, inserts the element at the front of this deque. |
498 |
|
* |
499 |
|
* <p>This method is equivalent to {@link #addFirst}. |
500 |
|
* |
524 |
|
* adjusting head, tail, and size as necessary. This can result in |
525 |
|
* motion of elements backwards or forwards in the array. |
526 |
|
* |
527 |
< |
* <p>This method is called delete rather than remove to emphasize |
527 |
> |
* <p>This method is called delete rather than remove to emphasize |
528 |
|
* that its semantics differ from those of List.remove(int). |
529 |
< |
* |
529 |
> |
* |
530 |
|
* @return true if elements moved backwards |
531 |
|
*/ |
532 |
|
private boolean delete(int i) { |
571 |
|
* will be ordered from first (head) to last (tail). This is the same |
572 |
|
* order that elements would be dequeued (via successive calls to |
573 |
|
* {@link #remove} or popped (via successive calls to {@link #pop}). |
574 |
< |
* |
574 |
> |
* |
575 |
|
* @return an <tt>Iterator</tt> over the elements in this deque |
576 |
|
*/ |
577 |
|
public Iterator<E> iterator() { |
675 |
|
} |
676 |
|
|
677 |
|
/** |
678 |
< |
* Returns an array containing all of the elements in this list |
678 |
> |
* Returns an array containing all of the elements in this deque |
679 |
|
* in the correct order. |
680 |
|
* |
681 |
< |
* @return an array containing all of the elements in this list |
681 |
> |
* @return an array containing all of the elements in this deque |
682 |
|
* in the correct order |
683 |
|
*/ |
684 |
|
public Object[] toArray() { |
722 |
|
* @return a copy of this deque |
723 |
|
*/ |
724 |
|
public ArrayDeque<E> clone() { |
725 |
< |
try { |
725 |
> |
try { |
726 |
|
ArrayDeque<E> result = (ArrayDeque<E>) super.clone(); |
727 |
|
// These two lines are currently faster than cloning the array: |
728 |
|
result.elements = (E[]) new Object[elements.length]; |
729 |
|
System.arraycopy(elements, 0, result.elements, 0, elements.length); |
730 |
|
return result; |
731 |
|
|
732 |
< |
} catch (CloneNotSupportedException e) { |
732 |
> |
} catch (CloneNotSupportedException e) { |
733 |
|
throw new AssertionError(); |
734 |
|
} |
735 |
|
} |