Class NearestNeighborsGNAT::Node

Nested Relationships

This class is a nested type of Template Class NearestNeighborsGNAT.

Class Documentation

class Node

The class used internally to define the GNAT.

Public Functions

inline Node(int degree, int capacity, _T pivot)

Construct a node of given degree with at most capacity data elements and with given pivot.

inline ~Node()
inline void updateRadius(double dist)

Update minRadius_ and maxRadius_, given that an element was added with distance dist to the pivot.

inline void updateRange(unsigned int i, double dist)

Update minRange_[i] and maxRange_[i], given that an element was added to the i-th child of the parent that has distance dist to this Node’s pivot.

inline void add(GNAT &gnat, const _T &data)

Add an element to the tree rooted at this node.

inline bool needToSplit(const GNAT &gnat) const

Return true iff the node needs to be split into child nodes.

inline void split(GNAT &gnat)

The split operation finds pivot elements for the child nodes and moves each data element of this node to the appropriate child node.

inline bool insertNeighborK(NearQueue &nbh, std::size_t k, const _T &data, const _T &key, double dist) const

Insert data in nbh if it is a near neighbor. Return true iff data was added to nbh.

inline void nearestK(const GNAT &gnat, const _T &data, std::size_t k, NearQueue &nbh, NodeQueue &nodeQueue, bool &isPivot) const

Compute the k nearest neighbors of data in the tree. For k=1, isPivot is true if the nearest neighbor is a pivot (which is important during removal; removing pivots is a special case). The nodeQueue, which contains other Nodes that need to be checked for nearest neighbors, is updated.

inline void insertNeighborR(NearQueue &nbh, double r, const _T &data, double dist) const

Insert data in nbh if it is a near neighbor.

inline void nearestR(const GNAT &gnat, const _T &data, double r, NearQueue &nbh, NodeQueue &nodeQueue) const

Return all elements that are within distance r in nbh. The nodeQueue, which contains other Nodes that need to be checked for nearest neighbors, is updated.

inline void list(const GNAT &gnat, std::vector<_T> &data) const

Public Members

unsigned int degree_

Number of child nodes.

const _T pivot_

Data element stored in this Node.

double minRadius_

Minimum distance between the pivot element and the elements stored in data_.

double maxRadius_

Maximum distance between the pivot element and the elements stored in data_.

std::vector<double> minRange_

The i-th element in minRange_ is the minimum distance between the pivot and any data_ element in the i-th child node of this node’s parent.

std::vector<double> maxRange_

The i-th element in maxRange_ is the maximum distance between the pivot and any data_ element in the i-th child node of this node’s parent.

std::vector<_T> data_

The data elements stored in this node (in addition to the pivot element). An internal node has no elements stored in data_.

std::vector<Node*> children_

The child nodes of this node. By definition, only internal nodes have child nodes.

Friends

inline friend std::ostream &operator<<(std::ostream &out, const Node &node)