A double-ended priority queue, which provides constant-time access to both its least element and its greatest element, as determined by the queue's specified comparator. If no comparator is given at creation time, the natural order of elements is used. If no maximum size is given at creation time, the queue is unbounded.

Usage example:

MinMaxPriorityQueue<User> users = MinMaxPriorityQueue.orderedBy(userComparator)
    .maximumSize(1000)
    .create();

As a Queue it functions exactly as a PriorityQueue: its head element -- the implicit target of the methods peek(), poll() and remove() -- is defined as the least element in the queue according to the queue's comparator. But unlike a regular priority queue, the methods peekLast, pollLast and removeLast are also provided, to act on the greatest element in the queue instead.

A min-max priority queue can be configured with a maximum size. If so, each time the size of the queue exceeds that value, the queue automatically removes its greatest element according to its comparator (which might be the element that was just added). This is different from conventional bounded queues, which either block or reject new elements when full.

This implementation is based on the min-max heap developed by Atkinson, et al. Unlike many other double-ended priority queues, it stores elements in a single array, as compact as the traditional heap data structure used in PriorityQueue.

This class is not thread-safe, and does not accept null elements.

Performance notes:

If you only access one end of the queue, and do use a maximum size, this class will perform significantly worse than a PriorityQueue with manual eviction above the maximum size. In many cases Ordering#leastOf may work for your use case with significantly improved (and asymptotically superior) performance.
The retrieval operations peek, peekFirst, peekLast, element, and size are constant-time.
The enqueuing and dequeuing operations (offer, add, and all the forms of poll and remove()) run in O(log n) time.
The remove(Object) and contains operations require linear (O(n)) time.
If you only access one end of the queue, and don't use a maximum size, this class is functionally equivalent to PriorityQueue, but significantly slower.

Nested and Inner Type Summary

Modifier and Type	Class and Description
public static class	MinMaxPriorityQueue.Builder< the upper bound on the eventual type that can be produced by this builder (for example, a `Builder<Number>` can produce a `Queue<Number>` or `Queue<Integer>` but not a `Queue<Object>`). B> The builder class used in creation of min-max priority queues.
pack-priv class	MinMaxPriorityQueue.Heap Each instance of MinMaxPriorityQueue encapsulates two instances of Heap: a min-heap and a max-heap.
pack-priv static class	MinMaxPriorityQueue.MoveDesc<E>
private class	MinMaxPriorityQueue.QueueIterator Iterates the elements of the queue in no particular order.

Field Summary

Modifier and Type	Field and Description
private static final int	DEFAULT_CAPACITY
private static final int	EVEN_POWERS_OF_TWO
private final MinMaxPriorityQueue<E>.Heap	maxHeap
pack-priv final int	maximumSize
private final MinMaxPriorityQueue<E>.Heap	minHeap
private int	modCount
private static final int	ODD_POWERS_OF_TWO
private @Nullable Object[]	queue
private int	size

Constructor Summary

Access	Constructor and Description
private	MinMaxPriorityQueue(MinMaxPriorityQueue.Builder<? super E> builder, int queueSize)

Method Summary

Modifier and Type	Method and Description
public boolean	Returns: `true` always add(E the element to add element) Overrides java.util.AbstractQueue.add. Implements java.util.Queue.add, java.util.Collection.add. Adds the given element to this queue.
public boolean	addAll(Collection<? extends E> collection containing elements to be added to this queue newElements) Overrides java.util.AbstractQueue.addAll. Implements java.util.Collection.addAll. Adds all of the elements in the specified collection to this queue.
private int	calculateNewCapacity() Returns ~2x the old capacity if small; ~1.5x otherwise.
pack-priv int	capacity()
private static int	capAtMaximumSize(int queueSize, int maximumSize) There's no reason for the queueSize to ever be more than maxSize + 1
public void	clear() Overrides java.util.AbstractQueue.clear. Implements java.util.Collection.clear. Removes all of the elements from this queue.
public Comparator<? super E>	comparator() Returns the comparator used to order the elements in this queue.
public static <E extends Comparable<E>> MinMaxPriorityQueue<E>	create() Creates a new min-max priority queue with default settings: natural order, no maximum size, no initial contents, and an initial expected size of 11.
public static <E extends Comparable<E>> MinMaxPriorityQueue<E>	create(Iterable<? extends E> initialContents) Creates a new min-max priority queue using natural order, no maximum size, and initially containing the given elements.
pack-priv E	elementData(int index)
public static MinMaxPriorityQueue.Builder<Comparable<T>>	expectedSize(int expectedSize) Creates and returns a new builder, configured to build `MinMaxPriorityQueue` instances sized appropriately to hold `expectedSize` elements.
private MinMaxPriorityQueue.MoveDesc<E>	fillHole(int index, E toTrickle)
private int	getMaxElementIndex() Returns the index of the max element.
private void	growIfNeeded()
private MinMaxPriorityQueue<E>.Heap	heapForIndex(int i)
pack-priv static int	initialQueueSize(int configuredExpectedSize, int maximumSize, Iterable<?> initialContents)
pack-priv static boolean	isEvenLevel(int index)
pack-priv boolean	isIntact() Returns `true` if the MinMax heap structure holds.
public Iterator<E>	Returns: an iterator over the elements contained in this collection iterator() Implements abstract java.util.AbstractCollection.iterator. Implements java.util.Collection.iterator. Returns an iterator over the elements contained in this collection, in no particular order.
public static MinMaxPriorityQueue.Builder<Comparable<T>>	maximumSize(int maximumSize) Creates and returns a new builder, configured to build `MinMaxPriorityQueue` instances that are limited to `maximumSize` elements.
public boolean	offer(E the element to add element) Implements java.util.Queue.offer. Adds the given element to this queue.
public static <B> MinMaxPriorityQueue.Builder<B>	orderedBy(Comparator<B> comparator) Creates and returns a new builder, configured to build `MinMaxPriorityQueue` instances that use `comparator` to determine the least and greatest elements.
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	peekFirst() Retrieves, but does not remove, the least element of this queue, or returns `null` if the queue is empty.
public E	peekLast() Retrieves, but does not remove, the greatest element of this queue, or returns `null` if the 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	pollFirst() Removes and returns the least element of this queue, or returns `null` if the queue is empty.
public E	pollLast() Removes and returns the greatest element of this queue, or returns `null` if the queue is empty.
private E	removeAndGet(int index) Removes and returns the value at `index`.
pack-priv MinMaxPriorityQueue.MoveDesc<E>	removeAt(int index) Removes the element at position `index`.
public E	removeFirst() Removes and returns the least element of this queue.
public E	removeLast() Removes and returns the greatest element of this queue.
public int	size() Implements abstract java.util.AbstractCollection.size. Implements java.util.Collection.size. Returns the number of elements in this collection.
public Object[]	toArray() Overrides java.util.AbstractCollection.toArray. Implements java.util.Collection.toArray. Returns an array containing all of the elements in this collection.

Inherited from java.util.AbstractQueue:: element remove

Field Detail

DEFAULT_CAPACITY	back to summary
private static final int DEFAULT_CAPACITY

EVEN_POWERS_OF_TWO	back to summary
private static final int EVEN_POWERS_OF_TWO

maxHeap	back to summary
private final MinMaxPriorityQueue<E>.Heap maxHeap

maximumSize	back to summary
pack-priv final int maximumSize Annotations @VisibleForTesting

minHeap	back to summary
private final MinMaxPriorityQueue<E>.Heap minHeap

modCount	back to summary
private int modCount

ODD_POWERS_OF_TWO	back to summary
private static final int ODD_POWERS_OF_TWO

queue	back to summary
private @Nullable Object[] queue

size	back to summary
private int size

Constructor Detail

MinMaxPriorityQueue	back to summary
private MinMaxPriorityQueue(MinMaxPriorityQueue.Builder<? super E> builder, int queueSize)

Method Detail

add back to summary

add	back to summary
public boolean add(E element) Overrides java.util.AbstractQueue.add. Implements java.util.Queue.add, java.util.Collection.add. Adds the given element to this queue. If this queue has a maximum size, after adding `element` the queue will automatically evict its greatest element (according to its comparator), which may be `element` itself. Parameters element:E Doc from java.util.AbstractQueue.add. the element to add Returns:boolean `true` always Annotations @CanIgnoreReturnValue @Override

public boolean add(E element)

Overrides java.util.AbstractQueue.add.

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

Adds the given element to this queue. If this queue has a maximum size, after adding element the queue will automatically evict its greatest element (according to its comparator), which may be element itself.

Parameters

element:E

Doc from java.util.AbstractQueue.add.

the element to add

Returns:boolean

true always

Annotations

@CanIgnoreReturnValue
@Override

addAll back to summary

addAll	back to summary
public boolean addAll(Collection<? extends E> newElements) Overrides java.util.AbstractQueue.addAll. Implements java.util.Collection.addAll. Doc from java.util.AbstractQueue.addAll. Adds all of the elements in the specified collection to this queue. Attempts to addAll of 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. This implementation iterates over the specified collection, and adds each element returned by the iterator to this queue, in turn. A runtime exception encountered while trying to add an element (including, in particular, a `null` element) may result in only some of the elements having been successfully added when the associated exception is thrown. Parameters newElements:Collection<? extends E> collection containing elements to be added to this queue Returns:boolean `true` if this queue changed as a result of the call Annotations @CanIgnoreReturnValue @Override

public boolean addAll(Collection<? extends E> newElements)

Overrides java.util.AbstractQueue.addAll.

Implements java.util.Collection.addAll.

Doc from java.util.AbstractQueue.addAll.

Adds all of the elements in the specified collection to this queue. Attempts to addAll of 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.

This implementation iterates over the specified collection, and adds each element returned by the iterator to this queue, in turn. A runtime exception encountered while trying to add an element (including, in particular, a null element) may result in only some of the elements having been successfully added when the associated exception is thrown.

Parameters

newElements:Collection<? extends E>: collection containing elements to be added to this queue

Returns:boolean

true if this queue changed as a result of the call

Annotations

@CanIgnoreReturnValue
@Override

calculateNewCapacity	back to summary
private int calculateNewCapacity() Returns ~2x the old capacity if small; ~1.5x otherwise.

capacity	back to summary
pack-priv int capacity() Annotations @VisibleForTesting

capAtMaximumSize	back to summary
private static int capAtMaximumSize(int queueSize, int maximumSize) There's no reason for the queueSize to ever be more than maxSize + 1

clear back to summary

clear	back to summary
public void clear() Overrides java.util.AbstractQueue.clear. Implements java.util.Collection.clear. Doc from java.util.AbstractQueue.clear. Removes all of the elements from this queue. The queue will be empty after this call returns. This implementation repeatedly invokes `poll` until it returns `null`. Annotations @Override

public void clear()

Overrides java.util.AbstractQueue.clear.

Implements java.util.Collection.clear.

Doc from java.util.AbstractQueue.clear.

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

This implementation repeatedly invokes poll until it returns null.

Annotations

@Override

comparator	back to summary
public Comparator<? super E> comparator() Returns the comparator used to order the elements in this queue. Obeys the general contract of `PriorityQueue#comparator`, but returns `Ordering#natural` instead of `null` to indicate natural ordering.

create	back to summary
public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create() Creates a new min-max priority queue with default settings: natural order, no maximum size, no initial contents, and an initial expected size of 11.

create	back to summary
public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create(Iterable<? extends E> initialContents) Creates a new min-max priority queue using natural order, no maximum size, and initially containing the given elements.

elementData	back to summary
pack-priv E elementData(int index) Annotations @SuppressWarnings:unchecked

expectedSize back to summary

expectedSize	back to summary
public static MinMaxPriorityQueue.Builder<Comparable<T>> expectedSize(int expectedSize) Creates and returns a new builder, configured to build `MinMaxPriorityQueue` instances sized appropriately to hold `expectedSize` elements. Annotations @SuppressWarnings:rawtypes

public static MinMaxPriorityQueue.Builder<Comparable<T>> expectedSize(int expectedSize)

Creates and returns a new builder, configured to build MinMaxPriorityQueue instances sized appropriately to hold expectedSize elements.

Annotations

@SuppressWarnings:rawtypes

fillHole	back to summary
private MinMaxPriorityQueue.MoveDesc<E> fillHole(int index, E toTrickle) Annotations @CheckForNull

getMaxElementIndex	back to summary
private int getMaxElementIndex() Returns the index of the max element.

growIfNeeded	back to summary
private void growIfNeeded()

heapForIndex	back to summary
private MinMaxPriorityQueue<E>.Heap heapForIndex(int i)

initialQueueSize	back to summary
pack-priv static int initialQueueSize(int configuredExpectedSize, int maximumSize, Iterable<?> initialContents) Annotations @VisibleForTesting

isEvenLevel	back to summary
pack-priv static boolean isEvenLevel(int index) Annotations @VisibleForTesting

isIntact back to summary

isIntact	back to summary
pack-priv boolean isIntact() Returns `true` if the MinMax heap structure holds. This is only used in testing. TODO(kevinb): move to the test class? Annotations @VisibleForTesting

pack-priv boolean isIntact()

Returns true if the MinMax heap structure holds. This is only used in testing.

TODO(kevinb): move to the test class?

Annotations

@VisibleForTesting

iterator back to summary

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 contained in this collection, in no particular order. The iterator is fail-fast: If the MinMaxPriorityQueue is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will generally throw a `ConcurrentModificationException`. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw `ConcurrentModificationException` on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs. Returns:Iterator<E> an iterator over the elements contained in this collection Annotations @Override

public Iterator<E> iterator()

Implements abstract java.util.AbstractCollection.iterator.

Implements java.util.Collection.iterator.

Returns an iterator over the elements contained in this collection, in no particular order.

The iterator is fail-fast: If the MinMaxPriorityQueue is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will generally throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

Returns:Iterator<E>

an iterator over the elements contained in this collection

Annotations

@Override

maximumSize back to summary

maximumSize	back to summary
public static MinMaxPriorityQueue.Builder<Comparable<T>> maximumSize(int maximumSize) Creates and returns a new builder, configured to build `MinMaxPriorityQueue` instances that are limited to `maximumSize` elements. Each time a queue grows beyond this bound, it immediately removes its greatest element (according to its comparator), which might be the element that was just added. Annotations @SuppressWarnings:rawtypes

public static MinMaxPriorityQueue.Builder<Comparable<T>> maximumSize(int maximumSize)

Creates and returns a new builder, configured to build MinMaxPriorityQueue instances that are limited to maximumSize elements. Each time a queue grows beyond this bound, it immediately removes its greatest element (according to its comparator), which might be the element that was just added.

Annotations

@SuppressWarnings:rawtypes

offer back to summary

offer	back to summary
public boolean offer(E element) Implements java.util.Queue.offer. Adds the given element to this queue. If this queue has a maximum size, after adding `element` the queue will automatically evict its greatest element (according to its comparator), which may be `element` itself. Parameters element:E Doc from java.util.Queue.offer. the element to add Returns:boolean Doc from java.util.Queue.offer. `true` if the element was added to this queue, else `false` Annotations @CanIgnoreReturnValue @Override

public boolean offer(E element)

Implements java.util.Queue.offer.

Parameters

element:E

Doc from java.util.Queue.offer.

the element to add

Returns:boolean

Doc from java.util.Queue.offer.

true if the element was added to this queue, else false

Annotations

@CanIgnoreReturnValue
@Override

orderedBy	back to summary
public static <B> MinMaxPriorityQueue.Builder<B> orderedBy(Comparator<B> comparator) Creates and returns a new builder, configured to build `MinMaxPriorityQueue` instances that use `comparator` to determine the least and greatest elements.

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. Returns:E the head of this queue, or `null` if this queue is empty Annotations @Override @CheckForNull

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.

Returns:E

the head of this queue, or null if this queue is empty

Annotations

@Override
@CheckForNull

peekFirst back to summary

peekFirst	back to summary
public E peekFirst() Retrieves, but does not remove, the least element of this queue, or returns `null` if the queue is empty. Annotations @CheckForNull

public E peekFirst()

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

Annotations

@CheckForNull

peekLast back to summary

peekLast	back to summary
public E peekLast() Retrieves, but does not remove, the greatest element of this queue, or returns `null` if the queue is empty. Annotations @CheckForNull

public E peekLast()

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

Annotations

@CheckForNull

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. Returns:E the head of this queue, or `null` if this queue is empty Annotations @CanIgnoreReturnValue @Override @CheckForNull

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.

Returns:E

the head of this queue, or null if this queue is empty

Annotations

@CanIgnoreReturnValue
@Override
@CheckForNull

pollFirst back to summary

pollFirst	back to summary
public E pollFirst() Removes and returns the least element of this queue, or returns `null` if the queue is empty. Annotations @CanIgnoreReturnValue @CheckForNull

public E pollFirst()

Removes and returns the least element of this queue, or returns null if the queue is empty.

Annotations

@CanIgnoreReturnValue
@CheckForNull

pollLast back to summary

pollLast	back to summary
public E pollLast() Removes and returns the greatest element of this queue, or returns `null` if the queue is empty. Annotations @CanIgnoreReturnValue @CheckForNull

public E pollLast()

Removes and returns the greatest element of this queue, or returns null if the queue is empty.

Annotations

@CanIgnoreReturnValue
@CheckForNull

removeAndGet	back to summary
private E removeAndGet(int index) Removes and returns the value at `index`.

removeAt back to summary

removeAt	back to summary
pack-priv MinMaxPriorityQueue.MoveDesc<E> removeAt(int index) Removes the element at position `index`. Normally this method leaves the elements at up to `index - 1`, inclusive, untouched. Under these circumstances, it returns `null`. Occasionally, in order to maintain the heap invariant, it must swap a later element of the list with one before `index`. Under these circumstances it returns a pair of elements as a `MoveDesc`. The first one is the element that was previously at the end of the heap and is now at some position before `index`. The second element is the one that was swapped down to replace the element at `index`. This fact is used by iterator.remove so as to visit elements during a traversal once and only once. Annotations @VisibleForTesting @CanIgnoreReturnValue @CheckForNull

pack-priv MinMaxPriorityQueue.MoveDesc<E> removeAt(int index)

Removes the element at position index.

Normally this method leaves the elements at up to index - 1, inclusive, untouched. Under these circumstances, it returns null.

Occasionally, in order to maintain the heap invariant, it must swap a later element of the list with one before index. Under these circumstances it returns a pair of elements as a MoveDesc. The first one is the element that was previously at the end of the heap and is now at some position before index. The second element is the one that was swapped down to replace the element at index. This fact is used by iterator.remove so as to visit elements during a traversal once and only once.

Annotations

@VisibleForTesting
@CanIgnoreReturnValue
@CheckForNull

removeFirst	back to summary
public E removeFirst() Removes and returns the least element of this queue. Annotations @CanIgnoreReturnValue Exceptions NoSuchElementException: if the queue is empty

removeFirst

back to summary

public E removeFirst()

Removes and returns the least element of this queue.

Annotations

@CanIgnoreReturnValue

Exceptions

NoSuchElementException:: if the queue is empty

removeLast	back to summary
public E removeLast() Removes and returns the greatest element of this queue. Annotations @CanIgnoreReturnValue Exceptions NoSuchElementException: if the queue is empty

removeLast

back to summary

public E removeLast()

Removes and returns the greatest element of this queue.

Annotations

@CanIgnoreReturnValue

Exceptions

NoSuchElementException:: if the queue is empty

size back to summary

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`. Returns:int the number of elements in this collection Annotations @Override

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.

Returns:int

the number of elements in this collection

Annotations

@Override

toArray back to summary

toArray	back to summary
public Object[] toArray() Overrides java.util.AbstractCollection.toArray. Implements java.util.Collection.toArray. Doc from java.util.Collection.toArray. Returns an array containing all of the elements in this collection. If this collection makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order. The returned array's runtime component type is `Object`. The returned array will be "safe" in that no references to it are maintained by this collection. (In other words, this method must allocate a new array even if this collection is backed by an array). The caller is thus free to modify the returned array. Returns:Object[] an array, whose runtime component type is `Object`, containing all of the elements in this collection Annotations @Override @J2ktIncompatible

public Object[] toArray()

Overrides java.util.AbstractCollection.toArray.

Implements java.util.Collection.toArray.

Doc from java.util.Collection.toArray.

Returns an array containing all of the elements in this collection. If this collection makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order. The returned array's runtime component type is Object.

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

Returns:Object[]

an array, whose runtime component type is Object, containing all of the elements in this collection

Annotations

@Override
@J2ktIncompatible

com.google.common.collect back to summary

public final Class MinMaxPriorityQueue.Builder<B>

Class Inheritance

extends Object

java.lang.Object
com.google.common.collect.MinMaxPriorityQueue.Builder

Type Parameters

<B>: the upper bound on the eventual type that can be produced by this builder (for example, a Builder<Number> can produce a Queue<Number> or Queue<Integer> but not a Queue<Object>).

The builder class used in creation of min-max priority queues. Instead of constructing one directly, use MinMaxPriorityQueue#orderedBy(Comparator), MinMaxPriorityQueue#expectedSize(int) or MinMaxPriorityQueue#maximumSize(int).

Since: 8.0

Field Summary

Modifier and Type	Field and Description
private final Comparator<B>	comparator
private int	expectedSize
private int	maximumSize
private static final int	UNSET_EXPECTED_SIZE

Constructor Summary

Access	Constructor and Description
private	Builder(Comparator<B> comparator)

Method Summary

Modifier and Type	Method and Description
public <T extends B> MinMaxPriorityQueue<T>	create() Builds a new min-max priority queue using the previously specified options, and having no initial contents.
public <T extends B> MinMaxPriorityQueue<T>	create(Iterable<? extends T> initialContents) Builds a new min-max priority queue using the previously specified options, and having the given initial elements.
public MinMaxPriorityQueue.Builder<B>	expectedSize(int expectedSize) Configures this builder to build min-max priority queues with an initial expected size of `expectedSize`.
public MinMaxPriorityQueue.Builder<B>	maximumSize(int maximumSize) Configures this builder to build `MinMaxPriorityQueue` instances that are limited to `maximumSize` elements.
private <T extends B> Ordering<T>	ordering()

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

Field Detail

comparator	back to summary
private final Comparator<B> comparator

expectedSize	back to summary
private int expectedSize

maximumSize	back to summary
private int maximumSize

UNSET_EXPECTED_SIZE	back to summary
private static final int UNSET_EXPECTED_SIZE

Constructor Detail

Builder	back to summary
private Builder(Comparator<B> comparator)

Method Detail

create	back to summary
public <T extends B> MinMaxPriorityQueue<T> create() Builds a new min-max priority queue using the previously specified options, and having no initial contents.

create	back to summary
public <T extends B> MinMaxPriorityQueue<T> create(Iterable<? extends T> initialContents) Builds a new min-max priority queue using the previously specified options, and having the given initial elements.

expectedSize back to summary

public MinMaxPriorityQueue.Builder<B> expectedSize(int expectedSize)

Configures this builder to build min-max priority queues with an initial expected size of expectedSize.

Annotations

@CanIgnoreReturnValue

maximumSize back to summary

public MinMaxPriorityQueue.Builder<B> maximumSize(int maximumSize)

Configures this builder to build MinMaxPriorityQueue instances that are limited to maximumSize elements. Each time a queue grows beyond this bound, it immediately removes its greatest element (according to its comparator), which might be the element that was just added.

Annotations

@CanIgnoreReturnValue

ordering	back to summary
private <T extends B> Ordering<T> ordering() Annotations @SuppressWarnings:unchecked

com.google.common.collect back to summary

pack-priv Class MinMaxPriorityQueue.Heap

Class Inheritance

extends Object

java.lang.Object
com.google.common.collect.MinMaxPriorityQueue.Heap

Annotations

@WeakOuter

Each instance of MinMaxPriorityQueue encapsulates two instances of Heap: a min-heap and a max-heap. Conceptually, these might each have their own array for storage, but for efficiency's sake they are stored interleaved on alternate heap levels in the same array (MMPQ.queue).

Field Summary

Modifier and Type	Field and Description
pack-priv final Ordering<E>	ordering
pack-priv MinMaxPriorityQueue<E>.Heap	otherHeap

Constructor Summary

Access	Constructor and Description
pack-priv	Heap(Ordering<E> ordering)

Method Summary

Modifier and Type	Method and Description
pack-priv void	bubbleUp(int index, E x) Bubbles a value from `index` up the appropriate heap if required.
pack-priv int	bubbleUpAlternatingLevels(int index, E x) Bubbles a value from `index` up the levels of this heap, and returns the index the element ended up at.
pack-priv int	compareElements(int a, int b)
pack-priv int	crossOver(int index, E x) Crosses an element over to the opposite heap by moving it one level down (or up if there are no elements below it).
pack-priv int	crossOverUp(int index, E x) Moves an element one level up from a min level to a max level (or vice versa).
pack-priv int	Returns: the position of the new hole (where the lowest grandchild moved from, that had no grandchild to replace it) fillHoleAt(int index) Fills the hole at `index` by moving in the least of its grandchildren to this position, then recursively filling the new hole created.
pack-priv int	findMin(int index, int len) Returns the index of minimum value between `index` and `index + len`, or `-1` if `index` is greater than `size`.
pack-priv int	findMinChild(int index) Returns the minimum child or `-1` if no child exists.
pack-priv int	findMinGrandChild(int index) Returns the minimum grand child or -1 if no grand child exists.
private int	getGrandparentIndex(int i)
private int	getLeftChildIndex(int i)
private int	getParentIndex(int i)
private int	getRightChildIndex(int i)
pack-priv int	swapWithConceptuallyLastElement(E actualLastElement) Swap `actualLastElement` with the conceptually correct last element of the heap.
pack-priv MinMaxPriorityQueue.MoveDesc<E>	tryCrossOverAndBubbleUp(int removeIndex, int vacated, E toTrickle) Tries to move `toTrickle` from a min to a max level and bubble up there.
private boolean	verifyIndex(int i)

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

Field Detail

ordering	back to summary
pack-priv final Ordering<E> ordering

otherHeap	back to summary
pack-priv MinMaxPriorityQueue<E>.Heap otherHeap Annotations @SuppressWarnings:nullness:initialization.field.uninitialized @Weak

Constructor Detail

Heap	back to summary
pack-priv Heap(Ordering<E> ordering)

Method Detail

bubbleUp	back to summary
pack-priv void bubbleUp(int index, E x) Bubbles a value from `index` up the appropriate heap if required.

bubbleUpAlternatingLevels back to summary

pack-priv int bubbleUpAlternatingLevels(int index, E x)

Bubbles a value from index up the levels of this heap, and returns the index the element ended up at.

Annotations

@CanIgnoreReturnValue

compareElements	back to summary
pack-priv int compareElements(int a, int b)

crossOver

back to summary

pack-priv int crossOver(int index, E x)

Crosses an element over to the opposite heap by moving it one level down (or up if there are no elements below it).

Returns the new position of the element.

crossOverUp	back to summary
pack-priv int crossOverUp(int index, E x) Moves an element one level up from a min level to a max level (or vice versa). Returns the new position of the element.

fillHoleAt back to summary

pack-priv int fillHoleAt(int index)

Fills the hole at index by moving in the least of its grandchildren to this position, then recursively filling the new hole created.

Returns:int: the position of the new hole (where the lowest grandchild moved from, that had no grandchild to replace it)

findMin	back to summary
pack-priv int findMin(int index, int len) Returns the index of minimum value between `index` and `index + len`, or `-1` if `index` is greater than `size`.

findMinChild	back to summary
pack-priv int findMinChild(int index) Returns the minimum child or `-1` if no child exists.

findMinGrandChild	back to summary
pack-priv int findMinGrandChild(int index) Returns the minimum grand child or -1 if no grand child exists.

getGrandparentIndex	back to summary
private int getGrandparentIndex(int i)

getLeftChildIndex	back to summary
private int getLeftChildIndex(int i)

getParentIndex	back to summary
private int getParentIndex(int i)

getRightChildIndex	back to summary
private int getRightChildIndex(int i)

swapWithConceptuallyLastElement back to summary

pack-priv int swapWithConceptuallyLastElement(E actualLastElement)

Swap actualLastElement with the conceptually correct last element of the heap. Returns the index that actualLastElement now resides in.

Since the last element of the array is actually in the middle of the sorted structure, a childless aunt node could be smaller, which would corrupt the invariant if this element becomes the new parent of the aunt node. In that case, we first switch the last element with its aunt node, before returning.

tryCrossOverAndBubbleUp back to summary

pack-priv MinMaxPriorityQueue.MoveDesc<E> tryCrossOverAndBubbleUp(int removeIndex, int vacated, E toTrickle)

Tries to move toTrickle from a min to a max level and bubble up there. If it moved before removeIndex this method returns a pair as described in removeAt.

Annotations

@CheckForNull

verifyIndex	back to summary
private boolean verifyIndex(int i)

com.google.common.collect back to summary

pack-priv Class MinMaxPriorityQueue.MoveDesc<E>

Class Inheritance

extends Object

java.lang.Object
com.google.common.collect.MinMaxPriorityQueue.MoveDesc

Field Summary

Modifier and Type	Field and Description
pack-priv final E	replaced
pack-priv final E	toTrickle

Constructor Summary

Access	Constructor and Description
pack-priv	MoveDesc(E toTrickle, E replaced)

Method Summary

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

Field Detail

replaced	back to summary
pack-priv final E replaced

toTrickle	back to summary
pack-priv final E toTrickle

Constructor Detail

MoveDesc	back to summary
pack-priv MoveDesc(E toTrickle, E replaced)

com.google.common.collect back to summary

private Class MinMaxPriorityQueue.QueueIterator

Class Inheritance

extends Object
implements Iterator<E>

java.lang.Object
com.google.common.collect.MinMaxPriorityQueue.QueueIterator

All Implemented Interfaces

java.util.Iterator

Iterates the elements of the queue in no particular order.

If the underlying queue is modified during iteration an exception will be thrown.

Field Summary

Modifier and Type	Field and Description
private boolean	canRemove
private int	cursor
private int	expectedModCount
private Queue<E>	forgetMeNot
private E	lastFromForgetMeNot
private int	nextCursor
private List<E>	skipMe

Constructor Summary

Access	Constructor and Description
private	QueueIterator()

Method Summary

Modifier and Type	Method and Description
private void	checkModCount()
private boolean	foundAndRemovedExactReference(Iterable<E> elements, E target) Returns true if an exact reference (==) was found and removed from the supplied iterable.
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.
private void	nextNotInSkipMe(int c) Advances nextCursor to the index of the first element after `c` that is not in `skipMe` and returns `size()` if there is no such element.
public void	remove() Overrides default java.util.Iterator.remove. Removes from the underlying collection the last element returned by this iterator (optional operation).
private boolean	removeExact(Object target) Removes only this exact instance, not others that are equals()

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

Field Detail

canRemove	back to summary
private boolean canRemove

cursor	back to summary
private int cursor

expectedModCount	back to summary
private int expectedModCount

forgetMeNot	back to summary
private Queue<E> forgetMeNot Annotations @CheckForNull

lastFromForgetMeNot	back to summary
private E lastFromForgetMeNot Annotations @CheckForNull

nextCursor	back to summary
private int nextCursor

skipMe	back to summary
private List<E> skipMe Annotations @CheckForNull

Constructor Detail

QueueIterator	back to summary
private QueueIterator()

Method Detail

checkModCount	back to summary
private void checkModCount()

foundAndRemovedExactReference	back to summary
private boolean foundAndRemovedExactReference(Iterable<E> elements, E target) Returns true if an exact reference (==) was found and removed from the supplied iterable.

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.)

Returns:boolean

true if the iteration has more elements

Annotations

@Override

back to summary

public E next()

Implements java.util.Iterator.next.

Doc from java.util.Iterator.next.

Returns the next element in the iteration.

Returns:E

the next element in the iteration

Annotations

@Override

nextNotInSkipMe	back to summary
private void nextNotInSkipMe(int c) Advances nextCursor to the index of the first element after `c` that is not in `skipMe` and returns `size()` if there is no such element.

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.

Annotations

@Override

removeExact	back to summary
private boolean removeExact(Object target) Removes only this exact instance, not others that are equals()

public final Class MinMaxPriorityQueue<E>

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

public final Class MinMaxPriorityQueue.Builder<B>

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv Class MinMaxPriorityQueue.Heap

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv Class MinMaxPriorityQueue.MoveDesc<E>

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

private Class MinMaxPriorityQueue.QueueIterator

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail