MLPACK
1.0.4
|
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