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
All Methods Instance Methods Concrete Methods 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 heapint
internalGetIndex()
Internal only: Get the internal index.boolean
isEmpty()
Test if the heap is empty.double
peekKey()
Get the topmost value (the heap is aDBIDRef
, referencing the top element).void
poll()
Remove the topmost element.int
size()
Current size of heap.DoubleIntegerDBIDKNNList
toKNNList()
Serialize to aKNNList
.DoubleIntegerDBIDKNNList
toKNNListSqrt()
Serialize to aKNNList
, 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
-
-
-
-
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
-
-
Method Detail
-
getK
public int getK()
Description copied from interface:KNNHeap
Get the K parameter ("maxsize" internally).
-
getKNNDistance
public double getKNNDistance()
Description copied from interface:KNNHeap
Get the distance to the k nearest neighbor, or maxdist otherwise.- Specified by:
getKNNDistance
in interfaceKNNHeap
- 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 interfaceDoubleDBIDHeap
- Specified by:
insert
in interfaceKNNHeap
- Overrides:
insert
in classDoubleIntegerDBIDHeap
- Parameters:
distance
- Key valueid
- 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 interfaceDoubleDBIDHeap
- Overrides:
poll
in classDoubleIntegerDBIDHeap
-
size
public int size()
Description copied from interface:DoubleDBIDHeap
Current size of heap.- Specified by:
size
in interfaceDoubleDBIDHeap
- Overrides:
size
in classDoubleIntegerDBIDHeap
- Returns:
- Heap size
-
isEmpty
public boolean isEmpty()
Description copied from interface:DoubleDBIDHeap
Test if the heap is empty.- Specified by:
isEmpty
in interfaceDoubleDBIDHeap
- Overrides:
isEmpty
in classDoubleIntegerDBIDHeap
- Returns:
- true when empty.
-
clear
public void clear()
Description copied from interface:DoubleDBIDHeap
Clear the heap.- Specified by:
clear
in interfaceDoubleDBIDHeap
- Overrides:
clear
in classDoubleIntegerDBIDHeap
-
toKNNList
public DoubleIntegerDBIDKNNList toKNNList()
Description copied from interface:KNNHeap
Serialize to aKNNList
. This empties the heap!
-
toKNNListSqrt
public DoubleIntegerDBIDKNNList toKNNListSqrt()
Description copied from interface:KNNHeap
Serialize to aKNNList
, but applying sqrt to every distance. This empties the heap!- Specified by:
toKNNListSqrt
in interfaceKNNHeap
- Returns:
- KNNList with the heaps contents.
-
peekKey
public double peekKey()
Description copied from interface:DoubleDBIDHeap
Get the topmost value (the heap is aDBIDRef
, referencing the top element).- Specified by:
peekKey
in interfaceDoubleDBIDHeap
- Overrides:
peekKey
in classDoubleIntegerDBIDHeap
- 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 interfaceDBIDRef
- Overrides:
internalGetIndex
in classDoubleIntegerDBIDHeap
- 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 interfaceDoubleDBIDHeap
- Overrides:
contains
in classDoubleIntegerDBIDHeap
- 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 interfaceDoubleDBIDHeap
- Overrides:
unorderedIterator
in classDoubleIntegerDBIDHeap
- Returns:
- Iterator
-
toString
public java.lang.String toString()
- Overrides:
toString
in classDoubleIntegerDBIDHeap
-
-