ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/PriorityQueue.java

Comparing jsr166/src/main/java/util/PriorityQueue.java (file contents):
Revision 1.29 by dl, Sun Aug 24 23:31:53 2003 UTC vs.
Revision 1.34 by dholmes, Wed Aug 27 01:33:50 2003 UTC

#	Line 37 | Line 37
37		* Multiple threads should not access a <tt>PriorityQueue</tt>
38		* instance concurrently if any of the threads modifies the list
39		* structurally. Instead, use the thread-safe {@link
40	<	* java.util.concurrent.BlockingPriorityQueue} class.
40	>	* java.util.concurrent.PriorityBlockingQueue} class.
41		*
42		*
43		* <p>Implementation note: this implementation provides O(log(n)) time
#	Line 56 | Line 56
56		public class PriorityQueue<E> extends AbstractQueue<E>
57		implements Queue<E>, java.io.Serializable {
58
59	+	private static final long serialVersionUID = -7720805057305804111L;
60	+
61		private static final int DEFAULT_INITIAL_CAPACITY = 11;
62
63		/**
#	Line 429 | Line 431 | public class PriorityQueue<E> extends Ab
431		checkForComodification();
432
433		PriorityQueue.this.remove(lastRet);
434	<	if (lastRet < cursor)
433	<	cursor--;
434	>	cursor--;
435		lastRet = 0;
436		expectedModCount = modCount;
437		}
#	Line 462 | Line 463 | public class PriorityQueue<E> extends Ab
463		* Removes and returns the ith element from queue.  Recall
464		* that queue is one-based, so 1 <= i <= size.
465		*
465	–	* XXX: Could further special-case i==size, but is it worth it?
466	–	* XXX: Could special-case i==0, but is it worth it?
466		*/
467		private E remove(int i) {
468		assert i <= size;
#	Line 518 | Line 517 | public class PriorityQueue<E> extends Ab
517		private void fixDown(int k) {
518		int j;
519		if (comparator == null) {
520	<	while ((j = k << 1) <= size) {
520	>	while ((j = k << 1) <= size && (j > 0)) {
521		if (j<size && ((Comparable<E>)queue[j]).compareTo((E)queue[j+1]) > 0)
522		j++; // j indexes smallest kid
523		if (((Comparable<E>)queue[k]).compareTo((E)queue[j]) <= 0)
#	Line 527 | Line 526 | public class PriorityQueue<E> extends Ab
526		k = j;
527		}
528		} else {
529	<	while ((j = k << 1) <= size) {
529	>	while ((j = k << 1) <= size && (j > 0)) {
530		if (j < size && comparator.compare((E)queue[j], (E)queue[j+1]) > 0)
531		j++; // j indexes smallest kid
532		if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)

Diff Legend

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