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 };
00494 };
00495
00496
00497 #include "binary_space_tree_impl.hpp"
00498
00499 #endif