Package net.automatalib.common.smartcollection

Class BackedGeneralPriorityQueue<E,K extends Comparable<K>>

java.lang.Object

java.util.AbstractCollection<E>

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

net.automatalib.common.smartcollection.BackedGeneralPriorityQueue<E,K>

Type Parameters:

E - element class.

K - key class.

All Implemented Interfaces:

Iterable<E>, Collection<E>, SmartCollection<E>, SmartGeneralPriorityQueue<E,K>, SmartPriorityQueue<E>

public class BackedGeneralPriorityQueue<E,K extends Comparable<K>>
extends AbstractSmartCollection<E>
implements SmartGeneralPriorityQueue<E,K>

A SmartGeneralPriorityQueue implementation that is backed by a SmartDynamicPriorityQueue.

The default SmartDynamicPriorityQueue to be used is a BinaryHeap, but every other implementation of this interface may be used. The backing queue is specified in the constructor.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	BackedGeneralPriorityQueue.Entry<E,K extends Comparable<K>>	Note: this class has a natural ordering that is inconsistent with equals.

Constructor Summary

Constructors

Constructor	Description
BackedGeneralPriorityQueue()
BackedGeneralPriorityQueue(int initialCapacity)
BackedGeneralPriorityQueue(Supplier<? extends SmartDynamicPriorityQueue<BackedGeneralPriorityQueue.Entry<E,K>>> supplier)
BackedGeneralPriorityQueue(List<? extends E> init, List<K> keys)
BackedGeneralPriorityQueue(SmartDynamicPriorityQueue<BackedGeneralPriorityQueue.Entry<E,K>> backingQueue)	Constructor.

Method Summary

Modifier and Type	Method	Description
ElementReference	add(E elem, @Nullable K key)	Inserts an element with the specified key.
void	changeKey(ElementReference ref, K newKey)	Changes the key of an element in the priority key.
E	choose()	Retrieves an arbitrary element from the collection.
ElementReference	chooseRef()	Retrieves the reference to an arbitrary element from the collection.
void	clear()
void	deepClear()	Thoroughly clears the collection, fixing all issues that may have been caused by a call of the above SmartCollection.quickClear().
E	extractMin()	Retrieves and removes the element with the minimum key in the priority queue.
@Nullable ElementReference	find(@Nullable Object element)	Retrieves the reference for a given element.
E	get(ElementReference ref)	Retrieves an element by its reference.
boolean	isEmpty()
Iterator<E>	iterator()
E	peekMin()	Retrieves, but does not remove the element with the minimum key in the priority queue.
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.
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.
void	setDefaultKey(K defaultKey)	Sets the default key, which is used for elements that are inserted with no explicit key specified.
int	size()

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

add, addAll, addAll, references, remove

Methods inherited from class java.util.AbstractCollection

addAll, contains, containsAll, 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

add, addAll, contains, containsAll, equals, hashCode, parallelStream, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray

Methods inherited from interface java.lang.Iterable

forEach

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

addAll, addAll, references, remove

Constructor Detail

BackedGeneralPriorityQueue

public BackedGeneralPriorityQueue()

BackedGeneralPriorityQueue

public BackedGeneralPriorityQueue(int initialCapacity)

BackedGeneralPriorityQueue

public BackedGeneralPriorityQueue(List<? extends E> init,
                                  List<K> keys)

BackedGeneralPriorityQueue

public BackedGeneralPriorityQueue(Supplier<? extends SmartDynamicPriorityQueue<BackedGeneralPriorityQueue.Entry<E,K>>> supplier)

BackedGeneralPriorityQueue

public BackedGeneralPriorityQueue(SmartDynamicPriorityQueue<BackedGeneralPriorityQueue.Entry<E,K>> backingQueue)

Constructor. Explicitly initializes this queue with a given backing queue. Note that the provided queue must be empty and must not be used in any other way after being passed to the constructor.

Parameters:

backingQueue - the backing queue.

Method Detail

choose

public E choose()

Description copied from interface: SmartCollection

Retrieves an arbitrary element from the collection.

Specified by:

choose in interface SmartCollection<E>

Overrides:

choose in class AbstractSmartCollection<E>

Returns:

an arbitrary element from the collection

chooseRef

public ElementReference chooseRef()

Description copied from interface: SmartCollection

Retrieves the reference to an arbitrary element from the collection. If the collection is empty, a NoSuchElementException is thrown.

Specified by:

chooseRef in interface SmartCollection<E>

Overrides:

chooseRef in class AbstractSmartCollection<E>

Returns:

the reference to an arbitrary element in the collection

find

public @Nullable ElementReference find(@Nullable Object element)

Description copied from interface: SmartCollection

Retrieves the reference for a given element. If the element is not contained in the collection, null is returned.

Specified by:

find in interface SmartCollection<E>

Overrides:

find in class AbstractSmartCollection<E>

Parameters:

element - the element to search for.

Returns:

the reference to this element, or null.

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>

iterator

public Iterator<E> iterator()

Specified by:

iterator in interface Collection<E>

Specified by:

iterator in interface Iterable<E>

Overrides:

iterator in class AbstractSmartCollection<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.

add

public ElementReference add(E elem,
                            @Nullable K key)

Description copied from interface: SmartGeneralPriorityQueue

Inserts an element with the specified key.

Specified by:

add in interface SmartGeneralPriorityQueue<E,K extends Comparable<K>>

Parameters:

elem - the element to insert.

key - the key for this element.

Returns:

the reference to the inserted element.

setDefaultKey

public void setDefaultKey(K defaultKey)

Description copied from interface: SmartGeneralPriorityQueue

Sets the default key, which is used for elements that are inserted with no explicit key specified.

Specified by:

setDefaultKey in interface SmartGeneralPriorityQueue<E,K extends Comparable<K>>

Parameters:

defaultKey - the new default key.

changeKey

public void changeKey(ElementReference ref,
                      K newKey)

Description copied from interface: SmartGeneralPriorityQueue

Changes the key of an element in the priority key.

Specified by:

changeKey in interface SmartGeneralPriorityQueue<E,K extends Comparable<K>>

Parameters:

ref - reference to the element whose key is to be changed.

newKey - the new key of this element.

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.

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.

size

public int size()

Specified by:

size in interface Collection<E>

Specified by:

size in class AbstractCollection<E>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Collection<E>

Overrides:

isEmpty in class AbstractCollection<E>

clear

public void clear()

Specified by:

clear in interface Collection<E>

Overrides:

clear in class AbstractCollection<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.