de.lmu.ifi.dbs.elki.utilities.datastructures.heap

Class UpdatableHeap<O>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractQueue<E>

de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap<O>

de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap<O>

Type Parameters:

O - object type

All Implemented Interfaces:

Serializable, Iterable<O>, Collection<O>, Queue<O>

Direct Known Subclasses:

TopBoundedUpdatableHeap

public class UpdatableHeap<O>
extends Heap<O>

A heap as used in OPTICS that allows updating entries.

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap

Heap.Itr

Field Summary

Fields

Modifier and Type	Field and Description
protected static int	IN_TIES Constant for "in ties list", for tied heaps.
protected gnu.trove.map.TObjectIntMap<Object>	index Holds the indices in the heap of each element.
protected static int	NO_VALUE Constant for "not in heap"
private static long	serialVersionUID Serial version

Fields inherited from class de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap

comparator, modCount, queue, size, validSize

Constructor Summary

Constructors

Constructor and Description
UpdatableHeap() Simple constructor with default size.
UpdatableHeap(Comparator<? super O> comparator) Constructor with comparator
UpdatableHeap(int size) Constructor with predefined size.
UpdatableHeap(int size, Comparator<? super O> comparator) Constructor with predefined size and comparator

Method Summary

Methods

Modifier and Type	Method and Description
void	clear()
protected boolean	heapifyDownComparable(int ipos, Object reinsert) Execute a "Heapify Downwards" aka "SiftDown".
protected boolean	heapifyDownComparator(int ipos, Object cur) Execute a "Heapify Downwards" aka "SiftDown".
protected void	heapifyUpComparable(int pos, Object elem) Execute a "Heapify Upwards" aka "SiftUp".
protected void	heapifyUpComparator(int pos, Object cur) Execute a "Heapify Upwards" aka "SiftUp".
boolean	offer(O e)
protected boolean	offerAt(int pos, O e)
O	poll()
protected O	removeAt(int pos) Remove the element at the given position.
O	removeObject(O e) Remove the given object from the queue.

Methods inherited from class de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap

add, addAll, castQueueElement, checkHeap, contains, ensureValid, heapifyDown, heapifyUp, iterator, peek, resize, size, toSortedArrayList

Methods inherited from class java.util.AbstractQueue

element, remove

Methods inherited from class java.util.AbstractCollection

containsAll, isEmpty, remove, 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

containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, toArray, toArray

Field Detail

NO_VALUE

protected static final int NO_VALUE

Constant for "not in heap"

See Also:

Constant Field Values

IN_TIES

protected static final int IN_TIES

Constant for "in ties list", for tied heaps.

See Also:

Constant Field Values

serialVersionUID

private static final long serialVersionUID

Serial version

See Also:

Constant Field Values

index

protected final gnu.trove.map.TObjectIntMap<Object> index

Holds the indices in the heap of each element.

Constructor Detail

UpdatableHeap

public UpdatableHeap()

Simple constructor with default size.

UpdatableHeap

public UpdatableHeap(int size)

Constructor with predefined size.

Parameters:

size - Size

UpdatableHeap

public UpdatableHeap(Comparator<? super O> comparator)

Constructor with comparator

Parameters:

comparator - Comparator

UpdatableHeap

public UpdatableHeap(int size,
             Comparator<? super O> comparator)

Constructor with predefined size and comparator

Parameters:

size - Size

comparator - Comparator

Method Detail

clear

public void clear()

Specified by:

clear in interface Collection<O>

Overrides:

clear in class Heap<O>

offer

public boolean offer(O e)

Specified by:

offer in interface Queue<O>

Overrides:

offer in class Heap<O>

offerAt

protected boolean offerAt(int pos,
              O e)

removeAt

protected O removeAt(int pos)

Description copied from class: Heap

Remove the element at the given position.

Overrides:

removeAt in class Heap<O>

Parameters:

pos - Element position.

removeObject

public O removeObject(O e)

Remove the given object from the queue.

Parameters:

e - Object to remove

Returns:

Existing entry

poll

public O poll()

Specified by:

poll in interface Queue<O>

Overrides:

poll in class Heap<O>

heapifyUpComparable

protected void heapifyUpComparable(int pos,
                       Object elem)

Execute a "Heapify Upwards" aka "SiftUp". Used in insertions.

Overrides:

heapifyUpComparable in class Heap<O>

Parameters:

pos - insertion position

elem - Element to insert

heapifyUpComparator

protected void heapifyUpComparator(int pos,
                       Object cur)

Execute a "Heapify Upwards" aka "SiftUp". Used in insertions.

Overrides:

heapifyUpComparator in class Heap<O>

Parameters:

pos - insertion position

cur - Element to insert

heapifyDownComparable

protected boolean heapifyDownComparable(int ipos,
                            Object reinsert)

Description copied from class: Heap

Execute a "Heapify Downwards" aka "SiftDown". Used in deletions.

Overrides:

heapifyDownComparable in class Heap<O>

Parameters:

ipos - re-insertion position

Returns:

true when the order was changed

heapifyDownComparator

protected boolean heapifyDownComparator(int ipos,
                            Object cur)

Description copied from class: Heap

Execute a "Heapify Downwards" aka "SiftDown". Used in deletions.

Overrides:

heapifyDownComparator in class Heap<O>

Parameters:

ipos - re-insertion position

Returns:

true when the order was changed