binary_space_tree.hpp

Go to the documentation of this file.
00001 
00021 #ifndef __MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP
00022 #define __MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP
00023 
00024 #include <mlpack/core.hpp>
00025 
00026 #include "../statistic.hpp"
00027 
00028 namespace mlpack {
00029 namespace tree  {
00030 
00049 template<typename BoundType,
00050          typename StatisticType = EmptyStatistic,
00051          typename MatType = arma::mat>
00052 class BinarySpaceTree
00053 {
00054  private:
00056   BinarySpaceTree* left;
00058   BinarySpaceTree* right;
00060   BinarySpaceTree* parent;
00063   size_t begin;
00066   size_t count;
00068   size_t leafSize;
00070   BoundType bound;
00072   StatisticType stat;
00074   size_t splitDimension;
00076   double furthestDescendantDistance;
00078   MatType& dataset;
00079 
00080  public:
00082   typedef MatType Mat;
00083 
00086   template<typename RuleType>
00087   class SingleTreeTraverser;
00088 
00090   template<typename RuleType>
00091   class DualTreeTraverser;
00092 
00100   BinarySpaceTree(MatType& data, const size_t leafSize = 20);
00101 
00112   BinarySpaceTree(MatType& data,
00113                   std::vector<size_t>& oldFromNew,
00114                   const size_t leafSize = 20);
00115 
00129   BinarySpaceTree(MatType& data,
00130                   std::vector<size_t>& oldFromNew,
00131                   std::vector<size_t>& newFromOld,
00132                   const size_t leafSize = 20);
00133 
00145   BinarySpaceTree(MatType& data,
00146                   const size_t begin,
00147                   const size_t count,
00148                   BinarySpaceTree* parent = NULL,
00149                   const size_t leafSize = 20);
00150 
00169   BinarySpaceTree(MatType& data,
00170                   const size_t begin,
00171                   const size_t count,
00172                   std::vector<size_t>& oldFromNew,
00173                   BinarySpaceTree* parent = NULL,
00174                   const size_t leafSize = 20);
00175 
00197   BinarySpaceTree(MatType& data,
00198                   const size_t begin,
00199                   const size_t count,
00200                   std::vector<size_t>& oldFromNew,
00201                   std::vector<size_t>& newFromOld,
00202                   BinarySpaceTree* parent = NULL,
00203                   const size_t leafSize = 20);
00204 
00211   BinarySpaceTree(const BinarySpaceTree& other);
00212 
00218   ~BinarySpaceTree();
00219 
00231   const BinarySpaceTree* FindByBeginCount(size_t begin,
00232                                           size_t count) const;
00233 
00245   BinarySpaceTree* FindByBeginCount(size_t begin, size_t count);
00246 
00248   const BoundType& Bound() const { return bound; }
00250   BoundType& Bound() { return bound; }
00251 
00253   const StatisticType& Stat() const { return stat; }
00255   StatisticType& Stat() { return stat; }
00256 
00258   bool IsLeaf() const;
00259 
00261   size_t LeafSize() const { return leafSize; }
00263   size_t& LeafSize() { return leafSize; }
00264 
00266   size_t ExtendTree(const size_t level);
00267 
00269   BinarySpaceTree* Left() const { return left; }
00271   BinarySpaceTree*& Left() { return left; }
00272 
00274   BinarySpaceTree* Right() const { return right; }
00276   BinarySpaceTree*& Right() { return right; }
00277 
00279   BinarySpaceTree* Parent() const { return parent; }
00281   BinarySpaceTree*& Parent() { return parent; }
00282 
00284   size_t SplitDimension() const { return splitDimension; }
00286   size_t& SplitDimension() { return splitDimension; }
00287 
00289   const arma::mat& Dataset() const { return dataset; }
00291   arma::mat& Dataset() { return dataset; }
00292 
00294   typename BoundType::MetricType Metric() const { return bound.Metric(); }
00295 
00297   void Centroid(arma::vec& centroid) { bound.Centroid(centroid); }
00298 
00300   size_t NumChildren() const;
00301 
00306   double FurthestPointDistance() const;
00307 
00315   double FurthestDescendantDistance() const;
00316 
00323   BinarySpaceTree& Child(const size_t child) const;
00324 
00326   size_t NumPoints() const;
00327 
00333   size_t NumDescendants() const;
00334 
00342   size_t Descendant(const size_t index) const;
00343 
00352   size_t Point(const size_t index) const;
00353 
00355   double MinDistance(const BinarySpaceTree* other) const
00356   {
00357     return bound.MinDistance(other->Bound());
00358   }
00359 
00361   double MaxDistance(const BinarySpaceTree* other) const
00362   {
00363     return bound.MaxDistance(other->Bound());
00364   }
00365 
00367   math::Range RangeDistance(const BinarySpaceTree* other) const
00368   {
00369     return bound.RangeDistance(other->Bound());
00370   }
00371 
00373   double MinDistance(const arma::vec& point) const
00374   {
00375     return bound.MinDistance(point);
00376   }
00377 
00379   double MaxDistance(const arma::vec& point) const
00380   {
00381     return bound.MaxDistance(point);
00382   }
00383 
00385   math::Range RangeDistance(const arma::vec& point) const
00386   {
00387     return bound.RangeDistance(point);
00388   }
00389 
00393   size_t GetSplitDimension() const;
00394 
00398   size_t TreeSize() const;
00399 
00404   size_t TreeDepth() const;
00405 
00407   size_t Begin() const { return begin; }
00409   size_t& Begin() { return begin; }
00410 
00414   size_t End() const;
00415 
00417   size_t Count() const { return count; }
00419   size_t& Count() { return count; }
00420 
00422   static bool HasSelfChildren() { return false; }
00423 
00424  private:
00429   BinarySpaceTree(const size_t begin,
00430                   const size_t count,
00431                   BoundType bound,
00432                   StatisticType stat,
00433                   const int leafSize = 20) :
00434       left(NULL),
00435       right(NULL),
00436       begin(begin),
00437       count(count),
00438       bound(bound),
00439       stat(stat),
00440       leafSize(leafSize) { }
00441 
00442   BinarySpaceTree* CopyMe()
00443   {
00444     return new BinarySpaceTree(begin, count, bound, stat, leafSize);
00445   }
00446 
00452   void SplitNode(MatType& data);
00453 
00461   void SplitNode(MatType& data, std::vector<size_t>& oldFromNew);
00462 
00471   size_t GetSplitIndex(MatType& data, int splitDim, double splitVal);
00472 
00483   size_t GetSplitIndex(MatType& data, int splitDim, double splitVal,
00484       std::vector<size_t>& oldFromNew);
00485  public:
00489   std::string ToString() const;
00490 
00491 };
00492 
00493 }; // namespace tree
00494 }; // namespace mlpack
00495 
00496 // Include implementation.
00497 #include "binary_space_tree_impl.hpp"
00498 
00499 #endif

Generated on 13 Aug 2014 for MLPACK by  doxygen 1.6.1