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.27 by jsr166, Tue Feb 7 20:54:24 2006 UTC

#	Line 4 | Line 4
4		*/
5
6		package java.util;
7	–	import java.util.*; // for javadoc (till 6280605 is fixed)
7		import java.io.*;
8
9		/**
#	Line 479 | Line 478 | public class ArrayDeque<E> extends Abstr
478		return removeFirst();
479		}
480
481	+	private void checkInvariants() {
482	+	assert elements[tail] == null;
483	+	assert head == tail ? elements[head] == null :
484	+	(elements[head] != null &&
485	+	elements[(tail - 1) & (elements.length - 1)] != null);
486	+	assert elements[(head - 1) & (elements.length - 1)] == null;
487	+	}
488	+
489		/**
490		* Removes the element at the specified position in the elements array,
491		* adjusting head and tail as necessary.  This can result in motion of
#	Line 490 | Line 497 | public class ArrayDeque<E> extends Abstr
497		* @return true if elements moved backwards
498		*/
499		private boolean delete(int i) {
500	<	int mask = elements.length - 1;
501	<	int front = (i - head) & mask;
502	<	int back  = (tail - i) & mask;
500	>	checkInvariants();
501	>	final E[] elements = this.elements;
502	>	final int mask = elements.length - 1;
503	>	final int h = head;
504	>	final int t = tail;
505	>	final int front = (i - h) & mask;
506	>	final int back  = (t - i) & mask;
507
508		// Invariant: head <= i < tail mod circularity
509	<	if (front >= ((tail - head) & mask))
509	>	if (front >= ((t - h) & mask))
510		throw new ConcurrentModificationException();
511
512		// Optimize for least element motion
513		if (front < back) {
514	<	if (head <= i) {
515	<	System.arraycopy(elements, head, elements, head + 1, front);
514	>	if (h <= i) {
515	>	System.arraycopy(elements, h, elements, h + 1, front);
516		} else { // Wrap around
506	–	elements[0] = elements[mask];
517		System.arraycopy(elements, 0, elements, 1, i);
518	<	System.arraycopy(elements, head, elements, head + 1, mask - head);
518	>	elements[0] = elements[mask];
519	>	System.arraycopy(elements, h, elements, h + 1, mask - h);
520		}
521	<	elements[head] = null;
522	<	head = (head + 1) & mask;
523	<	return false;
521	>	elements[h] = null;
522	>	head = (h + 1) & mask;
523	>	return false;
524		} else {
514	–	int t = tail;
515	–	tail = (tail - 1) & mask;
525		if (i < t) { // Copy the null tail as well
526		System.arraycopy(elements, i + 1, elements, i, back);
527	<	} else {     // Wrap around
528	<	elements[mask] = elements[0];
527	>	tail = t - 1;
528	>	} else { // Wrap around
529		System.arraycopy(elements, i + 1, elements, i, mask - i);
530	+	elements[mask] = elements[0];
531		System.arraycopy(elements, 1, elements, 0, t);
532	+	tail = (t - 1) & mask;
533		}
534	<	return true;
534	>	return true;
535		}
536		}
537
#	Line 583 | Line 594 | public class ArrayDeque<E> extends Abstr
594		}
595
596		public E next() {
586	–	E result;
597		if (cursor == fence)
598		throw new NoSuchElementException();
599	+	E result = elements[cursor];
600		// This check doesn't catch all possible comodifications,
601		// but does catch the ones that corrupt traversal
602	<	if (tail != fence || (result = elements[cursor]) == null)
602	>	if (tail != fence || result == null)
603		throw new ConcurrentModificationException();
604		lastRet = cursor;
605		cursor = (cursor + 1) & (elements.length - 1);
#	Line 598 | Line 609 | public class ArrayDeque<E> extends Abstr
609		public void remove() {
610		if (lastRet < 0)
611		throw new IllegalStateException();
612	<	if (delete(lastRet)) // if left-shifted, undo increment in next()
612	>	if (delete(lastRet)) { // if left-shifted, undo increment in next()
613		cursor = (cursor - 1) & (elements.length - 1);
614	+	fence = tail;
615	+	}
616		lastRet = -1;
604	–	fence = tail;
617		}
618		}
619
608	–
620		private class DescendingIterator implements Iterator<E> {
621		/*
622		* This class is nearly a mirror-image of DeqIterator, using
623	<	* (tail-1) instead of head for initial cursor, (head-1)
624	<	* 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.
623	>	* tail instead of head for initial cursor, and head instead of
624	>	* tail for fence.
625		*/
626	<	private int cursor = (tail - 1) & (elements.length - 1);
627	<	private int fence =  (head - 1) & (elements.length - 1);
628	<	private int lastRet = elements.length;
626	>	private int cursor = tail;
627	>	private int fence = head;
628	>	private int lastRet = -1;
629
630		public boolean hasNext() {
631		return cursor != fence;
632		}
633
634		public E next() {
626	–	E result;
635		if (cursor == fence)
636		throw new NoSuchElementException();
637	<	if (((head - 1) & (elements.length - 1)) != fence ||
638	<	(result = elements[cursor]) == null)
637	>	cursor = (cursor - 1) & (elements.length - 1);
638	>	E result = elements[cursor];
639	>	if (head != fence || result == null)
640		throw new ConcurrentModificationException();
641		lastRet = cursor;
633	–	cursor = (cursor - 1) & (elements.length - 1);
642		return result;
643		}
644
645		public void remove() {
646	<	if (lastRet >= elements.length)
646	>	if (lastRet < 0)
647		throw new IllegalStateException();
648	<	if (!delete(lastRet))
648	>	if (!delete(lastRet)) {
649		cursor = (cursor + 1) & (elements.length - 1);
650	<	lastRet = elements.length;
651	<	fence = (head - 1) & (elements.length - 1);
650	>	fence = head;
651	>	}
652	>	lastRet = -1;
653		}
654		}
655
#	Line 826 | Line 835 | public class ArrayDeque<E> extends Abstr
835		// Read in all elements in the proper order.
836		for (int i = 0; i < size; i++)
837		elements[i] = (E)s.readObject();
829	–
838		}
839		}

Diff Legend

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