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.4 by dl, Tue Mar 8 19:07:39 2005 UTC vs.
Revision 1.8 by jsr166, Mon May 2 04:19:58 2005 UTC

#	Line 24 | Line 24 | import java.io.*;
24		*
25		* <p>The iterators returned by this class's <tt>iterator</tt> method are
26		* <i>fail-fast</i>: If the deque is modified at any time after the iterator
27	<	* is created, in any way except through the iterator's own remove method, the
28	<	* iterator will generally throw a {@link ConcurrentModificationException}.
29	<	* Thus, in the face of concurrent modification, the iterator fails quickly
30	<	* and cleanly, rather than risking arbitrary, non-deterministic behavior at
31	<	* an undetermined time in the future.
27	>	* is created, in any way except through the iterator's own <tt>remove</tt>
28	>	* method, the iterator will generally throw a {@link
29	>	* ConcurrentModificationException}.  Thus, in the face of concurrent
30	>	* modification, the iterator fails quickly and cleanly, rather than risking
31	>	* arbitrary, non-deterministic behavior at an undetermined time in the
32	>	* future.
33		*
34		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
35		* as it is, generally speaking, impossible to make any hard guarantees in the
36		* presence of unsynchronized concurrent modification.  Fail-fast iterators
37	<	* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
37	>	* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
38		* Therefore, it would be wrong to write a program that depended on this
39		* exception for its correctness: <i>the fail-fast behavior of iterators
40		* should be used only to detect bugs.</i>
#	Line 89 | Line 90 | public class ArrayDeque<E> extends Abstr
90		*
91		* @param numElements  the number of elements to hold.
92		*/
93	<	private void allocateElements(int numElements) {
93	>	private void allocateElements(int numElements) {
94		int initialCapacity = MIN_INITIAL_CAPACITY;
95		// Find the best power of two to hold elements.
96		// Tests "<=" because arrays aren't kept full.
#	Line 113 | Line 114 | public class ArrayDeque<E> extends Abstr
114		* when head and tail have wrapped around to become equal.
115		*/
116		private void doubleCapacity() {
117	<	assert head == tail;
117	>	assert head == tail;
118		int p = head;
119		int n = elements.length;
120		int r = n - p; // number of elements to the right of p
#	Line 129 | Line 130 | public class ArrayDeque<E> extends Abstr
130		}
131
132		/**
133	<	* Copy the elements from our element array into the specified array,
133	>	* Copies the elements from our element array into the specified array,
134		* in order (from first to last element in the deque).  It is assumed
135		* that the array is large enough to hold all elements in the deque.
136		*
#	Line 184 | Line 185 | public class ArrayDeque<E> extends Abstr
185		// terms of these.
186
187		/**
188	<	* Inserts the specified element to the front this deque.
188	>	* Inserts the specified element at the front of this deque.
189		*
190		* @param e the element to insert
191		* @throws NullPointerException if <tt>e</tt> is null
#	Line 193 | Line 194 | public class ArrayDeque<E> extends Abstr
194		if (e == null)
195		throw new NullPointerException();
196		elements[head = (head - 1) & (elements.length - 1)] = e;
197	<	if (head == tail)
197	>	if (head == tail)
198		doubleCapacity();
199		}
200
201		/**
202	<	* Inserts the specified element to the end this deque.
202	>	* Inserts the specified element at the end of this deque.
203		* This method is equivalent to {@link Collection#add} and
204		* {@link #push}.
205		*
#	Line 242 | Line 243 | public class ArrayDeque<E> extends Abstr
243		E result = elements[t];
244		if (result == null)
245		return null;
246	<	elements[t] = null;
246	>	elements[t] = null;
247		tail = t;
248		return result;
249		}
250
251		/**
252	<	* Inserts the specified element to the front this deque.
252	>	* Inserts the specified element at the front of this deque.
253		*
254		* @param e the element to insert
255		* @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
#	Line 260 | Line 261 | public class ArrayDeque<E> extends Abstr
261		}
262
263		/**
264	<	* Inserts the specified element to the end this deque.
264	>	* Inserts the specified element at the end of this deque.
265		*
266		* @param e the element to insert
267		* @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
#	Line 273 | Line 274 | public class ArrayDeque<E> extends Abstr
274
275		/**
276		* Retrieves and removes the first element of this deque.  This method
277	<	* differs from the <tt>pollFirst</tt> method in that it throws an
277	>	* differs from the {@link #pollFirst} method only in that it throws an
278		* exception if this deque is empty.
279		*
280		* @return the first element of this deque
#	Line 288 | Line 289 | public class ArrayDeque<E> extends Abstr
289
290		/**
291		* Retrieves and removes the last element of this deque.  This method
292	<	* differs from the <tt>pollLast</tt> method in that it throws an
292	>	* differs from the {@link #pollLast} method only in that it throws an
293		* exception if this deque is empty.
294		*
295		* @return the last element of this deque
#	Line 325 | Line 326 | public class ArrayDeque<E> extends Abstr
326
327		/**
328		* Retrieves, but does not remove, the first element of this
329	<	* deque.  This method differs from the <tt>peek</tt> method only
329	>	* deque.  This method differs from the {@link #peekFirst} method only
330		* in that it throws an exception if this deque is empty.
331		*
332		* @return the first element of this deque
#	Line 340 | Line 341 | public class ArrayDeque<E> extends Abstr
341
342		/**
343		* Retrieves, but does not remove, the last element of this
344	<	* deque.  This method differs from the <tt>peek</tt> method only
344	>	* deque.  This method differs from the {@link #peekLast} method only
345		* in that it throws an exception if this deque is empty.
346		*
347		* @return the last element of this deque
#	Line 355 | Line 356 | public class ArrayDeque<E> extends Abstr
356
357		/**
358		* Removes the first occurrence of the specified element in this
359	<	* deque (when traversing the deque from head to tail).  If the deque
360	<	* does not contain the element, it is unchanged.
359	>	* deque (when traversing the deque from head to tail).  More
360	>	* formally, removes the first element e such that (o==null ?
361	>	* e==null : o.equals(e)). If the deque does not contain the
362	>	* element, it is unchanged.
363		*
364	<	* @param e element to be removed from this deque, if present
364	>	* @param o element to be removed from this deque, if present
365		* @return <tt>true</tt> if the deque contained the specified element
366		*/
367	<	public boolean removeFirstOccurrence(Object e) {
368	<	if (e == null)
367	>	public boolean removeFirstOccurrence(Object o) {
368	>	if (o == null)
369		return false;
370		int mask = elements.length - 1;
371		int i = head;
372		E x;
373		while ( (x = elements[i]) != null) {
374	<	if (e.equals(x)) {
374	>	if (o.equals(x)) {
375		delete(i);
376		return true;
377		}
#	Line 379 | Line 382 | public class ArrayDeque<E> extends Abstr
382
383		/**
384		* Removes the last occurrence of the specified element in this
385	<	* deque (when traversing the deque from head to tail).  If the deque
385	>	* deque (when traversing the deque from head to tail). More
386	>	* formally, removes the last element e such that (o==null ?
387	>	* e==null : o.equals(e)). If the deque
388		* does not contain the element, it is unchanged.
389		*
390	<	* @param e element to be removed from this deque, if present
390	>	* @param o element to be removed from this deque, if present
391		* @return <tt>true</tt> if the deque contained the specified element
392		*/
393	<	public boolean removeLastOccurrence(Object e) {
394	<	if (e == null)
393	>	public boolean removeLastOccurrence(Object o) {
394	>	if (o == null)
395		return false;
396		int mask = elements.length - 1;
397		int i = (tail - 1) & mask;
398		E x;
399		while ( (x = elements[i]) != null) {
400	<	if (e.equals(x)) {
400	>	if (o.equals(x)) {
401		delete(i);
402		return true;
403		}
#	Line 404 | Line 409 | public class ArrayDeque<E> extends Abstr
409		// *** Queue methods ***
410
411		/**
412	<	* Inserts the specified element to the end of this deque.
412	>	* Inserts the specified element at the end of this deque.
413		*
414		* <p>This method is equivalent to {@link #offerLast}.
415		*
#	Line 417 | Line 422 | public class ArrayDeque<E> extends Abstr
422		}
423
424		/**
425	<	* Inserts the specified element to the end of this deque.
425	>	* Inserts the specified element at the end of this deque.
426		*
427		* <p>This method is equivalent to {@link #addLast}.
428		*
#	Line 447 | Line 452 | public class ArrayDeque<E> extends Abstr
452
453		/**
454		* Retrieves and removes the head of the queue represented by this deque.
455	<	* This method differs from the <tt>poll</tt> method in that it throws an
456	<	* exception if this deque is empty.
455	>	* This method differs from the {@link #poll} method only in that it
456	>	* throws an exception if this deque is empty.
457		*
458		* <p>This method is equivalent to {@link #removeFirst}.
459		*
#	Line 463 | Line 468 | public class ArrayDeque<E> extends Abstr
468		* Retrieves, but does not remove, the head of the queue represented by
469		* this deque, returning <tt>null</tt> if this deque is empty.
470		*
471	<	* <p>This method is equivalent to {@link #peekFirst}
471	>	* <p>This method is equivalent to {@link #peekFirst}.
472		*
473		* @return the head of the queue represented by this deque, or
474		*     <tt>null</tt> if this deque is empty
#	Line 474 | Line 479 | public class ArrayDeque<E> extends Abstr
479
480		/**
481		* Retrieves, but does not remove, the head of the queue represented by
482	<	* this deque.  This method differs from the <tt>peek</tt> method only in
482	>	* this deque.  This method differs from the {@link #peek} method only in
483		* that it throws an exception if this deque is empty.
484		*
485	<	* <p>This method is equivalent to {@link #getFirst}
485	>	* <p>This method is equivalent to {@link #getFirst}.
486		*
487		* @return the head of the queue represented by this deque
488		* @throws NoSuchElementException if this deque is empty
#	Line 490 | Line 495 | public class ArrayDeque<E> extends Abstr
495
496		/**
497		* Pushes an element onto the stack represented by this deque.  In other
498	<	* words, inserts the element to the front this deque.
498	>	* words, inserts the element at the front of this deque.
499		*
500		* <p>This method is equivalent to {@link #addFirst}.
501		*
#	Line 516 | Line 521 | public class ArrayDeque<E> extends Abstr
521		}
522
523		/**
524	<	* Remove the element at the specified position in the elements array,
524	>	* Removes the element at the specified position in the elements array,
525		* adjusting head, tail, and size as necessary.  This can result in
526		* motion of elements backwards or forwards in the array.
527		*
528	<	* <p>This method is called delete rather than remove to emphasize
528	>	* <p>This method is called delete rather than remove to emphasize
529		* that its semantics differ from those of List.remove(int).
530	<	*
530	>	*
531		* @return true if elements moved backwards
532		*/
533		private boolean delete(int i) {
#	Line 554 | Line 559 | public class ArrayDeque<E> extends Abstr
559		}
560
561		/**
562	<	* Returns <tt>true</tt> if this collection contains no elements.<p>
562	>	* Returns <tt>true</tt> if this deque contains no elements.<p>
563		*
564	<	* @return <tt>true</tt> if this collection contains no elements.
564	>	* @return <tt>true</tt> if this deque contains no elements.
565		*/
566		public boolean isEmpty() {
567		return head == tail;
#	Line 567 | Line 572 | public class ArrayDeque<E> extends Abstr
572		* will be ordered from first (head) to last (tail).  This is the same
573		* order that elements would be dequeued (via successive calls to
574		* {@link #remove} or popped (via successive calls to {@link #pop}).
575	<	*
575	>	*
576		* @return an <tt>Iterator</tt> over the elements in this deque
577		*/
578		public Iterator<E> iterator() {
#	Line 655 | Line 660 | public class ArrayDeque<E> extends Abstr
660
661		/**
662		* Removes all of the elements from this deque.
663	+	* The deque will be empty after this call returns.
664		*/
665		public void clear() {
666		int h = head;
#	Line 671 | Line 677 | public class ArrayDeque<E> extends Abstr
677		}
678
679		/**
680	<	* Returns an array containing all of the elements in this list
680	>	* Returns an array containing all of the elements in this deque
681		* in the correct order.
682		*
683	<	* @return an array containing all of the elements in this list
683	>	* @return an array containing all of the elements in this deque
684		*         in the correct order
685		*/
686		public Object[] toArray() {
#	Line 718 | Line 724 | public class ArrayDeque<E> extends Abstr
724		* @return a copy of this deque
725		*/
726		public ArrayDeque<E> clone() {
727	<	try {
727	>	try {
728		ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
729		// These two lines are currently faster than cloning the array:
730		result.elements = (E[]) new Object[elements.length];
731		System.arraycopy(elements, 0, result.elements, 0, elements.length);
732		return result;
733
734	<	} catch (CloneNotSupportedException e) {
734	>	} catch (CloneNotSupportedException e) {
735		throw new AssertionError();
736		}
737		}

Diff Legend

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