DoubleIntegerDBIDKNNHeap (ELKI: Environment for DeveLoping KDD-Applications Supported by Index-Structures)

java.lang.Object
- de.lmu.ifi.dbs.elki.database.ids.integer.DoubleIntegerDBIDKNNHeap

All Implemented Interfaces:

KNNHeap
```
class DoubleIntegerDBIDKNNHeap
extends java.lang.Object
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 and Description

private class DoubleIntegerDBIDKNNHeap.UnorderedIter
Iterate over all objects in the heap, not ordered.

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

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
Modifier Constructor and Description

protected DoubleIntegerDBIDKNNHeap(int k)
Constructor.

Constructors
Modifier	Constructor and Description
`protected`	`DoubleIntegerDBIDKNNHeap(int k)` Constructor.

Method Summary

All Methods Instance Methods Concrete 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.
`boolean`	`contains(DBIDRef o)` Check if an object is already in the heap.
`int`	`getK()` Get the K parameter ("maxsize" internally).
`double`	`getKNNDistance()` Get the distance to the k nearest neighbor, or maxdist otherwise.
`void`	`insert(DoubleDBIDPair e)` Add a distance-id pair to the heap unless the distance is too large.
`double`	`insert(double distance, DBIDRef id)` Add a distance-id pair to the heap unless the distance is too large.
`boolean`	`isEmpty()` Test if the heap is empty.
`protected double`	`peekDistance()` Peek the topmost distance.
`protected int`	`peekInternalDBID()` Peek the topmost internal ID.
`protected void`	`pop()` Pop 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.
`DoubleDBIDListIter`	`unorderedIterator()` Unordered iterator over the heap.
`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
  - 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: 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:
    
    distance - Distance value
    
    id - ID number
    
    Returns:
    
    current k-distance
  - 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
  - updateHeap
```
private void updateHeap(double distance,
                        int iid)
```
    Do a full update for the heap.
    
    Parameters:
    
    distance - Distance
    
    iid - Object id
  - addToTies
```
private void addToTies(int id)
```
    Ensure the ties array has capacity for at least one more element.
    
    Parameters:
    
    id - Id to add
  - pop
```
protected void pop()
```
    Pop the topmost element.
  - size
```
public int size()
```
    Description copied from interface: KNNHeap
    
    Current size of heap.
    
    Specified by:
    
    size in interface KNNHeap
    
    Returns:
    
    Heap size
  - isEmpty
```
public boolean isEmpty()
```
    Description copied from interface: KNNHeap
    
    Test if the heap is empty.
    
    Specified by:
    
    isEmpty in interface KNNHeap
    
    Returns:
    
    true when empty.
  - clear
```
public void clear()
```
    Description copied from interface: KNNHeap
    
    Clear the heap.
    
    Specified by:
    
    clear in interface KNNHeap
  - 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.
  - peekDistance
```
protected double peekDistance()
```
    Peek the topmost distance.
    
    Returns:
    
    distance
  - peekInternalDBID
```
protected int peekInternalDBID()
```
    Peek the topmost internal ID.
    
    Returns:
    
    internal id
  - contains
```
public boolean contains(DBIDRef o)
```
    Description copied from interface: KNNHeap
    
    Check if an object is already in the heap.
    
    Specified by:
    
    contains in interface KNNHeap
    
    Parameters:
    
    o - Other object
    
    Returns:
    
    true if contained
  - unorderedIterator
```
public DoubleDBIDListIter unorderedIterator()
```
    Description copied from interface: KNNHeap
    
    Unordered iterator over the heap.
    
    Specified by:
    
    unorderedIterator in interface KNNHeap
    
    Returns:
    
    Iterator

Class DoubleIntegerDBIDKNNHeap

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

k

heap

ties

numties

kdist

INITIAL_TIES_SIZE

Constructor Detail

DoubleIntegerDBIDKNNHeap

Method Detail

getK

getKNNDistance

insert

insert

updateHeap

addToTies

pop

size

isEmpty

clear

toKNNList

toKNNListSqrt

peekDistance

peekInternalDBID

contains

unorderedIterator