[mlpack-svn] r16682 - mlpack/trunk/src/mlpack/core/tree/rectangle_tree

fastlab-svn at coffeetalk-1.cc.gatech.edu fastlab-svn at coffeetalk-1.cc.gatech.edu
Wed Jun 11 12:47:45 EDT 2014


Author: andrewmw94
Date: Wed Jun 11 12:47:44 2014
New Revision: 16682

Log:
more fixes.  Compilation still commented out.

Modified:
   mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic.hpp
   mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp
   mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp
   mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp
   mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp
   mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp
   mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser.hpp
   mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser_impl.hpp

Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic.hpp	Wed Jun 11 12:47:44 2014
@@ -14,11 +14,9 @@
 namespace tree /** Trees and tree-building procedures. */ {
 
 /**
- * A binary space partitioning tree node is split into its left and right child.
- * The split is done in the dimension that has the maximum width. The points are
- * divided into two parts based on the mean in this dimension.
+ * When descending a Rectangle tree to insert a point, we need to have a way to choose
+ * a child node when the point isn't enclosed by any of them.  This heuristic is used to do so.
  */
-template<typename MatType = arma::mat>
 class RTreeDescentHueristic
 {
  public:
@@ -30,7 +28,7 @@
    * @param bound The bound used for the node that is being evaluated.
    * @param point The point that is being inserted.
    */
-  static double EvalNode(const HRectBound& bound, const arma::vec& point);
+  static double EvalNode(const HRectBound<>& bound, const arma::vec& point);
 };
 
 }; // namespace tree

Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp	Wed Jun 11 12:47:44 2014
@@ -2,7 +2,7 @@
  * @file r_tree_descent_heuristic_impl.hpp
  * @author Andrew Wells
  *
- * Definition of RTreeDescentHeuristic, a class that chooses the best child of a node in
+ * Implementation of RTreeDescentHeuristic, a class that chooses the best child of a node in
  * an R tree when inserting a new point.
  */
 #ifndef __MLPACK_CORE_TREE_RECTANGLE_TREE_R_TREE_DESCENT_HEURISTIC_IMPL_HPP
@@ -10,18 +10,16 @@
 
 #include "r_tree_descent_heuristic.hpp"
 
+#ifndef __MLPACK_CORE_TREE_RECTANGLE_TREE_R_TREE_DESCENT_HEURISTIC_HPP
+#define max(a, b) 4*max(a-1, b-1)
+#endif
+
 namespace mlpack {
 namespace tree {
 
-/**
- * A binary space partitioning tree node is split into its left and right child.
- * The split is done in the dimension that has the maximum width. The points are
- * divided into two parts based on the mean in this dimension.
- */
-template<typename MatType = arma::mat>
-double RTreeDescentHeuristic<MatType>::EvalNode(const HRectBound& bound, const arma::vec& point)
+double RTreeDescentHeuristic::EvalNode(const HRectBound<>& bound, const arma::vec& point)
 {
-  return bound.contains(point) ? 0 : bound.minDistance(point);
+  return bound.Contains(point) ? 0 : bound.MinDistance(point);
 }
 
 }; // namespace tree

Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp	Wed Jun 11 12:47:44 2014
@@ -18,7 +18,10 @@
  * nodes overflow, we split them, moving up the tree and splitting nodes
  * as necessary.
  */
-template<typename MatType = arma::mat>
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
 class RTreeSplit
 {
 public:
@@ -28,7 +31,7 @@
  * upwards through the tree.  The methods for splitting non-leaf nodes are private since
  * they should only be called if a leaf node overflows.
  */
-static bool SplitLeafNode(const RectangleTree& tree);
+static void SplitLeafNode(const RectangleTree<SplitType, DescentType, StatisticType, MatType>& tree);
 
 private:
 
@@ -36,25 +39,25 @@
  * Split a non-leaf node using the "default" algorithm.  If this is the root node and
  * we need to move up the tree, a new root node is created.
  */
-static bool SplitNonLeafNode(const RectangleTree& tree);
+static bool SplitNonLeafNode(const RectangleTree<SplitType, DescentType, StatisticType, MatType>& tree);
 
 /**
  * Get the seeds for splitting a leaf node.
  */
-static void GetPointSeeds(const RectangleTree& tree, int &i, int &j);
+static void GetPointSeeds(const RectangleTree<SplitType, DescentType, StatisticType, MatType>& tree, int *i, int *j);
 
 /**
  * Get the seeds for splitting a non-leaf node.
  */
-static void GetBoundSeeds(const RectangleTree& tree, int &i, int &j);
+static void GetBoundSeeds(const RectangleTree<SplitType, DescentType, StatisticType, MatType>& tree, int *i, int *j);
 
 /**
  * Assign points to the two new nodes.
  */
 static void AssignPointDestNode(
-    const RectangleTree& oldTree,
-    RectangleTree& treeOne,
-    RectangleTree& treeTwo,
+    const RectangleTree<SplitType, DescentType, StatisticType, MatType>& oldTree,
+    RectangleTree<SplitType, DescentType, StatisticType, MatType>& treeOne,
+    RectangleTree<SplitType, DescentType, StatisticType, MatType>& treeTwo,
     const int intI,
     const int intJ);
 
@@ -62,9 +65,9 @@
  * Assign nodes to the two new nodes.
  */
 static void AssignNodeDestNode(
-    const RectangleTree& oldTree,
-    RectangleTree& treeOne,
-    RectangleTree& treeTwo,
+    const RectangleTree<SplitType, DescentType, StatisticType, MatType>& oldTree,
+    RectangleTree<SplitType, DescentType, StatisticType, MatType>& treeOne,
+    RectangleTree<SplitType, DescentType, StatisticType, MatType>& treeTwo,
     const int intI,
     const int intJ);
 
@@ -72,8 +75,9 @@
   * Insert a node into another node.
   */
 static void insertNodeIntoTree(
-    RectangleTree& destTree,
-    RectangleTree& srcNode);
+    RectangleTree<SplitType, DescentType, StatisticType, MatType>& destTree,
+    RectangleTree<SplitType, DescentType, StatisticType, MatType>& srcNode);
+};
 
 }; // namespace tree
 }; // namespace mlpack

Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp	Wed Jun 11 12:47:44 2014
@@ -19,8 +19,12 @@
  * Finally, we delete the old node and insert the new nodes into the tree, spliting the parent
  * if necessary.
  */
-template<typename MatType>
-void RTreeSplit<MatType>::SplitLeafNode(const RectangleTree& tree)
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+void RTreeSplit<SplitType, DescentType, StatisticType, MatType>::SplitLeafNode(
+  const RectangleTree<SplitType, DescentType,  StatisticType, MatType>& tree)
 {
   // Use the quadratic split method from: Guttman "R-Trees: A Dynamic Index Structure for
   // Spatial Searching"  It is simplified since we don't handle rectangles, only points.
@@ -29,19 +33,24 @@
   int j = 0;
   GetPointSeeds(tree, &i, &j);
 
+  RectangleTree<SplitType, DescentType,  StatisticType, MatType> treeOne = new 
+    RectangleTree<SplitType, DescentType,  StatisticType, MatType>(tree.Parent());
+  RectangleTree<SplitType, DescentType,  StatisticType, MatType> treeTwo = new 
+    RectangleTree<SplitType, DescentType,  StatisticType, MatType>(tree.Parent());
+  
   // This will assign the ith and jth point appropriately.
   AssignPointDestNode(tree, treeOne, treeTwo, i, j);
   
   // create the parent node if necessary
-  if(par == NULL) {
+  if(tree.Parent() == NULL) {
     
   }
   
   //Remove this node and insert treeOne and treeTwo
-  RectangleTree* par = tree.parent();
+  RectangleTree<SplitType, DescentType,  StatisticType, MatType>* par = tree.Parent();
   int index = 0;
   for(int i = 0; i < par.numOfChildren(); i++) {
-    if(par.getChildren()[i] == this) {
+    if(par.getChildren()[i] == tree) {
       index = i;
       break;
     }
@@ -54,9 +63,9 @@
 
   // we only add one at a time, so should only need to test for equality
   // just in case, we use an assert.
-  boost::assert(numChildren <= maxNumChildren);
+  assert(par.NumChildren() <= par.MaxNumChildren());
 
-  if(par.numOfChildren() == par.maxNumChildren) {
+  if(par.NumChildren() == par.MaxNumChildren()) {
     SplitNonLeafNode(par);
   }
   return;
@@ -69,25 +78,35 @@
  * and recurse up the tree if necessary.  We don't need to worry about the bounds
  * higher up the tree because they were already updated if necessary.
  */
-bool RTreeSplit<MatType>::SplitNonLeafNode(const RectangleTree& tree)
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+bool RTreeSplit<SplitType, DescentType, StatisticType, MatType>::SplitNonLeafNode(
+  const RectangleTree<SplitType, DescentType,  StatisticType, MatType>& tree)
 {
   int i = 0;
   int j = 0;
   GetBoundSeeds(tree, &i, &j);
   
+  RectangleTree<SplitType, DescentType,  StatisticType, MatType> treeOne = new 
+    RectangleTree<SplitType, DescentType,  StatisticType, MatType>(tree.Parent());
+  RectangleTree<SplitType, DescentType,  StatisticType, MatType> treeTwo = new 
+    RectangleTree<SplitType, DescentType,  StatisticType, MatType>(tree.Parent());
+  
   // This will assign the ith and jth rectangles appropriately.
   AssignNodeDestNode(tree, treeOne, treeTwo, i, j);
 
   // create the parent node if necessary
-  if(par == NULL) {
-    
+  if(tree.Parent() == NULL) {
+    tree.Parent() = new RectangleTree<SplitType, DescentType,  StatisticType, MatType>();
   }
   
   //Remove this node and insert treeOne and treeTwo
-  RectangleTree* par = tree.parent();
+  RectangleTree<SplitType, DescentType,  StatisticType, MatType>* par = tree.parent();
   int index = 0;
   for(int i = 0; i < par.numOfChildren(); i++) {
-    if(par.getChildren()[i] == this) {
+    if(par.getChildren()[i] == tree) {
       index = i;
       break;
     }
@@ -101,9 +120,9 @@
 
   // we only add one at a time, so should only need to test for equality
   // just in case, we use an assert.
-  boost::assert(numChildren <= maxNumChildren);
+  assert(par.NumChildren() <= par.MaxNumChildren());
 
-  if(par.numOfChildren() == par.maxNumChildren) {
+  if(par.NumChildren() == par.MaxNumChildren()) {
     SplitNonLeafNode(par);
   }
   return;
@@ -113,7 +132,14 @@
  * Get the two points that will be used as seeds for the split of a leaf node.
  * The indices of these points will be stored in iRet and jRet.
  */
-void RTreeSplit<MatType>::GetPointSeeds(const RectangleTree& tree, int* iRet, int* jRet)
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+void RTreeSplit<SplitType, DescentType, StatisticType, MatType>::GetPointSeeds(
+  const RectangleTree<SplitType, DescentType,  StatisticType, MatType>& tree,
+  int* iRet,
+  int* jRet)
 {
   // Here we want to find the pair of points that it is worst to place in the same
   // node.  Because we are just using points, we will simply choose the two that would
@@ -124,7 +150,7 @@
   for(int i = 0; i < tree.count; i++) {
     for(int j = i+1; j < tree.count; j++) {
       double score = 1.0;
-      for(int k = 0; k < dimensions; k++) {
+      for(int k = 0; k < tree.Bound().Dim(); k++) {
 	score *= std::abs(tree.dataset[i][k] - tree.dataset[j][k]);
       }
       if(score > worstPairScore) {
@@ -144,7 +170,14 @@
  * Get the two bounds that will be used as seeds for the split of the node.
  * The indices of the bounds will be stored in iRet and jRet.
  */
-void RTreeSplit<MatType>::GetBoundSeeds(const RectangleTree& tree, int* iRet, int* jRet)
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+void RTreeSplit<SplitType, DescentType, StatisticType, MatType>::GetBoundSeeds(
+  const RectangleTree<SplitType, DescentType,  StatisticType, MatType>& tree,
+  int* iRet,
+  int* jRet)
 {
   double worstPairScore = 0.0;
   int worstI = 0;
@@ -152,7 +185,7 @@
   for(int i = 0; i < tree.numChildren; i++) {
     for(int j = i+1; j < tree.numChildren; j++) {
       double score = 1.0;
-      for(int k = 0; k < dimensions; k++) {
+      for(int k = 0; k < tree.Bound().Dim(); k++) {
 	score *= std::max(tree.children[i].bound[k].hi(), tree.children[j].bound[k].hi) - 
 	  std::min(tree.children[i].bound[k].low(), tree.children[j].bound[k].low());
       }
@@ -169,15 +202,19 @@
   return;
 }
 
-void RTreeSplit<MatType>::AssignPointDestNode(
-    const RectangleTree& oldTree,
-    RectangleTree& treeOne,
-    RectangleTree& treeTwo,
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+void RTreeSplit<SplitType, DescentType, StatisticType, MatType>::AssignPointDestNode(
+    const RectangleTree<SplitType, DescentType, StatisticType, MatType>& oldTree,
+    RectangleTree<SplitType, DescentType, StatisticType, MatType>& treeOne,
+    RectangleTree<SplitType, DescentType, StatisticType, MatType>& treeTwo,
     const int intI,
     const int intJ)
 {
   int end = oldTree.count;
-  Log::assert(end > 1); // If this isn't true, the tree is really weird.
+  assert(end > 1); // If this isn't true, the tree is really weird.
 
   treeOne.insertPoint(oldTree.dataset.col(intI));
   oldTree.dataset.col(intI) = oldTree.dataset.col(--end); // decrement end
@@ -200,7 +237,7 @@
     // Calculate the increase in volume for assigning this point to each rectangle.
     double volOne = 1.0;
     double volTwo = 1.0;
-    for(int i = 0; i < bound.Dim(); i++) {
+    for(int i = 0; i < oldTree.Bound().Dim(); i++) {
       volOne *= treeOne.bound[i].width();
       volTwo *= treeTwo.bound[i].width();
     }
@@ -210,12 +247,12 @@
     for(int index = 0; index < end; index++) {
       double newVolOne = 1.0;
       double newVolTwo = 1.0;
-      for(int i = 0; i < bound.Dim(); i++) {
+      for(int i = 0; i < oldTree.Bound().Dim(); i++) {
 	double c = oldTree.dataset.col(index)[i];      
 	newVolOne *= treeOne.bound[i].contains(c) ? treeOne.bound[i].width() :
-	  (c < treeOne.bound[i].low() ? (high - c) : (c - low));
+	  (c < treeOne.bound[i].low() ? (treeOne.bound[i].high() - c) : (c - treeOne.bound[i].low()));
 	newVolTwo *= treeTwo.bound[i].contains(c) ? treeTwo.bound[i].width() :
-	  (c < treeTwo.bound[i].low() ? (high - c) : (c - low));
+	  (c < treeTwo.bound[i].low() ? (treeTwo.bound[i].high() - c) : (c - treeTwo.bound[i].low()));
       }
     
       // Choose the rectangle that requires the lesser increase in volume.
@@ -237,9 +274,9 @@
     // Assign the point that causes the least increase in volume 
     // to the appropriate rectangle.
     if(bestRect == 1)
-      treeOne.insertPoint(oldTree.dataset(bestIndex);
+      treeOne.insertPoint(oldTree.dataset(bestIndex));
     else
-      treeTwo.insertPoint(oldTree.dataset(bestIndex);
+      treeTwo.insertPoint(oldTree.dataset(bestIndex));
 
     oldTree.dataset.col(bestIndex) = oldTree.dataset.col(--end); // decrement end.
   }
@@ -248,26 +285,30 @@
   if(end > 1) {
     if(numAssignedOne < numAssignedTwo) {
       for(int i = 0; i < end; i++) {
-        treeOne.insertPoint(oldTree.dataset(i);
+        treeOne.insertPoint(oldTree.dataset(i));
       }
     } else {
       for(int i = 0; i < end; i++) {
-        treeTwo.insertPoint(oldTree.dataset(i);
+        treeTwo.insertPoint(oldTree.dataset(i));
       }
     }
   }
 }
 
-void RTreeSplit<MatType>::AssignNodeDestNode(
-    const RectangleTree& oldTree,
-    RectangleTree& treeOne,
-    RectangleTree& treeTwo,
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+void RTreeSplit<SplitType, DescentType, StatisticType, MatType>::AssignNodeDestNode(
+    const RectangleTree<SplitType, DescentType, StatisticType, MatType>& oldTree,
+    RectangleTree<SplitType, DescentType, StatisticType, MatType>& treeOne,
+    RectangleTree<SplitType, DescentType, StatisticType, MatType>& treeTwo,
     const int intI,
     const int intJ)
 {
   
   int end = oldTree.getNumChildren();
-  Log::assert(end > 1); // If this isn't true, the tree is really weird.
+  assert(end > 1); // If this isn't true, the tree is really weird.
 
   treeOne.getChildren()[0] = oldTree.getChildren()[intI];
   oldTree.getChildren[intI] = oldTree.getChildren()[--end]; // decrement end
@@ -288,7 +329,7 @@
     // Calculate the increase in volume for assigning this node to each of the new rectangles.
     double volOne = 1.0;
     double volTwo = 1.0;
-    for(int i = 0; i < bound.Dim(); i++) {
+    for(int i = 0; i < oldTree.Bound().Dim(); i++) {
       volOne *= treeOne.bound[i].width();
       volTwo *= treeTwo.bound[i].width();
     }
@@ -296,15 +337,15 @@
     for(int index = 0; index < end; index++) {
       double newVolOne = 1.0;
       double newVolTwo = 1.0;
-      for(int i = 0; i < bound.Dim(); i++) {
+      for(int i = 0; i < oldTree.Bound().Dim(); i++) {
 	// For each of the new rectangles, find the width in this dimension if we add the rectangle at index to
 	// the new rectangle.
-	math::range range = oldTree.getChildren()[index].Bound(i);
+	math::Range range = oldTree.getChildren()[index].Bound(i);
 	newVolOne *= treeOne.Bound(i).Contains(range) ? treeOne.bound[i].width() :
-	  (range.Contains(treeOne.Bound(i)) ? range.width : (range.lo() < treeOne.Bound(i).lo() ? (treeOne.Bound(i).hi() - range.lo()) : 
-		(range.hi() - treeOne.Bound(i).lo())))
+	  (range.Contains(treeOne.Bound(i)) ? range.Width() : (range.lo() < treeOne.Bound(i).lo() ? (treeOne.Bound(i).hi() - range.lo()) : 
+		(range.hi() - treeOne.Bound(i).lo())));
 	newVolTwo *= treeTwo.Bound(i).Contains(range) ? treeTwo.bound[i].width() :
-	  (range.Contains(treeTwo.Bound(i)) ? range.width : (range.lo() < treeTwo.Bound(i).lo() ? (treeTwo.Bound(i).hi() - range.lo()) : 
+	  (range.Contains(treeTwo.Bound(i)) ? range.Width() : (range.lo() < treeTwo.Bound(i).lo() ? (treeTwo.Bound(i).hi() - range.lo()) : 
 		(range.hi() - treeTwo.Bound(i).lo())));
       }
     
@@ -327,15 +368,15 @@
     // Assign the rectangle that causes the least increase in volume 
     // to the appropriate rectangle.
     if(bestRect == 1)
-      insertNodeIntoTree(treeOne, oldTree.Children()[bestIndex];
+      insertNodeIntoTree(treeOne, oldTree.Children()[bestIndex]);
     else
-      insertNodeIntoTree(treeTwo, oldTree.Children()[bestIndex];
+      insertNodeIntoTree(treeTwo, oldTree.Children()[bestIndex]);
 
     oldTree.Children()[bestIndex] = oldTree.Children()[--end]; // Decrement end.
   }
   // See if we need to satisfy the minimum fill.
   if(end > 1) {
-    if(numAssignedOne < numAssignedTwo) {
+    if(numAssignTreeOne < numAssignTreeTwo) {
       for(int i = 0; i < end; i++) {
         insertNodeIntoTree(treeOne, oldTree.Children()[i]);
       }
@@ -350,9 +391,13 @@
 /**
   * Insert a node into another node.  Expanding the bounds and updating the numberOfChildren.
   */
-static void insertNodeIntoTree(
-    RectangleTree& destTree,
-    RectangleTree& srcNode)
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+void RTreeSplit<SplitType, DescentType, StatisticType, MatType>::insertNodeIntoTree(
+    RectangleTree<SplitType, DescentType, StatisticType, MatType>& destTree,
+    RectangleTree<SplitType, DescentType, StatisticType, MatType>& srcNode)
 {
   destTree.Bound() |= srcNode.Bound();
   destTree.Children()[destTree.getNumOfChildren()++] = &srcNode;

Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp	Wed Jun 11 12:47:44 2014
@@ -12,13 +12,15 @@
 #include "../hrectbound.hpp"
 #include "../statistic.hpp"
 
-#ifdef __MLPACK_CORE_TREE_HRECTBOUND_HPP
-#define max(a, b) 5  //something to break the build
-#endif
+// #ifdef __MLPACK_CORE_TREE_HRECTBOUND_HPP
+// #define max(a, b) 5  //something to break the build
+// #endif
 
 namespace mlpack {
 namespace tree /** Trees and tree-building procedures. */ {
 
+using bound::HRectBound;
+  
 /**
  * A rectangle type tree tree, such as an R-tree or X-tree.  Once the
  * bound and type of dataset is defined, the tree will construct itself.  Call
@@ -65,7 +67,7 @@
   //! The minimum leaf size.
   size_t minLeafSize;
   //! The bound object for this node.
-  HRectBound bound;
+  HRectBound<> bound;
   //! Any extra data contained in the node.
   StatisticType stat;
   //! The distance from the centroid of this node to the centroid of the parent.
@@ -89,10 +91,29 @@
    * dataset.  This will modify the ordering of the points in the dataset!
    *
    * @param data Dataset from which to create the tree.  This will be modified!
-   * @param maxLeafSize Maximum size of each leaf in the tree;
+   * @param maxLeafSize Maximum size of each leaf in the tree.
+   * @param minLeafSize Minimum size of each leaf in the tree.
    * @param maxNumChildren The maximum number of child nodes a non-leaf node may have.
+   * @param minNumChildren The minimum number of child nodes a non-leaf node may have.
+   * @param firstDataIndex The index of the first data point.  UNUSED UNLESS WE ADD SUPPORT FOR HAVING A 
+   * "CENTERAL" DATA MATRIX.
+   */
+  RectangleTree(MatType& data,
+		const size_t maxLeafSize,
+		const size_t minLeafSize,
+		const size_t maxNumChildren,
+		const size_t minNumChildren,
+		const size_t firstDataIndex
+ 	      );
+  
+  /**
+   * Construct this as an empty node with the specified parent.  Copying the parameters
+   * (maxLeafSize, minLeafSize, maxNumChildren, minNumChildren, firstDataIndex) from the parent.
+   *
+   * @param parentNode The parent of the node that is being constructed.
    */
-  RectangleTree(MatType& data, const size_t maxLeafSize = 20, const size_t maxNumChildren = 4);
+  RectangleTree(const RectangleTree<SplitType, DescentType, StatisticType, MatType>& parentNode);
+
 
   //TODO implement the oldFromNew stuff if applicable.
 
@@ -145,9 +166,9 @@
   RectangleTree* FindByBeginCount(size_t begin, size_t count);
 
   //! Return the bound object for this node.
-  const HRectBound& Bound() const { return bound; }
+  const HRectBound<>& Bound() const { return bound; }
   //! Modify the bound object for this node.
-  HRectBound& Bound() { return bound; }
+  HRectBound<>& Bound() { return bound; }
 
   //! Return the statistic object for this node.
   const StatisticType& Stat() const { return stat; }
@@ -188,7 +209,7 @@
   arma::mat& Dataset() { return dataset; }
 
   //! Get the metric which the tree uses.
-  typename HRectBound::MetricType Metric() const { return bound.Metric(); }
+  typename HRectBound<>::MetricType Metric() const { return bound.Metric(); }
 
   //! Get the centroid of the node and store it in the given vector.
   void Centroid(arma::vec& centroid) { bound.Centroid(centroid); }
@@ -343,7 +364,7 @@
    */
   RectangleTree(const size_t begin,
                   const size_t count,
-                  HRectBound bound,
+                  HRectBound<> bound,
                   StatisticType stat,
                   const int maxLeafSize = 20) :
       begin(begin),
@@ -362,7 +383,7 @@
    *
    * @param tree The RectangleTree object (node) to split.
    */
-  void SplitNode(RectangleTree& tree);
+  void SplitNode();
 
   /**
    * Splits the current node, recursing up the tree.
@@ -371,7 +392,7 @@
    * @param data Dataset which we are using.
    * @param oldFromNew Vector holding permuted indices NOT IMPLEMENTED.
    */
-  void SplitNode(MatType& data, std::vector<size_t>& oldFromNew);
+  void SplitNode(std::vector<size_t>& oldFromNew);
 
  public:
   /**

Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp	Wed Jun 11 12:47:44 2014
@@ -21,33 +21,32 @@
          typename DescentType,
 	 typename StatisticType,
          typename MatType>
-RectangleTree<StatisticType, MatType, SplitType, DescentType>::RectangleTree(
+RectangleTree<SplitType, DescentType, StatisticType, MatType>::RectangleTree(
     MatType& data,
-    const size_t maxLeafSize,
-    const size_t minLeafSize,
-    const size_t maxNumChildren,
-    const size_t minNumChildren,
+    const size_t maxLeafSize = 20,
+    const size_t minLeafSize = 6,
+    const size_t maxNumChildren = 4,
+    const size_t minNumChildren = 0,
     const size_t firstDataIndex = 0):
+    maxNumChildren(maxNumChildren),
+    minNumChildren(minNumChildren),
+    numChildren(0),
+    children(maxNumChildren+1), // Add one to make splitting the node simpler
+    parent(NULL),
+    begin(0),
+    count(0),
+    maxLeafSize(maxLeafSize),
+    minLeafSize(minLeafSize),
+    bound(data.n_rows),
+    parentDistance(0)
 
 {
-  this.maxNumChildren = maxNumChildren;
-  this.minNumChildren = minNumChildren;
-  this.numChildren = 0;
-  this.parent = NULL;
-  this.begin = 0;
-  this.count = 0;
-  this.maxLeafSize = maxLeafSize;
-  this.minLeafSize = minLeafSize;
-  this.bound = new HRectBound(data.n_rows);
-  this.stat = EmptyStatistic;
-  this.parentDistance = 0.0;
-  this.furthestDescendantDistance = 0.0;
+  this.stat = EmptyStatistic(*this);
   this.dataset = new MatType(maxLeafSize+1); // Add one to make splitting the node simpler
-  this.children = new std::vector<RectangleTree*>(maxNumChildren+1); // ibid.
   
   // For now, just insert the points in order.
   RectangleTree* root = this;
-  for(int i = firstDataIndex; i < n_cols; i++) {
+  for(int i = firstDataIndex; i < data.n_cols; i++) {
     root.insertPoint(data.col(i));
     if(root.Parent() != NULL) {
       root = root.Parent(); // OK since the level increases by at most one per iteration.
@@ -56,21 +55,44 @@
   
 }
 
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+RectangleTree<SplitType, DescentType, StatisticType, MatType>::RectangleTree(
+  const RectangleTree<SplitType, DescentType, StatisticType, MatType>& parentNode):
+  maxNumChildren(parentNode.MaxNumChildren()),
+  minNumChildren(parentNode.MinNumChildren()),
+  numChildren(0),
+  children(maxNumChildren+1),
+  parent(&parentNode),
+  begin(0),
+  count(0),
+  maxLeafSize(parentNode.MaxLeafSize()),
+  minLeafSize(parentNode.MinLeafSize()),
+  bound(parentNode.Bound().Dim()),
+  parentDistance(0)
+  {
+    this.stat = EmptyStatistic(*this);
+    this.dataset = new MatType(maxLeafSize+1); // Add one to make splitting the node simpler
+  }
+
 /**
  * Deletes this node, deallocating the memory for the children and calling
  * their destructors in turn.  This will invalidate any pointers or references
  * to any nodes which are children of this one.
  */
-template<typename StatisticType,
-	 typename MatType,
-	 typename SplitType,
-	 typename DescentType>
-RectangleTree<BoundType, StatisticType, MatType, SplitType, DescentType>::
+template<typename SplitType,
+         typename DescentType,
+	 typename StatisticType,
+         typename MatType>
+RectangleTree<SplitType, DescentType, StatisticType, MatType>::
   ~RectangleTree()
 {
-  for(int i = 0; i < numOfChildren; i++) {
+  for(int i = 0; i < numChildren; i++) {
     delete children[i];
   }
+  delete dataset;
 }
 
 
@@ -78,11 +100,11 @@
  * Recurse through the tree and insert the point at the leaf node chosen
  * by the heuristic.
  */
-template<typename StatisticType,
-	 typename MatType,
-	 typename SplitType,
-	 typename DescentType>
-RectangleTree<StatisticType, MatType, SplitType, DescentType>::
+template<typename SplitType,
+         typename DescentType,
+	 typename StatisticType,
+         typename MatType>
+void RectangleTree<SplitType, DescentType, StatisticType, MatType>::
     InsertPoint(const arma::vec& point)
 {
   // Expand the bound regardless of whether it is a leaf node.
@@ -90,34 +112,34 @@
   
   // If this is a leaf node, we stop here and add the point.
   if(numChildren == 0) {
-    data.col(points++) = point;
-    splitNode();
+    dataset.col(count++) = point;
+    SplitNode();
     return;
   }
 
   // If it is not a leaf node, we use the DescentHeuristic to choose a child
   // to which we recurse.
-  double minScore = DescentType.EvalNode(children[0].bound, point);
+  double minScore = DescentType::EvalNode(children[0].bound, point);
   int bestIndex = 0;
   for(int i = 1; i < numChildren; i++) {
-    double score = DescentType.EvalNode(children[i].bound, point);
+    double score = DescentType::EvalNode(children[i].bound, point);
     if(score < minScore) {
       minScore = score;
-      bestIndex = i
+      bestIndex = i;
     }
   }
   children[bestIndex].InsertPoint(point);
 }
 
-template<typename StatisticType,
-	 typename MatType,
-	 typename SplitType,
-	 typename DescentType>
-size_t RectangleTree<StatisticType, MatType, SplitType, DescentType>::
+template<typename SplitType,
+         typename DescentType,
+	 typename StatisticType,
+         typename MatType>
+size_t RectangleTree<SplitType, DescentType, StatisticType, MatType>::
     TreeSize() const
 {
   int n = 0;
-  for(int i = 0; i < numOfChildren; i++) {
+  for(int i = 0; i < numChildren; i++) {
     n += children[i].TreeSize();
   }
   return n + 1; // we add one for this node
@@ -125,17 +147,17 @@
 
 
 
-template<typename StatisticType,
-	 typename MatType,
-	 typename SplitType,
-	 typename DescentType>
-size_t RectangleTree<StatisticType, MatType, SplitType, DescentType>::
+template<typename SplitType,
+         typename DescentType,
+	 typename StatisticType,
+         typename MatType>
+size_t RectangleTree<SplitType, DescentType, StatisticType, MatType>::
     TreeDepth() const
 {
   // Recursively count the depth of each subtree.  The plus one is
   // because we have to count this node, too.
   int maxSubDepth = 0;
-  for(int i = 0; i < numOfChildren; i++) {
+  for(int i = 0; i < numChildren; i++) {
     int d = children[i].depth();
     if(d > maxSubDepth)
       maxSubDepth = d;
@@ -143,38 +165,26 @@
   return maxSubDepth + 1;
 }
 
-template<typename StatisticType,
-         typename MatType,
-         typename SplitType,
-	typename DescentType>
-inline bool BinarySpaceTree<StatisticType, MatType, SplitType, DescentType>::
+template<typename SplitType,
+         typename DescentType,
+	 typename StatisticType,
+         typename MatType>
+inline bool RectangleTree<SplitType, DescentType, StatisticType, MatType>::
     IsLeaf() const
 {
-  return numOfChildren == 0;
+  return numChildren == 0;
 }
 
-/**
- * Returns the number of children in this node.
- */
-template<typename StatisticType,
-	 typename MatType,
-	 typename SplitType,
-	 typename DescentType>
-inline size_t RectangleTree<StatisticType, MatType, SplitType, DescentType>::
-    NumChildren() const
-{
-  return NumChildren;
-}
 
 /**
  * Return a bound on the furthest point in the node form the centroid.
  * This returns 0 unless the node is a leaf.
  */
-template<typename StatisticType,
-         typename MatType,
-         typename SplitType,
-	typename DescentType>
-inline double RectangleTree<StatisticType, MatType, SplitType, DescentType>::
+template<typename SplitType,
+         typename DescentType,
+	 typename StatisticType,
+         typename MatType>
+inline double RectangleTree<SplitType, DescentType, StatisticType, MatType>::
 FurthestPointDistance() const
 {
   if(!IsLeaf())
@@ -191,11 +201,11 @@
  * furthest descendant distance may be less than what this method returns (but
  * it will never be greater than this).
  */
-template<typename StatisiticType,
-	 typename MatType,
-	 typename SplitType,
-	 typename DescentType>
-inline double RectangleTree<StatisticType, MatType, SplitType, DescentType>::
+template<typename SplitType,
+         typename DescentType,
+	 typename StatisticType,
+         typename MatType>
+inline double RectangleTree<SplitType, DescentType, StatisticType, MatType>::
     FurthestDescendantDistance() const
 {
   return furthestDescendantDistance;
@@ -204,12 +214,12 @@
 /**
  * Return the specified child.
  */
-template<typename StatisticType,
-	 typename MatType,
-	 typename SplitType,
-	 typename DescentType>
-inline RectangleTree<StatisticType, MatType, SplitType, DescentType>&
-    RectangleTree<StatisticType, MatType, SplitType, DescentType>::
+template<typename SplitType,
+         typename DescentType,
+	 typename StatisticType,
+         typename MatType>
+inline RectangleTree<SplitType, DescentType, StatisticType, MatType>&
+    RectangleTree<SplitType, DescentType, StatisticType, MatType>::
         Child(const size_t child) const
 {
   return children[child];
@@ -218,11 +228,11 @@
 /**
  * Return the number of points contained in this node.  Zero if it is not a leaf.
  */
-template<typename StatisticType,
-	 typename MatType,
-	 typename SplitType,
-	 typename DescentType>
-inline size_t RectangleTree<StatisticType, MatType, SplitType, DescentType>::
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+inline size_t RectangleTree<SplitType, DescentType, StatisticType, MatType>::
     NumPoints() const
 {
   if(numChildren == 0)
@@ -234,11 +244,11 @@
 /**
  * Return the number of descendants contained in this node.  MEANINIGLESS AS IT CURRENTLY STANDS.
  */
-template<typename StatisticType,
-	 typename MatType,
-	 typename SplitType,
-	 typename DescentType>
-inline size_t RectangleTree<StatisticType, MatType, SplitType, DescentType>::
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+inline size_t RectangleTree<SplitType, DescentType, StatisticType, MatType>::
     NumDescendants() const
 {
   return count;
@@ -247,12 +257,12 @@
 /**
  * Return the index of a particular descendant contained in this node.  SEE OTHER WARNINGS
  */
-template<typename StatisticType,
-	 typename MatType,
-	 typename SplitType,
-	 typename DescentType>
-inline size_t RectangleTree<StatisticType, MatType, SplitType, DescentType>::
-    Descendant(const size_t index> const
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+inline size_t RectangleTree<SplitType, DescentType, StatisticType, MatType>::
+    Descendant(const size_t index) const
 {
   return (begin + index);
 }
@@ -260,12 +270,12 @@
 /**
  * Return the index of a particular point contained in this node.  SEE OTHER WARNINGS
  */
-template<typename StatisticType,
-	 typename MatType,
-	 typename SplitType,
-	 typename DescentType>
-inline size_t RectangleTree<StatisticType, MatType, SplitType, DescentType>::
-    Point(const size_t index> const
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+inline size_t RectangleTree<SplitType, DescentType, StatisticType, MatType>::
+    Point(const size_t index) const
 {
   return (begin + index);
 }
@@ -274,15 +284,15 @@
  * Return the last point in the tree.  SINCE THE TREE STORES DATA SEPARATELY IN EACH LEAF
  * THIS IS CURRENTLY MEANINGLESS.
  */
-template<typename StatisticType,
-	 typename MatType,
-	 typename SplitType,
-	 typename DescentType>
-inline size_t RectangleTree<StatisticType, MatType, SplitType, DescentType>::End() const
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+inline size_t RectangleTree<SplitType, DescentType, StatisticType, MatType>::End() const
 {
-  if(numOfChildren)
+  if(numChildren)
     return begin + count;
-  return children[numOfChildren-1].End();
+  return children[numChildren-1].End();
 }
 
   //have functions for returning the list of modified indices if we end up doing it that way.
@@ -291,53 +301,53 @@
  * Split the tree.  This calls the SplitType code to split a node.  This method should only
  * be called on a leaf node.
  */
-template<typename StatisticType,
-	 typename MatType,
-	 typename SplitType,
-	 typename DescentType>
-void RectangleTree<StatisticType, MatType, SplitType, DescentType>::SplitNode(
-    RetangleTree& tree)
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+void RectangleTree<SplitType, DescentType, StatisticType, MatType>::SplitNode()
 {
   // This should always be a leaf node.  When we need to split other nodes,
   // the split will be called from here but will take place in the SplitType code.
-  boost::assert(numChildren == 0);
+  assert(numChildren == 0);
 
   // See if we are full.
-  if(points < maxLeafSize)
+  if(count < maxLeafSize)
     return;
   
   // If we are full, then we need to move up the tree.  The SplitType takes
   // care of this.
-  SplitType.SplitLeafNode(this);    
+  SplitType::SplitLeafNode(this);    
 }
 
 
 /**
  * Returns a string representation of this object.
  */
-  template<typename StatisticType,
-	   typename MatType,
-	   typename SplitType,
-	 typename DescentType>
-std::string RectangleTree<StatisticType, MatType, SplitType, DescentType>::ToString() const
+template<typename SplitType,
+	 typename DescentType,
+	 typename StatisticType,
+	 typename MatType>
+std::string RectangleTree<SplitType, DescentType, StatisticType, MatType>::ToString() const
 {
   std::ostringstream convert;
   convert << "RectangleTree [" << this << "]" << std::endl;
   convert << "  First point: " << begin << std::endl;
-  convert << "  Number of descendants: " << count << std::endl;
+  convert << "  Number of descendants: " << numChildren << std::endl;
+  convert << "  Number of points: " << count << std::endl;
   convert << "  Bound: " << std::endl;
   convert << mlpack::util::Indent(bound.ToString(), 2);
   convert << "  Statistic: " << std::endl;
   convert << mlpack::util::Indent(stat.ToString(), 2);
   convert << "  Max leaf size: " << maxLeafSize << std::endl;
-  convert << "  Split dimension: " << splitDimension << std::endl;
 
   // How many levels should we print?  This will print the root and it's children.
   if(parent == NULL) {
     for(int i = 0; i < numChildren; i++) {
-      children[i].ToString();
+      convert << children[i].ToString();
     }
   }
+  return convert.str();
 }
 
 }; //namespace tree

Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser.hpp	Wed Jun 11 12:47:44 2014
@@ -21,7 +21,7 @@
 	 typename StatisticType,
          typename MatType>
 template<typename RuleType>
-class RectangleTree<StatisticType, MatType, SplitType, DescentType>::
+class RectangleTree<SplitType, DescentType, StatisticType, MatType>::
     RectangleTreeTraverser
 {
  public:
@@ -52,7 +52,6 @@
   size_t numPrunes;
 };
 
-
 }; // namespace tree
 }; // namespace mlpack
 

Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser_impl.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser_impl.hpp	Wed Jun 11 12:47:44 2014
@@ -22,21 +22,21 @@
 	 typename StatisticType,
          typename MatType>
 template<typename RuleType>
-RectangleTree<StatisticType, MatType, SplitType, DescentType>::
+RectangleTree<SplitType, DescentType, StatisticType, MatType>::
 RectangleTreeTraverser<RuleType>::RectangleTreeTraverser(RuleType& rule) :
     rule(rule),
     numPrunes(0)
 { /* Nothing to do */ }
 
-template<typename StatisticType,
-    typename MatType,
-    typename SplitType
-    typename DescentType>
+template<typename SplitType,
+         typename DescentType,
+	 typename StatisticType,
+         typename MatType>
 template<typename RuleType>
-void RectangleTree<StatisticType, MatType, SplitType, DescentType>::
+void RectangleTree<SplitType, DescentType, StatisticType, MatType>::
 RectangleTreeTraverser<RuleType>::Traverse(
     const size_t queryIndex,
-    RectangeTree<StatisticType, MatyType, SplitType, DescentType>&
+    const RectangleTree<SplitType, DescentType, StatisticType, MatType>&
         referenceNode)
 {
   // If we reach a leaf node, we need to run the base case.
@@ -53,14 +53,14 @@
   std::vector<double> scores = new std::vector<double>(referenceNode.NumChildren());
   for(int i = 0; i < referenceNode.NumChildren(); i++) {
     nodes[i] = referenceNode.Children()[i];
-    scores[i] = Rule.Score(nodes[i]);
+    scores[i] = rule.Score(nodes[i]);
   }  
-  Rule.sortNodesAndScores(&nodes, &scores);
+  rule.sortNodesAndScores(&nodes, &scores);
   
   // Iterate through them starting with the best and stopping when we reach
   // one that isn't good enough.
   for(int i = 0; i < referenceNode.NumChildren(); i++) {
-   if(Rule.Rescore(queryIndex, nodes[i], scores[i]) != DBL_MAX)
+   if(rule.Rescore(queryIndex, nodes[i], scores[i]) != DBL_MAX)
      Traverse(queryIndex, nodes[i]);
    else {
     numPrunes += referenceNode.NumChildren - i;



More information about the mlpack-svn mailing list