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.12 by jsr166, Tue May 17 16:14:34 2005 UTC vs.
Revision 1.26 by jsr166, Mon Sep 19 13:42: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 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 476 | Line 479 | public class ArrayDeque<E> extends Abstr
479		return removeFirst();
480		}
481
482	+	private void checkInvariants() {
483	+	assert elements[tail] == null;
484	+	assert head == tail ? elements[head] == null :
485	+	(elements[head] != null &&
486	+	elements[(tail - 1) & (elements.length - 1)] != null);
487	+	assert elements[(head - 1) & (elements.length - 1)] == null;
488	+	}
489	+
490		/**
491		* Removes the element at the specified position in the elements array,
492		* adjusting head and tail as necessary.  This can result in motion of
#	Line 487 | Line 498 | public class ArrayDeque<E> extends Abstr
498		* @return true if elements moved backwards
499		*/
500		private boolean delete(int i) {
501	<	int mask = elements.length - 1;
501	>	checkInvariants();
502	>	final E[] elements = this.elements;
503	>	final int mask = elements.length - 1;
504	>	final int h = head;
505	>	final int t = tail;
506	>	final int front = (i - h) & mask;
507	>	final int back  = (t - i) & mask;
508
509		// Invariant: head <= i < tail mod circularity
510	<	if (((i - head) & mask) >= ((tail - head) & mask))
510	>	if (front >= ((t - h) & mask))
511		throw new ConcurrentModificationException();
512
513	<	// Case 1: Deque doesn't wrap
514	<	// Case 2: Deque does wrap and removed element is in the head portion
515	<	if (i >= head) {
516	<	System.arraycopy(elements, head, elements, head + 1, i - head);
517	<	elements[head] = null;
518	<	head = (head + 1) & mask;
519	<	return false;
520	<	}
521	<
522	<	// Case 3: Deque wraps and removed element is in the tail portion
523	<	tail--;
524	<	System.arraycopy(elements, i + 1, elements, i, tail - i);
525	<	elements[tail] = null;
526	<	return true;
513	>	// Optimize for least element motion
514	>	if (front < back) {
515	>	if (h <= i) {
516	>	System.arraycopy(elements, h, elements, h + 1, front);
517	>	} else { // Wrap around
518	>	System.arraycopy(elements, 0, elements, 1, i);
519	>	elements[0] = elements[mask];
520	>	System.arraycopy(elements, h, elements, h + 1, mask - h);
521	>	}
522	>	elements[h] = null;
523	>	head = (h + 1) & mask;
524	>	return false;
525	>	} else {
526	>	if (i < t) { // Copy the null tail as well
527	>	System.arraycopy(elements, i + 1, elements, i, back);
528	>	tail = t - 1;
529	>	} else { // Wrap around
530	>	System.arraycopy(elements, i + 1, elements, i, mask - i);
531	>	elements[mask] = elements[0];
532	>	System.arraycopy(elements, 1, elements, 0, t);
533	>	tail = (t - 1) & mask;
534	>	}
535	>	return true;
536	>	}
537		}
538
539		// *** Collection Methods ***
#	Line 535 | Line 562 | public class ArrayDeque<E> extends Abstr
562		* order that elements would be dequeued (via successive calls to
563		* {@link #remove} or popped (via successive calls to {@link #pop}).
564		*
565	<	* @return an <tt>Iterator</tt> over the elements in this deque
565	>	* @return an iterator over the elements in this deque
566		*/
567		public Iterator<E> iterator() {
568		return new DeqIterator();
569		}
570
571	+	public Iterator<E> descendingIterator() {
572	+	return new DescendingIterator();
573	+	}
574	+
575		private class DeqIterator implements Iterator<E> {
576		/**
577		* Index of element to be returned by subsequent call to next.
#	Line 564 | Line 595 | public class ArrayDeque<E> extends Abstr
595		}
596
597		public E next() {
567	–	E result;
598		if (cursor == fence)
599		throw new NoSuchElementException();
600	+	E result = elements[cursor];
601		// This check doesn't catch all possible comodifications,
602		// but does catch the ones that corrupt traversal
603	<	if (tail != fence || (result = elements[cursor]) == null)
603	>	if (tail != fence || result == null)
604		throw new ConcurrentModificationException();
605		lastRet = cursor;
606		cursor = (cursor + 1) & (elements.length - 1);
#	Line 579 | Line 610 | public class ArrayDeque<E> extends Abstr
610		public void remove() {
611		if (lastRet < 0)
612		throw new IllegalStateException();
613	<	if (delete(lastRet))
614	<	cursor--;
613	>	if (delete(lastRet)) { // if left-shifted, undo increment in next()
614	>	cursor = (cursor - 1) & (elements.length - 1);
615	>	fence = tail;
616	>	}
617	>	lastRet = -1;
618	>	}
619	>	}
620	>
621	>	private class DescendingIterator implements Iterator<E> {
622	>	/*
623	>	* This class is nearly a mirror-image of DeqIterator, using
624	>	* tail instead of head for initial cursor, and head instead of
625	>	* tail for fence.
626	>	*/
627	>	private int cursor = tail;
628	>	private int fence = head;
629	>	private int lastRet = -1;
630	>
631	>	public boolean hasNext() {
632	>	return cursor != fence;
633	>	}
634	>
635	>	public E next() {
636	>	if (cursor == fence)
637	>	throw new NoSuchElementException();
638	>	cursor = (cursor - 1) & (elements.length - 1);
639	>	E result = elements[cursor];
640	>	if (head != fence || result == null)
641	>	throw new ConcurrentModificationException();
642	>	lastRet = cursor;
643	>	return result;
644	>	}
645	>
646	>	public void remove() {
647	>	if (lastRet < 0)
648	>	throw new IllegalStateException();
649	>	if (!delete(lastRet)) {
650	>	cursor = (cursor + 1) & (elements.length - 1);
651	>	fence = head;
652	>	}
653		lastRet = -1;
585	–	fence = tail;
654		}
655		}
656
#	Line 650 | Line 718 | public class ArrayDeque<E> extends Abstr
718		* <p>The returned array will be "safe" in that no references to it are
719		* maintained by this deque.  (In other words, this method must allocate
720		* a new array).  The caller is thus free to modify the returned array.
721	<	*
721	>	*
722		* <p>This method acts as bridge between array-based and collection-based
723		* APIs.
724		*
#	Line 744 | Line 812 | public class ArrayDeque<E> extends Abstr
812		s.defaultWriteObject();
813
814		// Write out size
815	<	int size = size();
748	<	s.writeInt(size);
815	>	s.writeInt(size());
816
817		// Write out elements in order.
751	–	int i = head;
818		int mask = elements.length - 1;
819	<	for (int j = 0; j < size; j++) {
819	>	for (int i = head; i != tail; i = (i + 1) & mask)
820		s.writeObject(elements[i]);
755	–	i = (i + 1) & mask;
756	–	}
821		}
822
823		/**
#	Line 772 | Line 836 | public class ArrayDeque<E> extends Abstr
836		// Read in all elements in the proper order.
837		for (int i = 0; i < size; i++)
838		elements[i] = (E)s.readObject();
775	–
839		}
840		}

Diff Legend

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