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.55 by dl, Sun Nov 27 20:41:02 2005 UTC vs.
Revision 1.61 by jsr166, Tue Feb 7 20:54:24 2006 UTC

# Line 1 | Line 1
1   /*
2 < * @(#)PriorityQueue.java       1.8 05/08/27
2 > * %W% %E%
3   *
4 < * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
4 > * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
5   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6   */
7  
8   package java.util;
9 – import java.util.*; // for javadoc (till 6280605 is fixed)
9  
10   /**
11   * An unbounded priority {@linkplain Queue queue} based on a priority
# Line 136 | Line 135 | public class PriorityQueue<E> extends Ab
135          this.queue = new Object[initialCapacity];
136          this.comparator = comparator;
137      }
138 <    
138 >
139      /**
140       * Creates a <tt>PriorityQueue</tt> containing the elements in the
141       * specified collection.   If the specified collection is an
# Line 155 | Line 154 | public class PriorityQueue<E> extends Ab
154       */
155      public PriorityQueue(Collection<? extends E> c) {
156          initFromCollection(c);
157 <        if (c instanceof SortedSet)
157 >        if (c instanceof SortedSet)
158              comparator = (Comparator<? super E>)
159                  ((SortedSet<? extends E>)c).comparator();
160 <        else if (c instanceof PriorityQueue)
160 >        else if (c instanceof PriorityQueue)
161              comparator = (Comparator<? super E>)
162                  ((PriorityQueue<? extends E>)c).comparator();
163          else {
# Line 215 | Line 214 | public class PriorityQueue<E> extends Ab
214              a = Arrays.copyOf(a, a.length, Object[].class);
215          queue = a;
216          size = a.length;
217 <    }        
217 >    }
218  
219      /**
220       * Increases the capacity of the array.
# Line 229 | Line 228 | public class PriorityQueue<E> extends Ab
228          // Double size if small; else grow by 50%
229          int newCapacity = ((oldCapacity < 64)?
230                             ((oldCapacity + 1) * 2):
231 <                           ((oldCapacity * 3) / 2));
231 >                           ((oldCapacity / 2) * 3));
232 >        if (newCapacity < 0) // overflow
233 >            newCapacity = Integer.MAX_VALUE;
234          if (newCapacity < minCapacity)
235              newCapacity = minCapacity;
236          queue = Arrays.copyOf(queue, newCapacity);
# Line 307 | Line 308 | public class PriorityQueue<E> extends Ab
308          }
309      }
310  
311 <    /**
311 >    /**
312       * Version of remove using reference equality, not equals.
313 <     * Needed by iterator.remove
314 <     *
313 >     * Needed by iterator.remove.
314 >     *
315       * @param o element to be removed from this queue, if present
316 <     * @return <tt>true</tt> if removed.
316 >     * @return <tt>true</tt> if removed
317       */
318      boolean removeEq(Object o) {
319          for (int i = 0; i < size; i++) {
# Line 344 | Line 345 | public class PriorityQueue<E> extends Ab
345       * maintained by this list.  (In other words, this method must allocate
346       * a new array).  The caller is thus free to modify the returned array.
347       *
348 <     * @return an array containing all of the elements in this queue.
348 >     * @return an array containing all of the elements in this queue
349       */
350      public Object[] toArray() {
351          return Arrays.copyOf(queue, size);
# Line 435 | Line 436 | public class PriorityQueue<E> extends Ab
436          private int expectedModCount = modCount;
437  
438          public boolean hasNext() {
439 <            return cursor < size ||
439 >            return cursor < size ||
440                  (forgetMeNot != null && !forgetMeNot.isEmpty());
441          }
442  
443          public E next() {
444              if (expectedModCount != modCount)
445                  throw new ConcurrentModificationException();
446 <            if (cursor < size)
446 >            if (cursor < size)
447                  return (E) queue[lastRet = cursor++];
448              if (forgetMeNot != null) {
449                  lastRet = -1;
450                  lastRetElt = forgetMeNot.poll();
451 <                if (lastRetElt != null)
451 >                if (lastRetElt != null)
452                      return lastRetElt;
453              }
454              throw new NoSuchElementException();
# Line 461 | Line 462 | public class PriorityQueue<E> extends Ab
462              if (lastRet != -1) {
463                  E moved = PriorityQueue.this.removeAt(lastRet);
464                  lastRet = -1;
465 <                if (moved == null)
465 >                if (moved == null)
466                      cursor--;
467                  else {
468                      if (forgetMeNot == null)
469                          forgetMeNot = new ArrayDeque<E>();
470                      forgetMeNot.add(moved);
471 <                }            
471 >                }
472              } else {
473                  PriorityQueue.this.removeEq(lastRetElt);
474                  lastRetElt = null;
475 <            }
475 >            }
476              expectedModCount = modCount;
477          }
478  
# Line 525 | Line 526 | public class PriorityQueue<E> extends Ab
526              queue[i] = null;
527          else {
528              E moved = (E) queue[s];
529 <            queue[s] = null;  
529 >            queue[s] = null;
530              siftDown(i, moved);
531              if (queue[i] == moved) {
532                  siftUp(i, moved);
# Line 544 | Line 545 | public class PriorityQueue<E> extends Ab
545       * To simplify and speed up coercions and comparisons. the
546       * Comparable and Comparator versions are separated into different
547       * methods that are otherwise identical. (Similarly for siftDown.)
548 <     *
548 >     *
549       * @param k the position to fill
550       * @param x the item to insert
551       */
552      private void siftUp(int k, E x) {
553 <        if (comparator != null)
553 >        if (comparator != null)
554              siftUpUsingComparator(k, x);
555          else
556              siftUpComparable(k, x);
# Line 560 | Line 561 | public class PriorityQueue<E> extends Ab
561          while (k > 0) {
562              int parent = (k - 1) >>> 1;
563              Object e = queue[parent];
564 <            if (key.compareTo((E)e) >= 0)
564 >            if (key.compareTo((E)e) >= 0)
565                  break;
566              queue[k] = e;
567              k = parent;
# Line 572 | Line 573 | public class PriorityQueue<E> extends Ab
573          while (k > 0) {
574              int parent = (k - 1) >>> 1;
575              Object e = queue[parent];
576 <            if (comparator.compare(x, (E)e) >= 0)
576 >            if (comparator.compare(x, (E)e) >= 0)
577                  break;
578              queue[k] = e;
579              k = parent;
# Line 589 | Line 590 | public class PriorityQueue<E> extends Ab
590       * @param x the item to insert
591       */
592      private void siftDown(int k, E x) {
593 <        if (comparator != null)
593 >        if (comparator != null)
594              siftDownUsingComparator(k, x);
595          else
596              siftDownComparable(k, x);
# Line 621 | Line 622 | public class PriorityQueue<E> extends Ab
622              int right = child + 1;
623              if (right < size &&
624                  comparator.compare((E)c, (E)queue[right]) > 0)
625 <                c = queue[child = right];
626 <            if (comparator.compare(x, (E)c) <= 0)
625 >                c = queue[child = right];
626 >            if (comparator.compare(x, (E)c) <= 0)
627                  break;
628              queue[k] = c;
629              k = child;
# Line 635 | Line 636 | public class PriorityQueue<E> extends Ab
636       * assuming nothing about the order of the elements prior to the call.
637       */
638      private void heapify() {
639 <        for (int i = (size >>> 1) - 1; i >= 0; i--)
639 >        for (int i = (size >>> 1) - 1; i >= 0; i--)
640              siftDown(i, (E)queue[i]);
641      }
642  

Diff Legend

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