MLPACK  1.0.4
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 // Bad!
00029 #include <mlpack/methods/neighbor_search/neighbor_search_rules.hpp>
00030 
00031 namespace mlpack {
00032 namespace tree  {
00033 
00052 template<typename BoundType,
00053          typename StatisticType = EmptyStatistic,
00054          typename MatType = arma::mat>
00055 class BinarySpaceTree
00056 {
00057  private:
00059   BinarySpaceTree* left;
00061   BinarySpaceTree* right;
00064   size_t begin;
00067   size_t count;
00069   BoundType bound;
00071   StatisticType stat;
00073   size_t leafSize;
00075   size_t splitDimension;
00076 
00077  public:
00079   typedef MatType Mat;
00080 
00083   template<typename RuleType>
00084   class SingleTreeTraverser;
00085 
00087   template<typename RuleType>
00088   class DualTreeTraverser;
00089 
00097   BinarySpaceTree(MatType& data, const size_t leafSize = 20);
00098 
00109   BinarySpaceTree(MatType& data,
00110                   std::vector<size_t>& oldFromNew,
00111                   const size_t leafSize = 20);
00112 
00126   BinarySpaceTree(MatType& data,
00127                   std::vector<size_t>& oldFromNew,
00128                   std::vector<size_t>& newFromOld,
00129                   const size_t leafSize = 20);
00130 
00142   BinarySpaceTree(MatType& data,
00143                   const size_t begin,
00144                   const size_t count,
00145                   const size_t leafSize = 20);
00146 
00165   BinarySpaceTree(MatType& data,
00166                   const size_t begin,
00167                   const size_t count,
00168                   std::vector<size_t>& oldFromNew,
00169                   const size_t leafSize = 20);
00170 
00192   BinarySpaceTree(MatType& data,
00193                   const size_t begin,
00194                   const size_t count,
00195                   std::vector<size_t>& oldFromNew,
00196                   std::vector<size_t>& newFromOld,
00197                   const size_t leafSize = 20);
00198 
00202   BinarySpaceTree();
00203 
00209   ~BinarySpaceTree();
00210 
00222   const BinarySpaceTree* FindByBeginCount(size_t begin,
00223                                           size_t count) const;
00224 
00236   BinarySpaceTree* FindByBeginCount(size_t begin, size_t count);
00237 
00239   const BoundType& Bound() const;
00241   BoundType& Bound();
00242 
00244   const StatisticType& Stat() const;
00246   StatisticType& Stat();
00247 
00249   bool IsLeaf() const;
00250 
00252   size_t LeafSize() const;
00253 
00255   size_t ExtendTree(const size_t level);
00256 
00258   BinarySpaceTree* Left() const;
00259 
00261   BinarySpaceTree* Right() const;
00262 
00264   size_t NumChildren() const;
00265 
00273   double FurthestDescendantDistance() const;
00274 
00281   BinarySpaceTree& Child(const size_t child) const;
00282 
00284   size_t NumPoints() const;
00285 
00294   size_t Point(const size_t index) const;
00295 
00297   double MinDistance(const BinarySpaceTree* other) const
00298   {
00299     return bound.MinDistance(other->Bound());
00300   }
00301 
00303   double MaxDistance(const BinarySpaceTree* other) const
00304   {
00305     return bound.MaxDistance(other->Bound());
00306   }
00307 
00309   double MinDistance(const arma::vec& point) const
00310   {
00311     return bound.MinDistance(point);
00312   }
00313 
00315   double MaxDistance(const arma::vec& point) const
00316   {
00317     return bound.MaxDistance(point);
00318   }
00319 
00323   size_t GetSplitDimension() const;
00324 
00328   size_t TreeSize() const;
00329 
00334   size_t TreeDepth() const;
00335 
00339   size_t Begin() const;
00340 
00344   size_t End() const;
00345 
00349   size_t Count() const;
00350 
00352   static bool HasSelfChildren() { return false; }
00353 
00354  private:
00359   BinarySpaceTree(const size_t begin,
00360                   const size_t count,
00361                   BoundType bound,
00362                   StatisticType stat,
00363                   const int leafSize = 20) :
00364       left(NULL),
00365       right(NULL),
00366       begin(begin),
00367       count(count),
00368       bound(bound),
00369       stat(stat),
00370       leafSize(leafSize) { }
00371 
00372   BinarySpaceTree* CopyMe()
00373   {
00374     return new BinarySpaceTree(begin, count, bound, stat, leafSize);
00375   }
00376 
00382   void SplitNode(MatType& data);
00383 
00391   void SplitNode(MatType& data, std::vector<size_t>& oldFromNew);
00392 
00401   size_t GetSplitIndex(MatType& data, int splitDim, double splitVal);
00402 
00413   size_t GetSplitIndex(MatType& data, int splitDim, double splitVal,
00414       std::vector<size_t>& oldFromNew);
00415 };
00416 
00417 }; // namespace tree
00418 }; // namespace mlpack
00419 
00420 // Include implementation.
00421 #include "binary_space_tree_impl.hpp"
00422 
00423 #endif