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.3 by tim, Sun May 18 20:36:01 2003 UTC vs.
Revision 1.124 by jsr166, Sun May 6 19:35:51 2018 UTC

# Line 1 | Line 1
1 package java.util;
2
1   /*
2 < * Todo
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
6 > * under the terms of the GNU General Public License version 2 only, as
7 > * published by the Free Software Foundation.  Oracle designates this
8 > * particular file as subject to the "Classpath" exception as provided
9 > * by Oracle in the LICENSE file that accompanied this code.
10 > *
11 > * This code is distributed in the hope that it will be useful, but WITHOUT
12 > * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 > * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 > * version 2 for more details (a copy is included in the LICENSE file that
15 > * accompanied this code).
16   *
17 < *   1) Make it serializable.
17 > * You should have received a copy of the GNU General Public License version
18 > * 2 along with this work; if not, write to the Free Software Foundation,
19 > * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 > *
21 > * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 > * or visit www.oracle.com if you need additional information or have any
23 > * questions.
24   */
25  
26 + package java.util;
27 +
28 + import java.util.function.Consumer;
29 + import jdk.internal.misc.SharedSecrets;
30 +
31   /**
32 < * An unbounded priority queue based on a priority heap.  This queue orders
33 < * elements according to the order specified at creation time.  This order is
34 < * specified as for {@link TreeSet} and {@link TreeMap}: Elements are ordered
35 < * either according to their <i>natural order</i> (see {@link Comparable}), or
36 < * according to a {@link Comparator}, depending on which constructor is used.
37 < * The {@link #peek}, {@link #poll}, and {@link #remove} methods return the
38 < * minimal element with respect to the specified ordering.  If multiple
39 < * these elements are tied for least value, no guarantees are made as to
40 < * which of elements is returned.
41 < *
42 < * <p>Each priority queue has a <i>capacity</i>.  The capacity is the size of
43 < * the array used to store the elements on the queue.  It is always at least
44 < * as large as the queue size.  As elements are added to a priority list,
45 < * its capacity grows automatically.  The details of the growth policy are not
32 > * An unbounded priority {@linkplain Queue queue} based on a priority heap.
33 > * The elements of the priority queue are ordered according to their
34 > * {@linkplain Comparable natural ordering}, or by a {@link Comparator}
35 > * provided at queue construction time, depending on which constructor is
36 > * used.  A priority queue does not permit {@code null} elements.
37 > * A priority queue relying on natural ordering also does not permit
38 > * insertion of non-comparable objects (doing so may result in
39 > * {@code ClassCastException}).
40 > *
41 > * <p>The <em>head</em> of this queue is the <em>least</em> element
42 > * with respect to the specified ordering.  If multiple elements are
43 > * tied for least value, the head is one of those elements -- ties are
44 > * broken arbitrarily.  The queue retrieval operations {@code poll},
45 > * {@code remove}, {@code peek}, and {@code element} access the
46 > * element at the head of the queue.
47 > *
48 > * <p>A priority queue is unbounded, but has an internal
49 > * <i>capacity</i> governing the size of an array used to store the
50 > * elements on the queue.  It is always at least as large as the queue
51 > * size.  As elements are added to a priority queue, its capacity
52 > * grows automatically.  The details of the growth policy are not
53   * specified.
54   *
55 < *<p>Implementation note: this implementation provides O(log(n)) time for
56 < * the <tt>offer</tt>, <tt>poll</tt>, <tt>remove()</tt> and <tt>add</tt>
57 < * methods; linear time for the <tt>remove(Object)</tt> and
58 < * <tt>contains</tt> methods; and constant time for the <tt>peek</tt>,
59 < * <tt>element</tt>, and <tt>size</tt> methods.
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()} 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 > *
63 > * <p><strong>Note that this implementation is not synchronized.</strong>
64 > * Multiple threads should not access a {@code PriorityQueue}
65 > * instance concurrently if any of the threads modifies the queue.
66 > * Instead, use the thread-safe {@link
67 > * java.util.concurrent.PriorityBlockingQueue} class.
68 > *
69 > * <p>Implementation note: this implementation provides
70 > * O(log(n)) time for the enqueuing and dequeuing methods
71 > * ({@code offer}, {@code poll}, {@code remove()} and {@code add});
72 > * linear time for the {@code remove(Object)} and {@code contains(Object)}
73 > * methods; and constant time for the retrieval methods
74 > * ({@code peek}, {@code element}, and {@code size}).
75   *
76   * <p>This class is a member of the
77 < * <a href="{@docRoot}/../guide/collections/index.html">
77 > * <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework">
78   * Java Collections Framework</a>.
79 + *
80 + * @since 1.5
81 + * @author Josh Bloch, Doug Lea
82 + * @param <E> the type of elements held in this queue
83   */
84 + @SuppressWarnings("unchecked")
85   public class PriorityQueue<E> extends AbstractQueue<E>
86 <                              implements Queue<E>
87 < {
86 >    implements java.io.Serializable {
87 >
88 >    private static final long serialVersionUID = -7720805057305804111L;
89 >
90      private static final int DEFAULT_INITIAL_CAPACITY = 11;
91  
92      /**
93 <     * Priority queue represented as a balanced binary heap: the two children
94 <     * of queue[n] are queue[2*n] and queue[2*n + 1].  The priority queue is
95 <     * ordered by comparator, or by the elements' natural ordering, if
96 <     * comparator is null:  For each node n in the heap, and each descendant
97 <     * of n, d, n <= d.
98 <     *
48 <     * The element with the lowest value is in queue[1] (assuming the queue is
49 <     * nonempty). A one-based array is used in preference to the traditional
50 <     * zero-based array to simplify parent and child calculations.
51 <     *
52 <     * queue.length must be >= 2, even if size == 0.
93 >     * Priority queue represented as a balanced binary heap: the two
94 >     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
95 >     * priority queue is ordered by comparator, or by the elements'
96 >     * natural ordering, if comparator is null: For each node n in the
97 >     * heap and each descendant d of n, n <= d.  The element with the
98 >     * lowest value is in queue[0], assuming the queue is nonempty.
99       */
100 <    private E[] queue;
100 >    transient Object[] queue; // non-private to simplify nested class access
101  
102      /**
103       * The number of elements in the priority queue.
104       */
105 <    private int size = 0;
105 >    int size;
106  
107      /**
108       * The comparator, or null if priority queue uses elements'
109       * natural ordering.
110       */
111 <    private final Comparator<E> comparator;
111 >    private final Comparator<? super E> comparator;
112  
113      /**
114       * The number of times this priority queue has been
115       * <i>structurally modified</i>.  See AbstractList for gory details.
116       */
117 <    private int modCount = 0;
117 >    transient int modCount;     // non-private to simplify nested class access
118  
119      /**
120 <     * Create a new priority queue with the default initial capacity (11)
121 <     * that orders its elements according to their natural ordering.
120 >     * Creates a {@code PriorityQueue} with the default initial
121 >     * capacity (11) that orders its elements according to their
122 >     * {@linkplain Comparable natural ordering}.
123       */
124      public PriorityQueue() {
125 <        this(DEFAULT_INITIAL_CAPACITY);
125 >        this(DEFAULT_INITIAL_CAPACITY, null);
126      }
127  
128      /**
129 <     * Create a new priority queue with the specified initial capacity
130 <     * that orders its elements according to their natural ordering.
129 >     * Creates a {@code PriorityQueue} with the specified initial
130 >     * capacity that orders its elements according to their
131 >     * {@linkplain Comparable natural ordering}.
132       *
133 <     * @param initialCapacity the initial capacity for this priority queue.
133 >     * @param initialCapacity the initial capacity for this priority queue
134 >     * @throws IllegalArgumentException if {@code initialCapacity} is less
135 >     *         than 1
136       */
137      public PriorityQueue(int initialCapacity) {
138          this(initialCapacity, null);
139      }
140  
141      /**
142 <     * Create a new priority queue with the specified initial capacity (11)
143 <     * that orders its elements according to the specified comparator.
142 >     * Creates a {@code PriorityQueue} with the default initial capacity and
143 >     * whose elements are ordered according to the specified comparator.
144       *
145 <     * @param initialCapacity the initial capacity for this priority queue.
146 <     * @param comparator the comparator used to order this priority queue.
145 >     * @param  comparator the comparator that will be used to order this
146 >     *         priority queue.  If {@code null}, the {@linkplain Comparable
147 >     *         natural ordering} of the elements will be used.
148 >     * @since 1.8
149       */
150 <    public PriorityQueue(int initialCapacity, Comparator<E> comparator) {
150 >    public PriorityQueue(Comparator<? super E> comparator) {
151 >        this(DEFAULT_INITIAL_CAPACITY, comparator);
152 >    }
153 >
154 >    /**
155 >     * Creates a {@code PriorityQueue} with the specified initial capacity
156 >     * that orders its elements according to the specified comparator.
157 >     *
158 >     * @param  initialCapacity the initial capacity for this priority queue
159 >     * @param  comparator the comparator that will be used to order this
160 >     *         priority queue.  If {@code null}, the {@linkplain Comparable
161 >     *         natural ordering} of the elements will be used.
162 >     * @throws IllegalArgumentException if {@code initialCapacity} is
163 >     *         less than 1
164 >     */
165 >    public PriorityQueue(int initialCapacity,
166 >                         Comparator<? super E> comparator) {
167 >        // Note: This restriction of at least one is not actually needed,
168 >        // but continues for 1.5 compatibility
169          if (initialCapacity < 1)
170 <            initialCapacity = 1;
171 <        queue = new E[initialCapacity + 1];
170 >            throw new IllegalArgumentException();
171 >        this.queue = new Object[initialCapacity];
172          this.comparator = comparator;
173      }
174  
175      /**
176 <     * Create a new priority queue containing the elements in the specified
177 <     * collection.  The priority queue has an initial capacity of 110% of the
178 <     * size of the specified collection. If the specified collection
179 <     * implements the {@link Sorted} interface, the priority queue will be
180 <     * sorted according to the same comparator, or according to its elements'
181 <     * natural order if the collection is sorted according to its elements'
112 <     * natural order.  If the specified collection does not implement the
113 <     * <tt>Sorted</tt> interface, the priority queue is ordered according to
114 <     * its elements' natural order.
176 >     * Creates a {@code PriorityQueue} containing the elements in the
177 >     * specified collection.  If the specified collection is an instance of
178 >     * a {@link SortedSet} or is another {@code PriorityQueue}, this
179 >     * priority queue will be ordered according to the same ordering.
180 >     * Otherwise, this priority queue will be ordered according to the
181 >     * {@linkplain Comparable natural ordering} of its elements.
182       *
183 <     * @param initialElements the collection whose elements are to be placed
184 <     *        into this priority queue.
183 >     * @param  c the collection whose elements are to be placed
184 >     *         into this priority queue
185       * @throws ClassCastException if elements of the specified collection
186       *         cannot be compared to one another according to the priority
187 <     *         queue's ordering.
188 <     * @throws NullPointerException if the specified collection or an
189 <     *         element of the specified collection is <tt>null</tt>.
190 <     */
191 <    public PriorityQueue(Collection<E> initialElements) {
192 <        int sz = initialElements.size();
193 <        int initialCapacity = (int)Math.min((sz * 110L) / 100,
194 <                                            Integer.MAX_VALUE - 1);
195 <        if (initialCapacity < 1)
196 <            initialCapacity = 1;
197 <        queue = new E[initialCapacity + 1];
187 >     *         queue's ordering
188 >     * @throws NullPointerException if the specified collection or any
189 >     *         of its elements are null
190 >     */
191 >    public PriorityQueue(Collection<? extends E> c) {
192 >        if (c instanceof SortedSet<?>) {
193 >            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
194 >            this.comparator = (Comparator<? super E>) ss.comparator();
195 >            initElementsFromCollection(ss);
196 >        }
197 >        else if (c instanceof PriorityQueue<?>) {
198 >            PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
199 >            this.comparator = (Comparator<? super E>) pq.comparator();
200 >            initFromPriorityQueue(pq);
201 >        }
202 >        else {
203 >            this.comparator = null;
204 >            initFromCollection(c);
205 >        }
206 >    }
207  
208 <        /* Commented out to compile with generics compiler
208 >    /**
209 >     * Creates a {@code PriorityQueue} containing the elements in the
210 >     * specified priority queue.  This priority queue will be
211 >     * ordered according to the same ordering as the given priority
212 >     * queue.
213 >     *
214 >     * @param  c the priority queue whose elements are to be placed
215 >     *         into this priority queue
216 >     * @throws ClassCastException if elements of {@code c} cannot be
217 >     *         compared to one another according to {@code c}'s
218 >     *         ordering
219 >     * @throws NullPointerException if the specified priority queue or any
220 >     *         of its elements are null
221 >     */
222 >    public PriorityQueue(PriorityQueue<? extends E> c) {
223 >        this.comparator = (Comparator<? super E>) c.comparator();
224 >        initFromPriorityQueue(c);
225 >    }
226  
227 <        if (initialElements instanceof Sorted) {
228 <            comparator = ((Sorted)initialElements).comparator();
229 <            for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
230 <                queue[++size] = i.next();
227 >    /**
228 >     * Creates a {@code PriorityQueue} containing the elements in the
229 >     * specified sorted set.   This priority queue will be ordered
230 >     * according to the same ordering as the given sorted set.
231 >     *
232 >     * @param  c the sorted set whose elements are to be placed
233 >     *         into this priority queue
234 >     * @throws ClassCastException if elements of the specified sorted
235 >     *         set cannot be compared to one another according to the
236 >     *         sorted set's ordering
237 >     * @throws NullPointerException if the specified sorted set or any
238 >     *         of its elements are null
239 >     */
240 >    public PriorityQueue(SortedSet<? extends E> c) {
241 >        this.comparator = (Comparator<? super E>) c.comparator();
242 >        initElementsFromCollection(c);
243 >    }
244 >
245 >    private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
246 >        if (c.getClass() == PriorityQueue.class) {
247 >            this.queue = c.toArray();
248 >            this.size = c.size();
249          } else {
250 <        */
140 <        {
141 <            comparator = null;
142 <            for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
143 <                add(i.next());
250 >            initFromCollection(c);
251          }
252      }
253  
254 <    // Queue Methods
254 >    private void initElementsFromCollection(Collection<? extends E> c) {
255 >        Object[] es = c.toArray();
256 >        int len = es.length;
257 >        // If c.toArray incorrectly doesn't return Object[], copy it.
258 >        if (es.getClass() != Object[].class)
259 >            es = Arrays.copyOf(es, len, Object[].class);
260 >        if (len == 1 || this.comparator != null)
261 >            for (Object e : es)
262 >                if (e == null)
263 >                    throw new NullPointerException();
264 >        this.queue = es;
265 >        this.size = len;
266 >    }
267  
268      /**
269 <     * Remove and return the minimal element from this priority queue if
151 <     * it contains one or more elements, otherwise <tt>null</tt>.  The term
152 <     * <i>minimal</i> is defined according to this priority queue's order.
269 >     * Initializes queue array with elements from the given Collection.
270       *
271 <     * @return the minimal element from this priority queue if it contains
155 <     *         one or more elements, otherwise <tt>null</tt>.
271 >     * @param c the collection
272       */
273 <    public E poll() {
274 <        if (size == 0)
275 <            return null;
276 <        return remove(1);
273 >    private void initFromCollection(Collection<? extends E> c) {
274 >        initElementsFromCollection(c);
275 >        heapify();
276 >    }
277 >
278 >    /**
279 >     * The maximum size of array to allocate.
280 >     * Some VMs reserve some header words in an array.
281 >     * Attempts to allocate larger arrays may result in
282 >     * OutOfMemoryError: Requested array size exceeds VM limit
283 >     */
284 >    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
285 >
286 >    /**
287 >     * Increases the capacity of the array.
288 >     *
289 >     * @param minCapacity the desired minimum capacity
290 >     */
291 >    private void grow(int minCapacity) {
292 >        int oldCapacity = queue.length;
293 >        // Double size if small; else grow by 50%
294 >        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
295 >                                         (oldCapacity + 2) :
296 >                                         (oldCapacity >> 1));
297 >        // overflow-conscious code
298 >        if (newCapacity - MAX_ARRAY_SIZE > 0)
299 >            newCapacity = hugeCapacity(minCapacity);
300 >        queue = Arrays.copyOf(queue, newCapacity);
301 >    }
302 >
303 >    private static int hugeCapacity(int minCapacity) {
304 >        if (minCapacity < 0) // overflow
305 >            throw new OutOfMemoryError();
306 >        return (minCapacity > MAX_ARRAY_SIZE) ?
307 >            Integer.MAX_VALUE :
308 >            MAX_ARRAY_SIZE;
309 >    }
310 >
311 >    /**
312 >     * Inserts the specified element into this priority queue.
313 >     *
314 >     * @return {@code true} (as specified by {@link Collection#add})
315 >     * @throws ClassCastException if the specified element cannot be
316 >     *         compared with elements currently in this priority queue
317 >     *         according to the priority queue's ordering
318 >     * @throws NullPointerException if the specified element is null
319 >     */
320 >    public boolean add(E e) {
321 >        return offer(e);
322      }
323  
324      /**
325 <     * Return, but do not remove, the minimal element from the priority queue,
165 <     * or <tt>null</tt> if the queue is empty.  The term <i>minimal</i> is
166 <     * defined according to this priority queue's order.  This method returns
167 <     * the same object reference that would be returned by by the
168 <     * <tt>poll</tt> method.  The two methods differ in that this method
169 <     * does not remove the element from the priority queue.
325 >     * Inserts the specified element into this priority queue.
326       *
327 <     * @return the minimal element from this priority queue if it contains
328 <     *         one or more elements, otherwise <tt>null</tt>.
327 >     * @return {@code true} (as specified by {@link Queue#offer})
328 >     * @throws ClassCastException if the specified element cannot be
329 >     *         compared with elements currently in this priority queue
330 >     *         according to the priority queue's ordering
331 >     * @throws NullPointerException if the specified element is null
332       */
333 +    public boolean offer(E e) {
334 +        if (e == null)
335 +            throw new NullPointerException();
336 +        modCount++;
337 +        int i = size;
338 +        if (i >= queue.length)
339 +            grow(i + 1);
340 +        siftUp(i, e);
341 +        size = i + 1;
342 +        return true;
343 +    }
344 +
345      public E peek() {
346 <        return queue[1];
346 >        return (size == 0) ? null : (E) queue[0];
347      }
348  
349 <    // Collection Methods
349 >    private int indexOf(Object o) {
350 >        if (o != null) {
351 >            final Object[] es = queue;
352 >            for (int i = 0, n = size; i < n; i++)
353 >                if (o.equals(es[i]))
354 >                    return i;
355 >        }
356 >        return -1;
357 >    }
358  
359      /**
360 <     * Removes a single instance of the specified element from this priority
361 <     * queue, if it is present.  Returns true if this collection contained the
362 <     * specified element (or equivalently, if this collection changed as a
360 >     * Removes a single instance of the specified element from this queue,
361 >     * if it is present.  More formally, removes an element {@code e} such
362 >     * that {@code o.equals(e)}, if this queue contains one or more such
363 >     * elements.  Returns {@code true} if and only if this queue contained
364 >     * the specified element (or equivalently, if this queue changed as a
365       * result of the call).
366       *
367 <     * @param o element to be removed from this collection, if present.
368 <     * @return <tt>true</tt> if this collection changed as a result of the
188 <     *         call
189 <     * @throws ClassCastException if the specified element cannot be compared
190 <     *            with elements currently in the priority queue according
191 <     *            to the priority queue's ordering.
192 <     * @throws NullPointerException if the specified element is null.
367 >     * @param o element to be removed from this queue, if present
368 >     * @return {@code true} if this queue changed as a result of the call
369       */
370 <    public boolean remove(Object element) {
371 <        if (element == null)
372 <            throw new NullPointerException();
370 >    public boolean remove(Object o) {
371 >        int i = indexOf(o);
372 >        if (i == -1)
373 >            return false;
374 >        else {
375 >            removeAt(i);
376 >            return true;
377 >        }
378 >    }
379  
380 <        if (comparator == null) {
381 <            for (int i = 1; i <= size; i++) {
382 <                if (((Comparable)queue[i]).compareTo(element) == 0) {
383 <                    remove(i);
384 <                    return true;
385 <                }
386 <            }
387 <        } else {
388 <            for (int i = 1; i <= size; i++) {
389 <                if (comparator.compare(queue[i], (E) element) == 0) {
390 <                    remove(i);
209 <                    return true;
210 <                }
380 >    /**
381 >     * Identity-based version for use in Itr.remove.
382 >     *
383 >     * @param o element to be removed from this queue, if present
384 >     */
385 >    void removeEq(Object o) {
386 >        final Object[] es = queue;
387 >        for (int i = 0, n = size; i < n; i++) {
388 >            if (o == es[i]) {
389 >                removeAt(i);
390 >                break;
391              }
392          }
213        return false;
393      }
394  
395      /**
396 <     * Returns an iterator over the elements in this priority queue.  The
397 <     * first element returned by this iterator is the same element that
398 <     * would be returned by a call to <tt>peek</tt>.
396 >     * Returns {@code true} if this queue contains the specified element.
397 >     * More formally, returns {@code true} if and only if this queue contains
398 >     * at least one element {@code e} such that {@code o.equals(e)}.
399 >     *
400 >     * @param o object to be checked for containment in this queue
401 >     * @return {@code true} if this queue contains the specified element
402 >     */
403 >    public boolean contains(Object o) {
404 >        return indexOf(o) >= 0;
405 >    }
406 >
407 >    /**
408 >     * Returns an array containing all of the elements in this queue.
409 >     * The elements are in no particular order.
410       *
411 <     * @return an <tt>Iterator</tt> over the elements in this priority queue.
411 >     * <p>The returned array will be "safe" in that no references to it are
412 >     * maintained by this queue.  (In other words, this method must allocate
413 >     * a new array).  The caller is thus free to modify the returned array.
414 >     *
415 >     * <p>This method acts as bridge between array-based and collection-based
416 >     * APIs.
417 >     *
418 >     * @return an array containing all of the elements in this queue
419 >     */
420 >    public Object[] toArray() {
421 >        return Arrays.copyOf(queue, size);
422 >    }
423 >
424 >    /**
425 >     * Returns an array containing all of the elements in this queue; the
426 >     * runtime type of the returned array is that of the specified array.
427 >     * The returned array elements are in no particular order.
428 >     * If the queue fits in the specified array, it is returned therein.
429 >     * Otherwise, a new array is allocated with the runtime type of the
430 >     * specified array and the size of this queue.
431 >     *
432 >     * <p>If the queue fits in the specified array with room to spare
433 >     * (i.e., the array has more elements than the queue), the element in
434 >     * the array immediately following the end of the collection is set to
435 >     * {@code null}.
436 >     *
437 >     * <p>Like the {@link #toArray()} method, this method acts as bridge between
438 >     * array-based and collection-based APIs.  Further, this method allows
439 >     * precise control over the runtime type of the output array, and may,
440 >     * under certain circumstances, be used to save allocation costs.
441 >     *
442 >     * <p>Suppose {@code x} is a queue known to contain only strings.
443 >     * The following code can be used to dump the queue into a newly
444 >     * allocated array of {@code String}:
445 >     *
446 >     * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
447 >     *
448 >     * Note that {@code toArray(new Object[0])} is identical in function to
449 >     * {@code toArray()}.
450 >     *
451 >     * @param a the array into which the elements of the queue are to
452 >     *          be stored, if it is big enough; otherwise, a new array of the
453 >     *          same runtime type is allocated for this purpose.
454 >     * @return an array containing all of the elements in this queue
455 >     * @throws ArrayStoreException if the runtime type of the specified array
456 >     *         is not a supertype of the runtime type of every element in
457 >     *         this queue
458 >     * @throws NullPointerException if the specified array is null
459 >     */
460 >    public <T> T[] toArray(T[] a) {
461 >        final int size = this.size;
462 >        if (a.length < size)
463 >            // Make a new array of a's runtime type, but my contents:
464 >            return (T[]) Arrays.copyOf(queue, size, a.getClass());
465 >        System.arraycopy(queue, 0, a, 0, size);
466 >        if (a.length > size)
467 >            a[size] = null;
468 >        return a;
469 >    }
470 >
471 >    /**
472 >     * Returns an iterator over the elements in this queue. The iterator
473 >     * does not return the elements in any particular order.
474 >     *
475 >     * @return an iterator over the elements in this queue
476       */
477      public Iterator<E> iterator() {
478          return new Itr();
479      }
480  
481 <    private class Itr implements Iterator<E> {
481 >    private final class Itr implements Iterator<E> {
482          /**
483           * Index (into queue array) of element to be returned by
484           * subsequent call to next.
485           */
486 <        int cursor = 1;
486 >        private int cursor;
487 >
488 >        /**
489 >         * Index of element returned by most recent call to next,
490 >         * unless that element came from the forgetMeNot list.
491 >         * Set to -1 if element is deleted by a call to remove.
492 >         */
493 >        private int lastRet = -1;
494 >
495 >        /**
496 >         * A queue of elements that were moved from the unvisited portion of
497 >         * the heap into the visited portion as a result of "unlucky" element
498 >         * removals during the iteration.  (Unlucky element removals are those
499 >         * that require a siftup instead of a siftdown.)  We must visit all of
500 >         * the elements in this list to complete the iteration.  We do this
501 >         * after we've completed the "normal" iteration.
502 >         *
503 >         * We expect that most iterations, even those involving removals,
504 >         * will not need to store elements in this field.
505 >         */
506 >        private ArrayDeque<E> forgetMeNot;
507  
508          /**
509 <         * Index of element returned by most recent call to next or
510 <         * previous.  Reset to 0 if this element is deleted by a call
237 <         * to remove.
509 >         * Element returned by the most recent call to next iff that
510 >         * element was drawn from the forgetMeNot list.
511           */
512 <        int lastRet = 0;
512 >        private E lastRetElt;
513  
514          /**
515           * The modCount value that the iterator believes that the backing
516 <         * List should have.  If this expectation is violated, the iterator
516 >         * Queue should have.  If this expectation is violated, the iterator
517           * has detected concurrent modification.
518           */
519 <        int expectedModCount = modCount;
519 >        private int expectedModCount = modCount;
520 >
521 >        Itr() {}                        // prevent access constructor creation
522  
523          public boolean hasNext() {
524 <            return cursor <= size;
524 >            return cursor < size ||
525 >                (forgetMeNot != null && !forgetMeNot.isEmpty());
526          }
527  
528          public E next() {
529 <            checkForComodification();
530 <            if (cursor > size)
531 <                throw new NoSuchElementException();
532 <            E result = queue[cursor];
533 <            lastRet = cursor++;
534 <            return result;
529 >            if (expectedModCount != modCount)
530 >                throw new ConcurrentModificationException();
531 >            if (cursor < size)
532 >                return (E) queue[lastRet = cursor++];
533 >            if (forgetMeNot != null) {
534 >                lastRet = -1;
535 >                lastRetElt = forgetMeNot.poll();
536 >                if (lastRetElt != null)
537 >                    return lastRetElt;
538 >            }
539 >            throw new NoSuchElementException();
540          }
541  
542          public void remove() {
543 <            if (lastRet == 0)
543 >            if (expectedModCount != modCount)
544 >                throw new ConcurrentModificationException();
545 >            if (lastRet != -1) {
546 >                E moved = PriorityQueue.this.removeAt(lastRet);
547 >                lastRet = -1;
548 >                if (moved == null)
549 >                    cursor--;
550 >                else {
551 >                    if (forgetMeNot == null)
552 >                        forgetMeNot = new ArrayDeque<>();
553 >                    forgetMeNot.add(moved);
554 >                }
555 >            } else if (lastRetElt != null) {
556 >                PriorityQueue.this.removeEq(lastRetElt);
557 >                lastRetElt = null;
558 >            } else {
559                  throw new IllegalStateException();
560 <            checkForComodification();
265 <
266 <            PriorityQueue.this.remove(lastRet);
267 <            if (lastRet < cursor)
268 <                cursor--;
269 <            lastRet = 0;
560 >            }
561              expectedModCount = modCount;
562          }
563 +    }
564  
565 <        final void checkForComodification() {
566 <            if (modCount != expectedModCount)
275 <                throw new ConcurrentModificationException();
276 <        }
565 >    public int size() {
566 >        return size;
567      }
568  
569      /**
570 <     * Returns the number of elements in this priority queue.
571 <     *
282 <     * @return the number of elements in this priority queue.
570 >     * Removes all of the elements from this priority queue.
571 >     * The queue will be empty after this call returns.
572       */
573 <    public int size() {
574 <        return size;
573 >    public void clear() {
574 >        modCount++;
575 >        final Object[] es = queue;
576 >        for (int i = 0, n = size; i < n; i++)
577 >            es[i] = null;
578 >        size = 0;
579 >    }
580 >
581 >    public E poll() {
582 >        if (size == 0)
583 >            return null;
584 >        int s = --size;
585 >        modCount++;
586 >        E result = (E) queue[0];
587 >        E x = (E) queue[s];
588 >        queue[s] = null;
589 >        if (s != 0)
590 >            siftDown(0, x);
591 >        return result;
592      }
593  
594      /**
595 <     * Add the specified element to this priority queue.
595 >     * Removes the ith element from queue.
596       *
597 <     * @param element the element to add.
598 <     * @return true
599 <     * @throws ClassCastException if the specified element cannot be compared
600 <     *            with elements currently in the priority queue according
601 <     *            to the priority queue's ordering.
602 <     * @throws NullPointerException if the specified element is null.
597 >     * Normally this method leaves the elements at up to i-1,
598 >     * inclusive, untouched.  Under these circumstances, it returns
599 >     * null.  Occasionally, in order to maintain the heap invariant,
600 >     * it must swap a later element of the list with one earlier than
601 >     * i.  Under these circumstances, this method returns the element
602 >     * that was previously at the end of the list and is now at some
603 >     * position before i. This fact is used by iterator.remove so as to
604 >     * avoid missing traversing elements.
605       */
606 <    public boolean offer(E element) {
607 <        if (element == null)
300 <            throw new NullPointerException();
606 >    E removeAt(int i) {
607 >        // assert i >= 0 && i < size;
608          modCount++;
609 +        int s = --size;
610 +        if (s == i) // removed last element
611 +            queue[i] = null;
612 +        else {
613 +            E moved = (E) queue[s];
614 +            queue[s] = null;
615 +            siftDown(i, moved);
616 +            if (queue[i] == moved) {
617 +                siftUp(i, moved);
618 +                if (queue[i] != moved)
619 +                    return moved;
620 +            }
621 +        }
622 +        return null;
623 +    }
624  
625 <        // Grow backing store if necessary
626 <        if (++size == queue.length) {
627 <            E[] newQueue = new E[2 * queue.length];
628 <            System.arraycopy(queue, 0, newQueue, 0, size);
629 <            queue = newQueue;
625 >    /**
626 >     * Inserts item x at position k, maintaining heap invariant by
627 >     * promoting x up the tree until it is greater than or equal to
628 >     * its parent, or is the root.
629 >     *
630 >     * To simplify and speed up coercions and comparisons, the
631 >     * Comparable and Comparator versions are separated into different
632 >     * methods that are otherwise identical. (Similarly for siftDown.)
633 >     *
634 >     * @param k the position to fill
635 >     * @param x the item to insert
636 >     */
637 >    private void siftUp(int k, E x) {
638 >        if (comparator != null)
639 >            siftUpUsingComparator(k, x, queue, comparator);
640 >        else
641 >            siftUpComparable(k, x, queue);
642 >    }
643 >
644 >    private static <T> void siftUpComparable(int k, T x, Object[] es) {
645 >        Comparable<? super T> key = (Comparable<? super T>) x;
646 >        while (k > 0) {
647 >            int parent = (k - 1) >>> 1;
648 >            Object e = es[parent];
649 >            if (key.compareTo((T) e) >= 0)
650 >                break;
651 >            es[k] = e;
652 >            k = parent;
653          }
654 +        es[k] = key;
655 +    }
656  
657 <        queue[size] = element;
658 <        fixUp(size);
659 <        return true;
657 >    private static <T> void siftUpUsingComparator(
658 >        int k, T x, Object[] es, Comparator<? super T> cmp) {
659 >        while (k > 0) {
660 >            int parent = (k - 1) >>> 1;
661 >            Object e = es[parent];
662 >            if (cmp.compare(x, (T) e) >= 0)
663 >                break;
664 >            es[k] = e;
665 >            k = parent;
666 >        }
667 >        es[k] = x;
668 >    }
669 >
670 >    /**
671 >     * Inserts item x at position k, maintaining heap invariant by
672 >     * demoting x down the tree repeatedly until it is less than or
673 >     * equal to its children or is a leaf.
674 >     *
675 >     * @param k the position to fill
676 >     * @param x the item to insert
677 >     */
678 >    private void siftDown(int k, E x) {
679 >        if (comparator != null)
680 >            siftDownUsingComparator(k, x, queue, size, comparator);
681 >        else
682 >            siftDownComparable(k, x, queue, size);
683 >    }
684 >
685 >    private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
686 >        // assert n > 0;
687 >        Comparable<? super T> key = (Comparable<? super T>)x;
688 >        int half = n >>> 1;           // loop while a non-leaf
689 >        while (k < half) {
690 >            int child = (k << 1) + 1; // assume left child is least
691 >            Object c = es[child];
692 >            int right = child + 1;
693 >            if (right < n &&
694 >                ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
695 >                c = es[child = right];
696 >            if (key.compareTo((T) c) <= 0)
697 >                break;
698 >            es[k] = c;
699 >            k = child;
700 >        }
701 >        es[k] = key;
702 >    }
703 >
704 >    private static <T> void siftDownUsingComparator(
705 >        int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
706 >        // assert n > 0;
707 >        int half = n >>> 1;
708 >        while (k < half) {
709 >            int child = (k << 1) + 1;
710 >            Object c = es[child];
711 >            int right = child + 1;
712 >            if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
713 >                c = es[child = right];
714 >            if (cmp.compare(x, (T) c) <= 0)
715 >                break;
716 >            es[k] = c;
717 >            k = child;
718 >        }
719 >        es[k] = x;
720      }
721  
722      /**
723 <     * Remove all elements from the priority queue.
723 >     * Establishes the heap invariant (described above) in the entire tree,
724 >     * assuming nothing about the order of the elements prior to the call.
725 >     * This classic algorithm due to Floyd (1964) is known to be O(size).
726       */
727 <    public void clear() {
728 <        modCount++;
727 >    private void heapify() {
728 >        final Object[] es = queue;
729 >        int n = size, i = (n >>> 1) - 1;
730 >        Comparator<? super E> cmp = comparator;
731 >        if (cmp == null)
732 >            for (; i >= 0; i--)
733 >                siftDownComparable(i, (E) es[i], es, n);
734 >        else
735 >            for (; i >= 0; i--)
736 >                siftDownUsingComparator(i, (E) es[i], es, n, cmp);
737 >    }
738  
739 <        // Null out element references to prevent memory leak
740 <        for (int i=1; i<=size; i++)
741 <            queue[i] = null;
739 >    /**
740 >     * Returns the comparator used to order the elements in this
741 >     * queue, or {@code null} if this queue is sorted according to
742 >     * the {@linkplain Comparable natural ordering} of its elements.
743 >     *
744 >     * @return the comparator used to order this queue, or
745 >     *         {@code null} if this queue is sorted according to the
746 >     *         natural ordering of its elements
747 >     */
748 >    public Comparator<? super E> comparator() {
749 >        return comparator;
750 >    }
751  
752 <        size = 0;
752 >    /**
753 >     * Saves this queue to a stream (that is, serializes it).
754 >     *
755 >     * @param s the stream
756 >     * @throws java.io.IOException if an I/O error occurs
757 >     * @serialData The length of the array backing the instance is
758 >     *             emitted (int), followed by all of its elements
759 >     *             (each an {@code Object}) in the proper order.
760 >     */
761 >    private void writeObject(java.io.ObjectOutputStream s)
762 >        throws java.io.IOException {
763 >        // Write out element count, and any hidden stuff
764 >        s.defaultWriteObject();
765 >
766 >        // Write out array length, for compatibility with 1.5 version
767 >        s.writeInt(Math.max(2, size + 1));
768 >
769 >        // Write out all elements in the "proper order".
770 >        final Object[] es = queue;
771 >        for (int i = 0, n = size; i < n; i++)
772 >            s.writeObject(es[i]);
773      }
774  
775      /**
776 <     * Removes and returns the ith element from queue.  Recall
777 <     * that queue is one-based, so 1 <= i <= size.
776 >     * Reconstitutes the {@code PriorityQueue} instance from a stream
777 >     * (that is, deserializes it).
778       *
779 <     * XXX: Could further special-case i==size, but is it worth it?
780 <     * XXX: Could special-case i==0, but is it worth it?
779 >     * @param s the stream
780 >     * @throws ClassNotFoundException if the class of a serialized object
781 >     *         could not be found
782 >     * @throws java.io.IOException if an I/O error occurs
783       */
784 <    private E remove(int i) {
785 <        assert i <= size;
786 <        modCount++;
784 >    private void readObject(java.io.ObjectInputStream s)
785 >        throws java.io.IOException, ClassNotFoundException {
786 >        // Read in size, and any hidden stuff
787 >        s.defaultReadObject();
788  
789 <        E result = queue[i];
790 <        queue[i] = queue[size];
791 <        queue[size--] = null;  // Drop extra ref to prevent memory leak
792 <        if (i <= size)
793 <            fixDown(i);
794 <        return result;
789 >        // Read in (and discard) array length
790 >        s.readInt();
791 >
792 >        SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
793 >        queue = new Object[size];
794 >
795 >        // Read in all elements.
796 >        final Object[] es = queue;
797 >        for (int i = 0, n = size; i < n; i++)
798 >            es[i] = s.readObject();
799 >
800 >        // Elements are guaranteed to be in "proper order", but the
801 >        // spec has never explained what that might be.
802 >        heapify();
803      }
804  
805      /**
806 <     * Establishes the heap invariant (described above) assuming the heap
807 <     * satisfies the invariant except possibly for the leaf-node indexed by k
808 <     * (which may have a nextExecutionTime less than its parent's).
809 <     *
810 <     * This method functions by "promoting" queue[k] up the hierarchy
811 <     * (by swapping it with its parent) repeatedly until queue[k]
812 <     * is greater than or equal to its parent.
813 <     */
814 <    private void fixUp(int k) {
815 <        if (comparator == null) {
816 <            while (k > 1) {
817 <                int j = k >> 1;
818 <                if (((Comparable)queue[j]).compareTo(queue[k]) <= 0)
819 <                    break;
820 <                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
821 <                k = j;
822 <            }
823 <        } else {
824 <            while (k > 1) {
825 <                int j = k >> 1;
826 <                if (comparator.compare(queue[j], queue[k]) <= 0)
827 <                    break;
828 <                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
829 <                k = j;
806 >     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
807 >     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
808 >     * queue. The spliterator does not traverse elements in any particular order
809 >     * (the {@link Spliterator#ORDERED ORDERED} characteristic is not reported).
810 >     *
811 >     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
812 >     * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}.
813 >     * Overriding implementations should document the reporting of additional
814 >     * characteristic values.
815 >     *
816 >     * @return a {@code Spliterator} over the elements in this queue
817 >     * @since 1.8
818 >     */
819 >    public final Spliterator<E> spliterator() {
820 >        return new PriorityQueueSpliterator(0, -1, 0);
821 >    }
822 >
823 >    final class PriorityQueueSpliterator implements Spliterator<E> {
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(int origin, int fence, int expectedModCount) {
830 >            this.index = origin;
831 >            this.fence = fence;
832 >            this.expectedModCount = expectedModCount;
833 >        }
834 >
835 >        private int getFence() { // initialize fence to size on first use
836 >            int hi;
837 >            if ((hi = fence) < 0) {
838 >                expectedModCount = modCount;
839 >                hi = fence = size;
840              }
841 +            return hi;
842          }
374    }
843  
844 <    /**
845 <     * Establishes the heap invariant (described above) in the subtree
846 <     * rooted at k, which is assumed to satisfy the heap invariant except
847 <     * possibly for node k itself (which may be greater than its children).
848 <     *
849 <     * This method functions by "demoting" queue[k] down the hierarchy
850 <     * (by swapping it with its smaller child) repeatedly until queue[k]
851 <     * is less than or equal to its children.
852 <     */
853 <    private void fixDown(int k) {
854 <        int j;
855 <        if (comparator == null) {
856 <            while ((j = k << 1) <= size) {
857 <                if (j<size && ((Comparable)queue[j]).compareTo(queue[j+1]) > 0)
858 <                    j++; // j indexes smallest kid
859 <                if (((Comparable)queue[k]).compareTo(queue[j]) <= 0)
392 <                    break;
393 <                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
394 <                k = j;
844 >        public PriorityQueueSpliterator trySplit() {
845 >            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
846 >            return (lo >= mid) ? null :
847 >                new PriorityQueueSpliterator(lo, index = mid, expectedModCount);
848 >        }
849 >
850 >        public void forEachRemaining(Consumer<? super E> action) {
851 >            if (action == null)
852 >                throw new NullPointerException();
853 >            if (fence < 0) { fence = size; expectedModCount = modCount; }
854 >            final Object[] es = queue;
855 >            int i, hi; E e;
856 >            for (i = index, index = hi = fence; i < hi; i++) {
857 >                if ((e = (E) es[i]) == null)
858 >                    break;      // must be CME
859 >                action.accept(e);
860              }
861 <        } else {
862 <            while ((j = k << 1) <= size) {
863 <                if (j < size && comparator.compare(queue[j], queue[j+1]) > 0)
864 <                    j++; // j indexes smallest kid
865 <                if (comparator.compare(queue[k], queue[j]) <= 0)
866 <                    break;
867 <                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
868 <                k = j;
861 >            if (modCount != expectedModCount)
862 >                throw new ConcurrentModificationException();
863 >        }
864 >
865 >        public boolean tryAdvance(Consumer<? super E> action) {
866 >            if (action == null)
867 >                throw new NullPointerException();
868 >            if (fence < 0) { fence = size; expectedModCount = modCount; }
869 >            int i;
870 >            if ((i = index) < fence) {
871 >                index = i + 1;
872 >                E e;
873 >                if ((e = (E) queue[i]) == null
874 >                    || modCount != expectedModCount)
875 >                    throw new ConcurrentModificationException();
876 >                action.accept(e);
877 >                return true;
878              }
879 +            return false;
880 +        }
881 +
882 +        public long estimateSize() {
883 +            return getFence() - index;
884 +        }
885 +
886 +        public int characteristics() {
887 +            return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL;
888          }
889      }
890  
891      /**
892 <     * Returns the comparator associated with this priority queue, or
410 <     * <tt>null</tt> if it uses its elements' natural ordering.
411 <     *
412 <     * @return the comparator associated with this priority queue, or
413 <     *         <tt>null</tt> if it uses its elements' natural ordering.
892 >     * @throws NullPointerException {@inheritDoc}
893       */
894 <    Comparator<E> comparator() {
895 <        return comparator;
894 >    public void forEach(Consumer<? super E> action) {
895 >        Objects.requireNonNull(action);
896 >        final int expectedModCount = modCount;
897 >        final Object[] es = queue;
898 >        for (int i = 0, n = size; i < n; i++)
899 >            action.accept((E) es[i]);
900 >        if (expectedModCount != modCount)
901 >            throw new ConcurrentModificationException();
902      }
903   }

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines