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.76 by jsr166, Mon Oct 17 23:49:00 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 134 | Line 133 | public class ArrayDeque<E> extends Abstr
133		* to ensure that it can hold at least the given number of elements.
134		*
135		* @param minCapacity the desired minimum capacity
136	<	* @since 9
136	>	* @since TBD
137		*/
138	<	public void ensureCapacity(int minCapacity) {
138	>	/* public */ void ensureCapacity(int minCapacity) {
139		if (minCapacity > elements.length)
140		grow(minCapacity - elements.length);
141		// checkInvariants();
#	Line 145 | Line 144 | public class ArrayDeque<E> extends Abstr
144		/**
145		* Minimizes the internal storage of this collection.
146		*
147	<	* @since 9
147	>	* @since TBD
148		*/
149	<	public void trimToSize() {
149	>	/* public */ void trimToSize() {
150		if (size < elements.length) {
151		elements = toArray();
152		head = 0;
#	Line 184 | Line 183 | public class ArrayDeque<E> extends Abstr
183		* @throws NullPointerException if the specified collection is null
184		*/
185		public ArrayDeque(Collection<? extends E> c) {
186	<	Object[] elements = c.toArray();
186	>	Object[] es = c.toArray();
187		// defend against c.toArray (incorrectly) not returning Object[]
188		// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
189	<	if (elements.getClass() != Object[].class)
190	<	elements = Arrays.copyOf(elements, size, Object[].class);
191	<	for (Object obj : elements)
189	>	if (es.getClass() != Object[].class)
190	>	es = Arrays.copyOf(es, es.length, Object[].class);
191	>	for (Object obj : es)
192		Objects.requireNonNull(obj);
193	<	size = elements.length;
194	<	this.elements = elements;
193	>	this.elements = es;
194	>	this.size = es.length;
195		}
196
197		/**
198	<	* Returns the array index of the last element.
199	<	* May return invalid index -1 if there are no elements.
198	>	* Increments i, mod modulus.
199	>	* Precondition and postcondition: 0 <= i < modulus.
200		*/
201	<	final int tail() {
202	<	return add(head, size - 1, elements.length);
201	>	static final int inc(int i, int modulus) {
202	>	if (++i >= modulus) i = 0;
203	>	return i;
204		}
205
206		/**
207	<	* Adds i and j, mod modulus.
208	<	* Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
207	>	* Decrements i, mod modulus.
208	>	* Precondition and postcondition: 0 <= i < modulus.
209		*/
210	<	static final int add(int i, int j, int modulus) {
211	<	if ((i += j) - modulus >= 0) i -= modulus;
210	>	static final int dec(int i, int modulus) {
211	>	if (--i < 0) i = modulus - 1;
212		return i;
213		}
214
215		/**
216	<	* Increments i, mod modulus.
217	<	* Precondition and postcondition: 0 <= i < modulus.
216	>	* Adds i and j, mod modulus.
217	>	* Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
218		*/
219	<	static final int inc(int i, int modulus) {
220	<	if (++i == modulus) i = 0;
219	>	static final int add(int i, int j, int modulus) {
220	>	if ((i += j) - modulus >= 0) i -= modulus;
221		return i;
222		}
223
224		/**
225	<	* Decrements i, mod modulus.
226	<	* Precondition and postcondition: 0 <= i < modulus.
225	>	* Returns the array index of the last element.
226	>	* May return invalid index -1 if there are no elements.
227		*/
228	<	static final int dec(int i, int modulus) {
229	<	if (--i < 0) i += modulus;
230	<	return i;
228	>	final int tail() {
229	>	return add(head, size - 1, elements.length);
230		}
231
232		/**
233		* Returns element at array index i.
234		*/
235		@SuppressWarnings("unchecked")
236	<	final E elementAt(int i) {
236	>	private E elementAt(int i) {
237		return (E) elements[i];
238		}
239
240		/**
241		* A version of elementAt that checks for null elements.
242		* This check doesn't catch all possible comodifications,
243	<	* but does catch ones that corrupt traversal.
243	>	* but does catch ones that corrupt traversal.  It's a little
244	>	* surprising that javac allows this abuse of generics.
245		*/
246	<	E checkedElementAt(Object[] elements, int i) {
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	<	Object[] elements;
267	<	int capacity, s = size;
268	<	while (s == (capacity = (elements = this.elements).length))
266	>	Object[] es;
267	>	int capacity, h;
268	>	final int s;
269	>	if ((s = size) == (capacity = (es = elements).length)) {
270		grow(1);
271	<	elements[head = dec(head, capacity)] = e;
271	>	capacity = (es = elements).length;
272	>	}
273	>	if ((h = head - 1) < 0) h = capacity - 1;
274	>	es[head = h] = e;
275		size = s + 1;
276	+	// checkInvariants();
277		}
278
279		/**
#	Line 282 | Line 287 | public class ArrayDeque<E> extends Abstr
287		public void addLast(E e) {
288		// checkInvariants();
289		Objects.requireNonNull(e);
290	<	Object[] elements;
291	<	int capacity, s = size;
292	<	while (s == (capacity = (elements = this.elements).length))
290	>	Object[] es;
291	>	int capacity;
292	>	final int s;
293	>	if ((s = size) == (capacity = (es = elements).length)) {
294		grow(1);
295	<	elements[add(head, s, capacity)] = e;
295	>	capacity = (es = elements).length;
296	>	}
297	>	es[add(head, s, capacity)] = e;
298		size = s + 1;
299	+	// checkInvariants();
300		}
301
302		/**
#	Line 301 | Line 310 | public class ArrayDeque<E> extends Abstr
310		* @throws NullPointerException if the specified collection or any
311		*         of its elements are null
312		*/
304	–	@Override
313		public boolean addAll(Collection<? extends E> c) {
314	+	final int s = size, needed = c.size() - (elements.length - s);
315	+	if (needed > 0)
316	+	grow(needed);
317	+	c.forEach((e) -> addLast(e));
318		// checkInvariants();
319	<	Object[] a, elements;
308	<	int len, capacity, s = size;
309	<	if ((len = (a = c.toArray()).length) == 0)
310	<	return false;
311	<	while ((capacity = (elements = this.elements).length) - s < len)
312	<	grow(len - (capacity - s));
313	<	int i = add(head, s, capacity);
314	<	for (Object x : a) {
315	<	Objects.requireNonNull(x);
316	<	elements[i] = x;
317	<	i = inc(i, capacity);
318	<	size++;
319	<	}
320	<	return true;
319	>	return size > s;
320		}
321
322		/**
#	Line 349 | Line 348 | public class ArrayDeque<E> extends Abstr
348		*/
349		public E removeFirst() {
350		// checkInvariants();
351	<	E x = pollFirst();
352	<	if (x == null)
351	>	E e = pollFirst();
352	>	if (e == null)
353		throw new NoSuchElementException();
354	<	return x;
354	>	return e;
355		}
356
357		/**
#	Line 360 | Line 359 | public class ArrayDeque<E> extends Abstr
359		*/
360		public E removeLast() {
361		// checkInvariants();
362	<	E x = pollLast();
363	<	if (x == null)
362	>	E e = pollLast();
363	>	if (e == null)
364		throw new NoSuchElementException();
365	<	return x;
365	>	return e;
366		}
367
368		public E pollFirst() {
369		// checkInvariants();
370	<	final int s, h;
371	<	if ((s = size) == 0)
370	>	int s, h;
371	>	if ((s = size) <= 0)
372		return null;
373		final Object[] elements = this.elements;
374		@SuppressWarnings("unchecked") E e = (E) elements[h = head];
375		elements[h] = null;
376	<	head = inc(h, elements.length);
376	>	if (++h >= elements.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;
388		@SuppressWarnings("unchecked")
#	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[] 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 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	<	}
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 463 | 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 616 | 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 689 | Line 703 | public class ArrayDeque<E> extends Abstr
703
704		DeqIterator() { cursor = head; }
705
692	–	void doAdvance() {
693	–	cursor = inc(cursor, elements.length);
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	–
706		public final boolean hasNext() {
707		return remaining > 0;
708		}
709
710	<	public final E next() {
711	<	if (remaining == 0)
710	>	public E next() {
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	<	doAdvance();
716	>	if (++cursor >= elements.length) cursor = 0;
717		remaining--;
718		return e;
719		}
720
721	+	void postDelete(boolean leftShifted) {
722	+	if (leftShifted)
723	+	if (--cursor < 0) cursor = elements.length - 1;
724	+	}
725	+
726		public final void remove() {
727		if (lastRet < 0)
728		throw new IllegalStateException();
729	<	doRemove();
729	>	postDelete(delete(lastRet));
730		lastRet = -1;
731		}
732
733	<	public final void forEachRemaining(Consumer<? super E> action) {
734	<	Objects.requireNonNull(action);
735	<	final Object[] elements = ArrayDeque.this.elements;
736	<	final int capacity = elements.length;
737	<	for (; remaining > 0; remaining--) {
738	<	action.accept(checkedElementAt(elements, cursor));
739	<	doAdvance();
733	>	public void forEachRemaining(Consumer<? super E> action) {
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		}
#	Line 734 | Line 744 | public class ArrayDeque<E> extends Abstr
744		private class DescendingIterator extends DeqIterator {
745		DescendingIterator() { cursor = tail(); }
746
747	<	@Override void doAdvance() {
748	<	cursor = dec(cursor, elements.length);
747	>	public final E next() {
748	>	if (remaining <= 0)
749	>	throw new NoSuchElementException();
750	>	final Object[] elements = ArrayDeque.this.elements;
751	>	E e = nonNullElementAt(elements, cursor);
752	>	lastRet = cursor;
753	>	if (--cursor < 0) cursor = elements.length - 1;
754	>	remaining--;
755	>	return e;
756	>	}
757	>
758	>	void postDelete(boolean leftShifted) {
759	>	if (!leftShifted)
760	>	if (++cursor >= elements.length) cursor = 0;
761		}
762
763	<	@Override void doRemove() {
764	<	if (!delete(lastRet))
765	<	// if right-shifted, undo advance in next
766	<	cursor = inc(cursor, elements.length);
763	>	public final void forEachRemaining(Consumer<? super E> action) {
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 787 | Line 813 | public class ArrayDeque<E> extends Abstr
813		}
814
815		public ArrayDequeSpliterator trySplit() {
816	<	if (remaining() > 1) {
817	<	int mid = remaining >> 1;
816	>	final int mid;
817	>	if ((mid = remaining() >> 1) > 0) {
818		int oldCursor = cursor;
819		cursor = add(cursor, mid, elements.length);
820		remaining -= mid;
#	Line 798 | 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;
804	<	remaining();        // for the initialization side-effect
805	<	for (; remaining > 0; cursor = inc(cursor, capacity), remaining--)
806	<	action.accept(checkedElementAt(elements, cursor));
827	>	final int k = remaining(); // side effect!
828	>	remaining = 0;
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 828 | Line 852 | public class ArrayDeque<E> extends Abstr
852		}
853		}
854
855	<	@Override
855	>	@SuppressWarnings("unchecked")
856		public void forEach(Consumer<? super E> action) {
833	–	// 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		*
907		* @param operator the operator to apply to each element
908	<	* @since 9
908	>	* @since TBD
909		*/
910	<	public void replaceAll(UnaryOperator<E> operator) {
910	>	/* public */ void replaceAll(UnaryOperator<E> operator) {
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		*/
861	–	@Override
928		public boolean removeIf(Predicate<? super E> filter) {
929		Objects.requireNonNull(filter);
930		return bulkRemove(filter);
#	Line 867 | Line 933 | public class ArrayDeque<E> extends Abstr
933		/**
934		* @throws NullPointerException {@inheritDoc}
935		*/
870	–	@Override
936		public boolean removeAll(Collection<?> c) {
937		Objects.requireNonNull(c);
938		return bulkRemove(e -> c.contains(e));
#	Line 876 | Line 941 | public class ArrayDeque<E> extends Abstr
941		/**
942		* @throws NullPointerException {@inheritDoc}
943		*/
879	–	@Override
944		public boolean retainAll(Collection<?> c) {
945		Objects.requireNonNull(c);
946		return bulkRemove(e -> !c.contains(e));
#	Line 889 | 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	<	for (; remaining > 0;
970	<	remaining--, i = inc(i, capacity), j = inc(j, capacity))
971	<	elements[j] = elements[i];
969	>	if (deleted > 0)
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))
911	<	elements[j] = null;
978	>	clearSlice(elements, j, deleted);
979		// checkInvariants();
980		}
981		}
#	Line 925 | 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 954 | 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;
958	<	final int capacity = elements.length;
959	<	final int h = this.head;
960	<	final int s = size;
961	<	if (capacity - h >= s)
962	<	Arrays.fill(elements, h, h + s, null);
963	<	else {
964	<	Arrays.fill(elements, h, capacity, null);
965	<	Arrays.fill(elements, 0, s - capacity + h, null);
966	<	}
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 982 | 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 1028 | 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);
1040	<	if (size < a.length)
1041	<	a[size] = null;
1042	<	}
1043	<	if (wrap)
1044	<	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 1084 | 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 1108 | 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
1121	<	&& 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