ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/PriorityQueue.java
(Generate patch)

Comparing jsr166/src/main/java/util/PriorityQueue.java (file contents):
Revision 1.28 by dl, Wed Aug 13 14:11:59 2003 UTC vs.
Revision 1.32 by dl, Mon Aug 25 23:47:01 2003 UTC

# Line 28 | Line 28
28   * elements are added to a priority queue, its capacity grows
29   * automatically.  The details of the growth policy are not specified.
30   *
31 + * <p>The Iterator provided in method {@link #iterator()} is <em>not</em>
32 + * guaranteed to traverse the elements of the PriorityQueue in any
33 + * particular order. If you need ordered traversal, consider using
34 + * <tt>Arrays.sort(pq.toArray())</tt>.
35 + *
36 + * <p> <strong>Note that this implementation is not synchronized.</strong>
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.
41 + *
42 + *
43   * <p>Implementation note: this implementation provides O(log(n)) time
44   * for the insertion methods (<tt>offer</tt>, <tt>poll</tt>,
45   * <tt>remove()</tt> and <tt>add</tt>) methods; linear time for the
# Line 44 | 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 417 | Line 431 | public class PriorityQueue<E> extends Ab
431              checkForComodification();
432  
433              PriorityQueue.this.remove(lastRet);
434 <            if (lastRet < cursor)
421 <                cursor--;
434 >            cursor--;
435              lastRet = 0;
436              expectedModCount = modCount;
437          }
# Line 450 | 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       *
453 –     * XXX: Could further special-case i==size, but is it worth it?
454 –     * XXX: Could special-case i==0, but is it worth it?
466       */
467      private E remove(int i) {
468          assert i <= size;
# Line 506 | 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 515 | 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