[mlpack-git] master, mlpack-1.0.x: Add MinWidth(), which is a better solution than having the tree calculate it by hand. (9ba5fae)

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

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

On branches: master,mlpack-1.0.x
Link       : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40

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

commit 9ba5fae08337f0d8e4fd9a3702a528c69749287a
Author: Ryan Curtin <ryan at ratml.org>
Date:   Thu Jul 10 14:31:00 2014 +0000

    Add MinWidth(), which is a better solution than having the tree calculate it by
    hand.


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

9ba5fae08337f0d8e4fd9a3702a528c69749287a
 src/mlpack/core/tree/hrectbound.hpp      | 10 +++++++++-
 src/mlpack/core/tree/hrectbound_impl.hpp | 25 ++++++++++++++++++++++---
 2 files changed, 31 insertions(+), 4 deletions(-)

diff --git a/src/mlpack/core/tree/hrectbound.hpp b/src/mlpack/core/tree/hrectbound.hpp
index cb69196..79590f9 100644
--- a/src/mlpack/core/tree/hrectbound.hpp
+++ b/src/mlpack/core/tree/hrectbound.hpp
@@ -60,11 +60,17 @@ class HRectBound
   //! Gets the dimensionality.
   size_t Dim() const { return dim; }
 
-  //! Get the range for a particular dimension.  No bounds checking.
+  //! Get the range for a particular dimension.  No bounds checking.  Be
+  //! careful: this may make MinWidth() invalid.
   math::Range& operator[](const size_t i) { return bounds[i]; }
   //! Modify the range for a particular dimension.  No bounds checking.
   const math::Range& operator[](const size_t i) const { return bounds[i]; }
 
+  //! Get the minimum width of the bound.
+  double MinWidth() const { return minWidth; }
+  //! Modify the minimum width of the bound.
+  double& MinWidth() { return minWidth; }
+
   /**
    * Calculates the centroid of the range, placing it into the given vector.
    *
@@ -166,6 +172,8 @@ class HRectBound
   size_t dim;
   //! The bounds for each dimension.
   math::Range* bounds;
+  //! Cached minimum width of bound.
+  double minWidth;
 };
 
 }; // namespace bound
diff --git a/src/mlpack/core/tree/hrectbound_impl.hpp b/src/mlpack/core/tree/hrectbound_impl.hpp
index 9d3b3ad..862c811 100644
--- a/src/mlpack/core/tree/hrectbound_impl.hpp
+++ b/src/mlpack/core/tree/hrectbound_impl.hpp
@@ -23,7 +23,8 @@ namespace bound {
 template<int Power, bool TakeRoot>
 HRectBound<Power, TakeRoot>::HRectBound() :
     dim(0),
-    bounds(NULL)
+    bounds(NULL),
+    minWidth(0)
 { /* Nothing to do. */ }
 
 /**
@@ -33,7 +34,8 @@ HRectBound<Power, TakeRoot>::HRectBound() :
 template<int Power, bool TakeRoot>
 HRectBound<Power, TakeRoot>::HRectBound(const size_t dimension) :
     dim(dimension),
-    bounds(new math::Range[dim])
+    bounds(new math::Range[dim]),
+    minWidth(0)
 { /* Nothing to do. */ }
 
 /***
@@ -42,7 +44,8 @@ HRectBound<Power, TakeRoot>::HRectBound(const size_t dimension) :
 template<int Power, bool TakeRoot>
 HRectBound<Power, TakeRoot>::HRectBound(const HRectBound& other) :
     dim(other.Dim()),
-    bounds(new math::Range[dim])
+    bounds(new math::Range[dim]),
+    minWidth(other.MinWidth())
 {
   // Copy other bounds over.
   for (size_t i = 0; i < dim; i++)
@@ -70,6 +73,8 @@ HRectBound<Power, TakeRoot>& HRectBound<Power, TakeRoot>::operator=(
   for (size_t i = 0; i < dim; i++)
     bounds[i] = other[i];
 
+  minWidth = other.MinWidth();
+
   return *this;
 }
 
@@ -91,6 +96,7 @@ void HRectBound<Power, TakeRoot>::Clear()
 {
   for (size_t i = 0; i < dim; i++)
     bounds[i] = math::Range();
+  minWidth = 0;
 }
 
 /***
@@ -333,8 +339,14 @@ HRectBound<Power, TakeRoot>& HRectBound<Power, TakeRoot>::operator|=(
   arma::vec mins(min(data, 1));
   arma::vec maxs(max(data, 1));
 
+  minWidth = DBL_MAX;
   for (size_t i = 0; i < dim; i++)
+  {
     bounds[i] |= math::Range(mins[i], maxs[i]);
+    const double width = bounds[i].Hi() - bounds[i].Lo();
+    if (width < minWidth)
+      minWidth = width;
+  }
 
   return *this;
 }
@@ -348,8 +360,14 @@ HRectBound<Power, TakeRoot>& HRectBound<Power, TakeRoot>::operator|=(
 {
   assert(other.dim == dim);
 
+  minWidth = DBL_MAX;
   for (size_t i = 0; i < dim; i++)
+  {
     bounds[i] |= other.bounds[i];
+    const double width = bounds[i].Hi() - bounds[i].Lo();
+    if (width < minWidth)
+      minWidth = width;
+  }
 
   return *this;
 }
@@ -400,6 +418,7 @@ std::string HRectBound<Power, TakeRoot>::ToString() const
   convert << "  Bounds: " << std::endl;
   for (size_t i = 0; i < dim; ++i)
     convert << util::Indent(bounds[i].ToString()) << std::endl;
+  convert << "  Minimum width: " << minWidth << std::endl;
 
   return convert.str();
 }