--- jsr166/src/main/java/util/PriorityQueue.java 2016/11/29 18:11:28 1.112
+++ jsr166/src/main/java/util/PriorityQueue.java 2018/11/11 16:27:28 1.130
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2003, 2013, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2003, 2018, 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
@@ -26,6 +26,8 @@
package java.util;
import java.util.function.Consumer;
+import java.util.function.Predicate;
+// OPENJDK import jdk.internal.access.SharedSecrets;
/**
* An unbounded priority {@linkplain Queue queue} based on a priority heap.
@@ -73,13 +75,14 @@ import java.util.function.Consumer;
* ({@code peek}, {@code element}, and {@code size}).
*
*
This class is a member of the
- *
+ *
* Java Collections Framework.
*
* @since 1.5
* @author Josh Bloch, Doug Lea
* @param the type of elements held in this queue
*/
+@SuppressWarnings("unchecked")
public class PriorityQueue extends AbstractQueue
implements java.io.Serializable {
@@ -186,7 +189,6 @@ public class PriorityQueue extends Ab
* @throws NullPointerException if the specified collection or any
* of its elements are null
*/
- @SuppressWarnings("unchecked")
public PriorityQueue(Collection extends E> c) {
if (c instanceof SortedSet>) {
SortedSet extends E> ss = (SortedSet extends E>) c;
@@ -218,7 +220,6 @@ public class PriorityQueue extends Ab
* @throws NullPointerException if the specified priority queue or any
* of its elements are null
*/
- @SuppressWarnings("unchecked")
public PriorityQueue(PriorityQueue extends E> c) {
this.comparator = (Comparator super E>) c.comparator();
initFromPriorityQueue(c);
@@ -237,15 +238,19 @@ public class PriorityQueue extends Ab
* @throws NullPointerException if the specified sorted set or any
* of its elements are null
*/
- @SuppressWarnings("unchecked")
public PriorityQueue(SortedSet extends E> c) {
this.comparator = (Comparator super E>) c.comparator();
initElementsFromCollection(c);
}
+ /** Ensures that queue[0] exists, helping peek() and poll(). */
+ private static Object[] ensureNonEmpty(Object[] es) {
+ return (es.length > 0) ? es : new Object[1];
+ }
+
private void initFromPriorityQueue(PriorityQueue extends E> c) {
if (c.getClass() == PriorityQueue.class) {
- this.queue = c.toArray();
+ this.queue = ensureNonEmpty(c.toArray());
this.size = c.size();
} else {
initFromCollection(c);
@@ -253,17 +258,17 @@ public class PriorityQueue extends Ab
}
private void initElementsFromCollection(Collection extends E> c) {
- Object[] a = c.toArray();
+ Object[] es = c.toArray();
+ int len = es.length;
// If c.toArray incorrectly doesn't return Object[], copy it.
- if (a.getClass() != Object[].class)
- a = Arrays.copyOf(a, a.length, Object[].class);
- int len = a.length;
+ if (es.getClass() != Object[].class)
+ es = Arrays.copyOf(es, len, Object[].class);
if (len == 1 || this.comparator != null)
- for (Object e : a)
+ for (Object e : es)
if (e == null)
throw new NullPointerException();
- this.queue = a;
- this.size = a.length;
+ this.queue = ensureNonEmpty(es);
+ this.size = len;
}
/**
@@ -343,15 +348,15 @@ public class PriorityQueue extends Ab
return true;
}
- @SuppressWarnings("unchecked")
public E peek() {
- return (size == 0) ? null : (E) queue[0];
+ return (E) queue[0];
}
private int indexOf(Object o) {
if (o != null) {
- for (int i = 0; i < size; i++)
- if (o.equals(queue[i]))
+ final Object[] es = queue;
+ for (int i = 0, n = size; i < n; i++)
+ if (o.equals(es[i]))
return i;
}
return -1;
@@ -379,20 +384,18 @@ public class PriorityQueue extends Ab
}
/**
- * Version of remove using reference equality, not equals.
- * Needed by iterator.remove.
+ * Identity-based version for use in Itr.remove.
*
* @param o element to be removed from this queue, if present
- * @return {@code true} if removed
*/
- boolean removeEq(Object o) {
- for (int i = 0; i < size; i++) {
- if (o == queue[i]) {
+ void removeEq(Object o) {
+ final Object[] es = queue;
+ for (int i = 0, n = size; i < n; i++) {
+ if (o == es[i]) {
removeAt(i);
- return true;
+ break;
}
}
- return false;
}
/**
@@ -460,7 +463,6 @@ 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)
@@ -522,12 +524,13 @@ public class PriorityQueue extends Ab
*/
private int expectedModCount = modCount;
+ Itr() {} // prevent access constructor creation
+
public boolean hasNext() {
return cursor < size ||
(forgetMeNot != null && !forgetMeNot.isEmpty());
}
- @SuppressWarnings("unchecked")
public E next() {
if (expectedModCount != modCount)
throw new ConcurrentModificationException();
@@ -575,22 +578,29 @@ public class PriorityQueue extends Ab
*/
public void clear() {
modCount++;
- for (int i = 0; i < size; i++)
- queue[i] = null;
+ final Object[] es = queue;
+ for (int i = 0, n = size; i < n; i++)
+ es[i] = null;
size = 0;
}
- @SuppressWarnings("unchecked")
public E poll() {
- if (size == 0)
- return null;
- int s = --size;
- modCount++;
- E result = (E) queue[0];
- E x = (E) queue[s];
- queue[s] = null;
- if (s != 0)
- siftDown(0, x);
+ final Object[] es;
+ final E result;
+
+ if ((result = (E) ((es = queue)[0])) != null) {
+ modCount++;
+ final int n;
+ final E x = (E) es[(n = --size)];
+ es[n] = null;
+ if (n > 0) {
+ final Comparator super E> cmp;
+ if ((cmp = comparator) == null)
+ siftDownComparable(0, x, es, n);
+ else
+ siftDownUsingComparator(0, x, es, n, cmp);
+ }
+ }
return result;
}
@@ -606,20 +616,20 @@ public class PriorityQueue extends Ab
* position before i. This fact is used by iterator.remove so as to
* avoid missing traversing elements.
*/
- @SuppressWarnings("unchecked")
E removeAt(int i) {
// assert i >= 0 && i < size;
+ final Object[] es = queue;
modCount++;
int s = --size;
if (s == i) // removed last element
- queue[i] = null;
+ es[i] = null;
else {
- E moved = (E) queue[s];
- queue[s] = null;
+ E moved = (E) es[s];
+ es[s] = null;
siftDown(i, moved);
- if (queue[i] == moved) {
+ if (es[i] == moved) {
siftUp(i, moved);
- if (queue[i] != moved)
+ if (es[i] != moved)
return moved;
}
}
@@ -631,7 +641,7 @@ public class PriorityQueue extends Ab
* promoting x up the tree until it is greater than or equal to
* its parent, or is the root.
*
- * To simplify and speed up coercions and comparisons. the
+ * To simplify and speed up coercions and comparisons, the
* Comparable and Comparator versions are separated into different
* methods that are otherwise identical. (Similarly for siftDown.)
*
@@ -640,36 +650,35 @@ public class PriorityQueue extends Ab
*/
private void siftUp(int k, E x) {
if (comparator != null)
- siftUpUsingComparator(k, x);
+ siftUpUsingComparator(k, x, queue, comparator);
else
- siftUpComparable(k, x);
+ siftUpComparable(k, x, queue);
}
- @SuppressWarnings("unchecked")
- private void siftUpComparable(int k, E x) {
- Comparable super E> key = (Comparable super E>) x;
+ private static void siftUpComparable(int k, T x, Object[] es) {
+ Comparable super T> key = (Comparable super T>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
- Object e = queue[parent];
- if (key.compareTo((E) e) >= 0)
+ Object e = es[parent];
+ if (key.compareTo((T) e) >= 0)
break;
- queue[k] = e;
+ es[k] = e;
k = parent;
}
- queue[k] = key;
+ es[k] = key;
}
- @SuppressWarnings("unchecked")
- private void siftUpUsingComparator(int k, E x) {
+ private static void siftUpUsingComparator(
+ int k, T x, Object[] es, Comparator super T> cmp) {
while (k > 0) {
int parent = (k - 1) >>> 1;
- Object e = queue[parent];
- if (comparator.compare(x, (E) e) >= 0)
+ Object e = es[parent];
+ if (cmp.compare(x, (T) e) >= 0)
break;
- queue[k] = e;
+ es[k] = e;
k = parent;
}
- queue[k] = x;
+ es[k] = x;
}
/**
@@ -682,46 +691,46 @@ public class PriorityQueue extends Ab
*/
private void siftDown(int k, E x) {
if (comparator != null)
- siftDownUsingComparator(k, x);
+ siftDownUsingComparator(k, x, queue, size, comparator);
else
- siftDownComparable(k, x);
+ siftDownComparable(k, x, queue, size);
}
- @SuppressWarnings("unchecked")
- private void siftDownComparable(int k, E x) {
- Comparable super E> key = (Comparable super E>)x;
- int half = size >>> 1; // loop while a non-leaf
+ private static void siftDownComparable(int k, T x, Object[] es, int n) {
+ // assert n > 0;
+ Comparable super T> key = (Comparable super T>)x;
+ int half = n >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
- Object c = queue[child];
+ Object c = es[child];
int right = child + 1;
- if (right < size &&
- ((Comparable super E>) c).compareTo((E) queue[right]) > 0)
- c = queue[child = right];
- if (key.compareTo((E) c) <= 0)
+ if (right < n &&
+ ((Comparable super T>) c).compareTo((T) es[right]) > 0)
+ c = es[child = right];
+ if (key.compareTo((T) c) <= 0)
break;
- queue[k] = c;
+ es[k] = c;
k = child;
}
- queue[k] = key;
+ es[k] = key;
}
- @SuppressWarnings("unchecked")
- private void siftDownUsingComparator(int k, E x) {
- int half = size >>> 1;
+ private static void siftDownUsingComparator(
+ int k, T x, Object[] es, int n, Comparator super T> cmp) {
+ // assert n > 0;
+ int half = n >>> 1;
while (k < half) {
int child = (k << 1) + 1;
- Object c = queue[child];
+ Object c = es[child];
int right = child + 1;
- if (right < size &&
- comparator.compare((E) c, (E) queue[right]) > 0)
- c = queue[child = right];
- if (comparator.compare(x, (E) c) <= 0)
+ if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
+ c = es[child = right];
+ if (cmp.compare(x, (T) c) <= 0)
break;
- queue[k] = c;
+ es[k] = c;
k = child;
}
- queue[k] = x;
+ es[k] = x;
}
/**
@@ -729,10 +738,16 @@ public class PriorityQueue extends Ab
* assuming nothing about the order of the elements prior to the call.
* This classic algorithm due to Floyd (1964) is known to be O(size).
*/
- @SuppressWarnings("unchecked")
private void heapify() {
- for (int i = (size >>> 1) - 1; i >= 0; i--)
- siftDown(i, (E) queue[i]);
+ final Object[] es = queue;
+ int n = size, i = (n >>> 1) - 1;
+ final Comparator super E> cmp;
+ if ((cmp = comparator) == null)
+ for (; i >= 0; i--)
+ siftDownComparable(i, (E) es[i], es, n);
+ else
+ for (; i >= 0; i--)
+ siftDownUsingComparator(i, (E) es[i], es, n, cmp);
}
/**
@@ -766,8 +781,9 @@ public class PriorityQueue extends Ab
s.writeInt(Math.max(2, size + 1));
// Write out all elements in the "proper order".
- for (int i = 0; i < size; i++)
- s.writeObject(queue[i]);
+ final Object[] es = queue;
+ for (int i = 0, n = size; i < n; i++)
+ s.writeObject(es[i]);
}
/**
@@ -787,11 +803,12 @@ public class PriorityQueue extends Ab
// Read in (and discard) array length
s.readInt();
- queue = new Object[size];
+ jsr166.Platform.checkArray(s, Object[].class, size);
+ final Object[] es = queue = new Object[Math.max(size, 1)];
// Read in all elements.
- for (int i = 0; i < size; i++)
- queue[i] = s.readObject();
+ for (int i = 0, n = size; i < n; i++)
+ es[i] = s.readObject();
// Elements are guaranteed to be in "proper order", but the
// spec has never explained what that might be.
@@ -813,23 +830,16 @@ public class PriorityQueue extends Ab
* @since 1.8
*/
public final Spliterator spliterator() {
- return new PriorityQueueSpliterator<>(this, 0, -1, 0);
+ return new PriorityQueueSpliterator(0, -1, 0);
}
- static final class PriorityQueueSpliterator implements Spliterator {
- /*
- * This is very similar to ArrayList Spliterator, except for
- * extra null checks.
- */
- private final PriorityQueue pq;
+ final class PriorityQueueSpliterator implements Spliterator {
private int index; // current index, modified on advance/split
private int fence; // -1 until first use
private int expectedModCount; // initialized when fence set
/** Creates new spliterator covering the given range. */
- PriorityQueueSpliterator(PriorityQueue pq, int origin, int fence,
- int expectedModCount) {
- this.pq = pq;
+ PriorityQueueSpliterator(int origin, int fence, int expectedModCount) {
this.index = origin;
this.fence = fence;
this.expectedModCount = expectedModCount;
@@ -838,72 +848,140 @@ public class PriorityQueue extends Ab
private int getFence() { // initialize fence to size on first use
int hi;
if ((hi = fence) < 0) {
- expectedModCount = pq.modCount;
- hi = fence = pq.size;
+ expectedModCount = modCount;
+ hi = fence = size;
}
return hi;
}
- public PriorityQueueSpliterator trySplit() {
+ public PriorityQueueSpliterator trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null :
- new PriorityQueueSpliterator<>(pq, lo, index = mid,
- expectedModCount);
+ new PriorityQueueSpliterator(lo, index = mid, expectedModCount);
}
- @SuppressWarnings("unchecked")
public void forEachRemaining(Consumer super E> action) {
- int i, hi, mc; // hoist accesses and checks from loop
- PriorityQueue q; Object[] a;
if (action == null)
throw new NullPointerException();
- if ((q = pq) != null && (a = q.queue) != null) {
- if ((hi = fence) < 0) {
- mc = q.modCount;
- hi = q.size;
- }
- else
- mc = expectedModCount;
- if ((i = index) >= 0 && (index = hi) <= a.length) {
- for (E e;; ++i) {
- if (i < hi) {
- if ((e = (E) a[i]) == null) // must be CME
- break;
- action.accept(e);
- }
- else if (q.modCount != mc)
- break;
- else
- return;
- }
- }
+ if (fence < 0) { fence = size; expectedModCount = modCount; }
+ final Object[] es = queue;
+ int i, hi; E e;
+ for (i = index, index = hi = fence; i < hi; i++) {
+ if ((e = (E) es[i]) == null)
+ break; // must be CME
+ action.accept(e);
}
- throw new ConcurrentModificationException();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
}
public boolean tryAdvance(Consumer super E> action) {
if (action == null)
throw new NullPointerException();
- int hi = getFence(), lo = index;
- if (lo >= 0 && lo < hi) {
- index = lo + 1;
- @SuppressWarnings("unchecked") E e = (E)pq.queue[lo];
- if (e == null)
+ if (fence < 0) { fence = size; expectedModCount = modCount; }
+ int i;
+ if ((i = index) < fence) {
+ index = i + 1;
+ E e;
+ if ((e = (E) queue[i]) == null
+ || modCount != expectedModCount)
throw new ConcurrentModificationException();
action.accept(e);
- if (pq.modCount != expectedModCount)
- throw new ConcurrentModificationException();
return true;
}
return false;
}
public long estimateSize() {
- return (long) (getFence() - index);
+ return getFence() - index;
}
public int characteristics() {
return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL;
}
}
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean removeIf(Predicate super E> filter) {
+ Objects.requireNonNull(filter);
+ return bulkRemove(filter);
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean removeAll(Collection> c) {
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> c.contains(e));
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean retainAll(Collection> c) {
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> !c.contains(e));
+ }
+
+ // A tiny bit set implementation
+
+ private static long[] nBits(int n) {
+ return new long[((n - 1) >> 6) + 1];
+ }
+ private static void setBit(long[] bits, int i) {
+ bits[i >> 6] |= 1L << i;
+ }
+ private static boolean isClear(long[] bits, int i) {
+ return (bits[i >> 6] & (1L << i)) == 0;
+ }
+
+ /** Implementation of bulk remove methods. */
+ private boolean bulkRemove(Predicate super E> filter) {
+ final int expectedModCount = ++modCount;
+ final Object[] es = queue;
+ final int end = size;
+ int i;
+ // Optimize for initial run of survivors
+ for (i = 0; i < end && !filter.test((E) es[i]); i++)
+ ;
+ if (i >= end) {
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return false;
+ }
+ // Tolerate predicates that reentrantly access the collection for
+ // read (but writers still get CME), so traverse once to find
+ // elements to delete, a second pass to physically expunge.
+ final int beg = i;
+ final long[] deathRow = nBits(end - beg);
+ deathRow[0] = 1L; // set bit 0
+ for (i = beg + 1; i < end; i++)
+ if (filter.test((E) es[i]))
+ setBit(deathRow, i - beg);
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ int w = beg;
+ for (i = beg; i < end; i++)
+ if (isClear(deathRow, i - beg))
+ es[w++] = es[i];
+ for (i = size = w; i < end; i++)
+ es[i] = null;
+ heapify();
+ return true;
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public void forEach(Consumer super E> action) {
+ Objects.requireNonNull(action);
+ final int expectedModCount = modCount;
+ final Object[] es = queue;
+ for (int i = 0, n = size; i < n; i++)
+ action.accept((E) es[i]);
+ if (expectedModCount != modCount)
+ throw new ConcurrentModificationException();
+ }
}