[mlpack-git] master: Fixed a segfault in RPlusTreeSplit. Fixed traits for the R+/R++ tree. (2ec9b6c)

[gitdub at mlpack.org]

Repository : https://github.com/mlpack/mlpack
On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/ccc6ff0c01d670536dca496ebdf74d78497020f6...8900b8ca1591c68aee93b462afabfc4be0e7e83b

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

commit 2ec9b6ca75c8987e5bae064aac3608b4addcf235
Author: Mikhail Lozhnikov <lozhnikovma at gmail.com>
Date:   Sat Jul 16 19:50:12 2016 +0300

    Fixed a segfault in RPlusTreeSplit. Fixed traits for the R+/R++ tree.


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

2ec9b6ca75c8987e5bae064aac3608b4addcf235
 src/mlpack/core/tree/rectangle_tree.hpp            |  2 +-
 .../tree/rectangle_tree/r_plus_tree_split_impl.hpp | 21 ++++++++--
 src/mlpack/core/tree/rectangle_tree/traits.hpp     | 48 ++++++++++++++++++++++
 src/mlpack/tests/rectangle_tree_test.cpp           |  8 ++++
 4 files changed, 74 insertions(+), 5 deletions(-)

diff --git a/src/mlpack/core/tree/rectangle_tree.hpp b/src/mlpack/core/tree/rectangle_tree.hpp
index 6ed68ec..8bb8160 100644
--- a/src/mlpack/core/tree/rectangle_tree.hpp
+++ b/src/mlpack/core/tree/rectangle_tree.hpp
@@ -22,7 +22,6 @@
 #include "rectangle_tree/no_auxiliary_information.hpp"
 #include "rectangle_tree/r_tree_descent_heuristic.hpp"
 #include "rectangle_tree/r_star_tree_descent_heuristic.hpp"
-#include "rectangle_tree/traits.hpp"
 #include "rectangle_tree/x_tree_split.hpp"
 #include "rectangle_tree/x_tree_auxiliary_information.hpp"
 #include "rectangle_tree/hilbert_r_tree_descent_heuristic.hpp"
@@ -37,6 +36,7 @@
 #include "rectangle_tree/r_plus_plus_tree_auxiliary_information.hpp"
 #include "rectangle_tree/r_plus_plus_tree_descent_heuristic.hpp"
 #include "rectangle_tree/r_plus_plus_tree_split_policy.hpp"
+#include "rectangle_tree/traits.hpp"
 #include "rectangle_tree/typedef.hpp"
 
 #endif
diff --git a/src/mlpack/core/tree/rectangle_tree/r_plus_tree_split_impl.hpp b/src/mlpack/core/tree/rectangle_tree/r_plus_tree_split_impl.hpp
index 67025d5..64b4043 100644
--- a/src/mlpack/core/tree/rectangle_tree/r_plus_tree_split_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/r_plus_tree_split_impl.hpp
@@ -83,8 +83,8 @@ SplitLeafNode(TreeType* tree, std::vector<bool>& relevels)
     return;
   }
 
-  TreeType* treeOne = new TreeType(tree->Parent());
-  TreeType* treeTwo = new TreeType(tree->Parent());
+  TreeType* treeOne = new TreeType(tree->Parent(), tree->MaxNumChildren());
+  TreeType* treeTwo = new TreeType(tree->Parent(), tree->MaxNumChildren());
   treeOne->MinLeafSize() = 0;
   treeOne->MinNumChildren() = 0;
   treeTwo->MinLeafSize() = 0;
@@ -153,8 +153,8 @@ SplitNonLeafNode(TreeType* tree, std::vector<bool>& relevels)
     return false;
   }
 
-  TreeType* treeOne = new TreeType(tree->Parent());
-  TreeType* treeTwo = new TreeType(tree->Parent());
+  TreeType* treeOne = new TreeType(tree->Parent(), tree->MaxNumChildren());
+  TreeType* treeTwo = new TreeType(tree->Parent(), tree->MaxNumChildren());
   treeOne->MinLeafSize() = 0;
   treeOne->MinNumChildren() = 0;
   treeTwo->MinLeafSize() = 0;
@@ -198,6 +198,19 @@ void RPlusTreeSplit<SplitPolicyType, SweepType>::SplitLeafNodeAlongPartition(
   // Split the auxiliary information.
   tree->AuxiliaryInfo().SplitAuxiliaryInfo(treeOne, treeTwo, cutAxis, cut);
 
+  // Ensure that the capacity of the nodes is sufficient.
+  if (treeOne->MaxLeafSize() < tree->NumPoints())
+  {
+    treeOne->MaxLeafSize() = tree->NumPoints();
+    treeOne->points.resize(treeOne->MaxLeafSize() + 1);
+  }
+
+  if (treeTwo->MaxLeafSize() < tree->NumPoints())
+  {
+    treeTwo->MaxLeafSize() = tree->NumPoints();
+    treeTwo->points.resize(treeTwo->MaxLeafSize() + 1);
+  }
+
   // Insert points into the corresponding subtree.
   for (size_t i = 0; i < tree->NumPoints(); i++)
   {
diff --git a/src/mlpack/core/tree/rectangle_tree/traits.hpp b/src/mlpack/core/tree/rectangle_tree/traits.hpp
index 76452ec..e4e16f9 100644
--- a/src/mlpack/core/tree/rectangle_tree/traits.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/traits.hpp
@@ -56,6 +56,54 @@ class TreeTraits<RectangleTree<MetricType, StatisticType, MatType, SplitType,
   static const bool BinaryTree = false;
 };
 
+/**
+ * Since the R+/R++ tree can not have overlapping children, we should define
+ * traits for the R+/R++ tree.
+ */
+template<typename MetricType,
+         typename StatisticType,
+         typename MatType,
+         typename SplitPolicyType,
+         template<typename> class SweepType,
+         typename DescentType,
+         template<typename> class AuxiliaryInformationType>
+class TreeTraits<RectangleTree<MetricType,
+    StatisticType,
+    MatType,
+    RPlusTreeSplit<SplitPolicyType,
+                   SweepType>,
+    DescentType,
+    AuxiliaryInformationType>>
+{
+ public:
+  /**
+   * The R+/R++ tree can't have overlapping children.
+   */
+  static const bool HasOverlappingChildren = false;
+
+  /**
+   * There is no guarantee that the first point in a node is its centroid.
+   */
+  static const bool FirstPointIsCentroid = false;
+
+  /**
+   * Points are not contained at multiple levels of the R-tree.
+   */
+  static const bool HasSelfChildren = false;
+
+  /**
+   * Points are rearranged during building of the tree.
+   * THIS MAY NOT BE TRUE.  IT'S HARD TO DYNAMICALLY INSERT POINTS
+   * AND REARRANGE THE MATRIX
+   */
+  static const bool RearrangesDataset = false;
+
+  /**
+   * This tree is not necessarily a binary tree.
+   */
+  static const bool BinaryTree = false;
+};
+
 } // namespace tree
 } // namespace mlpack
 
diff --git a/src/mlpack/tests/rectangle_tree_test.cpp b/src/mlpack/tests/rectangle_tree_test.cpp
index 5ba1ec8..80e6fc7 100644
--- a/src/mlpack/tests/rectangle_tree_test.cpp
+++ b/src/mlpack/tests/rectangle_tree_test.cpp
@@ -904,6 +904,10 @@ BOOST_AUTO_TEST_CASE(RPlusTreeOverlapTest)
 
   CheckOverlap(rPlusTree);
 
+  // Children can not be overlapping.
+  bool b = TreeTraits<TreeType>::HasOverlappingChildren;
+  BOOST_REQUIRE_EQUAL(b, false);
+
   // Ensure that all leaf nodes are at the same level.
   BOOST_REQUIRE_EQUAL(GetMinLevel(rPlusTree), GetMaxLevel(rPlusTree));
   BOOST_REQUIRE_EQUAL(rPlusTree.TreeDepth(), GetMinLevel(rPlusTree));
@@ -1019,6 +1023,10 @@ BOOST_AUTO_TEST_CASE(RPlusPlusTreeBoundTest)
 
   CheckRPlusPlusTreeBound(rPlusPlusTree);
 
+  // Children can not be overlapping.
+  bool b = TreeTraits<TreeType>::HasOverlappingChildren;
+  BOOST_REQUIRE_EQUAL(b, false);
+
   BOOST_REQUIRE_EQUAL(GetMinLevel(rPlusPlusTree), GetMaxLevel(rPlusPlusTree));
   BOOST_REQUIRE_EQUAL(rPlusPlusTree.TreeDepth(), GetMinLevel(rPlusPlusTree));