[mlpack-git] master: Don't do base cases before recursing. This is slightly cleaner code and will properly handle the case where the tree is only one node deep. (d0ad39f)

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

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

On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40

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

commit d0ad39fc7913da4865814703c3a5ea9f2665463c
Author: Ryan Curtin <ryan at ratml.org>
Date:   Tue Jul 29 15:50:38 2014 +0000

    Don't do base cases before recursing.  This is slightly cleaner code and will
    properly handle the case where the tree is only one node deep.


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

d0ad39fc7913da4865814703c3a5ea9f2665463c
 .../single_tree_traverser_impl.hpp                 | 100 +++++++++------------
 1 file changed, 44 insertions(+), 56 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 0a1e71f..7b559e0 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,77 +39,65 @@ SingleTreeTraverser<RuleType>::Traverse(
     BinarySpaceTree<BoundType, StatisticType, MatType, SplitType>&
         referenceNode)
 {
-  // If this is a leaf, the base cases have already been run.
+  // If we are a leaf, run the base case as necessary.
   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.Left()->Begin();
-         i < referenceNode.Left()->End(); ++i)
+    for (size_t i = referenceNode.Begin(); i < referenceNode.End(); ++i)
       rule.BaseCase(queryIndex, i);
   }
-
-  double rightScore = rule.Score(queryIndex, *referenceNode.Right());
-
-  // Immediately run the base case if it's not pruned.
-  if ((rightScore != DBL_MAX) && (referenceNode.Right()->IsLeaf()))
+  else
   {
-    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());
-
-    // 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;
-  }
-  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 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());
 
-    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 (leftScore < rightScore)
     {
-      // Choose the left first.
+      // Recurse to the left.
       Traverse(queryIndex, *referenceNode.Left());
 
       // Is it still valid to recurse to the right?
-      rightScore = rule.Rescore(queryIndex, *referenceNode.Right(),
-          rightScore);
+      rightScore = rule.Rescore(queryIndex, *referenceNode.Right(), rightScore);
 
       if (rightScore != DBL_MAX)
-        Traverse(queryIndex, *referenceNode.Right());
+        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
+      {
+        // 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;
+      }
+    }
   }
 }