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