ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/ArrayDeque.java

Comparing jsr166/src/main/java/util/ArrayDeque.java (file contents):
Revision 1.6 by dl, Tue Mar 22 16:48:32 2005 UTC vs.
Revision 1.45 by dl, Fri Feb 1 01:02:25 2013 UTC

#	Line 1 | Line 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.
2	>	* Written by Doug Lea with assistance from members of JCP JSR-166
3	>	* Expert Group and released to the public domain, as explained at
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7		package java.util;
8	<	import java.io.*;
8	>	import java.util.Spliterator;
9	>	import java.util.stream.Stream;
10	>	import java.util.stream.Streams;
11	>	import java.util.function.Consumer;
12
13		/**
14		* Resizable-array implementation of the {@link Deque} interface.  Array
#	Line 15 | Line 19 | import java.io.*;
19		* {@link Stack} when used as a stack, and faster than {@link LinkedList}
20		* when used as a queue.
21		*
22	<	* <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
22	>	* <p>Most {@code ArrayDeque} operations run in amortized constant time.
23		* Exceptions include {@link #remove(Object) remove}, {@link
24		* #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
25	<	* removeLastOccurrence}, {@link #contains contains }, {@link #iterator
25	>	* removeLastOccurrence}, {@link #contains contains}, {@link #iterator
26		* iterator.remove()}, and the bulk operations, all of which run in linear
27		* time.
28		*
29	<	* <p>The iterators returned by this class's <tt>iterator</tt> method are
29	>	* <p>The iterators returned by this class's {@code iterator} method are
30		* <i>fail-fast</i>: If the deque is modified at any time after the iterator
31	<	* is created, in any way except through the iterator's own remove method, the
32	<	* iterator will generally throw a {@link ConcurrentModificationException}.
33	<	* Thus, in the face of concurrent modification, the iterator fails quickly
34	<	* and cleanly, rather than risking arbitrary, non-deterministic behavior at
35	<	* an undetermined time in the future.
31	>	* is created, in any way except through the iterator's own {@code remove}
32	>	* method, the iterator will generally throw a {@link
33	>	* ConcurrentModificationException}.  Thus, in the face of concurrent
34	>	* modification, the iterator fails quickly and cleanly, rather than risking
35	>	* arbitrary, non-deterministic behavior at an undetermined time in the
36	>	* future.
37		*
38		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
39		* as it is, generally speaking, impossible to make any hard guarantees in the
40		* presence of unsynchronized concurrent modification.  Fail-fast iterators
41	<	* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
41	>	* throw {@code ConcurrentModificationException} on a best-effort basis.
42		* Therefore, it would be wrong to write a program that depended on this
43		* exception for its correctness: <i>the fail-fast behavior of iterators
44		* should be used only to detect bugs.</i>
45		*
46		* <p>This class and its iterator implement all of the
47	<	* optional methods of the {@link Collection} and {@link
48	<	* Iterator} interfaces.  This class is a member of the <a
49	<	* href="{@docRoot}/../guide/collections/index.html"> Java Collections
50	<	* Framework</a>.
47	>	* <em>optional</em> methods of the {@link Collection} and {@link
48	>	* Iterator} interfaces.
49	>	*
50	>	* <p>This class is a member of the
51	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
52	>	* Java Collections Framework</a>.
53		*
54		* @author  Josh Bloch and Doug Lea
55		* @since   1.6
56		* @param <E> the type of elements held in this collection
57		*/
58		public class ArrayDeque<E> extends AbstractCollection<E>
59	<	implements Deque<E>, Cloneable, Serializable
59	>	implements Deque<E>, Cloneable, java.io.Serializable
60		{
61		/**
62		* The array in which the elements of the deque are stored.
#	Line 61 | Line 68 | public class ArrayDeque<E> extends Abstr
68		* other.  We also guarantee that all array cells not holding
69		* deque elements are always null.
70		*/
71	<	private transient E[] elements;
71	>	transient Object[] elements; // non-private to simplify nested class access
72
73		/**
74		* The index of the element at the head of the deque (which is the
75		* element that would be removed by remove() or pop()); or an
76		* arbitrary number equal to tail if the deque is empty.
77		*/
78	<	private transient int head;
78	>	transient int head;
79
80		/**
81		* The index at which the next element would be added to the tail
82		* of the deque (via addLast(E), add(E), or push(E)).
83		*/
84	<	private transient int tail;
84	>	transient int tail;
85
86		/**
87		* The minimum capacity that we'll use for a newly created deque.
#	Line 85 | Line 92 | public class ArrayDeque<E> extends Abstr
92		// ******  Array allocation and resizing utilities ******
93
94		/**
95	<	* Allocate empty array to hold the given number of elements.
95	>	* Allocates empty array to hold the given number of elements.
96		*
97	<	* @param numElements  the number of elements to hold.
97	>	* @param numElements  the number of elements to hold
98		*/
99		private void allocateElements(int numElements) {
100		int initialCapacity = MIN_INITIAL_CAPACITY;
#	Line 105 | Line 112 | public class ArrayDeque<E> extends Abstr
112		if (initialCapacity < 0)   // Too many elements, must back off
113		initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
114		}
115	<	elements = (E[]) new Object[initialCapacity];
115	>	elements = new Object[initialCapacity];
116		}
117
118		/**
119	<	* Double the capacity of this deque.  Call only when full, i.e.,
119	>	* Doubles the capacity of this deque.  Call only when full, i.e.,
120		* when head and tail have wrapped around to become equal.
121		*/
122		private void doubleCapacity() {
#	Line 123 | Line 130 | public class ArrayDeque<E> extends Abstr
130		Object[] a = new Object[newCapacity];
131		System.arraycopy(elements, p, a, 0, r);
132		System.arraycopy(elements, 0, a, r, p);
133	<	elements = (E[])a;
133	>	elements = a;
134		head = 0;
135		tail = n;
136		}
137
138		/**
139	<	* Copy the elements from our element array into the specified array,
139	>	* Copies the elements from our element array into the specified array,
140		* in order (from first to last element in the deque).  It is assumed
141		* that the array is large enough to hold all elements in the deque.
142		*
#	Line 151 | Line 158 | public class ArrayDeque<E> extends Abstr
158		* sufficient to hold 16 elements.
159		*/
160		public ArrayDeque() {
161	<	elements = (E[]) new Object[16];
161	>	elements = new Object[16];
162		}
163
164		/**
#	Line 186 | Line 193 | public class ArrayDeque<E> extends Abstr
193		/**
194		* Inserts the specified element at the front of this deque.
195		*
196	<	* @param e the element to insert
197	<	* @throws NullPointerException if <tt>e</tt> is null
196	>	* @param e the element to add
197	>	* @throws NullPointerException if the specified element is null
198		*/
199		public void addFirst(E e) {
200		if (e == null)
#	Line 199 | Line 206 | public class ArrayDeque<E> extends Abstr
206
207		/**
208		* Inserts the specified element at the end of this deque.
202	–	* This method is equivalent to {@link Collection#add} and
203	–	* {@link #push}.
209		*
210	<	* @param e the element to insert
211	<	* @throws NullPointerException if <tt>e</tt> is null
210	>	* <p>This method is equivalent to {@link #add}.
211	>	*
212	>	* @param e the element to add
213	>	* @throws NullPointerException if the specified element is null
214		*/
215		public void addLast(E e) {
216		if (e == null)
#	Line 214 | Line 221 | public class ArrayDeque<E> extends Abstr
221		}
222
223		/**
217	–	* Retrieves and removes the first element of this deque, or
218	–	* <tt>null</tt> if this deque is empty.
219	–	*
220	–	* @return the first element of this deque, or <tt>null</tt> if
221	–	*     this deque is empty
222	–	*/
223	–	public E pollFirst() {
224	–	int h = head;
225	–	E result = elements[h]; // Element is null if deque empty
226	–	if (result == null)
227	–	return null;
228	–	elements[h] = null;     // Must null out slot
229	–	head = (h + 1) & (elements.length - 1);
230	–	return result;
231	–	}
232	–
233	–	/**
234	–	* Retrieves and removes the last element of this deque, or
235	–	* <tt>null</tt> if this deque is empty.
236	–	*
237	–	* @return the last element of this deque, or <tt>null</tt> if
238	–	*     this deque is empty
239	–	*/
240	–	public E pollLast() {
241	–	int t = (tail - 1) & (elements.length - 1);
242	–	E result = elements[t];
243	–	if (result == null)
244	–	return null;
245	–	elements[t] = null;
246	–	tail = t;
247	–	return result;
248	–	}
249	–
250	–	/**
224		* Inserts the specified element at the front of this deque.
225		*
226	<	* @param e the element to insert
227	<	* @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
228	<	* @throws NullPointerException if <tt>e</tt> is null
226	>	* @param e the element to add
227	>	* @return {@code true} (as specified by {@link Deque#offerFirst})
228	>	* @throws NullPointerException if the specified element is null
229		*/
230		public boolean offerFirst(E e) {
231		addFirst(e);
#	Line 262 | Line 235 | public class ArrayDeque<E> extends Abstr
235		/**
236		* Inserts the specified element at the end of this deque.
237		*
238	<	* @param e the element to insert
239	<	* @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
240	<	* @throws NullPointerException if <tt>e</tt> is null
238	>	* @param e the element to add
239	>	* @return {@code true} (as specified by {@link Deque#offerLast})
240	>	* @throws NullPointerException if the specified element is null
241		*/
242		public boolean offerLast(E e) {
243		addLast(e);
#	Line 272 | Line 245 | public class ArrayDeque<E> extends Abstr
245		}
246
247		/**
248	<	* Retrieves and removes the first element of this deque.  This method
276	<	* differs from the <tt>pollFirst</tt> method in that it throws an
277	<	* exception if this deque is empty.
278	<	*
279	<	* @return the first element of this deque
280	<	* @throws NoSuchElementException if this deque is empty
248	>	* @throws NoSuchElementException {@inheritDoc}
249		*/
250		public E removeFirst() {
251		E x = pollFirst();
#	Line 287 | Line 255 | public class ArrayDeque<E> extends Abstr
255		}
256
257		/**
258	<	* Retrieves and removes the last element of this deque.  This method
291	<	* differs from the <tt>pollLast</tt> method in that it throws an
292	<	* exception if this deque is empty.
293	<	*
294	<	* @return the last element of this deque
295	<	* @throws NoSuchElementException if this deque is empty
258	>	* @throws NoSuchElementException {@inheritDoc}
259		*/
260		public E removeLast() {
261		E x = pollLast();
#	Line 301 | Line 264 | public class ArrayDeque<E> extends Abstr
264		return x;
265		}
266
267	<	/**
268	<	* Retrieves, but does not remove, the first element of this deque,
269	<	* returning <tt>null</tt> if this deque is empty.
270	<	*
271	<	* @return the first element of this deque, or <tt>null</tt> if
272	<	*     this deque is empty
273	<	*/
274	<	public E peekFirst() {
275	<	return elements[head]; // elements[head] is null if deque empty
267	>	public E pollFirst() {
268	>	int h = head;
269	>	@SuppressWarnings("unchecked")
270	>	E result = (E) elements[h];
271	>	// Element is null if deque empty
272	>	if (result == null)
273	>	return null;
274	>	elements[h] = null;     // Must null out slot
275	>	head = (h + 1) & (elements.length - 1);
276	>	return result;
277		}
278
279	<	/**
280	<	* Retrieves, but does not remove, the last element of this deque,
281	<	* returning <tt>null</tt> if this deque is empty.
282	<	*
283	<	* @return the last element of this deque, or <tt>null</tt> if this deque
284	<	*     is empty
285	<	*/
286	<	public E peekLast() {
287	<	return elements[(tail - 1) & (elements.length - 1)];
279	>	public E pollLast() {
280	>	int t = (tail - 1) & (elements.length - 1);
281	>	@SuppressWarnings("unchecked")
282	>	E result = (E) elements[t];
283	>	if (result == null)
284	>	return null;
285	>	elements[t] = null;
286	>	tail = t;
287	>	return result;
288		}
289
290		/**
291	<	* Retrieves, but does not remove, the first element of this
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
332	<	* @throws NoSuchElementException if this deque is empty
291	>	* @throws NoSuchElementException {@inheritDoc}
292		*/
293		public E getFirst() {
294	<	E x = elements[head];
295	<	if (x == null)
294	>	@SuppressWarnings("unchecked")
295	>	E result = (E) elements[head];
296	>	if (result == null)
297		throw new NoSuchElementException();
298	<	return x;
298	>	return result;
299		}
300
301		/**
302	<	* Retrieves, but does not remove, the last element of this
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
347	<	* @throws NoSuchElementException if this deque is empty
302	>	* @throws NoSuchElementException {@inheritDoc}
303		*/
304		public E getLast() {
305	<	E x = elements[(tail - 1) & (elements.length - 1)];
306	<	if (x == null)
305	>	@SuppressWarnings("unchecked")
306	>	E result = (E) elements[(tail - 1) & (elements.length - 1)];
307	>	if (result == null)
308		throw new NoSuchElementException();
309	<	return x;
309	>	return result;
310	>	}
311	>
312	>	@SuppressWarnings("unchecked")
313	>	public E peekFirst() {
314	>	// elements[head] is null if deque empty
315	>	return (E) elements[head];
316	>	}
317	>
318	>	@SuppressWarnings("unchecked")
319	>	public E peekLast() {
320	>	return (E) elements[(tail - 1) & (elements.length - 1)];
321		}
322
323		/**
324		* Removes the first occurrence of the specified element in this
325	<	* deque (when traversing the deque from head to tail).  More
326	<	* formally, removes the first element e such that (o==null ?
327	<	* e==null : o.equals(e)). If the deque does not contain the
328	<	* element, it is unchanged.
325	>	* deque (when traversing the deque from head to tail).
326	>	* If the deque does not contain the element, it is unchanged.
327	>	* More formally, removes the first element {@code e} such that
328	>	* {@code o.equals(e)} (if such an element exists).
329	>	* Returns {@code true} if this deque contained the specified element
330	>	* (or equivalently, if this deque changed as a result of the call).
331		*
332		* @param o element to be removed from this deque, if present
333	<	* @return <tt>true</tt> if the deque contained the specified element
333	>	* @return {@code true} if the deque contained the specified element
334		*/
335		public boolean removeFirstOccurrence(Object o) {
336		if (o == null)
337		return false;
338		int mask = elements.length - 1;
339		int i = head;
340	<	E x;
340	>	Object x;
341		while ( (x = elements[i]) != null) {
342		if (o.equals(x)) {
343		delete(i);
#	Line 381 | Line 350 | public class ArrayDeque<E> extends Abstr
350
351		/**
352		* Removes the last occurrence of the specified element in this
353	<	* deque (when traversing the deque from head to tail). More
354	<	* formally, removes the last element e such that (o==null ?
355	<	* e==null : o.equals(e)). If the deque
356	<	* does not contain the element, it is unchanged.
353	>	* deque (when traversing the deque from head to tail).
354	>	* If the deque does not contain the element, it is unchanged.
355	>	* More formally, removes the last element {@code e} such that
356	>	* {@code o.equals(e)} (if such an element exists).
357	>	* Returns {@code true} if this deque contained the specified element
358	>	* (or equivalently, if this deque changed as a result of the call).
359		*
360		* @param o element to be removed from this deque, if present
361	<	* @return <tt>true</tt> if the deque contained the specified element
361	>	* @return {@code true} if the deque contained the specified element
362		*/
363		public boolean removeLastOccurrence(Object o) {
364		if (o == null)
365		return false;
366		int mask = elements.length - 1;
367		int i = (tail - 1) & mask;
368	<	E x;
368	>	Object x;
369		while ( (x = elements[i]) != null) {
370		if (o.equals(x)) {
371		delete(i);
#	Line 410 | Line 381 | public class ArrayDeque<E> extends Abstr
381		/**
382		* Inserts the specified element at the end of this deque.
383		*
413	–	* <p>This method is equivalent to {@link #offerLast}.
414	–	*
415	–	* @param e the element to insert
416	–	* @return <tt>true</tt> (as per the spec for {@link Queue#offer})
417	–	* @throws NullPointerException if <tt>e</tt> is null
418	–	*/
419	–	public boolean offer(E e) {
420	–	return offerLast(e);
421	–	}
422	–
423	–	/**
424	–	* Inserts the specified element at the end of this deque.
425	–	*
384		* <p>This method is equivalent to {@link #addLast}.
385		*
386	<	* @param e the element to insert
387	<	* @return <tt>true</tt> (as per the spec for {@link Collection#add})
388	<	* @throws NullPointerException if <tt>e</tt> is null
386	>	* @param e the element to add
387	>	* @return {@code true} (as specified by {@link Collection#add})
388	>	* @throws NullPointerException if the specified element is null
389		*/
390		public boolean add(E e) {
391		addLast(e);
#	Line 435 | Line 393 | public class ArrayDeque<E> extends Abstr
393		}
394
395		/**
396	<	* Retrieves and removes the head of the queue represented by
439	<	* this deque, or <tt>null</tt> if this deque is empty.  In other words,
440	<	* retrieves and removes the first element of this deque, or <tt>null</tt>
441	<	* if this deque is empty.
396	>	* Inserts the specified element at the end of this deque.
397		*
398	<	* <p>This method is equivalent to {@link #pollFirst}.
398	>	* <p>This method is equivalent to {@link #offerLast}.
399		*
400	<	* @return the first element of this deque, or <tt>null</tt> if
401	<	*     this deque is empty
400	>	* @param e the element to add
401	>	* @return {@code true} (as specified by {@link Queue#offer})
402	>	* @throws NullPointerException if the specified element is null
403		*/
404	<	public E poll() {
405	<	return pollFirst();
404	>	public boolean offer(E e) {
405	>	return offerLast(e);
406		}
407
408		/**
409		* Retrieves and removes the head of the queue represented by this deque.
410	<	* This method differs from the <tt>poll</tt> method in that it throws an
410	>	*
411	>	* This method differs from {@link #poll poll} only in that it throws an
412		* exception if this deque is empty.
413		*
414		* <p>This method is equivalent to {@link #removeFirst}.
415		*
416		* @return the head of the queue represented by this deque
417	<	* @throws NoSuchElementException if this deque is empty
417	>	* @throws NoSuchElementException {@inheritDoc}
418		*/
419		public E remove() {
420		return removeFirst();
421		}
422
423		/**
424	<	* Retrieves, but does not remove, the head of the queue represented by
425	<	* this deque, returning <tt>null</tt> if this deque is empty.
424	>	* Retrieves and removes the head of the queue represented by this deque
425	>	* (in other words, the first element of this deque), or returns
426	>	* {@code null} if this deque is empty.
427		*
428	<	* <p>This method is equivalent to {@link #peekFirst}
428	>	* <p>This method is equivalent to {@link #pollFirst}.
429		*
430		* @return the head of the queue represented by this deque, or
431	<	*     <tt>null</tt> if this deque is empty
431	>	*         {@code null} if this deque is empty
432		*/
433	<	public E peek() {
434	<	return peekFirst();
433	>	public E poll() {
434	>	return pollFirst();
435		}
436
437		/**
438		* Retrieves, but does not remove, the head of the queue represented by
439	<	* this deque.  This method differs from the <tt>peek</tt> method only in
439	>	* this deque.  This method differs from {@link #peek peek} only in
440		* that it throws an exception if this deque is empty.
441		*
442	<	* <p>This method is equivalent to {@link #getFirst}
442	>	* <p>This method is equivalent to {@link #getFirst}.
443		*
444		* @return the head of the queue represented by this deque
445	<	* @throws NoSuchElementException if this deque is empty
445	>	* @throws NoSuchElementException {@inheritDoc}
446		*/
447		public E element() {
448		return getFirst();
449		}
450
451	+	/**
452	+	* Retrieves, but does not remove, the head of the queue represented by
453	+	* this deque, or returns {@code null} if this deque is empty.
454	+	*
455	+	* <p>This method is equivalent to {@link #peekFirst}.
456	+	*
457	+	* @return the head of the queue represented by this deque, or
458	+	*         {@code null} if this deque is empty
459	+	*/
460	+	public E peek() {
461	+	return peekFirst();
462	+	}
463	+
464		// *** Stack methods ***
465
466		/**
#	Line 499 | Line 470 | public class ArrayDeque<E> extends Abstr
470		* <p>This method is equivalent to {@link #addFirst}.
471		*
472		* @param e the element to push
473	<	* @throws NullPointerException if <tt>e</tt> is null
473	>	* @throws NullPointerException if the specified element is null
474		*/
475		public void push(E e) {
476		addFirst(e);
#	Line 512 | Line 483 | public class ArrayDeque<E> extends Abstr
483		* <p>This method is equivalent to {@link #removeFirst()}.
484		*
485		* @return the element at the front of this deque (which is the top
486	<	*     of the stack represented by this deque)
487	<	* @throws NoSuchElementException if this deque is empty
486	>	*         of the stack represented by this deque)
487	>	* @throws NoSuchElementException {@inheritDoc}
488		*/
489		public E pop() {
490		return removeFirst();
491		}
492
493	+	private void checkInvariants() {
494	+	assert elements[tail] == null;
495	+	assert head == tail ? elements[head] == null :
496	+	(elements[head] != null &&
497	+	elements[(tail - 1) & (elements.length - 1)] != null);
498	+	assert elements[(head - 1) & (elements.length - 1)] == null;
499	+	}
500	+
501		/**
502	<	* Remove the element at the specified position in the elements array,
503	<	* adjusting head, tail, and size as necessary.  This can result in
504	<	* motion of elements backwards or forwards in the array.
502	>	* Removes the element at the specified position in the elements array,
503	>	* adjusting head and tail as necessary.  This can result in motion of
504	>	* elements backwards or forwards in the array.
505		*
506		* <p>This method is called delete rather than remove to emphasize
507	<	* that its semantics differ from those of List.remove(int).
507	>	* that its semantics differ from those of {@link List#remove(int)}.
508		*
509		* @return true if elements moved backwards
510		*/
511		private boolean delete(int i) {
512	<	// Case 1: Deque doesn't wrap
513	<	// Case 2: Deque does wrap and removed element is in the head portion
514	<	if ((head < tail || tail == 0) || i >= head) {
515	<	System.arraycopy(elements, head, elements, head + 1, i - head);
516	<	elements[head] = null;
517	<	head = (head + 1) & (elements.length - 1);
512	>	checkInvariants();
513	>	final Object[] elements = this.elements;
514	>	final int mask = elements.length - 1;
515	>	final int h = head;
516	>	final int t = tail;
517	>	final int front = (i - h) & mask;
518	>	final int back  = (t - i) & mask;
519	>
520	>	// Invariant: head <= i < tail mod circularity
521	>	if (front >= ((t - h) & mask))
522	>	throw new ConcurrentModificationException();
523	>
524	>	// Optimize for least element motion
525	>	if (front < back) {
526	>	if (h <= i) {
527	>	System.arraycopy(elements, h, elements, h + 1, front);
528	>	} else { // Wrap around
529	>	System.arraycopy(elements, 0, elements, 1, i);
530	>	elements[0] = elements[mask];
531	>	System.arraycopy(elements, h, elements, h + 1, mask - h);
532	>	}
533	>	elements[h] = null;
534	>	head = (h + 1) & mask;
535		return false;
536	+	} else {
537	+	if (i < t) { // Copy the null tail as well
538	+	System.arraycopy(elements, i + 1, elements, i, back);
539	+	tail = t - 1;
540	+	} else { // Wrap around
541	+	System.arraycopy(elements, i + 1, elements, i, mask - i);
542	+	elements[mask] = elements[0];
543	+	System.arraycopy(elements, 1, elements, 0, t);
544	+	tail = (t - 1) & mask;
545	+	}
546	+	return true;
547		}
541	–
542	–	// Case 3: Deque wraps and removed element is in the tail portion
543	–	tail--;
544	–	System.arraycopy(elements, i + 1, elements, i, tail - i);
545	–	elements[tail] = null;
546	–	return true;
548		}
549
550		// *** Collection Methods ***
#	Line 558 | Line 559 | public class ArrayDeque<E> extends Abstr
559		}
560
561		/**
562	<	* Returns <tt>true</tt> if this collection contains no elements.<p>
562	>	* Returns {@code true} if this deque contains no elements.
563		*
564	<	* @return <tt>true</tt> if this collection contains no elements.
564	>	* @return {@code true} if this deque contains no elements
565		*/
566		public boolean isEmpty() {
567		return head == tail;
#	Line 572 | Line 573 | public class ArrayDeque<E> extends Abstr
573		* order that elements would be dequeued (via successive calls to
574		* {@link #remove} or popped (via successive calls to {@link #pop}).
575		*
576	<	* @return an <tt>Iterator</tt> over the elements in this deque
576	>	* @return an iterator over the elements in this deque
577		*/
578		public Iterator<E> iterator() {
579		return new DeqIterator();
580		}
581
582	+	public Iterator<E> descendingIterator() {
583	+	return new DescendingIterator();
584	+	}
585	+
586		private class DeqIterator implements Iterator<E> {
587		/**
588		* Index of element to be returned by subsequent call to next.
#	Line 601 | Line 606 | public class ArrayDeque<E> extends Abstr
606		}
607
608		public E next() {
604	–	E result;
609		if (cursor == fence)
610		throw new NoSuchElementException();
611	+	@SuppressWarnings("unchecked")
612	+	E result = (E) elements[cursor];
613		// This check doesn't catch all possible comodifications,
614		// but does catch the ones that corrupt traversal
615	<	if (tail != fence || (result = elements[cursor]) == null)
615	>	if (tail != fence || result == null)
616		throw new ConcurrentModificationException();
617		lastRet = cursor;
618		cursor = (cursor + 1) & (elements.length - 1);
#	Line 616 | Line 622 | public class ArrayDeque<E> extends Abstr
622		public void remove() {
623		if (lastRet < 0)
624		throw new IllegalStateException();
625	<	if (delete(lastRet))
626	<	cursor--;
625	>	if (delete(lastRet)) { // if left-shifted, undo increment in next()
626	>	cursor = (cursor - 1) & (elements.length - 1);
627	>	fence = tail;
628	>	}
629	>	lastRet = -1;
630	>	}
631	>	}
632	>
633	>	private class DescendingIterator implements Iterator<E> {
634	>	/*
635	>	* This class is nearly a mirror-image of DeqIterator, using
636	>	* tail instead of head for initial cursor, and head instead of
637	>	* tail for fence.
638	>	*/
639	>	private int cursor = tail;
640	>	private int fence = head;
641	>	private int lastRet = -1;
642	>
643	>	public boolean hasNext() {
644	>	return cursor != fence;
645	>	}
646	>
647	>	public E next() {
648	>	if (cursor == fence)
649	>	throw new NoSuchElementException();
650	>	cursor = (cursor - 1) & (elements.length - 1);
651	>	@SuppressWarnings("unchecked")
652	>	E result = (E) elements[cursor];
653	>	if (head != fence || result == null)
654	>	throw new ConcurrentModificationException();
655	>	lastRet = cursor;
656	>	return result;
657	>	}
658	>
659	>	public void remove() {
660	>	if (lastRet < 0)
661	>	throw new IllegalStateException();
662	>	if (!delete(lastRet)) {
663	>	cursor = (cursor + 1) & (elements.length - 1);
664	>	fence = head;
665	>	}
666		lastRet = -1;
622	–	fence = tail;
667		}
668		}
669
670		/**
671	<	* Returns <tt>true</tt> if this deque contains the specified
672	<	* element.  More formally, returns <tt>true</tt> if and only if this
673	<	* deque contains at least one element <tt>e</tt> such that
630	<	* <tt>e.equals(o)</tt>.
671	>	* Returns {@code true} if this deque contains the specified element.
672	>	* More formally, returns {@code true} if and only if this deque contains
673	>	* at least one element {@code e} such that {@code o.equals(e)}.
674		*
675		* @param o object to be checked for containment in this deque
676	<	* @return <tt>true</tt> if this deque contains the specified element
676	>	* @return {@code true} if this deque contains the specified element
677		*/
678		public boolean contains(Object o) {
679		if (o == null)
680		return false;
681		int mask = elements.length - 1;
682		int i = head;
683	<	E x;
683	>	Object x;
684		while ( (x = elements[i]) != null) {
685		if (o.equals(x))
686		return true;
#	Line 648 | Line 691 | public class ArrayDeque<E> extends Abstr
691
692		/**
693		* Removes a single instance of the specified element from this deque.
694	<	* This method is equivalent to {@link #removeFirstOccurrence}.
694	>	* If the deque does not contain the element, it is unchanged.
695	>	* More formally, removes the first element {@code e} such that
696	>	* {@code o.equals(e)} (if such an element exists).
697	>	* Returns {@code true} if this deque contained the specified element
698	>	* (or equivalently, if this deque changed as a result of the call).
699	>	*
700	>	* <p>This method is equivalent to {@link #removeFirstOccurrence}.
701		*
702	<	* @param e element to be removed from this deque, if present
703	<	* @return <tt>true</tt> if this deque contained the specified element
702	>	* @param o element to be removed from this deque, if present
703	>	* @return {@code true} if this deque contained the specified element
704		*/
705	<	public boolean remove(Object e) {
706	<	return removeFirstOccurrence(e);
705	>	public boolean remove(Object o) {
706	>	return removeFirstOccurrence(o);
707		}
708
709		/**
710		* Removes all of the elements from this deque.
711	+	* The deque will be empty after this call returns.
712		*/
713		public void clear() {
714		int h = head;
#	Line 670 | Line 720 | public class ArrayDeque<E> extends Abstr
720		do {
721		elements[i] = null;
722		i = (i + 1) & mask;
723	<	} while(i != t);
723	>	} while (i != t);
724		}
725		}
726
727		/**
728		* Returns an array containing all of the elements in this deque
729	<	* in the correct order.
729	>	* in proper sequence (from first to last element).
730	>	*
731	>	* <p>The returned array will be "safe" in that no references to it are
732	>	* maintained by this deque.  (In other words, this method must allocate
733	>	* a new array).  The caller is thus free to modify the returned array.
734	>	*
735	>	* <p>This method acts as bridge between array-based and collection-based
736	>	* APIs.
737		*
738		* @return an array containing all of the elements in this deque
682	–	*         in the correct order
739		*/
740		public Object[] toArray() {
741	<	return copyElements(new Object[size()]);
741	>	return copyElements(new Object[size()]);
742		}
743
744		/**
745	<	* Returns an array containing all of the elements in this deque in the
746	<	* correct order; the runtime type of the returned array is that of the
747	<	* specified array.  If the deque fits in the specified array, it is
748	<	* returned therein.  Otherwise, a new array is allocated with the runtime
749	<	* type of the specified array and the size of this deque.
745	>	* Returns an array containing all of the elements in this deque in
746	>	* proper sequence (from first to last element); the runtime type of the
747	>	* returned array is that of the specified array.  If the deque fits in
748	>	* the specified array, it is returned therein.  Otherwise, a new array
749	>	* is allocated with the runtime type of the specified array and the
750	>	* size of this deque.
751	>	*
752	>	* <p>If this deque fits in the specified array with room to spare
753	>	* (i.e., the array has more elements than this deque), the element in
754	>	* the array immediately following the end of the deque is set to
755	>	* {@code null}.
756	>	*
757	>	* <p>Like the {@link #toArray()} method, this method acts as bridge between
758	>	* array-based and collection-based APIs.  Further, this method allows
759	>	* precise control over the runtime type of the output array, and may,
760	>	* under certain circumstances, be used to save allocation costs.
761		*
762	<	* <p>If the deque fits in the specified array with room to spare (i.e.,
763	<	* the array has more elements than the deque), the element in the array
764	<	* immediately following the end of the collection is set to <tt>null</tt>.
762	>	* <p>Suppose {@code x} is a deque known to contain only strings.
763	>	* The following code can be used to dump the deque into a newly
764	>	* allocated array of {@code String}:
765	>	*
766	>	*  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
767	>	*
768	>	* Note that {@code toArray(new Object[0])} is identical in function to
769	>	* {@code toArray()}.
770		*
771		* @param a the array into which the elements of the deque are to
772	<	*          be stored, if it is big enough; otherwise, a new array of the
773	<	*          same runtime type is allocated for this purpose
774	<	* @return an array containing the elements of the deque
775	<	* @throws ArrayStoreException if the runtime type of a is not a supertype
776	<	*         of the runtime type of every element in this deque
772	>	*          be stored, if it is big enough; otherwise, a new array of the
773	>	*          same runtime type is allocated for this purpose
774	>	* @return an array containing all of the elements in this deque
775	>	* @throws ArrayStoreException if the runtime type of the specified array
776	>	*         is not a supertype of the runtime type of every element in
777	>	*         this deque
778	>	* @throws NullPointerException if the specified array is null
779		*/
780	+	@SuppressWarnings("unchecked")
781		public <T> T[] toArray(T[] a) {
782		int size = size();
783		if (a.length < size)
784		a = (T[])java.lang.reflect.Array.newInstance(
785		a.getClass().getComponentType(), size);
786	<	copyElements(a);
786	>	copyElements(a);
787		if (a.length > size)
788		a[size] = null;
789		return a;
#	Line 723 | Line 798 | public class ArrayDeque<E> extends Abstr
798		*/
799		public ArrayDeque<E> clone() {
800		try {
801	+	@SuppressWarnings("unchecked")
802		ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
803	<	// 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);
803	>	result.elements = Arrays.copyOf(elements, elements.length);
804		return result;
731	–
805		} catch (CloneNotSupportedException e) {
806		throw new AssertionError();
807		}
808		}
809
737	–	/**
738	–	* Appease the serialization gods.
739	–	*/
810		private static final long serialVersionUID = 2340985798034038923L;
811
812		/**
813	<	* Serialize this deque.
813	>	* Saves this deque to a stream (that is, serializes it).
814		*
815	<	* @serialData The current size (<tt>int</tt>) of the deque,
815	>	* @serialData The current size ({@code int}) of the deque,
816		* followed by all of its elements (each an object reference) in
817		* first-to-last order.
818		*/
819	<	private void writeObject(ObjectOutputStream s) throws IOException {
819	>	private void writeObject(java.io.ObjectOutputStream s)
820	>	throws java.io.IOException {
821		s.defaultWriteObject();
822
823		// Write out size
824	<	int size = size();
754	<	s.writeInt(size);
824	>	s.writeInt(size());
825
826		// Write out elements in order.
757	–	int i = head;
827		int mask = elements.length - 1;
828	<	for (int j = 0; j < size; j++) {
828	>	for (int i = head; i != tail; i = (i + 1) & mask)
829		s.writeObject(elements[i]);
761	–	i = (i + 1) & mask;
762	–	}
830		}
831
832		/**
833	<	* Deserialize this deque.
833	>	* Reconstitutes this deque from a stream (that is, deserializes it).
834		*/
835	<	private void readObject(ObjectInputStream s)
836	<	throws IOException, ClassNotFoundException {
835	>	private void readObject(java.io.ObjectInputStream s)
836	>	throws java.io.IOException, ClassNotFoundException {
837		s.defaultReadObject();
838
839		// Read in size and allocate array
#	Line 777 | Line 844 | public class ArrayDeque<E> extends Abstr
844
845		// Read in all elements in the proper order.
846		for (int i = 0; i < size; i++)
847	<	elements[i] = (E)s.readObject();
847	>	elements[i] = s.readObject();
848	>	}
849
850	+	public Stream<E> stream() {
851	+	int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
852	+	return Streams.stream
853	+	(() -> new DeqSpliterator<E>(this, head, tail), flags);
854		}
855	+	public Stream<E> parallelStream() {
856	+	int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
857	+	return Streams.parallelStream
858	+	(() -> new DeqSpliterator<E>(this, head, tail), flags);
859	+	}
860	+
861	+
862	+	static final class DeqSpliterator<E> implements Spliterator<E> {
863	+	private final ArrayDeque<E> deq;
864	+	private final int fence;  // initially tail
865	+	private int index;        // current index, modified on traverse/split
866	+
867	+	/** Create new spliterator covering the given array and range */
868	+	DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
869	+	this.deq = deq; this.index = origin; this.fence = fence;
870	+	}
871	+
872	+	public DeqSpliterator<E> trySplit() {
873	+	int n = deq.elements.length;
874	+	int h = index, t = fence;
875	+	if (h != t && ((h + 1) & (n - 1)) != t) {
876	+	if (h > t)
877	+	t += n;
878	+	int m = ((h + t) >>> 1) & (n - 1);
879	+	return new DeqSpliterator<E>(deq, h, index = m);
880	+	}
881	+	return null;
882	+	}
883	+
884	+	public void forEach(Consumer<? super E> block) {
885	+	if (block == null)
886	+	throw new NullPointerException();
887	+	Object[] a = deq.elements;
888	+	int m = a.length - 1, f = fence, i = index;
889	+	index = f;
890	+	while (i != f) {
891	+	@SuppressWarnings("unchecked") E e = (E)a[i];
892	+	i = (i + 1) & m;
893	+	if (e == null)
894	+	throw new ConcurrentModificationException();
895	+	block.accept(e);
896	+	}
897	+	}
898	+
899	+	public boolean tryAdvance(Consumer<? super E> block) {
900	+	if (block == null)
901	+	throw new NullPointerException();
902	+	Object[] a = deq.elements;
903	+	int m = a.length - 1, i = index;
904	+	if (i != fence) {
905	+	@SuppressWarnings("unchecked") E e = (E)a[i];
906	+	index = (i + 1) & m;
907	+	if (e == null)
908	+	throw new ConcurrentModificationException();
909	+	block.accept(e);
910	+	return true;
911	+	}
912	+	return false;
913	+	}
914	+
915	+	// Other spliterator methods
916	+	public long estimateSize() {
917	+	int n = fence - index;
918	+	if (n < 0)
919	+	n += deq.elements.length;
920	+	return (long)n;
921	+	}
922	+	public boolean hasExactSize() { return true; }
923	+	public boolean hasExactSplits() { return true; }
924	+	}
925	+
926		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines