@Generated(date="2017-07-11T19:16:22+0200",
value="KTypeHeapPriorityQueue.java")
public class LongHeapPriorityQueue
extends AbstractLongCollection
implements LongPriorityQueue, java.lang.Cloneable
longs.
i.e. top() is the smallest element,
as defined by Sedgewick: Algorithms 4th Edition (2011).
It assure O(log(N)) complexity for insertion, deletion and update priority of the min element,
and constant time to examine the min element by top().
Important:
Ordering of elements must be defined either
* by natural ordering
* or by a custom comparator provided in constructors,
see comparator() .
| Modifier and Type | Class and Description |
|---|---|
class |
LongHeapPriorityQueue.ValueIterator
An iterator implementation for
iterator(). |
| Modifier and Type | Field and Description |
|---|---|
long[] |
buffer
Internal array for storing the priority queue.
|
protected LongComparator |
comparator
Defines the Comparator ordering of the queue,
If null, natural ordering is used.
|
protected long |
currentOccurenceToBeRemoved
The current value set for removeAll
|
protected long |
defaultValue
Default value returned when specified
in methods.
|
protected int |
elementsCount
Number of elements in the queue.
|
protected LongPredicate |
removeAllOccurencesPredicate
Internal predicate for removeAll
|
protected ArraySizingStrategy |
resizer
Buffer resizing strategy.
|
protected IteratorPool<LongCursor,LongHeapPriorityQueue.ValueIterator> |
valueIteratorPool
internal pool of ValueIterator (must be created in constructor)
|
containsNegateTestPredicate, containsTestPredicate, negatePredicate, testContainer, testPredicate| Constructor and Description |
|---|
LongHeapPriorityQueue()
Default constructor: create with a default
numbers of elements (
Containers.DEFAULT_EXPECTED_ELEMENTS),
using the natural ordering of longs. |
LongHeapPriorityQueue(int initialCapacity)
Create with an initial capacity,
using the natural ordering of
longs |
LongHeapPriorityQueue(LongComparator comp)
Create with default sizing strategy and initial capacity
(
Containers.DEFAULT_EXPECTED_ELEMENTS)
using a specific Comparator. |
LongHeapPriorityQueue(LongComparator comp,
int initialCapacity)
Create with a given initial capacity, using a
Comparator for ordering.
|
LongHeapPriorityQueue(LongComparator comp,
int initialCapacity,
ArraySizingStrategy resizer)
Create with a Comparator, an initial capacity, and a custom buffer resizing strategy.
|
LongHeapPriorityQueue(LongContainer container)
Creates a new heap from elements of another container.
|
| Modifier and Type | Method and Description |
|---|---|
void |
add(long element)
Insert a long into the queue.
|
int |
addAll(java.lang.Iterable<? extends LongCursor> iterable)
Adds all elements from another iterable.
|
int |
addAll(LongContainer container)
Adds all elements from another container.
|
int |
capacity()
Return the maximum number of elements this container is guaranteed to hold without reallocating.
|
void |
clear()
Removes all elements from this collection.
|
LongHeapPriorityQueue |
clone()
Clone this object.
|
LongComparator |
comparator()
Get the custom comparator used for comparing elements
|
boolean |
contains(long element)
Lookup a given element in the container.
|
protected void |
ensureBufferSpace(int expectedAdditions)
Ensures the internal buffer has enough free slots to store
expectedAdditions. |
boolean |
equals(java.lang.Object obj)
this instance and obj can only be equal to this if either:
(both don't have set comparators)
or
(both have equal comparators defined by
comparator().equals(obj.comparator))
then, both heap elements are compared with equals(Object) iterating their buffer. |
<T extends LongPredicate> |
forEach(T predicate)
Applies a
predicate to container elements, as long as the predicate
returns true. |
<T extends LongProcedure> |
forEach(T procedure)
Applies a
procedure to all container elements. |
static LongHeapPriorityQueue |
from(long... elements)
Create a heap from a variable number of arguments or an array of
long. |
static LongHeapPriorityQueue |
from(LongContainer container)
Create a heap from elements of another container (constructor shortcut)
|
long |
getDefaultValue()
Returns the "default value" value used
in methods returning "default value"
|
int |
hashCode() |
LongHeapPriorityQueue.ValueIterator |
iterator()
Returns an iterator to a cursor traversing the collection.
|
long |
popTop()
Retrieve, and remove the top element of the queue,
i.e. the min element with respect to the comparison criteria
(implementation defined) Returns the default value if empty.
|
int |
removeAll(long e1)
Removes all occurrences of
e from this collection. |
int |
removeAll(LongPredicate predicate)
Removes all elements in this collection for which the
given predicate returns
true. |
void |
setDefaultValue(long defaultValue)
Set the "default value" value to be used
in methods returning "default value"
|
int |
size()
Return the current number of elements in this container.
|
long[] |
toArray(long[] target)
Default implementation for:
Copies all elements of this container to an existing array of the same type.
|
long |
top()
Retrieve, but not remove, the top element of the queue,
i.e. the min element with respect to the comparison criteria
(implementation defined)
of the queue.
|
void |
updatePriorities()
Update priorities of all the elements of the queue, to re-establish the correct priorities
towards the comparison criteria.
|
void |
updateTopPriority()
Update the priority of the
LongPriorityQueue.top() element, to re-establish its actual priority
towards the comparison criteria when it may have changed such that it is no longer the
min element with respect to the comparison criteria. |
isEmpty, removeAll, retainAll, retainAll, toArray, toStringfinalize, getClass, notify, notifyAll, wait, wait, waitremoveAll, retainAll, retainAllisEmpty, toArraypublic long[] buffer
Direct priority queue iteration: iterate buffer[i] for i in [1; size()] (included) but is out-of-order w.r.t popTop()
protected int elementsCount
protected LongComparator comparator
protected final ArraySizingStrategy resizer
protected final IteratorPool<LongCursor,LongHeapPriorityQueue.ValueIterator> valueIteratorPool
protected long currentOccurenceToBeRemoved
protected LongPredicate removeAllOccurencesPredicate
protected long defaultValue
top()public LongHeapPriorityQueue(LongComparator comp, int initialCapacity, ArraySizingStrategy resizer)
public LongHeapPriorityQueue(LongComparator comp)
Containers.DEFAULT_EXPECTED_ELEMENTS)
using a specific Comparator.BoundedProportionalArraySizingStrategypublic LongHeapPriorityQueue()
Containers.DEFAULT_EXPECTED_ELEMENTS),
using the natural ordering of longs.public LongHeapPriorityQueue(int initialCapacity)
longspublic LongHeapPriorityQueue(LongComparator comp, int initialCapacity)
BoundedProportionalArraySizingStrategypublic LongHeapPriorityQueue(LongContainer container)
public static LongHeapPriorityQueue from(LongContainer container)
public static LongHeapPriorityQueue from(long... elements)
long.public int removeAll(long e1)
e from this collection.removeAll in interface LongCollectione1 - Element to be removed from this collection, if present.public int removeAll(LongPredicate predicate)
true.removeAll in interface LongCollectionpublic void clear()
clear in interface LongCollectionpublic LongHeapPriorityQueue.ValueIterator iterator()
The iterator is implemented as a
cursor and it returns the same cursor instance on every call to
Iterator.next() (to avoid boxing of primitive types). To read the current
list's value (or index in the list) use the cursor's public fields. An example is
shown below.
for (LongCursor<long> c : container) {
System.out.println("index=" + c.index + " value=" + c.value);
}
iterator in interface LongContaineriterator in interface java.lang.Iterable<LongCursor>public boolean contains(long element)
contains in interface LongContainertrue if this container has an element
equal to e.public int size()
O(n) time, although implementing classes
should try to maintain the current size and return in constant time.size in interface LongContainerpublic int capacity()
O(n) time.capacity in interface LongContainerpublic <T extends LongProcedure> T forEach(T procedure)
procedure to all container elements. Returns the argument (any
subclass of LongProcedure. This lets the caller to call methods of the argument
by chaining the call (even if the argument is an anonymous type) to retrieve computed values,
for example (IntContainer):
int count = container.forEach(new IntProcedure() {
int count; // this is a field declaration in an anonymous class.
public void apply(int value) { count++; }}).count;
forEach in interface LongContainerpublic <T extends LongPredicate> T forEach(T predicate)
predicate to container elements, as long as the predicate
returns true. The iteration is interrupted otherwise.forEach in interface LongContainerpublic void add(long element)
add in interface LongPriorityQueuepublic long top()
top in interface LongPriorityQueuepublic long popTop()
popTop in interface LongPriorityQueuepublic int addAll(LongContainer container)
public int addAll(java.lang.Iterable<? extends LongCursor> iterable)
public int hashCode()
hashCode in class java.lang.Objectpublic void updatePriorities()
updatePriorities in interface LongPriorityQueuepublic void updateTopPriority()
LongPriorityQueue.top() element, to re-establish its actual priority
towards the comparison criteria when it may have changed such that it is no longer the
min element with respect to the comparison criteria.
cost: O(log(N))updateTopPriority in interface LongPriorityQueuepublic LongHeapPriorityQueue clone()
clone in class java.lang.Objectpublic boolean equals(java.lang.Object obj)
(both don't have set comparators)
or
(both have equal comparators defined by comparator().equals(obj.comparator))
then, both heap elements are compared with equals(Object) iterating their buffer.equals in class java.lang.Objectprotected void ensureBufferSpace(int expectedAdditions)
expectedAdditions. Increases internal buffer size if needed.public long[] toArray(long[] target)
toArray in interface LongContainertoArray in class AbstractLongCollectiontarget - The target array must be large enough to hold all elements, i.e >= LongContainer.size().public LongComparator comparator()
longs is used insteadpublic long getDefaultValue()
getDefaultValue in interface LongPriorityQueuepublic void setDefaultValue(long defaultValue)
setDefaultValue in interface LongPriorityQueueCopyright © 2017. All rights reserved.