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.21 by dl, Fri Sep 16 23:17:05 2005 UTC vs.
Revision 1.34 by jsr166, Fri Jun 10 20:58:50 2011 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 java.util;
7	–	import java.util.*; // for javadoc (till 6280605 is fixed)
8	–	import java.io.*;
7
8		/**
9		* Resizable-array implementation of the {@link Deque} interface.  Array
#	Line 45 | Line 43 | import java.io.*;
43		* Iterator} interfaces.
44		*
45		* <p>This class is a member of the
46	<	* <a href="{@docRoot}/../guide/collections/index.html">
46	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
47		* Java Collections Framework</a>.
48		*
49		* @author  Josh Bloch and Doug Lea
#	Line 53 | Line 51 | import java.io.*;
51		* @param <E> the type of elements held in this collection
52		*/
53		public class ArrayDeque<E> extends AbstractCollection<E>
54	<	implements Deque<E>, Cloneable, Serializable
54	>	implements Deque<E>, Cloneable, java.io.Serializable
55		{
56		/**
57		* The array in which the elements of the deque are stored.
#	Line 65 | Line 63 | public class ArrayDeque<E> extends Abstr
63		* other.  We also guarantee that all array cells not holding
64		* deque elements are always null.
65		*/
66	<	private transient E[] elements;
66	>	private transient Object[] elements;
67
68		/**
69		* The index of the element at the head of the deque (which is the
#	Line 109 | Line 107 | public class ArrayDeque<E> extends Abstr
107		if (initialCapacity < 0)   // Too many elements, must back off
108		initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
109		}
110	<	elements = (E[]) new Object[initialCapacity];
110	>	elements = new Object[initialCapacity];
111		}
112
113		/**
#	Line 127 | Line 125 | public class ArrayDeque<E> extends Abstr
125		Object[] a = new Object[newCapacity];
126		System.arraycopy(elements, p, a, 0, r);
127		System.arraycopy(elements, 0, a, r, p);
128	<	elements = (E[])a;
128	>	elements = a;
129		head = 0;
130		tail = n;
131		}
#	Line 155 | Line 153 | public class ArrayDeque<E> extends Abstr
153		* sufficient to hold 16 elements.
154		*/
155		public ArrayDeque() {
156	<	elements = (E[]) new Object[16];
156	>	elements = new Object[16];
157		}
158
159		/**
#	Line 263 | Line 261 | public class ArrayDeque<E> extends Abstr
261
262		public E pollFirst() {
263		int h = head;
264	<	E result = elements[h]; // Element is null if deque empty
264	>	@SuppressWarnings("unchecked") E result = (E) elements[h];
265	>	// Element is null if deque empty
266		if (result == null)
267		return null;
268		elements[h] = null;     // Must null out slot
#	Line 273 | Line 272 | public class ArrayDeque<E> extends Abstr
272
273		public E pollLast() {
274		int t = (tail - 1) & (elements.length - 1);
275	<	E result = elements[t];
275	>	@SuppressWarnings("unchecked") E result = (E) elements[t];
276		if (result == null)
277		return null;
278		elements[t] = null;
#	Line 285 | Line 284 | public class ArrayDeque<E> extends Abstr
284		* @throws NoSuchElementException {@inheritDoc}
285		*/
286		public E getFirst() {
287	<	E x = elements[head];
288	<	if (x == null)
287	>	@SuppressWarnings("unchecked") E result = (E) elements[head];
288	>	if (result == null)
289		throw new NoSuchElementException();
290	<	return x;
290	>	return result;
291		}
292
293		/**
294		* @throws NoSuchElementException {@inheritDoc}
295		*/
296		public E getLast() {
297	<	E x = elements[(tail - 1) & (elements.length - 1)];
298	<	if (x == null)
297	>	@SuppressWarnings("unchecked")
298	>	E result = (E) elements[(tail - 1) & (elements.length - 1)];
299	>	if (result == null)
300		throw new NoSuchElementException();
301	<	return x;
301	>	return result;
302		}
303
304		public E peekFirst() {
305	<	return elements[head]; // elements[head] is null if deque empty
305	>	@SuppressWarnings("unchecked") E result = (E) elements[head];
306	>	// elements[head] is null if deque empty
307	>	return result;
308		}
309
310		public E peekLast() {
311	<	return elements[(tail - 1) & (elements.length - 1)];
311	>	@SuppressWarnings("unchecked")
312	>	E result = (E) elements[(tail - 1) & (elements.length - 1)];
313	>	return result;
314		}
315
316		/**
#	Line 326 | Line 330 | public class ArrayDeque<E> extends Abstr
330		return false;
331		int mask = elements.length - 1;
332		int i = head;
333	<	E x;
333	>	Object x;
334		while ( (x = elements[i]) != null) {
335		if (o.equals(x)) {
336		delete(i);
#	Line 354 | Line 358 | public class ArrayDeque<E> extends Abstr
358		return false;
359		int mask = elements.length - 1;
360		int i = (tail - 1) & mask;
361	<	E x;
361	>	Object x;
362		while ( (x = elements[i]) != null) {
363		if (o.equals(x)) {
364		delete(i);
#	Line 479 | Line 483 | public class ArrayDeque<E> extends Abstr
483		return removeFirst();
484		}
485
486	+	private void checkInvariants() {
487	+	assert elements[tail] == null;
488	+	assert head == tail ? elements[head] == null :
489	+	(elements[head] != null &&
490	+	elements[(tail - 1) & (elements.length - 1)] != null);
491	+	assert elements[(head - 1) & (elements.length - 1)] == null;
492	+	}
493	+
494		/**
495		* Removes the element at the specified position in the elements array,
496		* adjusting head and tail as necessary.  This can result in motion of
#	Line 490 | Line 502 | public class ArrayDeque<E> extends Abstr
502		* @return true if elements moved backwards
503		*/
504		private boolean delete(int i) {
505	<	int mask = elements.length - 1;
506	<	int front = (i - head) & mask;
507	<	int back  = (tail - i) & mask;
508	<
509	<	// Invariant: head <= i < tail mod circularity
510	<	if (front >= ((tail - head) & mask))
511	<	throw new ConcurrentModificationException();
512	<
513	<	// Optimize for least element motion
514	<	if (front < back) {
515	<	if (head <= i) {
516	<	System.arraycopy(elements, head, elements, head + 1, front);
517	<	} else { // Wrap around
518	<	elements[0] = elements[mask];
519	<	System.arraycopy(elements, 0, elements, 1, i);
520	<	System.arraycopy(elements, head, elements, head + 1, mask - head);
521	<	}
522	<	elements[head] = null;
523	<	head = (head + 1) & mask;
505	>	checkInvariants();
506	>	final Object[] elements = this.elements;
507	>	final int mask = elements.length - 1;
508	>	final int h = head;
509	>	final int t = tail;
510	>	final int front = (i - h) & mask;
511	>	final int back  = (t - i) & mask;
512	>
513	>	// Invariant: head <= i < tail mod circularity
514	>	if (front >= ((t - h) & mask))
515	>	throw new ConcurrentModificationException();
516	>
517	>	// Optimize for least element motion
518	>	if (front < back) {
519	>	if (h <= i) {
520	>	System.arraycopy(elements, h, elements, h + 1, front);
521	>	} else { // Wrap around
522	>	System.arraycopy(elements, 0, elements, 1, i);
523	>	elements[0] = elements[mask];
524	>	System.arraycopy(elements, h, elements, h + 1, mask - h);
525	>	}
526	>	elements[h] = null;
527	>	head = (h + 1) & mask;
528		return false;
529	<	} else {
530	<	int t = tail;
531	<	tail = (tail - 1) & mask;
532	<	if (i < t) { // Copy the null tail as well
533	<	System.arraycopy(elements, i + 1, elements, i, back);
534	<	} else {     // Wrap around
535	<	elements[mask] = elements[0];
536	<	System.arraycopy(elements, i + 1, elements, i, mask - i);
537	<	System.arraycopy(elements, 1, elements, 0, t);
538	<	}
529	>	} else {
530	>	if (i < t) { // Copy the null tail as well
531	>	System.arraycopy(elements, i + 1, elements, i, back);
532	>	tail = t - 1;
533	>	} else { // Wrap around
534	>	System.arraycopy(elements, i + 1, elements, i, mask - i);
535	>	elements[mask] = elements[0];
536	>	System.arraycopy(elements, 1, elements, 0, t);
537	>	tail = (t - 1) & mask;
538	>	}
539		return true;
540	<	}
540	>	}
541		}
542
543		// *** Collection Methods ***
#	Line 583 | Line 599 | public class ArrayDeque<E> extends Abstr
599		}
600
601		public E next() {
586	–	E result;
602		if (cursor == fence)
603		throw new NoSuchElementException();
604	+	@SuppressWarnings("unchecked") E result = (E) elements[cursor];
605		// This check doesn't catch all possible comodifications,
606		// but does catch the ones that corrupt traversal
607	<	if (tail != fence || (result = elements[cursor]) == null)
607	>	if (tail != fence || result == null)
608		throw new ConcurrentModificationException();
609		lastRet = cursor;
610		cursor = (cursor + 1) & (elements.length - 1);
#	Line 598 | Line 614 | public class ArrayDeque<E> extends Abstr
614		public void remove() {
615		if (lastRet < 0)
616		throw new IllegalStateException();
617	<	if (delete(lastRet)) // if left-shifted, undo increment in next()
617	>	if (delete(lastRet)) { // if left-shifted, undo increment in next()
618		cursor = (cursor - 1) & (elements.length - 1);
619	+	fence = tail;
620	+	}
621		lastRet = -1;
604	–	fence = tail;
622		}
623		}
624
608	–
625		private class DescendingIterator implements Iterator<E> {
626		/*
627		* This class is nearly a mirror-image of DeqIterator, using
628	<	* (tail-1) instead of head for initial cursor, (head-1)
629	<	* instead of tail for fence, and elements.length instead of -1
614	<	* for sentinel. It shares the same structure, but not many
615	<	* actual lines of code.
628	>	* tail instead of head for initial cursor, and head instead of
629	>	* tail for fence.
630		*/
631	<	private int cursor = (tail - 1) & (elements.length - 1);
632	<	private int fence =  (head - 1) & (elements.length - 1);
633	<	private int lastRet = elements.length;
631	>	private int cursor = tail;
632	>	private int fence = head;
633	>	private int lastRet = -1;
634
635		public boolean hasNext() {
636		return cursor != fence;
637		}
638
639		public E next() {
626	–	E result;
640		if (cursor == fence)
641		throw new NoSuchElementException();
642	<	if (((head - 1) & (elements.length - 1)) != fence ||
643	<	(result = elements[cursor]) == null)
642	>	cursor = (cursor - 1) & (elements.length - 1);
643	>	@SuppressWarnings("unchecked") E result = (E) elements[cursor];
644	>	if (head != fence || result == null)
645		throw new ConcurrentModificationException();
646		lastRet = cursor;
633	–	cursor = (cursor - 1) & (elements.length - 1);
647		return result;
648		}
649
650		public void remove() {
651	<	if (lastRet >= elements.length)
651	>	if (lastRet < 0)
652		throw new IllegalStateException();
653	<	if (!delete(lastRet))
653	>	if (!delete(lastRet)) {
654		cursor = (cursor + 1) & (elements.length - 1);
655	<	lastRet = elements.length;
656	<	fence = (head - 1) & (elements.length - 1);
655	>	fence = head;
656	>	}
657	>	lastRet = -1;
658		}
659		}
660
#	Line 657 | Line 671 | public class ArrayDeque<E> extends Abstr
671		return false;
672		int mask = elements.length - 1;
673		int i = head;
674	<	E x;
674	>	Object x;
675		while ( (x = elements[i]) != null) {
676		if (o.equals(x))
677		return true;
#	Line 715 | Line 729 | public class ArrayDeque<E> extends Abstr
729		* @return an array containing all of the elements in this deque
730		*/
731		public Object[] toArray() {
732	<	return copyElements(new Object[size()]);
732	>	return copyElements(new Object[size()]);
733		}
734
735		/**
#	Line 740 | Line 754 | public class ArrayDeque<E> extends Abstr
754		* The following code can be used to dump the deque into a newly
755		* allocated array of <tt>String</tt>:
756		*
757	<	* <pre>
744	<	*     String[] y = x.toArray(new String[0]);</pre>
757	>	*  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
758		*
759		* Note that <tt>toArray(new Object[0])</tt> is identical in function to
760		* <tt>toArray()</tt>.
#	Line 755 | Line 768 | public class ArrayDeque<E> extends Abstr
768		*         this deque
769		* @throws NullPointerException if the specified array is null
770		*/
771	+	@SuppressWarnings("unchecked")
772		public <T> T[] toArray(T[] a) {
773		int size = size();
774		if (a.length < size)
775		a = (T[])java.lang.reflect.Array.newInstance(
776		a.getClass().getComponentType(), size);
777	<	copyElements(a);
777	>	copyElements(a);
778		if (a.length > size)
779		a[size] = null;
780		return a;
#	Line 775 | Line 789 | public class ArrayDeque<E> extends Abstr
789		*/
790		public ArrayDeque<E> clone() {
791		try {
792	+	@SuppressWarnings("unchecked")
793		ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
794	<	// These two lines are currently faster than cloning the array:
780	<	result.elements = (E[]) new Object[elements.length];
781	<	System.arraycopy(elements, 0, result.elements, 0, elements.length);
794	>	result.elements = Arrays.copyOf(elements, elements.length);
795		return result;
796
797		} catch (CloneNotSupportedException e) {
#	Line 798 | Line 811 | public class ArrayDeque<E> extends Abstr
811		* followed by all of its elements (each an object reference) in
812		* first-to-last order.
813		*/
814	<	private void writeObject(ObjectOutputStream s) throws IOException {
814	>	private void writeObject(java.io.ObjectOutputStream s)
815	>	throws java.io.IOException {
816		s.defaultWriteObject();
817
818		// Write out size
#	Line 813 | Line 827 | public class ArrayDeque<E> extends Abstr
827		/**
828		* Deserialize this deque.
829		*/
830	<	private void readObject(ObjectInputStream s)
831	<	throws IOException, ClassNotFoundException {
830	>	private void readObject(java.io.ObjectInputStream s)
831	>	throws java.io.IOException, ClassNotFoundException {
832		s.defaultReadObject();
833
834		// Read in size and allocate array
#	Line 825 | Line 839 | public class ArrayDeque<E> extends Abstr
839
840		// Read in all elements in the proper order.
841		for (int i = 0; i < size; i++)
842	<	elements[i] = (E)s.readObject();
829	<
842	>	elements[i] = s.readObject();
843		}
844		}

Diff Legend

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