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.5 by dl, Tue Mar 22 01:29:00 2005 UTC vs.
Revision 1.43 by jsr166, Wed Jan 16 21:25:33 2013 UTC

#	Line 1 | Line 1
1		/*
2	+	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3	+	*
4	+	* This code is free software; you can redistribute it and/or modify it
5	+	* under the terms of the GNU General Public License version 2 only, as
6	+	* published by the Free Software Foundation.  Oracle designates this
7	+	* particular file as subject to the "Classpath" exception as provided
8	+	* by Oracle in the LICENSE file that accompanied this code.
9	+	*
10	+	* This code is distributed in the hope that it will be useful, but WITHOUT
11	+	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12	+	* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
13	+	* version 2 for more details (a copy is included in the LICENSE file that
14	+	* accompanied this code).
15	+	*
16	+	* You should have received a copy of the GNU General Public License version
17	+	* 2 along with this work; if not, write to the Free Software Foundation,
18	+	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19	+	*
20	+	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21	+	* or visit www.oracle.com if you need additional information or have any
22	+	* questions.
23	+	*/
24	+
25	+	/*
26	+	* This file is available under and governed by the GNU General Public
27	+	* License version 2 only, as published by the Free Software Foundation.
28	+	* However, the following notice accompanied the original version of this
29	+	* file:
30	+	*
31		* Written by Josh Bloch of Google Inc. and released to the public domain,
32	<	* as explained at http://creativecommons.org/licenses/publicdomain.
32	>	* as explained at http://creativecommons.org/publicdomain/zero/1.0/.
33		*/
34
35		package java.util;
36	<	import java.io.*;
36	>	import java.util.Spliterator;
37	>	import java.util.stream.Stream;
38	>	import java.util.stream.Streams;
39	>	import java.util.function.Block;
40
41		/**
42		* Resizable-array implementation of the {@link Deque} interface.  Array
#	Line 15 | Line 47 | import java.io.*;
47		* {@link Stack} when used as a stack, and faster than {@link LinkedList}
48		* when used as a queue.
49		*
50	<	* <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
50	>	* <p>Most {@code ArrayDeque} operations run in amortized constant time.
51		* Exceptions include {@link #remove(Object) remove}, {@link
52		* #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
53	<	* removeLastOccurrence}, {@link #contains contains }, {@link #iterator
53	>	* removeLastOccurrence}, {@link #contains contains}, {@link #iterator
54		* iterator.remove()}, and the bulk operations, all of which run in linear
55		* time.
56		*
57	<	* <p>The iterators returned by this class's <tt>iterator</tt> method are
57	>	* <p>The iterators returned by this class's {@code iterator} method are
58		* <i>fail-fast</i>: If the deque is modified at any time after the iterator
59	<	* is created, in any way except through the iterator's own remove method, the
60	<	* iterator will generally throw a {@link ConcurrentModificationException}.
61	<	* Thus, in the face of concurrent modification, the iterator fails quickly
62	<	* and cleanly, rather than risking arbitrary, non-deterministic behavior at
63	<	* an undetermined time in the future.
59	>	* is created, in any way except through the iterator's own {@code remove}
60	>	* method, the iterator will generally throw a {@link
61	>	* ConcurrentModificationException}.  Thus, in the face of concurrent
62	>	* modification, the iterator fails quickly and cleanly, rather than risking
63	>	* arbitrary, non-deterministic behavior at an undetermined time in the
64	>	* future.
65		*
66		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
67		* as it is, generally speaking, impossible to make any hard guarantees in the
68		* presence of unsynchronized concurrent modification.  Fail-fast iterators
69	<	* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
69	>	* throw {@code ConcurrentModificationException} on a best-effort basis.
70		* Therefore, it would be wrong to write a program that depended on this
71		* exception for its correctness: <i>the fail-fast behavior of iterators
72		* should be used only to detect bugs.</i>
73		*
74		* <p>This class and its iterator implement all of the
75	<	* optional methods of the {@link Collection} and {@link
76	<	* Iterator} interfaces.  This class is a member of the <a
77	<	* href="{@docRoot}/../guide/collections/index.html"> Java Collections
78	<	* Framework</a>.
75	>	* <em>optional</em> methods of the {@link Collection} and {@link
76	>	* Iterator} interfaces.
77	>	*
78	>	* <p>This class is a member of the
79	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
80	>	* Java Collections Framework</a>.
81		*
82		* @author  Josh Bloch and Doug Lea
83		* @since   1.6
84		* @param <E> the type of elements held in this collection
85		*/
86		public class ArrayDeque<E> extends AbstractCollection<E>
87	<	implements Deque<E>, Cloneable, Serializable
87	>	implements Deque<E>, Cloneable, java.io.Serializable
88		{
89		/**
90		* The array in which the elements of the deque are stored.
#	Line 61 | Line 96 | public class ArrayDeque<E> extends Abstr
96		* other.  We also guarantee that all array cells not holding
97		* deque elements are always null.
98		*/
99	<	private transient E[] elements;
99	>	transient Object[] elements; // non-private to simplify nested class access
100
101		/**
102		* The index of the element at the head of the deque (which is the
103		* element that would be removed by remove() or pop()); or an
104		* arbitrary number equal to tail if the deque is empty.
105		*/
106	<	private transient int head;
106	>	transient int head;
107
108		/**
109		* The index at which the next element would be added to the tail
110		* of the deque (via addLast(E), add(E), or push(E)).
111		*/
112	<	private transient int tail;
112	>	transient int tail;
113
114		/**
115		* The minimum capacity that we'll use for a newly created deque.
#	Line 85 | Line 120 | public class ArrayDeque<E> extends Abstr
120		// ******  Array allocation and resizing utilities ******
121
122		/**
123	<	* Allocate empty array to hold the given number of elements.
123	>	* Allocates empty array to hold the given number of elements.
124		*
125	<	* @param numElements  the number of elements to hold.
125	>	* @param numElements  the number of elements to hold
126		*/
127		private void allocateElements(int numElements) {
128		int initialCapacity = MIN_INITIAL_CAPACITY;
#	Line 105 | Line 140 | public class ArrayDeque<E> extends Abstr
140		if (initialCapacity < 0)   // Too many elements, must back off
141		initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
142		}
143	<	elements = (E[]) new Object[initialCapacity];
143	>	elements = new Object[initialCapacity];
144		}
145
146		/**
147	<	* Double the capacity of this deque.  Call only when full, i.e.,
147	>	* Doubles the capacity of this deque.  Call only when full, i.e.,
148		* when head and tail have wrapped around to become equal.
149		*/
150		private void doubleCapacity() {
#	Line 123 | Line 158 | public class ArrayDeque<E> extends Abstr
158		Object[] a = new Object[newCapacity];
159		System.arraycopy(elements, p, a, 0, r);
160		System.arraycopy(elements, 0, a, r, p);
161	<	elements = (E[])a;
161	>	elements = a;
162		head = 0;
163		tail = n;
164		}
165
166		/**
167	<	* Copy the elements from our element array into the specified array,
167	>	* Copies the elements from our element array into the specified array,
168		* in order (from first to last element in the deque).  It is assumed
169		* that the array is large enough to hold all elements in the deque.
170		*
#	Line 151 | Line 186 | public class ArrayDeque<E> extends Abstr
186		* sufficient to hold 16 elements.
187		*/
188		public ArrayDeque() {
189	<	elements = (E[]) new Object[16];
189	>	elements = new Object[16];
190		}
191
192		/**
#	Line 186 | Line 221 | public class ArrayDeque<E> extends Abstr
221		/**
222		* Inserts the specified element at the front of this deque.
223		*
224	<	* @param e the element to insert
225	<	* @throws NullPointerException if <tt>e</tt> is null
224	>	* @param e the element to add
225	>	* @throws NullPointerException if the specified element is null
226		*/
227		public void addFirst(E e) {
228		if (e == null)
#	Line 198 | Line 233 | public class ArrayDeque<E> extends Abstr
233		}
234
235		/**
236	<	* Inserts the specified element to the end of this deque.
202	<	* This method is equivalent to {@link Collection#add} and
203	<	* {@link #push}.
236	>	* Inserts the specified element at the end of this deque.
237		*
238	<	* @param e the element to insert
239	<	* @throws NullPointerException if <tt>e</tt> is null
238	>	* <p>This method is equivalent to {@link #add}.
239	>	*
240	>	* @param e the element to add
241	>	* @throws NullPointerException if the specified element is null
242		*/
243		public void addLast(E e) {
244		if (e == null)
#	Line 214 | Line 249 | public class ArrayDeque<E> extends Abstr
249		}
250
251		/**
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	–	/**
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})
256	<	* @throws NullPointerException if <tt>e</tt> is null
254	>	* @param e the element to add
255	>	* @return {@code true} (as specified by {@link Deque#offerFirst})
256	>	* @throws NullPointerException if the specified element is null
257		*/
258		public boolean offerFirst(E e) {
259		addFirst(e);
#	Line 260 | Line 261 | public class ArrayDeque<E> extends Abstr
261		}
262
263		/**
264	<	* Inserts the specified element to the end of 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})
268	<	* @throws NullPointerException if <tt>e</tt> is null
266	>	* @param e the element to add
267	>	* @return {@code true} (as specified by {@link Deque#offerLast})
268	>	* @throws NullPointerException if the specified element is null
269		*/
270		public boolean offerLast(E e) {
271		addLast(e);
#	Line 272 | Line 273 | public class ArrayDeque<E> extends Abstr
273		}
274
275		/**
276	<	* 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
276	>	* @throws NoSuchElementException {@inheritDoc}
277		*/
278		public E removeFirst() {
279		E x = pollFirst();
#	Line 287 | Line 283 | public class ArrayDeque<E> extends Abstr
283		}
284
285		/**
286	<	* 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
286	>	* @throws NoSuchElementException {@inheritDoc}
287		*/
288		public E removeLast() {
289		E x = pollLast();
#	Line 301 | Line 292 | public class ArrayDeque<E> extends Abstr
292		return x;
293		}
294
295	<	/**
296	<	* Retrieves, but does not remove, the first element of this deque,
297	<	* returning <tt>null</tt> if this deque is empty.
298	<	*
299	<	* @return the first element of this deque, or <tt>null</tt> if
300	<	*     this deque is empty
301	<	*/
302	<	public E peekFirst() {
303	<	return elements[head]; // elements[head] is null if deque empty
295	>	public E pollFirst() {
296	>	int h = head;
297	>	@SuppressWarnings("unchecked")
298	>	E result = (E) elements[h];
299	>	// Element is null if deque empty
300	>	if (result == null)
301	>	return null;
302	>	elements[h] = null;     // Must null out slot
303	>	head = (h + 1) & (elements.length - 1);
304	>	return result;
305		}
306
307	<	/**
308	<	* Retrieves, but does not remove, the last element of this deque,
309	<	* returning <tt>null</tt> if this deque is empty.
310	<	*
311	<	* @return the last element of this deque, or <tt>null</tt> if this deque
312	<	*     is empty
313	<	*/
314	<	public E peekLast() {
315	<	return elements[(tail - 1) & (elements.length - 1)];
307	>	public E pollLast() {
308	>	int t = (tail - 1) & (elements.length - 1);
309	>	@SuppressWarnings("unchecked")
310	>	E result = (E) elements[t];
311	>	if (result == null)
312	>	return null;
313	>	elements[t] = null;
314	>	tail = t;
315	>	return result;
316		}
317
318		/**
319	<	* 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
319	>	* @throws NoSuchElementException {@inheritDoc}
320		*/
321		public E getFirst() {
322	<	E x = elements[head];
323	<	if (x == null)
322	>	@SuppressWarnings("unchecked")
323	>	E result = (E) elements[head];
324	>	if (result == null)
325		throw new NoSuchElementException();
326	<	return x;
326	>	return result;
327		}
328
329		/**
330	<	* 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
330	>	* @throws NoSuchElementException {@inheritDoc}
331		*/
332		public E getLast() {
333	<	E x = elements[(tail - 1) & (elements.length - 1)];
334	<	if (x == null)
333	>	@SuppressWarnings("unchecked")
334	>	E result = (E) elements[(tail - 1) & (elements.length - 1)];
335	>	if (result == null)
336		throw new NoSuchElementException();
337	<	return x;
337	>	return result;
338	>	}
339	>
340	>	@SuppressWarnings("unchecked")
341	>	public E peekFirst() {
342	>	// elements[head] is null if deque empty
343	>	return (E) elements[head];
344	>	}
345	>
346	>	@SuppressWarnings("unchecked")
347	>	public E peekLast() {
348	>	return (E) elements[(tail - 1) & (elements.length - 1)];
349		}
350
351		/**
352		* Removes the first occurrence of the specified element in this
353	<	* deque (when traversing the deque from head to tail).  More
354	<	* formally, removes the first element e such that (o==null ?
355	<	* e==null : o.equals(e)). If the deque does not contain the
356	<	* 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 first 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 removeFirstOccurrence(Object o) {
364		if (o == null)
365		return false;
366		int mask = elements.length - 1;
367		int i = head;
368	<	E x;
368	>	Object x;
369		while ( (x = elements[i]) != null) {
370		if (o.equals(x)) {
371		delete(i);
#	Line 381 | Line 378 | public class ArrayDeque<E> extends Abstr
378
379		/**
380		* Removes the last occurrence of the specified element in this
381	<	* deque (when traversing the deque from head to tail). More
382	<	* formally, removes the last element e such that (o==null ?
383	<	* e==null : o.equals(e)). If the deque
384	<	* does not contain the element, it is unchanged.
381	>	* deque (when traversing the deque from head to tail).
382	>	* If the deque does not contain the element, it is unchanged.
383	>	* More formally, removes the last element {@code e} such that
384	>	* {@code o.equals(e)} (if such an element exists).
385	>	* Returns {@code true} if this deque contained the specified element
386	>	* (or equivalently, if this deque changed as a result of the call).
387		*
388		* @param o element to be removed from this deque, if present
389	<	* @return <tt>true</tt> if the deque contained the specified element
389	>	* @return {@code true} if the deque contained the specified element
390		*/
391		public boolean removeLastOccurrence(Object o) {
392		if (o == null)
393		return false;
394		int mask = elements.length - 1;
395		int i = (tail - 1) & mask;
396	<	E x;
396	>	Object x;
397		while ( (x = elements[i]) != null) {
398		if (o.equals(x)) {
399		delete(i);
#	Line 408 | Line 407 | public class ArrayDeque<E> extends Abstr
407		// *** Queue methods ***
408
409		/**
410	<	* Inserts the specified element to the end of this deque.
412	<	*
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 to the end of this deque.
410	>	* Inserts the specified element at the end of this deque.
411		*
412		* <p>This method is equivalent to {@link #addLast}.
413		*
414	<	* @param e the element to insert
415	<	* @return <tt>true</tt> (as per the spec for {@link Collection#add})
416	<	* @throws NullPointerException if <tt>e</tt> is null
414	>	* @param e the element to add
415	>	* @return {@code true} (as specified by {@link Collection#add})
416	>	* @throws NullPointerException if the specified element is null
417		*/
418		public boolean add(E e) {
419		addLast(e);
#	Line 435 | Line 421 | public class ArrayDeque<E> extends Abstr
421		}
422
423		/**
424	<	* 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.
424	>	* Inserts the specified element at the end of this deque.
425		*
426	<	* <p>This method is equivalent to {@link #pollFirst}.
426	>	* <p>This method is equivalent to {@link #offerLast}.
427		*
428	<	* @return the first element of this deque, or <tt>null</tt> if
429	<	*     this deque is empty
428	>	* @param e the element to add
429	>	* @return {@code true} (as specified by {@link Queue#offer})
430	>	* @throws NullPointerException if the specified element is null
431		*/
432	<	public E poll() {
433	<	return pollFirst();
432	>	public boolean offer(E e) {
433	>	return offerLast(e);
434		}
435
436		/**
437		* Retrieves and removes the head of the queue represented by this deque.
438	<	* This method differs from the <tt>poll</tt> method in that it throws an
438	>	*
439	>	* This method differs from {@link #poll poll} only in that it throws an
440		* exception if this deque is empty.
441		*
442		* <p>This method is equivalent to {@link #removeFirst}.
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 remove() {
448		return removeFirst();
449		}
450
451		/**
452	<	* Retrieves, but does not remove, the head of the queue represented by
453	<	* this deque, returning <tt>null</tt> if this deque is empty.
452	>	* Retrieves and removes the head of the queue represented by this deque
453	>	* (in other words, the first element of this deque), or returns
454	>	* {@code null} if this deque is empty.
455		*
456	<	* <p>This method is equivalent to {@link #peekFirst}
456	>	* <p>This method is equivalent to {@link #pollFirst}.
457		*
458		* @return the head of the queue represented by this deque, or
459	<	*     <tt>null</tt> if this deque is empty
459	>	*         {@code null} if this deque is empty
460		*/
461	<	public E peek() {
462	<	return peekFirst();
461	>	public E poll() {
462	>	return pollFirst();
463		}
464
465		/**
466		* Retrieves, but does not remove, the head of the queue represented by
467	<	* this deque.  This method differs from the <tt>peek</tt> method only in
467	>	* this deque.  This method differs from {@link #peek peek} only in
468		* that it throws an exception if this deque is empty.
469		*
470	<	* <p>This method is equivalent to {@link #getFirst}
470	>	* <p>This method is equivalent to {@link #getFirst}.
471		*
472		* @return the head of the queue represented by this deque
473	<	* @throws NoSuchElementException if this deque is empty
473	>	* @throws NoSuchElementException {@inheritDoc}
474		*/
475		public E element() {
476		return getFirst();
477		}
478
479	+	/**
480	+	* Retrieves, but does not remove, the head of the queue represented by
481	+	* this deque, or returns {@code null} if this deque is empty.
482	+	*
483	+	* <p>This method is equivalent to {@link #peekFirst}.
484	+	*
485	+	* @return the head of the queue represented by this deque, or
486	+	*         {@code null} if this deque is empty
487	+	*/
488	+	public E peek() {
489	+	return peekFirst();
490	+	}
491	+
492		// *** Stack methods ***
493
494		/**
#	Line 499 | Line 498 | public class ArrayDeque<E> extends Abstr
498		* <p>This method is equivalent to {@link #addFirst}.
499		*
500		* @param e the element to push
501	<	* @throws NullPointerException if <tt>e</tt> is null
501	>	* @throws NullPointerException if the specified element is null
502		*/
503		public void push(E e) {
504		addFirst(e);
#	Line 512 | Line 511 | public class ArrayDeque<E> extends Abstr
511		* <p>This method is equivalent to {@link #removeFirst()}.
512		*
513		* @return the element at the front of this deque (which is the top
514	<	*     of the stack represented by this deque)
515	<	* @throws NoSuchElementException if this deque is empty
514	>	*         of the stack represented by this deque)
515	>	* @throws NoSuchElementException {@inheritDoc}
516		*/
517		public E pop() {
518		return removeFirst();
519		}
520
521	+	private void checkInvariants() {
522	+	assert elements[tail] == null;
523	+	assert head == tail ? elements[head] == null :
524	+	(elements[head] != null &&
525	+	elements[(tail - 1) & (elements.length - 1)] != null);
526	+	assert elements[(head - 1) & (elements.length - 1)] == null;
527	+	}
528	+
529		/**
530	<	* Remove the element at the specified position in the elements array,
531	<	* adjusting head, tail, and size as necessary.  This can result in
532	<	* motion of elements backwards or forwards in the array.
530	>	* Removes the element at the specified position in the elements array,
531	>	* adjusting head and tail as necessary.  This can result in motion of
532	>	* elements backwards or forwards in the array.
533		*
534		* <p>This method is called delete rather than remove to emphasize
535	<	* that its semantics differ from those of List.remove(int).
535	>	* that its semantics differ from those of {@link List#remove(int)}.
536		*
537		* @return true if elements moved backwards
538		*/
539		private boolean delete(int i) {
540	<	// Case 1: Deque doesn't wrap
541	<	// Case 2: Deque does wrap and removed element is in the head portion
542	<	if ((head < tail || tail == 0) || i >= head) {
543	<	System.arraycopy(elements, head, elements, head + 1, i - head);
544	<	elements[head] = null;
545	<	head = (head + 1) & (elements.length - 1);
540	>	checkInvariants();
541	>	final Object[] elements = this.elements;
542	>	final int mask = elements.length - 1;
543	>	final int h = head;
544	>	final int t = tail;
545	>	final int front = (i - h) & mask;
546	>	final int back  = (t - i) & mask;
547	>
548	>	// Invariant: head <= i < tail mod circularity
549	>	if (front >= ((t - h) & mask))
550	>	throw new ConcurrentModificationException();
551	>
552	>	// Optimize for least element motion
553	>	if (front < back) {
554	>	if (h <= i) {
555	>	System.arraycopy(elements, h, elements, h + 1, front);
556	>	} else { // Wrap around
557	>	System.arraycopy(elements, 0, elements, 1, i);
558	>	elements[0] = elements[mask];
559	>	System.arraycopy(elements, h, elements, h + 1, mask - h);
560	>	}
561	>	elements[h] = null;
562	>	head = (h + 1) & mask;
563		return false;
564	+	} else {
565	+	if (i < t) { // Copy the null tail as well
566	+	System.arraycopy(elements, i + 1, elements, i, back);
567	+	tail = t - 1;
568	+	} else { // Wrap around
569	+	System.arraycopy(elements, i + 1, elements, i, mask - i);
570	+	elements[mask] = elements[0];
571	+	System.arraycopy(elements, 1, elements, 0, t);
572	+	tail = (t - 1) & mask;
573	+	}
574	+	return true;
575		}
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;
576		}
577
578		// *** Collection Methods ***
#	Line 558 | Line 587 | public class ArrayDeque<E> extends Abstr
587		}
588
589		/**
590	<	* Returns <tt>true</tt> if this collection contains no elements.<p>
590	>	* Returns {@code true} if this deque contains no elements.
591		*
592	<	* @return <tt>true</tt> if this collection contains no elements.
592	>	* @return {@code true} if this deque contains no elements
593		*/
594		public boolean isEmpty() {
595		return head == tail;
#	Line 572 | Line 601 | public class ArrayDeque<E> extends Abstr
601		* order that elements would be dequeued (via successive calls to
602		* {@link #remove} or popped (via successive calls to {@link #pop}).
603		*
604	<	* @return an <tt>Iterator</tt> over the elements in this deque
604	>	* @return an iterator over the elements in this deque
605		*/
606		public Iterator<E> iterator() {
607		return new DeqIterator();
608		}
609
610	+	public Iterator<E> descendingIterator() {
611	+	return new DescendingIterator();
612	+	}
613	+
614		private class DeqIterator implements Iterator<E> {
615		/**
616		* Index of element to be returned by subsequent call to next.
#	Line 601 | Line 634 | public class ArrayDeque<E> extends Abstr
634		}
635
636		public E next() {
604	–	E result;
637		if (cursor == fence)
638		throw new NoSuchElementException();
639	+	@SuppressWarnings("unchecked")
640	+	E result = (E) elements[cursor];
641		// This check doesn't catch all possible comodifications,
642		// but does catch the ones that corrupt traversal
643	<	if (tail != fence || (result = elements[cursor]) == null)
643	>	if (tail != fence || result == null)
644		throw new ConcurrentModificationException();
645		lastRet = cursor;
646		cursor = (cursor + 1) & (elements.length - 1);
#	Line 616 | Line 650 | public class ArrayDeque<E> extends Abstr
650		public void remove() {
651		if (lastRet < 0)
652		throw new IllegalStateException();
653	<	if (delete(lastRet))
654	<	cursor--;
653	>	if (delete(lastRet)) { // if left-shifted, undo increment in next()
654	>	cursor = (cursor - 1) & (elements.length - 1);
655	>	fence = tail;
656	>	}
657	>	lastRet = -1;
658	>	}
659	>	}
660	>
661	>	private class DescendingIterator implements Iterator<E> {
662	>	/*
663	>	* This class is nearly a mirror-image of DeqIterator, using
664	>	* tail instead of head for initial cursor, and head instead of
665	>	* tail for fence.
666	>	*/
667	>	private int cursor = tail;
668	>	private int fence = head;
669	>	private int lastRet = -1;
670	>
671	>	public boolean hasNext() {
672	>	return cursor != fence;
673	>	}
674	>
675	>	public E next() {
676	>	if (cursor == fence)
677	>	throw new NoSuchElementException();
678	>	cursor = (cursor - 1) & (elements.length - 1);
679	>	@SuppressWarnings("unchecked")
680	>	E result = (E) elements[cursor];
681	>	if (head != fence || result == null)
682	>	throw new ConcurrentModificationException();
683	>	lastRet = cursor;
684	>	return result;
685	>	}
686	>
687	>	public void remove() {
688	>	if (lastRet < 0)
689	>	throw new IllegalStateException();
690	>	if (!delete(lastRet)) {
691	>	cursor = (cursor + 1) & (elements.length - 1);
692	>	fence = head;
693	>	}
694		lastRet = -1;
622	–	fence = tail;
695		}
696		}
697
698		/**
699	<	* Returns <tt>true</tt> if this deque contains the specified
700	<	* element.  More formally, returns <tt>true</tt> if and only if this
701	<	* deque contains at least one element <tt>e</tt> such that
630	<	* <tt>e.equals(o)</tt>.
699	>	* Returns {@code true} if this deque contains the specified element.
700	>	* More formally, returns {@code true} if and only if this deque contains
701	>	* at least one element {@code e} such that {@code o.equals(e)}.
702		*
703		* @param o object to be checked for containment in this deque
704	<	* @return <tt>true</tt> if this deque contains the specified element
704	>	* @return {@code true} if this deque contains the specified element
705		*/
706		public boolean contains(Object o) {
707		if (o == null)
708		return false;
709		int mask = elements.length - 1;
710		int i = head;
711	<	E x;
711	>	Object x;
712		while ( (x = elements[i]) != null) {
713		if (o.equals(x))
714		return true;
#	Line 648 | Line 719 | public class ArrayDeque<E> extends Abstr
719
720		/**
721		* Removes a single instance of the specified element from this deque.
722	<	* This method is equivalent to {@link #removeFirstOccurrence}.
722	>	* If the deque does not contain the element, it is unchanged.
723	>	* More formally, removes the first element {@code e} such that
724	>	* {@code o.equals(e)} (if such an element exists).
725	>	* Returns {@code true} if this deque contained the specified element
726	>	* (or equivalently, if this deque changed as a result of the call).
727	>	*
728	>	* <p>This method is equivalent to {@link #removeFirstOccurrence}.
729		*
730	<	* @param e element to be removed from this deque, if present
731	<	* @return <tt>true</tt> if this deque contained the specified element
730	>	* @param o element to be removed from this deque, if present
731	>	* @return {@code true} if this deque contained the specified element
732		*/
733	<	public boolean remove(Object e) {
734	<	return removeFirstOccurrence(e);
733	>	public boolean remove(Object o) {
734	>	return removeFirstOccurrence(o);
735		}
736
737		/**
738		* Removes all of the elements from this deque.
739	+	* The deque will be empty after this call returns.
740		*/
741		public void clear() {
742		int h = head;
#	Line 670 | Line 748 | public class ArrayDeque<E> extends Abstr
748		do {
749		elements[i] = null;
750		i = (i + 1) & mask;
751	<	} while(i != t);
751	>	} while (i != t);
752		}
753		}
754
755		/**
756		* Returns an array containing all of the elements in this deque
757	<	* in the correct order.
757	>	* in proper sequence (from first to last element).
758	>	*
759	>	* <p>The returned array will be "safe" in that no references to it are
760	>	* maintained by this deque.  (In other words, this method must allocate
761	>	* a new array).  The caller is thus free to modify the returned array.
762	>	*
763	>	* <p>This method acts as bridge between array-based and collection-based
764	>	* APIs.
765		*
766		* @return an array containing all of the elements in this deque
682	–	*         in the correct order
767		*/
768		public Object[] toArray() {
769	<	return copyElements(new Object[size()]);
769	>	return copyElements(new Object[size()]);
770		}
771
772		/**
773	<	* Returns an array containing all of the elements in this deque in the
774	<	* correct order; the runtime type of the returned array is that of the
775	<	* specified array.  If the deque fits in the specified array, it is
776	<	* returned therein.  Otherwise, a new array is allocated with the runtime
777	<	* type of the specified array and the size of this deque.
773	>	* Returns an array containing all of the elements in this deque in
774	>	* proper sequence (from first to last element); the runtime type of the
775	>	* returned array is that of the specified array.  If the deque fits in
776	>	* the specified array, it is returned therein.  Otherwise, a new array
777	>	* is allocated with the runtime type of the specified array and the
778	>	* size of this deque.
779		*
780	<	* <p>If the deque fits in the specified array with room to spare (i.e.,
781	<	* the array has more elements than the deque), the element in the array
782	<	* immediately following the end of the collection is set to <tt>null</tt>.
780	>	* <p>If this deque fits in the specified array with room to spare
781	>	* (i.e., the array has more elements than this deque), the element in
782	>	* the array immediately following the end of the deque is set to
783	>	* {@code null}.
784	>	*
785	>	* <p>Like the {@link #toArray()} method, this method acts as bridge between
786	>	* array-based and collection-based APIs.  Further, this method allows
787	>	* precise control over the runtime type of the output array, and may,
788	>	* under certain circumstances, be used to save allocation costs.
789	>	*
790	>	* <p>Suppose {@code x} is a deque known to contain only strings.
791	>	* The following code can be used to dump the deque into a newly
792	>	* allocated array of {@code String}:
793	>	*
794	>	*  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
795	>	*
796	>	* Note that {@code toArray(new Object[0])} is identical in function to
797	>	* {@code toArray()}.
798		*
799		* @param a the array into which the elements of the deque are to
800	<	*          be stored, if it is big enough; otherwise, a new array of the
801	<	*          same runtime type is allocated for this purpose
802	<	* @return an array containing the elements of the deque
803	<	* @throws ArrayStoreException if the runtime type of a is not a supertype
804	<	*         of the runtime type of every element in this deque
800	>	*          be stored, if it is big enough; otherwise, a new array of the
801	>	*          same runtime type is allocated for this purpose
802	>	* @return an array containing all of the elements in this deque
803	>	* @throws ArrayStoreException if the runtime type of the specified array
804	>	*         is not a supertype of the runtime type of every element in
805	>	*         this deque
806	>	* @throws NullPointerException if the specified array is null
807		*/
808	+	@SuppressWarnings("unchecked")
809		public <T> T[] toArray(T[] a) {
810		int size = size();
811		if (a.length < size)
812		a = (T[])java.lang.reflect.Array.newInstance(
813		a.getClass().getComponentType(), size);
814	<	copyElements(a);
814	>	copyElements(a);
815		if (a.length > size)
816		a[size] = null;
817		return a;
#	Line 723 | Line 826 | public class ArrayDeque<E> extends Abstr
826		*/
827		public ArrayDeque<E> clone() {
828		try {
829	+	@SuppressWarnings("unchecked")
830		ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
831	<	// 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);
831	>	result.elements = Arrays.copyOf(elements, elements.length);
832		return result;
731	–
833		} catch (CloneNotSupportedException e) {
834		throw new AssertionError();
835		}
836		}
837
737	–	/**
738	–	* Appease the serialization gods.
739	–	*/
838		private static final long serialVersionUID = 2340985798034038923L;
839
840		/**
841	<	* Serialize this deque.
841	>	* Saves this deque to a stream (that is, serializes it).
842		*
843	<	* @serialData The current size (<tt>int</tt>) of the deque,
843	>	* @serialData The current size ({@code int}) of the deque,
844		* followed by all of its elements (each an object reference) in
845		* first-to-last order.
846		*/
847	<	private void writeObject(ObjectOutputStream s) throws IOException {
847	>	private void writeObject(java.io.ObjectOutputStream s)
848	>	throws java.io.IOException {
849		s.defaultWriteObject();
850
851		// Write out size
852	<	int size = size();
754	<	s.writeInt(size);
852	>	s.writeInt(size());
853
854		// Write out elements in order.
757	–	int i = head;
855		int mask = elements.length - 1;
856	<	for (int j = 0; j < size; j++) {
856	>	for (int i = head; i != tail; i = (i + 1) & mask)
857		s.writeObject(elements[i]);
761	–	i = (i + 1) & mask;
762	–	}
858		}
859
860		/**
861	<	* Deserialize this deque.
861	>	* Reconstitutes this deque from a stream (that is, deserializes it).
862		*/
863	<	private void readObject(ObjectInputStream s)
864	<	throws IOException, ClassNotFoundException {
863	>	private void readObject(java.io.ObjectInputStream s)
864	>	throws java.io.IOException, ClassNotFoundException {
865		s.defaultReadObject();
866
867		// Read in size and allocate array
#	Line 777 | Line 872 | public class ArrayDeque<E> extends Abstr
872
873		// Read in all elements in the proper order.
874		for (int i = 0; i < size; i++)
875	<	elements[i] = (E)s.readObject();
875	>	elements[i] = s.readObject();
876	>	}
877
878	+	public Stream<E> stream() {
879	+	int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
880	+	return Streams.stream
881	+	(() -> new DeqSpliterator<E>(this, head, tail), flags);
882	+	}
883	+	public Stream<E> parallelStream() {
884	+	int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
885	+	return Streams.parallelStream
886	+	(() -> new DeqSpliterator<E>(this, head, tail), flags);
887		}
888	+
889	+
890	+	static final class DeqSpliterator<E> implements Spliterator<E>, Iterator<E> {
891	+	private final ArrayDeque<E> deq;
892	+	private final Object[] array;
893	+	private final int fence;  // initially tail
894	+	private int index;        // current index, modified on traverse/split
895	+
896	+	/** Create new spliterator covering the given array and range */
897	+	DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
898	+	this.deq = deq; this.array = deq.elements;
899	+	this.index = origin; this.fence = fence;
900	+	}
901	+
902	+	public DeqSpliterator<E> trySplit() {
903	+	int n = array.length;
904	+	int h = index, t = fence;
905	+	if (h != t && ((h + 1) & (n - 1)) != t) {
906	+	if (h > t)
907	+	t += n;
908	+	int m = ((h + t) >>> 1) & (n - 1);
909	+	return new DeqSpliterator<E>(deq, h, index = m);
910	+	}
911	+	return null;
912	+	}
913	+
914	+	@SuppressWarnings("unchecked")
915	+	public void forEach(Block<? super E> block) {
916	+	if (block == null)
917	+	throw new NullPointerException();
918	+	Object[] a = array;
919	+	if (a != deq.elements)
920	+	throw new ConcurrentModificationException();
921	+	int m = a.length - 1, f = fence, i = index;
922	+	index = f;
923	+	while (i != f) {
924	+	Object e = a[i];
925	+	if (e == null)
926	+	throw new ConcurrentModificationException();
927	+	block.accept((E)e);
928	+	i = (i + 1) & m;
929	+	}
930	+	}
931	+
932	+	@SuppressWarnings("unchecked")
933	+	public boolean tryAdvance(Block<? super E> block) {
934	+	if (block == null)
935	+	throw new NullPointerException();
936	+	Object[] a = array;
937	+	if (a != deq.elements)
938	+	throw new ConcurrentModificationException();
939	+	int m = a.length - 1, i = index;
940	+	if (i != fence) {
941	+	Object e = a[i];
942	+	if (e == null)
943	+	throw new ConcurrentModificationException();
944	+	block.accept((E)e);
945	+	index = (i + 1) & m;
946	+	return true;
947	+	}
948	+	return false;
949	+	}
950	+
951	+	// Iterator support
952	+	public Iterator<E> iterator() {
953	+	return this;
954	+	}
955	+
956	+	public boolean hasNext() {
957	+	return index >= 0 && index != fence;
958	+	}
959	+
960	+	@SuppressWarnings("unchecked")
961	+	public E next() {
962	+	if (index < 0 || index == fence)
963	+	throw new NoSuchElementException();
964	+	Object[] a = array;
965	+	if (a != deq.elements)
966	+	throw new ConcurrentModificationException();
967	+	Object e = a[index];
968	+	if (e == null)
969	+	throw new ConcurrentModificationException();
970	+	index = (index + 1) & (a.length - 1);
971	+	return (E) e;
972	+	}
973	+
974	+	public void remove() { throw new UnsupportedOperationException(); }
975	+
976	+	// Other spliterator methods
977	+	public long estimateSize() {
978	+	int n = fence - index;
979	+	if (n < 0)
980	+	n += array.length;
981	+	return (long)n;
982	+	}
983	+	public boolean hasExactSize() { return true; }
984	+	public boolean hasExactSplits() { return true; }
985	+	}
986	+
987		}

Diff Legend

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