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.82 by jsr166, Sat Oct 22 19:42:42 2016 UTC vs.
Revision 1.98 by jsr166, Sat Oct 29 22:47:55 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	<	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;
273	–	}
274	–
275	–	private void addFirstSlowPath(E e) {
276	–	grow(1);
277	–	final Object[] elements = this.elements;
278	–	elements[head = dec(head, elements.length)] = e;
276		// checkInvariants();
277		}
278
#	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;
300	–	}
301	–
302	–	private void addLastSlowPath(E e) {
303	–	grow(1);
304	–	final Object[] elements = this.elements;
305	–	elements[add(head, size, elements.length)] = e;
299		// checkInvariants();
300		}
301
#	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 365 | 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 376 | 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);
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 733 | Line 732 | public class ArrayDeque<E> extends Abstr
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));
735	>	final int k;
736	>	if ((k = remaining) > 0) {
737	>	remaining = 0;
738	>	ArrayDeque.forEachRemaining(action, elements, cursor, k);
739	>	if ((lastRet = cursor + k - 1) >= elements.length)
740	>	lastRet -= elements.length;
741	>	}
742		}
743		}
744
#	Line 746 | Line 746 | public class ArrayDeque<E> extends Abstr
746		DescendingIterator() { cursor = tail(); }
747
748		public final E next() {
749	<	if (remaining == 0)
749	>	if (remaining <= 0)
750		throw new NoSuchElementException();
751	<	E e = checkedElementAt(elements, cursor);
751	>	final Object[] elements = ArrayDeque.this.elements;
752	>	E e = nonNullElementAt(elements, cursor);
753		lastRet = cursor;
754	<	cursor = dec(cursor, elements.length);
754	>	if (--cursor < 0) cursor = elements.length - 1;
755		remaining--;
756		return e;
757		}
758
759		void postDelete(boolean leftShifted) {
760		if (!leftShifted)
761	<	cursor = inc(cursor, elements.length); // undo dec in next
761	>	if (++cursor >= elements.length) cursor = 0;
762		}
763
764		public final void forEachRemaining(Consumer<? super E> action) {
765		Objects.requireNonNull(action);
766	<	final Object[] elements = ArrayDeque.this.elements;
767	<	final int capacity = elements.length;
768	<	int k = remaining;
769	<	remaining = 0;
770	<	for (int i = cursor; --k >= 0; i = dec(i, capacity))
771	<	action.accept(checkedElementAt(elements, i));
766	>	final int k;
767	>	if ((k = remaining) > 0) {
768	>	remaining = 0;
769	>	final Object[] elements = ArrayDeque.this.elements;
770	>	int i, end, to, todo;
771	>	todo = (to = ((end = (i = cursor) - k) >= -1) ? end : -1) - end;
772	>	for (;; to = (i = elements.length - 1) - todo, todo = 0) {
773	>	for (; i > to; i--)
774	>	action.accept(nonNullElementAt(elements, i));
775	>	if (todo == 0) break;
776	>	}
777	>	if ((lastRet = cursor - (k - 1)) < 0)
778	>	lastRet += elements.length;
779	>	}
780		}
781		}
782
#	Line 825 | Line 834 | public class ArrayDeque<E> extends Abstr
834
835		public void forEachRemaining(Consumer<? super E> action) {
836		Objects.requireNonNull(action);
837	<	final Object[] elements = ArrayDeque.this.elements;
829	<	final int capacity = elements.length;
830	<	int k = remaining();
837	>	final int k = remaining(); // side effect!
838		remaining = 0;
839	<	for (int i = cursor; --k >= 0; i = inc(i, capacity))
833	<	action.accept(checkedElementAt(elements, i));
839	>	ArrayDeque.forEachRemaining(action, elements, cursor, k);
840		}
841
842		public boolean tryAdvance(Consumer<? super E> action) {
843		Objects.requireNonNull(action);
844	<	if (remaining() == 0)
844	>	final int k;
845	>	if ((k = remaining()) <= 0)
846		return false;
847	<	action.accept(checkedElementAt(elements, cursor));
848	<	cursor = inc(cursor, elements.length);
849	<	remaining--;
847	>	action.accept(nonNullElementAt(elements, cursor));
848	>	if (++cursor >= elements.length) cursor = 0;
849	>	remaining = k - 1;
850		return true;
851		}
852
#	Line 855 | Line 862 | public class ArrayDeque<E> extends Abstr
862		}
863		}
864
865	<	@Override
865	>	@SuppressWarnings("unchecked")
866		public void forEach(Consumer<? super E> action) {
860	–	// checkInvariants();
867		Objects.requireNonNull(action);
868		final Object[] elements = this.elements;
869		final int capacity = elements.length;
870	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
871	<	action.accept(elementAt(i));
870	>	int i, end, to, todo;
871	>	todo = (end = (i = head) + size)
872	>	- (to = (capacity - end >= 0) ? end : capacity);
873	>	for (;; to = todo, i = 0, todo = 0) {
874	>	for (; i < to; i++)
875	>	action.accept((E) elements[i]);
876	>	if (todo == 0) break;
877	>	}
878		// checkInvariants();
879		}
880
881		/**
882	+	* Calls action on remaining elements, starting at index i and
883	+	* traversing in ascending order.  A variant of forEach that also
884	+	* checks for concurrent modification, for use in iterators.
885	+	*/
886	+	static <E> void forEachRemaining(
887	+	Consumer<? super E> action, Object[] es, int i, int remaining) {
888	+	final int capacity = es.length;
889	+	int end, to, todo;
890	+	todo = (end = i + remaining)
891	+	- (to = (capacity - end >= 0) ? end : capacity);
892	+	for (;; to = todo, i = 0, todo = 0) {
893	+	for (; i < to; i++)
894	+	action.accept(nonNullElementAt(es, i));
895	+	if (todo == 0) break;
896	+	}
897	+	}
898	+
899	+	/**
900		* Replaces each element of this deque with the result of applying the
901		* operator to that element, as specified by {@link List#replaceAll}.
902		*
#	Line 877 | Line 907 | public class ArrayDeque<E> extends Abstr
907		Objects.requireNonNull(operator);
908		final Object[] elements = this.elements;
909		final int capacity = elements.length;
910	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
911	<	elements[i] = operator.apply(elementAt(i));
910	>	int i, end, to, todo;
911	>	todo = (end = (i = head) + size)
912	>	- (to = (capacity - end >= 0) ? end : capacity);
913	>	for (;; to = todo, i = 0, todo = 0) {
914	>	for (; i < to; i++)
915	>	elements[i] = operator.apply(elementAt(i));
916	>	if (todo == 0) break;
917	>	}
918		// checkInvariants();
919		}
920
921		/**
922		* @throws NullPointerException {@inheritDoc}
923		*/
888	–	@Override
924		public boolean removeIf(Predicate<? super E> filter) {
925		Objects.requireNonNull(filter);
926		return bulkRemove(filter);
#	Line 894 | Line 929 | public class ArrayDeque<E> extends Abstr
929		/**
930		* @throws NullPointerException {@inheritDoc}
931		*/
897	–	@Override
932		public boolean removeAll(Collection<?> c) {
933		Objects.requireNonNull(c);
934		return bulkRemove(e -> c.contains(e));
#	Line 903 | Line 937 | public class ArrayDeque<E> extends Abstr
937		/**
938		* @throws NullPointerException {@inheritDoc}
939		*/
906	–	@Override
940		public boolean retainAll(Collection<?> c) {
941		Objects.requireNonNull(c);
942		return bulkRemove(e -> !c.contains(e));
#	Line 916 | Line 949 | public class ArrayDeque<E> extends Abstr
949		final int capacity = elements.length;
950		int i = head, j = i, remaining = size, deleted = 0;
951		try {
952	<	for (; remaining > 0; remaining--, i = inc(i, capacity)) {
952	>	for (; remaining > 0; remaining--) {
953		@SuppressWarnings("unchecked") E e = (E) elements[i];
954		if (filter.test(e))
955		deleted++;
956		else {
957		if (j != i)
958		elements[j] = e;
959	<	j = inc(j, capacity);
959	>	if (++j >= capacity) j = 0;
960		}
961	+	if (++i >= capacity) i = 0;
962		}
963		return deleted > 0;
964		} catch (Throwable ex) {
965		if (deleted > 0)
966	<	for (; remaining > 0;
933	<	remaining--, i = inc(i, capacity), j = inc(j, capacity))
966	>	for (; remaining > 0; remaining--) {
967		elements[j] = elements[i];
968	+	if (++i >= capacity) i = 0;
969	+	if (++j >= capacity) j = 0;
970	+	}
971		throw ex;
972		} finally {
973		size -= deleted;
974	<	for (; --deleted >= 0; j = inc(j, capacity))
939	<	elements[j] = null;
974	>	clearSlice(elements, j, deleted);
975		// checkInvariants();
976		}
977		}
#	Line 953 | Line 988 | public class ArrayDeque<E> extends Abstr
988		if (o != null) {
989		final Object[] elements = this.elements;
990		final int capacity = elements.length;
991	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
992	<	if (o.equals(elements[i]))
993	<	return true;
991	>	int i, end, to, todo;
992	>	todo = (end = (i = head) + size)
993	>	- (to = (capacity - end >= 0) ? end : capacity);
994	>	for (;; to = todo, i = 0, todo = 0) {
995	>	for (; i < to; i++)
996	>	if (o.equals(elements[i]))
997	>	return true;
998	>	if (todo == 0) break;
999	>	}
1000		}
1001		return false;
1002		}
#	Line 982 | Line 1023 | public class ArrayDeque<E> extends Abstr
1023		* The deque will be empty after this call returns.
1024		*/
1025		public void clear() {
1026	<	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	<	}
1026	>	clearSlice(elements, head, size);
1027		size = head = 0;
1028		// checkInvariants();
1029		}
1030
1031		/**
1032	+	* Nulls out count elements, starting at array index from.
1033	+	*/
1034	+	private static void clearSlice(Object[] es, int from, int count) {
1035	+	final int capacity = es.length, end = from + count;
1036	+	final int leg = (capacity - end >= 0) ? end : capacity;
1037	+	Arrays.fill(es, from, leg, null);
1038	+	if (leg != end)
1039	+	Arrays.fill(es, 0, end - capacity, null);
1040	+	}
1041	+
1042	+	/**
1043		* Returns an array containing all of the elements in this deque
1044		* in proper sequence (from first to last element).
1045		*
#	Line 1010 | Line 1053 | public class ArrayDeque<E> extends Abstr
1053		* @return an array containing all of the elements in this deque
1054		*/
1055		public Object[] toArray() {
1056	<	final int head = this.head;
1057	<	final int firstLeg;
1058	<	Object[] a = Arrays.copyOfRange(elements, head, head + size);
1059	<	if ((firstLeg = elements.length - head) < size)
1060	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1056	>	return toArray(Object[].class);
1057	>	}
1058	>
1059	>	private <T> T[] toArray(Class<T[]> klazz) {
1060	>	final Object[] elements = this.elements;
1061	>	final int capacity = elements.length;
1062	>	final int head = this.head, end = head + size;
1063	>	final T[] a;
1064	>	if (end >= 0) {
1065	>	a = Arrays.copyOfRange(elements, head, end, klazz);
1066	>	} else {
1067	>	// integer overflow!
1068	>	a = Arrays.copyOfRange(elements, 0, size, klazz);
1069	>	System.arraycopy(elements, head, a, 0, capacity - head);
1070	>	}
1071	>	if (end - capacity > 0)
1072	>	System.arraycopy(elements, 0, a, capacity - head, end - capacity);
1073		return a;
1074		}
1075
#	Line 1056 | Line 1111 | public class ArrayDeque<E> extends Abstr
1111		*/
1112		@SuppressWarnings("unchecked")
1113		public <T> T[] toArray(T[] a) {
1114	+	final int size = this.size;
1115	+	if (size > a.length)
1116	+	return toArray((Class<T[]>) a.getClass());
1117		final Object[] elements = this.elements;
1118	<	final int head = this.head;
1119	<	final int firstLeg;
1120	<	boolean wrap = (firstLeg = elements.length - head) < size;
1121	<	if (size > a.length) {
1122	<	a = (T[]) Arrays.copyOfRange(elements, head, head + size,
1123	<	a.getClass());
1124	<	} else {
1125	<	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);
1118	>	final int capacity = elements.length;
1119	>	final int head = this.head, end = head + size;
1120	>	final int front = (capacity - end >= 0) ? size : capacity - head;
1121	>	System.arraycopy(elements, head, a, 0, front);
1122	>	if (front != size)
1123	>	System.arraycopy(elements, 0, a, capacity - head, end - capacity);
1124	>	if (size < a.length)
1125	>	a[size] = null;
1126		return a;
1127		}
1128
#	Line 1112 | Line 1165 | public class ArrayDeque<E> extends Abstr
1165		// Write out elements in order.
1166		final Object[] elements = this.elements;
1167		final int capacity = elements.length;
1168	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
1169	<	s.writeObject(elements[i]);
1168	>	int i, end, to, todo;
1169	>	todo = (end = (i = head) + size)
1170	>	- (to = (capacity - end >= 0) ? end : capacity);
1171	>	for (;; to = todo, i = 0, todo = 0) {
1172	>	for (; i < to; i++)
1173	>	s.writeObject(elements[i]);
1174	>	if (todo == 0) break;
1175	>	}
1176		}
1177
1178		/**
#	Line 1136 | Line 1195 | public class ArrayDeque<E> extends Abstr
1195		}
1196
1197		/** debugging */
1198	<	private void checkInvariants() {
1198	>	void checkInvariants() {
1199		try {
1200		int capacity = elements.length;
1201	<	assert size >= 0 && size <= capacity;
1202	<	assert head >= 0 && ((capacity == 0 && head == 0 && size == 0)
1203	<	|| head < capacity);
1204	<	assert size == 0
1205	<	|| (elements[head] != null && elements[tail()] != null);
1206	<	assert size == capacity
1207	<	|| (elements[dec(head, capacity)] == null
1149	<	&& elements[inc(tail(), capacity)] == null);
1201	>	// assert size >= 0 && size <= capacity;
1202	>	// assert head >= 0;
1203	>	// assert capacity == 0 || head < capacity;
1204	>	// assert size == 0 || elements[head] != null;
1205	>	// assert size == 0 || elements[tail()] != null;
1206	>	// assert size == capacity || elements[dec(head, capacity)] == null;
1207	>	// assert size == capacity || elements[inc(tail(), capacity)] == null;
1208		} catch (Throwable t) {
1209		System.err.printf("head=%d size=%d capacity=%d%n",
1210		head, size, elements.length);

Diff Legend

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