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.106 by jsr166, Tue Jun 16 23:06:01 2015 UTC vs.
Revision 1.123 by jsr166, Sun May 6 16:26:03 2018 UTC

# Line 1 | Line 1
1   /*
2 < * Copyright (c) 2003, 2013, Oracle and/or its affiliates. All rights reserved.
2 > * Copyright (c) 2003, 2018, Oracle and/or its affiliates. All rights reserved.
3   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4   *
5   * This code is free software; you can redistribute it and/or modify it
# Line 26 | Line 26
26   package java.util;
27  
28   import java.util.function.Consumer;
29 + import jdk.internal.misc.SharedSecrets;
30  
31   /**
32   * An unbounded priority {@linkplain Queue queue} based on a priority heap.
# Line 54 | Line 55 | import java.util.function.Consumer;
55   * <p>This class and its iterator implement all of the
56   * <em>optional</em> methods of the {@link Collection} and {@link
57   * Iterator} interfaces.  The Iterator provided in method {@link
58 < * #iterator()} is <em>not</em> guaranteed to traverse the elements of
58 > * #iterator()} and the Spliterator provided in method {@link #spliterator()}
59 > * are <em>not</em> guaranteed to traverse the elements of
60   * the priority queue in any particular order. If you need ordered
61   * traversal, consider using {@code Arrays.sort(pq.toArray())}.
62   *
# Line 72 | Line 74 | import java.util.function.Consumer;
74   * ({@code peek}, {@code element}, and {@code size}).
75   *
76   * <p>This class is a member of the
77 < * <a href="{@docRoot}/../technotes/guides/collections/index.html">
77 > * <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework">
78   * Java Collections Framework</a>.
79   *
80   * @since 1.5
# Line 99 | Line 101 | public class PriorityQueue<E> extends Ab
101      /**
102       * The number of elements in the priority queue.
103       */
104 <    private int size;
104 >    int size;
105  
106      /**
107       * The comparator, or null if priority queue uses elements'
# Line 337 | Line 339 | public class PriorityQueue<E> extends Ab
339          int i = size;
340          if (i >= queue.length)
341              grow(i + 1);
342 +        siftUp(i, e);
343          size = i + 1;
341 –        if (i == 0)
342 –            queue[0] = e;
343 –        else
344 –            siftUp(i, e);
344          return true;
345      }
346  
# Line 352 | Line 351 | public class PriorityQueue<E> extends Ab
351  
352      private int indexOf(Object o) {
353          if (o != null) {
354 <            for (int i = 0; i < size; i++)
355 <                if (o.equals(queue[i]))
354 >            final Object[] es = queue;
355 >            for (int i = 0, n = size; i < n; i++)
356 >                if (o.equals(es[i]))
357                      return i;
358          }
359          return -1;
# Line 381 | Line 381 | public class PriorityQueue<E> extends Ab
381      }
382  
383      /**
384 <     * Version of remove using reference equality, not equals.
385 <     * Needed by iterator.remove.
384 >     * Identity-based version for use in Itr.remove.
385       *
386       * @param o element to be removed from this queue, if present
388 –     * @return {@code true} if removed
387       */
388 <    boolean removeEq(Object o) {
389 <        for (int i = 0; i < size; i++) {
390 <            if (o == queue[i]) {
388 >    void removeEq(Object o) {
389 >        final Object[] es = queue;
390 >        for (int i = 0, n = size; i < n; i++) {
391 >            if (o == es[i]) {
392                  removeAt(i);
393 <                return true;
393 >                break;
394              }
395          }
397 –        return false;
396      }
397  
398      /**
# Line 524 | Line 522 | public class PriorityQueue<E> extends Ab
522           */
523          private int expectedModCount = modCount;
524  
525 +        Itr() {}                        // prevent access constructor creation
526 +
527          public boolean hasNext() {
528              return cursor < size ||
529                  (forgetMeNot != null && !forgetMeNot.isEmpty());
# Line 577 | Line 577 | public class PriorityQueue<E> extends Ab
577       */
578      public void clear() {
579          modCount++;
580 <        for (int i = 0; i < size; i++)
581 <            queue[i] = null;
580 >        final Object[] es = queue;
581 >        for (int i = 0, n = size; i < n; i++)
582 >            es[i] = null;
583          size = 0;
584      }
585  
# Line 609 | Line 610 | public class PriorityQueue<E> extends Ab
610       * avoid missing traversing elements.
611       */
612      @SuppressWarnings("unchecked")
613 <    private E removeAt(int i) {
613 >    E removeAt(int i) {
614          // assert i >= 0 && i < size;
615          modCount++;
616          int s = --size;
# Line 633 | Line 634 | public class PriorityQueue<E> extends Ab
634       * promoting x up the tree until it is greater than or equal to
635       * its parent, or is the root.
636       *
637 <     * To simplify and speed up coercions and comparisons. the
637 >     * To simplify and speed up coercions and comparisons, the
638       * Comparable and Comparator versions are separated into different
639       * methods that are otherwise identical. (Similarly for siftDown.)
640       *
# Line 729 | Line 730 | public class PriorityQueue<E> extends Ab
730      /**
731       * Establishes the heap invariant (described above) in the entire tree,
732       * assuming nothing about the order of the elements prior to the call.
733 +     * This classic algorithm due to Floyd (1964) is known to be O(size).
734       */
735      @SuppressWarnings("unchecked")
736      private void heapify() {
737 <        for (int i = (size >>> 1) - 1; i >= 0; i--)
738 <            siftDown(i, (E) queue[i]);
737 >        final Object[] es = queue;
738 >        int i = (size >>> 1) - 1;
739 >        if (comparator == null)
740 >            for (; i >= 0; i--)
741 >                siftDownComparable(i, (E) es[i]);
742 >        else
743 >            for (; i >= 0; i--)
744 >                siftDownUsingComparator(i, (E) es[i]);
745      }
746  
747      /**
# Line 752 | Line 760 | public class PriorityQueue<E> extends Ab
760      /**
761       * Saves this queue to a stream (that is, serializes it).
762       *
763 +     * @param s the stream
764 +     * @throws java.io.IOException if an I/O error occurs
765       * @serialData The length of the array backing the instance is
766       *             emitted (int), followed by all of its elements
767       *             (each an {@code Object}) in the proper order.
758 –     * @param s the stream
759 –     * @throws java.io.IOException if an I/O error occurs
768       */
769      private void writeObject(java.io.ObjectOutputStream s)
770          throws java.io.IOException {
# Line 767 | Line 775 | public class PriorityQueue<E> extends Ab
775          s.writeInt(Math.max(2, size + 1));
776  
777          // Write out all elements in the "proper order".
778 <        for (int i = 0; i < size; i++)
779 <            s.writeObject(queue[i]);
778 >        final Object[] es = queue;
779 >        for (int i = 0, n = size; i < n; i++)
780 >            s.writeObject(es[i]);
781      }
782  
783      /**
# Line 788 | Line 797 | public class PriorityQueue<E> extends Ab
797          // Read in (and discard) array length
798          s.readInt();
799  
800 +        SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
801          queue = new Object[size];
802  
803          // Read in all elements.
804 <        for (int i = 0; i < size; i++)
805 <            queue[i] = s.readObject();
804 >        final Object[] es = queue;
805 >        for (int i = 0, n = size; i < n; i++)
806 >            es[i] = s.readObject();
807  
808          // Elements are guaranteed to be in "proper order", but the
809          // spec has never explained what that might be.
# Line 802 | Line 813 | public class PriorityQueue<E> extends Ab
813      /**
814       * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
815       * and <em>fail-fast</em> {@link Spliterator} over the elements in this
816 <     * queue.
816 >     * queue. The spliterator does not traverse elements in any particular order
817 >     * (the {@link Spliterator#ORDERED ORDERED} characteristic is not reported).
818       *
819       * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
820       * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}.
# Line 813 | Line 825 | public class PriorityQueue<E> extends Ab
825       * @since 1.8
826       */
827      public final Spliterator<E> spliterator() {
828 <        return new PriorityQueueSpliterator<>(this, 0, -1, 0);
828 >        return new PriorityQueueSpliterator(0, -1, 0);
829      }
830  
831 <    static final class PriorityQueueSpliterator<E> implements Spliterator<E> {
820 <        /*
821 <         * This is very similar to ArrayList Spliterator, except for
822 <         * extra null checks.
823 <         */
824 <        private final PriorityQueue<E> pq;
831 >    final class PriorityQueueSpliterator implements Spliterator<E> {
832          private int index;            // current index, modified on advance/split
833          private int fence;            // -1 until first use
834          private int expectedModCount; // initialized when fence set
835  
836 <        /** Creates new spliterator covering the given range */
837 <        PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence,
831 <                             int expectedModCount) {
832 <            this.pq = pq;
836 >        /** Creates new spliterator covering the given range. */
837 >        PriorityQueueSpliterator(int origin, int fence, int expectedModCount) {
838              this.index = origin;
839              this.fence = fence;
840              this.expectedModCount = expectedModCount;
# Line 838 | Line 843 | public class PriorityQueue<E> extends Ab
843          private int getFence() { // initialize fence to size on first use
844              int hi;
845              if ((hi = fence) < 0) {
846 <                expectedModCount = pq.modCount;
847 <                hi = fence = pq.size;
846 >                expectedModCount = modCount;
847 >                hi = fence = size;
848              }
849              return hi;
850          }
851  
852 <        public PriorityQueueSpliterator<E> trySplit() {
852 >        public PriorityQueueSpliterator trySplit() {
853              int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
854              return (lo >= mid) ? null :
855 <                new PriorityQueueSpliterator<>(pq, lo, index = mid,
851 <                                               expectedModCount);
855 >                new PriorityQueueSpliterator(lo, index = mid, expectedModCount);
856          }
857  
858          @SuppressWarnings("unchecked")
859          public void forEachRemaining(Consumer<? super E> action) {
856 –            int i, hi, mc; // hoist accesses and checks from loop
857 –            PriorityQueue<E> q; Object[] a;
860              if (action == null)
861                  throw new NullPointerException();
862 <            if ((q = pq) != null && (a = q.queue) != null) {
863 <                if ((hi = fence) < 0) {
864 <                    mc = q.modCount;
865 <                    hi = q.size;
866 <                }
867 <                else
868 <                    mc = expectedModCount;
867 <                if ((i = index) >= 0 && (index = hi) <= a.length) {
868 <                    for (E e;; ++i) {
869 <                        if (i < hi) {
870 <                            if ((e = (E) a[i]) == null) // must be CME
871 <                                break;
872 <                            action.accept(e);
873 <                        }
874 <                        else if (q.modCount != mc)
875 <                            break;
876 <                        else
877 <                            return;
878 <                    }
879 <                }
862 >            if (fence < 0) { fence = size; expectedModCount = modCount; }
863 >            final Object[] a = queue;
864 >            int i, hi; E e;
865 >            for (i = index, index = hi = fence; i < hi; i++) {
866 >                if ((e = (E) a[i]) == null)
867 >                    break;      // must be CME
868 >                action.accept(e);
869              }
870 <            throw new ConcurrentModificationException();
870 >            if (modCount != expectedModCount)
871 >                throw new ConcurrentModificationException();
872          }
873  
874 +        @SuppressWarnings("unchecked")
875          public boolean tryAdvance(Consumer<? super E> action) {
876              if (action == null)
877                  throw new NullPointerException();
878 <            int hi = getFence(), lo = index;
879 <            if (lo >= 0 && lo < hi) {
880 <                index = lo + 1;
881 <                @SuppressWarnings("unchecked") E e = (E)pq.queue[lo];
882 <                if (e == null)
878 >            if (fence < 0) { fence = size; expectedModCount = modCount; }
879 >            int i;
880 >            if ((i = index) < fence) {
881 >                index = i + 1;
882 >                E e;
883 >                if ((e = (E) queue[i]) == null
884 >                    || modCount != expectedModCount)
885                      throw new ConcurrentModificationException();
886                  action.accept(e);
894 –                if (pq.modCount != expectedModCount)
895 –                    throw new ConcurrentModificationException();
887                  return true;
888              }
889              return false;
890          }
891  
892          public long estimateSize() {
893 <            return (long) (getFence() - index);
893 >            return getFence() - index;
894          }
895  
896          public int characteristics() {
897              return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL;
898          }
899      }
900 +
901 +    /**
902 +     * @throws NullPointerException {@inheritDoc}
903 +     */
904 +    @SuppressWarnings("unchecked")
905 +    public void forEach(Consumer<? super E> action) {
906 +        Objects.requireNonNull(action);
907 +        final int expectedModCount = modCount;
908 +        final Object[] es = queue;
909 +        for (int i = 0, n = size; i < n; i++)
910 +            action.accept((E) es[i]);
911 +        if (expectedModCount != modCount)
912 +            throw new ConcurrentModificationException();
913 +    }
914   }

Diff Legend

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