[mlpack-git] master, mlpack-1.0.x: Ensure that BaseCase() is called right after a node is scored. (acfa22e)

[gitdub at big.cc.gt.atl.ga.us]

Repository : https://github.com/mlpack/mlpack

On branches: master,mlpack-1.0.x
Link       : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40

>---------------------------------------------------------------

commit acfa22e5318bb3924e12c68ac09a70ab665efc21
Author: Ryan Curtin <ryan at ratml.org>
Date:   Tue May 27 00:31:47 2014 +0000

    Ensure that BaseCase() is called right after a node is scored.


>---------------------------------------------------------------

acfa22e5318bb3924e12c68ac09a70ab665efc21
 .../single_tree_traverser_impl.hpp                 | 100 ++++++++++++---------
 1 file changed, 56 insertions(+), 44 deletions(-)

diff --git a/src/mlpack/core/tree/binary_space_tree/single_tree_traverser_impl.hpp b/src/mlpack/core/tree/binary_space_tree/single_tree_traverser_impl.hpp
index 7b559e0..0a1e71f 100644
--- a/src/mlpack/core/tree/binary_space_tree/single_tree_traverser_impl.hpp
+++ b/src/mlpack/core/tree/binary_space_tree/single_tree_traverser_impl.hpp
@@ -39,65 +39,77 @@ SingleTreeTraverser<RuleType>::Traverse(
     BinarySpaceTree<BoundType, StatisticType, MatType, SplitType>&
         referenceNode)
 {
-  // If we are a leaf, run the base case as necessary.
+  // If this is a leaf, the base cases have already been run.
   if (referenceNode.IsLeaf())
+    return;
+
+  // If either score is DBL_MAX, we do not recurse into that node.
+  double leftScore = rule.Score(queryIndex, *referenceNode.Left());
+
+  // Immediately run the base case if it's not pruned.
+  if ((leftScore != DBL_MAX) && (referenceNode.Left()->IsLeaf()))
   {
-    for (size_t i = referenceNode.Begin(); i < referenceNode.End(); ++i)
+    for (size_t i = referenceNode.Left()->Begin();
+         i < referenceNode.Left()->End(); ++i)
       rule.BaseCase(queryIndex, i);
   }
-  else
+
+  double rightScore = rule.Score(queryIndex, *referenceNode.Right());
+
+  // Immediately run the base case if it's not pruned.
+  if ((rightScore != DBL_MAX) && (referenceNode.Right()->IsLeaf()))
   {
-    // If either score is DBL_MAX, we do not recurse into that node.
-    double leftScore = rule.Score(queryIndex, *referenceNode.Left());
-    double rightScore = rule.Score(queryIndex, *referenceNode.Right());
+    for (size_t i = referenceNode.Right()->Begin();
+         i < referenceNode.Right()->End(); ++i)
+      rule.BaseCase(queryIndex, i);
+  }
 
-    if (leftScore < rightScore)
-    {
-      // Recurse to the left.
-      Traverse(queryIndex, *referenceNode.Left());
+  if (leftScore < rightScore)
+  {
+    // Recurse to the left.
+    Traverse(queryIndex, *referenceNode.Left());
 
-      // Is it still valid to recurse to the right?
-      rightScore = rule.Rescore(queryIndex, *referenceNode.Right(), rightScore);
+    // Is it still valid to recurse to the right?
+    rightScore = rule.Rescore(queryIndex, *referenceNode.Right(), rightScore);
 
-      if (rightScore != DBL_MAX)
-        Traverse(queryIndex, *referenceNode.Right()); // Recurse to the right.
-      else
-        ++numPrunes;
+    if (rightScore != DBL_MAX)
+      Traverse(queryIndex, *referenceNode.Right()); // Recurse to the right.
+    else
+      ++numPrunes;
+  }
+  else if (rightScore < leftScore)
+  {
+    // Recurse to the right.
+    Traverse(queryIndex, *referenceNode.Right());
+
+    // Is it still valid to recurse to the left?
+    leftScore = rule.Rescore(queryIndex, *referenceNode.Left(), leftScore);
+
+    if (leftScore != DBL_MAX)
+      Traverse(queryIndex, *referenceNode.Left()); // Recurse to the left.
+    else
+      ++numPrunes;
+  }
+  else // leftScore is equal to rightScore.
+  {
+    if (leftScore == DBL_MAX)
+    {
+      numPrunes += 2; // Pruned both left and right.
     }
-    else if (rightScore < leftScore)
+    else
     {
-      // Recurse to the right.
-      Traverse(queryIndex, *referenceNode.Right());
+      // Choose the left first.
+      Traverse(queryIndex, *referenceNode.Left());
 
-      // Is it still valid to recurse to the left?
-      leftScore = rule.Rescore(queryIndex, *referenceNode.Left(), leftScore);
+      // Is it still valid to recurse to the right?
+      rightScore = rule.Rescore(queryIndex, *referenceNode.Right(),
+          rightScore);
 
-      if (leftScore != DBL_MAX)
-        Traverse(queryIndex, *referenceNode.Left()); // Recurse to the left.
+      if (rightScore != DBL_MAX)
+        Traverse(queryIndex, *referenceNode.Right());
       else
         ++numPrunes;
     }
-    else // leftScore is equal to rightScore.
-    {
-      if (leftScore == DBL_MAX)
-      {
-        numPrunes += 2; // Pruned both left and right.
-      }
-      else
-      {
-        // Choose the left first.
-        Traverse(queryIndex, *referenceNode.Left());
-
-        // Is it still valid to recurse to the right?
-        rightScore = rule.Rescore(queryIndex, *referenceNode.Right(),
-            rightScore);
-
-        if (rightScore != DBL_MAX)
-          Traverse(queryIndex, *referenceNode.Right());
-        else
-          ++numPrunes;
-      }
-    }
   }
 }