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