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.88 by jsr166, Mon Oct 24 16:01:25 2016 UTC vs.
Revision 1.89 by jsr166, Mon Oct 24 23:40:56 2016 UTC

#	Line 200 | Line 200 | public class ArrayDeque<E> extends Abstr
200		* Precondition and postcondition: 0 <= i < modulus.
201		*/
202		static final int inc(int i, int modulus) {
203	<	if (++i == modulus) i = 0;
203	>	if (++i >= modulus) i = 0;
204		return i;
205		}
206
#	Line 209 | Line 209 | public class ArrayDeque<E> extends Abstr
209		* Precondition and postcondition: 0 <= i < modulus.
210		*/
211		static final int dec(int i, int modulus) {
212	<	if (--i < 0) i += modulus;
212	>	if (--i < 0) i = modulus - 1;
213		return i;
214		}
215
#	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[] elements;
267	>	int capacity, h;
268	>	final int s;
269	>	if ((s = size) == (capacity = (elements = this.elements).length)) {
270	>	grow(1);
271	>	capacity = (elements = this.elements).length;
272	>	}
273	>	if ((h = head - 1) < 0) h = capacity - 1;
274	>	elements[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[] elements;
291	>	int capacity;
292	>	final int s;
293	>	if ((s = size) == (capacity = (elements = this.elements).length)) {
294	>	grow(1);
295	>	capacity = (elements = this.elements).length;
296	>	}
297	>	elements[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 374 | Line 367 | public class ArrayDeque<E> extends Abstr
367
368		public E pollFirst() {
369		// checkInvariants();
370	<	final int s, h;
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 439 | Line 433 | public class ArrayDeque<E> extends Abstr
433		* @return {@code true} if the deque contained the specified element
434		*/
435		public boolean removeFirstOccurrence(Object o) {
442	–	// checkInvariants();
436		if (o != null) {
437		final Object[] elements = this.elements;
438		final int capacity = elements.length;
439	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity)) {
440	<	if (o.equals(elements[i])) {
441	<	delete(i);
442	<	return true;
443	<	}
439	>	int from, end, to, leftover;
440	>	leftover = (end = (from = head) + size)
441	>	- (to = (capacity - end >= 0) ? end : capacity);
442	>	for (;; from = 0, to = leftover, leftover = 0) {
443	>	for (int i = from; i < to; i++)
444	>	if (o.equals(elements[i])) {
445	>	delete(i);
446	>	return true;
447	>	}
448	>	if (leftover == 0) break;
449		}
450		}
451		return false;
#	Line 469 | Line 467 | public class ArrayDeque<E> extends Abstr
467		if (o != null) {
468		final Object[] elements = this.elements;
469		final int capacity = elements.length;
470	<	for (int k = size, i = add(head, k - 1, capacity);
471	<	--k >= 0; i = dec(i, capacity)) {
472	<	if (o.equals(elements[i])) {
473	<	delete(i);
474	<	return true;
475	<	}
470	>	int from, to, end, leftover;
471	>	leftover = (to = ((end = (from = tail()) - size) >= -1) ? end : -1) - end;
472	>	for (;; from = capacity - 1, to = capacity - 1 - leftover, leftover = 0) {
473	>	for (int i = from; i > to; i--)
474	>	if (o.equals(elements[i])) {
475	>	delete(i);
476	>	return true;
477	>	}
478	>	if (leftover == 0) break;
479		}
480		}
481		return false;
#	Line 622 | Line 623 | public class ArrayDeque<E> extends Abstr
623		System.arraycopy(elements, h, elements, h + 1, front - (i + 1));
624		}
625		elements[h] = null;
626	<	head = inc(h, capacity);
626	>	if ((head = (h + 1)) >= capacity) head = 0;
627		size--;
628		// checkInvariants();
629		return false;
#	Line 702 | Line 703 | public class ArrayDeque<E> extends Abstr
703		public E next() {
704		if (remaining == 0)
705		throw new NoSuchElementException();
706	+	final Object[] elements = ArrayDeque.this.elements;
707		E e = checkedElementAt(elements, cursor);
708		lastRet = cursor;
709	<	cursor = inc(cursor, elements.length);
709	>	if (++cursor >= elements.length) cursor = 0;
710		remaining--;
711		return e;
712		}
713
714		void postDelete(boolean leftShifted) {
715		if (leftShifted)
716	<	cursor = dec(cursor, elements.length); // undo inc in next
716	>	if (--cursor < 0) cursor = elements.length - 1;
717		}
718
719		public final void remove() {
#	Line 722 | Line 724 | public class ArrayDeque<E> extends Abstr
724		}
725
726		public void forEachRemaining(Consumer<? super E> action) {
727	<	Objects.requireNonNull(action);
728	<	final Object[] elements = ArrayDeque.this.elements;
729	<	final int capacity = elements.length;
730	<	int k = remaining;
731	<	remaining = 0;
732	<	for (int i = cursor; --k >= 0; i = inc(i, capacity))
733	<	action.accept(checkedElementAt(elements, i));
727	>	int k;
728	>	if ((k = remaining) > 0) {
729	>	remaining = 0;
730	>	ArrayDeque.forEachRemaining(action, elements, cursor, k);
731	>	if ((lastRet = cursor + k - 1) >= elements.length)
732	>	lastRet -= elements.length;
733	>	}
734		}
735		}
736
#	Line 738 | Line 740 | public class ArrayDeque<E> extends Abstr
740		public final E next() {
741		if (remaining == 0)
742		throw new NoSuchElementException();
743	+	final Object[] elements = ArrayDeque.this.elements;
744		E e = checkedElementAt(elements, cursor);
745		lastRet = cursor;
746	<	cursor = dec(cursor, elements.length);
746	>	if (--cursor < 0) cursor = elements.length - 1;
747		remaining--;
748		return e;
749		}
750
751		void postDelete(boolean leftShifted) {
752		if (!leftShifted)
753	<	cursor = inc(cursor, elements.length); // undo dec in next
753	>	if (++cursor >= elements.length) cursor = 0;
754		}
755
756		public final void forEachRemaining(Consumer<? super E> action) {
757	<	Objects.requireNonNull(action);
758	<	final Object[] elements = ArrayDeque.this.elements;
759	<	final int capacity = elements.length;
760	<	int k = remaining;
761	<	remaining = 0;
762	<	for (int i = cursor; --k >= 0; i = dec(i, capacity))
763	<	action.accept(checkedElementAt(elements, i));
757	>	int k;
758	>	if ((k = remaining) > 0) {
759	>	remaining = 0;
760	>	forEachRemainingDescending(action, elements, cursor, k);
761	>	if ((lastRet = cursor - (k - 1)) < 0)
762	>	lastRet += elements.length;
763	>	}
764		}
765		}
766
#	Line 814 | Line 817 | public class ArrayDeque<E> extends Abstr
817		}
818
819		public void forEachRemaining(Consumer<? super E> action) {
820	<	Objects.requireNonNull(action);
818	<	final Object[] elements = ArrayDeque.this.elements;
819	<	final int capacity = elements.length;
820	<	int k = remaining();
820	>	int k = remaining(); // side effect!
821		remaining = 0;
822	<	for (int i = cursor; --k >= 0; i = inc(i, capacity))
823	<	action.accept(checkedElementAt(elements, i));
822	>	ArrayDeque.forEachRemaining(action, elements, cursor, k);
823		}
824
825		public boolean tryAdvance(Consumer<? super E> action) {
#	Line 828 | Line 827 | public class ArrayDeque<E> extends Abstr
827		if (remaining() == 0)
828		return false;
829		action.accept(checkedElementAt(elements, cursor));
830	<	cursor = inc(cursor, elements.length);
830	>	if (++cursor >= elements.length) cursor = 0;
831		remaining--;
832		return true;
833		}
#	Line 845 | Line 844 | public class ArrayDeque<E> extends Abstr
844		}
845		}
846
847	+	@SuppressWarnings("unchecked")
848		public void forEach(Consumer<? super E> action) {
849	–	// checkInvariants();
849		Objects.requireNonNull(action);
850		final Object[] elements = this.elements;
851		final int capacity = elements.length;
852	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
853	<	action.accept(elementAt(i));
852	>	int from, end, to, leftover;
853	>	leftover = (end = (from = head) + size)
854	>	- (to = (capacity - end >= 0) ? end : capacity);
855	>	for (;; from = 0, to = leftover, leftover = 0) {
856	>	for (int i = from; i < to; i++)
857	>	action.accept((E) elements[i]);
858	>	if (leftover == 0) break;
859	>	}
860		// checkInvariants();
861		}
862
863		/**
864	+	* A variant of forEach that also checks for concurrent
865	+	* modification, for use in iterators.
866	+	*/
867	+	static <E> void forEachRemaining(
868	+	Consumer<? super E> action, Object[] elements, int from, int size) {
869	+	Objects.requireNonNull(action);
870	+	final int capacity = elements.length;
871	+	int end, to, leftover;
872	+	leftover = (end = from + size)
873	+	- (to = (capacity - end >= 0) ? end : capacity);
874	+	for (;; from = 0, to = leftover, leftover = 0) {
875	+	for (int i = from; i < to; i++) {
876	+	@SuppressWarnings("unchecked") E e = (E) elements[i];
877	+	if (e == null)
878	+	throw new ConcurrentModificationException();
879	+	action.accept(e);
880	+	}
881	+	if (leftover == 0) break;
882	+	}
883	+	}
884	+
885	+	static <E> void forEachRemainingDescending(
886	+	Consumer<? super E> action, Object[] elements, int from, int size) {
887	+	Objects.requireNonNull(action);
888	+	final int capacity = elements.length;
889	+	int end, to, leftover;
890	+	leftover = (to = ((end = from - size) >= -1) ? end : -1) - end;
891	+	for (;; from = capacity - 1, to = capacity - 1 - leftover, leftover = 0) {
892	+	for (int i = from; i > to; i--) {
893	+	@SuppressWarnings("unchecked") E e = (E) elements[i];
894	+	if (e == null)
895	+	throw new ConcurrentModificationException();
896	+	action.accept(e);
897	+	}
898	+	if (leftover == 0) break;
899	+	}
900	+	}
901	+
902	+	/**
903		* Replaces each element of this deque with the result of applying the
904		* operator to that element, as specified by {@link List#replaceAll}.
905		*
#	Line 866 | Line 910 | public class ArrayDeque<E> extends Abstr
910		Objects.requireNonNull(operator);
911		final Object[] elements = this.elements;
912		final int capacity = elements.length;
913	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
914	<	elements[i] = operator.apply(elementAt(i));
913	>	int from, end, to, leftover;
914	>	leftover = (end = (from = head) + size)
915	>	- (to = (capacity - end >= 0) ? end : capacity);
916	>	for (;; from = 0, to = leftover, leftover = 0) {
917	>	for (int i = from; i < to; i++)
918	>	elements[i] = operator.apply(elementAt(i));
919	>	if (leftover == 0) break;
920	>	}
921		// checkInvariants();
922		}
923
#	Line 902 | Line 952 | public class ArrayDeque<E> extends Abstr
952		final int capacity = elements.length;
953		int i = head, j = i, remaining = size, deleted = 0;
954		try {
955	<	for (; remaining > 0; remaining--, i = inc(i, capacity)) {
955	>	for (; remaining > 0; remaining--) {
956		@SuppressWarnings("unchecked") E e = (E) elements[i];
957		if (filter.test(e))
958		deleted++;
959		else {
960		if (j != i)
961		elements[j] = e;
962	<	j = inc(j, capacity);
962	>	if (++j >= capacity) j = 0;
963		}
964	+	if (++i >= capacity) i = 0;
965		}
966		return deleted > 0;
967		} catch (Throwable ex) {
968		if (deleted > 0)
969	<	for (; remaining > 0;
919	<	remaining--, i = inc(i, capacity), j = inc(j, capacity))
969	>	for (; remaining > 0; remaining--) {
970		elements[j] = elements[i];
971	+	if (++i >= capacity) i = 0;
972	+	if (++j >= capacity) j = 0;
973	+	}
974		throw ex;
975		} finally {
976		size -= deleted;
977	<	for (; --deleted >= 0; j = inc(j, capacity))
925	<	elements[j] = null;
977	>	clearSlice(elements, j, deleted);
978		// checkInvariants();
979		}
980		}
#	Line 939 | Line 991 | public class ArrayDeque<E> extends Abstr
991		if (o != null) {
992		final Object[] elements = this.elements;
993		final int capacity = elements.length;
994	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
995	<	if (o.equals(elements[i]))
996	<	return true;
994	>	int from, end, to, leftover;
995	>	leftover = (end = (from = head) + size)
996	>	- (to = (capacity - end >= 0) ? end : capacity);
997	>	for (;; from = 0, to = leftover, leftover = 0) {
998	>	for (int i = from; i < to; i++)
999	>	if (o.equals(elements[i]))
1000	>	return true;
1001	>	if (leftover == 0) break;
1002	>	}
1003		}
1004		return false;
1005		}
#	Line 968 | Line 1026 | public class ArrayDeque<E> extends Abstr
1026		* The deque will be empty after this call returns.
1027		*/
1028		public void clear() {
1029	<	final Object[] elements = this.elements;
972	<	final int capacity = elements.length, tail = head + size;
973	<	if (capacity - tail >= 0)
974	<	Arrays.fill(elements, head, tail, null);
975	<	else {
976	<	Arrays.fill(elements, head, capacity, null);
977	<	Arrays.fill(elements, 0, tail - capacity, null);
978	<	}
1029	>	clearSlice(elements, head, size);
1030		size = head = 0;
1031		// checkInvariants();
1032		}
1033
1034		/**
1035	+	* Nulls out size elements, starting at head.
1036	+	*/
1037	+	private static void clearSlice(Object[] elements, int head, int size) {
1038	+	final int capacity = elements.length, end = head + size;
1039	+	final int leg = (capacity - end >= 0) ? end : capacity;
1040	+	Arrays.fill(elements, head, leg, null);
1041	+	if (leg != end)
1042	+	Arrays.fill(elements, 0, end - capacity, null);
1043	+	}
1044	+
1045	+	/**
1046		* Returns an array containing all of the elements in this deque
1047		* in proper sequence (from first to last element).
1048		*
#	Line 1000 | Line 1062 | public class ArrayDeque<E> extends Abstr
1062		private <T> T[] toArray(Class<T[]> klazz) {
1063		final Object[] elements = this.elements;
1064		final int capacity = elements.length;
1065	<	final int head = this.head, tail = head + size;
1065	>	final int head = this.head, end = head + size;
1066		final T[] a;
1067	<	if (tail >= 0) {
1068	<	a = Arrays.copyOfRange(elements, head, tail, klazz);
1067	>	if (end >= 0) {
1068	>	a = Arrays.copyOfRange(elements, head, end, klazz);
1069		} else {
1070		// integer overflow!
1071		a = Arrays.copyOfRange(elements, 0, size, klazz);
1072		System.arraycopy(elements, head, a, 0, capacity - head);
1073		}
1074	<	if (tail - capacity > 0)
1075	<	System.arraycopy(elements, 0, a, capacity - head, tail - capacity);
1074	>	if (end - capacity > 0)
1075	>	System.arraycopy(elements, 0, a, capacity - head, end - capacity);
1076		return a;
1077		}
1078
#	Line 1057 | Line 1119 | public class ArrayDeque<E> extends Abstr
1119		return toArray((Class<T[]>) a.getClass());
1120		final Object[] elements = this.elements;
1121		final int capacity = elements.length;
1122	<	final int head = this.head, tail = head + size;
1123	<	if (capacity - tail >= 0)
1124	<	System.arraycopy(elements, head, a, 0, size);
1125	<	else {
1126	<	System.arraycopy(elements, head, a, 0, capacity - head);
1065	<	System.arraycopy(elements, 0, a, capacity - head, tail - capacity);
1066	<	}
1122	>	final int head = this.head, end = head + size;
1123	>	final int front = (capacity - end >= 0) ? size : capacity - head;
1124	>	System.arraycopy(elements, head, a, 0, front);
1125	>	if (front != size)
1126	>	System.arraycopy(elements, 0, a, capacity - head, end - capacity);
1127		if (size < a.length)
1128		a[size] = null;
1129		return a;
#	Line 1108 | Line 1168 | public class ArrayDeque<E> extends Abstr
1168		// Write out elements in order.
1169		final Object[] elements = this.elements;
1170		final int capacity = elements.length;
1171	<	for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
1172	<	s.writeObject(elements[i]);
1171	>	int from, end, to, leftover;
1172	>	leftover = (end = (from = head) + size)
1173	>	- (to = (capacity - end >= 0) ? end : capacity);
1174	>	for (;; from = 0, to = leftover, leftover = 0) {
1175	>	for (int i = from; i < to; i++)
1176	>	s.writeObject(elements[i]);
1177	>	if (leftover == 0) break;
1178	>	}
1179		}
1180
1181		/**
#	Line 1132 | Line 1198 | public class ArrayDeque<E> extends Abstr
1198		}
1199
1200		/** debugging */
1201	<	private void checkInvariants() {
1201	>	void checkInvariants() {
1202		try {
1203		int capacity = elements.length;
1204	<	assert size >= 0 && size <= capacity;
1205	<	assert head >= 0 && ((capacity == 0 && head == 0 && size == 0)
1206	<	|| head < capacity);
1207	<	assert size == 0
1208	<	|| (elements[head] != null && elements[tail()] != null);
1209	<	assert size == capacity
1210	<	|| (elements[dec(head, capacity)] == null
1145	<	&& elements[inc(tail(), capacity)] == null);
1204	>	// assert size >= 0 && size <= capacity;
1205	>	// assert head >= 0;
1206	>	// assert capacity == 0 || head < capacity;
1207	>	// assert size == 0 || elements[head] != null;
1208	>	// assert size == 0 || elements[tail()] != null;
1209	>	// assert size == capacity || elements[dec(head, capacity)] == null;
1210	>	// assert size == capacity || elements[inc(tail(), capacity)] == null;
1211		} catch (Throwable t) {
1212		System.err.printf("head=%d size=%d capacity=%d%n",
1213		head, size, elements.length);

Diff Legend

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