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.85 by jsr166, Sun Oct 23 19:30:54 2016 UTC vs.
Revision 1.95 by jsr166, Sat Oct 29 19:10:27 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	<	size = elements.length;
190	<	if (elements.getClass() != Object[].class)
191	<	elements = Arrays.copyOf(elements, size, Object[].class);
193	<	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	<	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) {
246	>	static final <E> E nonNullElementAt(Object[] elements, int i) {
247		@SuppressWarnings("unchecked") E e = (E) elements[i];
248		if (e == null)
249		throw new ConcurrentModificationException();
#	Line 263 | Line 263 | public class ArrayDeque<E> extends Abstr
263		public void addFirst(E e) {
264		// checkInvariants();
265		Objects.requireNonNull(e);
266	<	final Object[] elements;
267	<	final int capacity, s;
268	<	if ((s = size) == (capacity = (elements = this.elements).length))
269	<	addFirstSlowPath(e);
270	<	else
271	<	elements[head = dec(head, capacity)] = e;
266	>	Object[] es;
267	>	int capacity, h;
268	>	final int s;
269	>	if ((s = size) == (capacity = (es = elements).length)) {
270	>	grow(1);
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
276	–	private void addFirstSlowPath(E e) {
277	–	grow(1);
278	–	final Object[] elements = this.elements;
279	–	elements[head = dec(head, elements.length)] = e;
280	–	}
281	–
279		/**
280		* Inserts the specified element at the end of this deque.
281		*
#	Line 290 | Line 287 | public class ArrayDeque<E> extends Abstr
287		public void addLast(E e) {
288		// checkInvariants();
289		Objects.requireNonNull(e);
290	<	final Object[] elements;
291	<	final int capacity, s;
292	<	if ((s = size) == (capacity = (elements = this.elements).length))
293	<	addLastSlowPath(e);
294	<	else
295	<	elements[add(head, s, capacity)] = e;
290	>	Object[] es;
291	>	int capacity;
292	>	final int s;
293	>	if ((s = size) == (capacity = (es = elements).length)) {
294	>	grow(1);
295	>	capacity = (es = elements).length;
296	>	}
297	>	es[add(head, s, capacity)] = e;
298		size = s + 1;
299		// checkInvariants();
300		}
301
303	–	private void addLastSlowPath(E e) {
304	–	grow(1);
305	–	final Object[] elements = this.elements;
306	–	elements[add(head, size, elements.length)] = e;
307	–	}
308	–
302		/**
303		* Adds all of the elements in the specified collection at the end
304		* of this deque, as if by calling {@link #addLast} on each one,
#	Line 317 | Line 310 | public class ArrayDeque<E> extends Abstr
310		* @throws NullPointerException if the specified collection or any
311		*         of its elements are null
312		*/
320	–	@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;
324	<	int newcomers, capacity, s = size;
325	<	if ((newcomers = (a = c.toArray()).length) == 0)
326	<	return false;
327	<	while ((capacity = (elements = this.elements).length) - s < newcomers)
328	<	grow(newcomers - (capacity - s));
329	<	int i = add(head, s, capacity);
330	<	for (Object x : a) {
331	<	Objects.requireNonNull(x);
332	<	elements[i] = x;
333	<	i = inc(i, capacity);
334	<	size++;
335	<	}
336	<	return true;
319	>	return size > s;
320		}
321
322		/**
#	Line 384 | Line 367 | public class ArrayDeque<E> extends Abstr
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);
376	>	if (++h >= elements.length) h = 0;
377	>	head = h;
378		size = s - 1;
379		return e;
380		}
#	Line 398 | 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;
388		@SuppressWarnings("unchecked")
#	Line 413 | 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[] elements = this.elements;
413	>	return (E) elements[add(head, s - 1, elements.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[] elements = this.elements;
427	>	return (E) elements[add(head, s - 1, elements.length)];
428		}
429
430		/**
#	Line 449 | 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) {
452	–	// 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	<	}
446	>	int i, end, to, todo;
447	>	todo = (end = (i = head) + size)
448	>	- (to = (capacity - end >= 0) ? end : capacity);
449	>	for (;; to = todo, i = 0, todo = 0) {
450	>	for (; i < to; i++)
451	>	if (o.equals(elements[i])) {
452	>	delete(i);
453	>	return true;
454	>	}
455	>	if (todo == 0) break;
456		}
457		}
458		return false;
#	Line 479 | Line 474 | public class ArrayDeque<E> extends Abstr
474		if (o != null) {
475		final Object[] elements = this.elements;
476		final int capacity = elements.length;
477	<	for (int k = size, i = add(head, k - 1, capacity);
478	<	--k >= 0; i = dec(i, capacity)) {
479	<	if (o.equals(elements[i])) {
480	<	delete(i);
481	<	return true;
482	<	}
477	>	int i, to, end, todo;
478	>	todo = (to = ((end = (i = tail()) - size) >= -1) ? end : -1) - end;
479	>	for (;; to = (i = capacity - 1) - todo, todo = 0) {
480	>	for (; i > to; i--)
481	>	if (o.equals(elements[i])) {
482	>	delete(i);
483	>	return true;
484	>	}
485	>	if (todo == 0) break;
486		}
487		}
488		return false;
#	Line 632 | Line 630 | public class ArrayDeque<E> extends Abstr
630		System.arraycopy(elements, h, elements, h + 1, front - (i + 1));
631		}
632		elements[h] = null;
633	<	head = inc(h, capacity);
633	>	if ((head = (h + 1)) >= capacity) head = 0;
634		size--;
635		// checkInvariants();
636		return false;
#	Line 710 | Line 708 | public class ArrayDeque<E> extends Abstr
708		}
709
710		public E next() {
711	<	if (remaining == 0)
711	>	if (remaining <= 0)
712		throw new NoSuchElementException();
713	<	E e = checkedElementAt(elements, cursor);
713	>	final Object[] elements = ArrayDeque.this.elements;
714	>	E e = nonNullElementAt(elements, cursor);
715		lastRet = cursor;
716	<	cursor = inc(cursor, elements.length);
716	>	if (++cursor >= elements.length) cursor = 0;
717		remaining--;
718		return e;
719		}
720
721		void postDelete(boolean leftShifted) {
722		if (leftShifted)
723	<	cursor = dec(cursor, elements.length); // undo inc in next
723	>	if (--cursor < 0) cursor = elements.length - 1;
724		}
725
726		public final void remove() {
#	Line 732 | Line 731 | public class ArrayDeque<E> extends Abstr
731		}
732
733		public void forEachRemaining(Consumer<? super E> action) {
734	<	Objects.requireNonNull(action);
735	<	final Object[] elements = ArrayDeque.this.elements;
736	<	final int capacity = elements.length;
737	<	int k = remaining;
738	<	remaining = 0;
739	<	for (int i = cursor; --k >= 0; i = inc(i, capacity))
740	<	action.accept(checkedElementAt(elements, i));
734	>	final int k;
735	>	if ((k = remaining) > 0) {
736	>	remaining = 0;
737	>	ArrayDeque.forEachRemaining(action, elements, cursor, k);
738	>	if ((lastRet = cursor + k - 1) >= elements.length)
739	>	lastRet -= elements.length;
740	>	}
741		}
742		}
743
#	Line 746 | Line 745 | public class ArrayDeque<E> extends Abstr
745		DescendingIterator() { cursor = tail(); }
746
747		public final E next() {
748	<	if (remaining == 0)
748	>	if (remaining <= 0)
749		throw new NoSuchElementException();
750	<	E e = checkedElementAt(elements, cursor);
750	>	final Object[] elements = ArrayDeque.this.elements;
751	>	E e = nonNullElementAt(elements, cursor);
752		lastRet = cursor;
753	<	cursor = dec(cursor, elements.length);
753	>	if (--cursor < 0) cursor = elements.length - 1;
754		remaining--;
755		return e;
756		}
757
758		void postDelete(boolean leftShifted) {
759		if (!leftShifted)
760	<	cursor = inc(cursor, elements.length); // undo dec in next
760	>	if (++cursor >= elements.length) cursor = 0;
761		}
762
763		public final void forEachRemaining(Consumer<? super E> action) {
764	<	Objects.requireNonNull(action);
765	<	final Object[] elements = ArrayDeque.this.elements;
766	<	final int capacity = elements.length;
767	<	int k = remaining;
768	<	remaining = 0;
769	<	for (int i = cursor; --k >= 0; i = dec(i, capacity))
770	<	action.accept(checkedElementAt(elements, i));
764	>	final int k;
765	>	if ((k = remaining) > 0) {
766	>	remaining = 0;
767	>	forEachRemainingDescending(action, elements, cursor, k);
768	>	if ((lastRet = cursor - (k - 1)) < 0)
769	>	lastRet += elements.length;
770	>	}
771		}
772		}
773
#	Line 824 | Line 824 | public class ArrayDeque<E> extends Abstr
824		}
825
826		public void forEachRemaining(Consumer<? super E> action) {
827	<	Objects.requireNonNull(action);
828	<	final Object[] elements = ArrayDeque.this.elements;
829	<	final int capacity = elements.length;
830	<	int k = remaining();
827	>	final int k = remaining(); // side effect!
828		remaining = 0;
829	<	for (int i = cursor; --k >= 0; i = inc(i, capacity))
833	<	action.accept(checkedElementAt(elements, i));
829	>	ArrayDeque.forEachRemaining(action, elements, cursor, k);
830		}
831
832		public boolean tryAdvance(Consumer<? super E> action) {
833		Objects.requireNonNull(action);
834	<	if (remaining() == 0)
834	>	final int k;
835	>	if ((k = remaining()) <= 0)
836		return false;
837	<	action.accept(checkedElementAt(elements, cursor));
838	<	cursor = inc(cursor, elements.length);
839	<	remaining--;
837	>	action.accept(nonNullElementAt(elements, cursor));
838	>	if (++cursor >= elements.length) cursor = 0;
839	>	remaining = k - 1;
840		return true;
841		}
842
#	Line 855 | Line 852 | public class ArrayDeque<E> extends Abstr
852		}
853		}
854
855	<	@Override
855	>	@SuppressWarnings("unchecked")
856		public void forEach(Consumer<? super E> action) {
860	–	// checkInvariants();
857		Objects.requireNonNull(action);
858		final Object[] elements = this.elements;
859		final int capacity = elements.length;
860	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
861	<	action.accept(elementAt(i));
860	>	int i, end, to, todo;
861	>	todo = (end = (i = head) + size)
862	>	- (to = (capacity - end >= 0) ? end : capacity);
863	>	for (;; to = todo, i = 0, todo = 0) {
864	>	for (; i < to; i++)
865	>	action.accept((E) elements[i]);
866	>	if (todo == 0) break;
867	>	}
868		// checkInvariants();
869		}
870
871		/**
872	+	* Calls action on remaining elements, starting at index i and
873	+	* traversing in ascending order.  A variant of forEach that also
874	+	* checks for concurrent modification, for use in iterators.
875	+	*/
876	+	static <E> void forEachRemaining(
877	+	Consumer<? super E> action, Object[] elements, int i, int remaining) {
878	+	Objects.requireNonNull(action);
879	+	final int capacity = elements.length;
880	+	int end, to, todo;
881	+	todo = (end = i + remaining)
882	+	- (to = (capacity - end >= 0) ? end : capacity);
883	+	for (;; to = todo, i = 0, todo = 0) {
884	+	for (; i < to; i++)
885	+	action.accept(nonNullElementAt(elements, i));
886	+	if (todo == 0) break;
887	+	}
888	+	}
889	+
890	+	static <E> void forEachRemainingDescending(
891	+	Consumer<? super E> action, Object[] elements, int i, int remaining) {
892	+	Objects.requireNonNull(action);
893	+	final int capacity = elements.length;
894	+	int end, to, todo;
895	+	todo = (to = ((end = i - remaining) >= -1) ? end : -1) - end;
896	+	for (;; to = (i = capacity - 1) - todo, todo = 0) {
897	+	for (; i > to; i--)
898	+	action.accept(nonNullElementAt(elements, i));
899	+	if (todo == 0) break;
900	+	}
901	+	}
902	+
903	+	/**
904		* Replaces each element of this deque with the result of applying the
905		* operator to that element, as specified by {@link List#replaceAll}.
906		*
#	Line 877 | Line 911 | public class ArrayDeque<E> extends Abstr
911		Objects.requireNonNull(operator);
912		final Object[] elements = this.elements;
913		final int capacity = elements.length;
914	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
915	<	elements[i] = operator.apply(elementAt(i));
914	>	int i, end, to, todo;
915	>	todo = (end = (i = head) + size)
916	>	- (to = (capacity - end >= 0) ? end : capacity);
917	>	for (;; to = todo, i = 0, todo = 0) {
918	>	for (; i < to; i++)
919	>	elements[i] = operator.apply(elementAt(i));
920	>	if (todo == 0) break;
921	>	}
922		// checkInvariants();
923		}
924
925		/**
926		* @throws NullPointerException {@inheritDoc}
927		*/
888	–	@Override
928		public boolean removeIf(Predicate<? super E> filter) {
929		Objects.requireNonNull(filter);
930		return bulkRemove(filter);
#	Line 894 | Line 933 | public class ArrayDeque<E> extends Abstr
933		/**
934		* @throws NullPointerException {@inheritDoc}
935		*/
897	–	@Override
936		public boolean removeAll(Collection<?> c) {
937		Objects.requireNonNull(c);
938		return bulkRemove(e -> c.contains(e));
#	Line 903 | Line 941 | public class ArrayDeque<E> extends Abstr
941		/**
942		* @throws NullPointerException {@inheritDoc}
943		*/
906	–	@Override
944		public boolean retainAll(Collection<?> c) {
945		Objects.requireNonNull(c);
946		return bulkRemove(e -> !c.contains(e));
#	Line 916 | Line 953 | public class ArrayDeque<E> extends Abstr
953		final int capacity = elements.length;
954		int i = head, j = i, remaining = size, deleted = 0;
955		try {
956	<	for (; remaining > 0; remaining--, i = inc(i, capacity)) {
956	>	for (; remaining > 0; remaining--) {
957		@SuppressWarnings("unchecked") E e = (E) elements[i];
958		if (filter.test(e))
959		deleted++;
960		else {
961		if (j != i)
962		elements[j] = e;
963	<	j = inc(j, capacity);
963	>	if (++j >= capacity) j = 0;
964		}
965	+	if (++i >= capacity) i = 0;
966		}
967		return deleted > 0;
968		} catch (Throwable ex) {
969		if (deleted > 0)
970	<	for (; remaining > 0;
933	<	remaining--, i = inc(i, capacity), j = inc(j, capacity))
970	>	for (; remaining > 0; remaining--) {
971		elements[j] = elements[i];
972	+	if (++i >= capacity) i = 0;
973	+	if (++j >= capacity) j = 0;
974	+	}
975		throw ex;
976		} finally {
977		size -= deleted;
978	<	for (; --deleted >= 0; j = inc(j, capacity))
939	<	elements[j] = null;
978	>	clearSlice(elements, j, deleted);
979		// checkInvariants();
980		}
981		}
#	Line 953 | Line 992 | public class ArrayDeque<E> extends Abstr
992		if (o != null) {
993		final Object[] elements = this.elements;
994		final int capacity = elements.length;
995	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
996	<	if (o.equals(elements[i]))
997	<	return true;
995	>	int i, end, to, todo;
996	>	todo = (end = (i = head) + size)
997	>	- (to = (capacity - end >= 0) ? end : capacity);
998	>	for (;; to = todo, i = 0, todo = 0) {
999	>	for (; i < to; i++)
1000	>	if (o.equals(elements[i]))
1001	>	return true;
1002	>	if (todo == 0) break;
1003	>	}
1004		}
1005		return false;
1006		}
#	Line 982 | Line 1027 | public class ArrayDeque<E> extends Abstr
1027		* The deque will be empty after this call returns.
1028		*/
1029		public void clear() {
1030	<	final Object[] elements = this.elements;
986	<	final int capacity = elements.length;
987	<	final int h = this.head;
988	<	final int s = size;
989	<	if (capacity - h >= s)
990	<	Arrays.fill(elements, h, h + s, null);
991	<	else {
992	<	Arrays.fill(elements, h, capacity, null);
993	<	Arrays.fill(elements, 0, s - capacity + h, null);
994	<	}
1030	>	clearSlice(elements, head, size);
1031		size = head = 0;
1032		// checkInvariants();
1033		}
1034
1035		/**
1036	+	* Nulls out count elements, starting at array index from.
1037	+	*/
1038	+	private static void clearSlice(Object[] elements, int from, int count) {
1039	+	final int capacity = elements.length, end = from + count;
1040	+	final int leg = (capacity - end >= 0) ? end : capacity;
1041	+	Arrays.fill(elements, from, leg, null);
1042	+	if (leg != end)
1043	+	Arrays.fill(elements, 0, end - capacity, null);
1044	+	}
1045	+
1046	+	/**
1047		* Returns an array containing all of the elements in this deque
1048		* in proper sequence (from first to last element).
1049		*
#	Line 1010 | Line 1057 | public class ArrayDeque<E> extends Abstr
1057		* @return an array containing all of the elements in this deque
1058		*/
1059		public Object[] toArray() {
1060	<	final int head = this.head;
1061	<	final int firstLeg;
1062	<	Object[] a = Arrays.copyOfRange(elements, head, head + size);
1063	<	if ((firstLeg = elements.length - head) < size)
1064	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1060	>	return toArray(Object[].class);
1061	>	}
1062	>
1063	>	private <T> T[] toArray(Class<T[]> klazz) {
1064	>	final Object[] elements = this.elements;
1065	>	final int capacity = elements.length;
1066	>	final int head = this.head, end = head + size;
1067	>	final T[] a;
1068	>	if (end >= 0) {
1069	>	a = Arrays.copyOfRange(elements, head, end, klazz);
1070	>	} else {
1071	>	// integer overflow!
1072	>	a = Arrays.copyOfRange(elements, 0, size, klazz);
1073	>	System.arraycopy(elements, head, a, 0, capacity - head);
1074	>	}
1075	>	if (end - capacity > 0)
1076	>	System.arraycopy(elements, 0, a, capacity - head, end - capacity);
1077		return a;
1078		}
1079
#	Line 1056 | Line 1115 | public class ArrayDeque<E> extends Abstr
1115		*/
1116		@SuppressWarnings("unchecked")
1117		public <T> T[] toArray(T[] a) {
1118	+	final int size = this.size;
1119	+	if (size > a.length)
1120	+	return toArray((Class<T[]>) a.getClass());
1121		final Object[] elements = this.elements;
1122	<	final int head = this.head;
1123	<	final int firstLeg;
1124	<	boolean wrap = (firstLeg = elements.length - head) < size;
1125	<	if (size > a.length) {
1126	<	a = (T[]) Arrays.copyOfRange(elements, head, head + size,
1127	<	a.getClass());
1128	<	} else {
1129	<	System.arraycopy(elements, head, a, 0, wrap ? firstLeg : size);
1068	<	if (size < a.length)
1069	<	a[size] = null;
1070	<	}
1071	<	if (wrap)
1072	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1122	>	final int capacity = elements.length;
1123	>	final int head = this.head, end = head + size;
1124	>	final int front = (capacity - end >= 0) ? size : capacity - head;
1125	>	System.arraycopy(elements, head, a, 0, front);
1126	>	if (front != size)
1127	>	System.arraycopy(elements, 0, a, capacity - head, end - capacity);
1128	>	if (size < a.length)
1129	>	a[size] = null;
1130		return a;
1131		}
1132
#	Line 1112 | Line 1169 | public class ArrayDeque<E> extends Abstr
1169		// Write out elements in order.
1170		final Object[] elements = this.elements;
1171		final int capacity = elements.length;
1172	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
1173	<	s.writeObject(elements[i]);
1172	>	int i, end, to, todo;
1173	>	todo = (end = (i = head) + size)
1174	>	- (to = (capacity - end >= 0) ? end : capacity);
1175	>	for (;; to = todo, i = 0, todo = 0) {
1176	>	for (; i < to; i++)
1177	>	s.writeObject(elements[i]);
1178	>	if (todo == 0) break;
1179	>	}
1180		}
1181
1182		/**
#	Line 1136 | Line 1199 | public class ArrayDeque<E> extends Abstr
1199		}
1200
1201		/** debugging */
1202	<	private void checkInvariants() {
1202	>	void checkInvariants() {
1203		try {
1204		int capacity = elements.length;
1205	<	assert size >= 0 && size <= capacity;
1206	<	assert head >= 0 && ((capacity == 0 && head == 0 && size == 0)
1207	<	|| head < capacity);
1208	<	assert size == 0
1209	<	|| (elements[head] != null && elements[tail()] != null);
1210	<	assert size == capacity
1211	<	|| (elements[dec(head, capacity)] == null
1149	<	&& elements[inc(tail(), capacity)] == null);
1205	>	// assert size >= 0 && size <= capacity;
1206	>	// assert head >= 0;
1207	>	// assert capacity == 0 || head < capacity;
1208	>	// assert size == 0 || elements[head] != null;
1209	>	// assert size == 0 || elements[tail()] != null;
1210	>	// assert size == capacity || elements[dec(head, capacity)] == null;
1211	>	// assert size == capacity || elements[inc(tail(), capacity)] == null;
1212		} catch (Throwable t) {
1213		System.err.printf("head=%d size=%d capacity=%d%n",
1214		head, size, elements.length);

Diff Legend

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