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.91 by jsr166, Tue Oct 25 16:51:17 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 187 | Line 186 | public class ArrayDeque<E> extends Abstr
186		Object[] elements = c.toArray();
187		// defend against c.toArray (incorrectly) not returning Object[]
188		// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
189	+	size = elements.length;
190		if (elements.getClass() != Object[].class)
191		elements = Arrays.copyOf(elements, size, Object[].class);
192		for (Object obj : elements)
193		Objects.requireNonNull(obj);
194	–	size = elements.length;
194		this.elements = elements;
195		}
196
#	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
#	Line 264 | Line 263 | public class ArrayDeque<E> extends Abstr
263		// checkInvariants();
264		Objects.requireNonNull(e);
265		Object[] elements;
266	<	int capacity, s = size;
267	<	while (s == (capacity = (elements = this.elements).length))
266	>	int capacity, h;
267	>	final int s;
268	>	if ((s = size) == (capacity = (elements = this.elements).length)) {
269		grow(1);
270	<	elements[head = dec(head, capacity)] = e;
270	>	capacity = (elements = this.elements).length;
271	>	}
272	>	if ((h = head - 1) < 0) h = capacity - 1;
273	>	elements[head = h] = e;
274		size = s + 1;
275	+	// checkInvariants();
276		}
277
278		/**
#	Line 283 | Line 287 | public class ArrayDeque<E> extends Abstr
287		// checkInvariants();
288		Objects.requireNonNull(e);
289		Object[] elements;
290	<	int capacity, s = size;
291	<	while (s == (capacity = (elements = this.elements).length))
290	>	int capacity;
291	>	final int s;
292	>	if ((s = size) == (capacity = (elements = this.elements).length)) {
293		grow(1);
294	+	capacity = (elements = this.elements).length;
295	+	}
296		elements[add(head, s, capacity)] = e;
297		size = s + 1;
298	+	// checkInvariants();
299		}
300
301		/**
#	Line 301 | Line 309 | public class ArrayDeque<E> extends Abstr
309		* @throws NullPointerException if the specified collection or any
310		*         of its elements are null
311		*/
304	–	@Override
312		public boolean addAll(Collection<? extends E> c) {
313	+	final int s = size, needed = c.size() - (elements.length - s);
314	+	if (needed > 0)
315	+	grow(needed);
316	+	c.forEach((e) -> addLast(e));
317		// checkInvariants();
318	<	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;
318	>	return size > s;
319		}
320
321		/**
#	Line 349 | Line 347 | public class ArrayDeque<E> extends Abstr
347		*/
348		public E removeFirst() {
349		// checkInvariants();
350	<	E x = pollFirst();
351	<	if (x == null)
350	>	E e = pollFirst();
351	>	if (e == null)
352		throw new NoSuchElementException();
353	<	return x;
353	>	return e;
354		}
355
356		/**
#	Line 360 | Line 358 | public class ArrayDeque<E> extends Abstr
358		*/
359		public E removeLast() {
360		// checkInvariants();
361	<	E x = pollLast();
362	<	if (x == null)
361	>	E e = pollLast();
362	>	if (e == null)
363		throw new NoSuchElementException();
364	<	return x;
364	>	return e;
365		}
366
367		public E pollFirst() {
368		// checkInvariants();
369	<	final int s, h;
370	<	if ((s = size) == 0)
369	>	int s, h;
370	>	if ((s = size) <= 0)
371		return null;
372		final Object[] elements = this.elements;
373		@SuppressWarnings("unchecked") E e = (E) elements[h = head];
374		elements[h] = null;
375	<	head = inc(h, elements.length);
375	>	if (++h >= elements.length) h = 0;
376	>	head = h;
377		size = s - 1;
378		return e;
379		}
#	Line 382 | Line 381 | public class ArrayDeque<E> extends Abstr
381		public E pollLast() {
382		// checkInvariants();
383		final int s, tail;
384	<	if ((s = size) == 0)
384	>	if ((s = size) <= 0)
385		return null;
386		final Object[] elements = this.elements;
387		@SuppressWarnings("unchecked")
#	Line 397 | Line 396 | public class ArrayDeque<E> extends Abstr
396		*/
397		public E getFirst() {
398		// checkInvariants();
399	<	if (size == 0) throw new NoSuchElementException();
399	>	if (size <= 0) throw new NoSuchElementException();
400		return elementAt(head);
401		}
402
403		/**
404		* @throws NoSuchElementException {@inheritDoc}
405		*/
406	+	@SuppressWarnings("unchecked")
407		public E getLast() {
408		// checkInvariants();
409	<	if (size == 0) throw new NoSuchElementException();
410	<	return elementAt(tail());
409	>	final int s;
410	>	if ((s = size) <= 0) throw new NoSuchElementException();
411	>	final Object[] elements = this.elements;
412	>	return (E) elements[add(head, s - 1, elements.length)];
413		}
414
415		public E peekFirst() {
416		// checkInvariants();
417	<	return (size == 0) ? null : elementAt(head);
417	>	return (size <= 0) ? null : elementAt(head);
418		}
419
420	+	@SuppressWarnings("unchecked")
421		public E peekLast() {
422		// checkInvariants();
423	<	return (size == 0) ? null : elementAt(tail());
423	>	final int s;
424	>	if ((s = size) <= 0) return null;
425	>	final Object[] elements = this.elements;
426	>	return (E) elements[add(head, s - 1, elements.length)];
427		}
428
429		/**
#	Line 433 | Line 439 | public class ArrayDeque<E> extends Abstr
439		* @return {@code true} if the deque contained the specified element
440		*/
441		public boolean removeFirstOccurrence(Object o) {
436	–	// checkInvariants();
442		if (o != null) {
443		final Object[] elements = this.elements;
444		final int capacity = elements.length;
445	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity)) {
446	<	if (o.equals(elements[i])) {
447	<	delete(i);
448	<	return true;
449	<	}
445	>	int from, end, to, todo;
446	>	todo = (end = (from = head) + size)
447	>	- (to = (capacity - end >= 0) ? end : capacity);
448	>	for (;; from = 0, to = todo, todo = 0) {
449	>	for (int i = from; i < to; i++)
450	>	if (o.equals(elements[i])) {
451	>	delete(i);
452	>	return true;
453	>	}
454	>	if (todo == 0) break;
455		}
456		}
457		return false;
#	Line 463 | Line 473 | public class ArrayDeque<E> extends Abstr
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	<	}
476	>	int from, to, end, todo;
477	>	todo = (to = ((end = (from = tail()) - size) >= -1) ? end : -1) - end;
478	>	for (;; from = capacity - 1, to = capacity - 1 - todo, todo = 0) {
479	>	for (int i = from; i > to; i--)
480	>	if (o.equals(elements[i])) {
481	>	delete(i);
482	>	return true;
483	>	}
484	>	if (todo == 0) break;
485		}
486		}
487		return false;
#	Line 616 | Line 629 | public class ArrayDeque<E> extends Abstr
629		System.arraycopy(elements, h, elements, h + 1, front - (i + 1));
630		}
631		elements[h] = null;
632	<	head = inc(h, capacity);
632	>	if ((head = (h + 1)) >= capacity) head = 0;
633		size--;
634		// checkInvariants();
635		return false;
#	Line 689 | Line 702 | public class ArrayDeque<E> extends Abstr
702
703		DeqIterator() { cursor = head; }
704
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	–
705		public final boolean hasNext() {
706		return remaining > 0;
707		}
708
709	<	public final E next() {
710	<	if (remaining == 0)
709	>	public E next() {
710	>	if (remaining <= 0)
711		throw new NoSuchElementException();
712	+	final Object[] elements = ArrayDeque.this.elements;
713		E e = checkedElementAt(elements, cursor);
714		lastRet = cursor;
715	<	cursor = advance(cursor, elements.length);
715	>	if (++cursor >= elements.length) cursor = 0;
716		remaining--;
717		return e;
718		}
719
720	+	void postDelete(boolean leftShifted) {
721	+	if (leftShifted)
722	+	if (--cursor < 0) cursor = elements.length - 1;
723	+	}
724	+
725		public final void remove() {
726		if (lastRet < 0)
727		throw new IllegalStateException();
728	<	doRemove();
728	>	postDelete(delete(lastRet));
729		lastRet = -1;
730		}
731
732	<	public final void forEachRemaining(Consumer<? super E> action) {
733	<	Objects.requireNonNull(action);
734	<	final Object[] elements = ArrayDeque.this.elements;
735	<	final int capacity = elements.length;
736	<	int k = remaining;
737	<	remaining = 0;
738	<	for (int i = cursor; --k >= 0; i = advance(i, capacity))
739	<	action.accept(checkedElementAt(elements, i));
732	>	public void forEachRemaining(Consumer<? super E> action) {
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[] elements = ArrayDeque.this.elements;
750	>	E e = checkedElementAt(elements, cursor);
751	>	lastRet = cursor;
752	>	if (--cursor < 0) cursor = elements.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	>	final int k;
764	>	if ((k = remaining) > 0) {
765	>	remaining = 0;
766	>	forEachRemainingDescending(action, elements, cursor, k);
767	>	if ((lastRet = cursor - (k - 1)) < 0)
768	>	lastRet += elements.length;
769	>	}
770		}
771		}
772
#	Line 798 | Line 823 | public class ArrayDeque<E> extends Abstr
823		}
824
825		public void forEachRemaining(Consumer<? super E> action) {
826	<	Objects.requireNonNull(action);
802	<	final Object[] elements = ArrayDeque.this.elements;
803	<	final int capacity = elements.length;
804	<	int k = remaining();
826	>	final int k = remaining(); // side effect!
827		remaining = 0;
828	<	for (int i = cursor; --k >= 0; i = inc(i, capacity))
807	<	action.accept(checkedElementAt(elements, i));
828	>	ArrayDeque.forEachRemaining(action, elements, cursor, k);
829		}
830
831		public boolean tryAdvance(Consumer<? super E> action) {
832		Objects.requireNonNull(action);
833	<	if (remaining() == 0)
833	>	final int k;
834	>	if ((k = remaining()) <= 0)
835		return false;
836		action.accept(checkedElementAt(elements, cursor));
837	<	cursor = inc(cursor, elements.length);
838	<	remaining--;
837	>	if (++cursor >= elements.length) cursor = 0;
838	>	remaining = k - 1;
839		return true;
840		}
841
#	Line 829 | Line 851 | public class ArrayDeque<E> extends Abstr
851		}
852		}
853
854	<	@Override
854	>	@SuppressWarnings("unchecked")
855		public void forEach(Consumer<? super E> action) {
834	–	// checkInvariants();
856		Objects.requireNonNull(action);
857		final Object[] elements = this.elements;
858		final int capacity = elements.length;
859	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
860	<	action.accept(elementAt(i));
859	>	int from, end, to, todo;
860	>	todo = (end = (from = head) + size)
861	>	- (to = (capacity - end >= 0) ? end : capacity);
862	>	for (;; from = 0, to = todo, todo = 0) {
863	>	for (int i = from; i < to; i++)
864	>	action.accept((E) elements[i]);
865	>	if (todo == 0) break;
866	>	}
867		// checkInvariants();
868		}
869
870		/**
871	+	* A variant of forEach that also checks for concurrent
872	+	* modification, for use in iterators.
873	+	*/
874	+	static <E> void forEachRemaining(
875	+	Consumer<? super E> action, Object[] elements, int from, int remaining) {
876	+	Objects.requireNonNull(action);
877	+	final int capacity = elements.length;
878	+	int end, to, todo;
879	+	todo = (end = from + remaining)
880	+	- (to = (capacity - end >= 0) ? end : capacity);
881	+	for (;; from = 0, to = todo, todo = 0) {
882	+	for (int i = from; i < to; i++) {
883	+	@SuppressWarnings("unchecked") E e = (E) elements[i];
884	+	if (e == null)
885	+	throw new ConcurrentModificationException();
886	+	action.accept(e);
887	+	}
888	+	if (todo == 0) break;
889	+	}
890	+	}
891	+
892	+	static <E> void forEachRemainingDescending(
893	+	Consumer<? super E> action, Object[] elements, int from, int remaining) {
894	+	Objects.requireNonNull(action);
895	+	final int capacity = elements.length;
896	+	int end, to, todo;
897	+	todo = (to = ((end = from - remaining) >= -1) ? end : -1) - end;
898	+	for (;; from = capacity - 1, to = capacity - 1 - todo, todo = 0) {
899	+	for (int i = from; i > to; i--) {
900	+	@SuppressWarnings("unchecked") E e = (E) elements[i];
901	+	if (e == null)
902	+	throw new ConcurrentModificationException();
903	+	action.accept(e);
904	+	}
905	+	if (todo == 0) break;
906	+	}
907	+	}
908	+
909	+	/**
910		* Replaces each element of this deque with the result of applying the
911		* operator to that element, as specified by {@link List#replaceAll}.
912		*
#	Line 851 | Line 917 | public class ArrayDeque<E> extends Abstr
917		Objects.requireNonNull(operator);
918		final Object[] elements = this.elements;
919		final int capacity = elements.length;
920	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
921	<	elements[i] = operator.apply(elementAt(i));
920	>	int from, end, to, todo;
921	>	todo = (end = (from = head) + size)
922	>	- (to = (capacity - end >= 0) ? end : capacity);
923	>	for (;; from = 0, to = todo, todo = 0) {
924	>	for (int i = from; i < to; i++)
925	>	elements[i] = operator.apply(elementAt(i));
926	>	if (todo == 0) break;
927	>	}
928		// checkInvariants();
929		}
930
931		/**
932		* @throws NullPointerException {@inheritDoc}
933		*/
862	–	@Override
934		public boolean removeIf(Predicate<? super E> filter) {
935		Objects.requireNonNull(filter);
936		return bulkRemove(filter);
#	Line 868 | Line 939 | public class ArrayDeque<E> extends Abstr
939		/**
940		* @throws NullPointerException {@inheritDoc}
941		*/
871	–	@Override
942		public boolean removeAll(Collection<?> c) {
943		Objects.requireNonNull(c);
944		return bulkRemove(e -> c.contains(e));
#	Line 877 | Line 947 | public class ArrayDeque<E> extends Abstr
947		/**
948		* @throws NullPointerException {@inheritDoc}
949		*/
880	–	@Override
950		public boolean retainAll(Collection<?> c) {
951		Objects.requireNonNull(c);
952		return bulkRemove(e -> !c.contains(e));
#	Line 890 | Line 959 | public class ArrayDeque<E> extends Abstr
959		final int capacity = elements.length;
960		int i = head, j = i, remaining = size, deleted = 0;
961		try {
962	<	for (; remaining > 0; remaining--, i = inc(i, capacity)) {
962	>	for (; remaining > 0; remaining--) {
963		@SuppressWarnings("unchecked") E e = (E) elements[i];
964		if (filter.test(e))
965		deleted++;
966		else {
967		if (j != i)
968		elements[j] = e;
969	<	j = inc(j, capacity);
969	>	if (++j >= capacity) j = 0;
970		}
971	+	if (++i >= capacity) i = 0;
972		}
973		return deleted > 0;
974		} catch (Throwable ex) {
975		if (deleted > 0)
976	<	for (; remaining > 0;
907	<	remaining--, i = inc(i, capacity), j = inc(j, capacity))
976	>	for (; remaining > 0; remaining--) {
977		elements[j] = elements[i];
978	+	if (++i >= capacity) i = 0;
979	+	if (++j >= capacity) j = 0;
980	+	}
981		throw ex;
982		} finally {
983		size -= deleted;
984	<	for (; --deleted >= 0; j = inc(j, capacity))
913	<	elements[j] = null;
984	>	clearSlice(elements, j, deleted);
985		// checkInvariants();
986		}
987		}
#	Line 927 | Line 998 | public class ArrayDeque<E> extends Abstr
998		if (o != null) {
999		final Object[] elements = this.elements;
1000		final int capacity = elements.length;
1001	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
1002	<	if (o.equals(elements[i]))
1003	<	return true;
1001	>	int from, end, to, todo;
1002	>	todo = (end = (from = head) + size)
1003	>	- (to = (capacity - end >= 0) ? end : capacity);
1004	>	for (;; from = 0, to = todo, todo = 0) {
1005	>	for (int i = from; i < to; i++)
1006	>	if (o.equals(elements[i]))
1007	>	return true;
1008	>	if (todo == 0) break;
1009	>	}
1010		}
1011		return false;
1012		}
#	Line 956 | Line 1033 | public class ArrayDeque<E> extends Abstr
1033		* The deque will be empty after this call returns.
1034		*/
1035		public void clear() {
1036	<	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	<	}
1036	>	clearSlice(elements, head, size);
1037		size = head = 0;
1038		// checkInvariants();
1039		}
1040
1041		/**
1042	+	* Nulls out count elements, starting at array index from.
1043	+	*/
1044	+	private static void clearSlice(Object[] elements, int from, int count) {
1045	+	final int capacity = elements.length, end = from + count;
1046	+	final int leg = (capacity - end >= 0) ? end : capacity;
1047	+	Arrays.fill(elements, from, leg, null);
1048	+	if (leg != end)
1049	+	Arrays.fill(elements, 0, end - capacity, null);
1050	+	}
1051	+
1052	+	/**
1053		* Returns an array containing all of the elements in this deque
1054		* in proper sequence (from first to last element).
1055		*
#	Line 984 | Line 1063 | public class ArrayDeque<E> extends Abstr
1063		* @return an array containing all of the elements in this deque
1064		*/
1065		public Object[] toArray() {
1066	<	final int head = this.head;
1067	<	final int firstLeg;
1068	<	Object[] a = Arrays.copyOfRange(elements, head, head + size);
1069	<	if ((firstLeg = elements.length - head) < size)
1070	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1066	>	return toArray(Object[].class);
1067	>	}
1068	>
1069	>	private <T> T[] toArray(Class<T[]> klazz) {
1070	>	final Object[] elements = this.elements;
1071	>	final int capacity = elements.length;
1072	>	final int head = this.head, end = head + size;
1073	>	final T[] a;
1074	>	if (end >= 0) {
1075	>	a = Arrays.copyOfRange(elements, head, end, klazz);
1076	>	} else {
1077	>	// integer overflow!
1078	>	a = Arrays.copyOfRange(elements, 0, size, klazz);
1079	>	System.arraycopy(elements, head, a, 0, capacity - head);
1080	>	}
1081	>	if (end - capacity > 0)
1082	>	System.arraycopy(elements, 0, a, capacity - head, end - capacity);
1083		return a;
1084		}
1085
#	Line 1030 | Line 1121 | public class ArrayDeque<E> extends Abstr
1121		*/
1122		@SuppressWarnings("unchecked")
1123		public <T> T[] toArray(T[] a) {
1124	+	final int size = this.size;
1125	+	if (size > a.length)
1126	+	return toArray((Class<T[]>) a.getClass());
1127		final Object[] elements = this.elements;
1128	<	final int head = this.head;
1129	<	final int firstLeg;
1130	<	boolean wrap = (firstLeg = elements.length - head) < size;
1131	<	if (size > a.length) {
1132	<	a = (T[]) Arrays.copyOfRange(elements, head, head + size,
1133	<	a.getClass());
1134	<	} else {
1135	<	System.arraycopy(elements, head, a, 0, wrap ? firstLeg : size);
1042	<	if (size < a.length)
1043	<	a[size] = null;
1044	<	}
1045	<	if (wrap)
1046	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1128	>	final int capacity = elements.length;
1129	>	final int head = this.head, end = head + size;
1130	>	final int front = (capacity - end >= 0) ? size : capacity - head;
1131	>	System.arraycopy(elements, head, a, 0, front);
1132	>	if (front != size)
1133	>	System.arraycopy(elements, 0, a, capacity - head, end - capacity);
1134	>	if (size < a.length)
1135	>	a[size] = null;
1136		return a;
1137		}
1138
#	Line 1086 | Line 1175 | public class ArrayDeque<E> extends Abstr
1175		// Write out elements in order.
1176		final Object[] elements = this.elements;
1177		final int capacity = elements.length;
1178	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
1179	<	s.writeObject(elements[i]);
1178	>	int from, end, to, todo;
1179	>	todo = (end = (from = head) + size)
1180	>	- (to = (capacity - end >= 0) ? end : capacity);
1181	>	for (;; from = 0, to = todo, todo = 0) {
1182	>	for (int i = from; i < to; i++)
1183	>	s.writeObject(elements[i]);
1184	>	if (todo == 0) break;
1185	>	}
1186		}
1187
1188		/**
#	Line 1110 | Line 1205 | public class ArrayDeque<E> extends Abstr
1205		}
1206
1207		/** debugging */
1208	<	private void checkInvariants() {
1208	>	void checkInvariants() {
1209		try {
1210		int capacity = elements.length;
1211	<	assert size >= 0 && size <= capacity;
1212	<	assert head >= 0 && ((capacity == 0 && head == 0 && size == 0)
1213	<	|| head < capacity);
1214	<	assert size == 0
1215	<	|| (elements[head] != null && elements[tail()] != null);
1216	<	assert size == capacity
1217	<	|| (elements[dec(head, capacity)] == null
1123	<	&& elements[inc(tail(), capacity)] == null);
1211	>	// assert size >= 0 && size <= capacity;
1212	>	// assert head >= 0;
1213	>	// assert capacity == 0 || head < capacity;
1214	>	// assert size == 0 || elements[head] != null;
1215	>	// assert size == 0 || elements[tail()] != null;
1216	>	// assert size == capacity || elements[dec(head, capacity)] == null;
1217	>	// assert size == capacity || elements[inc(tail(), capacity)] == null;
1218		} catch (Throwable t) {
1219		System.err.printf("head=%d size=%d capacity=%d%n",
1220		head, size, elements.length);

Diff Legend

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