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.14 by jsr166, Sat Jun 18 01:56:01 2005 UTC vs.
Revision 1.21 by dl, Fri Sep 16 23:17:05 2005 UTC

#	Line 4 | Line 4
4		*/
5
6		package java.util;
7	<	import java.util.*; // for javadoc
7	>	import java.util.*; // for javadoc (till 6280605 is fixed)
8		import java.io.*;
9
10		/**
#	Line 221 | 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 233 | 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 373 | 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 387 | 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 396 | 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 424 | 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 490 | Line 491 | public class ArrayDeque<E> extends Abstr
491		*/
492		private boolean delete(int i) {
493		int mask = elements.length - 1;
494	+	int front = (i - head) & mask;
495	+	int back  = (tail - i) & mask;
496
497		// Invariant: head <= i < tail mod circularity
498	<	if (((i - head) & mask) >= ((tail - head) & mask))
498	>	if (front >= ((tail - head) & mask))
499		throw new ConcurrentModificationException();
500
501	<	// Case 1: Deque doesn't wrap
502	<	// Case 2: Deque does wrap and removed element is in the head portion
503	<	if (i >= head) {
504	<	System.arraycopy(elements, head, elements, head + 1, i - head);
505	<	elements[head] = null;
506	<	head = (head + 1) & mask;
501	>	// Optimize for least element motion
502	>	if (front < back) {
503	>	if (head <= i) {
504	>	System.arraycopy(elements, head, elements, head + 1, front);
505	>	} else { // Wrap around
506	>	elements[0] = elements[mask];
507	>	System.arraycopy(elements, 0, elements, 1, i);
508	>	System.arraycopy(elements, head, elements, head + 1, mask - head);
509	>	}
510	>	elements[head] = null;
511	>	head = (head + 1) & mask;
512		return false;
513	<	}
514	<
515	<	// Case 3: Deque wraps and removed element is in the tail portion
516	<	tail--;
517	<	System.arraycopy(elements, i + 1, elements, i, tail - i);
518	<	elements[tail] = null;
519	<	return true;
513	>	} else {
514	>	int t = tail;
515	>	tail = (tail - 1) & mask;
516	>	if (i < t) { // Copy the null tail as well
517	>	System.arraycopy(elements, i + 1, elements, i, back);
518	>	} else {     // Wrap around
519	>	elements[mask] = elements[0];
520	>	System.arraycopy(elements, i + 1, elements, i, mask - i);
521	>	System.arraycopy(elements, 1, elements, 0, t);
522	>	}
523	>	return true;
524	>	}
525		}
526
527		// *** Collection Methods ***
#	Line 537 | Line 550 | public class ArrayDeque<E> extends Abstr
550		* order that elements would be dequeued (via successive calls to
551		* {@link #remove} or popped (via successive calls to {@link #pop}).
552		*
553	<	* @return an <tt>Iterator</tt> over the elements in this deque
553	>	* @return an iterator over the elements in this deque
554		*/
555		public Iterator<E> iterator() {
556		return new DeqIterator();
557		}
558
559	+	public Iterator<E> descendingIterator() {
560	+	return new DescendingIterator();
561	+	}
562	+
563		private class DeqIterator implements Iterator<E> {
564		/**
565		* Index of element to be returned by subsequent call to next.
#	Line 581 | Line 598 | public class ArrayDeque<E> extends Abstr
598		public void remove() {
599		if (lastRet < 0)
600		throw new IllegalStateException();
601	<	if (delete(lastRet))
602	<	cursor--;
601	>	if (delete(lastRet)) // if left-shifted, undo increment in next()
602	>	cursor = (cursor - 1) & (elements.length - 1);
603		lastRet = -1;
604		fence = tail;
605		}
606		}
607
608	+
609	+	private class DescendingIterator implements Iterator<E> {
610	+	/*
611	+	* This class is nearly a mirror-image of DeqIterator, using
612	+	* (tail-1) instead of head for initial cursor, (head-1)
613	+	* 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.
616	+	*/
617	+	private int cursor = (tail - 1) & (elements.length - 1);
618	+	private int fence =  (head - 1) & (elements.length - 1);
619	+	private int lastRet = elements.length;
620	+
621	+	public boolean hasNext() {
622	+	return cursor != fence;
623	+	}
624	+
625	+	public E next() {
626	+	E result;
627	+	if (cursor == fence)
628	+	throw new NoSuchElementException();
629	+	if (((head - 1) & (elements.length - 1)) != fence ||
630	+	(result = elements[cursor]) == null)
631	+	throw new ConcurrentModificationException();
632	+	lastRet = cursor;
633	+	cursor = (cursor - 1) & (elements.length - 1);
634	+	return result;
635	+	}
636	+
637	+	public void remove() {
638	+	if (lastRet >= elements.length)
639	+	throw new IllegalStateException();
640	+	if (!delete(lastRet))
641	+	cursor = (cursor + 1) & (elements.length - 1);
642	+	lastRet = elements.length;
643	+	fence = (head - 1) & (elements.length - 1);
644	+	}
645	+	}
646	+
647		/**
648		* Returns <tt>true</tt> if this deque contains the specified element.
649		* More formally, returns <tt>true</tt> if and only if this deque contains
#	Line 746 | Line 802 | public class ArrayDeque<E> extends Abstr
802		s.defaultWriteObject();
803
804		// Write out size
805	<	int size = size();
750	<	s.writeInt(size);
805	>	s.writeInt(size());
806
807		// Write out elements in order.
753	–	int i = head;
808		int mask = elements.length - 1;
809	<	for (int j = 0; j < size; j++) {
809	>	for (int i = head; i != tail; i = (i + 1) & mask)
810		s.writeObject(elements[i]);
757	–	i = (i + 1) & mask;
758	–	}
811		}
812
813		/**

Diff Legend

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