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.56 by jsr166, Mon Nov 28 02:35:46 2005 UTC

# 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 307 | Line 307 | public class PriorityQueue<E> extends Ab
307          }
308      }
309  
310 <    /**
310 >    /**
311       * Version of remove using reference equality, not equals.
312       * Needed by iterator.remove
313 <     *
313 >     *
314       * @param o element to be removed from this queue, if present
315       * @return <tt>true</tt> if removed.
316       */
# Line 435 | Line 435 | public class PriorityQueue<E> extends Ab
435          private int expectedModCount = modCount;
436  
437          public boolean hasNext() {
438 <            return cursor < size ||
438 >            return cursor < size ||
439                  (forgetMeNot != null && !forgetMeNot.isEmpty());
440          }
441  
442          public E next() {
443              if (expectedModCount != modCount)
444                  throw new ConcurrentModificationException();
445 <            if (cursor < size)
445 >            if (cursor < size)
446                  return (E) queue[lastRet = cursor++];
447              if (forgetMeNot != null) {
448                  lastRet = -1;
449                  lastRetElt = forgetMeNot.poll();
450 <                if (lastRetElt != null)
450 >                if (lastRetElt != null)
451                      return lastRetElt;
452              }
453              throw new NoSuchElementException();
# Line 461 | Line 461 | public class PriorityQueue<E> extends Ab
461              if (lastRet != -1) {
462                  E moved = PriorityQueue.this.removeAt(lastRet);
463                  lastRet = -1;
464 <                if (moved == null)
464 >                if (moved == null)
465                      cursor--;
466                  else {
467                      if (forgetMeNot == null)
468                          forgetMeNot = new ArrayDeque<E>();
469                      forgetMeNot.add(moved);
470 <                }            
470 >                }
471              } else {
472                  PriorityQueue.this.removeEq(lastRetElt);
473                  lastRetElt = null;
474 <            }
474 >            }
475              expectedModCount = modCount;
476          }
477  
# Line 525 | Line 525 | public class PriorityQueue<E> extends Ab
525              queue[i] = null;
526          else {
527              E moved = (E) queue[s];
528 <            queue[s] = null;  
528 >            queue[s] = null;
529              siftDown(i, moved);
530              if (queue[i] == moved) {
531                  siftUp(i, moved);
# Line 544 | Line 544 | public class PriorityQueue<E> extends Ab
544       * To simplify and speed up coercions and comparisons. the
545       * Comparable and Comparator versions are separated into different
546       * methods that are otherwise identical. (Similarly for siftDown.)
547 <     *
547 >     *
548       * @param k the position to fill
549       * @param x the item to insert
550       */
551      private void siftUp(int k, E x) {
552 <        if (comparator != null)
552 >        if (comparator != null)
553              siftUpUsingComparator(k, x);
554          else
555              siftUpComparable(k, x);
# Line 560 | Line 560 | public class PriorityQueue<E> extends Ab
560          while (k > 0) {
561              int parent = (k - 1) >>> 1;
562              Object e = queue[parent];
563 <            if (key.compareTo((E)e) >= 0)
563 >            if (key.compareTo((E)e) >= 0)
564                  break;
565              queue[k] = e;
566              k = parent;
# Line 572 | Line 572 | public class PriorityQueue<E> extends Ab
572          while (k > 0) {
573              int parent = (k - 1) >>> 1;
574              Object e = queue[parent];
575 <            if (comparator.compare(x, (E)e) >= 0)
575 >            if (comparator.compare(x, (E)e) >= 0)
576                  break;
577              queue[k] = e;
578              k = parent;
# Line 589 | Line 589 | public class PriorityQueue<E> extends Ab
589       * @param x the item to insert
590       */
591      private void siftDown(int k, E x) {
592 <        if (comparator != null)
592 >        if (comparator != null)
593              siftDownUsingComparator(k, x);
594          else
595              siftDownComparable(k, x);
# Line 621 | Line 621 | public class PriorityQueue<E> extends Ab
621              int right = child + 1;
622              if (right < size &&
623                  comparator.compare((E)c, (E)queue[right]) > 0)
624 <                c = queue[child = right];
625 <            if (comparator.compare(x, (E)c) <= 0)
624 >                c = queue[child = right];
625 >            if (comparator.compare(x, (E)c) <= 0)
626                  break;
627              queue[k] = c;
628              k = child;
# Line 635 | Line 635 | public class PriorityQueue<E> extends Ab
635       * assuming nothing about the order of the elements prior to the call.
636       */
637      private void heapify() {
638 <        for (int i = (size >>> 1) - 1; i >= 0; i--)
638 >        for (int i = (size >>> 1) - 1; i >= 0; i--)
639              siftDown(i, (E)queue[i]);
640      }
641  

Diff Legend

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