21 #ifndef __MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP
22 #define __MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP
27 #include "../statistic.hpp"
55 template<
typename BoundType,
57 typename MatType = arma::mat,
98 template<
typename RuleType>
102 template<
typename RuleType>
125 std::vector<size_t>& oldFromNew,
126 const size_t maxLeafSize = 20);
142 std::vector<size_t>& oldFromNew,
143 std::vector<size_t>& newFromOld,
144 const size_t maxLeafSize = 20);
161 const size_t maxLeafSize = 20);
184 std::vector<size_t>& oldFromNew,
186 const size_t maxLeafSize = 20);
212 std::vector<size_t>& oldFromNew,
213 std::vector<size_t>& newFromOld,
215 const size_t maxLeafSize = 20);
306 typename BoundType::MetricType
Metric()
const {
return bound.Metric(); }
309 void Centroid(arma::vec& centroid) { bound.Centroid(centroid); }
374 size_t Point(
const size_t index)
const;
379 return bound.MinDistance(other->
Bound());
385 return bound.MaxDistance(other->
Bound());
391 return bound.RangeDistance(other->
Bound());
395 template<
typename VecType>
400 return bound.MinDistance(point);
404 template<
typename VecType>
409 return bound.MaxDistance(point);
413 template<
typename VecType>
418 return bound.RangeDistance(point);
464 const int maxLeafSize = 20) :
471 maxLeafSize(maxLeafSize) { }
492 void SplitNode(MatType& data, std::vector<size_t>& oldFromNew);
506 #include "binary_space_tree_impl.hpp"
double MinDistance(const BinarySpaceTree *other) const
Return the minimum distance to another node.
void SplitNode(MatType &data)
Splits the current node, assigning its left and right children recursively.
size_t NumChildren() const
Return the number of children in this node.
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
BinarySpaceTree * left
The left child node.
size_t TreeSize() const
Obtains the number of nodes in the tree, starting with this.
BinarySpaceTree *& Parent()
Modify the parent of this node.
std::string ToString() const
Returns a string representation of this object.
Linear algebra utility functions, generally performed on matrices or vectors.
size_t & Begin()
Modify the index of the beginning point of this subset.
double parentDistance
The distance from the centroid of this node to the centroid of the parent.
BinarySpaceTree * parent
The parent node (NULL if this is the root of the tree).
BinarySpaceTree * Left() const
Gets the left child of this node.
MatType & dataset
The dataset.
BinarySpaceTree *& Right()
Modify the right child of this node.
math::Range RangeDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum and maximum distance to another point.
size_t TreeDepth() const
Obtains the number of levels below this node in the tree, starting with this.
double minimumBoundDistance
The minimum distance from the center to any edge of the bound.
double furthestDescendantDistance
The worst possible distance to the furthest descendant, cached to speed things up.
BinarySpaceTree(const size_t begin, const size_t count, BoundType bound, StatisticType stat, const int maxLeafSize=20)
Private copy constructor, available only to fill (pad) the tree to a specified level.
BinarySpaceTree * CopyMe()
double MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the maximum distance to another point.
BoundType bound
The bound object for this node.
BinarySpaceTree & Child(const size_t child) const
Return the specified child (0 will be left, 1 will be right).
double FurthestDescendantDistance() const
Return the furthest possible descendant distance.
const BinarySpaceTree * FindByBeginCount(size_t begin, size_t count) const
Find a node in this tree by its begin and count (const).
size_t SplitDimension() const
Get the split dimension for this node.
const StatisticType & Stat() const
Return the statistic object for this node.
size_t splitDimension
The dimension this node split on if it is a parent.
~BinarySpaceTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn...
size_t Count() const
Return the number of points in this subset.
math::Range RangeDistance(const BinarySpaceTree *other) const
Return the minimum and maximum distance to another node.
size_t ExtendTree(const size_t level)
Fills the tree to the specified level.
size_t NumDescendants() const
Return the number of descendants of this node.
size_t begin
The index of the first point in the dataset contained in this node (and its children).
A binary space partitioning tree, such as a KD-tree or a ball tree.
BinarySpaceTree * right
The right child node.
size_t & MaxLeafSize()
Modify the max leaf size.
double MinDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum distance to another point.
MatType Mat
So other classes can use TreeType::Mat.
size_t Descendant(const size_t index) const
Return the index (with reference to the dataset) of a particular descendant of this node...
StatisticType & Stat()
Return the statistic object for this node.
A single-tree traverser for binary space trees; see single_tree_traverser.hpp for implementation...
size_t MaxLeafSize() const
Return the max leaf size.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
StatisticType stat
Any extra data contained in the node.
BinarySpaceTree *& Left()
Modify the left child of this node.
size_t maxLeafSize
The max leaf size.
BoundType & Bound()
Return the bound object for this node.
double & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
size_t NumPoints() const
Return the number of points in this node (0 if not a leaf).
size_t Begin() const
Return the index of the beginning point of this subset.
size_t count
The number of points of the dataset contained in this node (and its children).
size_t & SplitDimension()
Modify the split dimension for this node.
size_t & Count()
Modify the number of points in this subset.
double MaxDistance(const BinarySpaceTree *other) const
Return the maximum distance to another node.
double MinimumBoundDistance() const
Return the minimum distance from the center of the node to any bound edge.
A binary space partitioning tree node is split into its left and right child.
BinarySpaceTree * Right() const
Gets the right child of this node.
const MatType & Dataset() const
Get the dataset which the tree is built on.
static bool HasSelfChildren()
Returns false: this tree type does not have self children.
double ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
BinarySpaceTree(MatType &data, const size_t maxLeafSize=20)
Construct this as the root node of a binary space tree using the given dataset.
BinarySpaceTree * Parent() const
Gets the parent of this node.
size_t GetSplitDimension() const
Returns the dimension this parent's children are split on.
double FurthestPointDistance() const
Return the furthest distance to a point held in this node.
const BoundType & Bound() const
Return the bound object for this node.
size_t End() const
Gets the index one beyond the last index in the subset.
If value == true, then VecType is some sort of Armadillo vector or subview.
void Centroid(arma::vec ¢roid)
Get the centroid of the node and store it in the given vector.
BoundType::MetricType Metric() const
Get the metric which the tree uses.
Simple real-valued range.
A dual-tree traverser for binary space trees; see dual_tree_traverser.hpp.
Empty statistic if you are not interested in storing statistics in your tree.
MatType & Dataset()
Modify the dataset which the tree is built on. Be careful!