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.100 by jsr166, Sun Oct 30 16:50:05 2016 UTC

#	Line 93 | Line 93 | public class ArrayDeque<E> extends Abstr
93		private void 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 115 | Line 115 | public class ArrayDeque<E> extends Abstr
115
116		/** Capacity calculation for edge conditions, especially overflow. */
117		private int newCapacity(int needed, int jump) {
118	<	int oldCapacity = elements.length;
119	<	int minCapacity;
118	>	final int oldCapacity = elements.length, minCapacity;
119		if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
120		if (minCapacity < 0)
121		throw new IllegalStateException("Sorry, deque too big");
#	Line 134 | Line 133 | public class ArrayDeque<E> extends Abstr
133		* to ensure that it can hold at least the given number of elements.
134		*
135		* @param minCapacity the desired minimum capacity
136	<	* @since 9
136	>	* @since TBD
137		*/
138	<	public void ensureCapacity(int minCapacity) {
138	>	/* public */ void ensureCapacity(int minCapacity) {
139		if (minCapacity > elements.length)
140		grow(minCapacity - elements.length);
141		// checkInvariants();
#	Line 145 | Line 144 | public class ArrayDeque<E> extends Abstr
144		/**
145		* Minimizes the internal storage of this collection.
146		*
147	<	* @since 9
147	>	* @since TBD
148		*/
149	<	public void trimToSize() {
149	>	/* public */ void trimToSize() {
150		if (size < elements.length) {
151		elements = toArray();
152		head = 0;
#	Line 184 | Line 183 | public class ArrayDeque<E> extends Abstr
183		* @throws NullPointerException if the specified collection is null
184		*/
185		public ArrayDeque(Collection<? extends E> c) {
186	<	Object[] elements = c.toArray();
186	>	Object[] es = c.toArray();
187		// defend against c.toArray (incorrectly) not returning Object[]
188		// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
189	<	if (elements.getClass() != Object[].class)
190	<	elements = Arrays.copyOf(elements, size, Object[].class);
191	<	for (Object obj : elements)
189	>	if (es.getClass() != Object[].class)
190	>	es = Arrays.copyOf(es, es.length, Object[].class);
191	>	for (Object obj : es)
192		Objects.requireNonNull(obj);
193	<	size = elements.length;
194	<	this.elements = elements;
193	>	this.elements = es;
194	>	this.size = es.length;
195		}
196
197		/**
198	<	* Returns the array index of the last element.
199	<	* May return invalid index -1 if there are no elements.
198	>	* Increments i, mod modulus.
199	>	* Precondition and postcondition: 0 <= i < modulus.
200		*/
201	<	final int tail() {
202	<	return add(head, size - 1, elements.length);
201	>	static final int inc(int i, int modulus) {
202	>	if (++i >= modulus) i = 0;
203	>	return i;
204		}
205
206		/**
207	<	* Adds i and j, mod modulus.
208	<	* Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
207	>	* Decrements i, mod modulus.
208	>	* Precondition and postcondition: 0 <= i < modulus.
209		*/
210	<	static final int add(int i, int j, int modulus) {
211	<	if ((i += j) - modulus >= 0) i -= modulus;
210	>	static final int dec(int i, int modulus) {
211	>	if (--i < 0) i = modulus - 1;
212		return i;
213		}
214
215		/**
216	<	* Increments i, mod modulus.
217	<	* Precondition and postcondition: 0 <= i < modulus.
216	>	* Adds i and j, mod modulus.
217	>	* Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
218		*/
219	<	static final int inc(int i, int modulus) {
220	<	if (++i == modulus) i = 0;
219	>	static final int add(int i, int j, int modulus) {
220	>	if ((i += j) - modulus >= 0) i -= modulus;
221		return i;
222		}
223
224		/**
225	<	* Decrements i, mod modulus.
226	<	* Precondition and postcondition: 0 <= i < modulus.
225	>	* Returns the array index of the last element.
226	>	* May return invalid index -1 if there are no elements.
227		*/
228	<	static final int dec(int i, int modulus) {
229	<	if (--i < 0) i += modulus;
230	<	return i;
228	>	final int tail() {
229	>	return add(head, size - 1, elements.length);
230		}
231
232		/**
233		* Returns element at array index i.
234		*/
235		@SuppressWarnings("unchecked")
236	<	final E elementAt(int i) {
236	>	private E elementAt(int i) {
237		return (E) elements[i];
238		}
239
240		/**
241		* A version of elementAt that checks for null elements.
242		* This check doesn't catch all possible comodifications,
243	<	* but does catch ones that corrupt traversal.
243	>	* but does catch ones that corrupt traversal.  It's a little
244	>	* surprising that javac allows this abuse of generics.
245		*/
246	<	E checkedElementAt(Object[] elements, int i) {
247	<	@SuppressWarnings("unchecked") E e = (E) elements[i];
246	>	static final <E> E nonNullElementAt(Object[] es, int i) {
247	>	@SuppressWarnings("unchecked") E e = (E) es[i];
248		if (e == null)
249		throw new ConcurrentModificationException();
250		return e;
#	Line 263 | Line 263 | public class ArrayDeque<E> extends Abstr
263		public void addFirst(E e) {
264		// checkInvariants();
265		Objects.requireNonNull(e);
266	<	Object[] elements;
267	<	int capacity, s = size;
268	<	while (s == (capacity = (elements = this.elements).length))
266	>	Object[] es;
267	>	int capacity, h;
268	>	final int s;
269	>	if ((s = size) == (capacity = (es = elements).length)) {
270		grow(1);
271	<	elements[head = dec(head, capacity)] = e;
271	>	capacity = (es = elements).length;
272	>	}
273	>	if ((h = head - 1) < 0) h = capacity - 1;
274	>	es[head = h] = e;
275		size = s + 1;
276	+	// checkInvariants();
277		}
278
279		/**
#	Line 282 | Line 287 | public class ArrayDeque<E> extends Abstr
287		public void addLast(E e) {
288		// checkInvariants();
289		Objects.requireNonNull(e);
290	<	Object[] elements;
291	<	int capacity, s = size;
292	<	while (s == (capacity = (elements = this.elements).length))
290	>	Object[] es;
291	>	int capacity;
292	>	final int s;
293	>	if ((s = size) == (capacity = (es = elements).length)) {
294		grow(1);
295	<	elements[add(head, s, capacity)] = e;
295	>	capacity = (es = elements).length;
296	>	}
297	>	es[add(head, s, capacity)] = e;
298		size = s + 1;
299	+	// checkInvariants();
300		}
301
302		/**
#	Line 301 | Line 310 | public class ArrayDeque<E> extends Abstr
310		* @throws NullPointerException if the specified collection or any
311		*         of its elements are null
312		*/
304	–	@Override
313		public boolean addAll(Collection<? extends E> c) {
314	+	final int s = size, needed = c.size() - (elements.length - s);
315	+	if (needed > 0)
316	+	grow(needed);
317	+	c.forEach((e) -> addLast(e));
318		// checkInvariants();
319	<	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;
319	>	return size > s;
320		}
321
322		/**
#	Line 349 | Line 348 | public class ArrayDeque<E> extends Abstr
348		*/
349		public E removeFirst() {
350		// checkInvariants();
351	<	E x = pollFirst();
352	<	if (x == null)
351	>	E e = pollFirst();
352	>	if (e == null)
353		throw new NoSuchElementException();
354	<	return x;
354	>	return e;
355		}
356
357		/**
#	Line 360 | Line 359 | public class ArrayDeque<E> extends Abstr
359		*/
360		public E removeLast() {
361		// checkInvariants();
362	<	E x = pollLast();
363	<	if (x == null)
362	>	E e = pollLast();
363	>	if (e == null)
364		throw new NoSuchElementException();
365	<	return x;
365	>	return e;
366		}
367
368		public E pollFirst() {
369		// checkInvariants();
370	<	final int s, h;
371	<	if ((s = size) == 0)
370	>	int s, h;
371	>	if ((s = size) <= 0)
372		return null;
373	<	final Object[] elements = this.elements;
374	<	@SuppressWarnings("unchecked") E e = (E) elements[h = head];
375	<	elements[h] = null;
376	<	head = inc(h, elements.length);
373	>	final Object[] es = elements;
374	>	@SuppressWarnings("unchecked") E e = (E) es[h = head];
375	>	es[h] = null;
376	>	if (++h >= es.length) h = 0;
377	>	head = h;
378		size = s - 1;
379		return e;
380		}
#	Line 382 | Line 382 | public class ArrayDeque<E> extends Abstr
382		public E pollLast() {
383		// checkInvariants();
384		final int s, tail;
385	<	if ((s = size) == 0)
385	>	if ((s = size) <= 0)
386		return null;
387	<	final Object[] elements = this.elements;
387	>	final Object[] es = elements;
388		@SuppressWarnings("unchecked")
389	<	E e = (E) elements[tail = add(head, s - 1, elements.length)];
390	<	elements[tail] = null;
389	>	E e = (E) es[tail = add(head, s - 1, es.length)];
390	>	es[tail] = null;
391		size = s - 1;
392		return e;
393		}
#	Line 397 | Line 397 | public class ArrayDeque<E> extends Abstr
397		*/
398		public E getFirst() {
399		// checkInvariants();
400	<	if (size == 0) throw new NoSuchElementException();
400	>	if (size <= 0) throw new NoSuchElementException();
401		return elementAt(head);
402		}
403
404		/**
405		* @throws NoSuchElementException {@inheritDoc}
406		*/
407	+	@SuppressWarnings("unchecked")
408		public E getLast() {
409		// checkInvariants();
410	<	if (size == 0) throw new NoSuchElementException();
411	<	return elementAt(tail());
410	>	final int s;
411	>	if ((s = size) <= 0) throw new NoSuchElementException();
412	>	final Object[] es = elements;
413	>	return (E) es[add(head, s - 1, es.length)];
414		}
415
416		public E peekFirst() {
417		// checkInvariants();
418	<	return (size == 0) ? null : elementAt(head);
418	>	return (size <= 0) ? null : elementAt(head);
419		}
420
421	+	@SuppressWarnings("unchecked")
422		public E peekLast() {
423		// checkInvariants();
424	<	return (size == 0) ? null : elementAt(tail());
424	>	final int s;
425	>	if ((s = size) <= 0) return null;
426	>	final Object[] es = elements;
427	>	return (E) es[add(head, s - 1, es.length)];
428		}
429
430		/**
#	Line 433 | Line 440 | public class ArrayDeque<E> extends Abstr
440		* @return {@code true} if the deque contained the specified element
441		*/
442		public boolean removeFirstOccurrence(Object o) {
436	–	// checkInvariants();
443		if (o != null) {
444	<	final Object[] elements = this.elements;
445	<	final int capacity = elements.length;
446	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity)) {
447	<	if (o.equals(elements[i])) {
448	<	delete(i);
449	<	return true;
450	<	}
444	>	final Object[] es = elements;
445	>	int i, end, to, todo;
446	>	todo = (end = (i = head) + size)
447	>	- (to = (es.length - end >= 0) ? end : es.length);
448	>	for (;; to = todo, i = 0, todo = 0) {
449	>	for (; i < to; i++)
450	>	if (o.equals(es[i])) {
451	>	delete(i);
452	>	return true;
453	>	}
454	>	if (todo == 0) break;
455		}
456		}
457		return false;
#	Line 461 | Line 471 | public class ArrayDeque<E> extends Abstr
471		*/
472		public boolean removeLastOccurrence(Object o) {
473		if (o != null) {
474	<	final Object[] elements = this.elements;
475	<	final int capacity = elements.length;
476	<	for (int k = size, i = add(head, k - 1, capacity);
477	<	--k >= 0; i = dec(i, capacity)) {
478	<	if (o.equals(elements[i])) {
479	<	delete(i);
480	<	return true;
481	<	}
474	>	final Object[] es = elements;
475	>	int i, to, end, todo;
476	>	todo = (to = ((end = (i = tail()) - size) >= -1) ? end : -1) - end;
477	>	for (;; to = (i = es.length - 1) - todo, todo = 0) {
478	>	for (; i > to; i--)
479	>	if (o.equals(es[i])) {
480	>	delete(i);
481	>	return true;
482	>	}
483	>	if (todo == 0) break;
484		}
485		}
486		return false;
#	Line 600 | Line 612 | public class ArrayDeque<E> extends Abstr
612		*/
613		boolean delete(int i) {
614		// checkInvariants();
615	<	final Object[] elements = this.elements;
616	<	final int capacity = elements.length;
615	>	final Object[] es = elements;
616	>	final int capacity = es.length;
617		final int h = head;
618		int front;              // number of elements before to-be-deleted elt
619		if ((front = i - h) < 0) front += capacity;
#	Line 609 | Line 621 | public class ArrayDeque<E> extends Abstr
621		if (front < back) {
622		// move front elements forwards
623		if (h <= i) {
624	<	System.arraycopy(elements, h, elements, h + 1, front);
624	>	System.arraycopy(es, h, es, h + 1, front);
625		} else { // Wrap around
626	<	System.arraycopy(elements, 0, elements, 1, i);
627	<	elements[0] = elements[capacity - 1];
628	<	System.arraycopy(elements, h, elements, h + 1, front - (i + 1));
626	>	System.arraycopy(es, 0, es, 1, i);
627	>	es[0] = es[capacity - 1];
628	>	System.arraycopy(es, h, es, h + 1, front - (i + 1));
629		}
630	<	elements[h] = null;
631	<	head = inc(h, capacity);
630	>	es[h] = null;
631	>	if ((head = (h + 1)) >= capacity) head = 0;
632		size--;
633		// checkInvariants();
634		return false;
#	Line 624 | Line 636 | public class ArrayDeque<E> extends Abstr
636		// move back elements backwards
637		int tail = tail();
638		if (i <= tail) {
639	<	System.arraycopy(elements, i + 1, elements, i, back);
639	>	System.arraycopy(es, i + 1, es, i, back);
640		} else { // Wrap around
641		int firstLeg = capacity - (i + 1);
642	<	System.arraycopy(elements, i + 1, elements, i, firstLeg);
643	<	elements[capacity - 1] = elements[0];
644	<	System.arraycopy(elements, 1, elements, 0, back - firstLeg - 1);
642	>	System.arraycopy(es, i + 1, es, i, firstLeg);
643	>	es[capacity - 1] = es[0];
644	>	System.arraycopy(es, 1, es, 0, back - firstLeg - 1);
645		}
646	<	elements[tail] = null;
646	>	es[tail] = null;
647		size--;
648		// checkInvariants();
649		return true;
#	Line 689 | Line 701 | public class ArrayDeque<E> extends Abstr
701
702		DeqIterator() { cursor = head; }
703
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	–
704		public final boolean hasNext() {
705		return remaining > 0;
706		}
707
708	<	public final E next() {
709	<	if (remaining == 0)
708	>	public E next() {
709	>	if (remaining <= 0)
710		throw new NoSuchElementException();
711	<	E e = checkedElementAt(elements, cursor);
711	>	final Object[] es = elements;
712	>	E e = nonNullElementAt(es, cursor);
713		lastRet = cursor;
714	<	cursor = advance(cursor, elements.length);
714	>	if (++cursor >= es.length) cursor = 0;
715		remaining--;
716		return e;
717		}
718
719	+	void postDelete(boolean leftShifted) {
720	+	if (leftShifted)
721	+	if (--cursor < 0) cursor = elements.length - 1;
722	+	}
723	+
724		public final void remove() {
725		if (lastRet < 0)
726		throw new IllegalStateException();
727	<	doRemove();
727	>	postDelete(delete(lastRet));
728		lastRet = -1;
729		}
730
731	<	public final void forEachRemaining(Consumer<? super E> action) {
731	>	public void forEachRemaining(Consumer<? super E> action) {
732		Objects.requireNonNull(action);
733	<	final Object[] elements = ArrayDeque.this.elements;
734	<	final int capacity = elements.length;
735	<	int k = remaining;
736	<	remaining = 0;
737	<	for (int i = cursor; --k >= 0; i = advance(i, capacity))
738	<	action.accept(checkedElementAt(elements, i));
733	>	final int k;
734	>	if ((k = remaining) > 0) {
735	>	remaining = 0;
736	>	ArrayDeque.forEachRemaining(action, elements, cursor, k);
737	>	if ((lastRet = cursor + k - 1) >= elements.length)
738	>	lastRet -= elements.length;
739	>	}
740		}
741		}
742
743		private class DescendingIterator extends DeqIterator {
744		DescendingIterator() { cursor = tail(); }
745
746	<	@Override int advance(int i, int modulus) {
747	<	return dec(i, modulus);
746	>	public final E next() {
747	>	if (remaining <= 0)
748	>	throw new NoSuchElementException();
749	>	final Object[] es = elements;
750	>	E e = nonNullElementAt(es, cursor);
751	>	lastRet = cursor;
752	>	if (--cursor < 0) cursor = es.length - 1;
753	>	remaining--;
754	>	return e;
755		}
756
757	<	@Override void doRemove() {
758	<	if (!delete(lastRet))
759	<	// if right-shifted, undo advance in next
760	<	cursor = inc(cursor, elements.length);
757	>	void postDelete(boolean leftShifted) {
758	>	if (!leftShifted)
759	>	if (++cursor >= elements.length) cursor = 0;
760	>	}
761	>
762	>	public final void forEachRemaining(Consumer<? super E> action) {
763	>	Objects.requireNonNull(action);
764	>	final int k;
765	>	if ((k = remaining) > 0) {
766	>	remaining = 0;
767	>	final Object[] es = elements;
768	>	int i, end, to, todo;
769	>	todo = (to = ((end = (i = cursor) - k) >= -1) ? end : -1) - end;
770	>	for (;; to = (i = es.length - 1) - todo, todo = 0) {
771	>	for (; i > to; i--)
772	>	action.accept(nonNullElementAt(es, i));
773	>	if (todo == 0) break;
774	>	}
775	>	if ((lastRet = cursor - (k - 1)) < 0)
776	>	lastRet += es.length;
777	>	}
778		}
779		}
780
#	Line 799 | Line 832 | public class ArrayDeque<E> extends Abstr
832
833		public void forEachRemaining(Consumer<? super E> action) {
834		Objects.requireNonNull(action);
835	<	final Object[] elements = ArrayDeque.this.elements;
803	<	final int capacity = elements.length;
804	<	int k = remaining();
835	>	final int k = remaining(); // side effect!
836		remaining = 0;
837	<	for (int i = cursor; --k >= 0; i = inc(i, capacity))
807	<	action.accept(checkedElementAt(elements, i));
837	>	ArrayDeque.forEachRemaining(action, elements, cursor, k);
838		}
839
840		public boolean tryAdvance(Consumer<? super E> action) {
841		Objects.requireNonNull(action);
842	<	if (remaining() == 0)
842	>	final int k;
843	>	if ((k = remaining()) <= 0)
844		return false;
845	<	action.accept(checkedElementAt(elements, cursor));
846	<	cursor = inc(cursor, elements.length);
847	<	remaining--;
845	>	action.accept(nonNullElementAt(elements, cursor));
846	>	if (++cursor >= elements.length) cursor = 0;
847	>	remaining = k - 1;
848		return true;
849		}
850
#	Line 829 | Line 860 | public class ArrayDeque<E> extends Abstr
860		}
861		}
862
863	<	@Override
863	>	@SuppressWarnings("unchecked")
864		public void forEach(Consumer<? super E> action) {
834	–	// checkInvariants();
865		Objects.requireNonNull(action);
866	<	final Object[] elements = this.elements;
867	<	final int capacity = elements.length;
868	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
869	<	action.accept(elementAt(i));
866	>	final Object[] es = elements;
867	>	int i, end, to, todo;
868	>	todo = (end = (i = head) + size)
869	>	- (to = (es.length - end >= 0) ? end : es.length);
870	>	for (;; to = todo, i = 0, todo = 0) {
871	>	for (; i < to; i++)
872	>	action.accept((E) es[i]);
873	>	if (todo == 0) break;
874	>	}
875		// checkInvariants();
876		}
877
878		/**
879	+	* Calls action on remaining elements, starting at index i and
880	+	* traversing in ascending order.  A variant of forEach that also
881	+	* checks for concurrent modification, for use in iterators.
882	+	*/
883	+	static <E> void forEachRemaining(
884	+	Consumer<? super E> action, Object[] es, int i, int remaining) {
885	+	int end, to, todo;
886	+	todo = (end = i + remaining)
887	+	- (to = (es.length - end >= 0) ? end : es.length);
888	+	for (;; to = todo, i = 0, todo = 0) {
889	+	for (; i < to; i++)
890	+	action.accept(nonNullElementAt(es, i));
891	+	if (todo == 0) break;
892	+	}
893	+	}
894	+
895	+	/**
896		* Replaces each element of this deque with the result of applying the
897		* operator to that element, as specified by {@link List#replaceAll}.
898		*
899		* @param operator the operator to apply to each element
900	<	* @since 9
900	>	* @since TBD
901		*/
902	<	public void replaceAll(UnaryOperator<E> operator) {
902	>	@SuppressWarnings("unchecked")
903	>	/* public */ void replaceAll(UnaryOperator<E> operator) {
904		Objects.requireNonNull(operator);
905	<	final Object[] elements = this.elements;
906	<	final int capacity = elements.length;
907	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
908	<	elements[i] = operator.apply(elementAt(i));
905	>	final Object[] es = elements;
906	>	int i, end, to, todo;
907	>	todo = (end = (i = head) + size)
908	>	- (to = (es.length - end >= 0) ? end : es.length);
909	>	for (;; to = todo, i = 0, todo = 0) {
910	>	for (; i < to; i++)
911	>	es[i] = operator.apply((E) es[i]);
912	>	if (todo == 0) break;
913	>	}
914		// checkInvariants();
915		}
916
917		/**
918		* @throws NullPointerException {@inheritDoc}
919		*/
862	–	@Override
920		public boolean removeIf(Predicate<? super E> filter) {
921		Objects.requireNonNull(filter);
922		return bulkRemove(filter);
#	Line 868 | Line 925 | public class ArrayDeque<E> extends Abstr
925		/**
926		* @throws NullPointerException {@inheritDoc}
927		*/
871	–	@Override
928		public boolean removeAll(Collection<?> c) {
929		Objects.requireNonNull(c);
930		return bulkRemove(e -> c.contains(e));
#	Line 877 | Line 933 | public class ArrayDeque<E> extends Abstr
933		/**
934		* @throws NullPointerException {@inheritDoc}
935		*/
880	–	@Override
936		public boolean retainAll(Collection<?> c) {
937		Objects.requireNonNull(c);
938		return bulkRemove(e -> !c.contains(e));
#	Line 886 | Line 941 | public class ArrayDeque<E> extends Abstr
941		/** Implementation of bulk remove methods. */
942		private boolean bulkRemove(Predicate<? super E> filter) {
943		// checkInvariants();
944	<	final Object[] elements = this.elements;
945	<	final int capacity = elements.length;
944	>	final Object[] es = elements;
945	>	final int capacity = es.length;
946		int i = head, j = i, remaining = size, deleted = 0;
947		try {
948	<	for (; remaining > 0; remaining--, i = inc(i, capacity)) {
949	<	@SuppressWarnings("unchecked") E e = (E) elements[i];
948	>	for (; remaining > 0; remaining--) {
949	>	@SuppressWarnings("unchecked") E e = (E) es[i];
950		if (filter.test(e))
951		deleted++;
952		else {
953		if (j != i)
954	<	elements[j] = e;
955	<	j = inc(j, capacity);
954	>	es[j] = e;
955	>	if (++j >= capacity) j = 0;
956		}
957	+	if (++i >= capacity) i = 0;
958		}
959		return deleted > 0;
960		} catch (Throwable ex) {
961	<	for (; remaining > 0;
962	<	remaining--, i = inc(i, capacity), j = inc(j, capacity))
963	<	elements[j] = elements[i];
961	>	if (deleted > 0)
962	>	for (; remaining > 0; remaining--) {
963	>	es[j] = es[i];
964	>	if (++i >= capacity) i = 0;
965	>	if (++j >= capacity) j = 0;
966	>	}
967		throw ex;
968		} finally {
969		size -= deleted;
970	<	for (; --deleted >= 0; j = inc(j, capacity))
912	<	elements[j] = null;
970	>	circularClear(es, j, deleted);
971		// checkInvariants();
972		}
973		}
#	Line 924 | Line 982 | public class ArrayDeque<E> extends Abstr
982		*/
983		public boolean contains(Object o) {
984		if (o != null) {
985	<	final Object[] elements = this.elements;
986	<	final int capacity = elements.length;
987	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
988	<	if (o.equals(elements[i]))
989	<	return true;
985	>	final Object[] es = elements;
986	>	int i, end, to, todo;
987	>	todo = (end = (i = head) + size)
988	>	- (to = (es.length - end >= 0) ? end : es.length);
989	>	for (;; to = todo, i = 0, todo = 0) {
990	>	for (; i < to; i++)
991	>	if (o.equals(es[i]))
992	>	return true;
993	>	if (todo == 0) break;
994	>	}
995		}
996		return false;
997		}
#	Line 955 | Line 1018 | public class ArrayDeque<E> extends Abstr
1018		* The deque will be empty after this call returns.
1019		*/
1020		public void clear() {
1021	<	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	<	}
1021	>	circularClear(elements, head, size);
1022		size = head = 0;
1023		// checkInvariants();
1024		}
1025
1026		/**
1027	+	* Nulls out count elements, starting at array index from.
1028	+	*/
1029	+	private static void circularClear(Object[] es, int from, int count) {
1030	+	int end, to, todo;
1031	+	todo = (end = from + count)
1032	+	- (to = (es.length - end >= 0) ? end : es.length);
1033	+	for (;; to = todo, from = 0, todo = 0) {
1034	+	Arrays.fill(es, from, to, null);
1035	+	if (todo == 0) break;
1036	+	}
1037	+	}
1038	+
1039	+	/**
1040		* Returns an array containing all of the elements in this deque
1041		* in proper sequence (from first to last element).
1042		*
#	Line 983 | Line 1050 | public class ArrayDeque<E> extends Abstr
1050		* @return an array containing all of the elements in this deque
1051		*/
1052		public Object[] toArray() {
1053	<	final int head = this.head;
1054	<	final int firstLeg;
1055	<	Object[] a = Arrays.copyOfRange(elements, head, head + size);
1056	<	if ((firstLeg = elements.length - head) < size)
1057	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1053	>	return toArray(Object[].class);
1054	>	}
1055	>
1056	>	private <T> T[] toArray(Class<T[]> klazz) {
1057	>	final Object[] es = elements;
1058	>	final int capacity = es.length;
1059	>	final int head = this.head, end = head + size;
1060	>	final T[] a;
1061	>	if (end >= 0) {
1062	>	a = Arrays.copyOfRange(es, head, end, klazz);
1063	>	} else {
1064	>	// integer overflow!
1065	>	a = Arrays.copyOfRange(es, 0, size, klazz);
1066	>	System.arraycopy(es, head, a, 0, capacity - head);
1067	>	}
1068	>	if (end - capacity > 0)
1069	>	System.arraycopy(es, 0, a, capacity - head, end - capacity);
1070		return a;
1071		}
1072
#	Line 1029 | Line 1108 | public class ArrayDeque<E> extends Abstr
1108		*/
1109		@SuppressWarnings("unchecked")
1110		public <T> T[] toArray(T[] a) {
1111	<	final Object[] elements = this.elements;
1112	<	final int head = this.head;
1113	<	final int firstLeg;
1114	<	boolean wrap = (firstLeg = elements.length - head) < size;
1115	<	if (size > a.length) {
1116	<	a = (T[]) Arrays.copyOfRange(elements, head, head + size,
1117	<	a.getClass());
1118	<	} else {
1119	<	System.arraycopy(elements, head, a, 0, wrap ? firstLeg : size);
1120	<	if (size < a.length)
1121	<	a[size] = null;
1043	<	}
1044	<	if (wrap)
1045	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1111	>	final int size;
1112	>	if ((size = this.size) > a.length)
1113	>	return toArray((Class<T[]>) a.getClass());
1114	>	final Object[] es = elements;
1115	>	final int head = this.head, end = head + size;
1116	>	final int front = (es.length - end >= 0) ? size : es.length - head;
1117	>	System.arraycopy(es, head, a, 0, front);
1118	>	if (front < size)
1119	>	System.arraycopy(es, 0, a, front, size - front);
1120	>	if (size < a.length)
1121	>	a[size] = null;
1122		return a;
1123		}
1124
#	Line 1083 | Line 1159 | public class ArrayDeque<E> extends Abstr
1159		s.writeInt(size);
1160
1161		// Write out elements in order.
1162	<	final Object[] elements = this.elements;
1163	<	final int capacity = elements.length;
1164	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
1165	<	s.writeObject(elements[i]);
1162	>	final Object[] es = elements;
1163	>	int i, end, to, todo;
1164	>	todo = (end = (i = head) + size)
1165	>	- (to = (es.length - end >= 0) ? end : es.length);
1166	>	for (;; to = todo, i = 0, todo = 0) {
1167	>	for (; i < to; i++)
1168	>	s.writeObject(es[i]);
1169	>	if (todo == 0) break;
1170	>	}
1171		}
1172
1173		/**
#	Line 1109 | Line 1190 | public class ArrayDeque<E> extends Abstr
1190		}
1191
1192		/** debugging */
1193	<	private void checkInvariants() {
1193	>	void checkInvariants() {
1194		try {
1195		int capacity = elements.length;
1196	<	assert size >= 0 && size <= capacity;
1197	<	assert head >= 0 && ((capacity == 0 && head == 0 && size == 0)
1198	<	|| head < capacity);
1199	<	assert size == 0
1200	<	|| (elements[head] != null && elements[tail()] != null);
1201	<	assert size == capacity
1202	<	|| (elements[dec(head, capacity)] == null
1122	<	&& elements[inc(tail(), capacity)] == null);
1196	>	// assert size >= 0 && size <= capacity;
1197	>	// assert head >= 0;
1198	>	// assert capacity == 0 || head < capacity;
1199	>	// assert size == 0 || elements[head] != null;
1200	>	// assert size == 0 || elements[tail()] != null;
1201	>	// assert size == capacity || elements[dec(head, capacity)] == null;
1202	>	// assert size == capacity || elements[inc(tail(), capacity)] == null;
1203		} catch (Throwable t) {
1204		System.err.printf("head=%d size=%d capacity=%d%n",
1205		head, size, elements.length);

Diff Legend

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