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.77 by jsr166, Tue Oct 18 00:33:05 2016 UTC vs.
Revision 1.88 by jsr166, Mon Oct 24 16:01:25 2016 UTC

#	Line 134 | Line 134 | public class ArrayDeque<E> extends Abstr
134		* to ensure that it can hold at least the given number of elements.
135		*
136		* @param minCapacity the desired minimum capacity
137	<	* @since 9
137	>	* @since TBD
138		*/
139	<	public void ensureCapacity(int minCapacity) {
139	>	/* public */ void ensureCapacity(int minCapacity) {
140		if (minCapacity > elements.length)
141		grow(minCapacity - elements.length);
142		// checkInvariants();
#	Line 145 | Line 145 | public class ArrayDeque<E> extends Abstr
145		/**
146		* Minimizes the internal storage of this collection.
147		*
148	<	* @since 9
148	>	* @since TBD
149		*/
150	<	public void trimToSize() {
150	>	/* public */ void trimToSize() {
151		if (size < elements.length) {
152		elements = toArray();
153		head = 0;
#	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
198		/**
199	–	* Returns the array index of the last element.
200	–	* May return invalid index -1 if there are no elements.
201	–	*/
202	–	final int tail() {
203	–	return add(head, size - 1, elements.length);
204	–	}
205	–
206	–	/**
207	–	* Adds i and j, mod modulus.
208	–	* Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
209	–	*/
210	–	static final int add(int i, int j, int modulus) {
211	–	if ((i += j) - modulus >= 0) i -= modulus;
212	–	return i;
213	–	}
214	–
215	–	/**
199		* Increments i, mod modulus.
200		* Precondition and postcondition: 0 <= i < modulus.
201		*/
#	Line 231 | Line 214 | public class ArrayDeque<E> extends Abstr
214		}
215
216		/**
217	+	* Adds i and j, mod modulus.
218	+	* Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
219	+	*/
220	+	static final int add(int i, int j, int modulus) {
221	+	if ((i += j) - modulus >= 0) i -= modulus;
222	+	return i;
223	+	}
224	+
225	+	/**
226	+	* Returns the array index of the last element.
227	+	* May return invalid index -1 if there are no elements.
228	+	*/
229	+	final int tail() {
230	+	return add(head, size - 1, elements.length);
231	+	}
232	+
233	+	/**
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 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))
269	<	grow(1);
270	<	elements[head = dec(head, capacity)] = 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;
272		size = s + 1;
273	+	// checkInvariants();
274	+	}
275	+
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
282		/**
#	Line 282 | Line 290 | public class ArrayDeque<E> extends Abstr
290		public void addLast(E e) {
291		// checkInvariants();
292		Objects.requireNonNull(e);
293	<	Object[] elements;
294	<	int capacity, s = size;
295	<	while (s == (capacity = (elements = this.elements).length))
296	<	grow(1);
297	<	elements[add(head, s, capacity)] = e;
293	>	final Object[] elements;
294	>	final int capacity, s;
295	>	if ((s = size) == (capacity = (elements = this.elements).length))
296	>	addLastSlowPath(e);
297	>	else
298	>	elements[add(head, s, capacity)] = e;
299		size = s + 1;
300	+	// checkInvariants();
301	+	}
302	+
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
309		/**
#	Line 301 | Line 317 | public class ArrayDeque<E> extends Abstr
317		* @throws NullPointerException if the specified collection or any
318		*         of its elements are null
319		*/
304	–	@Override
320		public boolean addAll(Collection<? extends E> c) {
321	+	final int s = size, needed = c.size() - (elements.length - s);
322	+	if (needed > 0)
323	+	grow(needed);
324	+	c.forEach((e) -> addLast(e));
325		// checkInvariants();
326	<	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;
326	>	return size > s;
327		}
328
329		/**
#	Line 349 | Line 355 | public class ArrayDeque<E> extends Abstr
355		*/
356		public E removeFirst() {
357		// checkInvariants();
358	<	E x = pollFirst();
359	<	if (x == null)
358	>	E e = pollFirst();
359	>	if (e == null)
360		throw new NoSuchElementException();
361	<	return x;
361	>	return e;
362		}
363
364		/**
#	Line 360 | Line 366 | public class ArrayDeque<E> extends Abstr
366		*/
367		public E removeLast() {
368		// checkInvariants();
369	<	E x = pollLast();
370	<	if (x == null)
369	>	E e = pollLast();
370	>	if (e == null)
371		throw new NoSuchElementException();
372	<	return x;
372	>	return e;
373		}
374
375		public E pollFirst() {
#	Line 689 | Line 695 | public class ArrayDeque<E> extends Abstr
695
696		DeqIterator() { cursor = head; }
697
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	–
698		public final boolean hasNext() {
699		return remaining > 0;
700		}
701
702	<	public final E next() {
702	>	public E next() {
703		if (remaining == 0)
704		throw new NoSuchElementException();
705		E e = checkedElementAt(elements, cursor);
706		lastRet = cursor;
707	<	cursor = advance(cursor, elements.length);
707	>	cursor = inc(cursor, elements.length);
708		remaining--;
709		return e;
710		}
711
712	+	void postDelete(boolean leftShifted) {
713	+	if (leftShifted)
714	+	cursor = dec(cursor, elements.length); // undo inc in next
715	+	}
716	+
717		public final void remove() {
718		if (lastRet < 0)
719		throw new IllegalStateException();
720	<	doRemove();
720	>	postDelete(delete(lastRet));
721		lastRet = -1;
722		}
723
724	<	public final void forEachRemaining(Consumer<? super E> action) {
724	>	public void forEachRemaining(Consumer<? super E> action) {
725		Objects.requireNonNull(action);
726		final Object[] elements = ArrayDeque.this.elements;
727		final int capacity = elements.length;
728		int k = remaining;
729		remaining = 0;
730	<	for (int i = cursor; --k >= 0; i = advance(i, capacity))
730	>	for (int i = cursor; --k >= 0; i = inc(i, capacity))
731		action.accept(checkedElementAt(elements, i));
732		}
733		}
#	Line 734 | Line 735 | public class ArrayDeque<E> extends Abstr
735		private class DescendingIterator extends DeqIterator {
736		DescendingIterator() { cursor = tail(); }
737
738	<	@Override int advance(int i, int modulus) {
739	<	return dec(i, modulus);
738	>	public final E next() {
739	>	if (remaining == 0)
740	>	throw new NoSuchElementException();
741	>	E e = checkedElementAt(elements, cursor);
742	>	lastRet = cursor;
743	>	cursor = dec(cursor, elements.length);
744	>	remaining--;
745	>	return e;
746	>	}
747	>
748	>	void postDelete(boolean leftShifted) {
749	>	if (!leftShifted)
750	>	cursor = inc(cursor, elements.length); // undo dec in next
751		}
752
753	<	@Override void doRemove() {
754	<	if (!delete(lastRet))
755	<	// if right-shifted, undo advance in next
756	<	cursor = inc(cursor, elements.length);
753	>	public final void forEachRemaining(Consumer<? super E> action) {
754	>	Objects.requireNonNull(action);
755	>	final Object[] elements = ArrayDeque.this.elements;
756	>	final int capacity = elements.length;
757	>	int k = remaining;
758	>	remaining = 0;
759	>	for (int i = cursor; --k >= 0; i = dec(i, capacity))
760	>	action.accept(checkedElementAt(elements, i));
761		}
762		}
763
#	Line 829 | Line 845 | public class ArrayDeque<E> extends Abstr
845		}
846		}
847
832	–	@Override
848		public void forEach(Consumer<? super E> action) {
849		// checkInvariants();
850		Objects.requireNonNull(action);
#	Line 845 | Line 860 | public class ArrayDeque<E> extends Abstr
860		* operator to that element, as specified by {@link List#replaceAll}.
861		*
862		* @param operator the operator to apply to each element
863	<	* @since 9
863	>	* @since TBD
864		*/
865	<	public void replaceAll(UnaryOperator<E> operator) {
865	>	/* public */ void replaceAll(UnaryOperator<E> operator) {
866		Objects.requireNonNull(operator);
867		final Object[] elements = this.elements;
868		final int capacity = elements.length;
#	Line 859 | Line 874 | public class ArrayDeque<E> extends Abstr
874		/**
875		* @throws NullPointerException {@inheritDoc}
876		*/
862	–	@Override
877		public boolean removeIf(Predicate<? super E> filter) {
878		Objects.requireNonNull(filter);
879		return bulkRemove(filter);
#	Line 868 | Line 882 | public class ArrayDeque<E> extends Abstr
882		/**
883		* @throws NullPointerException {@inheritDoc}
884		*/
871	–	@Override
885		public boolean removeAll(Collection<?> c) {
886		Objects.requireNonNull(c);
887		return bulkRemove(e -> c.contains(e));
#	Line 877 | Line 890 | public class ArrayDeque<E> extends Abstr
890		/**
891		* @throws NullPointerException {@inheritDoc}
892		*/
880	–	@Override
893		public boolean retainAll(Collection<?> c) {
894		Objects.requireNonNull(c);
895		return bulkRemove(e -> !c.contains(e));
#	Line 902 | Line 914 | public class ArrayDeque<E> extends Abstr
914		}
915		return deleted > 0;
916		} catch (Throwable ex) {
917	<	for (; remaining > 0;
918	<	remaining--, i = inc(i, capacity), j = inc(j, capacity))
919	<	elements[j] = elements[i];
917	>	if (deleted > 0)
918	>	for (; remaining > 0;
919	>	remaining--, i = inc(i, capacity), j = inc(j, capacity))
920	>	elements[j] = elements[i];
921		throw ex;
922		} finally {
923		size -= deleted;
#	Line 956 | Line 969 | public class ArrayDeque<E> extends Abstr
969		*/
970		public void clear() {
971		final Object[] elements = this.elements;
972	<	final int capacity = elements.length;
973	<	final int h = this.head;
974	<	final int s = size;
962	<	if (capacity - h >= s)
963	<	Arrays.fill(elements, h, h + s, null);
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, h, capacity, null);
977	<	Arrays.fill(elements, 0, s - capacity + h, null);
976	>	Arrays.fill(elements, head, capacity, null);
977	>	Arrays.fill(elements, 0, tail - capacity, null);
978		}
979		size = head = 0;
980		// checkInvariants();
#	Line 983 | Line 994 | public class ArrayDeque<E> extends Abstr
994		* @return an array containing all of the elements in this deque
995		*/
996		public Object[] toArray() {
997	<	final int head = this.head;
998	<	final int firstLeg;
999	<	Object[] a = Arrays.copyOfRange(elements, head, head + size);
1000	<	if ((firstLeg = elements.length - head) < size)
1001	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
997	>	return toArray(Object[].class);
998	>	}
999	>
1000	>	private <T> T[] toArray(Class<T[]> klazz) {
1001	>	final Object[] elements = this.elements;
1002	>	final int capacity = elements.length;
1003	>	final int head = this.head, tail = head + size;
1004	>	final T[] a;
1005	>	if (tail >= 0) {
1006	>	a = Arrays.copyOfRange(elements, head, tail, klazz);
1007	>	} else {
1008	>	// integer overflow!
1009	>	a = Arrays.copyOfRange(elements, 0, size, klazz);
1010	>	System.arraycopy(elements, head, a, 0, capacity - head);
1011	>	}
1012	>	if (tail - capacity > 0)
1013	>	System.arraycopy(elements, 0, a, capacity - head, tail - capacity);
1014		return a;
1015		}
1016
#	Line 1029 | Line 1052 | public class ArrayDeque<E> extends Abstr
1052		*/
1053		@SuppressWarnings("unchecked")
1054		public <T> T[] toArray(T[] a) {
1055	+	final int size = this.size;
1056	+	if (size > a.length)
1057	+	return toArray((Class<T[]>) a.getClass());
1058		final Object[] elements = this.elements;
1059	<	final int head = this.head;
1060	<	final int firstLeg;
1061	<	boolean wrap = (firstLeg = elements.length - head) < size;
1062	<	if (size > a.length) {
1063	<	a = (T[]) Arrays.copyOfRange(elements, head, head + size,
1064	<	a.getClass());
1065	<	} else {
1040	<	System.arraycopy(elements, head, a, 0, wrap ? firstLeg : size);
1041	<	if (size < a.length)
1042	<	a[size] = null;
1059	>	final int capacity = elements.length;
1060	>	final int head = this.head, tail = head + size;
1061	>	if (capacity - tail >= 0)
1062	>	System.arraycopy(elements, head, a, 0, size);
1063	>	else {
1064	>	System.arraycopy(elements, head, a, 0, capacity - head);
1065	>	System.arraycopy(elements, 0, a, capacity - head, tail - capacity);
1066		}
1067	<	if (wrap)
1068	<	System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1067	>	if (size < a.length)
1068	>	a[size] = null;
1069		return a;
1070		}
1071

Diff Legend

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