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.124 by jsr166, Sun May 6 19:35:51 2018 UTC vs.
Revision 1.127 by jsr166, Sun May 6 23:09:28 2018 UTC

# Line 242 | Line 242 | public class PriorityQueue<E> extends Ab
242          initElementsFromCollection(c);
243      }
244  
245 +    /** Ensures that queue[0] exists, helping peek() and poll(). */
246 +    private static Object[] ensureNonEmpty(Object[] es) {
247 +        return (es.length > 0) ? es : new Object[1];
248 +    }
249 +
250      private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
251          if (c.getClass() == PriorityQueue.class) {
252 <            this.queue = c.toArray();
252 >            this.queue = ensureNonEmpty(c.toArray());
253              this.size = c.size();
254          } else {
255              initFromCollection(c);
# Line 261 | Line 266 | public class PriorityQueue<E> extends Ab
266              for (Object e : es)
267                  if (e == null)
268                      throw new NullPointerException();
269 <        this.queue = es;
269 >        this.queue = ensureNonEmpty(es);
270          this.size = len;
271      }
272  
# Line 343 | Line 348 | public class PriorityQueue<E> extends Ab
348      }
349  
350      public E peek() {
351 <        return (size == 0) ? null : (E) queue[0];
351 >        return (E) queue[0];
352      }
353  
354      private int indexOf(Object o) {
# Line 579 | Line 584 | public class PriorityQueue<E> extends Ab
584      }
585  
586      public E poll() {
587 <        if (size == 0)
588 <            return null;
589 <        int s = --size;
590 <        modCount++;
591 <        E result = (E) queue[0];
592 <        E x = (E) queue[s];
593 <        queue[s] = null;
594 <        if (s != 0)
595 <            siftDown(0, x);
587 >        final Object[] es;
588 >        final E result;
589 >
590 >        if ((result = (E) ((es = queue)[0])) != null) {
591 >            modCount++;
592 >            final int n;
593 >            final E x = (E) es[(n = --size)];
594 >            es[n] = null;
595 >            if (n > 0) {
596 >                final Comparator<? super E> cmp;
597 >                if ((cmp = comparator) == null)
598 >                    siftDownComparable(0, x, es, n);
599 >                else
600 >                    siftDownUsingComparator(0, x, es, n, cmp);
601 >            }
602 >        }
603          return result;
604      }
605  
# Line 605 | Line 617 | public class PriorityQueue<E> extends Ab
617       */
618      E removeAt(int i) {
619          // assert i >= 0 && i < size;
620 +        final Object[] es = queue;
621          modCount++;
622          int s = --size;
623          if (s == i) // removed last element
624 <            queue[i] = null;
624 >            es[i] = null;
625          else {
626 <            E moved = (E) queue[s];
627 <            queue[s] = null;
626 >            E moved = (E) es[s];
627 >            es[s] = null;
628              siftDown(i, moved);
629 <            if (queue[i] == moved) {
629 >            if (es[i] == moved) {
630                  siftUp(i, moved);
631 <                if (queue[i] != moved)
631 >                if (es[i] != moved)
632                      return moved;
633              }
634          }
# Line 727 | Line 740 | public class PriorityQueue<E> extends Ab
740      private void heapify() {
741          final Object[] es = queue;
742          int n = size, i = (n >>> 1) - 1;
743 <        Comparator<? super E> cmp = comparator;
744 <        if (cmp == null)
743 >        final Comparator<? super E> cmp;
744 >        if ((cmp = comparator) == null)
745              for (; i >= 0; i--)
746                  siftDownComparable(i, (E) es[i], es, n);
747          else
# Line 790 | Line 803 | public class PriorityQueue<E> extends Ab
803          s.readInt();
804  
805          SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
806 <        queue = new Object[size];
806 >        final Object[] es = queue = new Object[Math.max(size, 1)];
807  
808          // Read in all elements.
796 –        final Object[] es = queue;
809          for (int i = 0, n = size; i < n; i++)
810              es[i] = s.readObject();
811  

Diff Legend

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