[mlpack-svn] r14061 - mlpack/trunk/src/mlpack/core/tree/binary_space_tree

[fastlab-svn at coffeetalk-1.cc.gatech.edu]

Author: rcurtin
Date: 2013-01-02 02:28:03 -0500 (Wed, 02 Jan 2013)
New Revision: 14061

Modified:
   mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
   mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp
Log:
Add parent and Parent() so that trees can be traveled both down and up.


Modified: mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp	2013-01-02 03:16:28 UTC (rev 14060)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp	2013-01-02 07:28:03 UTC (rev 14061)
@@ -44,6 +44,8 @@
   BinarySpaceTree* left;
   //! The right child node.
   BinarySpaceTree* right;
+  //! The parent node (NULL if this is the root of the tree).
+  BinarySpaceTree* parent;
   //! The index of the first point in the dataset contained in this node (and
   //! its children).
   size_t begin;
@@ -127,6 +129,7 @@
   BinarySpaceTree(MatType& data,
                   const size_t begin,
                   const size_t count,
+                  BinarySpaceTree* parent = NULL,
                   const size_t leafSize = 20);
 
   /**
@@ -151,6 +154,7 @@
                   const size_t begin,
                   const size_t count,
                   std::vector<size_t>& oldFromNew,
+                  BinarySpaceTree* parent = NULL,
                   const size_t leafSize = 20);
 
   /**
@@ -179,6 +183,7 @@
                   const size_t count,
                   std::vector<size_t>& oldFromNew,
                   std::vector<size_t>& newFromOld,
+                  BinarySpaceTree* parent = NULL,
                   const size_t leafSize = 20);
 
   /**
@@ -259,6 +264,11 @@
   //! Modify the right child of this node.
   BinarySpaceTree*& Right() { return right; }
 
+  //! Gets the parent of this node.
+  BinarySpaceTree* Parent() const { return parent; }
+  //! Modify the parent of this node.
+  BinarySpaceTree*& Parent() { return parent; }
+
   //! Get the split dimension for this node.
   size_t SplitDimension() const { return splitDimension; }
   //! Modify the split dimension for this node.

Modified: mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp	2013-01-02 03:16:28 UTC (rev 14060)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp	2013-01-02 07:28:03 UTC (rev 14061)
@@ -24,6 +24,7 @@
     const size_t leafSize) :
     left(NULL),
     right(NULL),
+    parent(NULL),
     begin(0), /* This root node starts at index 0, */
     count(data.n_cols), /* and spans all of the dataset. */
     bound(data.n_rows),
@@ -47,6 +48,7 @@
     const size_t leafSize) :
     left(NULL),
     right(NULL),
+    parent(NULL),
     begin(0),
     count(data.n_cols),
     bound(data.n_rows),
@@ -76,6 +78,7 @@
     const size_t leafSize) :
     left(NULL),
     right(NULL),
+    parent(NULL),
     begin(0),
     count(data.n_cols),
     bound(data.n_rows),
@@ -107,9 +110,11 @@
     MatType& data,
     const size_t begin,
     const size_t count,
+    BinarySpaceTree* parent,
     const size_t leafSize) :
     left(NULL),
     right(NULL),
+    parent(parent),
     begin(begin),
     count(count),
     bound(data.n_rows),
@@ -132,9 +137,11 @@
     const size_t begin,
     const size_t count,
     std::vector<size_t>& oldFromNew,
+    BinarySpaceTree* parent,
     const size_t leafSize) :
     left(NULL),
     right(NULL),
+    parent(parent),
     begin(begin),
     count(count),
     bound(data.n_rows),
@@ -162,9 +169,11 @@
     const size_t count,
     std::vector<size_t>& oldFromNew,
     std::vector<size_t>& newFromOld,
+    BinarySpaceTree* parent,
     const size_t leafSize) :
     left(NULL),
     right(NULL),
+    parent(parent),
     begin(begin),
     count(count),
     bound(data.n_rows),
@@ -194,6 +203,7 @@
 BinarySpaceTree<BoundType, StatisticType, MatType>::BinarySpaceTree() :
     left(NULL),
     right(NULL),
+    parent(NULL),
     begin(0),
     count(0),
     bound(),
@@ -212,6 +222,7 @@
     const BinarySpaceTree& other) :
     left(NULL),
     right(NULL),
+    parent(other.Parent()),
     begin(other.Begin()),
     count(other.Count()),
     bound(other.Bound()),
@@ -221,10 +232,16 @@
 {
   // Create left and right children (if any).
   if (other.Left())
+  {
     left = new BinarySpaceTree(*other.Left());
+    left->Parent() = this; // Set parent to this, not other tree.
+  }
 
   if (other.Right())
+  {
     right = new BinarySpaceTree(*other.Right());
+    right->Parent() = this; // Set parent to this, not other tree.
+  }
 }
 
 /**
@@ -478,9 +495,9 @@
   // Now that we know the split column, we will recursively split the children
   // by calling their constructors (which perform this splitting process).
   left = new BinarySpaceTree<BoundType, StatisticType, MatType>(data, begin,
-      splitCol - begin, leafSize);
+      splitCol - begin, this, leafSize);
   right = new BinarySpaceTree<BoundType, StatisticType, MatType>(data, splitCol,
-      begin + count - splitCol, leafSize);
+      begin + count - splitCol, this, leafSize);
 }
 
 template<typename BoundType, typename StatisticType, typename MatType>
@@ -528,9 +545,9 @@
   // Now that we know the split column, we will recursively split the children
   // by calling their constructors (which perform this splitting process).
   left = new BinarySpaceTree<BoundType, StatisticType, MatType>(data, begin,
-      splitCol - begin, oldFromNew, leafSize);
+      splitCol - begin, oldFromNew, this, leafSize);
   right = new BinarySpaceTree<BoundType, StatisticType, MatType>(data, splitCol,
-      begin + count - splitCol, oldFromNew, leafSize);
+      begin + count - splitCol, oldFromNew, this, leafSize);
 }
 
 template<typename BoundType, typename StatisticType, typename MatType>