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

Class DoubleDistanceIntegerDBIDKNNHeap

java.lang.Object

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

All Implemented Interfaces:

DoubleDistanceKNNHeap, KNNHeap<DoubleDistance>

public class DoubleDistanceIntegerDBIDKNNHeap
extends Object
implements DoubleDistanceKNNHeap

Class to efficiently manage a kNN heap.

Field Summary

Fields

Modifier and Type	Field and Description
private DoubleIntegerMaxHeap	heap The main heap.
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

Constructor and Description
DoubleDistanceIntegerDBIDKNNHeap(int k) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
private void	addToTies(int id) Ensure the ties array has capacity for at least one more element.
void	clear() Clear the heap.
double	doubleKNNDistance() Get the distance to the k nearest neighbor, or maxdist otherwise.
int	getK() Get the K parameter ("maxsize" internally).
DoubleDistance	getKNNDistance() Deprecated.
double	insert(double distance, DBIDRef id) Add a distance-id pair to the heap unless the distance is too large.
void	insert(Double distance, DBIDRef id) Deprecated.
void	insert(DoubleDistanceDBIDPair e) Add a distance-id pair to the heap unless the distance is too large.
void	insert(DoubleDistance distance, DBIDRef id) Deprecated.
boolean	isEmpty() Test if the heap is empty.
DoubleDistanceIntegerDBIDPair	peek() Peek at the largest element in the heap.
protected double	peekDistance() Peek the topmost distance.
protected int	peekInternalDBID() Peek the topmost internal ID.
DoubleDistanceIntegerDBIDPair	poll() Poll the largest element from the heap.
protected void	pop() Pop the topmost element.
int	size() Current size of heap.
DoubleDistanceIntegerDBIDKNNList	toKNNList() Serialize to a KNNList.
private void	updateHeap(double distance, int iid) Do a full update for the heap.

Methods inherited from class java.lang.Object

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

Field Detail

k

private final int k

k for this heap.

heap

private final DoubleIntegerMaxHeap heap

The main 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

DoubleDistanceIntegerDBIDKNNHeap

public DoubleDistanceIntegerDBIDKNNHeap(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<DoubleDistance>

Returns:

K

getKNNDistance

@Deprecated
public DoubleDistance getKNNDistance()

Deprecated.

Description copied from interface: DoubleDistanceKNNHeap

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

Specified by:

getKNNDistance in interface DoubleDistanceKNNHeap

Specified by:

getKNNDistance in interface KNNHeap<DoubleDistance>

Returns:

Maximum distance

doubleKNNDistance

public double doubleKNNDistance()

Description copied from interface: DoubleDistanceKNNHeap

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

Specified by:

doubleKNNDistance in interface DoubleDistanceKNNHeap

Returns:

Maximum distance

insert

@Deprecated
public void insert(DoubleDistance distance,
                     DBIDRef id)

Deprecated.

Description copied from interface: DoubleDistanceKNNHeap

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 DoubleDistanceKNNHeap

Specified by:

insert in interface KNNHeap<DoubleDistance>

Parameters:

distance - Distance value

id - ID number

insert

@Deprecated
public void insert(Double distance,
                     DBIDRef id)

Deprecated.

Description copied from interface: DoubleDistanceKNNHeap

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 DoubleDistanceKNNHeap

Parameters:

distance - Distance value

id - ID number

insert

public final double insert(double distance,
            DBIDRef id)

Description copied from interface: DoubleDistanceKNNHeap

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 DoubleDistanceKNNHeap

Parameters:

distance - Distance value

id - ID number

Returns:

updated k-distance

insert

public void insert(DoubleDistanceDBIDPair e)

Description copied from interface: DoubleDistanceKNNHeap

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

Specified by:

insert in interface DoubleDistanceKNNHeap

Parameters:

e - Existing distance pair

updateHeap

private final void updateHeap(double distance,
              int iid)

Do a full update for the heap.

Parameters:

distance - Distance

iid - Object id

addToTies

private final void addToTies(int id)

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

Parameters:

id - Id to add

poll

public DoubleDistanceIntegerDBIDPair 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 DoubleDistanceKNNHeap

Specified by:

poll in interface KNNHeap<DoubleDistance>

Returns:

largest element

pop

protected void pop()

Pop the topmost element.

peek

public DoubleDistanceIntegerDBIDPair peek()

Description copied from interface: KNNHeap

Peek at the largest element in the heap.

Specified by:

peek in interface DoubleDistanceKNNHeap

Specified by:

peek in interface KNNHeap<DoubleDistance>

Returns:

The current largest element.

size

public int size()

Description copied from interface: KNNHeap

Current size of heap.

Specified by:

size in interface KNNHeap<DoubleDistance>

Returns:

Heap size

isEmpty

public boolean isEmpty()

Description copied from interface: KNNHeap

Test if the heap is empty.

Specified by:

isEmpty in interface KNNHeap<DoubleDistance>

Returns:

true when empty.

clear

public void clear()

Description copied from interface: KNNHeap

Clear the heap.

Specified by:

clear in interface KNNHeap<DoubleDistance>

toKNNList

public DoubleDistanceIntegerDBIDKNNList toKNNList()

Description copied from interface: KNNHeap

Serialize to a KNNList. This empties the heap!

Specified by:

toKNNList in interface DoubleDistanceKNNHeap

Specified by:

toKNNList in interface KNNHeap<DoubleDistance>

Returns:

KNNList with the heaps contents.

peekDistance

protected double peekDistance()

Peek the topmost distance.

Returns:

distance

peekInternalDBID

protected int peekInternalDBID()

Peek the topmost internal ID.

Returns:

internal id