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.81 by jsr166, Sat Oct 22 18:16:56 2016 UTC vs.
Revision 1.89 by jsr166, Mon Oct 24 23:40:56 2016 UTC

#	Line 187 | Line 187 | public class ArrayDeque<E> extends Abstr
187		Object[] elements = c.toArray();
188		// defend against c.toArray (incorrectly) not returning Object[]
189		// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
190	+	size = elements.length;
191		if (elements.getClass() != Object[].class)
192		elements = Arrays.copyOf(elements, size, Object[].class);
193		for (Object obj : elements)
194		Objects.requireNonNull(obj);
194	–	size = elements.length;
195		this.elements = elements;
196		}
197
#	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 234 | Line 234 | public class ArrayDeque<E> extends Abstr
234		* Returns element at array index i.
235		*/
236		@SuppressWarnings("unchecked")
237	<	final E elementAt(int i) {
237	>	private E elementAt(int i) {
238		return (E) elements[i];
239		}
240
#	Line 264 | Line 264 | public class ArrayDeque<E> extends Abstr
264		// checkInvariants();
265		Objects.requireNonNull(e);
266		Object[] elements;
267	<	int capacity, s = size;
268	<	while (s == (capacity = (elements = this.elements).length))
267	>	int capacity, h;
268	>	final int s;
269	>	if ((s = size) == (capacity = (elements = this.elements).length)) {
270		grow(1);
271	<	elements[head = dec(head, capacity)] = e;
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
279		/**
#	Line 283 | Line 288 | public class ArrayDeque<E> extends Abstr
288		// checkInvariants();
289		Objects.requireNonNull(e);
290		Object[] elements;
291	<	int capacity, s = size;
292	<	while (s == (capacity = (elements = this.elements).length))
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
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 newcomers, capacity, s = size;
309	<	if ((newcomers = (a = c.toArray()).length) == 0)
310	<	return false;
311	<	while ((capacity = (elements = this.elements).length) - s < newcomers)
312	<	grow(newcomers - (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;
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 433 | 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) {
436	–	// 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 463 | 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 616 | 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 696 | 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 716 | 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 732 | 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 808 | Line 817 | public class ArrayDeque<E> extends Abstr
817		}
818
819		public void forEachRemaining(Consumer<? super E> action) {
820	<	Objects.requireNonNull(action);
812	<	final Object[] elements = ArrayDeque.this.elements;
813	<	final int capacity = elements.length;
814	<	int k = remaining();
820	>	int k = remaining(); // side effect!
821		remaining = 0;
822	<	for (int i = cursor; --k >= 0; i = inc(i, capacity))
817	<	action.accept(checkedElementAt(elements, i));
822	>	ArrayDeque.forEachRemaining(action, elements, cursor, k);
823		}
824
825		public boolean tryAdvance(Consumer<? super E> action) {
#	Line 822 | 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 839 | Line 844 | public class ArrayDeque<E> extends Abstr
844		}
845		}
846
847	<	@Override
847	>	@SuppressWarnings("unchecked")
848		public void forEach(Consumer<? super E> action) {
844	–	// 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 861 | 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
924		/**
925		* @throws NullPointerException {@inheritDoc}
926		*/
872	–	@Override
927		public boolean removeIf(Predicate<? super E> filter) {
928		Objects.requireNonNull(filter);
929		return bulkRemove(filter);
#	Line 878 | Line 932 | public class ArrayDeque<E> extends Abstr
932		/**
933		* @throws NullPointerException {@inheritDoc}
934		*/
881	–	@Override
935		public boolean removeAll(Collection<?> c) {
936		Objects.requireNonNull(c);
937		return bulkRemove(e -> c.contains(e));
#	Line 887 | Line 940 | public class ArrayDeque<E> extends Abstr
940		/**
941		* @throws NullPointerException {@inheritDoc}
942		*/
890	–	@Override
943		public boolean retainAll(Collection<?> c) {
944		Objects.requireNonNull(c);
945		return bulkRemove(e -> !c.contains(e));
#	Line 900 | 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;
917	<	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))
923	<	elements[j] = null;
977	>	clearSlice(elements, j, deleted);
978		// checkInvariants();
979		}
980		}
#	Line 937 | 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 966 | 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;
970	<	final int capacity = elements.length;
971	<	final int h = this.head;
972	<	final int s = size;
973	<	if (capacity - h >= s)
974	<	Arrays.fill(elements, h, h + s, null);
975	<	else {
976	<	Arrays.fill(elements, h, capacity, null);
977	<	Arrays.fill(elements, 0, s - capacity + h, 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 994 | Line 1056 | public class ArrayDeque<E> extends Abstr
1056		* @return an array containing all of the elements in this deque
1057		*/
1058		public Object[] toArray() {
1059	<	final int head = this.head;
1060	<	final int firstLeg;
1061	<	Object[] a = Arrays.copyOfRange(elements, head, head + size);
1062	<	if ((firstLeg = elements.length - head) < size)
1063	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1059	>	return toArray(Object[].class);
1060	>	}
1061	>
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, end = head + size;
1066	>	final T[] a;
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 (end - capacity > 0)
1075	>	System.arraycopy(elements, 0, a, capacity - head, end - capacity);
1076		return a;
1077		}
1078
#	Line 1040 | Line 1114 | public class ArrayDeque<E> extends Abstr
1114		*/
1115		@SuppressWarnings("unchecked")
1116		public <T> T[] toArray(T[] a) {
1117	+	final int size = this.size;
1118	+	if (size > a.length)
1119	+	return toArray((Class<T[]>) a.getClass());
1120		final Object[] elements = this.elements;
1121	<	final int head = this.head;
1122	<	final int firstLeg;
1123	<	boolean wrap = (firstLeg = elements.length - head) < size;
1124	<	if (size > a.length) {
1125	<	a = (T[]) Arrays.copyOfRange(elements, head, head + size,
1126	<	a.getClass());
1127	<	} else {
1128	<	System.arraycopy(elements, head, a, 0, wrap ? firstLeg : size);
1052	<	if (size < a.length)
1053	<	a[size] = null;
1054	<	}
1055	<	if (wrap)
1056	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1121	>	final int capacity = elements.length;
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;
1130		}
1131
#	Line 1096 | 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 1120 | 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
1133	<	&& 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