de.lmu.ifi.dbs.elki.database.ids.integer

Class DoubleIntegerDBIDListKNNHeap

java.lang.Object

de.lmu.ifi.dbs.elki.database.ids.integer.DoubleIntegerDBIDList

de.lmu.ifi.dbs.elki.database.ids.integer.DoubleIntegerDBIDKNNList

de.lmu.ifi.dbs.elki.database.ids.integer.DoubleIntegerDBIDListKNNHeap

All Implemented Interfaces:

DBIDs, DoubleDBIDList, IntegerDBIDKNNList, IntegerDBIDs, KNNHeap, KNNList, ModifiableDoubleDBIDList

 class DoubleIntegerDBIDListKNNHeap
extends DoubleIntegerDBIDKNNList
implements KNNHeap

Track the k nearest neighbors, with insertion sort to ensure the correct order.

Author:

Erich Schubert

Field Summary

Fields inherited from class de.lmu.ifi.dbs.elki.database.ids.integer.DoubleIntegerDBIDKNNList

k

Fields inherited from class de.lmu.ifi.dbs.elki.database.ids.integer.DoubleIntegerDBIDList

dists, ids, size

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	DoubleIntegerDBIDListKNNHeap(int k) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
void	add(double dist, DBIDRef id) Add an object to this result.
protected void	addInternal(double dist, int id) Add a new element to the heap/list.
void	insert(DoubleDBIDPair e) Add a distance-id pair to the heap unless the distance is too large.
double	insert(double dist, DBIDRef id) Add a distance-id pair to the heap unless the distance is too large.
private void	insertionSort(double dist, int id) Insertion sort a single object.
DoubleIntegerDBIDPair	peek() Peek at the largest element in the heap.
DoubleIntegerDBIDPair	poll() Poll the largest element from the heap.
KNNList	toKNNList() Serialize to a KNNList.
String	toString()

Methods inherited from class de.lmu.ifi.dbs.elki.database.ids.integer.DoubleIntegerDBIDKNNList

getK, getKNNDistance

Methods inherited from class de.lmu.ifi.dbs.elki.database.ids.integer.DoubleIntegerDBIDList

add, clear, contains, get, grow, isEmpty, iter, remove, removeSwap, reverse, size, sort, swap, truncate

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.database.ids.KNNHeap

clear, getK, getKNNDistance, isEmpty, size

Methods inherited from interface de.lmu.ifi.dbs.elki.database.ids.integer.IntegerDBIDKNNList

get, iter

Methods inherited from interface de.lmu.ifi.dbs.elki.database.ids.KNNList

size

Methods inherited from interface de.lmu.ifi.dbs.elki.database.ids.DBIDs

contains, isEmpty

Constructor Detail

DoubleIntegerDBIDListKNNHeap

protected DoubleIntegerDBIDListKNNHeap(int k)

Constructor.

Parameters:

k - K parameter

Method Detail

addInternal

protected final void addInternal(double dist,
               int id)

Add a new element to the heap/list.

Overrides:

addInternal in class DoubleIntegerDBIDList

Parameters:

dist - Distance

id - Object ID

insertionSort

private void insertionSort(double dist,
                 int id)

Insertion sort a single object.

Parameters:

dist - New distance

id - New id

insert

public double insert(double dist,
            DBIDRef id)

Description copied from interface: KNNHeap

Add a distance-id pair to the heap unless the distance is too large. Compared to the super.add() method, this often saves the pair construction.

Specified by:

insert in interface KNNHeap

Parameters:

dist - Distance value

id - ID number

Returns:

current k-distance

add

public void add(double dist,
       DBIDRef id)

Description copied from interface: ModifiableDoubleDBIDList

Add an object to this result.

Specified by:

add in interface ModifiableDoubleDBIDList

Overrides:

add in class DoubleIntegerDBIDList

Parameters:

dist - Distance to add

id - DBID to add

insert

public void insert(DoubleDBIDPair e)

Description copied from interface: KNNHeap

Add a distance-id pair to the heap unless the distance is too large. Use for existing pairs.

Specified by:

insert in interface KNNHeap

Parameters:

e - Existing distance pair

poll

public DoubleIntegerDBIDPair poll()

Description copied from interface: KNNHeap

Poll the largest element from the heap. This is in descending order because of the heap structure. For a convenient way to serialize the heap into a list that you can iterate in ascending order, see KNNHeap.toKNNList().

Specified by:

poll in interface KNNHeap

Returns:

largest element

peek

public DoubleIntegerDBIDPair peek()

Description copied from interface: KNNHeap

Peek at the largest element in the heap.

Specified by:

peek in interface KNNHeap

Returns:

The current largest element.

toKNNList

public KNNList toKNNList()

Description copied from interface: KNNHeap

Serialize to a KNNList. This empties the heap!

Specified by:

toKNNList in interface KNNHeap

Returns:

KNNList with the heaps contents.

toString

public String toString()

Overrides:

toString in class DoubleIntegerDBIDKNNList