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.92 by jsr166, Wed Oct 26 21:19:22 2016 UTC vs.
Revision 1.104 by jsr166, Mon Oct 31 21:15:35 2016 UTC

#	Line 183 | 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	<	size = elements.length;
190	<	if (elements.getClass() != Object[].class)
191	<	elements = Arrays.copyOf(elements, size, Object[].class);
192	<	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	<	this.elements = elements;
193	>	this.elements = es;
194	>	this.size = es.length;
195		}
196
197		/**
#	Line 243 | Line 243 | public class ArrayDeque<E> extends Abstr
243		* but does catch ones that corrupt traversal.  It's a little
244		* surprising that javac allows this abuse of generics.
245		*/
246	<	static final <E> E nonNullElementAt(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;
266	>	Object[] es;
267		int capacity, h;
268		final int s;
269	<	if ((s = size) == (capacity = (elements = this.elements).length)) {
269	>	if ((s = size) == (capacity = (es = elements).length)) {
270		grow(1);
271	<	capacity = (elements = this.elements).length;
271	>	capacity = (es = elements).length;
272		}
273		if ((h = head - 1) < 0) h = capacity - 1;
274	<	elements[head = h] = e;
274	>	es[head = h] = e;
275		size = s + 1;
276		// checkInvariants();
277		}
#	Line 287 | Line 287 | public class ArrayDeque<E> extends Abstr
287		public void addLast(E e) {
288		// checkInvariants();
289		Objects.requireNonNull(e);
290	<	Object[] elements;
290	>	Object[] es;
291		int capacity;
292		final int s;
293	<	if ((s = size) == (capacity = (elements = this.elements).length)) {
293	>	if ((s = size) == (capacity = (es = elements).length)) {
294		grow(1);
295	<	capacity = (elements = this.elements).length;
295	>	capacity = (es = elements).length;
296		}
297	<	elements[add(head, s, capacity)] = e;
297	>	es[add(head, s, capacity)] = e;
298		size = s + 1;
299		// checkInvariants();
300		}
#	Line 370 | Line 370 | public class ArrayDeque<E> extends Abstr
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	<	if (++h >= elements.length) h = 0;
373	>	final Object[] es = elements;
374	>	@SuppressWarnings("unchecked") E e = (E) es[h = head];
375	>	es[h] = null;
376	>	if (++h >= es.length) h = 0;
377		head = h;
378		size = s - 1;
379		return e;
#	Line 384 | Line 384 | public class ArrayDeque<E> extends Abstr
384		final int s, tail;
385		if ((s = size) <= 0)
386		return null;
387	<	final Object[] elements = this.elements;
387	>	final Object[] es = elements;
388		@SuppressWarnings("unchecked")
389	<	E e = (E) elements[tail = add(head, s - 1, elements.length)];
390	<	elements[tail] = null;
389	>	E e = (E) es[tail = add(head, s - 1, es.length)];
390	>	es[tail] = null;
391		size = s - 1;
392		return e;
393		}
#	Line 409 | Line 409 | public class ArrayDeque<E> extends Abstr
409		// checkInvariants();
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)];
412	>	final Object[] es = elements;
413	>	return (E) es[add(head, s - 1, es.length)];
414		}
415
416		public E peekFirst() {
#	Line 423 | Line 423 | public class ArrayDeque<E> extends Abstr
423		// checkInvariants();
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)];
426	>	final Object[] es = elements;
427	>	return (E) es[add(head, s - 1, es.length)];
428		}
429
430		/**
#	Line 441 | Line 441 | public class ArrayDeque<E> extends Abstr
441		*/
442		public boolean removeFirstOccurrence(Object o) {
443		if (o != null) {
444	<	final Object[] elements = this.elements;
445	<	final int capacity = elements.length;
444	>	final Object[] es = elements;
445		int i, end, to, todo;
446		todo = (end = (i = head) + size)
447	<	- (to = (capacity - end >= 0) ? end : capacity);
448	<	for (;; i = 0, to = todo, todo = 0) {
447	>	- (to = (es.length - end >= 0) ? end : es.length);
448	>	for (;; to = todo, todo = 0, i = 0) {
449		for (; i < to; i++)
450	<	if (o.equals(elements[i])) {
450	>	if (o.equals(es[i])) {
451		delete(i);
452		return true;
453		}
#	Line 472 | Line 471 | public class ArrayDeque<E> extends Abstr
471		*/
472		public boolean removeLastOccurrence(Object o) {
473		if (o != null) {
474	<	final Object[] elements = this.elements;
476	<	final int capacity = elements.length;
474	>	final Object[] es = elements;
475		int i, to, end, todo;
476		todo = (to = ((end = (i = tail()) - size) >= -1) ? end : -1) - end;
477	<	for (;; i = capacity - 1, to = capacity - 1 - todo, todo = 0) {
477	>	for (;; to = (i = es.length - 1) - todo, todo = 0) {
478		for (; i > to; i--)
479	<	if (o.equals(elements[i])) {
479	>	if (o.equals(es[i])) {
480		delete(i);
481		return true;
482		}
#	Line 614 | Line 612 | public class ArrayDeque<E> extends Abstr
612		*/
613		boolean delete(int i) {
614		// checkInvariants();
615	<	final Object[] elements = this.elements;
616	<	final int capacity = elements.length;
615	>	final Object[] es = elements;
616	>	final int capacity = es.length;
617		final int h = head;
618		int front;              // number of elements before to-be-deleted elt
619		if ((front = i - h) < 0) front += capacity;
#	Line 623 | Line 621 | public class ArrayDeque<E> extends Abstr
621		if (front < back) {
622		// move front elements forwards
623		if (h <= i) {
624	<	System.arraycopy(elements, h, elements, h + 1, front);
624	>	System.arraycopy(es, h, es, h + 1, front);
625		} else { // Wrap around
626	<	System.arraycopy(elements, 0, elements, 1, i);
627	<	elements[0] = elements[capacity - 1];
628	<	System.arraycopy(elements, h, elements, h + 1, front - (i + 1));
626	>	System.arraycopy(es, 0, es, 1, i);
627	>	es[0] = es[capacity - 1];
628	>	System.arraycopy(es, h, es, h + 1, front - (i + 1));
629		}
630	<	elements[h] = null;
630	>	es[h] = null;
631		if ((head = (h + 1)) >= capacity) head = 0;
632		size--;
633		// checkInvariants();
#	Line 638 | Line 636 | public class ArrayDeque<E> extends Abstr
636		// move back elements backwards
637		int tail = tail();
638		if (i <= tail) {
639	<	System.arraycopy(elements, i + 1, elements, i, back);
639	>	System.arraycopy(es, i + 1, es, i, back);
640		} else { // Wrap around
641		int firstLeg = capacity - (i + 1);
642	<	System.arraycopy(elements, i + 1, elements, i, firstLeg);
643	<	elements[capacity - 1] = elements[0];
644	<	System.arraycopy(elements, 1, elements, 0, back - firstLeg - 1);
642	>	System.arraycopy(es, i + 1, es, i, firstLeg);
643	>	es[capacity - 1] = es[0];
644	>	System.arraycopy(es, 1, es, 0, back - firstLeg - 1);
645		}
646	<	elements[tail] = null;
646	>	es[tail] = null;
647		size--;
648		// checkInvariants();
649		return true;
#	Line 710 | Line 708 | public class ArrayDeque<E> extends Abstr
708		public E next() {
709		if (remaining <= 0)
710		throw new NoSuchElementException();
711	<	final Object[] elements = ArrayDeque.this.elements;
712	<	E e = nonNullElementAt(elements, cursor);
711	>	final Object[] es = elements;
712	>	E e = nonNullElementAt(es, cursor);
713		lastRet = cursor;
714	<	if (++cursor >= elements.length) cursor = 0;
714	>	if (++cursor >= es.length) cursor = 0;
715		remaining--;
716		return e;
717		}
#	Line 731 | Line 729 | public class ArrayDeque<E> extends Abstr
729		}
730
731		public void forEachRemaining(Consumer<? super E> action) {
732	+	Objects.requireNonNull(action);
733		final int k;
734		if ((k = remaining) > 0) {
735		remaining = 0;
#	Line 747 | Line 746 | public class ArrayDeque<E> extends Abstr
746		public final E next() {
747		if (remaining <= 0)
748		throw new NoSuchElementException();
749	<	final Object[] elements = ArrayDeque.this.elements;
750	<	E e = nonNullElementAt(elements, cursor);
749	>	final Object[] es = elements;
750	>	E e = nonNullElementAt(es, cursor);
751		lastRet = cursor;
752	<	if (--cursor < 0) cursor = elements.length - 1;
752	>	if (--cursor < 0) cursor = es.length - 1;
753		remaining--;
754		return e;
755		}
#	Line 761 | Line 760 | public class ArrayDeque<E> extends Abstr
760		}
761
762		public final void forEachRemaining(Consumer<? super E> action) {
763	+	Objects.requireNonNull(action);
764		final int k;
765		if ((k = remaining) > 0) {
766		remaining = 0;
767	<	forEachRemainingDescending(action, elements, cursor, k);
767	>	final Object[] es = elements;
768	>	int i, end, to, todo;
769	>	todo = (to = ((end = (i = cursor) - k) >= -1) ? end : -1) - end;
770	>	for (;; to = (i = es.length - 1) - todo, todo = 0) {
771	>	for (; i > to; i--)
772	>	action.accept(nonNullElementAt(es, i));
773	>	if (todo == 0) break;
774	>	}
775		if ((lastRet = cursor - (k - 1)) < 0)
776	<	lastRet += elements.length;
776	>	lastRet += es.length;
777		}
778		}
779		}
#	Line 824 | Line 831 | public class ArrayDeque<E> extends Abstr
831		}
832
833		public void forEachRemaining(Consumer<? super E> action) {
834	+	Objects.requireNonNull(action);
835		final int k = remaining(); // side effect!
836		remaining = 0;
837		ArrayDeque.forEachRemaining(action, elements, cursor, k);
#	Line 855 | Line 863 | public class ArrayDeque<E> extends Abstr
863		@SuppressWarnings("unchecked")
864		public void forEach(Consumer<? super E> action) {
865		Objects.requireNonNull(action);
866	<	final Object[] elements = this.elements;
859	<	final int capacity = elements.length;
866	>	final Object[] es = elements;
867		int i, end, to, todo;
868		todo = (end = (i = head) + size)
869	<	- (to = (capacity - end >= 0) ? end : capacity);
870	<	for (;; i = 0, to = todo, todo = 0) {
869	>	- (to = (es.length - end >= 0) ? end : es.length);
870	>	for (;; to = todo, todo = 0, i = 0) {
871		for (; i < to; i++)
872	<	action.accept((E) elements[i]);
872	>	action.accept((E) es[i]);
873		if (todo == 0) break;
874		}
875		// checkInvariants();
#	Line 874 | Line 881 | public class ArrayDeque<E> extends Abstr
881		* checks for concurrent modification, for use in iterators.
882		*/
883		static <E> void forEachRemaining(
884	<	Consumer<? super E> action, Object[] elements, int i, int remaining) {
878	<	Objects.requireNonNull(action);
879	<	final int capacity = elements.length;
884	>	Consumer<? super E> action, Object[] es, int i, int remaining) {
885		int end, to, todo;
886		todo = (end = i + remaining)
887	<	- (to = (capacity - end >= 0) ? end : capacity);
888	<	for (;; i = 0, to = todo, todo = 0) {
887	>	- (to = (es.length - end >= 0) ? end : es.length);
888	>	for (;; to = todo, todo = 0, i = 0) {
889		for (; i < to; i++)
890	<	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 (;; i = capacity - 1, to = capacity - 1 - todo, todo = 0) {
897	<	for (; i > to; i--)
898	<	action.accept(nonNullElementAt(elements, i));
890	>	action.accept(nonNullElementAt(es, i));
891		if (todo == 0) break;
892		}
893		}
#	Line 907 | Line 899 | public class ArrayDeque<E> extends Abstr
899		* @param operator the operator to apply to each element
900		* @since TBD
901		*/
902	+	@SuppressWarnings("unchecked")
903		/* public */ void replaceAll(UnaryOperator<E> operator) {
904		Objects.requireNonNull(operator);
905	<	final Object[] elements = this.elements;
913	<	final int capacity = elements.length;
905	>	final Object[] es = elements;
906		int i, end, to, todo;
907		todo = (end = (i = head) + size)
908	<	- (to = (capacity - end >= 0) ? end : capacity);
909	<	for (;; i = 0, to = todo, todo = 0) {
908	>	- (to = (es.length - end >= 0) ? end : es.length);
909	>	for (;; to = todo, todo = 0, i = 0) {
910		for (; i < to; i++)
911	<	elements[i] = operator.apply(elementAt(i));
911	>	es[i] = operator.apply((E) es[i]);
912		if (todo == 0) break;
913		}
914		// checkInvariants();
#	Line 947 | Line 939 | public class ArrayDeque<E> extends Abstr
939		}
940
941		/** Implementation of bulk remove methods. */
942	+	@SuppressWarnings("unchecked")
943		private boolean bulkRemove(Predicate<? super E> filter) {
944		// checkInvariants();
945	<	final Object[] elements = this.elements;
946	<	final int capacity = elements.length;
947	<	int i = head, j = i, remaining = size, deleted = 0;
945	>	final Object[] es = elements;
946	>	int i, end, to, todo;
947	>	todo = (end = (i = head) + size)
948	>	- (to = (es.length - end >= 0) ? end : es.length);
949	>	// Optimize for initial run of non-removed elements
950	>	findFirstRemoved:
951	>	for (;; to = todo, todo = 0, i = 0) {
952	>	for (; i < to; i++)
953	>	if (filter.test((E) es[i]))
954	>	break findFirstRemoved;
955	>	if (todo == 0) return false;
956	>	}
957	>	bulkRemoveModified(filter, i, to, todo);
958	>	return true;
959	>	}
960	>
961	>	/**
962	>	* Helper for bulkRemove, in case of at least one deletion.
963	>	* @param i valid index of first element to be deleted
964	>	*/
965	>	@SuppressWarnings("unchecked")
966	>	private void bulkRemoveModified(
967	>	Predicate<? super E> filter, int i, int to, int todo) {
968	>	final Object[] es = elements;
969	>	final int capacity = es.length;
970	>	// a two-finger algorithm, with hare i and tortoise j
971	>	int j = i++;
972		try {
973	<	for (; remaining > 0; remaining--) {
974	<	@SuppressWarnings("unchecked") E e = (E) elements[i];
975	<	if (filter.test(e))
976	<	deleted++;
977	<	else {
978	<	if (j != i)
979	<	elements[j] = e;
980	<	if (++j >= capacity) j = 0;
981	<	}
982	<	if (++i >= capacity) i = 0;
973	>	for (;;) {
974	>	E e;
975	>	// In this loop, i and j are on the same leg, with i > j
976	>	for (; i < to; i++)
977	>	if (!filter.test(e = (E) es[i]))
978	>	es[j++] = e;
979	>	if (todo == 0) break;
980	>	// In this loop, j is on the first leg, i on the second
981	>	for (to = todo, todo = 0, i = 0; i < to && j < capacity; i++)
982	>	if (!filter.test(e = (E) es[i]))
983	>	es[j++] = e;
984	>	if (i >= to) break;
985	>	j = 0;          // j rejoins i on second leg
986		}
987	<	return deleted > 0;
987	>	bulkRemoveClear(es, j, i);
988	>	// checkInvariants();
989		} catch (Throwable ex) {
990	<	if (deleted > 0)
991	<	for (; remaining > 0; remaining--) {
992	<	elements[j] = elements[i];
993	<	if (++i >= capacity) i = 0;
994	<	if (++j >= capacity) j = 0;
995	<	}
996	<	throw ex;
976	<	} finally {
977	<	size -= deleted;
978	<	clearSlice(elements, j, deleted);
990	>	// copy remaining elements
991	>	for (int remaining = (to - i) + todo; --remaining >= 0;) {
992	>	es[j] = es[i];
993	>	if (++i >= capacity) i = 0;
994	>	if (++j >= capacity) j = 0;
995	>	}
996	>	bulkRemoveClear(es, j, i);
997		// checkInvariants();
998	+	throw ex;
999		}
1000		}
1001
1002		/**
1003	+	* Nulls out all elements from index j upto index i.
1004	+	*/
1005	+	private void bulkRemoveClear(Object[] es, int j, int i) {
1006	+	int deleted;
1007	+	if ((deleted = i - j) <= 0) deleted += es.length;
1008	+	size -= deleted;
1009	+	circularClear(es, j, deleted);
1010	+	}
1011	+
1012	+	/**
1013		* Returns {@code true} if this deque contains the specified element.
1014		* More formally, returns {@code true} if and only if this deque contains
1015		* at least one element {@code e} such that {@code o.equals(e)}.
#	Line 990 | Line 1019 | public class ArrayDeque<E> extends Abstr
1019		*/
1020		public boolean contains(Object o) {
1021		if (o != null) {
1022	<	final Object[] elements = this.elements;
994	<	final int capacity = elements.length;
1022	>	final Object[] es = elements;
1023		int i, end, to, todo;
1024		todo = (end = (i = head) + size)
1025	<	- (to = (capacity - end >= 0) ? end : capacity);
1026	<	for (;; i = 0, to = todo, todo = 0) {
1025	>	- (to = (es.length - end >= 0) ? end : es.length);
1026	>	for (;; to = todo, todo = 0, i = 0) {
1027		for (; i < to; i++)
1028	<	if (o.equals(elements[i]))
1028	>	if (o.equals(es[i]))
1029		return true;
1030		if (todo == 0) break;
1031		}
#	Line 1027 | Line 1055 | public class ArrayDeque<E> extends Abstr
1055		* The deque will be empty after this call returns.
1056		*/
1057		public void clear() {
1058	<	clearSlice(elements, head, size);
1058	>	circularClear(elements, head, size);
1059		size = head = 0;
1060		// checkInvariants();
1061		}
1062
1063		/**
1064		* Nulls out count elements, starting at array index from.
1065	+	* Special case (from == es.length) is treated the same as (from == 0).
1066		*/
1067	<	private static void clearSlice(Object[] elements, int from, int count) {
1068	<	final int capacity = elements.length, end = from + count;
1069	<	final int leg = (capacity - end >= 0) ? end : capacity;
1070	<	Arrays.fill(elements, from, leg, null);
1071	<	if (leg != end)
1072	<	Arrays.fill(elements, 0, end - capacity, null);
1067	>	private static void circularClear(Object[] es, int from, int count) {
1068	>	int end, to, todo;
1069	>	todo = (end = from + count)
1070	>	- (to = (es.length - end >= 0) ? end : es.length);
1071	>	for (;; to = todo, todo = 0, from = 0) {
1072	>	Arrays.fill(es, from, to, null);
1073	>	if (todo == 0) break;
1074	>	}
1075		}
1076
1077		/**
#	Line 1061 | Line 1092 | public class ArrayDeque<E> extends Abstr
1092		}
1093
1094		private <T> T[] toArray(Class<T[]> klazz) {
1095	<	final Object[] elements = this.elements;
1065	<	final int capacity = elements.length;
1066	<	final int head = this.head, end = head + size;
1095	>	final Object[] es = elements;
1096		final T[] a;
1097	<	if (end >= 0) {
1098	<	a = Arrays.copyOfRange(elements, head, end, klazz);
1097	>	final int head, len, end, todo;
1098	>	todo = size - (len = Math.min(size, es.length - (head = this.head)));
1099	>	if ((end = head + size) >= 0) {
1100	>	a = Arrays.copyOfRange(es, head, end, klazz);
1101		} else {
1102		// integer overflow!
1103	<	a = Arrays.copyOfRange(elements, 0, size, klazz);
1104	<	System.arraycopy(elements, head, a, 0, capacity - head);
1103	>	a = Arrays.copyOfRange(es, 0, size, klazz);
1104	>	System.arraycopy(es, head, a, 0, len);
1105		}
1106	<	if (end - capacity > 0)
1107	<	System.arraycopy(elements, 0, a, capacity - head, end - capacity);
1106	>	if (todo > 0)
1107	>	System.arraycopy(es, 0, a, len, todo);
1108		return a;
1109		}
1110
#	Line 1115 | Line 1146 | public class ArrayDeque<E> extends Abstr
1146		*/
1147		@SuppressWarnings("unchecked")
1148		public <T> T[] toArray(T[] a) {
1149	<	final int size = this.size;
1150	<	if (size > a.length)
1149	>	final int size;
1150	>	if ((size = this.size) > a.length)
1151		return toArray((Class<T[]>) a.getClass());
1152	<	final Object[] elements = this.elements;
1153	<	final int capacity = elements.length;
1154	<	final int head = this.head, end = head + size;
1155	<	final int front = (capacity - end >= 0) ? size : capacity - head;
1156	<	System.arraycopy(elements, head, a, 0, front);
1157	<	if (front != size)
1158	<	System.arraycopy(elements, 0, a, capacity - head, end - capacity);
1152	>	final Object[] es = elements;
1153	>	int i, j, len, todo;
1154	>	todo = size - (len = Math.min(size, es.length - (i = head)));
1155	>	for (j = 0;; j += len, len = todo, todo = 0, i = 0) {
1156	>	System.arraycopy(es, i, a, j, len);
1157	>	if (todo == 0) break;
1158	>	}
1159		if (size < a.length)
1160		a[size] = null;
1161		return a;
#	Line 1167 | Line 1198 | public class ArrayDeque<E> extends Abstr
1198		s.writeInt(size);
1199
1200		// Write out elements in order.
1201	<	final Object[] elements = this.elements;
1171	<	final int capacity = elements.length;
1201	>	final Object[] es = elements;
1202		int i, end, to, todo;
1203		todo = (end = (i = head) + size)
1204	<	- (to = (capacity - end >= 0) ? end : capacity);
1205	<	for (;; i = 0, to = todo, todo = 0) {
1204	>	- (to = (es.length - end >= 0) ? end : es.length);
1205	>	for (;; to = todo, todo = 0, i = 0) {
1206		for (; i < to; i++)
1207	<	s.writeObject(elements[i]);
1207	>	s.writeObject(es[i]);
1208		if (todo == 0) break;
1209		}
1210		}

Diff Legend

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