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.40 by jsr166, Sun Feb 26 22:43:03 2012 UTC vs.
Revision 1.41 by dl, Wed Jan 16 15:06:10 2013 UTC

#	Line 1 | Line 1
1		/*
2	+	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3	+	*
4	+	* This code is free software; you can redistribute it and/or modify it
5	+	* under the terms of the GNU General Public License version 2 only, as
6	+	* published by the Free Software Foundation.  Oracle designates this
7	+	* particular file as subject to the "Classpath" exception as provided
8	+	* by Oracle in the LICENSE file that accompanied this code.
9	+	*
10	+	* This code is distributed in the hope that it will be useful, but WITHOUT
11	+	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12	+	* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
13	+	* version 2 for more details (a copy is included in the LICENSE file that
14	+	* accompanied this code).
15	+	*
16	+	* You should have received a copy of the GNU General Public License version
17	+	* 2 along with this work; if not, write to the Free Software Foundation,
18	+	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19	+	*
20	+	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21	+	* or visit www.oracle.com if you need additional information or have any
22	+	* questions.
23	+	*/
24	+
25	+	/*
26	+	* This file is available under and governed by the GNU General Public
27	+	* License version 2 only, as published by the Free Software Foundation.
28	+	* However, the following notice accompanied the original version of this
29	+	* file:
30	+	*
31		* Written by Josh Bloch of Google Inc. and released to the public domain,
32		* as explained at http://creativecommons.org/publicdomain/zero/1.0/.
33		*/
34
35		package java.util;
36	+	import java.util.Spliterator;
37	+	import java.util.stream.Stream;
38	+	import java.util.stream.Streams;
39	+	import java.util.function.Block;
40
41		/**
42		* Resizable-array implementation of the {@link Deque} interface.  Array
#	Line 14 | Line 47 | package java.util;
47		* {@link Stack} when used as a stack, and faster than {@link LinkedList}
48		* when used as a queue.
49		*
50	<	* <p>Most {@code ArrayDeque} operations run in amortized constant time.
51	<	* Exceptions include
52	<	* {@link #remove(Object) remove},
53	<	* {@link #removeFirstOccurrence removeFirstOccurrence},
54	<	* {@link #removeLastOccurrence removeLastOccurrence},
55	<	* {@link #contains contains},
56	<	* {@link #iterator iterator.remove()},
57	<	* and the bulk operations, all of which run in linear time.
58	<	*
59	<	* <p>The iterators returned by this class's {@link #iterator() iterator}
60	<	* method are <em>fail-fast</em>: If the deque is modified at any time after
28	<	* the iterator is created, in any way except through the iterator's own
29	<	* {@code remove} method, the iterator will generally throw a {@link
50	>	* <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
51	>	* Exceptions include {@link #remove(Object) remove}, {@link
52	>	* #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
53	>	* removeLastOccurrence}, {@link #contains contains}, {@link #iterator
54	>	* iterator.remove()}, and the bulk operations, all of which run in linear
55	>	* time.
56	>	*
57	>	* <p>The iterators returned by this class's <tt>iterator</tt> method are
58	>	* <i>fail-fast</i>: If the deque is modified at any time after the iterator
59	>	* is created, in any way except through the iterator's own <tt>remove</tt>
60	>	* method, the iterator will generally throw a {@link
61		* ConcurrentModificationException}.  Thus, in the face of concurrent
62		* modification, the iterator fails quickly and cleanly, rather than risking
63		* arbitrary, non-deterministic behavior at an undetermined time in the
#	Line 35 | Line 66 | package java.util;
66		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
67		* as it is, generally speaking, impossible to make any hard guarantees in the
68		* presence of unsynchronized concurrent modification.  Fail-fast iterators
69	<	* throw {@code ConcurrentModificationException} on a best-effort basis.
69	>	* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
70		* Therefore, it would be wrong to write a program that depended on this
71		* exception for its correctness: <i>the fail-fast behavior of iterators
72		* should be used only to detect bugs.</i>
#	Line 65 | Line 96 | public class ArrayDeque<E> extends Abstr
96		* other.  We also guarantee that all array cells not holding
97		* deque elements are always null.
98		*/
99	<	private transient Object[] elements;
99	>	transient Object[] elements; // non-private to simplify nested class access
100
101		/**
102		* The index of the element at the head of the deque (which is the
103		* element that would be removed by remove() or pop()); or an
104		* arbitrary number equal to tail if the deque is empty.
105		*/
106	<	private transient int head;
106	>	transient int head;
107
108		/**
109		* The index at which the next element would be added to the tail
110		* of the deque (via addLast(E), add(E), or push(E)).
111		*/
112	<	private transient int tail;
112	>	transient int tail;
113
114		/**
115		* The minimum capacity that we'll use for a newly created deque.
#	Line 843 | Line 874 | public class ArrayDeque<E> extends Abstr
874		for (int i = 0; i < size; i++)
875		elements[i] = s.readObject();
876		}
877	+
878	+	public Stream<E> stream() {
879	+	int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
880	+	return Streams.stream
881	+	(() -> new DeqSpliterator<E>(this, head, tail), flags);
882	+	}
883	+	public Stream<E> parallelStream() {
884	+	int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_SIZED;
885	+	return Streams.parallelStream
886	+	(() -> new DeqSpliterator<E>(this, head, tail), flags);
887	+	}
888	+
889	+
890	+	static final class DeqSpliterator<E> implements Spliterator<E>, Iterator<E> {
891	+	private final ArrayDeque<E> deq;
892	+	private final Object[] array;
893	+	private final int fence;  // initially tail
894	+	private int index;        // current index, modified on traverse/split
895	+
896	+	/** Create new spliterator covering the given array and range */
897	+	DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
898	+	this.deq = deq; this.array = deq.elements;
899	+	this.index = origin; this.fence = fence;
900	+	}
901	+
902	+	public DeqSpliterator<E> trySplit() {
903	+	int n = array.length;
904	+	int h = index, t = fence;
905	+	if (h != t && ((h + 1) & (n - 1)) != t) {
906	+	if (h > t)
907	+	t += n;
908	+	int m = ((h + t) >>> 1) & (n - 1);
909	+	return new DeqSpliterator<E>(deq, h, index = m);
910	+	}
911	+	return null;
912	+	}
913	+
914	+	@SuppressWarnings("unchecked")
915	+	public void forEach(Block<? super E> block) {
916	+	if (block == null)
917	+	throw new NullPointerException();
918	+	Object[] a = array;
919	+	if (a != deq.elements)
920	+	throw new ConcurrentModificationException();
921	+	int m = a.length - 1, f = fence, i = index;
922	+	index = f;
923	+	while (i != f) {
924	+	Object e = a[i];
925	+	if (e == null)
926	+	throw new ConcurrentModificationException();
927	+	block.accept((E)e);
928	+	i = (i + 1) & m;
929	+	}
930	+	}
931	+
932	+	@SuppressWarnings("unchecked")
933	+	public boolean tryAdvance(Block<? super E> block) {
934	+	if (block == null)
935	+	throw new NullPointerException();
936	+	Object[] a = array;
937	+	if (a != deq.elements)
938	+	throw new ConcurrentModificationException();
939	+	int m = a.length - 1, i = index;
940	+	if (i != fence) {
941	+	Object e = a[i];
942	+	if (e == null)
943	+	throw new ConcurrentModificationException();
944	+	block.accept((E)e);
945	+	index = (i + 1) & m;
946	+	return true;
947	+	}
948	+	return false;
949	+	}
950	+
951	+	// Iterator support
952	+	public Iterator<E> iterator() {
953	+	return this;
954	+	}
955	+
956	+	public boolean hasNext() {
957	+	return index >= 0 && index != fence;
958	+	}
959	+
960	+	@SuppressWarnings("unchecked")
961	+	public E next() {
962	+	if (index < 0 || index == fence)
963	+	throw new NoSuchElementException();
964	+	Object[] a = array;
965	+	if (a != deq.elements)
966	+	throw new ConcurrentModificationException();
967	+	Object e = a[index];
968	+	if (e == null)
969	+	throw new ConcurrentModificationException();
970	+	index = (index + 1) & (a.length - 1);
971	+	return (E) e;
972	+	}
973	+
974	+	public void remove() { throw new UnsupportedOperationException(); }
975	+
976	+	// Other spliterator methods
977	+	public long estimateSize() {
978	+	int n = fence - index;
979	+	if (n < 0)
980	+	n += array.length;
981	+	return (long)n;
982	+	}
983	+	public boolean hasExactSize() { return true; }
984	+	public boolean hasExactSplits() { return true; }
985	+	}
986	+
987		}

Diff Legend

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