13 #ifndef MLPACK_CORE_TREE_RECTANGLE_TREE_RECTANGLE_TREE_HPP
14 #define MLPACK_CORE_TREE_RECTANGLE_TREE_RECTANGLE_TREE_HPP
18 #include "../hrectbound.hpp"
19 #include "../statistic.hpp"
48 typename StatisticType = EmptyStatistic,
49 typename MatType = arma::mat,
50 typename SplitType = RTreeSplit,
51 typename DescentType = RTreeDescentHeuristic,
52 template<
typename>
class AuxiliaryInformationType = NoAuxiliaryInformation>
56 static_assert(boost::is_same<MetricType, metric::EuclideanDistance>::value,
57 "RectangleTree: MetricType must be metric::EuclideanDistance.");
68 size_t maxNumChildren;
70 size_t minNumChildren;
74 std::vector<RectangleTree*> children;
86 size_t numDescendants;
98 const MatType* dataset;
103 std::vector<size_t> points;
105 AuxiliaryInformationType<RectangleTree> auxiliaryInfo;
110 template<
typename RuleType>
113 template<
typename RuleType>
131 const size_t maxLeafSize = 20,
132 const size_t minLeafSize = 8,
133 const size_t maxNumChildren = 5,
134 const size_t minNumChildren = 2,
135 const size_t firstDataIndex = 0);
152 const size_t maxLeafSize = 20,
153 const size_t minLeafSize = 8,
154 const size_t maxNumChildren = 5,
155 const size_t minNumChildren = 2,
156 const size_t firstDataIndex = 0);
167 const size_t numMaxChildren = 0);
177 const bool deepCopy =
true,
190 template<
typename Archive>
193 const typename boost::enable_if<typename Archive::is_loading>::type* = 0);
230 void InsertPoint(
const size_t point, std::vector<bool>& relevels);
245 std::vector<bool>& relevels);
264 bool DeletePoint(
const size_t point, std::vector<bool>& relevels);
304 const StatisticType&
Stat()
const {
return stat; }
306 StatisticType&
Stat() {
return stat; }
310 {
return auxiliaryInfo; }
313 {
return auxiliaryInfo; }
344 const MatType&
Dataset()
const {
return *dataset; }
346 MatType&
Dataset() {
return const_cast<MatType&
>(*dataset); }
349 MetricType
Metric()
const {
return MetricType(); }
363 template<
typename VecType>
365 const VecType& point,
372 template<
typename VecType>
374 const VecType& point,
423 return *children[child];
433 return *children[child];
464 size_t Point(
const size_t index)
const {
return points[index]; }
468 size_t&
Point(
const size_t index) {
return points[index]; }
489 template<
typename VecType>
498 template<
typename VecType>
507 template<
typename VecType>
509 const VecType& point,
527 size_t Begin()
const {
return begin; }
532 size_t Count()
const {
return count; }
542 void SplitNode(std::vector<bool>& relevels);
554 friend class boost::serialization::access;
578 std::vector<bool>& relevels,
579 const bool usePoint);
607 template<
typename Archive>
608 void Serialize(Archive& ar,
const unsigned int );
615 #include "rectangle_tree_impl.hpp"
size_t Begin() const
Return the index of the beginning point of this subset.
MatType Mat
So other classes can use TreeType::Mat.
size_t & Count()
Modify the number of points in this subset.
size_t NumChildren() const
Return the number of child nodes. (One level beneath this one only.)
math::RangeType< ElemType > RangeDistance(const RectangleTree &other) const
Return the minimum and maximum distance to another node.
ElemType FurthestDescendantDistance() const
Return the furthest possible descendant distance.
RectangleTree *& Parent()
Modify the parent of this node.
bool ShrinkBoundForPoint(const arma::vec &point)
Shrink the bound object of this node for the removal of a point.
ElemType MinimumBoundDistance() const
Return the minimum distance from the center to any edge of the bound.
ElemType & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
ElemType MinWidth() const
Get the minimum width of the bound.
size_t MinNumChildren() const
Return the minimum number of children (in a non-leaf node).
The core includes that mlpack expects; standard C++ includes and Armadillo.
const AuxiliaryInformationType< RectangleTree > & AuxiliaryInfo() const
Return the auxiliary information object of this node.
const bound::HRectBound< MetricType > & Bound() const
Return the bound object for this node.
ElemType FurthestPointDistance() const
Return the furthest distance to a point held in this node.
AuxiliaryInformationType< RectangleTree > AuxiliaryInformation
The auxiliary information type held by the tree.
size_t & MaxNumChildren()
Modify the maximum number of children (in a non-leaf node).
size_t MaxLeafSize() const
Return the maximum leaf size.
friend DescentType
Give friend access for DescentType.
size_t & Begin()
Modify the index of the beginning point of 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 MaxNumChildren() const
Return the maximum number of children (in a non-leaf 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.
void CondenseTree(const arma::vec &point, std::vector< bool > &relevels, const bool usePoint)
Condense the bounding rectangles for this node based on the removal of the point specified by the arm...
void Center(arma::Col< ElemType > ¢er) const
Calculates the center of the range, placing it into the given vector.
void SoftDelete()
Delete this node of the tree, but leave the stuff contained in it intact.
MetricType Metric() const
Get the metric which the tree uses.
size_t & MinLeafSize()
Modify the minimum leaf size.
size_t TreeDepth() const
Obtains the number of levels below this node in the tree, starting with this.
A rectangle type tree tree, such as an R-tree or X-tree.
size_t NumPoints() const
Return the number of points in this node (returns 0 if this node is not a leaf).
void Serialize(Archive &ar, const unsigned int)
Serialize the tree.
ElemType MinDistance(const RectangleTree &other) const
Return the minimum distance to another node.
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.
StatisticType & Stat()
Modify the statistic object for this node.
void InsertPoint(const size_t point)
Inserts a point into the tree.
size_t NumDescendants() const
Return the number of descendants of this node.
A dual tree traverser for rectangle type trees.
ElemType MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType >> *=0) const
Calculates maximum bound-to-point squared distance.
size_t Count() const
Return the number of points in this subset.
const StatisticType & Stat() const
Return the statistic object for this node.
~RectangleTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn...
size_t TreeSize() const
Obtains the number of nodes in the tree, starting with this.
bool RemoveNode(const RectangleTree *node, std::vector< bool > &relevels)
Removes a node from the tree.
size_t & MaxLeafSize()
Modify the maximum leaf size.
friend AuxiliaryInformation
Give friend access for AuxiliaryInformationType.
void NullifyData()
Nullify the auxiliary information.
bool DeletePoint(const size_t point)
Deletes a point from the treeand, updates the bounding rectangle.
void Center(arma::vec ¢er)
Get the centroid of the node and store it in the given vector.
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.
ElemType MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the maximum distance to another point.
MatType::elem_type ElemType
The element type held by the matrix type.
size_t & NumChildren()
Modify the number of child nodes. Be careful.
A single traverser for rectangle type trees.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
const RectangleTree * FindByBeginCount(size_t begin, size_t count) const
Find a node in this tree by its begin and count (const).
AuxiliaryInformationType< RectangleTree > & AuxiliaryInfo()
Modify the split object of this node.
ElemType ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
MatType & Dataset()
Modify the dataset which the tree is built on. Be careful!
void InsertNode(RectangleTree *node, const size_t level, std::vector< bool > &relevels)
Inserts a node into the tree, tracking which levels have been inserted into.
friend SplitType
Give friend access for SplitType.
size_t & Point(const size_t index)
Modify the index of a particular point in this node.
RectangleTree * Parent() const
Gets the parent of this node.
ElemType MinDistance(const VecType &point, typename boost::enable_if< IsVector< VecType >> *=0) const
Calculates minimum bound-to-point distance.
RectangleTree & Child(const size_t child)
Modify the specified child.
const MatType & Dataset() const
Get the dataset which the tree is built on.
ElemType MaxDistance(const RectangleTree &other) const
Return the maximum distance to another node.
LMetric< 2, true > EuclideanDistance
The Euclidean (L2) distance.
size_t & MinNumChildren()
Modify the minimum number of children (in a non-leaf node).
math::RangeType< ElemType > RangeDistance(const HRectBound &other) const
Calculates minimum and maximum bound-to-bound distance.
bound::HRectBound< MetricType > & Bound()
Modify the bound object for this node.
If value == true, then VecType is some sort of Armadillo vector or subview.
RectangleTree & Child(const size_t child) const
Get the specified child.
size_t MinLeafSize() const
Return the minimum leaf size.
ElemType MinDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum distance to another point.
bool ShrinkBoundForBound(const bound::HRectBound< MetricType > &changedBound)
Shrink the bound object of this node for the removal of a child node.
RectangleTree()
A default constructor.
RectangleTree * ExactClone()
Make an exact copy of this node, pointers and everything.