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.17 by dl, Thu Sep 15 16:55:24 2005 UTC vs.
Revision 1.44 by dl, Tue Jan 22 19:28:04 2013 UTC

#	Line 1 | Line 1
1		/*
2	<	* Written by Josh Bloch of Google Inc. and released to the public domain,
3	<	* as explained at http://creativecommons.org/licenses/publicdomain.
2	>	* Written by Doug Lea with assistance from members of JCP JSR-166
3	>	* Expert Group and released to the public domain, as explained at
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7		package java.util;
8	<	import java.util.*; // for javadoc (till 6280605 is fixed)
9	<	import java.io.*;
8	>	import java.util.Spliterator;
9	>	import java.util.stream.Stream;
10	>	import java.util.stream.Streams;
11	>	import java.util.function.Block;
12
13		/**
14		* Resizable-array implementation of the {@link Deque} interface.  Array
#	Line 16 | Line 19 | import java.io.*;
19		* {@link Stack} when used as a stack, and faster than {@link LinkedList}
20		* when used as a queue.
21		*
22	<	* <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
22	>	* <p>Most {@code ArrayDeque} operations run in amortized constant time.
23		* Exceptions include {@link #remove(Object) remove}, {@link
24		* #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
25		* removeLastOccurrence}, {@link #contains contains}, {@link #iterator
26		* iterator.remove()}, and the bulk operations, all of which run in linear
27		* time.
28		*
29	<	* <p>The iterators returned by this class's <tt>iterator</tt> method are
29	>	* <p>The iterators returned by this class's {@code iterator} method are
30		* <i>fail-fast</i>: If the deque is modified at any time after the iterator
31	<	* is created, in any way except through the iterator's own <tt>remove</tt>
31	>	* is created, in any way except through the iterator's own {@code remove}
32		* method, the iterator will generally throw a {@link
33		* ConcurrentModificationException}.  Thus, in the face of concurrent
34		* modification, the iterator fails quickly and cleanly, rather than risking
#	Line 35 | Line 38 | import java.io.*;
38		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
39		* as it is, generally speaking, impossible to make any hard guarantees in the
40		* presence of unsynchronized concurrent modification.  Fail-fast iterators
41	<	* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
41	>	* throw {@code ConcurrentModificationException} on a best-effort basis.
42		* Therefore, it would be wrong to write a program that depended on this
43		* exception for its correctness: <i>the fail-fast behavior of iterators
44		* should be used only to detect bugs.</i>
#	Line 45 | Line 48 | import java.io.*;
48		* Iterator} interfaces.
49		*
50		* <p>This class is a member of the
51	<	* <a href="{@docRoot}/../guide/collections/index.html">
51	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
52		* Java Collections Framework</a>.
53		*
54		* @author  Josh Bloch and Doug Lea
#	Line 53 | Line 56 | import java.io.*;
56		* @param <E> the type of elements held in this collection
57		*/
58		public class ArrayDeque<E> extends AbstractCollection<E>
59	<	implements Deque<E>, Cloneable, Serializable
59	>	implements Deque<E>, Cloneable, java.io.Serializable
60		{
61		/**
62		* The array in which the elements of the deque are stored.
#	Line 65 | Line 68 | public class ArrayDeque<E> extends Abstr
68		* other.  We also guarantee that all array cells not holding
69		* deque elements are always null.
70		*/
71	<	private transient E[] elements;
71	>	transient Object[] elements; // non-private to simplify nested class access
72
73		/**
74		* The index of the element at the head of the deque (which is the
75		* element that would be removed by remove() or pop()); or an
76		* arbitrary number equal to tail if the deque is empty.
77		*/
78	<	private transient int head;
78	>	transient int head;
79
80		/**
81		* The index at which the next element would be added to the tail
82		* of the deque (via addLast(E), add(E), or push(E)).
83		*/
84	<	private transient int tail;
84	>	transient int tail;
85
86		/**
87		* The minimum capacity that we'll use for a newly created deque.
#	Line 89 | Line 92 | public class ArrayDeque<E> extends Abstr
92		// ******  Array allocation and resizing utilities ******
93
94		/**
95	<	* Allocate empty array to hold the given number of elements.
95	>	* Allocates empty array to hold the given number of elements.
96		*
97		* @param numElements  the number of elements to hold
98		*/
#	Line 109 | Line 112 | public class ArrayDeque<E> extends Abstr
112		if (initialCapacity < 0)   // Too many elements, must back off
113		initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
114		}
115	<	elements = (E[]) new Object[initialCapacity];
115	>	elements = new Object[initialCapacity];
116		}
117
118		/**
119	<	* Double the capacity of this deque.  Call only when full, i.e.,
119	>	* Doubles the capacity of this deque.  Call only when full, i.e.,
120		* when head and tail have wrapped around to become equal.
121		*/
122		private void doubleCapacity() {
#	Line 127 | Line 130 | public class ArrayDeque<E> extends Abstr
130		Object[] a = new Object[newCapacity];
131		System.arraycopy(elements, p, a, 0, r);
132		System.arraycopy(elements, 0, a, r, p);
133	<	elements = (E[])a;
133	>	elements = a;
134		head = 0;
135		tail = n;
136		}
#	Line 155 | Line 158 | public class ArrayDeque<E> extends Abstr
158		* sufficient to hold 16 elements.
159		*/
160		public ArrayDeque() {
161	<	elements = (E[]) new Object[16];
161	>	elements = new Object[16];
162		}
163
164		/**
#	Line 221 | Line 224 | public class ArrayDeque<E> extends Abstr
224		* Inserts the specified element at the front of this deque.
225		*
226		* @param e the element to add
227	<	* @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
227	>	* @return {@code true} (as specified by {@link Deque#offerFirst})
228		* @throws NullPointerException if the specified element is null
229		*/
230		public boolean offerFirst(E e) {
#	Line 233 | Line 236 | public class ArrayDeque<E> extends Abstr
236		* Inserts the specified element at the end of this deque.
237		*
238		* @param e the element to add
239	<	* @return <tt>true</tt> (as specified by {@link Deque#offerLast})
239	>	* @return {@code true} (as specified by {@link Deque#offerLast})
240		* @throws NullPointerException if the specified element is null
241		*/
242		public boolean offerLast(E e) {
#	Line 263 | Line 266 | public class ArrayDeque<E> extends Abstr
266
267		public E pollFirst() {
268		int h = head;
269	<	E result = elements[h]; // Element is null if deque empty
269	>	@SuppressWarnings("unchecked")
270	>	E result = (E) elements[h];
271	>	// Element is null if deque empty
272		if (result == null)
273		return null;
274		elements[h] = null;     // Must null out slot
#	Line 273 | Line 278 | public class ArrayDeque<E> extends Abstr
278
279		public E pollLast() {
280		int t = (tail - 1) & (elements.length - 1);
281	<	E result = elements[t];
281	>	@SuppressWarnings("unchecked")
282	>	E result = (E) elements[t];
283		if (result == null)
284		return null;
285		elements[t] = null;
#	Line 285 | Line 291 | public class ArrayDeque<E> extends Abstr
291		* @throws NoSuchElementException {@inheritDoc}
292		*/
293		public E getFirst() {
294	<	E x = elements[head];
295	<	if (x == null)
294	>	@SuppressWarnings("unchecked")
295	>	E result = (E) elements[head];
296	>	if (result == null)
297		throw new NoSuchElementException();
298	<	return x;
298	>	return result;
299		}
300
301		/**
302		* @throws NoSuchElementException {@inheritDoc}
303		*/
304		public E getLast() {
305	<	E x = elements[(tail - 1) & (elements.length - 1)];
306	<	if (x == null)
305	>	@SuppressWarnings("unchecked")
306	>	E result = (E) elements[(tail - 1) & (elements.length - 1)];
307	>	if (result == null)
308		throw new NoSuchElementException();
309	<	return x;
309	>	return result;
310		}
311
312	+	@SuppressWarnings("unchecked")
313		public E peekFirst() {
314	<	return elements[head]; // elements[head] is null if deque empty
314	>	// elements[head] is null if deque empty
315	>	return (E) elements[head];
316		}
317
318	+	@SuppressWarnings("unchecked")
319		public E peekLast() {
320	<	return elements[(tail - 1) & (elements.length - 1)];
320	>	return (E) elements[(tail - 1) & (elements.length - 1)];
321		}
322
323		/**
324		* Removes the first occurrence of the specified element in this
325		* deque (when traversing the deque from head to tail).
326		* If the deque does not contain the element, it is unchanged.
327	<	* More formally, removes the first element <tt>e</tt> such that
328	<	* <tt>o.equals(e)</tt> (if such an element exists).
329	<	* Returns <tt>true</tt> if this deque contained the specified element
327	>	* More formally, removes the first element {@code e} such that
328	>	* {@code o.equals(e)} (if such an element exists).
329	>	* Returns {@code true} if this deque contained the specified element
330		* (or equivalently, if this deque changed as a result of the call).
331		*
332		* @param o element to be removed from this deque, if present
333	<	* @return <tt>true</tt> if the deque contained the specified element
333	>	* @return {@code true} if the deque contained the specified element
334		*/
335		public boolean removeFirstOccurrence(Object o) {
336		if (o == null)
337		return false;
338		int mask = elements.length - 1;
339		int i = head;
340	<	E x;
340	>	Object x;
341		while ( (x = elements[i]) != null) {
342		if (o.equals(x)) {
343		delete(i);
#	Line 341 | Line 352 | public class ArrayDeque<E> extends Abstr
352		* Removes the last occurrence of the specified element in this
353		* deque (when traversing the deque from head to tail).
354		* If the deque does not contain the element, it is unchanged.
355	<	* More formally, removes the last element <tt>e</tt> such that
356	<	* <tt>o.equals(e)</tt> (if such an element exists).
357	<	* Returns <tt>true</tt> if this deque contained the specified element
355	>	* More formally, removes the last element {@code e} such that
356	>	* {@code o.equals(e)} (if such an element exists).
357	>	* Returns {@code true} if this deque contained the specified element
358		* (or equivalently, if this deque changed as a result of the call).
359		*
360		* @param o element to be removed from this deque, if present
361	<	* @return <tt>true</tt> if the deque contained the specified element
361	>	* @return {@code true} if the deque contained the specified element
362		*/
363		public boolean removeLastOccurrence(Object o) {
364		if (o == null)
365		return false;
366		int mask = elements.length - 1;
367		int i = (tail - 1) & mask;
368	<	E x;
368	>	Object x;
369		while ( (x = elements[i]) != null) {
370		if (o.equals(x)) {
371		delete(i);
#	Line 373 | Line 384 | public class ArrayDeque<E> extends Abstr
384		* <p>This method is equivalent to {@link #addLast}.
385		*
386		* @param e the element to add
387	<	* @return <tt>true</tt> (as specified by {@link Collection#add})
387	>	* @return {@code true} (as specified by {@link Collection#add})
388		* @throws NullPointerException if the specified element is null
389		*/
390		public boolean add(E e) {
#	Line 387 | Line 398 | public class ArrayDeque<E> extends Abstr
398		* <p>This method is equivalent to {@link #offerLast}.
399		*
400		* @param e the element to add
401	<	* @return <tt>true</tt> (as specified by {@link Queue#offer})
401	>	* @return {@code true} (as specified by {@link Queue#offer})
402		* @throws NullPointerException if the specified element is null
403		*/
404		public boolean offer(E e) {
#	Line 412 | Line 423 | public class ArrayDeque<E> extends Abstr
423		/**
424		* Retrieves and removes the head of the queue represented by this deque
425		* (in other words, the first element of this deque), or returns
426	<	* <tt>null</tt> if this deque is empty.
426	>	* {@code null} if this deque is empty.
427		*
428		* <p>This method is equivalent to {@link #pollFirst}.
429		*
430		* @return the head of the queue represented by this deque, or
431	<	*         <tt>null</tt> if this deque is empty
431	>	*         {@code null} if this deque is empty
432		*/
433		public E poll() {
434		return pollFirst();
#	Line 439 | Line 450 | public class ArrayDeque<E> extends Abstr
450
451		/**
452		* Retrieves, but does not remove, the head of the queue represented by
453	<	* this deque, or returns <tt>null</tt> if this deque is empty.
453	>	* this deque, or returns {@code null} if this deque is empty.
454		*
455		* <p>This method is equivalent to {@link #peekFirst}.
456		*
457		* @return the head of the queue represented by this deque, or
458	<	*         <tt>null</tt> if this deque is empty
458	>	*         {@code null} if this deque is empty
459		*/
460		public E peek() {
461		return peekFirst();
#	Line 479 | Line 490 | public class ArrayDeque<E> extends Abstr
490		return removeFirst();
491		}
492
493	+	private void checkInvariants() {
494	+	assert elements[tail] == null;
495	+	assert head == tail ? elements[head] == null :
496	+	(elements[head] != null &&
497	+	elements[(tail - 1) & (elements.length - 1)] != null);
498	+	assert elements[(head - 1) & (elements.length - 1)] == null;
499	+	}
500	+
501		/**
502		* Removes the element at the specified position in the elements array,
503		* adjusting head and tail as necessary.  This can result in motion of
#	Line 490 | Line 509 | public class ArrayDeque<E> extends Abstr
509		* @return true if elements moved backwards
510		*/
511		private boolean delete(int i) {
512	<	int mask = elements.length - 1;
513	<
514	<	// Invariant: head <= i < tail mod circularity
515	<	if (((i - head) & mask) >= ((tail - head) & mask))
516	<	throw new ConcurrentModificationException();
517	<
518	<	// Case 1: Deque doesn't wrap
519	<	// Case 2: Deque does wrap and removed element is in the head portion
520	<	if (i >= head) {
521	<	System.arraycopy(elements, head, elements, head + 1, i - head);
522	<	elements[head] = null;
523	<	head = (head + 1) & mask;
512	>	checkInvariants();
513	>	final Object[] elements = this.elements;
514	>	final int mask = elements.length - 1;
515	>	final int h = head;
516	>	final int t = tail;
517	>	final int front = (i - h) & mask;
518	>	final int back  = (t - i) & mask;
519	>
520	>	// Invariant: head <= i < tail mod circularity
521	>	if (front >= ((t - h) & mask))
522	>	throw new ConcurrentModificationException();
523	>
524	>	// Optimize for least element motion
525	>	if (front < back) {
526	>	if (h <= i) {
527	>	System.arraycopy(elements, h, elements, h + 1, front);
528	>	} else { // Wrap around
529	>	System.arraycopy(elements, 0, elements, 1, i);
530	>	elements[0] = elements[mask];
531	>	System.arraycopy(elements, h, elements, h + 1, mask - h);
532	>	}
533	>	elements[h] = null;
534	>	head = (h + 1) & mask;
535		return false;
536	+	} else {
537	+	if (i < t) { // Copy the null tail as well
538	+	System.arraycopy(elements, i + 1, elements, i, back);
539	+	tail = t - 1;
540	+	} else { // Wrap around
541	+	System.arraycopy(elements, i + 1, elements, i, mask - i);
542	+	elements[mask] = elements[0];
543	+	System.arraycopy(elements, 1, elements, 0, t);
544	+	tail = (t - 1) & mask;
545	+	}
546	+	return true;
547		}
507	–
508	–	// Case 3: Deque wraps and removed element is in the tail portion
509	–	tail--;
510	–	System.arraycopy(elements, i + 1, elements, i, tail - i);
511	–	elements[tail] = null;
512	–	return true;
548		}
549
550		// *** Collection Methods ***
#	Line 524 | Line 559 | public class ArrayDeque<E> extends Abstr
559		}
560
561		/**
562	<	* Returns <tt>true</tt> if this deque contains no elements.
562	>	* Returns {@code true} if this deque contains no elements.
563		*
564	<	* @return <tt>true</tt> if this deque contains no elements
564	>	* @return {@code true} if this deque contains no elements
565		*/
566		public boolean isEmpty() {
567		return head == tail;
#	Line 538 | Line 573 | public class ArrayDeque<E> extends Abstr
573		* order that elements would be dequeued (via successive calls to
574		* {@link #remove} or popped (via successive calls to {@link #pop}).
575		*
576	<	* @return an <tt>Iterator</tt> over the elements in this deque
576	>	* @return an iterator over the elements in this deque
577		*/
578		public Iterator<E> iterator() {
579		return new DeqIterator();
580		}
581
547	–	/**
548	–	* Returns an iterator over the elements in this deque in reverse
549	–	* sequential order.  The elements will be returned in order from
550	–	* last (tail) to first (head).
551	–	*
552	–	* @return an iterator over the elements in this deque in reverse
553	–	* sequence
554	–	*/
582		public Iterator<E> descendingIterator() {
583		return new DescendingIterator();
584		}
#	Line 579 | Line 606 | public class ArrayDeque<E> extends Abstr
606		}
607
608		public E next() {
582	–	E result;
609		if (cursor == fence)
610		throw new NoSuchElementException();
611	+	@SuppressWarnings("unchecked")
612	+	E result = (E) elements[cursor];
613		// This check doesn't catch all possible comodifications,
614		// but does catch the ones that corrupt traversal
615	<	if (tail != fence || (result = elements[cursor]) == null)
615	>	if (tail != fence || result == null)
616		throw new ConcurrentModificationException();
617		lastRet = cursor;
618		cursor = (cursor + 1) & (elements.length - 1);
#	Line 594 | Line 622 | public class ArrayDeque<E> extends Abstr
622		public void remove() {
623		if (lastRet < 0)
624		throw new IllegalStateException();
625	<	if (delete(lastRet)) // if left-shifted, undo increment in next()
625	>	if (delete(lastRet)) { // if left-shifted, undo increment in next()
626		cursor = (cursor - 1) & (elements.length - 1);
627	+	fence = tail;
628	+	}
629		lastRet = -1;
600	–	fence = tail;
630		}
631		}
632
604	–
633		private class DescendingIterator implements Iterator<E> {
634	<	/*
634	>	/*
635		* This class is nearly a mirror-image of DeqIterator, using
636	<	* (tail-1) instead of head for initial cursor, (head-1)
637	<	* instead of tail for fence, and elements.length instead of -1
610	<	* for sentinel. It shares the same structure, but not many
611	<	* actual lines of code.
636	>	* tail instead of head for initial cursor, and head instead of
637	>	* tail for fence.
638		*/
639	<	private int cursor = (tail - 1) & (elements.length - 1);
640	<	private int fence =  (head - 1) & (elements.length - 1);
641	<	private int lastRet = elements.length;
639	>	private int cursor = tail;
640	>	private int fence = head;
641	>	private int lastRet = -1;
642
643		public boolean hasNext() {
644		return cursor != fence;
645		}
646
647		public E next() {
622	–	E result;
648		if (cursor == fence)
649		throw new NoSuchElementException();
650	<	if (((head - 1) & (elements.length - 1)) != fence ||
651	<	(result = elements[cursor]) == null)
650	>	cursor = (cursor - 1) & (elements.length - 1);
651	>	@SuppressWarnings("unchecked")
652	>	E result = (E) elements[cursor];
653	>	if (head != fence || result == null)
654		throw new ConcurrentModificationException();
655		lastRet = cursor;
629	–	cursor = (cursor - 1) & (elements.length - 1);
656		return result;
657		}
658
659		public void remove() {
660	<	if (lastRet >= elements.length)
660	>	if (lastRet < 0)
661		throw new IllegalStateException();
662	<	if (!delete(lastRet))
662	>	if (!delete(lastRet)) {
663		cursor = (cursor + 1) & (elements.length - 1);
664	<	lastRet = elements.length;
665	<	fence = (head - 1) & (elements.length - 1);
664	>	fence = head;
665	>	}
666	>	lastRet = -1;
667		}
668		}
669
670		/**
671	<	* Returns <tt>true</tt> if this deque contains the specified element.
672	<	* More formally, returns <tt>true</tt> if and only if this deque contains
673	<	* at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
671	>	* Returns {@code true} if this deque contains the specified element.
672	>	* More formally, returns {@code true} if and only if this deque contains
673	>	* at least one element {@code e} such that {@code o.equals(e)}.
674		*
675		* @param o object to be checked for containment in this deque
676	<	* @return <tt>true</tt> if this deque contains the specified element
676	>	* @return {@code true} if this deque contains the specified element
677		*/
678		public boolean contains(Object o) {
679		if (o == null)
680		return false;
681		int mask = elements.length - 1;
682		int i = head;
683	<	E x;
683	>	Object x;
684		while ( (x = elements[i]) != null) {
685		if (o.equals(x))
686		return true;
#	Line 665 | Line 692 | public class ArrayDeque<E> extends Abstr
692		/**
693		* Removes a single instance of the specified element from this deque.
694		* If the deque does not contain the element, it is unchanged.
695	<	* More formally, removes the first element <tt>e</tt> such that
696	<	* <tt>o.equals(e)</tt> (if such an element exists).
697	<	* Returns <tt>true</tt> if this deque contained the specified element
695	>	* More formally, removes the first element {@code e} such that
696	>	* {@code o.equals(e)} (if such an element exists).
697	>	* Returns {@code true} if this deque contained the specified element
698		* (or equivalently, if this deque changed as a result of the call).
699		*
700		* <p>This method is equivalent to {@link #removeFirstOccurrence}.
701		*
702		* @param o element to be removed from this deque, if present
703	<	* @return <tt>true</tt> if this deque contained the specified element
703	>	* @return {@code true} if this deque contained the specified element
704		*/
705		public boolean remove(Object o) {
706		return removeFirstOccurrence(o);
#	Line 711 | Line 738 | public class ArrayDeque<E> extends Abstr
738		* @return an array containing all of the elements in this deque
739		*/
740		public Object[] toArray() {
741	<	return copyElements(new Object[size()]);
741	>	return copyElements(new Object[size()]);
742		}
743
744		/**
#	Line 725 | Line 752 | public class ArrayDeque<E> extends Abstr
752		* <p>If this deque fits in the specified array with room to spare
753		* (i.e., the array has more elements than this deque), the element in
754		* the array immediately following the end of the deque is set to
755	<	* <tt>null</tt>.
755	>	* {@code null}.
756		*
757		* <p>Like the {@link #toArray()} method, this method acts as bridge between
758		* array-based and collection-based APIs.  Further, this method allows
759		* precise control over the runtime type of the output array, and may,
760		* under certain circumstances, be used to save allocation costs.
761		*
762	<	* <p>Suppose <tt>x</tt> is a deque known to contain only strings.
762	>	* <p>Suppose {@code x} is a deque known to contain only strings.
763		* The following code can be used to dump the deque into a newly
764	<	* allocated array of <tt>String</tt>:
764	>	* allocated array of {@code String}:
765		*
766	<	* <pre>
740	<	*     String[] y = x.toArray(new String[0]);</pre>
766	>	*  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
767		*
768	<	* Note that <tt>toArray(new Object[0])</tt> is identical in function to
769	<	* <tt>toArray()</tt>.
768	>	* Note that {@code toArray(new Object[0])} is identical in function to
769	>	* {@code toArray()}.
770		*
771		* @param a the array into which the elements of the deque are to
772		*          be stored, if it is big enough; otherwise, a new array of the
#	Line 751 | Line 777 | public class ArrayDeque<E> extends Abstr
777		*         this deque
778		* @throws NullPointerException if the specified array is null
779		*/
780	+	@SuppressWarnings("unchecked")
781		public <T> T[] toArray(T[] a) {
782		int size = size();
783		if (a.length < size)
784		a = (T[])java.lang.reflect.Array.newInstance(
785		a.getClass().getComponentType(), size);
786	<	copyElements(a);
786	>	copyElements(a);
787		if (a.length > size)
788		a[size] = null;
789		return a;
#	Line 771 | Line 798 | public class ArrayDeque<E> extends Abstr
798		*/
799		public ArrayDeque<E> clone() {
800		try {
801	+	@SuppressWarnings("unchecked")
802		ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
803	<	// These two lines are currently faster than cloning the array:
776	<	result.elements = (E[]) new Object[elements.length];
777	<	System.arraycopy(elements, 0, result.elements, 0, elements.length);
803	>	result.elements = Arrays.copyOf(elements, elements.length);
804		return result;
779	–
805		} catch (CloneNotSupportedException e) {
806		throw new AssertionError();
807		}
808		}
809
785	–	/**
786	–	* Appease the serialization gods.
787	–	*/
810		private static final long serialVersionUID = 2340985798034038923L;
811
812		/**
813	<	* Serialize this deque.
813	>	* Saves this deque to a stream (that is, serializes it).
814		*
815	<	* @serialData The current size (<tt>int</tt>) of the deque,
815	>	* @serialData The current size ({@code int}) of the deque,
816		* followed by all of its elements (each an object reference) in
817		* first-to-last order.
818		*/
819	<	private void writeObject(ObjectOutputStream s) throws IOException {
819	>	private void writeObject(java.io.ObjectOutputStream s)
820	>	throws java.io.IOException {
821		s.defaultWriteObject();
822
823		// Write out size
824	<	int size = size();
802	<	s.writeInt(size);
824	>	s.writeInt(size());
825
826		// Write out elements in order.
805	–	int i = head;
827		int mask = elements.length - 1;
828	<	for (int j = 0; j < size; j++) {
828	>	for (int i = head; i != tail; i = (i + 1) & mask)
829		s.writeObject(elements[i]);
809	–	i = (i + 1) & mask;
810	–	}
830		}
831
832		/**
833	<	* Deserialize this deque.
833	>	* Reconstitutes this deque from a stream (that is, deserializes it).
834		*/
835	<	private void readObject(ObjectInputStream s)
836	<	throws IOException, ClassNotFoundException {
835	>	private void readObject(java.io.ObjectInputStream s)
836	>	throws java.io.IOException, ClassNotFoundException {
837		s.defaultReadObject();
838
839		// Read in size and allocate array
#	Line 825 | Line 844 | public class ArrayDeque<E> extends Abstr
844
845		// Read in all elements in the proper order.
846		for (int i = 0; i < size; i++)
847	<	elements[i] = (E)s.readObject();
847	>	elements[i] = s.readObject();
848	>	}
849
850	+	public Stream<E> stream() {
851	+	int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
852	+	return Streams.stream
853	+	(() -> new DeqSpliterator<E>(this, head, tail), flags);
854	+	}
855	+	public Stream<E> parallelStream() {
856	+	int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
857	+	return Streams.parallelStream
858	+	(() -> new DeqSpliterator<E>(this, head, tail), flags);
859		}
860	+
861	+
862	+	static final class DeqSpliterator<E> implements Spliterator<E> {
863	+	private final ArrayDeque<E> deq;
864	+	private final int fence;  // initially tail
865	+	private int index;        // current index, modified on traverse/split
866	+
867	+	/** Create new spliterator covering the given array and range */
868	+	DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
869	+	this.deq = deq; this.index = origin; this.fence = fence;
870	+	}
871	+
872	+	public DeqSpliterator<E> trySplit() {
873	+	int n = deq.elements.length;
874	+	int h = index, t = fence;
875	+	if (h != t && ((h + 1) & (n - 1)) != t) {
876	+	if (h > t)
877	+	t += n;
878	+	int m = ((h + t) >>> 1) & (n - 1);
879	+	return new DeqSpliterator<E>(deq, h, index = m);
880	+	}
881	+	return null;
882	+	}
883	+
884	+	public void forEach(Block<? super E> block) {
885	+	if (block == null)
886	+	throw new NullPointerException();
887	+	Object[] a = deq.elements;
888	+	int m = a.length - 1, f = fence, i = index;
889	+	index = f;
890	+	while (i != f) {
891	+	@SuppressWarnings("unchecked") E e = (E)a[i];
892	+	i = (i + 1) & m;
893	+	if (e == null)
894	+	throw new ConcurrentModificationException();
895	+	block.accept(e);
896	+	}
897	+	}
898	+
899	+	public boolean tryAdvance(Block<? super E> block) {
900	+	if (block == null)
901	+	throw new NullPointerException();
902	+	Object[] a = deq.elements;
903	+	int m = a.length - 1, i = index;
904	+	if (i != fence) {
905	+	@SuppressWarnings("unchecked") E e = (E)a[i];
906	+	index = (i + 1) & m;
907	+	if (e == null)
908	+	throw new ConcurrentModificationException();
909	+	block.accept(e);
910	+	return true;
911	+	}
912	+	return false;
913	+	}
914	+
915	+	// Other spliterator methods
916	+	public long estimateSize() {
917	+	int n = fence - index;
918	+	if (n < 0)
919	+	n += deq.elements.length;
920	+	return (long)n;
921	+	}
922	+	public boolean hasExactSize() { return true; }
923	+	public boolean hasExactSplits() { return true; }
924	+	}
925	+
926		}

Diff Legend

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