MLPACK  1.0.7
Classes | Public Types | Public Member Functions | Static Public Member Functions | Private Member Functions | Private Attributes | List of all members
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType > Class Template Reference

A binary space partitioning tree, such as a KD-tree or a ball tree. More...

Collaboration diagram for mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >:
Collaboration graph
[legend]

Classes

class  DualTreeTraverser
 A dual-tree traverser for binary space trees; see dual_tree_traverser.hpp. More...
 
class  SingleTreeTraverser
 A single-tree traverser for binary space trees; see single_tree_traverser.hpp for implementation. More...
 

Public Types

typedef MatType Mat
 So other classes can use TreeType::Mat. More...
 

Public Member Functions

 BinarySpaceTree (MatType &data, const size_t leafSize=20)
 Construct this as the root node of a binary space tree using the given dataset. More...
 
 BinarySpaceTree (MatType &data, std::vector< size_t > &oldFromNew, const size_t leafSize=20)
 Construct this as the root node of a binary space tree using the given dataset. More...
 
 BinarySpaceTree (MatType &data, std::vector< size_t > &oldFromNew, std::vector< size_t > &newFromOld, const size_t leafSize=20)
 Construct this as the root node of a binary space tree using the given dataset. More...
 
 BinarySpaceTree (MatType &data, const size_t begin, const size_t count, BinarySpaceTree *parent=NULL, const size_t leafSize=20)
 Construct this node on a subset of the given matrix, starting at column begin and using count points. More...
 
 BinarySpaceTree (MatType &data, const size_t begin, const size_t count, std::vector< size_t > &oldFromNew, BinarySpaceTree *parent=NULL, const size_t leafSize=20)
 Construct this node on a subset of the given matrix, starting at column begin_in and using count_in points. More...
 
 BinarySpaceTree (MatType &data, const size_t begin, const size_t count, std::vector< size_t > &oldFromNew, std::vector< size_t > &newFromOld, BinarySpaceTree *parent=NULL, const size_t leafSize=20)
 Construct this node on a subset of the given matrix, starting at column begin_in and using count_in points. More...
 
 BinarySpaceTree (const BinarySpaceTree &other)
 Create a binary space tree by copying the other tree. More...
 
 ~BinarySpaceTree ()
 Deletes this node, deallocating the memory for the children and calling their destructors in turn. More...
 
size_t Begin () const
 Return the index of the beginning point of this subset. More...
 
size_t & Begin ()
 Modify the index of the beginning point of this subset. More...
 
const BoundType & Bound () const
 Return the bound object for this node. More...
 
BoundType & Bound ()
 Return the bound object for this node. More...
 
void Centroid (arma::vec &centroid)
 Get the centroid of the node and store it in the given vector. More...
 
BinarySpaceTreeChild (const size_t child) const
 Return the specified child (0 will be left, 1 will be right). More...
 
size_t Count () const
 Return the number of points in this subset. More...
 
size_t & Count ()
 Modify the number of points in this subset. More...
 
const arma::mat & Dataset () const
 Get the dataset which the tree is built on. More...
 
arma::mat & Dataset ()
 Modify the dataset which the tree is built on. Be careful! More...
 
size_t Descendant (const size_t index) const
 Return the index (with reference to the dataset) of a particular descendant of this node. More...
 
size_t End () const
 Gets the index one beyond the last index in the subset. More...
 
size_t ExtendTree (const size_t level)
 Fills the tree to the specified level. More...
 
const BinarySpaceTreeFindByBeginCount (size_t begin, size_t count) const
 Find a node in this tree by its begin and count (const). More...
 
BinarySpaceTreeFindByBeginCount (size_t begin, size_t count)
 Find a node in this tree by its begin and count. More...
 
double FurthestDescendantDistance () const
 Return the furthest possible descendant distance. More...
 
size_t GetSplitDimension () const
 Returns the dimension this parent's children are split on. More...
 
bool IsLeaf () const
 Return whether or not this node is a leaf (true if it has no children). More...
 
size_t LeafSize () const
 Return the leaf size. More...
 
size_t & LeafSize ()
 Modify the leaf size. More...
 
BinarySpaceTreeLeft () const
 Gets the left child of this node. More...
 
BinarySpaceTree *& Left ()
 Modify the left child of this node. More...
 
double MaxDistance (const BinarySpaceTree *other) const
 Return the maximum distance to another node. More...
 
double MaxDistance (const arma::vec &point) const
 Return the maximum distance to another point. More...
 
BoundType::MetricType Metric () const
 Get the metric which the tree uses. More...
 
double MinDistance (const BinarySpaceTree *other) const
 Return the minimum distance to another node. More...
 
double MinDistance (const arma::vec &point) const
 Return the minimum distance to another point. More...
 
size_t NumChildren () const
 Return the number of children in this node. More...
 
size_t NumDescendants () const
 Return the number of descendants of this node. More...
 
size_t NumPoints () const
 Return the number of points in this node (0 if not a leaf). More...
 
BinarySpaceTreeParent () const
 Gets the parent of this node. More...
 
BinarySpaceTree *& Parent ()
 Modify the parent of this node. More...
 
size_t Point (const size_t index) const
 Return the index (with reference to the dataset) of a particular point in this node. More...
 
math::Range RangeDistance (const BinarySpaceTree *other) const
 Return the minimum and maximum distance to another node. More...
 
math::Range RangeDistance (const arma::vec &point) const
 Return the minimum and maximum distance to another point. More...
 
BinarySpaceTreeRight () const
 Gets the right child of this node. More...
 
BinarySpaceTree *& Right ()
 Modify the right child of this node. More...
 
size_t SplitDimension () const
 Get the split dimension for this node. More...
 
size_t & SplitDimension ()
 Modify the split dimension for this node. More...
 
const StatisticType & Stat () const
 Return the statistic object for this node. More...
 
StatisticType & Stat ()
 Return the statistic object for this node. More...
 
std::string ToString () const
 Returns a string representation of this object. More...
 
size_t TreeDepth () const
 Obtains the number of levels below this node in the tree, starting with this. More...
 
size_t TreeSize () const
 Obtains the number of nodes in the tree, starting with this. More...
 

Static Public Member Functions

static bool HasSelfChildren ()
 Returns false: this tree type does not have self children. More...
 

Private Member Functions

 BinarySpaceTree (const size_t begin, const size_t count, BoundType bound, StatisticType stat, const int leafSize=20)
 Private copy constructor, available only to fill (pad) the tree to a specified level. More...
 
BinarySpaceTreeCopyMe ()
 
size_t GetSplitIndex (MatType &data, int splitDim, double splitVal)
 Find the index to split on for this node, given that we are splitting in the given split dimension on the specified split value. More...
 
size_t GetSplitIndex (MatType &data, int splitDim, double splitVal, std::vector< size_t > &oldFromNew)
 Find the index to split on for this node, given that we are splitting in the given split dimension on the specified split value. More...
 
void SplitNode (MatType &data)
 Splits the current node, assigning its left and right children recursively. More...
 
void SplitNode (MatType &data, std::vector< size_t > &oldFromNew)
 Splits the current node, assigning its left and right children recursively. More...
 

Private Attributes

size_t begin
 The index of the first point in the dataset contained in this node (and its children). More...
 
BoundType bound
 The bound object for this node. More...
 
size_t count
 The number of points of the dataset contained in this node (and its children). More...
 
MatType & dataset
 The dataset. More...
 
double furthestDescendantDistance
 The distance to the furthest descendant, cached to speed things up. More...
 
size_t leafSize
 The leaf size. More...
 
BinarySpaceTreeleft
 The left child node. More...
 
BinarySpaceTreeparent
 The parent node (NULL if this is the root of the tree). More...
 
BinarySpaceTreeright
 The right child node. More...
 
size_t splitDimension
 The dimension this node split on if it is a parent. More...
 
StatisticType stat
 Any extra data contained in the node. More...
 

Detailed Description

template<typename BoundType, typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
class mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >

A binary space partitioning tree, such as a KD-tree or a ball tree.

Once the bound and type of dataset is defined, the tree will construct itself. Call the constructor with the dataset to build the tree on, and the entire tree will be built.

This particular tree does not allow growth, so you cannot add or delete nodes from it. If you need to add or delete a node, the better procedure is to rebuild the tree entirely.

This tree does take one parameter, which is the leaf size to be used.

Template Parameters
BoundTypeThe bound used for each node. The valid types of bounds and the necessary skeleton interface for this class can be found in bounds/.
StatisticTypeExtra data contained in the node. See statistic.hpp for the necessary skeleton interface.

Definition at line 52 of file binary_space_tree.hpp.

Member Typedef Documentation

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
typedef MatType mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Mat

So other classes can use TreeType::Mat.

Definition at line 82 of file binary_space_tree.hpp.

Constructor & Destructor Documentation

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree ( MatType &  data,
const size_t  leafSize = 20 
)

Construct this as the root node of a binary space tree using the given dataset.

This will modify the ordering of the points in the dataset!

Parameters
dataDataset to create tree from. This will be modified!
leafSizeSize of each leaf in the tree.

Referenced by mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::CopyMe().

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree ( MatType &  data,
std::vector< size_t > &  oldFromNew,
const size_t  leafSize = 20 
)

Construct this as the root node of a binary space tree using the given dataset.

This will modify the ordering of points in the dataset! A mapping of the old point indices to the new point indices is filled.

Parameters
dataDataset to create tree from. This will be modified!
oldFromNewVector which will be filled with the old positions for each new point.
leafSizeSize of each leaf in the tree.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree ( MatType &  data,
std::vector< size_t > &  oldFromNew,
std::vector< size_t > &  newFromOld,
const size_t  leafSize = 20 
)

Construct this as the root node of a binary space tree using the given dataset.

This will modify the ordering of points in the dataset! A mapping of the old point indices to the new point indices is filled, as well as a mapping of the new point indices to the old point indices.

Parameters
dataDataset to create tree from. This will be modified!
oldFromNewVector which will be filled with the old positions for each new point.
newFromOldVector which will be filled with the new positions for each old point.
leafSizeSize of each leaf in the tree.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree ( MatType &  data,
const size_t  begin,
const size_t  count,
BinarySpaceTree< BoundType, StatisticType, MatType > *  parent = NULL,
const size_t  leafSize = 20 
)

Construct this node on a subset of the given matrix, starting at column begin and using count points.

The ordering of that subset of points will be modified! This is used for recursive tree-building by the other constructors which don't specify point indices.

Parameters
dataDataset to create tree from. This will be modified!
beginIndex of point to start tree construction with.
countNumber of points to use to construct tree.
leafSizeSize of each leaf in the tree.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree ( MatType &  data,
const size_t  begin,
const size_t  count,
std::vector< size_t > &  oldFromNew,
BinarySpaceTree< BoundType, StatisticType, MatType > *  parent = NULL,
const size_t  leafSize = 20 
)

Construct this node on a subset of the given matrix, starting at column begin_in and using count_in points.

The ordering of that subset of points will be modified! This is used for recursive tree-building by the other constructors which don't specify point indices.

A mapping of the old point indices to the new point indices is filled, but it is expected that the vector is already allocated with size greater than or equal to (begin_in + count_in), and if that is not true, invalid memory reads (and writes) will occur.

Parameters
dataDataset to create tree from. This will be modified!
beginIndex of point to start tree construction with.
countNumber of points to use to construct tree.
oldFromNewVector which will be filled with the old positions for each new point.
leafSizeSize of each leaf in the tree.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree ( MatType &  data,
const size_t  begin,
const size_t  count,
std::vector< size_t > &  oldFromNew,
std::vector< size_t > &  newFromOld,
BinarySpaceTree< BoundType, StatisticType, MatType > *  parent = NULL,
const size_t  leafSize = 20 
)

Construct this node on a subset of the given matrix, starting at column begin_in and using count_in points.

The ordering of that subset of points will be modified! This is used for recursive tree-building by the other constructors which don't specify point indices.

A mapping of the old point indices to the new point indices is filled, as well as a mapping of the new point indices to the old point indices. It is expected that the vector is already allocated with size greater than or equal to (begin_in + count_in), and if that is not true, invalid memory reads (and writes) will occur.

Parameters
dataDataset to create tree from. This will be modified!
beginIndex of point to start tree construction with.
countNumber of points to use to construct tree.
oldFromNewVector which will be filled with the old positions for each new point.
newFromOldVector which will be filled with the new positions for each old point.
leafSizeSize of each leaf in the tree.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree ( const BinarySpaceTree< BoundType, StatisticType, MatType > &  other)

Create a binary space tree by copying the other tree.

Be careful! This can take a long time and use a lot of memory.

Parameters
otherTree to be replicated.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::~BinarySpaceTree ( )

Deletes this node, deallocating the memory for the children and calling their destructors in turn.

This will invalidate any pointers or references to any nodes which are children of this one.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree ( const size_t  begin,
const size_t  count,
BoundType  bound,
StatisticType  stat,
const int  leafSize = 20 
)
inlineprivate

Private copy constructor, available only to fill (pad) the tree to a specified level.

Definition at line 423 of file binary_space_tree.hpp.

Member Function Documentation

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Begin ( ) const
inline

Return the index of the beginning point of this subset.

Definition at line 401 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::begin.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Begin ( )
inline

Modify the index of the beginning point of this subset.

Definition at line 403 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::begin.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
const BoundType& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Bound ( ) const
inline
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BoundType& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Bound ( )
inline

Return the bound object for this node.

Definition at line 250 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::bound.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
void mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Centroid ( arma::vec &  centroid)
inline

Get the centroid of the node and store it in the given vector.

Definition at line 297 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::bound.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BinarySpaceTree& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Child ( const size_t  child) const

Return the specified child (0 will be left, 1 will be right).

If the index is greater than 1, this will return the right child.

Parameters
childIndex of child to return.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::CopyMe ( )
inlineprivate
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Count ( ) const
inline

Return the number of points in this subset.

Definition at line 411 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::count.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Count ( )
inline

Modify the number of points in this subset.

Definition at line 413 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::count.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
const arma::mat& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Dataset ( ) const
inline

Get the dataset which the tree is built on.

Definition at line 289 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::dataset.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
arma::mat& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Dataset ( )
inline

Modify the dataset which the tree is built on. Be careful!

Definition at line 291 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::dataset.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Descendant ( const size_t  index) const

Return the index (with reference to the dataset) of a particular descendant of this node.

The index should be greater than zero but less than the number of descendants.

Parameters
indexIndex of the descendant.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::End ( ) const

Gets the index one beyond the last index in the subset.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::ExtendTree ( const size_t  level)

Fills the tree to the specified level.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
const BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::FindByBeginCount ( size_t  begin,
size_t  count 
) const

Find a node in this tree by its begin and count (const).

Every node is uniquely identified by these two numbers. This is useful for communicating position over the network, when pointers would be invalid.

Parameters
beginThe begin() of the node to find.
countThe count() of the node to find.
Returns
The found node, or NULL if not found.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::FindByBeginCount ( size_t  begin,
size_t  count 
)

Find a node in this tree by its begin and count.

Every node is uniquely identified by these two numbers. This is useful for communicating position over the network, when pointers would be invalid.

Parameters
beginThe begin() of the node to find.
countThe count() of the node to find.
Returns
The found node, or NULL if not found.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
double mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::FurthestDescendantDistance ( ) const

Return the furthest possible descendant distance.

This returns the maximum distance from the centroid to the edge of the bound and not the empirical quantity which is the actual furthest descendant distance. So the actual furthest descendant distance may be less than what this method returns (but it will never be greater than this).

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::GetSplitDimension ( ) const

Returns the dimension this parent's children are split on.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::GetSplitIndex ( MatType &  data,
int  splitDim,
double  splitVal 
)
private

Find the index to split on for this node, given that we are splitting in the given split dimension on the specified split value.

Parameters
dataDataset which we are using.
splitDimDimension of dataset to split on.
splitValValue to split on, in the given split dimension.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::GetSplitIndex ( MatType &  data,
int  splitDim,
double  splitVal,
std::vector< size_t > &  oldFromNew 
)
private

Find the index to split on for this node, given that we are splitting in the given split dimension on the specified split value.

Also returns a list of the changed indices.

Parameters
dataDataset which we are using.
splitDimDimension of dataset to split on.
splitValValue to split on, in the given split dimension.
oldFromNewVector holding permuted indices.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
static bool mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::HasSelfChildren ( )
inlinestatic

Returns false: this tree type does not have self children.

Definition at line 416 of file binary_space_tree.hpp.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
bool mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::IsLeaf ( ) const

Return whether or not this node is a leaf (true if it has no children).

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::LeafSize ( ) const
inline
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::LeafSize ( )
inline
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Left ( ) const
inline

Gets the left child of this node.

Definition at line 269 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::left.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BinarySpaceTree*& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Left ( )
inline

Modify the left child of this node.

Definition at line 271 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::left.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
double mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::MaxDistance ( const BinarySpaceTree< BoundType, StatisticType, MatType > *  other) const
inline
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
double mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::MaxDistance ( const arma::vec &  point) const
inline

Return the maximum distance to another point.

Definition at line 373 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::bound.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BoundType::MetricType mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Metric ( ) const
inline

Get the metric which the tree uses.

Definition at line 294 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::bound.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
double mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::MinDistance ( const BinarySpaceTree< BoundType, StatisticType, MatType > *  other) const
inline
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
double mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::MinDistance ( const arma::vec &  point) const
inline

Return the minimum distance to another point.

Definition at line 367 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::bound.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::NumChildren ( ) const

Return the number of children in this node.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::NumDescendants ( ) const

Return the number of descendants of this node.

For a non-leaf in a binary space tree, this is the number of points at the descendant leaves. For a leaf, this is the number of points in the leaf.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::NumPoints ( ) const

Return the number of points in this node (0 if not a leaf).

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Parent ( ) const
inline

Gets the parent of this node.

Definition at line 279 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::parent.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BinarySpaceTree*& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Parent ( )
inline

Modify the parent of this node.

Definition at line 281 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::parent.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Point ( const size_t  index) const

Return the index (with reference to the dataset) of a particular point in this node.

This will happily return invalid indices if the given index is greater than the number of points in this node (obtained with NumPoints()) – be careful.

Parameters
indexIndex of point for which a dataset index is wanted.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
math::Range mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::RangeDistance ( const BinarySpaceTree< BoundType, StatisticType, MatType > *  other) const
inline
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
math::Range mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::RangeDistance ( const arma::vec &  point) const
inline

Return the minimum and maximum distance to another point.

Definition at line 379 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::bound.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Right ( ) const
inline

Gets the right child of this node.

Definition at line 274 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::right.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BinarySpaceTree*& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Right ( )
inline

Modify the right child of this node.

Definition at line 276 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::right.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::SplitDimension ( ) const
inline

Get the split dimension for this node.

Definition at line 284 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::splitDimension.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::SplitDimension ( )
inline

Modify the split dimension for this node.

Definition at line 286 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::splitDimension.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
void mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::SplitNode ( MatType &  data)
private

Splits the current node, assigning its left and right children recursively.

Parameters
dataDataset which we are using.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
void mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::SplitNode ( MatType &  data,
std::vector< size_t > &  oldFromNew 
)
private

Splits the current node, assigning its left and right children recursively.

Also returns a list of the changed indices.

Parameters
dataDataset which we are using.
oldFromNewVector holding permuted indices.
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
const StatisticType& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Stat ( ) const
inline

Return the statistic object for this node.

Definition at line 253 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::stat.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
StatisticType& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Stat ( )
inline

Return the statistic object for this node.

Definition at line 255 of file binary_space_tree.hpp.

References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::stat.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
std::string mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::ToString ( ) const

Returns a string representation of this object.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::TreeDepth ( ) const

Obtains the number of levels below this node in the tree, starting with this.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::TreeSize ( ) const

Obtains the number of nodes in the tree, starting with this.

Member Data Documentation

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::begin
private

The index of the first point in the dataset contained in this node (and its children).

Definition at line 63 of file binary_space_tree.hpp.

Referenced by mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Begin(), and mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::CopyMe().

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BoundType mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::bound
private
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::count
private

The number of points of the dataset contained in this node (and its children).

Definition at line 66 of file binary_space_tree.hpp.

Referenced by mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::CopyMe(), and mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Count().

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
MatType& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::dataset
private
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
double mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::furthestDescendantDistance
private

The distance to the furthest descendant, cached to speed things up.

Definition at line 76 of file binary_space_tree.hpp.

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::leafSize
private
template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::left
private

The left child node.

Definition at line 56 of file binary_space_tree.hpp.

Referenced by mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Left().

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::parent
private

The parent node (NULL if this is the root of the tree).

Definition at line 60 of file binary_space_tree.hpp.

Referenced by mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Parent().

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::right
private

The right child node.

Definition at line 58 of file binary_space_tree.hpp.

Referenced by mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Right().

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::splitDimension
private

The dimension this node split on if it is a parent.

Definition at line 74 of file binary_space_tree.hpp.

Referenced by mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::SplitDimension().

template<typename BoundType , typename StatisticType = EmptyStatistic, typename MatType = arma::mat>
StatisticType mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::stat
private

The documentation for this class was generated from the following file: