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.9 by jsr166, Mon May 16 06:16:12 2005 UTC vs.
Revision 1.24 by dl, Sat Sep 17 13:21:19 2005 UTC

#	Line 4 | Line 4
4		*/
5
6		package java.util;
7	+	import java.util.*; // for javadoc (till 6280605 is fixed)
8		import java.io.*;
9
10		/**
#	Line 202 | Line 203 | public class ArrayDeque<E> extends Abstr
203
204		/**
205		* Inserts the specified element at the end of this deque.
206	<	* This method is equivalent to {@link #add} and {@link #push}.
206	>	*
207	>	* <p>This method is equivalent to {@link #add}.
208		*
209		* @param e the element to add
210		* @throws NullPointerException if the specified element is null
#	Line 219 | Line 221 | public class ArrayDeque<E> extends Abstr
221		* Inserts the specified element at the front of this deque.
222		*
223		* @param e the element to add
224	<	* @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
224	>	* @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
225		* @throws NullPointerException if the specified element is null
226		*/
227		public boolean offerFirst(E e) {
#	Line 231 | Line 233 | public class ArrayDeque<E> extends Abstr
233		* Inserts the specified element at the end of this deque.
234		*
235		* @param e the element to add
236	<	* @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
236	>	* @return <tt>true</tt> (as specified by {@link Deque#offerLast})
237		* @throws NullPointerException if the specified element is null
238		*/
239		public boolean offerLast(E e) {
#	Line 313 | Line 315 | public class ArrayDeque<E> extends Abstr
315		* If the deque does not contain the element, it is unchanged.
316		* More formally, removes the first element <tt>e</tt> such that
317		* <tt>o.equals(e)</tt> (if such an element exists).
318	<	* Returns true if this deque contained the specified element (or
319	<	* equivalently, if this deque changed as a result of the call).
318	>	* Returns <tt>true</tt> if this deque contained the specified element
319	>	* (or equivalently, if this deque changed as a result of the call).
320		*
321		* @param o element to be removed from this deque, if present
322		* @return <tt>true</tt> if the deque contained the specified element
#	Line 341 | Line 343 | public class ArrayDeque<E> extends Abstr
343		* If the deque does not contain the element, it is unchanged.
344		* More formally, removes the last element <tt>e</tt> such that
345		* <tt>o.equals(e)</tt> (if such an element exists).
346	<	* Returns true if this deque contained the specified element (or
347	<	* equivalently, if this deque changed as a result of the call).
346	>	* Returns <tt>true</tt> if this deque contained the specified element
347	>	* (or equivalently, if this deque changed as a result of the call).
348		*
349		* @param o element to be removed from this deque, if present
350		* @return <tt>true</tt> if the deque contained the specified element
#	Line 371 | Line 373 | public class ArrayDeque<E> extends Abstr
373		* <p>This method is equivalent to {@link #addLast}.
374		*
375		* @param e the element to add
376	<	* @return <tt>true</tt> (as per the spec for {@link Collection#add})
376	>	* @return <tt>true</tt> (as specified by {@link Collection#add})
377		* @throws NullPointerException if the specified element is null
378		*/
379		public boolean add(E e) {
#	Line 385 | Line 387 | public class ArrayDeque<E> extends Abstr
387		* <p>This method is equivalent to {@link #offerLast}.
388		*
389		* @param e the element to add
390	<	* @return <tt>true</tt> (as per the spec for {@link Queue#offer})
390	>	* @return <tt>true</tt> (as specified by {@link Queue#offer})
391		* @throws NullPointerException if the specified element is null
392		*/
393		public boolean offer(E e) {
#	Line 394 | Line 396 | public class ArrayDeque<E> extends Abstr
396
397		/**
398		* Retrieves and removes the head of the queue represented by this deque.
399	<	* This method differs from {@link #poll} only in that it throws an
399	>	*
400	>	* This method differs from {@link #poll poll} only in that it throws an
401		* exception if this deque is empty.
402		*
403		* <p>This method is equivalent to {@link #removeFirst}.
#	Line 422 | Line 425 | public class ArrayDeque<E> extends Abstr
425
426		/**
427		* Retrieves, but does not remove, the head of the queue represented by
428	<	* this deque.  This method differs from {@link #peek} only in that it
429	<	* throws an exception if this deque is empty.
428	>	* this deque.  This method differs from {@link #peek peek} only in
429	>	* that it throws an exception if this deque is empty.
430		*
431		* <p>This method is equivalent to {@link #getFirst}.
432		*
#	Line 487 | Line 490 | public class ArrayDeque<E> extends Abstr
490		* @return true if elements moved backwards
491		*/
492		private boolean delete(int i) {
493	<	int mask = elements.length - 1;
493	>	final E[] elements = this.elements;
494	>	final int mask = elements.length - 1;
495	>	final int h = head;
496	>	final int t = tail;
497	>	final int front = (i - h) & mask;
498	>	final int back  = (t - i) & mask;
499
500		// Invariant: head <= i < tail mod circularity
501	<	if (((i - head) & mask) >= ((tail - head) & mask))
501	>	if (front >= ((t - h) & mask))
502		throw new ConcurrentModificationException();
503
504	<	// Case 1: Deque doesn't wrap
505	<	// Case 2: Deque does wrap and removed element is in the head portion
506	<	if (i >= head) {
507	<	System.arraycopy(elements, head, elements, head + 1, i - head);
508	<	elements[head] = null;
509	<	head = (head + 1) & mask;
510	<	return false;
511	<	}
512	<
513	<	// Case 3: Deque wraps and removed element is in the tail portion
514	<	tail--;
515	<	System.arraycopy(elements, i + 1, elements, i, tail - i);
516	<	elements[tail] = null;
517	<	return true;
504	>	// Optimize for least element motion
505	>	if (front < back) {
506	>	if (h <= i) {
507	>	System.arraycopy(elements, h, elements, h + 1, front);
508	>	} else { // Wrap around
509	>	System.arraycopy(elements, 0, elements, 1, i);
510	>	elements[0] = elements[mask];
511	>	System.arraycopy(elements, h, elements, h + 1, mask - h);
512	>	}
513	>	elements[h] = null;
514	>	head = (h + 1) & mask;
515	>	return false;
516	>	} else {
517	>	if (i < t) { // Copy the null tail as well
518	>	System.arraycopy(elements, i + 1, elements, i, back);
519	>	tail = t - 1;
520	>	} else { // Wrap around
521	>	System.arraycopy(elements, i + 1, elements, i, mask - i);
522	>	elements[mask] = elements[0];
523	>	System.arraycopy(elements, 1, elements, 0, t);
524	>	tail = (t - 1) & mask;
525	>	}
526	>	return true;
527	>	}
528		}
529
530		// *** Collection Methods ***
#	Line 535 | Line 553 | public class ArrayDeque<E> extends Abstr
553		* order that elements would be dequeued (via successive calls to
554		* {@link #remove} or popped (via successive calls to {@link #pop}).
555		*
556	<	* @return an <tt>Iterator</tt> over the elements in this deque
556	>	* @return an iterator over the elements in this deque
557		*/
558		public Iterator<E> iterator() {
559		return new DeqIterator();
560		}
561
562	+	public Iterator<E> descendingIterator() {
563	+	return new DescendingIterator();
564	+	}
565	+
566		private class DeqIterator implements Iterator<E> {
567		/**
568		* Index of element to be returned by subsequent call to next.
#	Line 579 | Line 601 | public class ArrayDeque<E> extends Abstr
601		public void remove() {
602		if (lastRet < 0)
603		throw new IllegalStateException();
604	<	if (delete(lastRet))
605	<	cursor--;
604	>	if (delete(lastRet)) // if left-shifted, undo increment in next()
605	>	cursor = (cursor - 1) & (elements.length - 1);
606		lastRet = -1;
607		fence = tail;
608		}
609		}
610
611	+
612	+	private class DescendingIterator implements Iterator<E> {
613	+	/*
614	+	* This class is nearly a mirror-image of DeqIterator, using
615	+	* (tail-1) instead of head for initial cursor, (head-1)
616	+	* instead of tail for fence, and elements.length instead of -1
617	+	* for sentinel. It shares the same structure, but not many
618	+	* actual lines of code.
619	+	*/
620	+	private int cursor = (tail - 1) & (elements.length - 1);
621	+	private int fence =  (head - 1) & (elements.length - 1);
622	+	private int lastRet = elements.length;
623	+
624	+	public boolean hasNext() {
625	+	return cursor != fence;
626	+	}
627	+
628	+	public E next() {
629	+	E result;
630	+	if (cursor == fence)
631	+	throw new NoSuchElementException();
632	+	if (((head - 1) & (elements.length - 1)) != fence ||
633	+	(result = elements[cursor]) == null)
634	+	throw new ConcurrentModificationException();
635	+	lastRet = cursor;
636	+	cursor = (cursor - 1) & (elements.length - 1);
637	+	return result;
638	+	}
639	+
640	+	public void remove() {
641	+	if (lastRet >= elements.length)
642	+	throw new IllegalStateException();
643	+	if (!delete(lastRet))
644	+	cursor = (cursor + 1) & (elements.length - 1);
645	+	lastRet = elements.length;
646	+	fence = (head - 1) & (elements.length - 1);
647	+	}
648	+	}
649	+
650		/**
651		* Returns <tt>true</tt> if this deque contains the specified element.
652		* More formally, returns <tt>true</tt> if and only if this deque contains
#	Line 613 | Line 674 | public class ArrayDeque<E> extends Abstr
674		* If the deque does not contain the element, it is unchanged.
675		* More formally, removes the first element <tt>e</tt> such that
676		* <tt>o.equals(e)</tt> (if such an element exists).
677	<	* Returns true if this deque contained the specified element (or
678	<	* equivalently, if this deque changed as a result of the call).
677	>	* Returns <tt>true</tt> if this deque contained the specified element
678	>	* (or equivalently, if this deque changed as a result of the call).
679		*
680		* <p>This method is equivalent to {@link #removeFirstOccurrence}.
681		*
#	Line 645 | Line 706 | public class ArrayDeque<E> extends Abstr
706
707		/**
708		* Returns an array containing all of the elements in this deque
709	<	* in the correct order.
709	>	* in proper sequence (from first to last element).
710	>	*
711	>	* <p>The returned array will be "safe" in that no references to it are
712	>	* maintained by this deque.  (In other words, this method must allocate
713	>	* a new array).  The caller is thus free to modify the returned array.
714	>	*
715	>	* <p>This method acts as bridge between array-based and collection-based
716	>	* APIs.
717		*
718		* @return an array containing all of the elements in this deque
651	–	*         in the correct order
719		*/
720		public Object[] toArray() {
721		return copyElements(new Object[size()]);
722		}
723
724		/**
725	<	* Returns an array containing all of the elements in this deque in the
726	<	* correct order; the runtime type of the returned array is that of the
727	<	* specified array.  If the deque fits in the specified array, it is
728	<	* returned therein.  Otherwise, a new array is allocated with the runtime
729	<	* type of the specified array and the size of this deque.
730	<	*
731	<	* <p>If the deque fits in the specified array with room to spare (i.e.,
732	<	* the array has more elements than the deque), the element in the array
733	<	* immediately following the end of the collection is set to <tt>null</tt>.
725	>	* Returns an array containing all of the elements in this deque in
726	>	* proper sequence (from first to last element); the runtime type of the
727	>	* returned array is that of the specified array.  If the deque fits in
728	>	* the specified array, it is returned therein.  Otherwise, a new array
729	>	* is allocated with the runtime type of the specified array and the
730	>	* size of this deque.
731	>	*
732	>	* <p>If this deque fits in the specified array with room to spare
733	>	* (i.e., the array has more elements than this deque), the element in
734	>	* the array immediately following the end of the deque is set to
735	>	* <tt>null</tt>.
736	>	*
737	>	* <p>Like the {@link #toArray()} method, this method acts as bridge between
738	>	* array-based and collection-based APIs.  Further, this method allows
739	>	* precise control over the runtime type of the output array, and may,
740	>	* under certain circumstances, be used to save allocation costs.
741	>	*
742	>	* <p>Suppose <tt>x</tt> is a deque known to contain only strings.
743	>	* The following code can be used to dump the deque into a newly
744	>	* allocated array of <tt>String</tt>:
745	>	*
746	>	* <pre>
747	>	*     String[] y = x.toArray(new String[0]);</pre>
748	>	*
749	>	* Note that <tt>toArray(new Object[0])</tt> is identical in function to
750	>	* <tt>toArray()</tt>.
751		*
752		* @param a the array into which the elements of the deque are to
753		*          be stored, if it is big enough; otherwise, a new array of the
754		*          same runtime type is allocated for this purpose
755	<	* @return an array containing the elements of the deque
756	<	* @throws ArrayStoreException if the runtime type of a is not a supertype
757	<	*         of the runtime type of every element in this deque
755	>	* @return an array containing all of the elements in this deque
756	>	* @throws ArrayStoreException if the runtime type of the specified array
757	>	*         is not a supertype of the runtime type of every element in
758	>	*         this deque
759	>	* @throws NullPointerException if the specified array is null
760		*/
761		public <T> T[] toArray(T[] a) {
762		int size = size();
#	Line 719 | Line 805 | public class ArrayDeque<E> extends Abstr
805		s.defaultWriteObject();
806
807		// Write out size
808	<	int size = size();
723	<	s.writeInt(size);
808	>	s.writeInt(size());
809
810		// Write out elements in order.
726	–	int i = head;
811		int mask = elements.length - 1;
812	<	for (int j = 0; j < size; j++) {
812	>	for (int i = head; i != tail; i = (i + 1) & mask)
813		s.writeObject(elements[i]);
730	–	i = (i + 1) & mask;
731	–	}
814		}
815
816		/**

Diff Legend

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