Package elki.database.ids.integer

Class DoubleIntegerDBIDKNNHeap

java.lang.Object

elki.database.ids.integer.DoubleIntegerDBIDHeap

elki.database.ids.integer.DoubleIntegerDBIDKNNHeap

All Implemented Interfaces:

DBIDRef, DoubleDBIDHeap, KNNHeap

class DoubleIntegerDBIDKNNHeap
extends DoubleIntegerDBIDHeap
implements KNNHeap

Class to efficiently manage a kNN heap.

Since:

0.6.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	DoubleIntegerDBIDKNNHeap.UnorderedIter	Iterate over all objects in the heap, not ordered.

Field Summary

Fields

Modifier and Type	Field	Description
private static int	INITIAL_TIES_SIZE	Initial size of ties array.
private int	k	k for this heap.
private double	kdist	Current maximum value.
private int	numties	Number of element in ties list.
private int[]	ties	List to track ties.

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	DoubleIntegerDBIDKNNHeap(int k)	Constructor.

Method Summary

Modifier and Type	Method	Description
private void	addToTies(int id)	Ensure the ties array has capacity for at least one more element.
void	clear()	Clear the heap.
boolean	contains(DBIDRef o)	Check if an object is already in the heap (slow scan).
int	getK()	Get the K parameter ("maxsize" internally).
double	getKNNDistance()	Get the distance to the k nearest neighbor, or maxdist otherwise.
double	insert(double distance, DBIDRef id)	Add a double-id pair to the heap
int	internalGetIndex()	Internal only: Get the internal index.
boolean	isEmpty()	Test if the heap is empty.
double	peekKey()	Get the topmost value (the heap is a DBIDRef, referencing the top element).
void	poll()	Remove the topmost element.
int	size()	Current size of heap.
DoubleIntegerDBIDKNNList	toKNNList()	Serialize to a KNNList.
DoubleIntegerDBIDKNNList	toKNNListSqrt()	Serialize to a KNNList, but applying sqrt to every distance.
java.lang.String	toString()
DoubleDBIDIter	unorderedIterator()	Unordered iterator over the heap.

Methods inherited from class elki.database.ids.integer.DoubleIntegerDBIDHeap

insert, replaceTopElement

Methods inherited from class java.lang.Object

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

Methods inherited from interface elki.database.ids.DBIDRef

equals, hashCode

Methods inherited from interface elki.database.ids.KNNHeap

insert

Field Detail

k

private final int k

k for this heap.

ties

private int[] ties

List to track ties.

numties

private int numties

Number of element in ties list.

kdist

private double kdist

Current maximum value.

INITIAL_TIES_SIZE

private static final int INITIAL_TIES_SIZE

Initial size of ties array.

See Also:

Constant Field Values

Constructor Detail

DoubleIntegerDBIDKNNHeap

protected DoubleIntegerDBIDKNNHeap(int k)

Constructor.

Parameters:

k - Size of knn.

Method Detail

getK

public int getK()

Description copied from interface: KNNHeap

Get the K parameter ("maxsize" internally).

Specified by:

getK in interface KNNHeap

Returns:

K

getKNNDistance

public double getKNNDistance()

Description copied from interface: KNNHeap

Get the distance to the k nearest neighbor, or maxdist otherwise.

Specified by:

getKNNDistance in interface KNNHeap

Returns:

Maximum distance

insert

public final double insert(double distance,
                           DBIDRef id)

Description copied from interface: DoubleDBIDHeap

Add a double-id pair to the heap

Specified by:

insert in interface DoubleDBIDHeap

Specified by:

insert in interface KNNHeap

Overrides:

insert in class DoubleIntegerDBIDHeap

Parameters:

distance - Key value

id - ID number

Returns:

Value of to the element at the top of the heap

addToTies

private void addToTies(int id)

Ensure the ties array has capacity for at least one more element.

Parameters:

id - Id to add

poll

public void poll()

Description copied from interface: DoubleDBIDHeap

Remove the topmost element.

Specified by:

poll in interface DoubleDBIDHeap

Overrides:

poll in class DoubleIntegerDBIDHeap

size

public int size()

Description copied from interface: DoubleDBIDHeap

Current size of heap.

Specified by:

size in interface DoubleDBIDHeap

Overrides:

size in class DoubleIntegerDBIDHeap

Returns:

Heap size

isEmpty

public boolean isEmpty()

Description copied from interface: DoubleDBIDHeap

Test if the heap is empty.

Specified by:

isEmpty in interface DoubleDBIDHeap

Overrides:

isEmpty in class DoubleIntegerDBIDHeap

Returns:

true when empty.

clear

public void clear()

Description copied from interface: DoubleDBIDHeap

Clear the heap.

Specified by:

clear in interface DoubleDBIDHeap

Overrides:

clear in class DoubleIntegerDBIDHeap

toKNNList

public DoubleIntegerDBIDKNNList 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.

toKNNListSqrt

public DoubleIntegerDBIDKNNList toKNNListSqrt()

Description copied from interface: KNNHeap

Serialize to a KNNList, but applying sqrt to every distance. This empties the heap!

Specified by:

toKNNListSqrt in interface KNNHeap

Returns:

KNNList with the heaps contents.

peekKey

public double peekKey()

Description copied from interface: DoubleDBIDHeap

Get the topmost value (the heap is a DBIDRef, referencing the top element).

Specified by:

peekKey in interface DoubleDBIDHeap

Overrides:

peekKey in class DoubleIntegerDBIDHeap

Returns:

value at top

internalGetIndex

public int internalGetIndex()

Description copied from interface: DBIDRef

Internal only: Get the internal index.

NOT FOR PUBLIC USE - ELKI Optimization engine only.

Specified by:

internalGetIndex in interface DBIDRef

Overrides:

internalGetIndex in class DoubleIntegerDBIDHeap

Returns:

Internal index

contains

public boolean contains(DBIDRef o)

Description copied from interface: DoubleDBIDHeap

Check if an object is already in the heap (slow scan).

Specified by:

contains in interface DoubleDBIDHeap

Overrides:

contains in class DoubleIntegerDBIDHeap

Parameters:

o - Other object

Returns:

true if contained

unorderedIterator

public DoubleDBIDIter unorderedIterator()

Description copied from interface: DoubleDBIDHeap

Unordered iterator over the heap.

Specified by:

unorderedIterator in interface DoubleDBIDHeap

Overrides:

unorderedIterator in class DoubleIntegerDBIDHeap

Returns:

Iterator

toString

public java.lang.String toString()

Overrides:

toString in class DoubleIntegerDBIDHeap