Package net.automatalib.common.smartcollection

Class BinaryHeap<E>

java.lang.Object

java.util.AbstractCollection<E>

net.automatalib.common.smartcollection.AbstractSmartCollection<E>

net.automatalib.common.smartcollection.BinaryHeap<E>

Type Parameters:

E - element class.

All Implemented Interfaces:

Iterable<E>, Collection<E>, Queue<E>, CapacityManagement, SmartCollection<E>, SmartDynamicPriorityQueue<E>, SmartPriorityQueue<E>

public class BinaryHeap<E>
extends AbstractSmartCollection<E>
implements SmartDynamicPriorityQueue<E>, CapacityManagement, Queue<E>

A PriorityQueue implementation using a binary heap.

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	BinaryHeap(int initCapacity, Collection<? extends E> initValues, Comparator<? super E> comparator)
protected	BinaryHeap(int initialCapacity, Comparator<? super E> comparator)

Method Summary

Modifier and Type	Method	Description
static <E extends Comparable<E>> BinaryHeap<E>	create()
static <E extends Comparable<E>> BinaryHeap<E>	create(int initialCapacity)
static <E extends Comparable<E>> BinaryHeap<E>	create(int initialCapacity, Collection<? extends E> initValues)
static <E extends Comparable<E>> BinaryHeap<E>	create(Collection<? extends E> initValues)
static <E> BinaryHeap<E>	createCmp(Comparator<? super E> comparator)
static <E> BinaryHeap<E>	createCmp(Comparator<? super E> comparator, int initialCapacity)
static <E> BinaryHeap<E>	createCmp(Comparator<? super E> comparator, int initialCapacity, Collection<? extends E> initValues)
static <E> BinaryHeap<E>	createCmp(Comparator<? super E> comparator, Collection<? extends E> initValues)
void	deepClear()	Thoroughly clears the collection, fixing all issues that may have been caused by a call of the above SmartCollection.quickClear().
E	element()
boolean	ensureAdditionalCapacity(int additionalCapacity)	Ensures that the internal storage has room for at least the provided number of additional elements.
boolean	ensureCapacity(int minCapacity)	Ensures that the internal storage has room for at least the provided number of elements.
E	extractMin()	Retrieves and removes the element with the minimum key in the priority queue.
E	get(ElementReference ref)	Retrieves an element by its reference.
void	hintNextCapacity(int nextCapacityHint)	Gives a hint regarding the capacity that should be reserved when resizing the internal storage for the next time.
void	keyChanged(int index)
void	keyChanged(ElementReference ref)	Notifies the implementation that the key of an element has changed.
boolean	offer(E e)
@Nullable E	peek()
E	peekMin()	Retrieves, but does not remove the element with the minimum key in the priority queue.
@Nullable E	poll()
void	quickClear()	Quickly clears this collection.
ElementReference	referencedAdd(E elem)	Adds an element to the collection, returning a reference to the newly added element.
Iterator<ElementReference>	referenceIterator()	Retrieves an iterator for iterating over the references of elements in this collection.
E	remove()
void	remove(ElementReference ref)	Removes an element (by its reference) from the collection.
void	replace(ElementReference ref, E newElement)	Replaces the element referenced by the given reference with the specified element.
int	size()

Methods inherited from class net.automatalib.common.smartcollection.AbstractSmartCollection

add, addAll, addAll, choose, chooseRef, find, iterator, references, remove

Methods inherited from class java.util.AbstractCollection

addAll, clear, contains, containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, parallelStream, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray

Methods inherited from interface java.lang.Iterable

forEach

Methods inherited from interface java.util.Queue

add

Methods inherited from interface net.automatalib.common.smartcollection.SmartCollection

addAll, addAll, choose, chooseRef, find, references, remove

Constructor Detail

BinaryHeap

protected BinaryHeap(int initCapacity,
                     Collection<? extends E> initValues,
                     Comparator<? super E> comparator)

BinaryHeap

protected BinaryHeap(int initialCapacity,
                     Comparator<? super E> comparator)

Method Detail

create

public static <E extends Comparable<E>> BinaryHeap<E> create()

create

public static <E extends Comparable<E>> BinaryHeap<E> create(int initialCapacity)

create

public static <E extends Comparable<E>> BinaryHeap<E> create(Collection<? extends E> initValues)

create

public static <E extends Comparable<E>> BinaryHeap<E> create(int initialCapacity,
                                                             Collection<? extends E> initValues)

createCmp

public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator)

createCmp

public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator,
                                          int initialCapacity)

createCmp

public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator,
                                          Collection<? extends E> initValues)

createCmp

public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator,
                                          int initialCapacity,
                                          Collection<? extends E> initValues)

size

public int size()

Specified by:

size in interface Collection<E>

Specified by:

size in class AbstractCollection<E>

get

public E get(ElementReference ref)

Description copied from interface: SmartCollection

Retrieves an element by its reference.

If the reference belongs to another collection, the behavior is undefined.

Specified by:

get in interface SmartCollection<E>

Parameters:

ref - the element's reference.

Returns:

the element.

referencedAdd

public ElementReference referencedAdd(E elem)

Description copied from interface: SmartCollection

Adds an element to the collection, returning a reference to the newly added element. If the collection does not support containing the same element multiple times, a reference to the previously existing element is returned.

Specified by:

referencedAdd in interface SmartCollection<E>

Parameters:

elem - the element to be added.

Returns:

a reference to this element in the collection.

remove

public void remove(ElementReference ref)

Description copied from interface: SmartCollection

Removes an element (by its reference) from the collection.

If the reference does not belong to this collection, the behavior is undefined.

Specified by:

remove in interface SmartCollection<E>

Parameters:

ref - the reference to the element to be removed.

remove

public E remove()

Specified by:

remove in interface Queue<E>

referenceIterator

public Iterator<ElementReference> referenceIterator()

Description copied from interface: SmartCollection

Retrieves an iterator for iterating over the references of elements in this collection.

Specified by:

referenceIterator in interface SmartCollection<E>

Returns:

the reference iterator.

replace

public void replace(ElementReference ref,
                    E newElement)

Description copied from interface: SmartCollection

Replaces the element referenced by the given reference with the specified element.

Specified by:

replace in interface SmartCollection<E>

Parameters:

ref - the reference of the element to be replaced.

newElement - the replacement.

keyChanged

public void keyChanged(ElementReference ref)

Description copied from interface: SmartDynamicPriorityQueue

Notifies the implementation that the key of an element has changed.

Specified by:

keyChanged in interface SmartDynamicPriorityQueue<E>

Parameters:

ref - the reference for the element whose key has changed.

keyChanged

public void keyChanged(int index)

ensureCapacity

public boolean ensureCapacity(int minCapacity)

Description copied from interface: CapacityManagement

Ensures that the internal storage has room for at least the provided number of elements.

Specified by:

ensureCapacity in interface CapacityManagement

Parameters:

minCapacity - the minimal number of elements the storage should have room for.

Returns:

true iff the internal storage had to be resized, false otherwise.

ensureAdditionalCapacity

public boolean ensureAdditionalCapacity(int additionalCapacity)

Description copied from interface: CapacityManagement

Ensures that the internal storage has room for at least the provided number of additional elements.

Calling this method is equivalent to calling the above CapacityManagement.ensureCapacity(int) with an argument of size() + additionalCapacity.

Specified by:

ensureAdditionalCapacity in interface CapacityManagement

Parameters:

additionalCapacity - the number of additional elements the storage should have room for.

Returns:

true iff the internal storage had to be resized, false otherwise.

hintNextCapacity

public void hintNextCapacity(int nextCapacityHint)

Description copied from interface: CapacityManagement

Gives a hint regarding the capacity that should be reserved when resizing the internal storage for the next time. This method acts like a "lazy" CapacityManagement.ensureCapacity(int), i.e. it reserves the specified capacity at the time the next resizing of the internal storage is performed.

This method is useful when a not too imprecise upper bound on the elements that will in consequence be added is known. Since the actual number of elements added may be lower than the specified upper bound, a resizing that would have been performed by CapacityManagement.ensureCapacity(int) might not be necessary.

Specified by:

hintNextCapacity in interface CapacityManagement

Parameters:

nextCapacityHint - the next capacity hint.

quickClear

public void quickClear()

Description copied from interface: SmartCollection

Quickly clears this collection. This method is supposed to perform the minimum amount of effort such that this collection is emptied, disregarding all other side effects such as referencing or garbage collection issues.

Depending on the implementation, this may be just the same as Collection.clear(). However, this could also have side effects like hampering the garbage collection or such.

After calling this method, even a call of the normal Collection.clear() is not guaranteed to fix all these issues. This can only be achieved by the method SmartCollection.deepClear() below.

Specified by:

quickClear in interface SmartCollection<E>

Overrides:

quickClear in class AbstractSmartCollection<E>

deepClear

public void deepClear()

Description copied from interface: SmartCollection

Thoroughly clears the collection, fixing all issues that may have been caused by a call of the above SmartCollection.quickClear().

Specified by:

deepClear in interface SmartCollection<E>

Overrides:

deepClear in class AbstractSmartCollection<E>

offer

public boolean offer(E e)

Specified by:

offer in interface Queue<E>

poll

public @Nullable E poll()

Specified by:

poll in interface Queue<E>

element

public E element()

Specified by:

element in interface Queue<E>

peekMin

public E peekMin()

Description copied from interface: SmartPriorityQueue

Retrieves, but does not remove the element with the minimum key in the priority queue. If there are several elements with minimal key values, one of them is chosen arbitrarily.

Specified by:

peekMin in interface SmartPriorityQueue<E>

Returns:

an element with a minimal key.

extractMin

public E extractMin()

Description copied from interface: SmartPriorityQueue

Retrieves and removes the element with the minimum key in the priority queue. If there are several elements with minimal key values, one of them is chosen arbitrarily.

Specified by:

extractMin in interface SmartPriorityQueue<E>

Returns:

the element with the previously minimal key.

peek

public @Nullable E peek()

Specified by:

peek in interface Queue<E>