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.64 by dl, Mon Feb 23 19:54:04 2015 UTC vs.
Revision 1.79 by jsr166, Tue Oct 18 20:32:55 2016 UTC

#	Line 7 | Line 7 | package java.util;
7
8		import java.io.Serializable;
9		import java.util.function.Consumer;
10	+	import java.util.function.Predicate;
11	+	import java.util.function.UnaryOperator;
12
13		/**
14		* Resizable-array implementation of the {@link Deque} interface.  Array
#	Line 52 | Line 54 | import java.util.function.Consumer;
54		* Java Collections Framework</a>.
55		*
56		* @author  Josh Bloch and Doug Lea
55	–	* @since   1.6
57		* @param <E> the type of elements held in this deque
58	+	* @since   1.6
59		*/
60		public class ArrayDeque<E> extends AbstractCollection<E>
61		implements Deque<E>, Cloneable, Serializable
62		{
63		/**
64		* The array in which the elements of the deque are stored.
65	<	* The capacity of the deque is the length of this array, which is
66	<	* always a power of two. The array is never allowed to become
65	<	* full, except transiently within an addX method where it is
66	<	* resized (see doubleCapacity) immediately upon becoming full,
67	<	* thus avoiding head and tail wrapping around to equal each
68	<	* other.  We also guarantee that all array cells not holding
69	<	* deque elements are always null.
65	>	* We guarantee that all array cells not holding deque elements
66	>	* are always null.
67		*/
68	<	transient Object[] elements; // non-private to simplify nested class access
68	>	transient Object[] elements;
69
70		/**
71		* The index of the element at the head of the deque (which is the
72		* element that would be removed by remove() or pop()); or an
73	<	* arbitrary number equal to tail if the deque is empty.
73	>	* arbitrary number 0 <= head < elements.length if the deque is empty.
74		*/
75		transient int head;
76
77	+	/** Number of elements in this collection. */
78	+	transient int size;
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)).
81	>	* The maximum size of array to allocate.
82	>	* Some VMs reserve some header words in an array.
83	>	* Attempts to allocate larger arrays may result in
84	>	* OutOfMemoryError: Requested array size exceeds VM limit
85		*/
86	<	transient int tail;
86	>	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
87
88		/**
89	<	* The minimum capacity that we'll use for a newly created deque.
90	<	* Must be a power of 2.
89	>	* Increases the capacity of this deque by at least the given amount.
90	>	*
91	>	* @param needed the required minimum extra capacity; must be positive
92		*/
93	<	private static final int MIN_INITIAL_CAPACITY = 8;
93	>	private void grow(int needed) {
94	>	// overflow-conscious code
95	>	// checkInvariants();
96	>	int oldCapacity = elements.length;
97	>	int newCapacity;
98	>	// Double size if small; else grow by 50%
99	>	int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
100	>	if (jump < needed
101	>	|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
102	>	newCapacity = newCapacity(needed, jump);
103	>	elements = Arrays.copyOf(elements, newCapacity);
104	>	if (oldCapacity - head < size) {
105	>	// wrap around; slide first leg forward to end of array
106	>	int newSpace = newCapacity - oldCapacity;
107	>	System.arraycopy(elements, head,
108	>	elements, head + newSpace,
109	>	oldCapacity - head);
110	>	Arrays.fill(elements, head, head + newSpace, null);
111	>	head += newSpace;
112	>	}
113	>	// checkInvariants();
114	>	}
115
116	<	// ******  Array allocation and resizing utilities ******
116	>	/** Capacity calculation for edge conditions, especially overflow. */
117	>	private int newCapacity(int needed, int jump) {
118	>	int oldCapacity = elements.length;
119	>	int minCapacity;
120	>	if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
121	>	if (minCapacity < 0)
122	>	throw new IllegalStateException("Sorry, deque too big");
123	>	return Integer.MAX_VALUE;
124	>	}
125	>	if (needed > jump)
126	>	return minCapacity;
127	>	return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
128	>	? oldCapacity + jump
129	>	: MAX_ARRAY_SIZE;
130	>	}
131
132		/**
133	<	* Allocates empty array to hold the given number of elements.
133	>	* Increases the internal storage of this collection, if necessary,
134	>	* to ensure that it can hold at least the given number of elements.
135		*
136	<	* @param numElements  the number of elements to hold
136	>	* @param minCapacity the desired minimum capacity
137		*/
138	<	private void allocateElements(int numElements) {
139	<	int initialCapacity = MIN_INITIAL_CAPACITY;
140	<	// Find the best power of two to hold elements.
141	<	// Tests "<=" because arrays aren't kept full.
103	<	if (numElements >= initialCapacity) {
104	<	initialCapacity = numElements;
105	<	initialCapacity |= (initialCapacity >>>  1);
106	<	initialCapacity |= (initialCapacity >>>  2);
107	<	initialCapacity |= (initialCapacity >>>  4);
108	<	initialCapacity |= (initialCapacity >>>  8);
109	<	initialCapacity |= (initialCapacity >>> 16);
110	<	initialCapacity++;
111	<
112	<	if (initialCapacity < 0)   // Too many elements, must back off
113	<	initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
114	<	}
115	<	elements = new Object[initialCapacity];
138	>	/* TODO: public */ private void ensureCapacity(int minCapacity) {
139	>	if (minCapacity > elements.length)
140	>	grow(minCapacity - elements.length);
141	>	// checkInvariants();
142		}
143
144		/**
145	<	* Doubles the capacity of this deque.  Call only when full, i.e.,
120	<	* when head and tail have wrapped around to become equal.
145	>	* Minimizes the internal storage of this collection.
146		*/
147	<	private void doubleCapacity() {
148	<	assert head == tail;
149	<	int p = head;
150	<	int n = elements.length;
151	<	int r = n - p; // number of elements to the right of p
152	<	int newCapacity = n << 1;
128	<	if (newCapacity < 0)
129	<	throw new IllegalStateException("Sorry, deque too big");
130	<	Object[] a = new Object[newCapacity];
131	<	System.arraycopy(elements, p, a, 0, r);
132	<	System.arraycopy(elements, 0, a, r, p);
133	<	elements = a;
134	<	head = 0;
135	<	tail = n;
147	>	/* TODO: public */ private void trimToSize() {
148	>	if (size < elements.length) {
149	>	elements = toArray();
150	>	head = 0;
151	>	}
152	>	// checkInvariants();
153		}
154
155		/**
#	Line 147 | Line 164 | public class ArrayDeque<E> extends Abstr
164		* Constructs an empty array deque with an initial capacity
165		* sufficient to hold the specified number of elements.
166		*
167	<	* @param numElements  lower bound on initial capacity of the deque
167	>	* @param numElements lower bound on initial capacity of the deque
168		*/
169		public ArrayDeque(int numElements) {
170	<	allocateElements(numElements);
170	>	elements = new Object[numElements];
171		}
172
173		/**
#	Line 164 | Line 181 | public class ArrayDeque<E> extends Abstr
181		* @throws NullPointerException if the specified collection is null
182		*/
183		public ArrayDeque(Collection<? extends E> c) {
184	<	allocateElements(c.size());
185	<	addAll(c);
184	>	Object[] elements = c.toArray();
185	>	// defend against c.toArray (incorrectly) not returning Object[]
186	>	// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
187	>	if (elements.getClass() != Object[].class)
188	>	elements = Arrays.copyOf(elements, size, Object[].class);
189	>	for (Object obj : elements)
190	>	Objects.requireNonNull(obj);
191	>	size = elements.length;
192	>	this.elements = elements;
193	>	}
194	>
195	>	/**
196	>	* Increments i, mod modulus.
197	>	* Precondition and postcondition: 0 <= i < modulus.
198	>	*/
199	>	static final int inc(int i, int modulus) {
200	>	if (++i == modulus) i = 0;
201	>	return i;
202	>	}
203	>
204	>	/**
205	>	* Decrements i, mod modulus.
206	>	* Precondition and postcondition: 0 <= i < modulus.
207	>	*/
208	>	static final int dec(int i, int modulus) {
209	>	if (--i < 0) i += modulus;
210	>	return i;
211	>	}
212	>
213	>	/**
214	>	* Adds i and j, mod modulus.
215	>	* Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
216	>	*/
217	>	static final int add(int i, int j, int modulus) {
218	>	if ((i += j) - modulus >= 0) i -= modulus;
219	>	return i;
220	>	}
221	>
222	>	/**
223	>	* Returns the array index of the last element.
224	>	* May return invalid index -1 if there are no elements.
225	>	*/
226	>	final int tail() {
227	>	return add(head, size - 1, elements.length);
228	>	}
229	>
230	>	/**
231	>	* Returns element at array index i.
232	>	*/
233	>	@SuppressWarnings("unchecked")
234	>	final E elementAt(int i) {
235	>	return (E) elements[i];
236	>	}
237	>
238	>	/**
239	>	* A version of elementAt that checks for null elements.
240	>	* This check doesn't catch all possible comodifications,
241	>	* but does catch ones that corrupt traversal.
242	>	*/
243	>	E checkedElementAt(Object[] elements, int i) {
244	>	@SuppressWarnings("unchecked") E e = (E) elements[i];
245	>	if (e == null)
246	>	throw new ConcurrentModificationException();
247	>	return e;
248		}
249
250		// The main insertion and extraction methods are addFirst,
#	Line 179 | Line 258 | public class ArrayDeque<E> extends Abstr
258		* @throws NullPointerException if the specified element is null
259		*/
260		public void addFirst(E e) {
261	<	if (e == null)
262	<	throw new NullPointerException();
263	<	elements[head = (head - 1) & (elements.length - 1)] = e;
264	<	if (head == tail)
265	<	doubleCapacity();
261	>	// checkInvariants();
262	>	Objects.requireNonNull(e);
263	>	Object[] elements;
264	>	int capacity, s = size;
265	>	while (s == (capacity = (elements = this.elements).length))
266	>	grow(1);
267	>	elements[head = dec(head, capacity)] = e;
268	>	size = s + 1;
269		}
270
271		/**
#	Line 195 | Line 277 | public class ArrayDeque<E> extends Abstr
277		* @throws NullPointerException if the specified element is null
278		*/
279		public void addLast(E e) {
280	<	if (e == null)
281	<	throw new NullPointerException();
282	<	elements[tail] = e;
283	<	if ( (tail = (tail + 1) & (elements.length - 1)) == head)
284	<	doubleCapacity();
280	>	// checkInvariants();
281	>	Objects.requireNonNull(e);
282	>	Object[] elements;
283	>	int capacity, s = size;
284	>	while (s == (capacity = (elements = this.elements).length))
285	>	grow(1);
286	>	elements[add(head, s, capacity)] = e;
287	>	size = s + 1;
288	>	}
289	>
290	>	/**
291	>	* Adds all of the elements in the specified collection at the end
292	>	* of this deque, as if by calling {@link #addLast} on each one,
293	>	* in the order that they are returned by the collection's
294	>	* iterator.
295	>	*
296	>	* @param c the elements to be inserted into this deque
297	>	* @return {@code true} if this deque changed as a result of the call
298	>	* @throws NullPointerException if the specified collection or any
299	>	*         of its elements are null
300	>	*/
301	>	@Override
302	>	public boolean addAll(Collection<? extends E> c) {
303	>	// checkInvariants();
304	>	Object[] a, elements;
305	>	int newcomers, capacity, s = size;
306	>	if ((newcomers = (a = c.toArray()).length) == 0)
307	>	return false;
308	>	while ((capacity = (elements = this.elements).length) - s < newcomers)
309	>	grow(newcomers - (capacity - s));
310	>	int i = add(head, s, capacity);
311	>	for (Object x : a) {
312	>	Objects.requireNonNull(x);
313	>	elements[i] = x;
314	>	i = inc(i, capacity);
315	>	size++;
316	>	}
317	>	return true;
318		}
319
320		/**
#	Line 230 | Line 345 | public class ArrayDeque<E> extends Abstr
345		* @throws NoSuchElementException {@inheritDoc}
346		*/
347		public E removeFirst() {
348	+	// checkInvariants();
349		E x = pollFirst();
350		if (x == null)
351		throw new NoSuchElementException();
#	Line 240 | Line 356 | public class ArrayDeque<E> extends Abstr
356		* @throws NoSuchElementException {@inheritDoc}
357		*/
358		public E removeLast() {
359	+	// checkInvariants();
360		E x = pollLast();
361		if (x == null)
362		throw new NoSuchElementException();
#	Line 247 | Line 364 | public class ArrayDeque<E> extends Abstr
364		}
365
366		public E pollFirst() {
367	<	int h = head;
368	<	@SuppressWarnings("unchecked")
369	<	E result = (E) elements[h];
253	<	// Element is null if deque empty
254	<	if (result == null)
367	>	// checkInvariants();
368	>	final int s, h;
369	>	if ((s = size) == 0)
370		return null;
371	<	elements[h] = null;     // Must null out slot
372	<	head = (h + 1) & (elements.length - 1);
373	<	return result;
371	>	final Object[] elements = this.elements;
372	>	@SuppressWarnings("unchecked") E e = (E) elements[h = head];
373	>	elements[h] = null;
374	>	head = inc(h, elements.length);
375	>	size = s - 1;
376	>	return e;
377		}
378
379		public E pollLast() {
380	<	int t = (tail - 1) & (elements.length - 1);
381	<	@SuppressWarnings("unchecked")
382	<	E result = (E) elements[t];
265	<	if (result == null)
380	>	// checkInvariants();
381	>	final int s, tail;
382	>	if ((s = size) == 0)
383		return null;
384	<	elements[t] = null;
385	<	tail = t;
386	<	return result;
384	>	final Object[] elements = this.elements;
385	>	@SuppressWarnings("unchecked")
386	>	E e = (E) elements[tail = add(head, s - 1, elements.length)];
387	>	elements[tail] = null;
388	>	size = s - 1;
389	>	return e;
390		}
391
392		/**
393		* @throws NoSuchElementException {@inheritDoc}
394		*/
395		public E getFirst() {
396	<	@SuppressWarnings("unchecked")
397	<	E result = (E) elements[head];
398	<	if (result == null)
279	<	throw new NoSuchElementException();
280	<	return result;
396	>	// checkInvariants();
397	>	if (size == 0) throw new NoSuchElementException();
398	>	return elementAt(head);
399		}
400
401		/**
402		* @throws NoSuchElementException {@inheritDoc}
403		*/
404		public E getLast() {
405	<	@SuppressWarnings("unchecked")
406	<	E result = (E) elements[(tail - 1) & (elements.length - 1)];
407	<	if (result == null)
290	<	throw new NoSuchElementException();
291	<	return result;
405	>	// checkInvariants();
406	>	if (size == 0) throw new NoSuchElementException();
407	>	return elementAt(tail());
408		}
409
294	–	@SuppressWarnings("unchecked")
410		public E peekFirst() {
411	<	// elements[head] is null if deque empty
412	<	return (E) elements[head];
411	>	// checkInvariants();
412	>	return (size == 0) ? null : elementAt(head);
413		}
414
300	–	@SuppressWarnings("unchecked")
415		public E peekLast() {
416	<	return (E) elements[(tail - 1) & (elements.length - 1)];
416	>	// checkInvariants();
417	>	return (size == 0) ? null : elementAt(tail());
418		}
419
420		/**
#	Line 315 | Line 430 | public class ArrayDeque<E> extends Abstr
430		* @return {@code true} if the deque contained the specified element
431		*/
432		public boolean removeFirstOccurrence(Object o) {
433	+	// checkInvariants();
434		if (o != null) {
435	<	int mask = elements.length - 1;
436	<	int i = head;
437	<	for (Object x; (x = elements[i]) != null; i = (i + 1) & mask) {
438	<	if (o.equals(x)) {
435	>	final Object[] elements = this.elements;
436	>	final int capacity = elements.length;
437	>	for (int k = size, i = head; --k >= 0; i = inc(i, capacity)) {
438	>	if (o.equals(elements[i])) {
439		delete(i);
440		return true;
441		}
#	Line 342 | Line 458 | public class ArrayDeque<E> extends Abstr
458		*/
459		public boolean removeLastOccurrence(Object o) {
460		if (o != null) {
461	<	int mask = elements.length - 1;
462	<	int i = (tail - 1) & mask;
463	<	for (Object x; (x = elements[i]) != null; i = (i - 1) & mask) {
464	<	if (o.equals(x)) {
461	>	final Object[] elements = this.elements;
462	>	final int capacity = elements.length;
463	>	for (int k = size, i = add(head, k - 1, capacity);
464	>	--k >= 0; i = dec(i, capacity)) {
465	>	if (o.equals(elements[i])) {
466		delete(i);
467		return true;
468		}
#	Line 468 | Line 585 | public class ArrayDeque<E> extends Abstr
585		return removeFirst();
586		}
587
471	–	private void checkInvariants() {
472	–	assert elements[tail] == null;
473	–	assert head == tail ? elements[head] == null :
474	–	(elements[head] != null &&
475	–	elements[(tail - 1) & (elements.length - 1)] != null);
476	–	assert elements[(head - 1) & (elements.length - 1)] == null;
477	–	}
478	–
588		/**
589	<	* Removes the element at the specified position in the elements array,
590	<	* adjusting head and tail as necessary.  This can result in motion of
591	<	* elements backwards or forwards in the array.
589	>	* Removes the element at the specified position in the elements array.
590	>	* This can result in forward or backwards motion of array elements.
591	>	* We optimize for least element motion.
592		*
593		* <p>This method is called delete rather than remove to emphasize
594		* that its semantics differ from those of {@link List#remove(int)}.
595		*
596		* @return true if elements moved backwards
597		*/
598	<	private boolean delete(int i) {
599	<	checkInvariants();
598	>	boolean delete(int i) {
599	>	// checkInvariants();
600		final Object[] elements = this.elements;
601	<	final int mask = elements.length - 1;
601	>	final int capacity = elements.length;
602		final int h = head;
603	<	final int t = tail;
604	<	final int front = (i - h) & mask;
605	<	final int back  = (t - i) & mask;
497	<
498	<	// Invariant: head <= i < tail mod circularity
499	<	if (front >= ((t - h) & mask))
500	<	throw new ConcurrentModificationException();
501	<
502	<	// Optimize for least element motion
603	>	int front;              // number of elements before to-be-deleted elt
604	>	if ((front = i - h) < 0) front += capacity;
605	>	final int back = size - front - 1; // number of elements after
606		if (front < back) {
607	+	// move front elements forwards
608		if (h <= i) {
609		System.arraycopy(elements, h, elements, h + 1, front);
610		} else { // Wrap around
611		System.arraycopy(elements, 0, elements, 1, i);
612	<	elements[0] = elements[mask];
613	<	System.arraycopy(elements, h, elements, h + 1, mask - h);
612	>	elements[0] = elements[capacity - 1];
613	>	System.arraycopy(elements, h, elements, h + 1, front - (i + 1));
614		}
615		elements[h] = null;
616	<	head = (h + 1) & mask;
616	>	head = inc(h, capacity);
617	>	size--;
618	>	// checkInvariants();
619		return false;
620		} else {
621	<	if (i < t) { // Copy the null tail as well
621	>	// move back elements backwards
622	>	int tail = tail();
623	>	if (i <= tail) {
624		System.arraycopy(elements, i + 1, elements, i, back);
517	–	tail = t - 1;
625		} else { // Wrap around
626	<	System.arraycopy(elements, i + 1, elements, i, mask - i);
627	<	elements[mask] = elements[0];
628	<	System.arraycopy(elements, 1, elements, 0, t);
629	<	tail = (t - 1) & mask;
626	>	int firstLeg = capacity - (i + 1);
627	>	System.arraycopy(elements, i + 1, elements, i, firstLeg);
628	>	elements[capacity - 1] = elements[0];
629	>	System.arraycopy(elements, 1, elements, 0, back - firstLeg - 1);
630		}
631	+	elements[tail] = null;
632	+	size--;
633	+	// checkInvariants();
634		return true;
635		}
636		}
#	Line 533 | Line 643 | public class ArrayDeque<E> extends Abstr
643		* @return the number of elements in this deque
644		*/
645		public int size() {
646	<	return (tail - head) & (elements.length - 1);
646	>	return size;
647		}
648
649		/**
#	Line 542 | Line 652 | public class ArrayDeque<E> extends Abstr
652		* @return {@code true} if this deque contains no elements
653		*/
654		public boolean isEmpty() {
655	<	return head == tail;
655	>	return size == 0;
656		}
657
658		/**
#	Line 562 | Line 672 | public class ArrayDeque<E> extends Abstr
672		}
673
674		private class DeqIterator implements Iterator<E> {
675	<	/**
676	<	* Index of element to be returned by subsequent call to next.
567	<	*/
568	<	private int cursor = head;
675	>	/** Index of element to be returned by subsequent call to next. */
676	>	int cursor;
677
678	<	/**
679	<	* Tail recorded at construction (also in remove), to stop
572	<	* iterator and also to check for comodification.
573	<	*/
574	<	private int fence = tail;
678	>	/** Number of elements yet to be returned. */
679	>	int remaining = size;
680
681		/**
682		* Index of element returned by most recent call to next.
683		* Reset to -1 if element is deleted by a call to remove.
684		*/
685	<	private int lastRet = -1;
685	>	int lastRet = -1;
686	>
687	>	DeqIterator() { cursor = head; }
688	>
689	>	int advance(int i, int modulus) {
690	>	return inc(i, modulus);
691	>	}
692	>
693	>	void doRemove() {
694	>	if (delete(lastRet))
695	>	// if left-shifted, undo advance in next()
696	>	cursor = dec(cursor, elements.length);
697	>	}
698
699	<	public boolean hasNext() {
700	<	return cursor != fence;
699	>	public final boolean hasNext() {
700	>	return remaining > 0;
701		}
702
703	<	public E next() {
704	<	if (cursor == fence)
703	>	public final E next() {
704	>	if (remaining == 0)
705		throw new NoSuchElementException();
706	<	@SuppressWarnings("unchecked")
590	<	E result = (E) elements[cursor];
591	<	// This check doesn't catch all possible comodifications,
592	<	// but does catch the ones that corrupt traversal
593	<	if (tail != fence || result == null)
594	<	throw new ConcurrentModificationException();
706	>	E e = checkedElementAt(elements, cursor);
707		lastRet = cursor;
708	<	cursor = (cursor + 1) & (elements.length - 1);
709	<	return result;
708	>	cursor = advance(cursor, elements.length);
709	>	remaining--;
710	>	return e;
711		}
712
713	<	public void remove() {
713	>	public final void remove() {
714		if (lastRet < 0)
715		throw new IllegalStateException();
716	<	if (delete(lastRet)) { // if left-shifted, undo increment in next()
604	<	cursor = (cursor - 1) & (elements.length - 1);
605	<	fence = tail;
606	<	}
716	>	doRemove();
717		lastRet = -1;
718		}
719	+
720	+	public final void forEachRemaining(Consumer<? super E> action) {
721	+	Objects.requireNonNull(action);
722	+	final Object[] elements = ArrayDeque.this.elements;
723	+	final int capacity = elements.length;
724	+	int k = remaining;
725	+	remaining = 0;
726	+	for (int i = cursor; --k >= 0; i = advance(i, capacity))
727	+	action.accept(checkedElementAt(elements, i));
728	+	}
729	+	}
730	+
731	+	private class DescendingIterator extends DeqIterator {
732	+	DescendingIterator() { cursor = tail(); }
733	+
734	+	@Override int advance(int i, int modulus) {
735	+	return dec(i, modulus);
736	+	}
737	+
738	+	@Override void doRemove() {
739	+	if (!delete(lastRet))
740	+	// if right-shifted, undo advance in next
741	+	cursor = inc(cursor, elements.length);
742	+	}
743		}
744
745		/**
746	<	* This class is nearly a mirror-image of DeqIterator, using tail
747	<	* instead of head for initial cursor, and head instead of tail
748	<	* for fence.
746	>	* Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
747	>	* and <em>fail-fast</em> {@link Spliterator} over the elements in this
748	>	* deque.
749	>	*
750	>	* <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
751	>	* {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
752	>	* {@link Spliterator#NONNULL}.  Overriding implementations should document
753	>	* the reporting of additional characteristic values.
754	>	*
755	>	* @return a {@code Spliterator} over the elements in this deque
756	>	* @since 1.8
757		*/
758	<	private class DescendingIterator implements Iterator<E> {
759	<	private int cursor = tail;
760	<	private int fence = head;
761	<	private int lastRet = -1;
758	>	public Spliterator<E> spliterator() {
759	>	return new ArrayDequeSpliterator();
760	>	}
761	>
762	>	final class ArrayDequeSpliterator implements Spliterator<E> {
763	>	private int cursor;
764	>	private int remaining; // -1 until late-binding first use
765
766	<	public boolean hasNext() {
767	<	return cursor != fence;
766	>	/** Constructs late-binding spliterator over all elements. */
767	>	ArrayDequeSpliterator() {
768	>	this.remaining = -1;
769		}
770
771	<	public E next() {
772	<	if (cursor == fence)
773	<	throw new NoSuchElementException();
774	<	cursor = (cursor - 1) & (elements.length - 1);
629	<	@SuppressWarnings("unchecked")
630	<	E result = (E) elements[cursor];
631	<	if (head != fence || result == null)
632	<	throw new ConcurrentModificationException();
633	<	lastRet = cursor;
634	<	return result;
771	>	/** Constructs spliterator over the given slice. */
772	>	ArrayDequeSpliterator(int cursor, int count) {
773	>	this.cursor = cursor;
774	>	this.remaining = count;
775		}
776
777	<	public void remove() {
778	<	if (lastRet < 0)
779	<	throw new IllegalStateException();
780	<	if (!delete(lastRet)) {
781	<	cursor = (cursor + 1) & (elements.length - 1);
642	<	fence = head;
777	>	/** Ensures late-binding initialization; then returns remaining. */
778	>	private int remaining() {
779	>	if (remaining < 0) {
780	>	cursor = head;
781	>	remaining = size;
782		}
783	<	lastRet = -1;
783	>	return remaining;
784	>	}
785	>
786	>	public ArrayDequeSpliterator trySplit() {
787	>	final int mid;
788	>	if ((mid = remaining() >> 1) > 0) {
789	>	int oldCursor = cursor;
790	>	cursor = add(cursor, mid, elements.length);
791	>	remaining -= mid;
792	>	return new ArrayDequeSpliterator(oldCursor, mid);
793	>	}
794	>	return null;
795	>	}
796	>
797	>	public void forEachRemaining(Consumer<? super E> action) {
798	>	Objects.requireNonNull(action);
799	>	final Object[] elements = ArrayDeque.this.elements;
800	>	final int capacity = elements.length;
801	>	int k = remaining();
802	>	remaining = 0;
803	>	for (int i = cursor; --k >= 0; i = inc(i, capacity))
804	>	action.accept(checkedElementAt(elements, i));
805	>	}
806	>
807	>	public boolean tryAdvance(Consumer<? super E> action) {
808	>	Objects.requireNonNull(action);
809	>	if (remaining() == 0)
810	>	return false;
811	>	action.accept(checkedElementAt(elements, cursor));
812	>	cursor = inc(cursor, elements.length);
813	>	remaining--;
814	>	return true;
815	>	}
816	>
817	>	public long estimateSize() {
818	>	return remaining();
819	>	}
820	>
821	>	public int characteristics() {
822	>	return Spliterator.NONNULL
823	>	| Spliterator.ORDERED
824	>	| Spliterator.SIZED
825	>	| Spliterator.SUBSIZED;
826	>	}
827	>	}
828	>
829	>	@Override
830	>	public void forEach(Consumer<? super E> action) {
831	>	// checkInvariants();
832	>	Objects.requireNonNull(action);
833	>	final Object[] elements = this.elements;
834	>	final int capacity = elements.length;
835	>	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
836	>	action.accept(elementAt(i));
837	>	// checkInvariants();
838	>	}
839	>
840	>	/**
841	>	* Replaces each element of this deque with the result of applying the
842	>	* operator to that element, as specified by {@link List#replaceAll}.
843	>	*
844	>	* @param operator the operator to apply to each element
845	>	*/
846	>	/* TODO: public */ private void replaceAll(UnaryOperator<E> operator) {
847	>	Objects.requireNonNull(operator);
848	>	final Object[] elements = this.elements;
849	>	final int capacity = elements.length;
850	>	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
851	>	elements[i] = operator.apply(elementAt(i));
852	>	// checkInvariants();
853	>	}
854	>
855	>	/**
856	>	* @throws NullPointerException {@inheritDoc}
857	>	*/
858	>	@Override
859	>	public boolean removeIf(Predicate<? super E> filter) {
860	>	Objects.requireNonNull(filter);
861	>	return bulkRemove(filter);
862	>	}
863	>
864	>	/**
865	>	* @throws NullPointerException {@inheritDoc}
866	>	*/
867	>	@Override
868	>	public boolean removeAll(Collection<?> c) {
869	>	Objects.requireNonNull(c);
870	>	return bulkRemove(e -> c.contains(e));
871	>	}
872	>
873	>	/**
874	>	* @throws NullPointerException {@inheritDoc}
875	>	*/
876	>	@Override
877	>	public boolean retainAll(Collection<?> c) {
878	>	Objects.requireNonNull(c);
879	>	return bulkRemove(e -> !c.contains(e));
880	>	}
881	>
882	>	/** Implementation of bulk remove methods. */
883	>	private boolean bulkRemove(Predicate<? super E> filter) {
884	>	// checkInvariants();
885	>	final Object[] elements = this.elements;
886	>	final int capacity = elements.length;
887	>	int i = head, j = i, remaining = size, deleted = 0;
888	>	try {
889	>	for (; remaining > 0; remaining--, i = inc(i, capacity)) {
890	>	@SuppressWarnings("unchecked") E e = (E) elements[i];
891	>	if (filter.test(e))
892	>	deleted++;
893	>	else {
894	>	if (j != i)
895	>	elements[j] = e;
896	>	j = inc(j, capacity);
897	>	}
898	>	}
899	>	return deleted > 0;
900	>	} catch (Throwable ex) {
901	>	if (deleted > 0)
902	>	for (; remaining > 0;
903	>	remaining--, i = inc(i, capacity), j = inc(j, capacity))
904	>	elements[j] = elements[i];
905	>	throw ex;
906	>	} finally {
907	>	size -= deleted;
908	>	for (; --deleted >= 0; j = inc(j, capacity))
909	>	elements[j] = null;
910	>	// checkInvariants();
911		}
912		}
913
#	Line 655 | Line 921 | public class ArrayDeque<E> extends Abstr
921		*/
922		public boolean contains(Object o) {
923		if (o != null) {
924	<	int mask = elements.length - 1;
925	<	int i = head;
926	<	for (Object x; (x = elements[i]) != null; i = (i + 1) & mask) {
927	<	if (o.equals(x))
924	>	final Object[] elements = this.elements;
925	>	final int capacity = elements.length;
926	>	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
927	>	if (o.equals(elements[i]))
928		return true;
663	–	}
929		}
930		return false;
931		}
#	Line 687 | Line 952 | public class ArrayDeque<E> extends Abstr
952		* The deque will be empty after this call returns.
953		*/
954		public void clear() {
955	<	int h = head;
956	<	int t = tail;
957	<	if (h != t) { // clear all cells
958	<	head = tail = 0;
959	<	int i = h;
960	<	int mask = elements.length - 1;
961	<	do {
962	<	elements[i] = null;
963	<	i = (i + 1) & mask;
699	<	} while (i != t);
955	>	final Object[] elements = this.elements;
956	>	final int capacity = elements.length;
957	>	final int h = this.head;
958	>	final int s = size;
959	>	if (capacity - h >= s)
960	>	Arrays.fill(elements, h, h + s, null);
961	>	else {
962	>	Arrays.fill(elements, h, capacity, null);
963	>	Arrays.fill(elements, 0, s - capacity + h, null);
964		}
965	+	size = head = 0;
966	+	// checkInvariants();
967		}
968
969		/**
#	Line 715 | Line 981 | public class ArrayDeque<E> extends Abstr
981		*/
982		public Object[] toArray() {
983		final int head = this.head;
984	<	final int tail = this.tail;
985	<	boolean wrap = (tail < head);
986	<	int end = wrap ? tail + elements.length : tail;
987	<	Object[] a = Arrays.copyOfRange(elements, head, end);
722	<	if (wrap)
723	<	System.arraycopy(elements, 0, a, elements.length - head, tail);
984	>	final int firstLeg;
985	>	Object[] a = Arrays.copyOfRange(elements, head, head + size);
986	>	if ((firstLeg = elements.length - head) < size)
987	>	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
988		return a;
989		}
990
#	Line 762 | Line 1026 | public class ArrayDeque<E> extends Abstr
1026		*/
1027		@SuppressWarnings("unchecked")
1028		public <T> T[] toArray(T[] a) {
1029	+	final Object[] elements = this.elements;
1030		final int head = this.head;
1031	<	final int tail = this.tail;
1032	<	boolean wrap = (tail < head);
1033	<	int size = (tail - head) + (wrap ? elements.length : 0);
769	<	int firstLeg = size - (wrap ? tail : 0);
770	<	int len = a.length;
771	<	if (size > len) {
1031	>	final int firstLeg;
1032	>	boolean wrap = (firstLeg = elements.length - head) < size;
1033	>	if (size > a.length) {
1034		a = (T[]) Arrays.copyOfRange(elements, head, head + size,
1035		a.getClass());
1036		} else {
1037	<	System.arraycopy(elements, head, a, 0, firstLeg);
1038	<	if (size < len)
1037	>	System.arraycopy(elements, head, a, 0, wrap ? firstLeg : size);
1038	>	if (size < a.length)
1039		a[size] = null;
1040		}
1041		if (wrap)
1042	<	System.arraycopy(elements, 0, a, firstLeg, tail);
1042	>	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1043		return a;
1044		}
1045
#	Line 815 | Line 1077 | public class ArrayDeque<E> extends Abstr
1077		s.defaultWriteObject();
1078
1079		// Write out size
1080	<	s.writeInt(size());
1080	>	s.writeInt(size);
1081
1082		// Write out elements in order.
1083	<	int mask = elements.length - 1;
1084	<	for (int i = head; i != tail; i = (i + 1) & mask)
1083	>	final Object[] elements = this.elements;
1084	>	final int capacity = elements.length;
1085	>	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
1086		s.writeObject(elements[i]);
1087		}
1088
#	Line 835 | Line 1098 | public class ArrayDeque<E> extends Abstr
1098		s.defaultReadObject();
1099
1100		// Read in size and allocate array
1101	<	int size = s.readInt();
839	<	allocateElements(size);
840	<	head = 0;
841	<	tail = size;
1101	>	elements = new Object[size = s.readInt()];
1102
1103		// Read in all elements in the proper order.
1104		for (int i = 0; i < size; i++)
1105		elements[i] = s.readObject();
1106		}
1107
1108	<	public Spliterator<E> spliterator() {
1109	<	return new DeqSpliterator<E>(this, -1, -1);
1110	<	}
1111	<
1112	<	static final class DeqSpliterator<E> implements Spliterator<E> {
1113	<	private final ArrayDeque<E> deq;
1114	<	private int fence;  // -1 until first use
1115	<	private int index;  // current index, modified on traverse/split
1116	<
1117	<	/** Creates new spliterator covering the given array and range */
1118	<	DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
1119	<	this.deq = deq;
1120	<	this.index = origin;
1121	<	this.fence = fence;
1122	<	}
1123	<
1124	<	private int getFence() { // force initialization
1125	<	int t;
866	<	if ((t = fence) < 0) {
867	<	t = fence = deq.tail;
868	<	index = deq.head;
869	<	}
870	<	return t;
871	<	}
872	<
873	<	public Spliterator<E> trySplit() {
874	<	int t = getFence(), h = index, n = deq.elements.length;
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<>(deq, h, index = m);
880	<	}
881	<	return null;
882	<	}
883	<
884	<	public void forEachRemaining(Consumer<? super E> consumer) {
885	<	if (consumer == null)
886	<	throw new NullPointerException();
887	<	Object[] a = deq.elements;
888	<	int m = a.length - 1, f = getFence(), 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	<	consumer.accept(e);
896	<	}
897	<	}
898	<
899	<	public boolean tryAdvance(Consumer<? super E> consumer) {
900	<	if (consumer == null)
901	<	throw new NullPointerException();
902	<	Object[] a = deq.elements;
903	<	int m = a.length - 1, f = getFence(), i = index;
904	<	if (i != f) {
905	<	@SuppressWarnings("unchecked") E e = (E)a[i];
906	<	index = (i + 1) & m;
907	<	if (e == null)
908	<	throw new ConcurrentModificationException();
909	<	consumer.accept(e);
910	<	return true;
911	<	}
912	<	return false;
913	<	}
914	<
915	<	public long estimateSize() {
916	<	int n = getFence() - index;
917	<	if (n < 0)
918	<	n += deq.elements.length;
919	<	return (long) n;
920	<	}
921	<
922	<	@Override
923	<	public int characteristics() {
924	<	return Spliterator.ORDERED | Spliterator.SIZED |
925	<	Spliterator.NONNULL | Spliterator.SUBSIZED;
1108	>	/** debugging */
1109	>	private void checkInvariants() {
1110	>	try {
1111	>	int capacity = elements.length;
1112	>	assert size >= 0 && size <= capacity;
1113	>	assert head >= 0 && ((capacity == 0 && head == 0 && size == 0)
1114	>	|| head < capacity);
1115	>	assert size == 0
1116	>	|| (elements[head] != null && elements[tail()] != null);
1117	>	assert size == capacity
1118	>	|| (elements[dec(head, capacity)] == null
1119	>	&& elements[inc(tail(), capacity)] == null);
1120	>	} catch (Throwable t) {
1121	>	System.err.printf("head=%d size=%d capacity=%d%n",
1122	>	head, size, elements.length);
1123	>	System.err.printf("elements=%s%n",
1124	>	Arrays.toString(elements));
1125	>	throw t;
1126		}
1127		}
1128

Diff Legend

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