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

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

Author: rcurtin
Date: Fri Aug 23 15:06:43 2013
New Revision: 15649

Log:
When removing implicit nodes, ParentDistance() was not being correctly
preserved.


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

Modified: mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp	Fri Aug 23 15:06:43 2013
@@ -446,6 +446,13 @@
                      const double bound,
                      const size_t nearSetSize,
                      const size_t pointSetSize);
+
+  /**
+   * Take a look at the last child (the most recently created one) and remove
+   * any implicit nodes that have been created.
+   */
+  void RemoveNewImplicitNodes();
+
  public:
   /**
    * Returns a string representation of this object.

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 Aug 23 15:06:43 2013
@@ -455,25 +455,8 @@
   // can modify the furthestDescendantDistance.
   furthestDescendantDistance = children[0]->FurthestDescendantDistance();
 
-  // If we created an implicit node, take its self-child instead (this could
-  // happen multiple times).
-  while (children[children.size() - 1]->NumChildren() == 1)
-  {
-    CoverTree* old = children[children.size() - 1];
-    children.erase(children.begin() + children.size() - 1);
-
-    // Now take its child.
-    children.push_back(&(old->Child(0)));
-
-    // Set its parent correctly.
-    old->Child(0).Parent() = this;
-
-    // Remove its child (so it doesn't delete it).
-    old->Children().erase(old->Children().begin() + old->Children().size() - 1);
-
-    // Now delete it.
-    delete old;
-  }
+  // Remove any implicit nodes we may have created.
+  RemoveNewImplicitNodes();
 
   // Now the arrays, in memory, look like this:
   // [ childFar | childUsed | far | used ]
@@ -564,26 +547,8 @@
         childFarSetSize, childUsedSetSize, *metric));
     numDescendants += children[children.size() - 1]->NumDescendants();
 
-    // If we created an implicit node, take its self-child instead (this could
-    // happen multiple times).
-    while (children[children.size() - 1]->NumChildren() == 1)
-    {
-      CoverTree* old = children[children.size() - 1];
-      children.erase(children.begin() + children.size() - 1);
-
-      // Now take its child.
-      children.push_back(&(old->Child(0)));
-
-      // Set its parent correctly.
-      old->Child(0).Parent() = this;
-
-      // Remove its child (so it doesn't delete it).
-      old->Children().erase(old->Children().begin() + old->Children().size()
-          - 1);
-
-      // Now delete it.
-      delete old;
-    }
+    // Remove any implicit nodes.
+    RemoveNewImplicitNodes();
 
     // Now with the child created, it returns the childIndices and
     // childDistances vectors in this form:
@@ -909,6 +874,36 @@
 }
 
 /**
+ * Take a look at the last child (the most recently created one) and remove any
+ * implicit nodes that have been created.
+ */
+template<typename MetricType, typename RootPointPolicy, typename StatisticType>
+inline void CoverTree<MetricType, RootPointPolicy, StatisticType>::
+    RemoveNewImplicitNodes()
+{
+  // If we created an implicit node, take its self-child instead (this could
+  // happen multiple times).
+  while (children[children.size() - 1]->NumChildren() == 1)
+  {
+    CoverTree* old = children[children.size() - 1];
+    children.erase(children.begin() + children.size() - 1);
+
+    // Now take its child.
+    children.push_back(&(old->Child(0)));
+
+    // Set its parent correctly.
+    old->Child(0).Parent() = this;
+    old->Child(0).ParentDistance() = old->ParentDistance();
+
+    // Remove its child (so it doesn't delete it).
+    old->Children().erase(old->Children().begin() + old->Children().size() - 1);
+
+    // Now delete it.
+    delete old;
+  }
+}
+
+/**
  * Returns a string representation of this object.
  */
 template<typename MetricType, typename RootPointPolicy, typename StatisticType>
@@ -936,6 +931,7 @@
   }
   return convert.str();
 }
+
 }; // namespace tree
 }; // namespace mlpack