[mlpack-git] master: Minor updates. (e32b630)

[gitdub at mlpack.org]

Repository : https://github.com/mlpack/mlpack
On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/9ef7339d40550a974b3939e9fcb966fac2c09065...ebdb5abeaa3fd621a06ae663862bb72df76d2b40

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

commit e32b630ac61012dfe565499258ab5921288697db
Author: Ryan Curtin <ryan at ratml.org>
Date:   Tue Sep 13 11:26:40 2016 -0400

    Minor updates.


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

e32b630ac61012dfe565499258ab5921288697db
 src/mlpack/core/tree/octree/octree.hpp | 168 +++++++++++++++++++++++++++++++++
 src/mlpack/tests/ub_tree_test.cpp      |   4 +-
 2 files changed, 170 insertions(+), 2 deletions(-)

diff --git a/src/mlpack/core/tree/octree/octree.hpp b/src/mlpack/core/tree/octree/octree.hpp
index 30d6bce..544fa75 100644
--- a/src/mlpack/core/tree/octree/octree.hpp
+++ b/src/mlpack/core/tree/octree/octree.hpp
@@ -34,6 +34,174 @@ class Octree
   //! The number of points of the dataset contained in this node (and its
   //! children).
   size_t count;
+  //! The minimum bounding rectangle of the points held in the node (and its
+  //! children).
+  HRectBound<MeetricType> bound;
+  //! The dataset.
+  MatType* dataset;
+  //! The parent (NULL if this node is the root).
+  Octree* parent;
+
+ public:
+  /**
+   * Construct this as the root node of an octree on the given dataset.  This
+   * copies the dataset.  If you don't want to copy the input dataset, consider
+   * using the constructor that takes an rvalue reference and use std::move().
+   *
+   * @param data Dataset to create tree from.  This will be copied!
+   * @param maxLeafSize Maximum number of points in a leaf node.
+   */
+  Octree(const MatType& data, const size_t maxLeafSize = 20);
+
+  /**
+   * Construct this as the root node of an octree on the given dataset.  This
+   * copies the dataset and modifies its ordering; a mapping of the old point
+   * indices to the new point indices is filled.  If you don't want the matrix
+   * to be copied, consider using the constructor that takes an rvalue reference
+   * and use std::move().
+   *
+   * @param data Dataset to create tree from.  This will be copied!
+   * @param oldFromNew Vector which will be filled with the old positions for
+   *      each new point.
+   * @param maxLeafSize Maximum number of points in a leaf node.
+   */
+  Octree(const MatType& data,
+         std::vector<size_t>& oldFromNew,
+         const size_t maxLeafSize = 20);
+
+  /**
+   * Construct this as the root node of an octree on the given dataset.  This
+   * copies the dataset and modifies its ordering; a mapping of the old point
+   * indices to the new point indices is filled, and a mapping of the new point
+   * indices to the old point indices is filled.  If you don't want the matrix
+   * to be copied, consider using the constructor that takes an rvalue reference
+   * and use std::move().
+   *
+   * @param data Dataset to create tree from.  This will be copied!
+   * @param oldFromNew Vector which will be filled with the old positions for
+   *      each new point.
+   * @param newFromOld Vector which will be filled with the new positions for
+   *      each old point.
+   * @param maxLeafSize Maximum number of points in a leaf node.
+   */
+  Octree(const MatType& data,
+         std::vector<size_t>& oldFromNew,
+         std::vector<size_t>& newFromOld,
+         const size_t maxLeafSize = 20);
+
+  /**
+   * Construct this as the root node of an octree on the given dataset.  This
+   * will take ownership of the dataset; if you don't want this, consider using
+   * the constructor that takes a const reference to the dataset.
+   *
+   * @param data Dataset to create tree from.  This will be copied!
+   * @param maxLeafSize Maximum number of points in a leaf node.
+   */
+  Octree(const MatType& data, const size_t maxLeafSize = 20);
 
+  /**
+   * Construct this as the root node of an octree on the given dataset. This
+   * will take ownership of the dataset; if you don't want this, consider using
+   * the constructor that takes a const reference to the dataset.  This modifies
+   * the ordering of the dataset; a mapping of the old point indices to the new
+   * point indices is filled.
+   *
+   * @param data Dataset to create tree from.  This will be copied!
+   * @param oldFromNew Vector which will be filled with the old positions for
+   *      each new point.
+   * @param maxLeafSize Maximum number of points in a leaf node.
+   */
+  Octree(MatType&& data,
+         std::vector<size_t>& oldFromNew,
+         const size_t maxLeafSize = 20);
+
+  /**
+   * Construct this as the root node of an octree on the given dataset.  This
+   * will take ownership of the dataset; if you don't want this, consider using
+   * the constructor that takes a const reference to the dataset.  This modifies
+   * the ordering of the dataset; a mapping of the old point indices to the new
+   * point indices is filled, and a mapping of the new point indices to the old
+   * point indices is filled.
+   *
+   * @param data Dataset to create tree from.  This will be copied!
+   * @param oldFromNew Vector which will be filled with the old positions for
+   *      each new point.
+   * @param newFromOld Vector which will be filled with the new positions for
+   *      each old point.
+   * @param maxLeafSize Maximum number of points in a leaf node.
+   */
+  Octree(MatType&& data,
+         std::vector<size_t>& oldFromNew,
+         std::vector<size_t>& newFromOld,
+         const size_t maxLeafSize = 20);
+
+  /**
+   * Construct this node as a child of the given parent, starting at column
+   * begin and using count points.  The ordering of that subset of points in the
+   * parent's data matrix will be modified!  This is used for recursive
+   * tree-building by the other constructors that don't specify point indices.
+   *
+   * @param parent Parent of this node.  Its dataset will be modified!
+   * @param begin Index of point to start tree construction with.
+   * @param count Number of points to use to construct tree.
+   * @param center Center of the node (for splitting).
+   * @param width Width of the node in each dimension.
+   * @param maxLeafSize Maximum number of points in a leaf node.
+   */
+  Octree(Octree* parent,
+         const size_t begin,
+         const size_t count,
+         const arma::vec& center,
+         const double width,
+         const size_t maxLeafSize = 20);
+
+  /**
+   * Construct this node as a child of the given parent, starting at column
+   * begin and using count points.  The ordering of that subset of points in the
+   * parent's data matrix will be modified!  This is used for recursive
+   * tree-building by the other constructors that don't specify point indices.
+   *
+   * A mapping of the old point indices to the new point indices is filled, but
+   * it is expected that the vector is already allocated with size greater than
+   * or equal to (begin + count), and if that is not true, invalid memory reads
+   * (and writes) will occur.
+   *
+   * @param parent Parent of this node.  Its dataset will be modified!
+   * @param begin Index of point to start tree construction with.
+   * @param count Number of points to use to construct tree.
+   * @param oldFromNew Vector which will be filled with the old positions for
+   *      each new point.
+   * @param center Center of the node (for splitting).
+   * @param width Width of the node in each dimension.
+   * @param maxLeafSize Maximum number of points in a leaf node.
+   */
+  Octree(Octree* parent,
+         const size_t begin,
+         const size_t count,
+         std::vector<size_t>& oldFromNew,
+         const arma::vec& center,
+         const double width,
+         const size_t maxLeafSize = 20);
+
+ private:
+  /**
+   * Split the node, using the given center and the given maximum width of this
+   * node.
+   *
+   * @param center Center of the node.
+   * @param width Width of the current node.
+   */
+  void SplitNode(const arma::vec& center, const double width);
 
+  /**
+   * Split the node, using the given center and the given maximum width of this
+   * node, and fill the mappings vector.
+   *
+   * @param center Center of the node.
+   * @param width Width of the current node.
+   * @param oldFromNew Mappings from old to new.
+   */
+  void SplitNode(const arma::vec& center,
+                 const double width,
+                 std::vector<size_t>& oldFromNew);
 };
diff --git a/src/mlpack/tests/ub_tree_test.cpp b/src/mlpack/tests/ub_tree_test.cpp
index 84bffed..426f4b0 100644
--- a/src/mlpack/tests/ub_tree_test.cpp
+++ b/src/mlpack/tests/ub_tree_test.cpp
@@ -282,9 +282,9 @@ BOOST_AUTO_TEST_CASE(UBTreeTest)
     BOOST_REQUIRE_EQUAL(root.NumDescendants(), size);
 
     // Check the forward and backward mappings for correctness.
-    for(size_t i = 0; i < size; i++)
+    for (size_t i = 0; i < size; i++)
     {
-      for(size_t j = 0; j < dimensions; j++)
+      for (size_t j = 0; j < dimensions; j++)
       {
         BOOST_REQUIRE_EQUAL(treeset(j, i), dataset(j, newToOld[i]));
         BOOST_REQUIRE_EQUAL(treeset(j, oldToNew[i]), dataset(j, i));