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.26 by tim, Fri Aug 8 20:05:07 2003 UTC vs.
Revision 1.34 by dholmes, Wed Aug 27 01:33:50 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.PriorityBlockingQueue} 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 176 | Line 190 | public class PriorityQueue<E> extends Ab
190       */
191      public PriorityQueue(Collection<? extends E> c) {
192          initializeArray(c);
193 <        if (c instanceof SortedSet<? extends E>) {
194 <            SortedSet<? extends E> s = (SortedSet<? extends E>) c;
193 >        if (c instanceof SortedSet) {
194 >            // @fixme double-cast workaround for compiler
195 >            SortedSet<? extends E> s = (SortedSet<? extends E>) (SortedSet)c;
196              comparator = (Comparator<? super E>)s.comparator();
197              fillFromSorted(s);
198 <        } else if (c instanceof PriorityQueue<? extends E>) {
198 >        } else if (c instanceof PriorityQueue) {
199              PriorityQueue<? extends E> s = (PriorityQueue<? extends E>) c;
200              comparator = (Comparator<? super E>)s.comparator();
201              fillFromSorted(s);
# Line 416 | Line 431 | public class PriorityQueue<E> extends Ab
431              checkForComodification();
432  
433              PriorityQueue.this.remove(lastRet);
434 <            if (lastRet < cursor)
420 <                cursor--;
434 >            cursor--;
435              lastRet = 0;
436              expectedModCount = modCount;
437          }
# Line 449 | 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       *
452 –     * XXX: Could further special-case i==size, but is it worth it?
453 –     * XXX: Could special-case i==0, but is it worth it?
466       */
467      private E remove(int i) {
468          assert i <= size;
# Line 505 | 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 514 | 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