11 #ifndef MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP 12 #define MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP 16 #include "../statistic.hpp" 47 template<
typename MetricType,
49 typename MatType = arma::mat,
50 template<
typename BoundMetricType,
typename...>
class BoundType =
52 template<
typename SplitBoundType,
typename SplitMatType>
62 typedef SplitType<BoundType<MetricType>, MatType>
Split;
78 BoundType<MetricType> bound;
95 template<
typename RuleType>
99 template<
typename RuleType>
102 template<
typename RuleType>
128 std::vector<size_t>& oldFromNew,
129 const size_t maxLeafSize = 20);
147 std::vector<size_t>& oldFromNew,
148 std::vector<size_t>& newFromOld,
149 const size_t maxLeafSize = 20);
161 const size_t maxLeafSize = 20);
176 std::vector<size_t>& oldFromNew,
177 const size_t maxLeafSize = 20);
195 std::vector<size_t>& oldFromNew,
196 std::vector<size_t>& newFromOld,
197 const size_t maxLeafSize = 20);
214 SplitType<BoundType<MetricType>, MatType>& splitter,
215 const size_t maxLeafSize = 20);
239 std::vector<size_t>& oldFromNew,
240 SplitType<BoundType<MetricType>, MatType>& splitter,
241 const size_t maxLeafSize = 20);
267 std::vector<size_t>& oldFromNew,
268 std::vector<size_t>& newFromOld,
269 SplitType<BoundType<MetricType>, MatType>& splitter,
270 const size_t maxLeafSize = 20);
291 template<
typename Archive>
294 const typename boost::enable_if<typename Archive::is_loading>::type* = 0);
304 const BoundType<MetricType>&
Bound()
const {
return bound; }
306 BoundType<MetricType>&
Bound() {
return bound; }
309 const StatisticType&
Stat()
const {
return stat; }
311 StatisticType&
Stat() {
return stat; }
332 const MatType&
Dataset()
const {
return *dataset; }
337 MetricType
Metric()
const {
return MetricType(); }
346 template<
typename VecType>
348 const VecType& point,
355 template<
typename VecType>
357 const VecType& point,
406 {
return (child == 0) ? left : right; }
435 size_t Point(
const size_t index)
const;
440 return bound.MinDistance(other.
Bound());
446 return bound.MaxDistance(other.
Bound());
452 return bound.RangeDistance(other.
Bound());
456 template<
typename VecType>
461 return bound.MinDistance(point);
465 template<
typename VecType>
470 return bound.MaxDistance(point);
474 template<
typename VecType>
479 return bound.RangeDistance(point);
483 size_t Begin()
const {
return begin; }
488 size_t Count()
const {
return count; }
493 void Center(arma::vec& center)
const { bound.Center(center); }
502 void SplitNode(
const size_t maxLeafSize,
503 SplitType<BoundType<MetricType>, MatType>& splitter);
513 void SplitNode(std::vector<size_t>& oldFromNew,
514 const size_t maxLeafSize,
515 SplitType<BoundType<MetricType>, MatType>& splitter);
523 template<
typename BoundType2>
524 void UpdateBound(BoundType2& boundToUpdate);
544 friend class boost::serialization::access;
550 template<
typename Archive>
551 void Serialize(Archive& ar,
const unsigned int version);
558 #include "binary_space_tree_impl.hpp" 561 #include "../binary_space_tree.hpp" ~BinarySpaceTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn...
const MatType & Dataset() const
Get the dataset which the tree is built on.
size_t NumPoints() const
Return the number of points in this node (0 if not a leaf).
BinarySpaceTree *& Left()
Modify the left child of this node.
ElemType MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the maximum distance to another point.
void Center(arma::vec ¢er) const
Store the center of the bounding region in the given vector.
size_t Descendant(const size_t index) const
Return the index (with reference to the dataset) of a particular descendant of this node...
A dual-tree traverser for binary space trees; see dual_tree_traverser.hpp.
size_t GetFurthestChild(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0)
Return the index of the furthest child node to the given query point.
Linear algebra utility functions, generally performed on matrices or vectors.
BinarySpaceTree * Right() const
Gets the right child of this node.
BinarySpaceTree *& ChildPtr(const size_t child)
void Serialize(Archive &ar, const unsigned int version)
Serialize the tree.
math::RangeType< ElemType > RangeDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum and maximum distance to another point.
BinarySpaceTree & Child(const size_t child) const
Return the specified child (0 will be left, 1 will be right).
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
The core includes that mlpack expects; standard C++ includes and Armadillo.
BinarySpaceTree * Parent() const
Gets the parent of this node.
MatType Mat
So other classes can use TreeType::Mat.
ElemType MaxDistance(const BinarySpaceTree &other) const
Return the maximum distance to another node.
BinarySpaceTree *& Parent()
Modify the parent of this node.
A binary space partitioning tree, such as a KD-tree or a ball tree.
A binary space partitioning tree node is split into its left and right child.
BinarySpaceTree()
A default constructor.
size_t NumDescendants() const
Return the number of descendants of this node.
BoundType< MetricType > & Bound()
Return the bound object for this node.
size_t NumChildren() const
Return the number of children in this node.
MetricType Metric() const
Get the metric that the tree uses.
BinarySpaceTree *& Right()
Modify the right child of this node.
Hyper-rectangle bound for an L-metric.
size_t & Begin()
Modify the index of the beginning point of this subset.
MatType::elem_type ElemType
The type of element held in MatType.
MatType & Dataset()
Modify the dataset which the tree is built on. Be careful!
const BoundType< MetricType > & Bound() const
Return the bound object for this node.
ElemType MinDistance(const BinarySpaceTree &other) const
Return the minimum distance to another node.
A single-tree traverser for binary space trees; see single_tree_traverser.hpp for implementation...
BinarySpaceTree * Left() const
Gets the left child of this node.
SplitType< BoundType< MetricType >, MatType > Split
ElemType ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
StatisticType & Stat()
Return the statistic object for 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.
size_t & Count()
Modify the number of points in this subset.
size_t Begin() const
Return the index of the beginning point of this subset.
ElemType MinimumBoundDistance() const
Return the minimum distance from the center of the node to any bound edge.
ElemType & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
ElemType MinDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum distance to another point.
const StatisticType & Stat() const
Return the statistic object for this node.
Hollow ball bound encloses a set of points at a specific distance (radius) from a specific point (cen...
math::RangeType< ElemType > RangeDistance(const BinarySpaceTree &other) const
Return the minimum and maximum distance to another node.
size_t GetNearestChild(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0)
Return the index of the nearest child node to the given query point.
If value == true, then VecType is some sort of Armadillo vector or subview.
ElemType FurthestPointDistance() const
Return the furthest distance to a point held in this node.
size_t Count() const
Return the number of points in this subset.
Empty statistic if you are not interested in storing statistics in your tree.
ElemType FurthestDescendantDistance() const
Return the furthest possible descendant distance.