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.99 by jsr166, Fri Apr 11 21:15:44 2014 UTC vs.
Revision 1.113 by jsr166, Wed Nov 30 03:31:47 2016 UTC

# Line 1 | Line 1
1   /*
2 < * Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved.
2 > * Copyright (c) 2003, 2013, 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 24 | Line 24
24   */
25  
26   package java.util;
27 +
28   import java.util.function.Consumer;
28 – import java.util.stream.Stream;
29  
30   /**
31   * An unbounded priority {@linkplain Queue queue} based on a priority heap.
# Line 54 | Line 54 | import java.util.stream.Stream;
54   * <p>This class and its iterator implement all of the
55   * <em>optional</em> methods of the {@link Collection} and {@link
56   * Iterator} interfaces.  The Iterator provided in method {@link
57 < * #iterator()} is <em>not</em> guaranteed to traverse the elements of
57 > * #iterator()} and the Spliterator provided in method {@link #spliterator()}
58 > * are <em>not</em> guaranteed to traverse the elements of
59   * the priority queue in any particular order. If you need ordered
60   * traversal, consider using {@code Arrays.sort(pq.toArray())}.
61   *
# Line 77 | Line 78 | import java.util.stream.Stream;
78   *
79   * @since 1.5
80   * @author Josh Bloch, Doug Lea
81 < * @param <E> the type of elements held in this collection
81 > * @param <E> the type of elements held in this queue
82   */
83   public class PriorityQueue<E> extends AbstractQueue<E>
84      implements java.io.Serializable {
# Line 99 | Line 100 | public class PriorityQueue<E> extends Ab
100      /**
101       * The number of elements in the priority queue.
102       */
103 <    private int size;
103 >    int size;
104  
105      /**
106       * The comparator, or null if priority queue uses elements'
# Line 111 | Line 112 | public class PriorityQueue<E> extends Ab
112       * The number of times this priority queue has been
113       * <i>structurally modified</i>.  See AbstractList for gory details.
114       */
115 <    transient int modCount = 0; // non-private to simplify nested class access
115 >    transient int modCount;     // non-private to simplify nested class access
116  
117      /**
118       * Creates a {@code PriorityQueue} with the default initial
# Line 136 | Line 137 | public class PriorityQueue<E> extends Ab
137      }
138  
139      /**
140 +     * Creates a {@code PriorityQueue} with the default initial capacity and
141 +     * whose elements are ordered according to the specified comparator.
142 +     *
143 +     * @param  comparator the comparator that will be used to order this
144 +     *         priority queue.  If {@code null}, the {@linkplain Comparable
145 +     *         natural ordering} of the elements will be used.
146 +     * @since 1.8
147 +     */
148 +    public PriorityQueue(Comparator<? super E> comparator) {
149 +        this(DEFAULT_INITIAL_CAPACITY, comparator);
150 +    }
151 +
152 +    /**
153       * Creates a {@code PriorityQueue} with the specified initial capacity
154       * that orders its elements according to the specified comparator.
155       *
# Line 245 | Line 259 | public class PriorityQueue<E> extends Ab
259              a = Arrays.copyOf(a, a.length, Object[].class);
260          int len = a.length;
261          if (len == 1 || this.comparator != null)
262 <            for (int i = 0; i < len; i++)
263 <                if (a[i] == null)
262 >            for (Object e : a)
263 >                if (e == null)
264                      throw new NullPointerException();
265          this.queue = a;
266          this.size = a.length;
# Line 324 | Line 338 | public class PriorityQueue<E> extends Ab
338          int i = size;
339          if (i >= queue.length)
340              grow(i + 1);
341 +        siftUp(i, e);
342          size = i + 1;
328 –        if (i == 0)
329 –            queue[0] = e;
330 –        else
331 –            siftUp(i, e);
343          return true;
344      }
345  
# Line 393 | Line 404 | public class PriorityQueue<E> extends Ab
404       * @return {@code true} if this queue contains the specified element
405       */
406      public boolean contains(Object o) {
407 <        return indexOf(o) != -1;
407 >        return indexOf(o) >= 0;
408      }
409  
410      /**
# Line 435 | Line 446 | public class PriorityQueue<E> extends Ab
446       * The following code can be used to dump the queue into a newly
447       * allocated array of {@code String}:
448       *
449 <     *  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
449 >     * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
450       *
451       * Note that {@code toArray(new Object[0])} is identical in function to
452       * {@code toArray()}.
# Line 596 | Line 607 | public class PriorityQueue<E> extends Ab
607       * avoid missing traversing elements.
608       */
609      @SuppressWarnings("unchecked")
610 <    private E removeAt(int i) {
610 >    E removeAt(int i) {
611          // assert i >= 0 && i < size;
612          modCount++;
613          int s = --size;
# Line 716 | Line 727 | public class PriorityQueue<E> extends Ab
727      /**
728       * Establishes the heap invariant (described above) in the entire tree,
729       * assuming nothing about the order of the elements prior to the call.
730 +     * This classic algorithm due to Floyd (1964) is known to be O(size).
731       */
732      @SuppressWarnings("unchecked")
733      private void heapify() {
# Line 739 | Line 751 | public class PriorityQueue<E> extends Ab
751      /**
752       * Saves this queue to a stream (that is, serializes it).
753       *
754 +     * @param s the stream
755 +     * @throws java.io.IOException if an I/O error occurs
756       * @serialData The length of the array backing the instance is
757       *             emitted (int), followed by all of its elements
758       *             (each an {@code Object}) in the proper order.
745 –     * @param s the stream
746 –     * @throws java.io.IOException if an I/O error occurs
759       */
760      private void writeObject(java.io.ObjectOutputStream s)
761          throws java.io.IOException {
# Line 786 | Line 798 | public class PriorityQueue<E> extends Ab
798          heapify();
799      }
800  
789 –    public Spliterator<E> spliterator() {
790 –        return new PriorityQueueSpliterator<E>(this, 0, -1, 0);
791 –    }
792 –
801      /**
802 <     * This is very similar to ArrayList Spliterator, except for extra
803 <     * null checks.
804 <     */
805 <    static final class PriorityQueueSpliterator<E> implements Spliterator<E> {
806 <        private final PriorityQueue<E> pq;
802 >     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
803 >     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
804 >     * queue. The spliterator does not traverse elements in any particular order
805 >     * (the {@link Spliterator#ORDERED ORDERED} characteristic is not reported).
806 >     *
807 >     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
808 >     * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}.
809 >     * Overriding implementations should document the reporting of additional
810 >     * characteristic values.
811 >     *
812 >     * @return a {@code Spliterator} over the elements in this queue
813 >     * @since 1.8
814 >     */
815 >    public final Spliterator<E> spliterator() {
816 >        return new PriorityQueueSpliterator(0, -1, 0);
817 >    }
818 >
819 >    final class PriorityQueueSpliterator implements Spliterator<E> {
820 >        /*
821 >         * This is very similar to ArrayList Spliterator, except for
822 >         * extra null checks.
823 >         */
824          private int index;            // current index, modified on advance/split
825          private int fence;            // -1 until first use
826          private int expectedModCount; // initialized when fence set
827  
828 <        /** Creates new spliterator covering the given range */
829 <        PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence,
805 <                             int expectedModCount) {
806 <            this.pq = pq;
828 >        /** Creates new spliterator covering the given range. */
829 >        PriorityQueueSpliterator(int origin, int fence, int expectedModCount) {
830              this.index = origin;
831              this.fence = fence;
832              this.expectedModCount = expectedModCount;
# Line 812 | Line 835 | public class PriorityQueue<E> extends Ab
835          private int getFence() { // initialize fence to size on first use
836              int hi;
837              if ((hi = fence) < 0) {
838 <                expectedModCount = pq.modCount;
839 <                hi = fence = pq.size;
838 >                expectedModCount = modCount;
839 >                hi = fence = size;
840              }
841              return hi;
842          }
843  
844 <        public Spliterator<E> trySplit() {
844 >        public PriorityQueueSpliterator trySplit() {
845              int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
846              return (lo >= mid) ? null :
847 <                new PriorityQueueSpliterator<E>(pq, lo, index = mid,
825 <                                                expectedModCount);
847 >                new PriorityQueueSpliterator(lo, index = mid, expectedModCount);
848          }
849  
850          @SuppressWarnings("unchecked")
851          public void forEachRemaining(Consumer<? super E> action) {
852              int i, hi, mc; // hoist accesses and checks from loop
853 <            PriorityQueue<E> q; Object[] a;
853 >            final Object[] a;
854              if (action == null)
855                  throw new NullPointerException();
856 <            if ((q = pq) != null && (a = q.queue) != null) {
856 >            if ((a = queue) != null) {
857                  if ((hi = fence) < 0) {
858 <                    mc = q.modCount;
859 <                    hi = q.size;
858 >                    mc = modCount;
859 >                    hi = size;
860                  }
861                  else
862                      mc = expectedModCount;
# Line 845 | Line 867 | public class PriorityQueue<E> extends Ab
867                                  break;
868                              action.accept(e);
869                          }
870 <                        else if (q.modCount != mc)
870 >                        else if (modCount != mc)
871                              break;
872                          else
873                              return;
# Line 856 | Line 878 | public class PriorityQueue<E> extends Ab
878          }
879  
880          public boolean tryAdvance(Consumer<? super E> action) {
881 +            if (action == null)
882 +                throw new NullPointerException();
883              int hi = getFence(), lo = index;
884              if (lo >= 0 && lo < hi) {
885                  index = lo + 1;
886 <                @SuppressWarnings("unchecked") E e = (E)pq.queue[lo];
886 >                @SuppressWarnings("unchecked") E e = (E)queue[lo];
887                  if (e == null)
888                      throw new ConcurrentModificationException();
889                  action.accept(e);
890 <                if (pq.modCount != expectedModCount)
890 >                if (modCount != expectedModCount)
891                      throw new ConcurrentModificationException();
892                  return true;
893              }
# Line 871 | Line 895 | public class PriorityQueue<E> extends Ab
895          }
896  
897          public long estimateSize() {
898 <            return (long) (getFence() - index);
898 >            return getFence() - index;
899          }
900  
901          public int characteristics() {

Diff Legend

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