15 #ifndef __MLPACK_CORE_TREE_RECTANGLE_TREE_RECTANGLE_TREE_HPP 16 #define __MLPACK_CORE_TREE_RECTANGLE_TREE_RECTANGLE_TREE_HPP 20 #include "../hrectbound.hpp" 21 #include "../statistic.hpp" 46 typename StatisticType = EmptyStatistic,
47 typename MatType = arma::mat,
48 typename SplitType = RTreeSplit,
49 typename DescentType = RTreeDescentHeuristic>
53 static_assert(boost::is_same<MetricType, metric::EuclideanDistance>::value,
54 "RectangleTree: MetricType must be metric::EuclideanDistance.");
68 for (
int i = 0; i < dim; i++)
72 template<
typename Archive>
127 template<
typename RuleType>
130 template<
typename RuleType>
148 const size_t maxLeafSize = 20,
149 const size_t minLeafSize = 8,
150 const size_t maxNumChildren = 5,
151 const size_t minNumChildren = 2,
152 const size_t firstDataIndex = 0);
169 const size_t maxLeafSize = 20,
170 const size_t minLeafSize = 8,
171 const size_t maxNumChildren = 5,
172 const size_t minNumChildren = 2,
173 const size_t firstDataIndex = 0);
196 template<
typename Archive>
199 const typename boost::enable_if<typename Archive::is_loading>::type* = 0);
239 void InsertPoint(
const size_t point, std::vector<bool>& relevels);
254 std::vector<bool>& relevels);
275 bool DeletePoint(
const size_t point, std::vector<bool>& relevels);
355 MatType&
Dataset() {
return const_cast<MatType&
>(*dataset); }
368 MetricType
Metric()
const {
return MetricType(); }
417 return *children[child];
427 return *children[child];
458 size_t Point(
const size_t index)
const;
479 template<
typename VecType>
488 template<
typename VecType>
497 template<
typename VecType>
499 const VecType& point,
538 const int maxLeafSize = 20) :
543 maxLeafSize(maxLeafSize) { }
547 return new RectangleTree(begin, count, bound, stat, maxLeafSize);
555 void SplitNode(std::vector<bool>& relevels);
567 friend class boost::serialization::access;
582 std::vector<bool>& relevels,
583 const bool usePoint);
611 template<
typename Archive>
612 void Serialize(Archive& ar,
const unsigned int );
619 #include "rectangle_tree_impl.hpp" RectangleTree * Parent() const
Gets the parent of this node.
SplitHistoryStruct splitHistory
A struct to store the "split history" for X trees.
double parentDistance
The distance from the centroid of this node to the centroid of the parent.
size_t MaxLeafSize() const
Return the maximum leaf size.
RectangleTree * ExactClone()
Make an exact copy of this node, pointers and everything.
size_t & Begin()
Modify the index of the beginning point of this subset.
~RectangleTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn...
double MinimumBoundDistance() const
Return the minimum distance from the center to any edge of the bound.
Linear algebra utility functions, generally performed on matrices or vectors.
FirstShim< T > CreateNVP(T &t, const std::string &name, typename boost::enable_if< HasSerialize< T >>::type *=0)
Call this function to produce a name-value pair; this is similar to BOOST_SERIALIZATION_NVP(), but should be used for types that have a Serialize() function (or contain a type that has a Serialize() function) instead of a serialize() function.
size_t & MinLeafSize()
Modify the minimum leaf size.
size_t MinNumChildren() const
Return the minimum number of children (in a non-leaf node).
size_t & MaxLeafSize()
Modify the maximum leaf size.
MetricType Metric() const
Get the metric which the tree uses.
LMetric< 2, true > EuclideanDistance
The Euclidean (L2) distance.
const MatType * dataset
The dataset.
RectangleTree * parent
The parent node (NULL if this is the root of the tree).
RectangleTree(const size_t begin, const size_t count, bound::HRectBound< MetricType > bound, StatisticType stat, const int maxLeafSize=20)
Private copy constructor, available only to fill (pad) the tree to a specified level.
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...
size_t TreeSize() const
Obtains the number of nodes in the tree, starting with this.
void SplitNode(std::vector< bool > &relevels)
Splits the current node, recursing up the tree.
bool DeletePoint(const size_t point)
Deletes a point in the tree.
SplitHistoryStruct & SplitHistory()
Modify the split history object of this node.
RectangleTree()
A default constructor.
size_t Descendant(const size_t index) const
Return the index (with reference to the dataset) of a particular descendant of this node...
math::Range RangeDistance(const HRectBound &other) const
Calculates minimum and maximum bound-to-bound distance.
size_t maxNumChildren
The max number of child nodes a non-leaf node can have.
double ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
std::vector< size_t > points
The mapping to the dataset.
const bound::HRectBound< MetricType > & Bound() const
Return the bound object for this node.
double FurthestDescendantDistance() const
Return the furthest possible descendant distance.
double MinWidth() const
Get the minimum width of the bound.
void InsertPoint(const size_t point)
Inserts a point into the tree.
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.
The X tree requires that the tree records it's "split history".
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
const SplitHistoryStruct & SplitHistory() const
Return the split history object of this node.
MatType * localDataset
The local dataset.
double MinDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum distance to another point.
double & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
RectangleTree *& Parent()
Modify the parent of this node.
bool ownsDataset
Whether or not we are responsible for deleting the dataset.
double MinDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > > *=0) const
Calculates minimum bound-to-point distance.
Hyper-rectangle bound for an L-metric.
size_t minNumChildren
The minimum number of child nodes a non-leaf node can have.
RectangleTree & Child(const size_t child) const
Get the specified child.
size_t & NumChildren()
Modify the number of child nodes. Be careful.
const MatType & Dataset() const
Get the dataset which the tree is built on.
const std::vector< size_t > & Points() const
Get the points vector for this node.
size_t count
The number of points in the dataset contained in this node (and its children).
std::vector< size_t > & Points()
Modify the points vector for this node. Be careful!
math::Range RangeDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum and maximum distance to another point.
bool ShrinkBoundForPoint(const arma::vec &point)
Shrink the bound object of this node for the removal of a point.
const std::vector< RectangleTree * > & Children() const
Get the children of this node.
size_t & MinNumChildren()
Modify the minimum number of children (in a non-leaf node).
Simple real-valued range.
double MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > > *=0) const
Calculates maximum bound-to-point squared distance.
bool RemoveNode(const RectangleTree *node, std::vector< bool > &relevels)
Removes a node from the tree.
size_t minLeafSize
The minimum leaf size.
A rectangle type tree tree, such as an R-tree or X-tree.
MatType Mat
So other classes can use TreeType::Mat.
const StatisticType & Stat() const
Return the statistic object for this node.
double FurthestPointDistance() const
Return the furthest distance to a point held in this node.
Include all of the base components required to write MLPACK methods, and the main MLPACK Doxygen docu...
size_t & MaxNumChildren()
Modify the maximum number of children (in a non-leaf node).
size_t TreeDepth() const
Obtains the number of levels below this node in the tree, starting with this.
RectangleTree & Child(const size_t child)
Modify the specified child.
size_t NumPoints() const
Return the number of points in this node (returns 0 if this node is not a leaf).
StatisticType & Stat()
Modify the statistic object for this node.
const RectangleTree * FindByBeginCount(size_t begin, size_t count) const
Find a node in this tree by its begin and count (const).
A dual tree traverser for rectangle type trees.
size_t & Count()
Modify the number of points in this subset.
math::Range RangeDistance(const RectangleTree *other) const
Return the minimum and maximum distance to another node.
void Center(arma::vec ¢er)
Get the centroid of the node and store it in the given vector.
size_t begin
The index of the first point in the dataset contained in this node (and its children).
void SoftDelete()
Delete this node of the tree, but leave the stuff contained in it intact.
void Serialize(Archive &ar, const unsigned int)
size_t NumChildren() const
Return the number of child nodes. (One level beneath this one only.)
size_t maxLeafSize
The max leaf size.
MatType & Dataset()
Modify the dataset which the tree is built on. Be careful!
std::vector< RectangleTree * > children
The child nodes (Starting at 0 and ending at (numChildren-1) ).
size_t Begin() const
Return the index of the beginning point of this subset.
const MatType & LocalDataset() const
Get the local dataset of this node.
bound::HRectBound< metric::EuclideanDistance > bound
The bound object for this node.
double MaxDistance(const RectangleTree *other) const
Return the maximum distance to another node.
void Center(arma::vec ¢er) const
Calculates the center of the range, placing it into the given vector.
A single traverser for rectangle type trees.
double MinDistance(const RectangleTree *other) const
Return the minimum distance to another node.
void NullifyData()
Set dataset to null.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
MatType & LocalDataset()
Modify the local dataset of this node.
size_t MinLeafSize() const
Return the minimum leaf size.
double MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the maximum distance to another point.
size_t Count() const
Return the number of points in this subset.
bool ShrinkBoundForBound(const bound::HRectBound< MetricType > &changedBound)
Shrink the bound object of this node for the removal of a child node.
size_t NumDescendants() const
Return the number of descendants of this node.
std::vector< bool > history
static bool HasSelfChildren()
Returns false: this tree type does not have self children.
std::vector< RectangleTree * > & Children()
Modify the children of this node.
bound::HRectBound< MetricType > & Bound()
Modify the bound object for this node.
If value == true, then VecType is some sort of Armadillo vector or subview.
StatisticType stat
Any extra data contained in the node.
size_t numChildren
The number of child nodes actually in use (0 if this is a leaf node).
SplitHistoryStruct(int dim)
size_t MaxNumChildren() const
Return the maximum number of children (in a non-leaf node).