21 #ifndef __MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP
22 #define __MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP
26 #include "../statistic.hpp"
49 template<
typename BoundType,
51 typename MatType = arma::mat>
86 template<
typename RuleType>
90 template<
typename RuleType>
113 std::vector<size_t>& oldFromNew,
130 std::vector<size_t>& oldFromNew,
131 std::vector<size_t>& newFromOld,
172 std::vector<size_t>& oldFromNew,
200 std::vector<size_t>& oldFromNew,
201 std::vector<size_t>& newFromOld,
294 typename BoundType::MetricType
Metric()
const {
return bound.Metric(); }
346 size_t Point(
const size_t index)
const;
369 return bound.MinDistance(point);
375 return bound.MaxDistance(point);
381 return bound.RangeDistance(point);
455 void SplitNode(MatType& data, std::vector<size_t>& oldFromNew);
465 size_t GetSplitIndex(MatType& data,
int splitDim,
double splitVal);
477 size_t GetSplitIndex(MatType& data,
int splitDim,
double splitVal,
478 std::vector<size_t>& oldFromNew);
491 #include "binary_space_tree_impl.hpp"
A dual-tree traverser for binary space trees; see dual_tree_traverser.hpp.
size_t & LeafSize()
Modify the leaf size.
BinarySpaceTree * right
The right child node.
BinarySpaceTree *& Parent()
Modify the parent of this node.
BinarySpaceTree *& Left()
Modify the left child of this node.
BinarySpaceTree * parent
The parent node (NULL if this is the root of the tree).
size_t End() const
Gets the index one beyond the last index in the subset.
BinarySpaceTree * Parent() const
Gets the parent of this node.
BoundType bound
The bound object for this node.
BoundType::MetricType Metric() const
Get the metric which the tree uses.
void SplitNode(MatType &data)
Splits the current node, assigning its left and right children recursively.
BinarySpaceTree * left
The left child node.
std::string ToString() const
Returns a string representation of this object.
BinarySpaceTree * CopyMe()
size_t splitDimension
The dimension this node split on if it is a parent.
BoundType & Bound()
Return the bound object for this node.
A binary space partitioning tree, such as a KD-tree or a ball tree.
size_t leafSize
The leaf size.
size_t GetSplitDimension() const
Returns the dimension this parent's children are split on.
const StatisticType & Stat() const
Return the statistic object for this node.
double FurthestDescendantDistance() const
Return the furthest possible descendant distance.
size_t NumPoints() const
Return the number of points in this node (0 if not a leaf).
size_t SplitDimension() const
Get the split dimension for this node.
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.
BinarySpaceTree *& Right()
Modify the right child of this node.
BinarySpaceTree * Right() const
Gets the right child of this node.
size_t & Begin()
Modify the index of the beginning point of this subset.
size_t LeafSize() const
Return the leaf size.
BinarySpaceTree * Left() const
Gets the left child of this node.
size_t count
The number of points of the dataset contained in this node (and its children).
size_t NumDescendants() const
Return the number of descendants of this node.
A single-tree traverser for binary space trees; see single_tree_traverser.hpp for implementation...
double MinDistance(const arma::vec &point) const
Return the minimum distance to another point.
size_t begin
The index of the first point in the dataset contained in this node (and its children).
BinarySpaceTree & Child(const size_t child) const
Return the specified child (0 will be left, 1 will be right).
size_t & Count()
Modify the number of points in this subset.
size_t Descendant(const size_t index) const
Return the index (with reference to the dataset) of a particular descendant of this node...
size_t Begin() const
Return the index of the beginning point of this subset.
size_t Count() const
Return the number of points in this subset.
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
const BinarySpaceTree * FindByBeginCount(size_t begin, size_t count) const
Find a node in this tree by its begin and count (const).
size_t TreeSize() const
Obtains the number of nodes in the tree, starting with this.
size_t NumChildren() const
Return the number of children in this node.
MatType Mat
So other classes can use TreeType::Mat.
math::Range RangeDistance(const BinarySpaceTree *other) const
Return the minimum and maximum distance to another node.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
static bool HasSelfChildren()
Returns false: this tree type does not have self children.
MatType & dataset
The dataset.
StatisticType & Stat()
Return the statistic object for this node.
math::Range RangeDistance(const arma::vec &point) const
Return the minimum and maximum distance to another point.
const arma::mat & Dataset() const
Get the dataset which the tree is built on.
~BinarySpaceTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn...
double furthestDescendantDistance
The distance to the furthest descendant, cached to speed things up.
const BoundType & Bound() const
Return the bound object for this node.
BinarySpaceTree(MatType &data, const size_t leafSize=20)
Construct this as the root node of a binary space tree using the given dataset.
size_t & SplitDimension()
Modify the split dimension for this node.
arma::mat & Dataset()
Modify the dataset which the tree is built on. Be careful!
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...
double MinDistance(const BinarySpaceTree *other) const
Return the minimum distance to another node.
double MaxDistance(const arma::vec &point) const
Return the maximum distance to another point.
void Centroid(arma::vec ¢roid)
Get the centroid of the node and store it in the given vector.
size_t TreeDepth() const
Obtains the number of levels below this node in the tree, starting with this.
Simple real-valued range.
StatisticType stat
Any extra data contained in the node.
size_t ExtendTree(const size_t level)
Fills the tree to the specified level.
double MaxDistance(const BinarySpaceTree *other) const
Return the maximum distance to another node.
Empty statistic if you are not interested in storing statistics in your tree.