ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/jsr166x/ArrayDeque.java

Comparing jsr166/src/jsr166x/ArrayDeque.java (file contents):
Revision 1.1 by dl, Sun Dec 5 21:15:30 2004 UTC vs.
Revision 1.13 by jsr166, Sun Jan 18 20:17:33 2015 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.
3	>	* as explained at http://creativecommons.org/publicdomain/zero/1.0/.
4		*/
5
6		package jsr166x;    // XXX This belongs in java.util!!! XXX
7	+
8		import java.util.*; // XXX This import goes away        XXX
9		import java.io.*;
10
#	Line 13 | Line 14 | import java.io.*;
14		* usage.  They are not thread-safe; in the absence of external
15		* synchronization, they do not support concurrent access by multiple threads.
16		* Null elements are prohibited.  This class is likely to be faster than
17	<	* {@link Stack} when used as as a stack, and faster than {@link LinkedList}
17	>	* {@link Stack} when used as a stack, and faster than {@link LinkedList}
18		* when used as a queue.
19		*
20	<	* <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
20	>	* <p>Most {@code ArrayDeque} operations run in amortized constant time.
21		* Exceptions include {@link #remove(Object) remove}, {@link
22		* #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
23		* removeLastOccurrence}, {@link #contains contains }, {@link #iterator
24		* iterator.remove()}, and the bulk operations, all of which run in linear
25		* time.
26		*
27	<	* <p>The iterators returned by this class's <tt>iterator</tt> method are
27	>	* <p>The iterators returned by this class's {@code iterator} method are
28		* <i>fail-fast</i>: If the deque is modified at any time after the iterator
29		* is created, in any way except through the iterator's own remove method, the
30		* iterator will generally throw a {@link ConcurrentModificationException}.
#	Line 34 | Line 35 | import java.io.*;
35		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
36		* as it is, generally speaking, impossible to make any hard guarantees in the
37		* presence of unsynchronized concurrent modification.  Fail-fast iterators
38	<	* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
38	>	* throw {@code ConcurrentModificationException} on a best-effort basis.
39		* Therefore, it would be wrong to write a program that depended on this
40		* exception for its correctness: <i>the fail-fast behavior of iterators
41		* should be used only to detect bugs.</i>
#	Line 86 | Line 87 | public class ArrayDeque<E> extends Abstr
87		// ******  Array allocation and resizing utilities ******
88
89		/**
90	<	* Allocate empty array to hold the given number of elements.
90	>	* Allocates empty array to hold the given number of elements.
91		*
92	<	* @param numElements  the number of elements to hold.
92	>	* @param numElements  the number of elements to hold
93		*/
94	<	private void allocateElements(int numElements) {
94	>	private void allocateElements(int numElements) {
95		int initialCapacity = MIN_INITIAL_CAPACITY;
96		// Find the best power of two to hold elements.
97		// Tests "<=" because arrays aren't kept full.
#	Line 110 | Line 111 | public class ArrayDeque<E> extends Abstr
111		}
112
113		/**
114	<	* Double the capacity of this deque.  Call only when full, i.e.,
114	>	* Doubles the capacity of this deque.  Call only when full, i.e.,
115		* when head and tail have wrapped around to become equal.
116		*/
117		private void doubleCapacity() {
118	<	assert head == tail;
118	>	assert head == tail;
119		int p = head;
120		int n = elements.length;
121		int r = n - p; // number of elements to the right of p
#	Line 130 | Line 131 | public class ArrayDeque<E> extends Abstr
131		}
132
133		/**
134	<	* Copy the elements from our element array into the specified array,
134	>	* Copies the elements from our element array into the specified array,
135		* in order (from first to last element in the deque).  It is assumed
136		* that the array is large enough to hold all elements in the deque.
137		*
#	Line 188 | Line 189 | public class ArrayDeque<E> extends Abstr
189		* Inserts the specified element to the front this deque.
190		*
191		* @param e the element to insert
192	<	* @throws NullPointerException if <tt>e</tt> is null
192	>	* @throws NullPointerException if {@code e} is null
193		*/
194		public void addFirst(E e) {
195		if (e == null)
196		throw new NullPointerException();
197		elements[head = (head - 1) & (elements.length - 1)] = e;
198	<	if (head == tail)
198	>	if (head == tail)
199		doubleCapacity();
200		}
201
#	Line 204 | Line 205 | public class ArrayDeque<E> extends Abstr
205		* {@link #push}.
206		*
207		* @param e the element to insert
208	<	* @throws NullPointerException if <tt>e</tt> is null
208	>	* @throws NullPointerException if {@code e} is null
209		*/
210		public void addLast(E e) {
211		if (e == null)
#	Line 216 | Line 217 | public class ArrayDeque<E> extends Abstr
217
218		/**
219		* Retrieves and removes the first element of this deque, or
220	<	* <tt>null</tt> if this deque is empty.
220	>	* {@code null} if this deque is empty.
221		*
222	<	* @return the first element of this deque, or <tt>null</tt> if
222	>	* @return the first element of this deque, or {@code null} if
223		*     this deque is empty
224		*/
225		public E pollFirst() {
#	Line 233 | Line 234 | public class ArrayDeque<E> extends Abstr
234
235		/**
236		* Retrieves and removes the last element of this deque, or
237	<	* <tt>null</tt> if this deque is empty.
237	>	* {@code null} if this deque is empty.
238		*
239	<	* @return the last element of this deque, or <tt>null</tt> if
239	>	* @return the last element of this deque, or {@code null} if
240		*     this deque is empty
241		*/
242		public E pollLast() {
#	Line 243 | Line 244 | public class ArrayDeque<E> extends Abstr
244		E result = elements[t];
245		if (result == null)
246		return null;
247	<	elements[t] = null;
247	>	elements[t] = null;
248		tail = t;
249		return result;
250		}
#	Line 252 | Line 253 | public class ArrayDeque<E> extends Abstr
253		* Inserts the specified element to the front this deque.
254		*
255		* @param e the element to insert
256	<	* @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
257	<	* @throws NullPointerException if <tt>e</tt> is null
256	>	* @return {@code true} (as per the spec for {@link Deque#offerFirst})
257	>	* @throws NullPointerException if {@code e} is null
258		*/
259		public boolean offerFirst(E e) {
260		addFirst(e);
#	Line 264 | Line 265 | public class ArrayDeque<E> extends Abstr
265		* Inserts the specified element to the end this deque.
266		*
267		* @param e the element to insert
268	<	* @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
269	<	* @throws NullPointerException if <tt>e</tt> is null
268	>	* @return {@code true} (as per the spec for {@link Deque#offerLast})
269	>	* @throws NullPointerException if {@code e} is null
270		*/
271		public boolean offerLast(E e) {
272		addLast(e);
#	Line 274 | Line 275 | public class ArrayDeque<E> extends Abstr
275
276		/**
277		* Retrieves and removes the first element of this deque.  This method
278	<	* differs from the <tt>pollFirst</tt> method in that it throws an
278	>	* differs from the {@code pollFirst} method in that it throws an
279		* exception if this deque is empty.
280		*
281		* @return the first element of this deque
#	Line 289 | Line 290 | public class ArrayDeque<E> extends Abstr
290
291		/**
292		* Retrieves and removes the last element of this deque.  This method
293	<	* differs from the <tt>pollLast</tt> method in that it throws an
293	>	* differs from the {@code pollLast} method in that it throws an
294		* exception if this deque is empty.
295		*
296		* @return the last element of this deque
#	Line 304 | Line 305 | public class ArrayDeque<E> extends Abstr
305
306		/**
307		* Retrieves, but does not remove, the first element of this deque,
308	<	* returning <tt>null</tt> if this deque is empty.
308	>	* returning {@code null} if this deque is empty.
309		*
310	<	* @return the first element of this deque, or <tt>null</tt> if
310	>	* @return the first element of this deque, or {@code null} if
311		*     this deque is empty
312		*/
313		public E peekFirst() {
#	Line 315 | Line 316 | public class ArrayDeque<E> extends Abstr
316
317		/**
318		* Retrieves, but does not remove, the last element of this deque,
319	<	* returning <tt>null</tt> if this deque is empty.
319	>	* returning {@code null} if this deque is empty.
320		*
321	<	* @return the last element of this deque, or <tt>null</tt> if this deque
321	>	* @return the last element of this deque, or {@code null} if this deque
322		*     is empty
323		*/
324		public E peekLast() {
#	Line 326 | Line 327 | public class ArrayDeque<E> extends Abstr
327
328		/**
329		* Retrieves, but does not remove, the first element of this
330	<	* deque.  This method differs from the <tt>peek</tt> method only
330	>	* deque.  This method differs from the {@code peek} method only
331		* in that it throws an exception if this deque is empty.
332		*
333		* @return the first element of this deque
334		* @throws NoSuchElementException if this deque is empty
335		*/
336	<	public E firstElement() {
336	>	public E getFirst() {
337		E x = elements[head];
338		if (x == null)
339		throw new NoSuchElementException();
#	Line 341 | Line 342 | public class ArrayDeque<E> extends Abstr
342
343		/**
344		* Retrieves, but does not remove, the last element of this
345	<	* deque.  This method differs from the <tt>peek</tt> method only
345	>	* deque.  This method differs from the {@code peek} method only
346		* in that it throws an exception if this deque is empty.
347		*
348		* @return the last element of this deque
349		* @throws NoSuchElementException if this deque is empty
350		*/
351	<	public E lastElement() {
351	>	public E getLast() {
352		E x = elements[(tail - 1) & (elements.length - 1)];
353		if (x == null)
354		throw new NoSuchElementException();
#	Line 360 | Line 361 | public class ArrayDeque<E> extends Abstr
361		* does not contain the element, it is unchanged.
362		*
363		* @param e element to be removed from this deque, if present
364	<	* @return <tt>true</tt> if the deque contained the specified element
364	>	* @return {@code true} if the deque contained the specified element
365		*/
366		public boolean removeFirstOccurrence(Object e) {
367		if (e == null)
#	Line 384 | Line 385 | public class ArrayDeque<E> extends Abstr
385		* does not contain the element, it is unchanged.
386		*
387		* @param e element to be removed from this deque, if present
388	<	* @return <tt>true</tt> if the deque contained the specified element
388	>	* @return {@code true} if the deque contained the specified element
389		*/
390		public boolean removeLastOccurrence(Object e) {
391		if (e == null)
#	Line 410 | Line 411 | public class ArrayDeque<E> extends Abstr
411		* <p>This method is equivalent to {@link #offerLast}.
412		*
413		* @param e the element to insert
414	<	* @return <tt>true</tt> (as per the spec for {@link Queue#offer})
415	<	* @throws NullPointerException if <tt>e</tt> is null
414	>	* @return {@code true} (as per the spec for {@link Queue#offer})
415	>	* @throws NullPointerException if {@code e} is null
416		*/
417		public boolean offer(E e) {
418		return offerLast(e);
#	Line 423 | Line 424 | public class ArrayDeque<E> extends Abstr
424		* <p>This method is equivalent to {@link #addLast}.
425		*
426		* @param e the element to insert
427	<	* @return <tt>true</tt> (as per the spec for {@link Collection#add})
428	<	* @throws NullPointerException if <tt>e</tt> is null
427	>	* @return {@code true} (as per the spec for {@link Collection#add})
428	>	* @throws NullPointerException if {@code e} is null
429		*/
430		public boolean add(E e) {
431		addLast(e);
#	Line 433 | Line 434 | public class ArrayDeque<E> extends Abstr
434
435		/**
436		* Retrieves and removes the head of the queue represented by
437	<	* this deque, or <tt>null</tt> if this deque is empty.  In other words,
438	<	* retrieves and removes the first element of this deque, or <tt>null</tt>
437	>	* this deque, or {@code null} if this deque is empty.  In other words,
438	>	* retrieves and removes the first element of this deque, or {@code null}
439		* if this deque is empty.
440		*
441		* <p>This method is equivalent to {@link #pollFirst}.
442		*
443	<	* @return the first element of this deque, or <tt>null</tt> if
443	>	* @return the first element of this deque, or {@code null} if
444		*     this deque is empty
445		*/
446		public E poll() {
#	Line 448 | Line 449 | public class ArrayDeque<E> extends Abstr
449
450		/**
451		* Retrieves and removes the head of the queue represented by this deque.
452	<	* This method differs from the <tt>poll</tt> method in that it throws an
452	>	* This method differs from the {@code poll} method in that it throws an
453		* exception if this deque is empty.
454		*
455		* <p>This method is equivalent to {@link #removeFirst}.
#	Line 462 | Line 463 | public class ArrayDeque<E> extends Abstr
463
464		/**
465		* Retrieves, but does not remove, the head of the queue represented by
466	<	* this deque, returning <tt>null</tt> if this deque is empty.
466	>	* this deque, returning {@code null} if this deque is empty.
467		*
468	<	* <p>This method is equivalent to {@link #peekFirst}
468	>	* <p>This method is equivalent to {@link #peekFirst}.
469		*
470		* @return the head of the queue represented by this deque, or
471	<	*     <tt>null</tt> if this deque is empty
471	>	*     {@code null} if this deque is empty
472		*/
473		public E peek() {
474		return peekFirst();
#	Line 475 | Line 476 | public class ArrayDeque<E> extends Abstr
476
477		/**
478		* Retrieves, but does not remove, the head of the queue represented by
479	<	* this deque.  This method differs from the <tt>peek</tt> method only in
479	>	* this deque.  This method differs from the {@code peek} method only in
480		* that it throws an exception if this deque is empty.
481		*
482	<	* <p>This method is equivalent to {@link #firstElement}
482	>	* <p>This method is equivalent to {@link #getFirst}.
483		*
484		* @return the head of the queue represented by this deque
485		* @throws NoSuchElementException if this deque is empty
486		*/
487		public E element() {
488	<	return firstElement();
488	>	return getFirst();
489		}
490
491		// *** Stack methods ***
#	Line 496 | Line 497 | public class ArrayDeque<E> extends Abstr
497		* <p>This method is equivalent to {@link #addFirst}.
498		*
499		* @param e the element to push
500	<	* @throws NullPointerException if <tt>e</tt> is null
500	>	* @throws NullPointerException if {@code e} is null
501		*/
502		public void push(E e) {
503		addFirst(e);
#	Line 504 | Line 505 | public class ArrayDeque<E> extends Abstr
505
506		/**
507		* Pops an element from the stack represented by this deque.  In other
508	<	* words, removes and returns the the first element of this deque.
508	>	* words, removes and returns the first element of this deque.
509		*
510		* <p>This method is equivalent to {@link #removeFirst()}.
511		*
#	Line 517 | Line 518 | public class ArrayDeque<E> extends Abstr
518		}
519
520		/**
521	<	* Remove the element at the specified position in the elements array,
521	>	* Removes the element at the specified position in the elements array,
522		* adjusting head, tail, and size as necessary.  This can result in
523		* motion of elements backwards or forwards in the array.
524		*
525		* <p>This method is called delete rather than remove to emphasize the
526		* that that its semantics differ from those of List.remove(int).
527	<	*
527	>	*
528		* @return true if elements moved backwards
529		*/
530		private boolean delete(int i) {
#	Line 555 | Line 556 | public class ArrayDeque<E> extends Abstr
556		}
557
558		/**
559	<	* Returns <tt>true</tt> if this collection contains no elements.<p>
559	>	* Returns {@code true} if this collection contains no elements.
560		*
561	<	* @return <tt>true</tt> if this collection contains no elements.
561	>	* @return {@code true} if this collection contains no elements
562		*/
563		public boolean isEmpty() {
564		return head == tail;
#	Line 568 | Line 569 | public class ArrayDeque<E> extends Abstr
569		* will be ordered from first (head) to last (tail).  This is the same
570		* order that elements would be dequeued (via successive calls to
571		* {@link #remove} or popped (via successive calls to {@link #pop}).
572	<	*
573	<	* @return an <tt>Iterator</tt> over the elements in this deque
572	>	*
573	>	* @return an {@code Iterator} over the elements in this deque
574		*/
575		public Iterator<E> iterator() {
576		return new DeqIterator();
#	Line 621 | Line 622 | public class ArrayDeque<E> extends Abstr
622		}
623
624		/**
625	<	* Returns <tt>true</tt> if this deque contains the specified
626	<	* element.  More formally, returns <tt>true</tt> if and only if this
627	<	* deque contains at least one element <tt>e</tt> such that
628	<	* <tt>e.equals(o)</tt>.
625	>	* Returns {@code true} if this deque contains the specified
626	>	* element.  More formally, returns {@code true} if and only if this
627	>	* deque contains at least one element {@code e} such that
628	>	* {@code e.equals(o)}.
629		*
630		* @param o object to be checked for containment in this deque
631	<	* @return <tt>true</tt> if this deque contains the specified element
631	>	* @return {@code true} if this deque contains the specified element
632		*/
633		public boolean contains(Object o) {
634		if (o == null)
#	Line 648 | Line 649 | public class ArrayDeque<E> extends Abstr
649		* This method is equivalent to {@link #removeFirstOccurrence}.
650		*
651		* @param e element to be removed from this deque, if present
652	<	* @return <tt>true</tt> if this deque contained the specified element
652	>	* @return {@code true} if this deque contained the specified element
653		*/
654		public boolean remove(Object e) {
655		return removeFirstOccurrence(e);
#	Line 667 | Line 668 | public class ArrayDeque<E> extends Abstr
668		do {
669		elements[i] = null;
670		i = (i + 1) & mask;
671	<	} while(i != t);
671	>	} while (i != t);
672		}
673		}
674
#	Line 676 | Line 677 | public class ArrayDeque<E> extends Abstr
677		* in the correct order.
678		*
679		* @return an array containing all of the elements in this list
680	<	*         in the correct order
680	>	*         in the correct order
681		*/
682		public Object[] toArray() {
683	<	return copyElements(new Object[size()]);
683	>	return copyElements(new Object[size()]);
684		}
685
686		/**
#	Line 691 | Line 692 | public class ArrayDeque<E> extends Abstr
692		*
693		* <p>If the deque fits in the specified array with room to spare (i.e.,
694		* the array has more elements than the deque), the element in the array
695	<	* immediately following the end of the collection is set to <tt>null</tt>.
695	>	* immediately following the end of the collection is set to {@code null}.
696		*
697		* @param a the array into which the elements of the deque are to
698	<	*          be stored, if it is big enough; otherwise, a new array of the
699	<	*          same runtime type is allocated for this purpose
698	>	*          be stored, if it is big enough; otherwise, a new array of the
699	>	*          same runtime type is allocated for this purpose
700		* @return an array containing the elements of the deque
701		* @throws ArrayStoreException if the runtime type of a is not a supertype
702		*         of the runtime type of every element in this deque
#	Line 705 | Line 706 | public class ArrayDeque<E> extends Abstr
706		if (a.length < size)
707		a = (T[])java.lang.reflect.Array.newInstance(
708		a.getClass().getComponentType(), size);
709	<	copyElements(a);
709	>	copyElements(a);
710		if (a.length > size)
711		a[size] = null;
712		return a;
#	Line 719 | Line 720 | public class ArrayDeque<E> extends Abstr
720		* @return a copy of this deque
721		*/
722		public ArrayDeque<E> clone() {
723	<	try {
723	>	try {
724		ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
725		// These two lines are currently faster than cloning the array:
726		result.elements = (E[]) new Object[elements.length];
727		System.arraycopy(elements, 0, result.elements, 0, elements.length);
728		return result;
729
730	<	} catch (CloneNotSupportedException e) {
730	>	} catch (CloneNotSupportedException e) {
731		throw new AssertionError();
732		}
733		}
#	Line 737 | Line 738 | public class ArrayDeque<E> extends Abstr
738		private static final long serialVersionUID = 2340985798034038923L;
739
740		/**
741	<	* Serialize this deque.
741	>	* Serializes this deque.
742		*
743	<	* @serialData The current size (<tt>int</tt>) of the deque,
743	>	* @serialData The current size ({@code int}) of the deque,
744		* followed by all of its elements (each an object reference) in
745		* first-to-last order.
746		*/
#	Line 760 | Line 761 | public class ArrayDeque<E> extends Abstr
761		}
762
763		/**
764	<	* Deserialize this deque.
764	>	* Deserializes this deque.
765		*/
766		private void readObject(ObjectInputStream s)
767		throws IOException, ClassNotFoundException {

Diff Legend

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