70 * methods of the {@link Collection} and {@link Iterator} interfaces.
71 * The Iterator provided in method {@link #iterator()} and the
72 * Spliterator provided in method {@link #spliterator()} are <em>not</em>
73 * guaranteed to traverse the elements of the PriorityBlockingQueue in
74 * any particular order. If you need ordered traversal, consider using
75 * {@code Arrays.sort(pq.toArray())}. Also, method {@code drainTo} can
76 * be used to <em>remove</em> some or all elements in priority order and
77 * place them in another collection.
78 *
79 * <p>Operations on this class make no guarantees about the ordering
80 * of elements with equal priority. If you need to enforce an
81 * ordering, you can define custom classes or comparators that use a
82 * secondary key to break ties in primary priority values. For
83 * example, here is a class that applies first-in-first-out
84 * tie-breaking to comparable elements. To use it, you would insert a
85 * {@code new FIFOEntry(anEntry)} instead of a plain entry object.
86 *
87 * <pre> {@code
88 * class FIFOEntry<E extends Comparable<? super E>>
89 * implements Comparable<FIFOEntry<E>> {
90 * static final AtomicLong seq = new AtomicLong(0);
91 * final long seqNum;
92 * final E entry;
93 * public FIFOEntry(E entry) {
94 * seqNum = seq.getAndIncrement();
95 * this.entry = entry;
96 * }
97 * public E getEntry() { return entry; }
98 * public int compareTo(FIFOEntry<E> other) {
99 * int res = entry.compareTo(other.entry);
100 * if (res == 0 && other.entry != this.entry)
101 * res = (seqNum < other.seqNum ? -1 : 1);
102 * return res;
103 * }
104 * }}</pre>
105 *
106 * <p>This class is a member of the
107 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
108 * Java Collections Framework</a>.
109 *
110 * @since 1.5
209 * comparator.
210 *
211 * @param initialCapacity the initial capacity for this priority queue
212 * @param comparator the comparator that will be used to order this
213 * priority queue. If {@code null}, the {@linkplain Comparable
214 * natural ordering} of the elements will be used.
215 * @throws IllegalArgumentException if {@code initialCapacity} is less
216 * than 1
217 */
218 public PriorityBlockingQueue(int initialCapacity,
219 Comparator<? super E> comparator) {
220 if (initialCapacity < 1)
221 throw new IllegalArgumentException();
222 this.comparator = comparator;
223 this.queue = new Object[Math.max(1, initialCapacity)];
224 }
225
226 /**
227 * Creates a {@code PriorityBlockingQueue} containing the elements
228 * in the specified collection. If the specified collection is a
229 * {@link SortedSet} or a {@link PriorityQueue}, this
230 * priority queue will be ordered according to the same ordering.
231 * Otherwise, this priority queue will be ordered according to the
232 * {@linkplain Comparable natural ordering} of its elements.
233 *
234 * @param c the collection whose elements are to be placed
235 * into this priority queue
236 * @throws ClassCastException if elements of the specified collection
237 * cannot be compared to one another according to the priority
238 * queue's ordering
239 * @throws NullPointerException if the specified collection or any
240 * of its elements are null
241 */
242 public PriorityBlockingQueue(Collection<? extends E> c) {
243 boolean heapify = true; // true if not known to be in heap order
244 boolean screen = true; // true if must screen for nulls
245 if (c instanceof SortedSet<?>) {
246 SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
247 this.comparator = (Comparator<? super E>) ss.comparator();
248 heapify = false;
249 }
273 /** Ensures that queue[0] exists, helping peek() and poll(). */
274 private static Object[] ensureNonEmpty(Object[] es) {
275 return (es.length > 0) ? es : new Object[1];
276 }
277
278 /**
279 * Tries to grow array to accommodate at least one more element
280 * (but normally expand by about 50%), giving up (allowing retry)
281 * on contention (which we expect to be rare). Call only while
282 * holding lock.
283 *
284 * @param array the heap array
285 * @param oldCap the length of the array
286 */
287 private void tryGrow(Object[] array, int oldCap) {
288 lock.unlock(); // must release and then re-acquire main lock
289 Object[] newArray = null;
290 if (allocationSpinLock == 0 &&
291 ALLOCATIONSPINLOCK.compareAndSet(this, 0, 1)) {
292 try {
293 int growth = oldCap < 64 ? oldCap + 2 : oldCap >> 1;
294 int newCap = ArraysSupport.newLength(oldCap, 1, growth);
295 if (queue == array)
296 newArray = new Object[newCap];
297 } finally {
298 allocationSpinLock = 0;
299 }
300 }
301 if (newArray == null) // back off if another thread is allocating
302 Thread.yield();
303 lock.lock();
304 if (newArray != null && queue == array) {
305 queue = newArray;
306 System.arraycopy(array, 0, newArray, 0, oldCap);
307 }
308 }
309
310 /**
311 * Mechanics for poll(). Call only while holding lock.
312 */
313 private E dequeue() {
|
70 * methods of the {@link Collection} and {@link Iterator} interfaces.
71 * The Iterator provided in method {@link #iterator()} and the
72 * Spliterator provided in method {@link #spliterator()} are <em>not</em>
73 * guaranteed to traverse the elements of the PriorityBlockingQueue in
74 * any particular order. If you need ordered traversal, consider using
75 * {@code Arrays.sort(pq.toArray())}. Also, method {@code drainTo} can
76 * be used to <em>remove</em> some or all elements in priority order and
77 * place them in another collection.
78 *
79 * <p>Operations on this class make no guarantees about the ordering
80 * of elements with equal priority. If you need to enforce an
81 * ordering, you can define custom classes or comparators that use a
82 * secondary key to break ties in primary priority values. For
83 * example, here is a class that applies first-in-first-out
84 * tie-breaking to comparable elements. To use it, you would insert a
85 * {@code new FIFOEntry(anEntry)} instead of a plain entry object.
86 *
87 * <pre> {@code
88 * class FIFOEntry<E extends Comparable<? super E>>
89 * implements Comparable<FIFOEntry<E>> {
90 * static final AtomicLong seq = new AtomicLong();
91 * final long seqNum;
92 * final E entry;
93 * public FIFOEntry(E entry) {
94 * seqNum = seq.getAndIncrement();
95 * this.entry = entry;
96 * }
97 * public E getEntry() { return entry; }
98 * public int compareTo(FIFOEntry<E> other) {
99 * int res = entry.compareTo(other.entry);
100 * if (res == 0 && other.entry != this.entry)
101 * res = (seqNum < other.seqNum ? -1 : 1);
102 * return res;
103 * }
104 * }}</pre>
105 *
106 * <p>This class is a member of the
107 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
108 * Java Collections Framework</a>.
109 *
110 * @since 1.5
209 * comparator.
210 *
211 * @param initialCapacity the initial capacity for this priority queue
212 * @param comparator the comparator that will be used to order this
213 * priority queue. If {@code null}, the {@linkplain Comparable
214 * natural ordering} of the elements will be used.
215 * @throws IllegalArgumentException if {@code initialCapacity} is less
216 * than 1
217 */
218 public PriorityBlockingQueue(int initialCapacity,
219 Comparator<? super E> comparator) {
220 if (initialCapacity < 1)
221 throw new IllegalArgumentException();
222 this.comparator = comparator;
223 this.queue = new Object[Math.max(1, initialCapacity)];
224 }
225
226 /**
227 * Creates a {@code PriorityBlockingQueue} containing the elements
228 * in the specified collection. If the specified collection is a
229 * {@link SortedSet} or a {@link PriorityBlockingQueue}, this
230 * priority queue will be ordered according to the same ordering.
231 * Otherwise, this priority queue will be ordered according to the
232 * {@linkplain Comparable natural ordering} of its elements.
233 *
234 * @param c the collection whose elements are to be placed
235 * into this priority queue
236 * @throws ClassCastException if elements of the specified collection
237 * cannot be compared to one another according to the priority
238 * queue's ordering
239 * @throws NullPointerException if the specified collection or any
240 * of its elements are null
241 */
242 public PriorityBlockingQueue(Collection<? extends E> c) {
243 boolean heapify = true; // true if not known to be in heap order
244 boolean screen = true; // true if must screen for nulls
245 if (c instanceof SortedSet<?>) {
246 SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
247 this.comparator = (Comparator<? super E>) ss.comparator();
248 heapify = false;
249 }
273 /** Ensures that queue[0] exists, helping peek() and poll(). */
274 private static Object[] ensureNonEmpty(Object[] es) {
275 return (es.length > 0) ? es : new Object[1];
276 }
277
278 /**
279 * Tries to grow array to accommodate at least one more element
280 * (but normally expand by about 50%), giving up (allowing retry)
281 * on contention (which we expect to be rare). Call only while
282 * holding lock.
283 *
284 * @param array the heap array
285 * @param oldCap the length of the array
286 */
287 private void tryGrow(Object[] array, int oldCap) {
288 lock.unlock(); // must release and then re-acquire main lock
289 Object[] newArray = null;
290 if (allocationSpinLock == 0 &&
291 ALLOCATIONSPINLOCK.compareAndSet(this, 0, 1)) {
292 try {
293 int growth = (oldCap < 64)
294 ? (oldCap + 2) // grow faster if small
295 : (oldCap >> 1);
296 int newCap = ArraysSupport.newLength(oldCap, 1, growth);
297 if (queue == array)
298 newArray = new Object[newCap];
299 } finally {
300 allocationSpinLock = 0;
301 }
302 }
303 if (newArray == null) // back off if another thread is allocating
304 Thread.yield();
305 lock.lock();
306 if (newArray != null && queue == array) {
307 queue = newArray;
308 System.arraycopy(array, 0, newArray, 0, oldCap);
309 }
310 }
311
312 /**
313 * Mechanics for poll(). Call only while holding lock.
314 */
315 private E dequeue() {
|