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.77 by jsr166, Tue Oct 18 00:33:05 2016 UTC vs.
Revision 1.105 by jsr166, Tue Nov 1 21:42:45 2016 UTC

#	Line 90 | Line 90 | public class ArrayDeque<E> extends Abstr
90		*
91		* @param needed the required minimum extra capacity; must be positive
92		*/
93	<	private void grow(int needed) {
93	>	private Object[] grow(int needed) {
94		// overflow-conscious code
95		// checkInvariants();
96	<	int oldCapacity = elements.length;
96	>	final 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);
#	Line 110 | Line 110 | public class ArrayDeque<E> extends Abstr
110		Arrays.fill(elements, head, head + newSpace, null);
111		head += newSpace;
112		}
113	+	return elements;
114		// checkInvariants();
115		}
116
117		/** Capacity calculation for edge conditions, especially overflow. */
118		private int newCapacity(int needed, int jump) {
119	<	int oldCapacity = elements.length;
119	<	int minCapacity;
119	>	final int oldCapacity = elements.length, minCapacity;
120		if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
121		if (minCapacity < 0)
122		throw new IllegalStateException("Sorry, deque too big");
#	Line 134 | Line 134 | public class ArrayDeque<E> extends Abstr
134		* to ensure that it can hold at least the given number of elements.
135		*
136		* @param minCapacity the desired minimum capacity
137	<	* @since 9
137	>	* @since TBD
138		*/
139	<	public void ensureCapacity(int minCapacity) {
139	>	/* public */ void ensureCapacity(int minCapacity) {
140		if (minCapacity > elements.length)
141		grow(minCapacity - elements.length);
142		// checkInvariants();
#	Line 145 | Line 145 | public class ArrayDeque<E> extends Abstr
145		/**
146		* Minimizes the internal storage of this collection.
147		*
148	<	* @since 9
148	>	* @since TBD
149		*/
150	<	public void trimToSize() {
150	>	/* public */ void trimToSize() {
151		if (size < elements.length) {
152		elements = toArray();
153		head = 0;
#	Line 184 | Line 184 | public class ArrayDeque<E> extends Abstr
184		* @throws NullPointerException if the specified collection is null
185		*/
186		public ArrayDeque(Collection<? extends E> c) {
187	<	Object[] elements = c.toArray();
187	>	Object[] es = c.toArray();
188		// defend against c.toArray (incorrectly) not returning Object[]
189		// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
190	<	if (elements.getClass() != Object[].class)
191	<	elements = Arrays.copyOf(elements, size, Object[].class);
192	<	for (Object obj : elements)
190	>	if (es.getClass() != Object[].class)
191	>	es = Arrays.copyOf(es, es.length, Object[].class);
192	>	for (Object obj : es)
193		Objects.requireNonNull(obj);
194	<	size = elements.length;
195	<	this.elements = elements;
194	>	this.elements = es;
195	>	this.size = es.length;
196		}
197
198		/**
199	<	* Returns the array index of the last element.
200	<	* May return invalid index -1 if there are no elements.
199	>	* Increments i, mod modulus.
200	>	* Precondition and postcondition: 0 <= i < modulus.
201		*/
202	<	final int tail() {
203	<	return add(head, size - 1, elements.length);
202	>	static final int inc(int i, int modulus) {
203	>	if (++i >= modulus) i = 0;
204	>	return i;
205		}
206
207		/**
208	<	* Adds i and j, mod modulus.
209	<	* Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
208	>	* Decrements i, mod modulus.
209	>	* Precondition and postcondition: 0 <= i < modulus.
210		*/
211	<	static final int add(int i, int j, int modulus) {
212	<	if ((i += j) - modulus >= 0) i -= modulus;
211	>	static final int dec(int i, int modulus) {
212	>	if (--i < 0) i = modulus - 1;
213		return i;
214		}
215
216		/**
217	<	* Increments i, mod modulus.
218	<	* Precondition and postcondition: 0 <= i < modulus.
217	>	* Adds i and j, mod modulus.
218	>	* Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
219		*/
220	<	static final int inc(int i, int modulus) {
221	<	if (++i == modulus) i = 0;
220	>	static final int add(int i, int j, int modulus) {
221	>	if ((i += j) - modulus >= 0) i -= modulus;
222		return i;
223		}
224
225		/**
226	<	* Decrements i, mod modulus.
227	<	* Precondition and postcondition: 0 <= i < modulus.
226	>	* Returns the array index of the last element.
227	>	* May return invalid index -1 if there are no elements.
228		*/
229	<	static final int dec(int i, int modulus) {
230	<	if (--i < 0) i += modulus;
230	<	return i;
229	>	final int tail() {
230	>	return add(head, size - 1, elements.length);
231		}
232
233		/**
234		* Returns element at array index i.
235		*/
236		@SuppressWarnings("unchecked")
237	<	final E elementAt(int i) {
237	>	private E elementAt(int i) {
238		return (E) elements[i];
239		}
240
241		/**
242		* A version of elementAt that checks for null elements.
243		* This check doesn't catch all possible comodifications,
244	<	* but does catch ones that corrupt traversal.
244	>	* but does catch ones that corrupt traversal.  It's a little
245	>	* surprising that javac allows this abuse of generics.
246		*/
247	<	E checkedElementAt(Object[] elements, int i) {
248	<	@SuppressWarnings("unchecked") E e = (E) elements[i];
247	>	static final <E> E nonNullElementAt(Object[] es, int i) {
248	>	@SuppressWarnings("unchecked") E e = (E) es[i];
249		if (e == null)
250		throw new ConcurrentModificationException();
251		return e;
#	Line 263 | Line 264 | public class ArrayDeque<E> extends Abstr
264		public void addFirst(E e) {
265		// checkInvariants();
266		Objects.requireNonNull(e);
267	<	Object[] elements;
268	<	int capacity, s = size;
269	<	while (s == (capacity = (elements = this.elements).length))
270	<	grow(1);
271	<	elements[head = dec(head, capacity)] = e;
267	>	Object[] es;
268	>	int capacity, h;
269	>	final int s;
270	>	if ((s = size) == (capacity = (es = elements).length))
271	>	capacity = (es = grow(1)).length;
272	>	if ((h = head - 1) < 0) h = capacity - 1;
273	>	es[head = h] = e;
274		size = s + 1;
275	+	// checkInvariants();
276		}
277
278		/**
#	Line 282 | Line 286 | public class ArrayDeque<E> extends Abstr
286		public void addLast(E e) {
287		// checkInvariants();
288		Objects.requireNonNull(e);
289	<	Object[] elements;
290	<	int capacity, s = size;
291	<	while (s == (capacity = (elements = this.elements).length))
292	<	grow(1);
293	<	elements[add(head, s, capacity)] = e;
289	>	Object[] es;
290	>	int capacity;
291	>	final int s;
292	>	if ((s = size) == (capacity = (es = elements).length))
293	>	capacity = (es = grow(1)).length;
294	>	es[add(head, s, capacity)] = e;
295		size = s + 1;
296	+	// checkInvariants();
297		}
298
299		/**
#	Line 301 | Line 307 | public class ArrayDeque<E> extends Abstr
307		* @throws NullPointerException if the specified collection or any
308		*         of its elements are null
309		*/
304	–	@Override
310		public boolean addAll(Collection<? extends E> c) {
311	+	final int s = size, needed = c.size() - (elements.length - s);
312	+	if (needed > 0)
313	+	grow(needed);
314	+	c.forEach((e) -> addLast(e));
315		// checkInvariants();
316	<	Object[] a, elements;
308	<	int len, capacity, s = size;
309	<	if ((len = (a = c.toArray()).length) == 0)
310	<	return false;
311	<	while ((capacity = (elements = this.elements).length) - s < len)
312	<	grow(len - (capacity - s));
313	<	int i = add(head, s, capacity);
314	<	for (Object x : a) {
315	<	Objects.requireNonNull(x);
316	<	elements[i] = x;
317	<	i = inc(i, capacity);
318	<	size++;
319	<	}
320	<	return true;
316	>	return size > s;
317		}
318
319		/**
#	Line 349 | Line 345 | public class ArrayDeque<E> extends Abstr
345		*/
346		public E removeFirst() {
347		// checkInvariants();
348	<	E x = pollFirst();
349	<	if (x == null)
348	>	E e = pollFirst();
349	>	if (e == null)
350		throw new NoSuchElementException();
351	<	return x;
351	>	return e;
352		}
353
354		/**
#	Line 360 | Line 356 | public class ArrayDeque<E> extends Abstr
356		*/
357		public E removeLast() {
358		// checkInvariants();
359	<	E x = pollLast();
360	<	if (x == null)
359	>	E e = pollLast();
360	>	if (e == null)
361		throw new NoSuchElementException();
362	<	return x;
362	>	return e;
363		}
364
365		public E pollFirst() {
366		// checkInvariants();
367	<	final int s, h;
368	<	if ((s = size) == 0)
367	>	int s, h;
368	>	if ((s = size) <= 0)
369		return null;
370	<	final Object[] elements = this.elements;
371	<	@SuppressWarnings("unchecked") E e = (E) elements[h = head];
372	<	elements[h] = null;
373	<	head = inc(h, elements.length);
370	>	final Object[] es = elements;
371	>	@SuppressWarnings("unchecked") E e = (E) es[h = head];
372	>	es[h] = null;
373	>	if (++h >= es.length) h = 0;
374	>	head = h;
375		size = s - 1;
376		return e;
377		}
#	Line 382 | Line 379 | public class ArrayDeque<E> extends Abstr
379		public E pollLast() {
380		// checkInvariants();
381		final int s, tail;
382	<	if ((s = size) == 0)
382	>	if ((s = size) <= 0)
383		return null;
384	<	final Object[] elements = this.elements;
384	>	final Object[] es = elements;
385		@SuppressWarnings("unchecked")
386	<	E e = (E) elements[tail = add(head, s - 1, elements.length)];
387	<	elements[tail] = null;
386	>	E e = (E) es[tail = add(head, s - 1, es.length)];
387	>	es[tail] = null;
388		size = s - 1;
389		return e;
390		}
#	Line 397 | Line 394 | public class ArrayDeque<E> extends Abstr
394		*/
395		public E getFirst() {
396		// checkInvariants();
397	<	if (size == 0) throw new NoSuchElementException();
397	>	if (size <= 0) throw new NoSuchElementException();
398		return elementAt(head);
399		}
400
401		/**
402		* @throws NoSuchElementException {@inheritDoc}
403		*/
404	+	@SuppressWarnings("unchecked")
405		public E getLast() {
406		// checkInvariants();
407	<	if (size == 0) throw new NoSuchElementException();
408	<	return elementAt(tail());
407	>	final int s;
408	>	if ((s = size) <= 0) throw new NoSuchElementException();
409	>	final Object[] es = elements;
410	>	return (E) es[add(head, s - 1, es.length)];
411		}
412
413		public E peekFirst() {
414		// checkInvariants();
415	<	return (size == 0) ? null : elementAt(head);
415	>	return (size <= 0) ? null : elementAt(head);
416		}
417
418	+	@SuppressWarnings("unchecked")
419		public E peekLast() {
420		// checkInvariants();
421	<	return (size == 0) ? null : elementAt(tail());
421	>	final int s;
422	>	if ((s = size) <= 0) return null;
423	>	final Object[] es = elements;
424	>	return (E) es[add(head, s - 1, es.length)];
425		}
426
427		/**
#	Line 433 | Line 437 | public class ArrayDeque<E> extends Abstr
437		* @return {@code true} if the deque contained the specified element
438		*/
439		public boolean removeFirstOccurrence(Object o) {
436	–	// checkInvariants();
440		if (o != null) {
441	<	final Object[] elements = this.elements;
442	<	final int capacity = elements.length;
443	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity)) {
444	<	if (o.equals(elements[i])) {
445	<	delete(i);
446	<	return true;
447	<	}
441	>	final Object[] es = elements;
442	>	int i, end, to, todo;
443	>	todo = (end = (i = head) + size)
444	>	- (to = (es.length - end >= 0) ? end : es.length);
445	>	for (;; to = todo, todo = 0, i = 0) {
446	>	for (; i < to; i++)
447	>	if (o.equals(es[i])) {
448	>	delete(i);
449	>	return true;
450	>	}
451	>	if (todo == 0) break;
452		}
453		}
454		return false;
#	Line 461 | Line 468 | public class ArrayDeque<E> extends Abstr
468		*/
469		public boolean removeLastOccurrence(Object o) {
470		if (o != null) {
471	<	final Object[] elements = this.elements;
472	<	final int capacity = elements.length;
473	<	for (int k = size, i = add(head, k - 1, capacity);
474	<	--k >= 0; i = dec(i, capacity)) {
475	<	if (o.equals(elements[i])) {
476	<	delete(i);
477	<	return true;
478	<	}
471	>	final Object[] es = elements;
472	>	int i, to, end, todo;
473	>	todo = (to = ((end = (i = tail()) - size) >= -1) ? end : -1) - end;
474	>	for (;; to = (i = es.length - 1) - todo, todo = 0) {
475	>	for (; i > to; i--)
476	>	if (o.equals(es[i])) {
477	>	delete(i);
478	>	return true;
479	>	}
480	>	if (todo == 0) break;
481		}
482		}
483		return false;
#	Line 600 | Line 609 | public class ArrayDeque<E> extends Abstr
609		*/
610		boolean delete(int i) {
611		// checkInvariants();
612	<	final Object[] elements = this.elements;
613	<	final int capacity = elements.length;
612	>	final Object[] es = elements;
613	>	final int capacity = es.length;
614		final int h = head;
615		int front;              // number of elements before to-be-deleted elt
616		if ((front = i - h) < 0) front += capacity;
#	Line 609 | Line 618 | public class ArrayDeque<E> extends Abstr
618		if (front < back) {
619		// move front elements forwards
620		if (h <= i) {
621	<	System.arraycopy(elements, h, elements, h + 1, front);
621	>	System.arraycopy(es, h, es, h + 1, front);
622		} else { // Wrap around
623	<	System.arraycopy(elements, 0, elements, 1, i);
624	<	elements[0] = elements[capacity - 1];
625	<	System.arraycopy(elements, h, elements, h + 1, front - (i + 1));
623	>	System.arraycopy(es, 0, es, 1, i);
624	>	es[0] = es[capacity - 1];
625	>	System.arraycopy(es, h, es, h + 1, front - (i + 1));
626		}
627	<	elements[h] = null;
628	<	head = inc(h, capacity);
627	>	es[h] = null;
628	>	if ((head = (h + 1)) >= capacity) head = 0;
629		size--;
630		// checkInvariants();
631		return false;
#	Line 624 | Line 633 | public class ArrayDeque<E> extends Abstr
633		// move back elements backwards
634		int tail = tail();
635		if (i <= tail) {
636	<	System.arraycopy(elements, i + 1, elements, i, back);
636	>	System.arraycopy(es, i + 1, es, i, back);
637		} else { // Wrap around
638		int firstLeg = capacity - (i + 1);
639	<	System.arraycopy(elements, i + 1, elements, i, firstLeg);
640	<	elements[capacity - 1] = elements[0];
641	<	System.arraycopy(elements, 1, elements, 0, back - firstLeg - 1);
639	>	System.arraycopy(es, i + 1, es, i, firstLeg);
640	>	es[capacity - 1] = es[0];
641	>	System.arraycopy(es, 1, es, 0, back - firstLeg - 1);
642		}
643	<	elements[tail] = null;
643	>	es[tail] = null;
644		size--;
645		// checkInvariants();
646		return true;
#	Line 689 | Line 698 | public class ArrayDeque<E> extends Abstr
698
699		DeqIterator() { cursor = head; }
700
692	–	int advance(int i, int modulus) {
693	–	return inc(i, modulus);
694	–	}
695	–
696	–	void doRemove() {
697	–	if (delete(lastRet))
698	–	// if left-shifted, undo advance in next()
699	–	cursor = dec(cursor, elements.length);
700	–	}
701	–
701		public final boolean hasNext() {
702		return remaining > 0;
703		}
704
705	<	public final E next() {
706	<	if (remaining == 0)
705	>	public E next() {
706	>	if (remaining <= 0)
707		throw new NoSuchElementException();
708	<	E e = checkedElementAt(elements, cursor);
708	>	final Object[] es = elements;
709	>	E e = nonNullElementAt(es, cursor);
710		lastRet = cursor;
711	<	cursor = advance(cursor, elements.length);
711	>	if (++cursor >= es.length) cursor = 0;
712		remaining--;
713		return e;
714		}
715
716	+	void postDelete(boolean leftShifted) {
717	+	if (leftShifted)
718	+	if (--cursor < 0) cursor = elements.length - 1;
719	+	}
720	+
721		public final void remove() {
722		if (lastRet < 0)
723		throw new IllegalStateException();
724	<	doRemove();
724	>	postDelete(delete(lastRet));
725		lastRet = -1;
726		}
727
728	<	public final void forEachRemaining(Consumer<? super E> action) {
728	>	public void forEachRemaining(Consumer<? super E> action) {
729		Objects.requireNonNull(action);
730	<	final Object[] elements = ArrayDeque.this.elements;
731	<	final int capacity = elements.length;
732	<	int k = remaining;
733	<	remaining = 0;
734	<	for (int i = cursor; --k >= 0; i = advance(i, capacity))
735	<	action.accept(checkedElementAt(elements, i));
730	>	final int k;
731	>	if ((k = remaining) > 0) {
732	>	remaining = 0;
733	>	ArrayDeque.forEachRemaining(action, elements, cursor, k);
734	>	if ((lastRet = cursor + k - 1) >= elements.length)
735	>	lastRet -= elements.length;
736	>	}
737		}
738		}
739
740		private class DescendingIterator extends DeqIterator {
741		DescendingIterator() { cursor = tail(); }
742
743	<	@Override int advance(int i, int modulus) {
744	<	return dec(i, modulus);
743	>	public final E next() {
744	>	if (remaining <= 0)
745	>	throw new NoSuchElementException();
746	>	final Object[] es = elements;
747	>	E e = nonNullElementAt(es, cursor);
748	>	lastRet = cursor;
749	>	if (--cursor < 0) cursor = es.length - 1;
750	>	remaining--;
751	>	return e;
752	>	}
753	>
754	>	void postDelete(boolean leftShifted) {
755	>	if (!leftShifted)
756	>	if (++cursor >= elements.length) cursor = 0;
757		}
758
759	<	@Override void doRemove() {
760	<	if (!delete(lastRet))
761	<	// if right-shifted, undo advance in next
762	<	cursor = inc(cursor, elements.length);
759	>	public final void forEachRemaining(Consumer<? super E> action) {
760	>	Objects.requireNonNull(action);
761	>	final int k;
762	>	if ((k = remaining) > 0) {
763	>	remaining = 0;
764	>	final Object[] es = elements;
765	>	int i, end, to, todo;
766	>	todo = (to = ((end = (i = cursor) - k) >= -1) ? end : -1) - end;
767	>	for (;; to = (i = es.length - 1) - todo, todo = 0) {
768	>	for (; i > to; i--)
769	>	action.accept(nonNullElementAt(es, i));
770	>	if (todo == 0) break;
771	>	}
772	>	if ((lastRet = cursor - (k - 1)) < 0)
773	>	lastRet += es.length;
774	>	}
775		}
776		}
777
#	Line 799 | Line 829 | public class ArrayDeque<E> extends Abstr
829
830		public void forEachRemaining(Consumer<? super E> action) {
831		Objects.requireNonNull(action);
832	<	final Object[] elements = ArrayDeque.this.elements;
803	<	final int capacity = elements.length;
804	<	int k = remaining();
832	>	final int k = remaining(); // side effect!
833		remaining = 0;
834	<	for (int i = cursor; --k >= 0; i = inc(i, capacity))
807	<	action.accept(checkedElementAt(elements, i));
834	>	ArrayDeque.forEachRemaining(action, elements, cursor, k);
835		}
836
837		public boolean tryAdvance(Consumer<? super E> action) {
838		Objects.requireNonNull(action);
839	<	if (remaining() == 0)
839	>	final int k;
840	>	if ((k = remaining()) <= 0)
841		return false;
842	<	action.accept(checkedElementAt(elements, cursor));
843	<	cursor = inc(cursor, elements.length);
844	<	remaining--;
842	>	action.accept(nonNullElementAt(elements, cursor));
843	>	if (++cursor >= elements.length) cursor = 0;
844	>	remaining = k - 1;
845		return true;
846		}
847
#	Line 829 | Line 857 | public class ArrayDeque<E> extends Abstr
857		}
858		}
859
860	<	@Override
860	>	@SuppressWarnings("unchecked")
861		public void forEach(Consumer<? super E> action) {
834	–	// checkInvariants();
862		Objects.requireNonNull(action);
863	<	final Object[] elements = this.elements;
864	<	final int capacity = elements.length;
865	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
866	<	action.accept(elementAt(i));
863	>	final Object[] es = elements;
864	>	int i, end, to, todo;
865	>	todo = (end = (i = head) + size)
866	>	- (to = (es.length - end >= 0) ? end : es.length);
867	>	for (;; to = todo, todo = 0, i = 0) {
868	>	for (; i < to; i++)
869	>	action.accept((E) es[i]);
870	>	if (todo == 0) break;
871	>	}
872		// checkInvariants();
873		}
874
875		/**
876	+	* Calls action on remaining elements, starting at index i and
877	+	* traversing in ascending order.  A variant of forEach that also
878	+	* checks for concurrent modification, for use in iterators.
879	+	*/
880	+	static <E> void forEachRemaining(
881	+	Consumer<? super E> action, Object[] es, int i, int remaining) {
882	+	int end, to, todo;
883	+	todo = (end = i + remaining)
884	+	- (to = (es.length - end >= 0) ? end : es.length);
885	+	for (;; to = todo, todo = 0, i = 0) {
886	+	for (; i < to; i++)
887	+	action.accept(nonNullElementAt(es, i));
888	+	if (todo == 0) break;
889	+	}
890	+	}
891	+
892	+	/**
893		* Replaces each element of this deque with the result of applying the
894		* operator to that element, as specified by {@link List#replaceAll}.
895		*
896		* @param operator the operator to apply to each element
897	<	* @since 9
897	>	* @since TBD
898		*/
899	<	public void replaceAll(UnaryOperator<E> operator) {
899	>	@SuppressWarnings("unchecked")
900	>	/* public */ void replaceAll(UnaryOperator<E> operator) {
901		Objects.requireNonNull(operator);
902	<	final Object[] elements = this.elements;
903	<	final int capacity = elements.length;
904	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
905	<	elements[i] = operator.apply(elementAt(i));
902	>	final Object[] es = elements;
903	>	int i, end, to, todo;
904	>	todo = (end = (i = head) + size)
905	>	- (to = (es.length - end >= 0) ? end : es.length);
906	>	for (;; to = todo, todo = 0, i = 0) {
907	>	for (; i < to; i++)
908	>	es[i] = operator.apply((E) es[i]);
909	>	if (todo == 0) break;
910	>	}
911		// checkInvariants();
912		}
913
914		/**
915		* @throws NullPointerException {@inheritDoc}
916		*/
862	–	@Override
917		public boolean removeIf(Predicate<? super E> filter) {
918		Objects.requireNonNull(filter);
919		return bulkRemove(filter);
#	Line 868 | Line 922 | public class ArrayDeque<E> extends Abstr
922		/**
923		* @throws NullPointerException {@inheritDoc}
924		*/
871	–	@Override
925		public boolean removeAll(Collection<?> c) {
926		Objects.requireNonNull(c);
927		return bulkRemove(e -> c.contains(e));
#	Line 877 | Line 930 | public class ArrayDeque<E> extends Abstr
930		/**
931		* @throws NullPointerException {@inheritDoc}
932		*/
880	–	@Override
933		public boolean retainAll(Collection<?> c) {
934		Objects.requireNonNull(c);
935		return bulkRemove(e -> !c.contains(e));
936		}
937
938		/** Implementation of bulk remove methods. */
939	+	@SuppressWarnings("unchecked")
940		private boolean bulkRemove(Predicate<? super E> filter) {
941		// checkInvariants();
942	<	final Object[] elements = this.elements;
943	<	final int capacity = elements.length;
944	<	int i = head, j = i, remaining = size, deleted = 0;
942	>	final Object[] es = elements;
943	>	int i, end, to, todo;
944	>	todo = (end = (i = head) + size)
945	>	- (to = (es.length - end >= 0) ? end : es.length);
946	>	// Optimize for initial run of non-removed elements
947	>	findFirstRemoved:
948	>	for (;; to = todo, todo = 0, i = 0) {
949	>	for (; i < to; i++)
950	>	if (filter.test((E) es[i]))
951	>	break findFirstRemoved;
952	>	if (todo == 0) return false;
953	>	}
954	>	bulkRemoveModified(filter, i, to, todo);
955	>	return true;
956	>	}
957	>
958	>	/**
959	>	* Helper for bulkRemove, in case of at least one deletion.
960	>	* @param i valid index of first element to be deleted
961	>	*/
962	>	@SuppressWarnings("unchecked")
963	>	private void bulkRemoveModified(
964	>	Predicate<? super E> filter, int i, int to, int todo) {
965	>	final Object[] es = elements;
966	>	final int capacity = es.length;
967	>	// a two-finger algorithm, with hare i and tortoise j
968	>	int j = i++;
969		try {
970	<	for (; remaining > 0; remaining--, i = inc(i, capacity)) {
971	<	@SuppressWarnings("unchecked") E e = (E) elements[i];
972	<	if (filter.test(e))
973	<	deleted++;
974	<	else {
975	<	if (j != i)
976	<	elements[j] = e;
977	<	j = inc(j, capacity);
978	<	}
970	>	for (;;) {
971	>	E e;
972	>	// In this loop, i and j are on the same leg, with i > j
973	>	for (; i < to; i++)
974	>	if (!filter.test(e = (E) es[i]))
975	>	es[j++] = e;
976	>	if (todo == 0) break;
977	>	// In this loop, j is on the first leg, i on the second
978	>	for (to = todo, todo = 0, i = 0; i < to && j < capacity; i++)
979	>	if (!filter.test(e = (E) es[i]))
980	>	es[j++] = e;
981	>	if (i >= to) break;
982	>	j = 0;          // j rejoins i on second leg
983		}
984	<	return deleted > 0;
984	>	bulkRemoveClear(es, j, i);
985	>	// checkInvariants();
986		} catch (Throwable ex) {
987	<	for (; remaining > 0;
988	<	remaining--, i = inc(i, capacity), j = inc(j, capacity))
989	<	elements[j] = elements[i];
990	<	throw ex;
991	<	} finally {
992	<	size -= deleted;
993	<	for (; --deleted >= 0; j = inc(j, capacity))
912	<	elements[j] = null;
987	>	// copy remaining elements
988	>	for (int remaining = (to - i) + todo; --remaining >= 0;) {
989	>	es[j] = es[i];
990	>	if (++i >= capacity) i = 0;
991	>	if (++j >= capacity) j = 0;
992	>	}
993	>	bulkRemoveClear(es, j, i);
994		// checkInvariants();
995	+	throw ex;
996		}
997		}
998
999		/**
1000	+	* Nulls out all elements from index j upto index i.
1001	+	*/
1002	+	private void bulkRemoveClear(Object[] es, int j, int i) {
1003	+	int deleted;
1004	+	if ((deleted = i - j) <= 0) deleted += es.length;
1005	+	size -= deleted;
1006	+	circularClear(es, j, deleted);
1007	+	}
1008	+
1009	+	/**
1010		* Returns {@code true} if this deque contains the specified element.
1011		* More formally, returns {@code true} if and only if this deque contains
1012		* at least one element {@code e} such that {@code o.equals(e)}.
#	Line 924 | Line 1016 | public class ArrayDeque<E> extends Abstr
1016		*/
1017		public boolean contains(Object o) {
1018		if (o != null) {
1019	<	final Object[] elements = this.elements;
1020	<	final int capacity = elements.length;
1021	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
1022	<	if (o.equals(elements[i]))
1023	<	return true;
1019	>	final Object[] es = elements;
1020	>	int i, end, to, todo;
1021	>	todo = (end = (i = head) + size)
1022	>	- (to = (es.length - end >= 0) ? end : es.length);
1023	>	for (;; to = todo, todo = 0, i = 0) {
1024	>	for (; i < to; i++)
1025	>	if (o.equals(es[i]))
1026	>	return true;
1027	>	if (todo == 0) break;
1028	>	}
1029		}
1030		return false;
1031		}
#	Line 955 | Line 1052 | public class ArrayDeque<E> extends Abstr
1052		* The deque will be empty after this call returns.
1053		*/
1054		public void clear() {
1055	<	final Object[] elements = this.elements;
959	<	final int capacity = elements.length;
960	<	final int h = this.head;
961	<	final int s = size;
962	<	if (capacity - h >= s)
963	<	Arrays.fill(elements, h, h + s, null);
964	<	else {
965	<	Arrays.fill(elements, h, capacity, null);
966	<	Arrays.fill(elements, 0, s - capacity + h, null);
967	<	}
1055	>	circularClear(elements, head, size);
1056		size = head = 0;
1057		// checkInvariants();
1058		}
1059
1060		/**
1061	+	* Nulls out count elements, starting at array index from.
1062	+	* Special case (from == es.length) is treated the same as (from == 0).
1063	+	*/
1064	+	private static void circularClear(Object[] es, int from, int count) {
1065	+	int end, to, todo;
1066	+	todo = (end = from + count)
1067	+	- (to = (es.length - end >= 0) ? end : es.length);
1068	+	for (;; to = todo, todo = 0, from = 0) {
1069	+	Arrays.fill(es, from, to, null);
1070	+	if (todo == 0) break;
1071	+	}
1072	+	}
1073	+
1074	+	/**
1075		* Returns an array containing all of the elements in this deque
1076		* in proper sequence (from first to last element).
1077		*
#	Line 983 | Line 1085 | public class ArrayDeque<E> extends Abstr
1085		* @return an array containing all of the elements in this deque
1086		*/
1087		public Object[] toArray() {
1088	<	final int head = this.head;
1089	<	final int firstLeg;
1090	<	Object[] a = Arrays.copyOfRange(elements, head, head + size);
1091	<	if ((firstLeg = elements.length - head) < size)
1092	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1088	>	return toArray(Object[].class);
1089	>	}
1090	>
1091	>	private <T> T[] toArray(Class<T[]> klazz) {
1092	>	final Object[] es = elements;
1093	>	final T[] a;
1094	>	final int head, len, end, todo;
1095	>	todo = size - (len = Math.min(size, es.length - (head = this.head)));
1096	>	if ((end = head + size) >= 0) {
1097	>	a = Arrays.copyOfRange(es, head, end, klazz);
1098	>	} else {
1099	>	// integer overflow!
1100	>	a = Arrays.copyOfRange(es, 0, size, klazz);
1101	>	System.arraycopy(es, head, a, 0, len);
1102	>	}
1103	>	if (todo > 0)
1104	>	System.arraycopy(es, 0, a, len, todo);
1105		return a;
1106		}
1107
#	Line 1029 | Line 1143 | public class ArrayDeque<E> extends Abstr
1143		*/
1144		@SuppressWarnings("unchecked")
1145		public <T> T[] toArray(T[] a) {
1146	<	final Object[] elements = this.elements;
1147	<	final int head = this.head;
1148	<	final int firstLeg;
1149	<	boolean wrap = (firstLeg = elements.length - head) < size;
1150	<	if (size > a.length) {
1151	<	a = (T[]) Arrays.copyOfRange(elements, head, head + size,
1152	<	a.getClass());
1153	<	} else {
1154	<	System.arraycopy(elements, head, a, 0, wrap ? firstLeg : size);
1041	<	if (size < a.length)
1042	<	a[size] = null;
1146	>	final int size;
1147	>	if ((size = this.size) > a.length)
1148	>	return toArray((Class<T[]>) a.getClass());
1149	>	final Object[] es = elements;
1150	>	int i, j, len, todo;
1151	>	todo = size - (len = Math.min(size, es.length - (i = head)));
1152	>	for (j = 0;; j += len, len = todo, todo = 0, i = 0) {
1153	>	System.arraycopy(es, i, a, j, len);
1154	>	if (todo == 0) break;
1155		}
1156	<	if (wrap)
1157	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1156	>	if (size < a.length)
1157	>	a[size] = null;
1158		return a;
1159		}
1160
#	Line 1083 | Line 1195 | public class ArrayDeque<E> extends Abstr
1195		s.writeInt(size);
1196
1197		// Write out elements in order.
1198	<	final Object[] elements = this.elements;
1199	<	final int capacity = elements.length;
1200	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
1201	<	s.writeObject(elements[i]);
1198	>	final Object[] es = elements;
1199	>	int i, end, to, todo;
1200	>	todo = (end = (i = head) + size)
1201	>	- (to = (es.length - end >= 0) ? end : es.length);
1202	>	for (;; to = todo, todo = 0, i = 0) {
1203	>	for (; i < to; i++)
1204	>	s.writeObject(es[i]);
1205	>	if (todo == 0) break;
1206	>	}
1207		}
1208
1209		/**
#	Line 1109 | Line 1226 | public class ArrayDeque<E> extends Abstr
1226		}
1227
1228		/** debugging */
1229	<	private void checkInvariants() {
1229	>	void checkInvariants() {
1230		try {
1231		int capacity = elements.length;
1232	<	assert size >= 0 && size <= capacity;
1233	<	assert head >= 0 && ((capacity == 0 && head == 0 && size == 0)
1234	<	|| head < capacity);
1235	<	assert size == 0
1236	<	|| (elements[head] != null && elements[tail()] != null);
1237	<	assert size == capacity
1238	<	|| (elements[dec(head, capacity)] == null
1122	<	&& elements[inc(tail(), capacity)] == null);
1232	>	// assert size >= 0 && size <= capacity;
1233	>	// assert head >= 0;
1234	>	// assert capacity == 0 || head < capacity;
1235	>	// assert size == 0 || elements[head] != null;
1236	>	// assert size == 0 || elements[tail()] != null;
1237	>	// assert size == capacity || elements[dec(head, capacity)] == null;
1238	>	// assert size == capacity || elements[inc(tail(), capacity)] == null;
1239		} catch (Throwable t) {
1240		System.err.printf("head=%d size=%d capacity=%d%n",
1241		head, size, elements.length);

Diff Legend

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