moa.classifiers.lazy.neighboursearch

Class NearestNeighbourSearch.MyHeap

java.lang.Object

moa.classifiers.lazy.neighboursearch.NearestNeighbourSearch.MyHeap

Enclosing class:

NearestNeighbourSearch

protected class NearestNeighbourSearch.MyHeap
extends Object

A class for a heap to store the nearest k neighbours to an instance. The heap also takes care of cases where multiple neighbours are the same distance away. i.e. the minimum size of the heap is k.

Version:

$Revision: 8034 $

Author:

Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)

Constructor Summary

Constructors

Constructor and Description
NearestNeighbourSearch.MyHeap(int maxSize) constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected void	downheap() performs downheap operation for the heap to maintian its properties.
NearestNeighbourSearch.MyHeapElement	get() returns the first element and removes it from the heap.
NearestNeighbourSearch.MyHeapElement	getKthNearest() returns the kth nearest element or null if none there.
int	noOfKthNearest() returns the number of k nearest.
NearestNeighbourSearch.MyHeapElement	peek() peeks at the first element.
void	put(int i, double d) adds the value to the heap.
void	putBySubstitute(int i, double d) Puts an element by substituting it in place of the top most element.
void	putKthNearest(int i, double d) Stores kth nearest elements (if there are more than one).
int	size() returns the size of the heap.
int	totalSize() returns the total size.
protected void	upheap() performs upheap operation for the heap to maintian its properties.

Methods inherited from class java.lang.Object

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

Constructor Detail

NearestNeighbourSearch.MyHeap

public NearestNeighbourSearch.MyHeap(int maxSize)

constructor.

Parameters:

maxSize - the maximum size of the heap

Method Detail

size

public int size()

returns the size of the heap.

Returns:

the size

peek

public NearestNeighbourSearch.MyHeapElement peek()

peeks at the first element.

Returns:

the first element

get

public NearestNeighbourSearch.MyHeapElement get()
                                         throws Exception

returns the first element and removes it from the heap.

Returns:

the first element

Throws:

Exception - if no elements in heap

put

public void put(int i,
       double d)
         throws Exception

adds the value to the heap.

Parameters:

i - the index

d - the distance

Throws:

Exception - if the heap gets too large

putBySubstitute

public void putBySubstitute(int i,
                   double d)
                     throws Exception

Puts an element by substituting it in place of the top most element.

Parameters:

i - the index

d - the distance

Throws:

Exception - if distance is smaller than that of the head element

noOfKthNearest

public int noOfKthNearest()

returns the number of k nearest.

Returns:

the number of k nearest

See Also:

m_KthNearestSize

putKthNearest

public void putKthNearest(int i,
                 double d)

Stores kth nearest elements (if there are more than one).

Parameters:

i - the index

d - the distance

getKthNearest

public NearestNeighbourSearch.MyHeapElement getKthNearest()

returns the kth nearest element or null if none there.

Returns:

the kth nearest element

upheap

protected void upheap()

performs upheap operation for the heap to maintian its properties.

downheap

protected void downheap()

performs downheap operation for the heap to maintian its properties.

totalSize

public int totalSize()

returns the total size.

Returns:

the total size