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.78 by jsr166, Tue Oct 18 17:31:18 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 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) {
247	<	@SuppressWarnings("unchecked") E e = (E) elements[i];
246	>	static final <E> E nonNullElementAt(Object[] es, int i) {
247	>	@SuppressWarnings("unchecked") E e = (E) es[i];
248		if (e == null)
249		throw new ConcurrentModificationException();
250		return e;
#	Line 263 | Line 263 | public class ArrayDeque<E> extends Abstr
263		public void addFirst(E e) {
264		// checkInvariants();
265		Objects.requireNonNull(e);
266	<	Object[] elements;
267	<	int capacity, s = size;
268	<	while (s == (capacity = (elements = this.elements).length))
266	>	Object[] es;
267	>	int capacity, h;
268	>	final int s;
269	>	if ((s = size) == (capacity = (es = elements).length)) {
270		grow(1);
271	<	elements[head = dec(head, capacity)] = e;
271	>	capacity = (es = elements).length;
272	>	}
273	>	if ((h = head - 1) < 0) h = capacity - 1;
274	>	es[head = h] = e;
275		size = s + 1;
276	+	// checkInvariants();
277		}
278
279		/**
#	Line 282 | Line 287 | public class ArrayDeque<E> extends Abstr
287		public void addLast(E e) {
288		// checkInvariants();
289		Objects.requireNonNull(e);
290	<	Object[] elements;
291	<	int capacity, s = size;
292	<	while (s == (capacity = (elements = this.elements).length))
290	>	Object[] es;
291	>	int capacity;
292	>	final int s;
293	>	if ((s = size) == (capacity = (es = elements).length)) {
294		grow(1);
295	<	elements[add(head, s, capacity)] = e;
295	>	capacity = (es = elements).length;
296	>	}
297	>	es[add(head, s, capacity)] = e;
298		size = s + 1;
299	+	// checkInvariants();
300		}
301
302		/**
#	Line 301 | Line 310 | public class ArrayDeque<E> extends Abstr
310		* @throws NullPointerException if the specified collection or any
311		*         of its elements are null
312		*/
304	–	@Override
313		public boolean addAll(Collection<? extends E> c) {
314	+	final int s = size, needed = c.size() - (elements.length - s);
315	+	if (needed > 0)
316	+	grow(needed);
317	+	c.forEach((e) -> addLast(e));
318		// checkInvariants();
319	<	Object[] a, elements;
308	<	int 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	–	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	–
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	<	cursor = advance(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	+	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) {
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 = advance(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
745		private class DescendingIterator extends DeqIterator {
746		DescendingIterator() { cursor = tail(); }
747
748	<	@Override int advance(int i, int modulus) {
749	<	return dec(i, modulus);
748	>	public final E next() {
749	>	if (remaining <= 0)
750	>	throw new NoSuchElementException();
751	>	final Object[] elements = ArrayDeque.this.elements;
752	>	E e = nonNullElementAt(elements, cursor);
753	>	lastRet = cursor;
754	>	if (--cursor < 0) cursor = elements.length - 1;
755	>	remaining--;
756	>	return e;
757	>	}
758	>
759	>	void postDelete(boolean leftShifted) {
760	>	if (!leftShifted)
761	>	if (++cursor >= elements.length) cursor = 0;
762		}
763
764	<	@Override void doRemove() {
765	<	if (!delete(lastRet))
766	<	// if right-shifted, undo advance in next
767	<	cursor = inc(cursor, elements.length);
764	>	public final void forEachRemaining(Consumer<? super E> action) {
765	>	Objects.requireNonNull(action);
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 799 | 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;
803	<	final int capacity = elements.length;
804	<	int k = remaining();
837	>	final int k = remaining(); // side effect!
838		remaining = 0;
839	<	for (int i = cursor; --k >= 0; i = inc(i, capacity))
807	<	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 829 | Line 862 | public class ArrayDeque<E> extends Abstr
862		}
863		}
864
865	<	@Override
865	>	@SuppressWarnings("unchecked")
866		public void forEach(Consumer<? super E> action) {
834	–	// 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		*
903		* @param operator the operator to apply to each element
904	<	* @since 9
904	>	* @since TBD
905		*/
906	<	public void replaceAll(UnaryOperator<E> operator) {
906	>	/* public */ void replaceAll(UnaryOperator<E> operator) {
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		*/
862	–	@Override
924		public boolean removeIf(Predicate<? super E> filter) {
925		Objects.requireNonNull(filter);
926		return bulkRemove(filter);
#	Line 868 | Line 929 | public class ArrayDeque<E> extends Abstr
929		/**
930		* @throws NullPointerException {@inheritDoc}
931		*/
871	–	@Override
932		public boolean removeAll(Collection<?> c) {
933		Objects.requireNonNull(c);
934		return bulkRemove(e -> c.contains(e));
#	Line 877 | Line 937 | public class ArrayDeque<E> extends Abstr
937		/**
938		* @throws NullPointerException {@inheritDoc}
939		*/
880	–	@Override
940		public boolean retainAll(Collection<?> c) {
941		Objects.requireNonNull(c);
942		return bulkRemove(e -> !c.contains(e));
#	Line 890 | 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;
907	<	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))
913	<	elements[j] = null;
974	>	clearSlice(elements, j, deleted);
975		// checkInvariants();
976		}
977		}
#	Line 927 | 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 956 | 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;
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	<	}
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 984 | 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 1030 | 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);
1042	<	if (size < a.length)
1043	<	a[size] = null;
1044	<	}
1045	<	if (wrap)
1046	<	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 1086 | 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 1110 | 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
1123	<	&& 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