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.80 by jsr166, Thu Oct 20 01:43:31 2016 UTC vs.
Revision 1.104 by jsr166, Mon Oct 31 21:15:35 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 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		/**
#	Line 200 | Line 199 | public class ArrayDeque<E> extends Abstr
199		* Precondition and postcondition: 0 <= i < modulus.
200		*/
201		static final int inc(int i, int modulus) {
202	<	if (++i == modulus) i = 0;
202	>	if (++i >= modulus) i = 0;
203		return i;
204		}
205
#	Line 209 | Line 208 | public class ArrayDeque<E> extends Abstr
208		* Precondition and postcondition: 0 <= i < modulus.
209		*/
210		static final int dec(int i, int modulus) {
211	<	if (--i < 0) i += modulus;
211	>	if (--i < 0) i = modulus - 1;
212		return i;
213		}
214
#	Line 234 | Line 233 | public class ArrayDeque<E> extends Abstr
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 newcomers, capacity, s = size;
309	<	if ((newcomers = (a = c.toArray()).length) == 0)
310	<	return false;
311	<	while ((capacity = (elements = this.elements).length) - s < newcomers)
312	<	grow(newcomers - (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, todo = 0, i = 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, todo = 0, i = 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, todo = 0, i = 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 TBD
901		*/
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, todo = 0, i = 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));
939		}
940
941		/** Implementation of bulk remove methods. */
942	+	@SuppressWarnings("unchecked")
943		private boolean bulkRemove(Predicate<? super E> filter) {
944		// checkInvariants();
945	<	final Object[] elements = this.elements;
946	<	final int capacity = elements.length;
947	<	int i = head, j = i, remaining = size, deleted = 0;
945	>	final Object[] es = elements;
946	>	int i, end, to, todo;
947	>	todo = (end = (i = head) + size)
948	>	- (to = (es.length - end >= 0) ? end : es.length);
949	>	// Optimize for initial run of non-removed elements
950	>	findFirstRemoved:
951	>	for (;; to = todo, todo = 0, i = 0) {
952	>	for (; i < to; i++)
953	>	if (filter.test((E) es[i]))
954	>	break findFirstRemoved;
955	>	if (todo == 0) return false;
956	>	}
957	>	bulkRemoveModified(filter, i, to, todo);
958	>	return true;
959	>	}
960	>
961	>	/**
962	>	* Helper for bulkRemove, in case of at least one deletion.
963	>	* @param i valid index of first element to be deleted
964	>	*/
965	>	@SuppressWarnings("unchecked")
966	>	private void bulkRemoveModified(
967	>	Predicate<? super E> filter, int i, int to, int todo) {
968	>	final Object[] es = elements;
969	>	final int capacity = es.length;
970	>	// a two-finger algorithm, with hare i and tortoise j
971	>	int j = i++;
972		try {
973	<	for (; remaining > 0; remaining--, i = inc(i, capacity)) {
974	<	@SuppressWarnings("unchecked") E e = (E) elements[i];
975	<	if (filter.test(e))
976	<	deleted++;
977	<	else {
978	<	if (j != i)
979	<	elements[j] = e;
980	<	j = inc(j, capacity);
981	<	}
973	>	for (;;) {
974	>	E e;
975	>	// In this loop, i and j are on the same leg, with i > j
976	>	for (; i < to; i++)
977	>	if (!filter.test(e = (E) es[i]))
978	>	es[j++] = e;
979	>	if (todo == 0) break;
980	>	// In this loop, j is on the first leg, i on the second
981	>	for (to = todo, todo = 0, i = 0; i < to && j < capacity; i++)
982	>	if (!filter.test(e = (E) es[i]))
983	>	es[j++] = e;
984	>	if (i >= to) break;
985	>	j = 0;          // j rejoins i on second leg
986		}
987	<	return deleted > 0;
987	>	bulkRemoveClear(es, j, i);
988	>	// checkInvariants();
989		} catch (Throwable ex) {
990	<	if (deleted > 0)
991	<	for (; remaining > 0;
992	<	remaining--, i = inc(i, capacity), j = inc(j, capacity))
993	<	elements[j] = elements[i];
994	<	throw ex;
995	<	} finally {
996	<	size -= deleted;
912	<	for (; --deleted >= 0; j = inc(j, capacity))
913	<	elements[j] = null;
990	>	// copy remaining elements
991	>	for (int remaining = (to - i) + todo; --remaining >= 0;) {
992	>	es[j] = es[i];
993	>	if (++i >= capacity) i = 0;
994	>	if (++j >= capacity) j = 0;
995	>	}
996	>	bulkRemoveClear(es, j, i);
997		// checkInvariants();
998	+	throw ex;
999		}
1000		}
1001
1002		/**
1003	+	* Nulls out all elements from index j upto index i.
1004	+	*/
1005	+	private void bulkRemoveClear(Object[] es, int j, int i) {
1006	+	int deleted;
1007	+	if ((deleted = i - j) <= 0) deleted += es.length;
1008	+	size -= deleted;
1009	+	circularClear(es, j, deleted);
1010	+	}
1011	+
1012	+	/**
1013		* Returns {@code true} if this deque contains the specified element.
1014		* More formally, returns {@code true} if and only if this deque contains
1015		* at least one element {@code e} such that {@code o.equals(e)}.
#	Line 925 | Line 1019 | public class ArrayDeque<E> extends Abstr
1019		*/
1020		public boolean contains(Object o) {
1021		if (o != null) {
1022	<	final Object[] elements = this.elements;
1023	<	final int capacity = elements.length;
1024	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
1025	<	if (o.equals(elements[i]))
1026	<	return true;
1022	>	final Object[] es = elements;
1023	>	int i, end, to, todo;
1024	>	todo = (end = (i = head) + size)
1025	>	- (to = (es.length - end >= 0) ? end : es.length);
1026	>	for (;; to = todo, todo = 0, i = 0) {
1027	>	for (; i < to; i++)
1028	>	if (o.equals(es[i]))
1029	>	return true;
1030	>	if (todo == 0) break;
1031	>	}
1032		}
1033		return false;
1034		}
#	Line 956 | Line 1055 | public class ArrayDeque<E> extends Abstr
1055		* The deque will be empty after this call returns.
1056		*/
1057		public void clear() {
1058	<	final Object[] elements = this.elements;
960	<	final int capacity = elements.length;
961	<	final int h = this.head;
962	<	final int s = size;
963	<	if (capacity - h >= s)
964	<	Arrays.fill(elements, h, h + s, null);
965	<	else {
966	<	Arrays.fill(elements, h, capacity, null);
967	<	Arrays.fill(elements, 0, s - capacity + h, null);
968	<	}
1058	>	circularClear(elements, head, size);
1059		size = head = 0;
1060		// checkInvariants();
1061		}
1062
1063		/**
1064	+	* Nulls out count elements, starting at array index from.
1065	+	* Special case (from == es.length) is treated the same as (from == 0).
1066	+	*/
1067	+	private static void circularClear(Object[] es, int from, int count) {
1068	+	int end, to, todo;
1069	+	todo = (end = from + count)
1070	+	- (to = (es.length - end >= 0) ? end : es.length);
1071	+	for (;; to = todo, todo = 0, from = 0) {
1072	+	Arrays.fill(es, from, to, null);
1073	+	if (todo == 0) break;
1074	+	}
1075	+	}
1076	+
1077	+	/**
1078		* Returns an array containing all of the elements in this deque
1079		* in proper sequence (from first to last element).
1080		*
#	Line 984 | Line 1088 | public class ArrayDeque<E> extends Abstr
1088		* @return an array containing all of the elements in this deque
1089		*/
1090		public Object[] toArray() {
1091	<	final int head = this.head;
1092	<	final int firstLeg;
1093	<	Object[] a = Arrays.copyOfRange(elements, head, head + size);
1094	<	if ((firstLeg = elements.length - head) < size)
1095	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1091	>	return toArray(Object[].class);
1092	>	}
1093	>
1094	>	private <T> T[] toArray(Class<T[]> klazz) {
1095	>	final Object[] es = elements;
1096	>	final T[] a;
1097	>	final int head, len, end, todo;
1098	>	todo = size - (len = Math.min(size, es.length - (head = this.head)));
1099	>	if ((end = head + size) >= 0) {
1100	>	a = Arrays.copyOfRange(es, head, end, klazz);
1101	>	} else {
1102	>	// integer overflow!
1103	>	a = Arrays.copyOfRange(es, 0, size, klazz);
1104	>	System.arraycopy(es, head, a, 0, len);
1105	>	}
1106	>	if (todo > 0)
1107	>	System.arraycopy(es, 0, a, len, todo);
1108		return a;
1109		}
1110
#	Line 1030 | Line 1146 | public class ArrayDeque<E> extends Abstr
1146		*/
1147		@SuppressWarnings("unchecked")
1148		public <T> T[] toArray(T[] a) {
1149	<	final Object[] elements = this.elements;
1150	<	final int head = this.head;
1151	<	final int firstLeg;
1152	<	boolean wrap = (firstLeg = elements.length - head) < size;
1153	<	if (size > a.length) {
1154	<	a = (T[]) Arrays.copyOfRange(elements, head, head + size,
1155	<	a.getClass());
1156	<	} else {
1157	<	System.arraycopy(elements, head, a, 0, wrap ? firstLeg : size);
1042	<	if (size < a.length)
1043	<	a[size] = null;
1149	>	final int size;
1150	>	if ((size = this.size) > a.length)
1151	>	return toArray((Class<T[]>) a.getClass());
1152	>	final Object[] es = elements;
1153	>	int i, j, len, todo;
1154	>	todo = size - (len = Math.min(size, es.length - (i = head)));
1155	>	for (j = 0;; j += len, len = todo, todo = 0, i = 0) {
1156	>	System.arraycopy(es, i, a, j, len);
1157	>	if (todo == 0) break;
1158		}
1159	<	if (wrap)
1160	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1159	>	if (size < a.length)
1160	>	a[size] = null;
1161		return a;
1162		}
1163
#	Line 1084 | Line 1198 | public class ArrayDeque<E> extends Abstr
1198		s.writeInt(size);
1199
1200		// Write out elements in order.
1201	<	final Object[] elements = this.elements;
1202	<	final int capacity = elements.length;
1203	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
1204	<	s.writeObject(elements[i]);
1201	>	final Object[] es = elements;
1202	>	int i, end, to, todo;
1203	>	todo = (end = (i = head) + size)
1204	>	- (to = (es.length - end >= 0) ? end : es.length);
1205	>	for (;; to = todo, todo = 0, i = 0) {
1206	>	for (; i < to; i++)
1207	>	s.writeObject(es[i]);
1208	>	if (todo == 0) break;
1209	>	}
1210		}
1211
1212		/**
#	Line 1110 | Line 1229 | public class ArrayDeque<E> extends Abstr
1229		}
1230
1231		/** debugging */
1232	<	private void checkInvariants() {
1232	>	void checkInvariants() {
1233		try {
1234		int capacity = elements.length;
1235	<	assert size >= 0 && size <= capacity;
1236	<	assert head >= 0 && ((capacity == 0 && head == 0 && size == 0)
1237	<	|| head < capacity);
1238	<	assert size == 0
1239	<	|| (elements[head] != null && elements[tail()] != null);
1240	<	assert size == capacity
1241	<	|| (elements[dec(head, capacity)] == null
1123	<	&& elements[inc(tail(), capacity)] == null);
1235	>	// assert size >= 0 && size <= capacity;
1236	>	// assert head >= 0;
1237	>	// assert capacity == 0 || head < capacity;
1238	>	// assert size == 0 || elements[head] != null;
1239	>	// assert size == 0 || elements[tail()] != null;
1240	>	// assert size == capacity || elements[dec(head, capacity)] == null;
1241	>	// assert size == capacity || elements[inc(tail(), capacity)] == null;
1242		} catch (Throwable t) {
1243		System.err.printf("head=%d size=%d capacity=%d%n",
1244		head, size, elements.length);

Diff Legend

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