--- jsr166/src/jdk7/java/util/PriorityQueue.java 2014/04/11 21:15:44 1.4 +++ jsr166/src/jdk7/java/util/PriorityQueue.java 2016/10/15 18:41:31 1.5 @@ -1,12 +1,12 @@ /* - * Copyright (c) 2003, 2006, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2003, 2013, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. Sun designates this + * published by the Free Software Foundation. Oracle designates this * particular file as subject to the "Classpath" exception as provided - * by Sun in the LICENSE file that accompanied this code. + * by Oracle in the LICENSE file that accompanied this code. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or @@ -75,9 +75,8 @@ package java.util; * * @since 1.5 * @author Josh Bloch, Doug Lea - * @param the type of elements held in this collection + * @param the type of elements held in this queue */ -@SuppressWarnings("unchecked") public class PriorityQueue extends AbstractQueue implements java.io.Serializable { @@ -93,12 +92,12 @@ public class PriorityQueue extends Ab * heap and each descendant d of n, n <= d. The element with the * lowest value is in queue[0], assuming the queue is nonempty. */ - private transient Object[] queue; + transient Object[] queue; // non-private to simplify nested class access /** * The number of elements in the priority queue. */ - private int size; + int size; /** * The comparator, or null if priority queue uses elements' @@ -110,7 +109,7 @@ public class PriorityQueue extends Ab * The number of times this priority queue has been * structurally modified. See AbstractList for gory details. */ - private transient int modCount; + transient int modCount; // non-private to simplify nested class access /** * Creates a {@code PriorityQueue} with the default initial @@ -135,6 +134,19 @@ public class PriorityQueue extends Ab } /** + * Creates a {@code PriorityQueue} with the default initial capacity and + * whose elements are ordered according to the specified comparator. + * + * @param comparator the comparator that will be used to order this + * priority queue. If {@code null}, the {@linkplain Comparable + * natural ordering} of the elements will be used. + * @since 1.8 + */ + public PriorityQueue(Comparator comparator) { + this(DEFAULT_INITIAL_CAPACITY, comparator); + } + + /** * Creates a {@code PriorityQueue} with the specified initial capacity * that orders its elements according to the specified comparator. * @@ -244,8 +256,8 @@ public class PriorityQueue extends Ab a = Arrays.copyOf(a, a.length, Object[].class); int len = a.length; if (len == 1 || this.comparator != null) - for (int i = 0; i < len; i++) - if (a[i] == null) + for (Object e : a) + if (e == null) throw new NullPointerException(); this.queue = a; this.size = a.length; @@ -323,14 +335,12 @@ public class PriorityQueue extends Ab int i = size; if (i >= queue.length) grow(i + 1); + siftUp(i, e); size = i + 1; - if (i == 0) - queue[0] = e; - else - siftUp(i, e); return true; } + @SuppressWarnings("unchecked") public E peek() { return (size == 0) ? null : (E) queue[0]; } @@ -391,7 +401,7 @@ public class PriorityQueue extends Ab * @return {@code true} if this queue contains the specified element */ public boolean contains(Object o) { - return indexOf(o) != -1; + return indexOf(o) >= 0; } /** @@ -433,7 +443,7 @@ public class PriorityQueue extends Ab * The following code can be used to dump the queue into a newly * allocated array of {@code String}: * - * 
 {@code String[] y = x.toArray(new String[0]);}
+ * 
 {@code String[] y = x.toArray(new String[0]);}
* * Note that {@code toArray(new Object[0])} is identical in function to * {@code toArray()}. @@ -447,6 +457,7 @@ public class PriorityQueue extends Ab * this queue * @throws NullPointerException if the specified array is null */ + @SuppressWarnings("unchecked") public T[] toArray(T[] a) { final int size = this.size; if (a.length < size) @@ -513,6 +524,7 @@ public class PriorityQueue extends Ab (forgetMeNot != null && !forgetMeNot.isEmpty()); } + @SuppressWarnings("unchecked") public E next() { if (expectedModCount != modCount) throw new ConcurrentModificationException(); @@ -565,6 +577,7 @@ public class PriorityQueue extends Ab size = 0; } + @SuppressWarnings("unchecked") public E poll() { if (size == 0) return null; @@ -590,7 +603,8 @@ public class PriorityQueue extends Ab * position before i. This fact is used by iterator.remove so as to * avoid missing traversing elements. */ - private E removeAt(int i) { + @SuppressWarnings("unchecked") + E removeAt(int i) { // assert i >= 0 && i < size; modCount++; int s = --size; @@ -628,6 +642,7 @@ public class PriorityQueue extends Ab siftUpComparable(k, x); } + @SuppressWarnings("unchecked") private void siftUpComparable(int k, E x) { Comparable key = (Comparable) x; while (k > 0) { @@ -641,6 +656,7 @@ public class PriorityQueue extends Ab queue[k] = key; } + @SuppressWarnings("unchecked") private void siftUpUsingComparator(int k, E x) { while (k > 0) { int parent = (k - 1) >>> 1; @@ -668,6 +684,7 @@ public class PriorityQueue extends Ab siftDownComparable(k, x); } + @SuppressWarnings("unchecked") private void siftDownComparable(int k, E x) { Comparable key = (Comparable)x; int half = size >>> 1; // loop while a non-leaf @@ -686,6 +703,7 @@ public class PriorityQueue extends Ab queue[k] = key; } + @SuppressWarnings("unchecked") private void siftDownUsingComparator(int k, E x) { int half = size >>> 1; while (k < half) { @@ -707,6 +725,7 @@ public class PriorityQueue extends Ab * Establishes the heap invariant (described above) in the entire tree, * assuming nothing about the order of the elements prior to the call. */ + @SuppressWarnings("unchecked") private void heapify() { for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]); @@ -728,6 +747,8 @@ public class PriorityQueue extends Ab /** * Saves this queue to a stream (that is, serializes it). * + * @param s the stream + * @throws java.io.IOException if an I/O error occurs * @serialData The length of the array backing the instance is * emitted (int), followed by all of its elements * (each an {@code Object}) in the proper order. @@ -746,7 +767,13 @@ public class PriorityQueue extends Ab } /** - * Reconstitutes this queue from a stream (that is, deserializes it). + * Reconstitutes the {@code PriorityQueue} instance from a stream + * (that is, deserializes it). + * + * @param s the stream + * @throws ClassNotFoundException if the class of a serialized object + * could not be found + * @throws java.io.IOException if an I/O error occurs */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {