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

Diff Legend

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