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.90 by jsr166, Mon Feb 18 01:30:23 2013 UTC vs.
Revision 1.109 by jsr166, Wed Jun 1 16:08:04 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 – import java.util.stream.Streams;
29  
30   /**
31   * An unbounded priority {@linkplain Queue queue} based on a priority heap.
# Line 66 | Line 65 | import java.util.stream.Streams;
65   * java.util.concurrent.PriorityBlockingQueue} class.
66   *
67   * <p>Implementation note: this implementation provides
68 < * O(log(n)) time for the enqueing and dequeing methods
68 > * O(log(n)) time for the enqueuing and dequeuing methods
69   * ({@code offer}, {@code poll}, {@code remove()} and {@code add});
70   * linear time for the {@code remove(Object)} and {@code contains(Object)}
71   * methods; and constant time for the retrieval methods
# Line 78 | Line 77 | import java.util.stream.Streams;
77   *
78   * @since 1.5
79   * @author Josh Bloch, Doug Lea
80 < * @param <E> the type of elements held in this collection
80 > * @param <E> the type of elements held in this queue
81   */
82   public class PriorityQueue<E> extends AbstractQueue<E>
83      implements java.io.Serializable {
# Line 100 | Line 99 | public class PriorityQueue<E> extends Ab
99      /**
100       * The number of elements in the priority queue.
101       */
102 <    private int size = 0;
102 >    int size;
103  
104      /**
105       * The comparator, or null if priority queue uses elements'
# Line 112 | Line 111 | public class PriorityQueue<E> extends Ab
111       * The number of times this priority queue has been
112       * <i>structurally modified</i>.  See AbstractList for gory details.
113       */
114 <    transient int modCount = 0; // non-private to simplify nested class access
114 >    transient int modCount;     // non-private to simplify nested class access
115  
116      /**
117       * Creates a {@code PriorityQueue} with the default initial
# Line 137 | Line 136 | public class PriorityQueue<E> extends Ab
136      }
137  
138      /**
139 +     * Creates a {@code PriorityQueue} with the default initial capacity and
140 +     * whose elements are ordered according to the specified comparator.
141 +     *
142 +     * @param  comparator the comparator that will be used to order this
143 +     *         priority queue.  If {@code null}, the {@linkplain Comparable
144 +     *         natural ordering} of the elements will be used.
145 +     * @since 1.8
146 +     */
147 +    public PriorityQueue(Comparator<? super E> comparator) {
148 +        this(DEFAULT_INITIAL_CAPACITY, comparator);
149 +    }
150 +
151 +    /**
152       * Creates a {@code PriorityQueue} with the specified initial capacity
153       * that orders its elements according to the specified comparator.
154       *
# Line 246 | Line 258 | public class PriorityQueue<E> extends Ab
258              a = Arrays.copyOf(a, a.length, Object[].class);
259          int len = a.length;
260          if (len == 1 || this.comparator != null)
261 <            for (int i = 0; i < len; i++)
262 <                if (a[i] == null)
261 >            for (Object e : a)
262 >                if (e == null)
263                      throw new NullPointerException();
264          this.queue = a;
265          this.size = a.length;
# Line 325 | Line 337 | public class PriorityQueue<E> extends Ab
337          int i = size;
338          if (i >= queue.length)
339              grow(i + 1);
340 +        siftUp(i, e);
341          size = i + 1;
329 –        if (i == 0)
330 –            queue[0] = e;
331 –        else
332 –            siftUp(i, e);
342          return true;
343      }
344  
# Line 394 | Line 403 | public class PriorityQueue<E> extends Ab
403       * @return {@code true} if this queue contains the specified element
404       */
405      public boolean contains(Object o) {
406 <        return indexOf(o) != -1;
406 >        return indexOf(o) >= 0;
407      }
408  
409      /**
# Line 436 | Line 445 | public class PriorityQueue<E> extends Ab
445       * The following code can be used to dump the queue into a newly
446       * allocated array of {@code String}:
447       *
448 <     *  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
448 >     * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
449       *
450       * Note that {@code toArray(new Object[0])} is identical in function to
451       * {@code toArray()}.
# Line 477 | Line 486 | public class PriorityQueue<E> extends Ab
486           * Index (into queue array) of element to be returned by
487           * subsequent call to next.
488           */
489 <        private int cursor = 0;
489 >        private int cursor;
490  
491          /**
492           * Index of element returned by most recent call to next,
# Line 497 | Line 506 | public class PriorityQueue<E> extends Ab
506           * We expect that most iterations, even those involving removals,
507           * will not need to store elements in this field.
508           */
509 <        private ArrayDeque<E> forgetMeNot = null;
509 >        private ArrayDeque<E> forgetMeNot;
510  
511          /**
512           * Element returned by the most recent call to next iff that
513           * element was drawn from the forgetMeNot list.
514           */
515 <        private E lastRetElt = null;
515 >        private E lastRetElt;
516  
517          /**
518           * The modCount value that the iterator believes that the backing
# Line 597 | Line 606 | public class PriorityQueue<E> extends Ab
606       * avoid missing traversing elements.
607       */
608      @SuppressWarnings("unchecked")
609 <    private E removeAt(int i) {
609 >    E removeAt(int i) {
610          // assert i >= 0 && i < size;
611          modCount++;
612          int s = --size;
# Line 744 | Line 753 | public class PriorityQueue<E> extends Ab
753       *             emitted (int), followed by all of its elements
754       *             (each an {@code Object}) in the proper order.
755       * @param s the stream
756 +     * @throws java.io.IOException if an I/O error occurs
757       */
758      private void writeObject(java.io.ObjectOutputStream s)
759          throws java.io.IOException {
# Line 763 | Line 773 | public class PriorityQueue<E> extends Ab
773       * (that is, deserializes it).
774       *
775       * @param s the stream
776 +     * @throws ClassNotFoundException if the class of a serialized object
777 +     *         could not be found
778 +     * @throws java.io.IOException if an I/O error occurs
779       */
780      private void readObject(java.io.ObjectInputStream s)
781          throws java.io.IOException, ClassNotFoundException {
# Line 783 | Line 796 | public class PriorityQueue<E> extends Ab
796          heapify();
797      }
798  
799 <    final Spliterator<E> spliterator() {
800 <        return new PriorityQueueSpliterator<E>(this, 0, -1, 0);
801 <    }
802 <
803 <    public Stream<E> stream() {
804 <        return Streams.stream(spliterator());
805 <    }
806 <
807 <    public Stream<E> parallelStream() {
808 <        return Streams.parallelStream(spliterator());
799 >    /**
800 >     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
801 >     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
802 >     * queue.
803 >     *
804 >     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
805 >     * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}.
806 >     * Overriding implementations should document the reporting of additional
807 >     * characteristic values.
808 >     *
809 >     * @return a {@code Spliterator} over the elements in this queue
810 >     * @since 1.8
811 >     */
812 >    public final Spliterator<E> spliterator() {
813 >        return new PriorityQueueSpliterator<>(this, 0, -1, 0);
814      }
815  
816      static final class PriorityQueueSpliterator<E> implements Spliterator<E> {
# Line 805 | Line 823 | public class PriorityQueue<E> extends Ab
823          private int fence;            // -1 until first use
824          private int expectedModCount; // initialized when fence set
825  
826 <        /** Create new spliterator covering the given  range */
826 >        /** Creates new spliterator covering the given range. */
827          PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence,
828 <                             int expectedModCount) {
828 >                                 int expectedModCount) {
829              this.pq = pq;
830              this.index = origin;
831              this.fence = fence;
# Line 826 | Line 844 | public class PriorityQueue<E> extends Ab
844          public PriorityQueueSpliterator<E> trySplit() {
845              int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
846              return (lo >= mid) ? null :
847 <                new PriorityQueueSpliterator<E>(pq, lo, index = mid,
848 <                                                expectedModCount);
847 >                new PriorityQueueSpliterator<>(pq, lo, index = mid,
848 >                                               expectedModCount);
849          }
850  
851          @SuppressWarnings("unchecked")
852 <        public void forEach(Consumer<? super E> action) {
852 >        public void forEachRemaining(Consumer<? super E> action) {
853              int i, hi, mc; // hoist accesses and checks from loop
854              PriorityQueue<E> q; Object[] a;
855              if (action == null)
# Line 861 | Line 879 | public class PriorityQueue<E> extends Ab
879          }
880  
881          public boolean tryAdvance(Consumer<? super E> action) {
882 +            if (action == null)
883 +                throw new NullPointerException();
884              int hi = getFence(), lo = index;
885              if (lo >= 0 && lo < hi) {
886                  index = lo + 1;

Diff Legend

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