[mlpack-svn] r15916 - mlpack/trunk/src/mlpack/core/tree/cover_tree

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

Author: rcurtin
Date: Fri Oct  4 00:29:14 2013
New Revision: 15916

Log:
If the root node ends up having an implicit child (not an illicit child!),
remove the implicit node.


Modified:
   mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp

Modified: mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp	Fri Oct  4 00:29:14 2013
@@ -61,6 +61,32 @@
   CreateChildren(indices, distances, dataset.n_cols - 1, farSetSize,
       usedSetSize);
 
+  // If we ended up creating only one child, remove the implicit node.
+  while (children.size() == 1)
+  {
+    // Prepare to delete the implicit child node.
+    CoverTree* old = children[0];
+
+    // Now take its children and set their parent correctly.
+    children.erase(children.begin());
+    for (size_t i = 0; i < old->NumChildren(); ++i)
+    {
+      children.push_back(&(old->Child(i)));
+
+      // Set its parent correctly.
+      old->Child(i).Parent() = this;
+    }
+
+    // Remove all the children so they don't get erased.
+    old->Children().clear();
+
+    // Reduce our own scale.
+    scale = old->Scale();
+
+    // Now delete it.
+    delete old;
+  }
+
   // Use the furthest descendant distance to determine the scale of the root
   // node.
   scale = (int) ceil(log(furthestDescendantDistance) / log(base));
@@ -112,6 +138,32 @@
   CreateChildren(indices, distances, dataset.n_cols - 1, farSetSize,
       usedSetSize);
 
+  // If we ended up creating only one child, remove the implicit node.
+  while (children.size() == 1)
+  {
+    // Prepare to delete the implicit child node.
+    CoverTree* old = children[0];
+
+    // Now take its children and set their parent correctly.
+    children.erase(children.begin());
+    for (size_t i = 0; i < old->NumChildren(); ++i)
+    {
+      children.push_back(&(old->Child(i)));
+
+      // Set its parent correctly.
+      old->Child(i).Parent() = this;
+    }
+
+    // Remove all the children so they don't get erased.
+    old->Children().clear();
+
+    // Reduce our own scale.
+    scale = old->Scale();
+
+    // Now delete it.
+    delete old;
+  }
+
   // Use the furthest descendant distance to determine the scale of the root
   // node.
   scale = (int) ceil(log(furthestDescendantDistance) / log(base));