Modifier and Type	Class and Description
pack-priv class	PriorityBlockingQueue.Itr Snapshot iterator that works off copy of underlying q array.
pack-priv class	PriorityBlockingQueue.PBQSpliterator Immutable snapshot spliterator that binds to elements "late".

Modifier and Type	Field and Description
private transient volatile int	allocationSpinLock Spinlock for allocation, acquired via CAS.
private static final VarHandle	ALLOCATIONSPINLOCK
private transient Comparator<? super E>	comparator The comparator, or null if priority queue uses elements' natural ordering.
private static final int	DEFAULT_INITIAL_CAPACITY Default array capacity.
private final ReentrantLock	lock
private final Condition	notEmpty
private PriorityQueue<E>	q
private transient Object[]	queue Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2n+1] and queue[2(n+1)].
private static final long	serialVersionUID
private transient int	size The number of elements in the priority queue.

Access	Constructor and Description
public	PriorityBlockingQueue() Creates a `PriorityBlockingQueue` with the default initial capacity (11) that orders its elements according to their natural ordering.
public	PriorityBlockingQueue(int the initial capacity for this priority queue initialCapacity) Creates a `PriorityBlockingQueue` with the specified initial capacity that orders its elements according to their natural ordering.
public	PriorityBlockingQueue(int the initial capacity for this priority queue initialCapacity, Comparator<? super E> the comparator that will be used to order this priority queue. If `null`, the natural ordering of the elements will be used. comparator) Creates a `PriorityBlockingQueue` with the specified initial capacity that orders its elements according to the specified comparator.
public	PriorityBlockingQueue(Collection<? extends E> the collection whose elements are to be placed into this priority queue c) Creates a `PriorityBlockingQueue` containing the elements in the specified collection.

Method Summary

Modifier and Type	Method and Description
public boolean	Returns: `true` (as specified by `Collection#add`) add(E the element to add e) Overrides java.util.AbstractQueue.add. Implements java.util.concurrent.BlockingQueue.add, java.util.Queue.add, java.util.Collection.add. Inserts the specified element into this priority queue.
private boolean	bulkRemove(Predicate<? super E> filter) Implementation of bulk remove methods.
public void	clear() Overrides java.util.AbstractQueue.clear. Implements java.util.Collection.clear. Atomically removes all of the elements from this queue.
public Comparator<? super E>	Returns: the comparator used to order the elements in this queue, or `null` if this queue uses the natural ordering of its elements comparator() Returns the comparator used to order the elements in this queue, or `null` if this queue uses the natural ordering of its elements.
public boolean	Returns: `true` if this queue contains the specified element contains(Object object to be checked for containment in this queue o) Overrides java.util.AbstractCollection.contains. Implements java.util.concurrent.BlockingQueue.contains, java.util.Collection.contains. Returns `true` if this queue contains the specified element.
private E	dequeue() Mechanics for poll().
public int	drainTo(Collection<? super E> c) Implements java.util.concurrent.BlockingQueue.drainTo. Removes all available elements from this queue and adds them to the given collection.
public int	drainTo(Collection<? super E> c, int maxElements) Implements java.util.concurrent.BlockingQueue.drainTo. Removes at most the given number of available elements from this queue and adds them to the given collection.
private static Object[]	ensureNonEmpty(Object[] es) Ensures that queue[0] exists, helping peek() and poll().
public void	forEach(Consumer<? super E> action) Overrides default java.lang.Iterable.forEach. Performs the given action for each element of the `Iterable` until all elements have been processed or the action throws an exception.
private void	heapify() Establishes the heap invariant (described above) in the entire tree, assuming nothing about the order of the elements prior to the call.
private int	indexOf(Object o)
private static boolean	isClear(long[] bits, int i)
public Iterator<E>	Returns: an iterator over the elements in this queue iterator() Implements abstract java.util.AbstractCollection.iterator. Implements java.util.Collection.iterator. Returns an iterator over the elements in this queue.
private static long[]	nBits(int n)
public boolean	Returns: `true` (as specified by `Queue#offer`) offer(E the element to add e) Implements java.util.concurrent.BlockingQueue.offer, java.util.Queue.offer. Inserts the specified element into this priority queue.
public boolean	Returns: `true` (as specified by `BlockingQueue.offer`) offer(E the element to add e, long This parameter is ignored as the method never blocks timeout, TimeUnit This parameter is ignored as the method never blocks unit) Implements java.util.concurrent.BlockingQueue.offer. Inserts the specified element into this priority queue.
public E	peek() Implements java.util.Queue.peek. Retrieves, but does not remove, the head of this queue, or returns `null` if this queue is empty.
public E	poll() Implements java.util.Queue.poll. Retrieves and removes the head of this queue, or returns `null` if this queue is empty.
public E	poll(long timeout, TimeUnit unit) Implements java.util.concurrent.BlockingQueue.poll. Retrieves and removes the head of this queue, waiting up to the specified wait time if necessary for an element to become available.
public void	put(E the element to add e) Implements java.util.concurrent.BlockingQueue.put. Inserts the specified element into this priority queue.
private void	readObject(ObjectInputStream the stream s) Reconstitutes this queue from a stream (that is, deserializes it).
public int	Returns: `Integer.MAX_VALUE` always remainingCapacity() Implements java.util.concurrent.BlockingQueue.remainingCapacity. Always returns `Integer.MAX_VALUE` because a `PriorityBlockingQueue` is not capacity constrained.
public boolean	Returns: `true` if this queue changed as a result of the call remove(Object element to be removed from this queue, if present o) Overrides java.util.AbstractCollection.remove. Implements java.util.concurrent.BlockingQueue.remove, java.util.Collection.remove. Removes a single instance of the specified element from this queue, if it is present.
public boolean	removeAll(Collection<?> c) Overrides java.util.AbstractCollection.removeAll. Implements java.util.Collection.removeAll. Removes all of this collection's elements that are also contained in the specified collection (optional operation).
private void	removeAt(int i) Removes the ith element from queue.
pack-priv void	removeEq(Object element to be removed from this queue, if present o) Identity-based version for use in Itr.remove.
public boolean	removeIf(Predicate<? super E> filter) Overrides default java.util.Collection.removeIf. Removes all of the elements of this collection that satisfy the given predicate (optional operation).
public boolean	retainAll(Collection<?> c) Overrides java.util.AbstractCollection.retainAll. Implements java.util.Collection.retainAll. Retains only the elements in this collection that are contained in the specified collection (optional operation).
private static void	setBit(long[] bits, int i)
private static <T> void	siftDownComparable(int the position to fill k, T the item to insert x, Object[] the heap array es, int heap size n) Inserts item x at position k, maintaining heap invariant by demoting x down the tree repeatedly until it is less than or equal to its children or is a leaf.
private static <T> void	siftDownUsingComparator(int k, T x, Object[] es, int n, Comparator<? super T> cmp)
private static <T> void	siftUpComparable(int the position to fill k, T the item to insert x, Object[] the heap array es) Inserts item x at position k, maintaining heap invariant by promoting x up the tree until it is greater than or equal to its parent, or is the root.
private static <T> void	siftUpUsingComparator(int k, T x, Object[] es, Comparator<? super T> cmp)
public int	size() Implements abstract java.util.AbstractCollection.size. Implements java.util.Collection.size. Returns the number of elements in this collection.
public Spliterator<E>	Returns: a `Spliterator` over the elements in this queue spliterator() Overrides default java.util.Collection.spliterator. Returns a `Spliterator` over the elements in this queue.
public E	take() Implements java.util.concurrent.BlockingQueue.take. Retrieves and removes the head of this queue, waiting if necessary until an element becomes available.
public Object[]	Returns: an array containing all of the elements in this queue toArray() Overrides java.util.AbstractCollection.toArray. Implements java.util.Collection.toArray. Returns an array containing all of the elements in this queue.
public <T> T[]	Returns: an array containing all of the elements in this queue toArray(T[] the array into which the elements of the queue are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose a) Overrides java.util.AbstractCollection.toArray. Implements java.util.Collection.toArray. Returns an array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array.
public String	toString() Overrides java.util.AbstractCollection.toString. Returns a string representation of this collection.
private void	tryGrow(Object[] the heap array array, int the length of the array oldCap) Tries to grow array to accommodate at least one more element (but normally expand by about 50%), giving up (allowing retry) on contention (which we expect to be rare).
private void	writeObject(ObjectOutputStream the stream s) Saves this queue to a stream (that is, serializes it).

Inherited from java.util.AbstractQueue:: addAll element remove

Field Detail

allocationSpinLock	back to summary
private transient volatile int allocationSpinLock Spinlock for allocation, acquired via CAS.

ALLOCATIONSPINLOCK	back to summary
private static final VarHandle ALLOCATIONSPINLOCK

comparator	back to summary
private transient Comparator<? super E> comparator The comparator, or null if priority queue uses elements' natural ordering.

DEFAULT_INITIAL_CAPACITY	back to summary
private static final int DEFAULT_INITIAL_CAPACITY Default array capacity.

lock	back to summary
private final ReentrantLock lock

notEmpty	back to summary
private final Condition notEmpty Annotations @SuppressWarnings:serial

q	back to summary
private PriorityQueue<E> q

queue	back to summary
private transient Object[] queue Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2n+1] and queue[2(n+1)]. The priority queue is ordered by comparator, or by the elements' natural ordering, if comparator is null: For each node n in the heap and each descendant d of n, n <= d. The element with the lowest value is in queue[0], assuming the queue is nonempty.

queue

back to summary

private transient Object[] queue

Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The priority queue is ordered by comparator, or by the elements' natural ordering, if comparator is null: For each node n in the heap and each descendant d of n, n <= d. The element with the lowest value is in queue[0], assuming the queue is nonempty.

serialVersionUID	back to summary
private static final long serialVersionUID

size	back to summary
private transient int size The number of elements in the priority queue.

Constructor Detail

PriorityBlockingQueue	back to summary
public PriorityBlockingQueue() Creates a `PriorityBlockingQueue` with the default initial capacity (11) that orders its elements according to their natural ordering.

PriorityBlockingQueue back to summary

PriorityBlockingQueue	back to summary
public PriorityBlockingQueue(int initialCapacity) Creates a `PriorityBlockingQueue` with the specified initial capacity that orders its elements according to their natural ordering. Parameters initialCapacity:int the initial capacity for this priority queue Exceptions IllegalArgumentException: if `initialCapacity` is less than 1

public PriorityBlockingQueue(int initialCapacity)

Creates a PriorityBlockingQueue with the specified initial capacity that orders its elements according to their natural ordering.

Parameters

initialCapacity:int: the initial capacity for this priority queue

Exceptions

IllegalArgumentException:: if initialCapacity is less than 1

PriorityBlockingQueue back to summary

PriorityBlockingQueue	back to summary
public PriorityBlockingQueue(int initialCapacity, Comparator<? super E> comparator) Creates a `PriorityBlockingQueue` with the specified initial capacity that orders its elements according to the specified comparator. Parameters initialCapacity:int the initial capacity for this priority queue comparator:Comparator<? super E> the comparator that will be used to order this priority queue. If `null`, the natural ordering of the elements will be used. Exceptions IllegalArgumentException: if `initialCapacity` is less than 1

public PriorityBlockingQueue(int initialCapacity, Comparator<? super E> comparator)

Creates a PriorityBlockingQueue with the specified initial capacity that orders its elements according to the specified comparator.

Parameters

initialCapacity:int: the initial capacity for this priority queue
comparator:Comparator<? super E>: the comparator that will be used to order this priority queue. If null, the natural ordering of the elements will be used.

Exceptions

IllegalArgumentException:: if initialCapacity is less than 1

PriorityBlockingQueue back to summary

PriorityBlockingQueue	back to summary
public PriorityBlockingQueue(Collection<? extends E> c) Creates a `PriorityBlockingQueue` containing the elements in the specified collection. If the specified collection is a `SortedSet` or a `PriorityBlockingQueue`, this priority queue will be ordered according to the same ordering. Otherwise, this priority queue will be ordered according to the natural ordering of its elements. Parameters c:Collection<? extends E> the collection whose elements are to be placed into this priority queue Exceptions ClassCastException: if elements of the specified collection cannot be compared to one another according to the priority queue's ordering NullPointerException: if the specified collection or any of its elements are null

public PriorityBlockingQueue(Collection<? extends E> c)

Creates a PriorityBlockingQueue containing the elements in the specified collection. If the specified collection is a SortedSet or a PriorityBlockingQueue, this priority queue will be ordered according to the same ordering. Otherwise, this priority queue will be ordered according to the natural ordering of its elements.

Parameters

c:Collection<? extends E>: the collection whose elements are to be placed into this priority queue

Exceptions

ClassCastException:: if elements of the specified collection cannot be compared to one another according to the priority queue's ordering
NullPointerException:: if the specified collection or any of its elements are null

Method Detail

add back to summary

add	back to summary
public boolean add(E e) Overrides java.util.AbstractQueue.add. Implements java.util.concurrent.BlockingQueue.add, java.util.Queue.add, java.util.Collection.add. Inserts the specified element into this priority queue. Parameters e:E the element to add Returns:boolean `true` (as specified by `Collection#add`) Exceptions ClassCastException: if the specified element cannot be compared with elements currently in the priority queue according to the priority queue's ordering NullPointerException: if the specified element is null

public boolean add(E e)

Overrides java.util.AbstractQueue.add.

Implements java.util.concurrent.BlockingQueue.add, java.util.Queue.add, java.util.Collection.add.

Inserts the specified element into this priority queue.

Parameters

e:E: the element to add

Returns:boolean

true (as specified by Collection#add)

Exceptions

ClassCastException:: if the specified element cannot be compared with elements currently in the priority queue according to the priority queue's ordering
NullPointerException:: if the specified element is null

bulkRemove	back to summary
private boolean bulkRemove(Predicate<? super E> filter) Implementation of bulk remove methods.

clear	back to summary
public void clear() Overrides java.util.AbstractQueue.clear. Implements java.util.Collection.clear. Atomically removes all of the elements from this queue. The queue will be empty after this call returns.

clear

back to summary

public void clear()

Overrides java.util.AbstractQueue.clear.

Implements java.util.Collection.clear.

Atomically removes all of the elements from this queue. The queue will be empty after this call returns.

comparator back to summary

comparator	back to summary
public Comparator<? super E> comparator() Returns the comparator used to order the elements in this queue, or `null` if this queue uses the natural ordering of its elements. Returns:Comparator<? super E> the comparator used to order the elements in this queue, or `null` if this queue uses the natural ordering of its elements

public Comparator<? super E> comparator()

Returns the comparator used to order the elements in this queue, or null if this queue uses the natural ordering of its elements.

Returns:Comparator<? super E>: the comparator used to order the elements in this queue, or null if this queue uses the natural ordering of its elements

contains back to summary

contains	back to summary
public boolean contains(Object o) Overrides java.util.AbstractCollection.contains. Implements java.util.concurrent.BlockingQueue.contains, java.util.Collection.contains. Returns `true` if this queue contains the specified element. More formally, returns `true` if and only if this queue contains at least one element `e` such that `o.equals(e)`. Parameters o:Object object to be checked for containment in this queue Returns:boolean `true` if this queue contains the specified element

public boolean contains(Object o)

Overrides java.util.AbstractCollection.contains.

Implements java.util.concurrent.BlockingQueue.contains, java.util.Collection.contains.

Returns true if this queue contains the specified element. More formally, returns true if and only if this queue contains at least one element e such that o.equals(e).

Parameters

o:Object: object to be checked for containment in this queue

Returns:boolean

true if this queue contains the specified element

dequeue	back to summary
private E dequeue() Mechanics for poll(). Call only while holding lock.

drainTo back to summary

drainTo	back to summary
public int drainTo(Collection<? super E> c) Implements java.util.concurrent.BlockingQueue.drainTo. Doc from java.util.concurrent.BlockingQueue.drainTo. Removes all available elements from this queue and adds them to the given collection. This operation may be more efficient than repeatedly polling this queue. A failure encountered while attempting to add elements to collection `c` may result in elements being in neither, either or both collections when the associated exception is thrown. Attempts to drain a queue to itself result in `IllegalArgumentException`. Further, the behavior of this operation is undefined if the specified collection is modified while the operation is in progress. Exceptions UnsupportedOperationException: if addition of elements is not supported by the specified collection ClassCastException: if the class of an element of this queue prevents it from being added to the specified collection NullPointerException: if the specified collection is null IllegalArgumentException: if the specified collection is this queue, or some property of an element of this queue prevents it from being added to the specified collection

public int drainTo(Collection<? super E> c)

Implements java.util.concurrent.BlockingQueue.drainTo.

Doc from java.util.concurrent.BlockingQueue.drainTo.

Removes all available elements from this queue and adds them to the given collection. This operation may be more efficient than repeatedly polling this queue. A failure encountered while attempting to add elements to collection c may result in elements being in neither, either or both collections when the associated exception is thrown. Attempts to drain a queue to itself result in IllegalArgumentException. Further, the behavior of this operation is undefined if the specified collection is modified while the operation is in progress.

Exceptions

UnsupportedOperationException:: if addition of elements is not supported by the specified collection
ClassCastException:: if the class of an element of this queue prevents it from being added to the specified collection
NullPointerException:: if the specified collection is null
IllegalArgumentException:: if the specified collection is this queue, or some property of an element of this queue prevents it from being added to the specified collection

drainTo back to summary

drainTo	back to summary
public int drainTo(Collection<? super E> c, int maxElements) Implements java.util.concurrent.BlockingQueue.drainTo. Doc from java.util.concurrent.BlockingQueue.drainTo. Removes at most the given number of available elements from this queue and adds them to the given collection. A failure encountered while attempting to add elements to collection `c` may result in elements being in neither, either or both collections when the associated exception is thrown. Attempts to drain a queue to itself result in `IllegalArgumentException`. Further, the behavior of this operation is undefined if the specified collection is modified while the operation is in progress. Exceptions UnsupportedOperationException: if addition of elements is not supported by the specified collection ClassCastException: if the class of an element of this queue prevents it from being added to the specified collection NullPointerException: if the specified collection is null IllegalArgumentException: if the specified collection is this queue, or some property of an element of this queue prevents it from being added to the specified collection

public int drainTo(Collection<? super E> c, int maxElements)

Implements java.util.concurrent.BlockingQueue.drainTo.

Doc from java.util.concurrent.BlockingQueue.drainTo.

Removes at most the given number of available elements from this queue and adds them to the given collection. A failure encountered while attempting to add elements to collection c may result in elements being in neither, either or both collections when the associated exception is thrown. Attempts to drain a queue to itself result in IllegalArgumentException. Further, the behavior of this operation is undefined if the specified collection is modified while the operation is in progress.

Exceptions

UnsupportedOperationException:: if addition of elements is not supported by the specified collection
ClassCastException:: if the class of an element of this queue prevents it from being added to the specified collection
NullPointerException:: if the specified collection is null
IllegalArgumentException:: if the specified collection is this queue, or some property of an element of this queue prevents it from being added to the specified collection

ensureNonEmpty	back to summary
private static Object[] ensureNonEmpty(Object[] es) Ensures that queue[0] exists, helping peek() and poll().

forEach back to summary

forEach	back to summary
public void forEach(Consumer<? super E> action) Overrides default java.lang.Iterable.forEach. Doc from java.lang.Iterable.forEach. Performs the given action for each element of the `Iterable` until all elements have been processed or the action throws an exception. Actions are performed in the order of iteration, if that order is specified. Exceptions thrown by the action are relayed to the caller. The behavior of this method is unspecified if the action performs side-effects that modify the underlying source of elements, unless an overriding class has specified a concurrent modification policy. Exceptions NullPointerException: if the specified action is null

public void forEach(Consumer<? super E> action)

Overrides default java.lang.Iterable.forEach.

Doc from java.lang.Iterable.forEach.

Performs the given action for each element of the Iterable until all elements have been processed or the action throws an exception. Actions are performed in the order of iteration, if that order is specified. Exceptions thrown by the action are relayed to the caller.

The behavior of this method is unspecified if the action performs side-effects that modify the underlying source of elements, unless an overriding class has specified a concurrent modification policy.

Exceptions

NullPointerException:: if the specified action is null

heapify	back to summary
private void heapify() Establishes the heap invariant (described above) in the entire tree, 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).

indexOf	back to summary
private int indexOf(Object o)

isClear	back to summary
private static boolean isClear(long[] bits, int i)

iterator	back to summary
public Iterator<E> iterator() Implements abstract java.util.AbstractCollection.iterator. Implements java.util.Collection.iterator. Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order. The returned iterator is weakly consistent. Returns:Iterator<E> an iterator over the elements in this queue

iterator

back to summary

public Iterator<E> iterator()

Implements abstract java.util.AbstractCollection.iterator.

Implements java.util.Collection.iterator.

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.

The returned iterator is weakly consistent.

Returns:Iterator<E>: an iterator over the elements in this queue

nBits	back to summary
private static long[] nBits(int n)

offer back to summary

offer	back to summary
public boolean offer(E e) Implements java.util.concurrent.BlockingQueue.offer, java.util.Queue.offer. Inserts the specified element into this priority queue. As the queue is unbounded, this method will never return `false`. Parameters e:E the element to add Returns:boolean `true` (as specified by `Queue#offer`) Exceptions ClassCastException: if the specified element cannot be compared with elements currently in the priority queue according to the priority queue's ordering NullPointerException: if the specified element is null

public boolean offer(E e)

Implements java.util.concurrent.BlockingQueue.offer, java.util.Queue.offer.

Inserts the specified element into this priority queue. As the queue is unbounded, this method will never return false.

Parameters

e:E: the element to add

Returns:boolean

true (as specified by Queue#offer)

Exceptions

ClassCastException:: if the specified element cannot be compared with elements currently in the priority queue according to the priority queue's ordering
NullPointerException:: if the specified element is null

offer back to summary

offer	back to summary
public boolean offer(E e, long timeout, TimeUnit unit) Implements java.util.concurrent.BlockingQueue.offer. Inserts the specified element into this priority queue. As the queue is unbounded, this method will never block or return `false`. Parameters e:E the element to add timeout:long This parameter is ignored as the method never blocks unit:TimeUnit This parameter is ignored as the method never blocks Returns:boolean `true` (as specified by `BlockingQueue.offer`) Exceptions ClassCastException: if the specified element cannot be compared with elements currently in the priority queue according to the priority queue's ordering NullPointerException: if the specified element is null

public boolean offer(E e, long timeout, TimeUnit unit)

Implements java.util.concurrent.BlockingQueue.offer.

Inserts the specified element into this priority queue. As the queue is unbounded, this method will never block or return false.

Parameters

e:E: the element to add
timeout:long: This parameter is ignored as the method never blocks
unit:TimeUnit: This parameter is ignored as the method never blocks

Returns:boolean

true (as specified by BlockingQueue.offer)

Exceptions

ClassCastException:: if the specified element cannot be compared with elements currently in the priority queue according to the priority queue's ordering
NullPointerException:: if the specified element is null

peek back to summary

peek	back to summary
public E peek() Implements java.util.Queue.peek. Doc from java.util.Queue.peek. Retrieves, but does not remove, the head of this queue, or returns `null` if this queue is empty.

public E peek()

Implements java.util.Queue.peek.

Doc from java.util.Queue.peek.

Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

poll back to summary

poll	back to summary
public E poll() Implements java.util.Queue.poll. Doc from java.util.Queue.poll. Retrieves and removes the head of this queue, or returns `null` if this queue is empty.

public E poll()

Implements java.util.Queue.poll.

Doc from java.util.Queue.poll.

Retrieves and removes the head of this queue, or returns null if this queue is empty.

poll	back to summary
public E poll(long timeout, TimeUnit unit) throws InterruptedException Implements java.util.concurrent.BlockingQueue.poll. Doc from java.util.concurrent.BlockingQueue.poll. Retrieves and removes the head of this queue, waiting up to the specified wait time if necessary for an element to become available. Exceptions InterruptedException: if interrupted while waiting

poll

back to summary

public E poll(long timeout, TimeUnit unit) throws InterruptedException

Implements java.util.concurrent.BlockingQueue.poll.

Doc from java.util.concurrent.BlockingQueue.poll.

Retrieves and removes the head of this queue, waiting up to the specified wait time if necessary for an element to become available.

Exceptions

InterruptedException:: if interrupted while waiting

put	back to summary
public void put(E e) Implements java.util.concurrent.BlockingQueue.put. Inserts the specified element into this priority queue. As the queue is unbounded, this method will never block. Parameters e:E the element to add Exceptions ClassCastException: if the specified element cannot be compared with elements currently in the priority queue according to the priority queue's ordering NullPointerException: if the specified element is null

put

back to summary

public void put(E e)

Implements java.util.concurrent.BlockingQueue.put.

Inserts the specified element into this priority queue. As the queue is unbounded, this method will never block.

Parameters

e:E: the element to add

Exceptions

ClassCastException:: if the specified element cannot be compared with elements currently in the priority queue according to the priority queue's ordering
NullPointerException:: if the specified element is null

readObject	back to summary
private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException Reconstitutes this queue from a stream (that is, deserializes it). Parameters s:ObjectInputStream the stream Exceptions IOException: if an I/O error occurs ClassNotFoundException: if the class of a serialized object could not be found

readObject

back to summary

private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException

Reconstitutes this queue from a stream (that is, deserializes it).

Parameters

s:ObjectInputStream: the stream

Exceptions

IOException:: if an I/O error occurs
ClassNotFoundException:: if the class of a serialized object could not be found

remainingCapacity back to summary

remainingCapacity	back to summary
public int remainingCapacity() Implements java.util.concurrent.BlockingQueue.remainingCapacity. Always returns `Integer.MAX_VALUE` because a `PriorityBlockingQueue` is not capacity constrained. Returns:int `Integer.MAX_VALUE` always

public int remainingCapacity()

Implements java.util.concurrent.BlockingQueue.remainingCapacity.

Always returns Integer.MAX_VALUE because a PriorityBlockingQueue is not capacity constrained.

Returns:int: Integer.MAX_VALUE always

remove back to summary

remove	back to summary
public boolean remove(Object o) Overrides java.util.AbstractCollection.remove. Implements java.util.concurrent.BlockingQueue.remove, java.util.Collection.remove. Removes a single instance of the specified element from this queue, if it is present. More formally, removes an element `e` such that `o.equals(e)`, if this queue contains one or more such elements. Returns `true` if and only if this queue contained the specified element (or equivalently, if this queue changed as a result of the call). Parameters o:Object element to be removed from this queue, if present Returns:boolean `true` if this queue changed as a result of the call

public boolean remove(Object o)

Overrides java.util.AbstractCollection.remove.

Implements java.util.concurrent.BlockingQueue.remove, java.util.Collection.remove.

Removes a single instance of the specified element from this queue, if it is present. More formally, removes an element e such that o.equals(e), if this queue contains one or more such elements. Returns true if and only if this queue contained the specified element (or equivalently, if this queue changed as a result of the call).

Parameters

o:Object: element to be removed from this queue, if present

Returns:boolean

true if this queue changed as a result of the call

removeAll	back to summary
public boolean removeAll(Collection<?> c) Overrides java.util.AbstractCollection.removeAll. Implements java.util.Collection.removeAll. Doc from java.util.Collection.removeAll. Removes all of this collection's elements that are also contained in the specified collection (optional operation). After this call returns, this collection will contain no elements in common with the specified collection. Exceptions NullPointerException: if this collection contains one or more null elements and the specified collection does not support null elements (optional) or if the specified collection is null

removeAll

back to summary

public boolean removeAll(Collection<?> c)

Overrides java.util.AbstractCollection.removeAll.

Implements java.util.Collection.removeAll.

Doc from java.util.Collection.removeAll.

Removes all of this collection's elements that are also contained in the specified collection (optional operation). After this call returns, this collection will contain no elements in common with the specified collection.

Exceptions

NullPointerException:: if this collection contains one or more null elements and the specified collection does not support null elements (optional) or if the specified collection is null

removeAt	back to summary
private void removeAt(int i) Removes the ith element from queue.

removeEq	back to summary
pack-priv void removeEq(Object o) Identity-based version for use in Itr.remove. Parameters o:Object element to be removed from this queue, if present

removeEq

back to summary

pack-priv void removeEq(Object o)

Identity-based version for use in Itr.remove.

Parameters

o:Object: element to be removed from this queue, if present

removeIf	back to summary
public boolean removeIf(Predicate<? super E> filter) Overrides default java.util.Collection.removeIf. Doc from java.util.Collection.removeIf. Removes all of the elements of this collection that satisfy the given predicate (optional operation). Errors or runtime exceptions thrown during iteration or by the predicate are relayed to the caller. Exceptions NullPointerException: if the specified filter is null

removeIf

back to summary

public boolean removeIf(Predicate<? super E> filter)

Overrides default java.util.Collection.removeIf.

Doc from java.util.Collection.removeIf.

Removes all of the elements of this collection that satisfy the given predicate (optional operation). Errors or runtime exceptions thrown during iteration or by the predicate are relayed to the caller.

Exceptions

NullPointerException:: if the specified filter is null

retainAll	back to summary
public boolean retainAll(Collection<?> c) Overrides java.util.AbstractCollection.retainAll. Implements java.util.Collection.retainAll. Doc from java.util.Collection.retainAll. Retains only the elements in this collection that are contained in the specified collection (optional operation). In other words, removes from this collection all of its elements that are not contained in the specified collection. Exceptions NullPointerException: if this collection contains one or more null elements and the specified collection does not permit null elements (optional) or if the specified collection is null

retainAll

back to summary

public boolean retainAll(Collection<?> c)

Overrides java.util.AbstractCollection.retainAll.

Implements java.util.Collection.retainAll.

Doc from java.util.Collection.retainAll.

Retains only the elements in this collection that are contained in the specified collection (optional operation). In other words, removes from this collection all of its elements that are not contained in the specified collection.

Exceptions

NullPointerException:: if this collection contains one or more null elements and the specified collection does not permit null elements (optional) or if the specified collection is null

setBit	back to summary
private static void setBit(long[] bits, int i)

siftDownComparable	back to summary
private static <T> void siftDownComparable(int k, T x, Object[] es, int n) Inserts item x at position k, maintaining heap invariant by demoting x down the tree repeatedly until it is less than or equal to its children or is a leaf. Parameters k:int the position to fill x:T the item to insert es:Object[] the heap array n:int heap size

siftDownComparable

back to summary

private static <T> void siftDownComparable(int k, T x, Object[] es, int n)

Inserts item x at position k, maintaining heap invariant by demoting x down the tree repeatedly until it is less than or equal to its children or is a leaf.

Parameters

k:int: the position to fill
x:T: the item to insert
es:Object[]: the heap array
n:int: heap size

siftDownUsingComparator	back to summary
private static <T> void siftDownUsingComparator(int k, T x, Object[] es, int n, Comparator<? super T> cmp)

siftUpComparable

back to summary

private static <T> void siftUpComparable(int k, T x, Object[] es)

Inserts item x at position k, maintaining heap invariant by 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 Comparable and Comparator versions are separated into different methods that are otherwise identical. (Similarly for siftDown.)

Parameters

k:int: the position to fill
x:T: the item to insert
es:Object[]: the heap array

siftUpUsingComparator	back to summary
private static <T> void siftUpUsingComparator(int k, T x, Object[] es, Comparator<? super T> cmp)

size back to summary

public int size()

Implements abstract java.util.AbstractCollection.size.

Implements java.util.Collection.size.

Doc from java.util.Collection.size.

Returns the number of elements in this collection. If this collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

spliterator back to summary

public Spliterator<E> spliterator()

Overrides default java.util.Collection.spliterator.

Returns a Spliterator over the elements in this queue. The spliterator does not traverse elements in any particular order (the ORDERED characteristic is not reported).

The returned spliterator is weakly consistent.

The Spliterator reports Spliterator#SIZED and Spliterator#NONNULL.

Implementation Note

The Spliterator additionally reports Spliterator#SUBSIZED.

Returns:Spliterator<E>: a Spliterator over the elements in this queue
Since: 1.8

take

back to summary

public E take() throws InterruptedException

Implements java.util.concurrent.BlockingQueue.take.

Doc from java.util.concurrent.BlockingQueue.take.

Retrieves and removes the head of this queue, waiting if necessary until an element becomes available.

Exceptions

InterruptedException:: if interrupted while waiting

toArray

back to summary

public Object[] toArray()

Overrides java.util.AbstractCollection.toArray.

Implements java.util.Collection.toArray.

Returns an array containing all of the elements in this queue. The returned array elements are in no particular order.

The returned array will be "safe" in that no references to it are maintained by this queue. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array.

This method acts as bridge between array-based and collection-based APIs.

Returns:Object[]: an array containing all of the elements in this queue

toArray back to summary

public <T> T[] toArray(T[] a)

Overrides java.util.AbstractCollection.toArray.

Implements java.util.Collection.toArray.

Returns an array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array. The returned array elements are in no particular order. If the queue fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this queue.

If this queue fits in the specified array with room to spare (i.e., the array has more elements than this queue), the element in the array immediately following the end of the queue is set to null.

Like the toArray() method, this method acts as bridge between array-based and collection-based APIs. Further, this method allows precise control over the runtime type of the output array, and may, under certain circumstances, be used to save allocation costs.

Suppose x is a queue known to contain only strings. The following code can be used to dump the queue into a newly allocated array of String:

 String[] y = x.toArray(new String[0]);

Note that toArray(new Object[0]) is identical in function to toArray().

Parameters

a:T[]: the array into which the elements of the queue are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose

Returns:T[]

an array containing all of the elements in this queue

Exceptions

ArrayStoreException:: if the runtime type of the specified array is not a supertype of the runtime type of every element in this queue
NullPointerException:: if the specified array is null

toString back to summary

public String toString()

Overrides java.util.AbstractCollection.toString.

Doc from java.util.AbstractCollection.toString.

Returns a string representation of this collection. The string representation consists of a list of the collection's elements in the order they are returned by its iterator, enclosed in square brackets ("[]"). Adjacent elements are separated by the characters ", " (comma and space). Elements are converted to strings as by String#valueOf(Object).

tryGrow

back to summary

private void tryGrow(Object[] array, int oldCap)

Tries to grow array to accommodate at least one more element (but normally expand by about 50%), giving up (allowing retry) on contention (which we expect to be rare). Call only while holding lock.

Parameters

array:Object[]: the heap array
oldCap:int: the length of the array

writeObject

back to summary

private void writeObject(ObjectOutputStream s) throws IOException

Saves this queue to a stream (that is, serializes it). For compatibility with previous version of this class, elements are first copied to a java.util.PriorityQueue, which is then serialized.

Parameters

s:ObjectOutputStream: the stream

Exceptions

IOException:: if an I/O error occurs

java.util.concurrent back to summary

pack-priv final Class PriorityBlockingQueue.Itr

Class Inheritance

extends Object
implements Iterator<E>

java.lang.Object
java.util.concurrent.PriorityBlockingQueue.Itr

All Implemented Interfaces

java.util.Iterator

Snapshot iterator that works off copy of underlying q array.

Field Summary

Modifier and Type	Field and Description
pack-priv final Object[]	array
pack-priv int	cursor
pack-priv int	lastRet

Constructor Summary

Access	Constructor and Description
pack-priv	Itr(Object[] array)

Method Summary

Modifier and Type	Method and Description
public void	forEachRemaining(Consumer<? super E> action) Overrides default java.util.Iterator.forEachRemaining. Performs the given action for each remaining element until all elements have been processed or the action throws an exception.
public boolean	hasNext() Implements java.util.Iterator.hasNext. Returns `true` if the iteration has more elements.
public E	next() Implements java.util.Iterator.next. Returns the next element in the iteration.
public void	remove() Overrides default java.util.Iterator.remove. Removes from the underlying collection the last element returned by this iterator (optional operation).

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

array	back to summary
pack-priv final Object[] array

cursor	back to summary
pack-priv int cursor

lastRet	back to summary
pack-priv int lastRet

Constructor Detail

Itr	back to summary
pack-priv Itr(Object[] array)

Method Detail

forEachRemaining back to summary

public void forEachRemaining(Consumer<? super E> action)

Overrides default java.util.Iterator.forEachRemaining.

Doc from java.util.Iterator.forEachRemaining.

Performs the given action for each remaining element until all elements have been processed or the action throws an exception. Actions are performed in the order of iteration, if that order is specified. Exceptions thrown by the action are relayed to the caller.

The behavior of an iterator is unspecified if the action modifies the collection in any way (even by calling the remove method or other mutator methods of Iterator subtypes), unless an overriding class has specified a concurrent modification policy.

Subsequent behavior of an iterator is unspecified if the action throws an exception.

hasNext back to summary

public boolean hasNext()

Implements java.util.Iterator.hasNext.

Doc from java.util.Iterator.hasNext.

Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)

back to summary

public E next()

Implements java.util.Iterator.next.

Doc from java.util.Iterator.next.

Returns the next element in the iteration.

remove back to summary

public void remove()

Overrides default java.util.Iterator.remove.

Doc from java.util.Iterator.remove.

Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next.

The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method, unless an overriding class has specified a concurrent modification policy.

The behavior of an iterator is unspecified if this method is called after a call to the forEachRemaining method.

java.util.concurrent back to summary

pack-priv final Class PriorityBlockingQueue.PBQSpliterator

Class Inheritance

extends Object
implements Spliterator<E>

java.lang.Object
java.util.concurrent.PriorityBlockingQueue.PBQSpliterator

All Implemented Interfaces

java.util.Spliterator

Immutable snapshot spliterator that binds to elements "late".

Field Summary

Modifier and Type	Field and Description
pack-priv Object[]	array
pack-priv int	fence
pack-priv int	index

Constructor Summary

Access	Constructor and Description
pack-priv	PBQSpliterator()
pack-priv	PBQSpliterator(Object[] array, int index, int fence)

Method Summary

Modifier and Type	Method and Description
public int	characteristics() Implements java.util.Spliterator.characteristics. Returns a set of characteristics of this Spliterator and its elements.
public long	estimateSize() Implements java.util.Spliterator.estimateSize. Returns an estimate of the number of elements that would be encountered by a `forEachRemaining` traversal, or returns `Long#MAX_VALUE` if infinite, unknown, or too expensive to compute.
public void	forEachRemaining(Consumer<? super E> action) Overrides default java.util.Spliterator.forEachRemaining. Performs the given action for each remaining element, sequentially in the current thread, until all elements have been processed or the action throws an exception.
private int	getFence()
public boolean	tryAdvance(Consumer<? super E> action) Implements java.util.Spliterator.tryAdvance. If a remaining element exists: performs the given action on it, returning `true`; else returns `false`.
public PriorityBlockingQueue<E>.PBQSpliterator	trySplit() Implements java.util.Spliterator.trySplit. If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

array	back to summary
pack-priv Object[] array

fence	back to summary
pack-priv int fence

index	back to summary
pack-priv int index

Constructor Detail

PBQSpliterator	back to summary
pack-priv PBQSpliterator()

PBQSpliterator	back to summary
pack-priv PBQSpliterator(Object[] array, int index, int fence)

Method Detail

characteristics back to summary

public int characteristics()

Implements java.util.Spliterator.characteristics.

Doc from java.util.Spliterator.characteristics.

Returns a set of characteristics of this Spliterator and its elements. The result is represented as ORed values from ORDERED, DISTINCT, SORTED, SIZED, NONNULL, IMMUTABLE, CONCURRENT, SUBSIZED. Repeated calls to characteristics() on a given spliterator, prior to or in-between calls to trySplit, should always return the same result.

If a Spliterator reports an inconsistent set of characteristics (either those returned from a single invocation or across multiple invocations), no guarantees can be made about any computation using this Spliterator.

estimateSize back to summary

public long estimateSize()

Implements java.util.Spliterator.estimateSize.

Doc from java.util.Spliterator.estimateSize.

Returns an estimate of the number of elements that would be encountered by a forEachRemaining traversal, or returns Long#MAX_VALUE if infinite, unknown, or too expensive to compute.

If this Spliterator is SIZED and has not yet been partially traversed or split, or this Spliterator is SUBSIZED and has not yet been partially traversed, this estimate must be an accurate count of elements that would be encountered by a complete traversal. Otherwise, this estimate may be arbitrarily inaccurate, but must decrease as specified across invocations of trySplit.

forEachRemaining back to summary

public void forEachRemaining(Consumer<? super E> action)

Overrides default java.util.Spliterator.forEachRemaining.

Doc from java.util.Spliterator.forEachRemaining.

Performs the given action for each remaining element, sequentially in the current thread, until all elements have been processed or the action throws an exception. If this Spliterator is ORDERED, actions are performed in encounter order. Exceptions thrown by the action are relayed to the caller.

Subsequent behavior of a spliterator is unspecified if the action throws an exception.

getFence	back to summary
private int getFence()

tryAdvance back to summary

public boolean tryAdvance(Consumer<? super E> action)

Implements java.util.Spliterator.tryAdvance.

Doc from java.util.Spliterator.tryAdvance.

If a remaining element exists: performs the given action on it, returning true; else returns false. If this Spliterator is ORDERED the action is performed on the next element in encounter order. Exceptions thrown by the action are relayed to the caller.

Subsequent behavior of a spliterator is unspecified if the action throws an exception.

trySplit back to summary

public PriorityBlockingQueue<E>.PBQSpliterator trySplit()

Implements java.util.Spliterator.trySplit.

Doc from java.util.Spliterator.trySplit.

If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator.

If this Spliterator is ORDERED, the returned Spliterator must cover a strict prefix of the elements.

Unless this Spliterator covers an infinite number of elements, repeated calls to trySplit() must eventually return null. Upon non-null return:

the value reported for estimateSize() before splitting, must, after splitting, be greater than or equal to estimateSize() for this and the returned Spliterator; and
if this Spliterator is SUBSIZED, then estimateSize() for this spliterator before splitting must be equal to the sum of estimateSize() for this and the returned Spliterator after splitting.

This method may return null for any reason, including emptiness, inability to split after traversal has commenced, data structure constraints, and efficiency considerations.

public Class PriorityBlockingQueue<E>

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv final Class PriorityBlockingQueue.Itr

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv final Class PriorityBlockingQueue.PBQSpliterator

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail