@Generated(date="2017-07-11T19:16:22+0200",
value="KTypeHeapPriorityQueue.java")
public class DoubleHeapPriorityQueue
extends AbstractDoubleCollection
implements DoublePriorityQueue, java.lang.Cloneable
doubles.
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 |
DoubleHeapPriorityQueue.ValueIterator
An iterator implementation for
iterator(). |
| Modifier and Type | Field and Description |
|---|---|
double[] |
buffer
Internal array for storing the priority queue.
|
protected DoubleComparator |
comparator
Defines the Comparator ordering of the queue,
If null, natural ordering is used.
|
protected double |
currentOccurenceToBeRemoved
The current value set for removeAll
|
protected double |
defaultValue
Default value returned when specified
in methods.
|
protected int |
elementsCount
Number of elements in the queue.
|
protected DoublePredicate |
removeAllOccurencesPredicate
Internal predicate for removeAll
|
protected ArraySizingStrategy |
resizer
Buffer resizing strategy.
|
protected IteratorPool<DoubleCursor,DoubleHeapPriorityQueue.ValueIterator> |
valueIteratorPool
internal pool of ValueIterator (must be created in constructor)
|
containsNegateTestPredicate, containsTestPredicate, negatePredicate, testContainer, testPredicate| Constructor and Description |
|---|
DoubleHeapPriorityQueue()
Default constructor: create with a default
numbers of elements (
Containers.DEFAULT_EXPECTED_ELEMENTS),
using the natural ordering of doubles. |
DoubleHeapPriorityQueue(DoubleComparator comp)
Create with default sizing strategy and initial capacity
(
Containers.DEFAULT_EXPECTED_ELEMENTS)
using a specific Comparator. |
DoubleHeapPriorityQueue(DoubleComparator comp,
int initialCapacity)
Create with a given initial capacity, using a
Comparator for ordering.
|
DoubleHeapPriorityQueue(DoubleComparator comp,
int initialCapacity,
ArraySizingStrategy resizer)
Create with a Comparator, an initial capacity, and a custom buffer resizing strategy.
|
DoubleHeapPriorityQueue(DoubleContainer container)
Creates a new heap from elements of another container.
|
DoubleHeapPriorityQueue(int initialCapacity)
Create with an initial capacity,
using the natural ordering of
doubles |
| Modifier and Type | Method and Description |
|---|---|
void |
add(double element)
Insert a double into the queue.
|
int |
addAll(DoubleContainer container)
Adds all elements from another container.
|
int |
addAll(java.lang.Iterable<? extends DoubleCursor> iterable)
Adds all elements from another iterable.
|
int |
capacity()
Return the maximum number of elements this container is guaranteed to hold without reallocating.
|
void |
clear()
Removes all elements from this collection.
|
DoubleHeapPriorityQueue |
clone()
Clone this object.
|
DoubleComparator |
comparator()
Get the custom comparator used for comparing elements
|
boolean |
contains(double 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 DoublePredicate> |
forEach(T predicate)
Applies a
predicate to container elements, as long as the predicate
returns true. |
<T extends DoubleProcedure> |
forEach(T procedure)
Applies a
procedure to all container elements. |
static DoubleHeapPriorityQueue |
from(double... elements)
Create a heap from a variable number of arguments or an array of
double. |
static DoubleHeapPriorityQueue |
from(DoubleContainer container)
Create a heap from elements of another container (constructor shortcut)
|
double |
getDefaultValue()
Returns the "default value" value used
in methods returning "default value"
|
int |
hashCode() |
DoubleHeapPriorityQueue.ValueIterator |
iterator()
Returns an iterator to a cursor traversing the collection.
|
double |
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(double e1)
Removes all occurrences of
e from this collection. |
int |
removeAll(DoublePredicate predicate)
Removes all elements in this collection for which the
given predicate returns
true. |
void |
setDefaultValue(double 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.
|
double[] |
toArray(double[] target)
Default implementation for:
Copies all elements of this container to an existing array of the same type.
|
double |
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
DoublePriorityQueue.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 double[] 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 DoubleComparator comparator
protected final ArraySizingStrategy resizer
protected final IteratorPool<DoubleCursor,DoubleHeapPriorityQueue.ValueIterator> valueIteratorPool
protected double currentOccurenceToBeRemoved
protected DoublePredicate removeAllOccurencesPredicate
protected double defaultValue
top()public DoubleHeapPriorityQueue(DoubleComparator comp, int initialCapacity, ArraySizingStrategy resizer)
public DoubleHeapPriorityQueue(DoubleComparator comp)
Containers.DEFAULT_EXPECTED_ELEMENTS)
using a specific Comparator.BoundedProportionalArraySizingStrategypublic DoubleHeapPriorityQueue()
Containers.DEFAULT_EXPECTED_ELEMENTS),
using the natural ordering of doubles.public DoubleHeapPriorityQueue(int initialCapacity)
doublespublic DoubleHeapPriorityQueue(DoubleComparator comp, int initialCapacity)
BoundedProportionalArraySizingStrategypublic DoubleHeapPriorityQueue(DoubleContainer container)
public static DoubleHeapPriorityQueue from(DoubleContainer container)
public static DoubleHeapPriorityQueue from(double... elements)
double.public int removeAll(double e1)
e from this collection.removeAll in interface DoubleCollectione1 - Element to be removed from this collection, if present.public int removeAll(DoublePredicate predicate)
true.removeAll in interface DoubleCollectionpublic void clear()
clear in interface DoubleCollectionpublic DoubleHeapPriorityQueue.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 (DoubleCursor<double> c : container) {
System.out.println("index=" + c.index + " value=" + c.value);
}
iterator in interface DoubleContaineriterator in interface java.lang.Iterable<DoubleCursor>public boolean contains(double element)
contains in interface DoubleContainertrue 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 DoubleContainerpublic int capacity()
O(n) time.capacity in interface DoubleContainerpublic <T extends DoubleProcedure> T forEach(T procedure)
procedure to all container elements. Returns the argument (any
subclass of DoubleProcedure. 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 DoubleContainerpublic <T extends DoublePredicate> T forEach(T predicate)
predicate to container elements, as long as the predicate
returns true. The iteration is interrupted otherwise.forEach in interface DoubleContainerpublic void add(double element)
add in interface DoublePriorityQueuepublic double top()
top in interface DoublePriorityQueuepublic double popTop()
popTop in interface DoublePriorityQueuepublic int addAll(DoubleContainer container)
public int addAll(java.lang.Iterable<? extends DoubleCursor> iterable)
public int hashCode()
hashCode in class java.lang.Objectpublic void updatePriorities()
updatePriorities in interface DoublePriorityQueuepublic void updateTopPriority()
DoublePriorityQueue.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 DoublePriorityQueuepublic DoubleHeapPriorityQueue 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 double[] toArray(double[] target)
toArray in interface DoubleContainertoArray in class AbstractDoubleCollectiontarget - The target array must be large enough to hold all elements, i.e >= DoubleContainer.size().public DoubleComparator comparator()
doubles is used insteadpublic double getDefaultValue()
getDefaultValue in interface DoublePriorityQueuepublic void setDefaultValue(double defaultValue)
setDefaultValue in interface DoublePriorityQueueCopyright © 2017. All rights reserved.