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.16 by dl, Wed Sep 14 23:49:59 2005 UTC vs.
Revision 1.24 by dl, Sat Sep 17 13:21:19 2005 UTC

#	Line 490 | 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 538 | 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
547	–	/**
548	–	* Returns an iterator over the elements in this deque in reverse
549	–	* sequential order.  The elements will be returned in order from
550	–	* last (tail) to first (head).
551	–	*
552	–	* @return an iterator over the elements in this deque in reverse
553	–	* sequence
554	–	*/
562		public Iterator<E> descendingIterator() {
563		return new DescendingIterator();
564		}
#	Line 594 | 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		}
#	Line 603 | Line 610 | public class ArrayDeque<E> extends Abstr
610
611
612		private class DescendingIterator implements Iterator<E> {
613	<	/*
614	<	* This class is nearly a mirror-image of DeqIterator. It
615	<	* shares the same structure, but not many actual lines of
616	<	* code. The only asymmetric part is that to simplify some
617	<	* checks, indices are anded with length mask only on array
618	<	* access rather than on each update.
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;
621	<	private int fence = head - 1;
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() {
#	Line 622 | Line 629 | public class ArrayDeque<E> extends Abstr
629		E result;
630		if (cursor == fence)
631		throw new NoSuchElementException();
632	<	if ((head - 1) != fence ||
633	<	(result = elements[cursor & (elements.length-1)]) == null)
632	>	if (((head - 1) & (elements.length - 1)) != fence ||
633	>	(result = elements[cursor]) == null)
634		throw new ConcurrentModificationException();
635		lastRet = cursor;
636	<	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 & (elements.length-1)))
644	<	cursor++;
643	>	if (!delete(lastRet))
644	>	cursor = (cursor + 1) & (elements.length - 1);
645		lastRet = elements.length;
646	<	fence = head - 1;
646	>	fence = (head - 1) & (elements.length - 1);
647		}
648		}
649
#	Line 798 | Line 805 | public class ArrayDeque<E> extends Abstr
805		s.defaultWriteObject();
806
807		// Write out size
808	<	int size = size();
802	<	s.writeInt(size);
808	>	s.writeInt(size());
809
810		// Write out elements in order.
805	–	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]);
809	–	i = (i + 1) & mask;
810	–	}
814		}
815
816		/**

Diff Legend

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