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

Class DoubleDistanceIntegerDBIDPairKNNListHeap

java.lang.Object

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

All Implemented Interfaces:

DBIDs, DistanceDBIDList<DoubleDistance>, DoubleDistanceKNNHeap, DoubleDistanceKNNList, KNNHeap<DoubleDistance>, KNNList<DoubleDistance>

public class DoubleDistanceIntegerDBIDPairKNNListHeap
extends Object
implements DoubleDistanceKNNList, DoubleDistanceKNNHeap

Finalized KNN List.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private class	DoubleDistanceIntegerDBIDPairKNNListHeap.Itr Iterator.

Field Summary

Fields

Modifier and Type	Field and Description
private DoubleDistanceIntegerDBIDPair[]	data The actual data array.
private int	k The value of k this was materialized for.
private int	size Current size

Constructor Summary

Constructors

Constructor and Description
DoubleDistanceIntegerDBIDPairKNNListHeap(int k) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
void	clear() Clear the heap.
boolean	contains(DBIDRef o) Test whether an ID is contained.
double	doubleKNNDistance() Get the kNN distance as double value.
DoubleDistanceIntegerDBIDPair	get(int index) Direct object access.
int	getK() Get the K parameter (note: this may be less than the size of the list!)
DoubleDistance	getKNNDistance() Deprecated.
private void	grow()
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 dist, DBIDRef id) Deprecated.
private void	insertionSort(DoubleDistanceIntegerDBIDPair obj) Perform insertion sort.
boolean	isEmpty() Test for an empty DBID collection.
DoubleDistanceIntegerDBIDListIter	iter() Get an iterator
DoubleDistanceIntegerDBIDPair	peek() Peek at the largest element in the heap.
DoubleDistanceIntegerDBIDPair	poll() Poll the largest element from the heap.
int	size() Size
DoubleDistanceKNNList	toKNNList() Serialize to a KNNList.
String	toString()
private void	truncate()

Methods inherited from class java.lang.Object

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

Field Detail

k

private final int k

The value of k this was materialized for.

data

private DoubleDistanceIntegerDBIDPair[] data

The actual data array.

size

private int size

Current size

Constructor Detail

DoubleDistanceIntegerDBIDPairKNNListHeap

public DoubleDistanceIntegerDBIDPairKNNListHeap(int k)

Constructor.

Parameters:

k - K parameter

Method Detail

clear

public void clear()

Description copied from interface: KNNHeap

Clear the heap.

Specified by:

clear in interface KNNHeap<DoubleDistance>

insert

public 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

truncate

private void truncate()

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

@Deprecated
public void insert(DoubleDistance dist,
                     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:

dist - Distance value

id - ID number

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

insertionSort

private void insertionSort(DoubleDistanceIntegerDBIDPair obj)

Perform insertion sort.

Parameters:

obj - Object to insert

grow

private void grow()

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

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.

toKNNList

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

getK

public int getK()

Description copied from interface: KNNList

Get the K parameter (note: this may be less than the size of the list!)

Specified by:

getK in interface KNNHeap<DoubleDistance>

Specified by:

getK in interface KNNList<DoubleDistance>

Returns:

K

getKNNDistance

@Deprecated
public DoubleDistance getKNNDistance()

Deprecated.

Description copied from interface: DoubleDistanceKNNList

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

Specified by:

getKNNDistance in interface DoubleDistanceKNNHeap

Specified by:

getKNNDistance in interface DoubleDistanceKNNList

Specified by:

getKNNDistance in interface KNNHeap<DoubleDistance>

Specified by:

getKNNDistance in interface KNNList<DoubleDistance>

Returns:

Maximum distance

doubleKNNDistance

public double doubleKNNDistance()

Description copied from interface: DoubleDistanceKNNList

Get the kNN distance as double value.

Specified by:

doubleKNNDistance in interface DoubleDistanceKNNHeap

Specified by:

doubleKNNDistance in interface DoubleDistanceKNNList

Returns:

Distance

toString

public String toString()

Overrides:

toString in class Object

get

public DoubleDistanceIntegerDBIDPair get(int index)

Description copied from interface: KNNList

Direct object access.

Specified by:

get in interface DistanceDBIDList<DoubleDistance>

Specified by:

get in interface DoubleDistanceKNNList

Specified by:

get in interface KNNList<DoubleDistance>

Parameters:

index - Offset

Returns:

Pair

iter

public DoubleDistanceIntegerDBIDListIter iter()

Description copied from interface: DistanceDBIDList

Get an iterator

Specified by:

iter in interface DBIDs

Specified by:

iter in interface DistanceDBIDList<DoubleDistance>

Specified by:

iter in interface DoubleDistanceKNNList

Returns:

New iterator

size

public int size()

Description copied from interface: KNNList

Size

Specified by:

size in interface DBIDs

Specified by:

size in interface DistanceDBIDList<DoubleDistance>

Specified by:

size in interface KNNHeap<DoubleDistance>

Specified by:

size in interface KNNList<DoubleDistance>

Returns:

Size

contains

public boolean contains(DBIDRef o)

Description copied from interface: DBIDs

Test whether an ID is contained.

Specified by:

contains in interface DBIDs

Parameters:

o - object to test

Returns:

true when contained

isEmpty

public boolean isEmpty()

Description copied from interface: DBIDs

Test for an empty DBID collection.

Specified by:

isEmpty in interface DBIDs

Specified by:

isEmpty in interface KNNHeap<DoubleDistance>

Returns:

true when empty.