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