[mlpack-svn] r10461 - mlpack/trunk/src/mlpack/core/tree
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Wed Nov 30 00:36:17 EST 2011
Author: rcurtin
Date: 2011-11-30 00:36:16 -0500 (Wed, 30 Nov 2011)
New Revision: 10461
Modified:
mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp
mlpack/trunk/src/mlpack/core/tree/binary_space_tree_impl.hpp
mlpack/trunk/src/mlpack/core/tree/hrectbound.hpp
mlpack/trunk/src/mlpack/core/tree/hrectbound_impl.hpp
mlpack/trunk/src/mlpack/core/tree/periodichrectbound.hpp
mlpack/trunk/src/mlpack/core/tree/periodichrectbound_impl.hpp
Log:
Change API to newer standards for HRectBound and BinarySpaceTree. Fix some
formatting issues introduced in r10459.
Modified: mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp 2011-11-30 02:16:36 UTC (rev 10460)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp 2011-11-30 05:36:16 UTC (rev 10461)
@@ -1,5 +1,5 @@
/**
- * @file spacetree.h
+ * @file binary_space_tree.hpp
*
* Definition of generalized binary space partitioning tree (BinarySpaceTree).
*/
@@ -13,9 +13,6 @@
namespace mlpack {
namespace tree /** Trees and tree-building procedures. */ {
-PARAM_MODULE("tree", "Parameters for the binary space partitioning tree.");
-PARAM_INT("leaf_size", "Leaf size used during tree construction.", "tree", 20);
-
/**
* A binary space partitioning tree, such as a KD-tree or a ball tree. Once the
* bound and type of dataset is defined, the tree will construct itself. Call
@@ -36,31 +33,33 @@
*
* @param leaf_size Maximum number of points allowed in each leaf.
*
- * @tparam TBound The bound used for each node. The valid types of bounds and
- * the necessary skeleton interface for this class can be found in bounds/.
- * @tparam TDataset The type of dataset (forced to be arma::mat for now).
- * @tparam TStatistic Extra data contained in the node. See statistic.h for
- * the necessary skeleton interface.
+ * @tparam BoundType The bound used for each node. The valid types of bounds
+ * and the necessary skeleton interface for this class can be found in
+ * bounds/.
+ * @tparam StatisticType Extra data contained in the node. See statistic.hpp
+ * for the necessary skeleton interface.
*/
-template<typename Bound,
- typename Statistic = EmptyStatistic>
+template<typename BoundType,
+ typename StatisticType = EmptyStatistic>
class BinarySpaceTree
{
private:
//! The left child node.
- BinarySpaceTree *left_;
+ BinarySpaceTree *left;
//! The right child node.
- BinarySpaceTree *right_;
+ BinarySpaceTree *right;
//! The index of the first point in the dataset contained in this node (and
//! its children).
- size_t begin_;
+ size_t begin;
//! The number of points of the dataset contained in this node (and its
//! children).
- size_t count_;
+ size_t count;
//! The bound object for this node.
- Bound bound_;
+ BoundType bound;
//! Any extra data contained in the node.
- Statistic stat_;
+ StatisticType stat;
+ //! The leaf size.
+ size_t leafSize;
public:
/**
@@ -68,8 +67,9 @@
* dataset. This will modify the ordering of the points in the dataset!
*
* @param data Dataset to create tree from. This will be modified!
+ * @param leafSize Size of each leaf in the tree.
*/
- BinarySpaceTree(arma::mat& data);
+ BinarySpaceTree(arma::mat& data, const size_t leafSize = 20);
/**
* Construct this as the root node of a binary space tree using the given
@@ -77,12 +77,13 @@
* mapping of the old point indices to the new point indices is filled.
*
* @param data Dataset to create tree from. This will be modified!
- * @param old_from_new Vector which will be filled with the old positions for
+ * @param oldFromNew Vector which will be filled with the old positions for
* each new point.
- * @param new_from_old Vector which will be filled with the new positions for
- * each old point.
+ * @param leafSize Size of each leaf in the tree.
*/
- BinarySpaceTree(arma::mat& data, std::vector<size_t>& old_from_new);
+ BinarySpaceTree(arma::mat& data,
+ std::vector<size_t>& oldFromNew,
+ const size_t leafSize = 20);
/**
* Construct this as the root node of a binary space tree using the given
@@ -91,28 +92,32 @@
* well as a mapping of the new point indices to the old point indices.
*
* @param data Dataset to create tree from. This will be modified!
- * @param old_from_new Vector which will be filled with the old positions for
+ * @param oldFromNew Vector which will be filled with the old positions for
* each new point.
- * @param new_from_old Vector which will be filled with the new positions for
+ * @param newFromOld Vector which will be filled with the new positions for
* each old point.
+ * @param leafSize Size of each leaf in the tree.
*/
BinarySpaceTree(arma::mat& data,
- std::vector<size_t>& old_from_new,
- std::vector<size_t>& new_from_old);
+ std::vector<size_t>& oldFromNew,
+ std::vector<size_t>& newFromOld,
+ const size_t leafSize = 20);
/**
* Construct this node on a subset of the given matrix, starting at column
- * begin_in and using count_in points. The ordering of that subset of points
+ * begin and using count points. The ordering of that subset of points
* will be modified! This is used for recursive tree-building by the other
* constructors which don't specify point indices.
*
* @param data Dataset to create tree from. This will be modified!
- * @param begin_in Index of point to start tree construction with.
- * @param count_in Number of points to use to construct tree.
+ * @param begin Index of point to start tree construction with.
+ * @param count Number of points to use to construct tree.
+ * @param leafSize Size of each leaf in the tree.
*/
BinarySpaceTree(arma::mat& data,
- size_t begin_in,
- size_t count_in);
+ const size_t begin,
+ const size_t count,
+ const size_t leafSize = 20);
/**
* Construct this node on a subset of the given matrix, starting at column
@@ -126,15 +131,17 @@
* reads (and writes) will occur.
*
* @param data Dataset to create tree from. This will be modified!
- * @param begin_in Index of point to start tree construction with.
- * @param count_in Number of points to use to construct tree.
- * @param old_from_new Vector which will be filled with the old positions for
+ * @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 leafSize Size of each leaf in the tree.
*/
BinarySpaceTree(arma::mat& data,
- size_t begin_in,
- size_t count_in,
- std::vector<size_t>& old_from_new);
+ const size_t begin,
+ const size_t count,
+ std::vector<size_t>& oldFromNew,
+ const size_t leafSize = 20);
/**
* Construct this node on a subset of the given matrix, starting at column
@@ -149,18 +156,20 @@
* reads (and writes) will occur.
*
* @param data Dataset to create tree from. This will be modified!
- * @param begin_in Index of point to start tree construction with.
- * @param count_in Number of points to use to construct tree.
- * @param old_from_new Vector which will be filled with the old positions for
+ * @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 new_from_old Vector which will be filled with the new positions for
+ * @param newFromOld Vector which will be filled with the new positions for
* each old point.
+ * @param leafSize Size of each leaf in the tree.
*/
BinarySpaceTree(arma::mat& data,
- size_t begin_in,
- size_t count_in,
- std::vector<size_t>& old_from_new,
- std::vector<size_t>& new_from_old);
+ const size_t begin,
+ const size_t count,
+ std::vector<size_t>& oldFromNew,
+ std::vector<size_t>& newFromOld,
+ const size_t leafSize = 20);
/**
* Create an empty tree node.
@@ -181,12 +190,12 @@
* This is useful for communicating position over the network,
* when pointers would be invalid.
*
- * @param begin_q The begin() of the node to find.
- * @param count_q The count() of the node to find.
+ * @param begin The begin() of the node to find.
+ * @param count The count() of the node to find.
* @return The found node, or NULL if not found.
*/
- const BinarySpaceTree* FindByBeginCount(size_t begin_q,
- size_t count_q) const;
+ const BinarySpaceTree* FindByBeginCount(size_t begin,
+ size_t count) const;
/**
* Find a node in this tree by its begin and count.
@@ -195,79 +204,92 @@
* This is useful for communicating position over the network,
* when pointers would be invalid.
*
- * @param begin_q The begin() of the node to find.
- * @param count_q The count() of the node to find.
+ * @param begin The begin() of the node to find.
+ * @param count The count() of the node to find.
* @return The found node, or NULL if not found.
*/
- BinarySpaceTree* FindByBeginCount(size_t begin_q, size_t count_q);
+ BinarySpaceTree* FindByBeginCount(size_t begin, size_t count);
//! Return the bound object for this node.
- const Bound& bound() const;
+ const BoundType& Bound() const;
//! Return the bound object for this node.
- Bound& bound();
+ BoundType& Bound();
//! Return the statistic object for this node.
- const Statistic& stat() const;
+ const StatisticType& Stat() const;
//! Return the statistic object for this node.
- Statistic& stat();
+ StatisticType& Stat();
//! Return whether or not this node is a leaf (true if it has no children).
- bool is_leaf() const;
+ bool IsLeaf() const;
- //! Fills the tree to the specified level
- size_t ExtendTree(size_t level);
+ //! Return the leaf size.
+ size_t LeafSize() const;
+ //! Fills the tree to the specified level.
+ size_t ExtendTree(const size_t level);
+
/**
* Gets the left child of this node.
*/
- BinarySpaceTree *left() const;
+ BinarySpaceTree* Left() const;
/**
* Gets the right child of this node.
*/
- BinarySpaceTree *right() const;
+ BinarySpaceTree *Right() const;
/**
- * Obtains the number of nodes in the tree, starting with this
- * */
+ * Obtains the number of nodes in the tree, starting with this.
+ */
size_t TreeSize() const;
/**
* Obtains the number of levels below this node in the tree, starting with
- * this
- * */
+ * this.
+ */
size_t TreeDepth() const;
/**
* Gets the index of the beginning point of this subset.
*/
- size_t begin() const;
+ size_t Begin() const;
/**
* Gets the index one beyond the last index in the subset.
*/
- size_t end() const;
+ size_t End() const;
/**
* Gets the number of points in this subset.
*/
- size_t count() const;
+ size_t Count() const;
void Print() const;
private:
- /* hidden copy constructor, available only to fill (pad) the tree to a specified level */
- BinarySpaceTree(size_t begin, size_t count, Bound bound, Statistic stat) :
- left_(NULL),
- right_(NULL),
- begin_(begin),
- count_(count),
- bound_(bound),
- stat_(stat) {}
+ /**
+ * Private copy constructor, available only to fill (pad) the tree to a
+ * specified level.
+ */
+ BinarySpaceTree(const size_t begin,
+ const size_t count,
+ BoundType bound,
+ StatisticType stat,
+ const int leafSize = 20) :
+ left(NULL),
+ right(NULL),
+ begin(begin),
+ count(count),
+ bound(bound),
+ stat(stat),
+ leafSize(leafSize) { }
+
BinarySpaceTree* CopyMe()
{
- return new BinarySpaceTree(begin_,count_,bound_,stat_);
+ return new BinarySpaceTree(begin, count, bound, stat, leafSize);
}
+
/**
* Splits the current node, assigning its left and right children recursively.
*
@@ -280,19 +302,19 @@
* Also returns a list of the changed indices.
*
* @param data Dataset which we are using.
- * @param old_from_new Vector holding permuted indices.
+ * @param oldFromNew Vector holding permuted indices.
*/
- void SplitNode(arma::mat& data, std::vector<size_t>& old_from_new);
+ void SplitNode(arma::mat& data, std::vector<size_t>& oldFromNew);
/**
* Find the index to split on for this node, given that we are splitting in
* the given split dimension on the specified split value.
*
* @param data Dataset which we are using.
- * @param split_dim Dimension of dataset to split on.
- * @param split_val Value to split on, in the given split dimension.
+ * @param splitDim Dimension of dataset to split on.
+ * @param splitVal Value to split on, in the given split dimension.
*/
- size_t GetSplitIndex(arma::mat& data, int split_dim, double split_val);
+ size_t GetSplitIndex(arma::mat& data, int splitDim, double splitVal);
/**
* Find the index to split on for this node, given that we are splitting in
@@ -300,13 +322,12 @@
* list of the changed indices.
*
* @param data Dataset which we are using.
- * @param split_dim Dimension of dataset to split on.
- * @param split_val Value to split on, in the given split dimension.
- * @param old_from_new Vector holding permuted indices.
+ * @param splitDim Dimension of dataset to split on.
+ * @param splitVal Value to split on, in the given split dimension.
+ * @param oldFromNew Vector holding permuted indices.
*/
- size_t GetSplitIndex(arma::mat& data, int split_dim, double split_val,
- std::vector<size_t>& old_from_new);
-
+ size_t GetSplitIndex(arma::mat& data, int splitDim, double splitVal,
+ std::vector<size_t>& oldFromNew);
};
}; // namespace tree
Modified: mlpack/trunk/src/mlpack/core/tree/binary_space_tree_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree_impl.hpp 2011-11-30 02:16:36 UTC (rev 10460)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree_impl.hpp 2011-11-30 05:36:16 UTC (rev 10461)
@@ -17,137 +17,151 @@
// Each of these overloads is kept as a separate function to keep the overhead
// from the two std::vectors out, if possible.
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>::BinarySpaceTree(arma::mat& data) :
- left_(NULL),
- right_(NULL),
- begin_(0), /* This root node starts at index 0, */
- count_(data.n_cols), /* and spans all of the dataset. */
- bound_(data.n_rows),
- stat_()
+template<typename BoundType, typename StatisticType>
+BinarySpaceTree<BoundType, StatisticType>::BinarySpaceTree(
+ arma::mat& data,
+ const size_t leafSize) :
+ left(NULL),
+ right(NULL),
+ begin(0), /* This root node starts at index 0, */
+ count(data.n_cols), /* and spans all of the dataset. */
+ bound(data.n_rows),
+ stat(),
+ leafSize(leafSize)
{
// Do the actual splitting of this node.
SplitNode(data);
}
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>::BinarySpaceTree(
+template<typename BoundType, typename StatisticType>
+BinarySpaceTree<BoundType, StatisticType>::BinarySpaceTree(
arma::mat& data,
- std::vector<size_t>& old_from_new) :
- left_(NULL),
- right_(NULL),
- begin_(0),
- count_(data.n_cols),
- bound_(data.n_rows),
- stat_()
+ std::vector<size_t>& oldFromNew,
+ const size_t leafSize) :
+ left(NULL),
+ right(NULL),
+ begin(0),
+ count(data.n_cols),
+ bound(data.n_rows),
+ stat(),
+ leafSize(leafSize)
{
- // Initialize old_from_new correctly.
- old_from_new.resize(data.n_cols);
+ // Initialize oldFromNew correctly.
+ oldFromNew.resize(data.n_cols);
for (size_t i = 0; i < data.n_cols; i++)
- old_from_new[i] = i; // Fill with unharmed indices.
+ oldFromNew[i] = i; // Fill with unharmed indices.
// Now do the actual splitting.
- SplitNode(data, old_from_new);
+ SplitNode(data, oldFromNew);
}
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>::BinarySpaceTree(
+template<typename BoundType, typename StatisticType>
+BinarySpaceTree<BoundType, StatisticType>::BinarySpaceTree(
arma::mat& data,
- std::vector<size_t>& old_from_new,
- std::vector<size_t>& new_from_old) :
- left_(NULL),
- right_(NULL),
- begin_(0),
- count_(data.n_cols),
- bound_(data.n_rows),
- stat_()
+ std::vector<size_t>& oldFromNew,
+ std::vector<size_t>& newFromOld,
+ const size_t leafSize) :
+ left(NULL),
+ right(NULL),
+ begin(0),
+ count(data.n_cols),
+ bound(data.n_rows),
+ stat(),
+ leafSize(leafSize)
{
- // Initialize the old_from_new vector correctly.
- old_from_new.resize(data.n_cols);
+ // Initialize the oldFromNew vector correctly.
+ oldFromNew.resize(data.n_cols);
for (size_t i = 0; i < data.n_cols; i++)
- old_from_new[i] = i; // Fill with unharmed indices.
+ oldFromNew[i] = i; // Fill with unharmed indices.
// Now do the actual splitting.
- SplitNode(data, old_from_new);
+ SplitNode(data, oldFromNew);
- // Map the new_from_old indices correctly.
- new_from_old.resize(data.n_cols);
+ // Map the newFromOld indices correctly.
+ newFromOld.resize(data.n_cols);
for (size_t i = 0; i < data.n_cols; i++)
- new_from_old[old_from_new[i]] = i;
+ newFromOld[oldFromNew[i]] = i;
}
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>::BinarySpaceTree(
+template<typename BoundType, typename StatisticType>
+BinarySpaceTree<BoundType, StatisticType>::BinarySpaceTree(
arma::mat& data,
- size_t begin_in,
- size_t count_in) :
- left_(NULL),
- right_(NULL),
- begin_(begin_in),
- count_(count_in),
- bound_(data.n_rows),
- stat_()
+ const size_t begin,
+ const size_t count,
+ const size_t leafSize) :
+ left(NULL),
+ right(NULL),
+ begin(begin),
+ count(count),
+ bound(data.n_rows),
+ stat(),
+ leafSize(leafSize)
{
// Perform the actual splitting.
SplitNode(data);
}
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>::BinarySpaceTree(
+template<typename BoundType, typename StatisticType>
+BinarySpaceTree<BoundType, StatisticType>::BinarySpaceTree(
arma::mat& data,
- size_t begin_in,
- size_t count_in,
- std::vector<size_t>& old_from_new) :
- left_(NULL),
- right_(NULL),
- begin_(begin_in),
- count_(count_in),
- bound_(data.n_rows),
- stat_()
+ const size_t begin,
+ const size_t count,
+ std::vector<size_t>& oldFromNew,
+ const size_t leafSize) :
+ left(NULL),
+ right(NULL),
+ begin(begin),
+ count(count),
+ bound(data.n_rows),
+ stat(),
+ leafSize(leafSize)
{
// Hopefully the vector is initialized correctly! We can't check that
// entirely but we can do a minor sanity check.
- Log::Assert(old_from_new.size() == data.n_cols);
+ assert(oldFromNew.size() == data.n_cols);
// Perform the actual splitting.
- SplitNode(data, old_from_new);
+ SplitNode(data, oldFromNew);
}
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>::BinarySpaceTree(
+template<typename BoundType, typename StatisticType>
+BinarySpaceTree<BoundType, StatisticType>::BinarySpaceTree(
arma::mat& data,
- size_t begin_in,
- size_t count_in,
- std::vector<size_t>& old_from_new,
- std::vector<size_t>& new_from_old) :
- left_(NULL),
- right_(NULL),
- begin_(begin_in),
- count_(count_in),
- bound_(data.n_rows),
- stat_()
+ const size_t begin,
+ const size_t count,
+ std::vector<size_t>& oldFromNew,
+ std::vector<size_t>& newFromOld,
+ const size_t leafSize) :
+ left(NULL),
+ right(NULL),
+ begin(begin),
+ count(count),
+ bound(data.n_rows),
+ stat(),
+ leafSize(leafSize)
{
// Hopefully the vector is initialized correctly! We can't check that
// entirely but we can do a minor sanity check.
- Log::Assert(old_from_new.size() == data.n_cols);
+ Log::Assert(oldFromNew.size() == data.n_cols);
// Perform the actual splitting.
- SplitNode(data, old_from_new);
+ SplitNode(data, oldFromNew);
- // Map the new_from_old indices correctly.
- new_from_old.resize(data.n_cols);
+ // Map the newFromOld indices correctly.
+ newFromOld.resize(data.n_cols);
for (size_t i = 0; i < data.n_cols; i++)
- new_from_old[old_from_new[i]] = i;
+ newFromOld[oldFromNew[i]] = i;
}
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>::BinarySpaceTree() :
- left_(NULL),
- right_(NULL),
- begin_(0),
- count_(0),
- bound_(),
- stat_()
+template<typename BoundType, typename StatisticType>
+BinarySpaceTree<BoundType, StatisticType>::BinarySpaceTree() :
+ left(NULL),
+ right(NULL),
+ begin(0),
+ count(0),
+ bound(),
+ stat(),
+ leafSize(20) // Default leaf size is 20.
{
// Nothing to do.
}
@@ -157,13 +171,13 @@
* destructors in turn. This will invalidate any pointers or references to any
* nodes which are children of this one.
*/
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>::~BinarySpaceTree()
+template<typename BoundType, typename StatisticType>
+BinarySpaceTree<BoundType, StatisticType>::~BinarySpaceTree()
{
- if (left_)
- delete left_;
- if (right_)
- delete right_;
+ if (left)
+ delete left;
+ if (right)
+ delete right;
}
/**
@@ -173,27 +187,26 @@
* This is useful for communicating position over the network,
* when pointers would be invalid.
*
- * @param begin_q the begin() of the node to find
- * @param count_q the count() of the node to find
- * @return the found node, or NULL
+ * @param queryBegin The Begin() of the node to find.
+ * @param queryCount The Count() of the node to find.
+ * @return The found node, or NULL if nothing is found.
*/
-template<typename Bound, typename Statistic>
-const BinarySpaceTree<Bound, Statistic>*
-BinarySpaceTree<Bound, Statistic>::FindByBeginCount(size_t begin_q,
- size_t count_q) const
+template<typename BoundType, typename StatisticType>
+const BinarySpaceTree<BoundType, StatisticType>*
+BinarySpaceTree<BoundType, StatisticType>::FindByBeginCount(size_t queryBegin,
+ size_t queryCount) const
{
- mlpack::Log::Assert(begin_q >= begin_);
- mlpack::Log::Assert(count_q <= count_);
- if (begin_ == begin_q && count_ == count_q)
+ Log::Assert(queryBegin >= begin);
+ Log::Assert(queryCount <= count);
+
+ if (begin == queryBegin && count == queryCount)
return this;
- else if (is_leaf())
+ else if (IsLeaf())
return NULL;
- else if (begin_q < left_->end_)
- return left_->FindByBeginCount(begin_q, count_q);
- else if (right_)
- return right_->FindByBeginCount(begin_q, count_q);
+ else if (queryBegin < right->Begin())
+ return left->FindByBeginCount(queryBegin, queryCount);
else
- return NULL;
+ return right->FindByBeginCount(queryBegin, queryCount);
}
/**
@@ -203,25 +216,27 @@
* This is useful for communicating position over the network,
* when pointers would be invalid.
*
- * @param begin_q the begin() of the node to find
- * @param count_q the count() of the node to find
+ * @param queryBegin the Begin() of the node to find
+ * @param queryCount the Count() of the node to find
* @return the found node, or NULL
*/
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>*
-BinarySpaceTree<Bound, Statistic>::FindByBeginCount(size_t begin_q,
- size_t count_q)
+template<typename BoundType, typename StatisticType>
+BinarySpaceTree<BoundType, StatisticType>*
+BinarySpaceTree<BoundType, StatisticType>::FindByBeginCount(
+ const size_t queryBegin,
+ const size_t queryCount)
{
- mlpack::Log::Assert(begin_q >= begin_);
- mlpack::Log::Assert(count_q <= count_);
- if (begin_ == begin_q && count_ == count_q)
+ mlpack::Log::Assert(begin >= queryBegin);
+ mlpack::Log::Assert(count <= queryCount);
+
+ if (begin == queryBegin && count == queryCount)
return this;
- else if (is_leaf())
+ else if (IsLeaf())
return NULL;
- else if (begin_q < left_->end_)
- return left_->FindByBeginCount(begin_q, count_q);
- else if (right_)
- return right_->FindByBeginCount(begin_q, count_q);
+ else if (queryBegin < left->End())
+ return left->FindByBeginCount(queryBegin, queryCount);
+ else if (right)
+ return right->FindByBeginCount(queryBegin, queryCount);
else
return NULL;
}
@@ -230,19 +245,19 @@
size_t BinarySpaceTree<Bound, Statistic>::ExtendTree(size_t level)
{
--level;
- /* return the number of nodes duplicated */
+ // Return the number of nodes duplicated.
size_t nodesDuplicated = 0;
if (level > 0)
{
- if (!left_)
+ if (!left)
{
- left_ = CopyMe();
+ left = CopyMe();
++nodesDuplicated;
}
- nodesDuplicated += left_->ExtendTree(level);
- if (right_)
+ nodesDuplicated += left->ExtendTree(level);
+ if (right)
{
- nodesDuplicated += right_->ExtendTree(level);
+ nodesDuplicated += right->ExtendTree(level);
}
}
return nodesDuplicated;
@@ -259,257 +274,225 @@
template<typename Bound, typename Statistic>
size_t BinarySpaceTree<Bound, Statistic>::TreeSize() const
{
- size_t size = 1;
- if (is_leaf())
- {
- return size;
- }
- else
- {
- size += this->left()->TreeSize();
- if (right_)
- {
- size += this->right()->TreeSize();
- }
- }
- return size;
+ // Recursively count the nodes on each side of the tree. The plus one is
+ // because we have to count this node, too.
+ return 1 + (left ? left->TreeSize() : 0) + (right ? right->TreeSize() : 0);
}
template<typename Bound, typename Statistic>
size_t BinarySpaceTree<Bound, Statistic>::TreeDepth() const
{
- size_t levels = 1;
- if (is_leaf())
- {
- return levels;
- }
- else
- {
- size_t rightLevels = 0;
- if (right_)
- {
- rightLevels = right_->TreeDepth();
- }
- size_t leftLevels = left_->TreeDepth();
- if (leftLevels > rightLevels)
- {
- levels += leftLevels;
- }
- else
- {
- levels += rightLevels;
- }
- }
- return levels;
+ // Recursively count the depth on each side of the tree. The plus one is
+ // because we have to count this node, too.
+ return 1 + std::max((left ? left->TreeDepth() : 0),
+ (right ? right->TreeDepth() : 0));
}
-template<typename Bound, typename Statistic>
-inline const Bound& BinarySpaceTree<Bound, Statistic>::bound() const
+template<typename BoundType, typename StatisticType>
+inline const BoundType& BinarySpaceTree<BoundType, StatisticType>::Bound() const
{
- return bound_;
+ return bound;
}
-template<typename Bound, typename Statistic>
-inline Bound& BinarySpaceTree<Bound, Statistic>::bound()
+template<typename BoundType, typename StatisticType>
+inline BoundType& BinarySpaceTree<BoundType, StatisticType>::Bound()
{
- return bound_;
+ return bound;
}
-template<typename Bound, typename Statistic>
-inline const Statistic& BinarySpaceTree<Bound, Statistic>::stat() const
+template<typename BoundType, typename StatisticType>
+inline const StatisticType& BinarySpaceTree<BoundType, StatisticType>::Stat()
+ const
{
- return stat_;
+ return stat;
}
-template<typename Bound, typename Statistic>
-inline Statistic& BinarySpaceTree<Bound, Statistic>::stat()
+template<typename BoundType, typename StatisticType>
+inline StatisticType& BinarySpaceTree<BoundType, StatisticType>::Stat()
{
- return stat_;
+ return stat;
}
-template<typename Bound, typename Statistic>
-inline bool BinarySpaceTree<Bound, Statistic>::is_leaf() const
+template<typename BoundType, typename StatisticType>
+inline bool BinarySpaceTree<BoundType, StatisticType>::IsLeaf() const
{
- return !left_;
+ return !left;
}
/**
* Gets the left branch of the tree.
*/
-template<typename Bound, typename Statistic>
-inline BinarySpaceTree<Bound, Statistic>*
-BinarySpaceTree<Bound, Statistic>::left() const
+template<typename BoundType, typename StatisticType>
+inline BinarySpaceTree<BoundType, StatisticType>*
+BinarySpaceTree<BoundType, StatisticType>::Left() const
{
- return left_;
+ return left;
}
/**
* Gets the right branch.
*/
-template<typename Bound, typename Statistic>
-inline BinarySpaceTree<Bound, Statistic>*
-BinarySpaceTree<Bound, Statistic>::right() const
+template<typename BoundType, typename StatisticType>
+inline BinarySpaceTree<BoundType, StatisticType>*
+BinarySpaceTree<BoundType, StatisticType>::Right() const
{
- return right_;
+ return right;
}
/**
* Gets the index of the begin point of this subset.
*/
-template<typename Bound, typename Statistic>
-inline size_t BinarySpaceTree<Bound, Statistic>::begin() const
+template<typename BoundType, typename StatisticType>
+inline size_t BinarySpaceTree<BoundType, StatisticType>::Begin() const
{
- return begin_;
+ return begin;
}
/**
* Gets the index one beyond the last index in the series.
*/
-template<typename Bound, typename Statistic>
-inline size_t BinarySpaceTree<Bound, Statistic>::end() const
+template<typename BoundType, typename StatisticType>
+inline size_t BinarySpaceTree<BoundType, StatisticType>::End() const
{
- return begin_ + count_;
+ return begin + count;
}
/**
* Gets the number of points in this subset.
*/
-template<typename Bound, typename Statistic>
-inline size_t BinarySpaceTree<Bound, Statistic>::count() const
+template<typename BoundType, typename StatisticType>
+inline size_t BinarySpaceTree<BoundType, StatisticType>::Count() const
{
- return count_;
+ return count;
}
-template<typename Bound, typename Statistic>
-void BinarySpaceTree<Bound, Statistic>::Print() const {
- printf("node: %d to %d: %d points total\n",
- begin_, begin_ + count_ - 1, count_);
- if (!is_leaf())
- {
- left_->Print();
- if (right_)
- {
- right_->Print();
- }
- }
+template<typename BoundType, typename StatisticType>
+void BinarySpaceTree<BoundType, StatisticType>::Print() const
+{
+ printf("node: %d to %d: %d points total\n", begin, begin + count - 1,
+ count);
+ if (left)
+ left->Print();
+ if (right)
+ right->Print();
}
-template<typename Bound, typename Statistic>
-void BinarySpaceTree<Bound, Statistic>::SplitNode(arma::mat& data)
+template<typename BoundType, typename StatisticType>
+void BinarySpaceTree<BoundType, StatisticType>::SplitNode(arma::mat& data)
{
// This should be a single function for Bound.
// We need to expand the bounds of this node properly.
- for (size_t i = begin_; i < (begin_ + count_); i++)
- bound_ |= data.unsafe_col(i);
+ for (size_t i = begin; i < (begin + count); i++)
+ bound |= data.unsafe_col(i);
// Now, check if we need to split at all.
- if (count_ <= (size_t) CLI::GetParam<int>("tree/leaf_size"))
+ if (count <= leafSize)
return; // We can't split this.
// Figure out which dimension to split on.
- size_t split_dim = data.n_rows; // Indicate invalid by max_dim + 1.
- double max_width = -1;
+ size_t splitDim = data.n_rows; // Indicate invalid by maxDim + 1.
+ double maxWidth = -1;
// Find the split dimension.
for (size_t d = 0; d < data.n_rows; d++)
{
- double width = bound_[d].width();
+ double width = bound[d].Width();
- if (width > max_width)
+ if (width > maxWidth)
{
- max_width = width;
- split_dim = d;
+ maxWidth = width;
+ splitDim = d;
}
}
- if (max_width == 0) // All these points are the same. We can't split.
+ // Split in the middle of that dimension.
+ double splitVal = bound[splitDim].Mid();
+
+ if (maxWidth == 0) // All these points are the same. We can't split.
return;
- double split_value = bound_[split_dim].mid();
-
// Perform the actual splitting. This will order the dataset such that points
- // with value in dimension split_dim less than or equal to split_value are on
- // the left of split_col, and points with value in dimension split_dim greater
- // than split_value are on the right side of split_col.
- size_t split_col = GetSplitIndex(data, split_dim, split_value);
+ // with value in dimension split_dim less than or equal to splitVal are on
+ // the left of splitCol, and points with value in dimension splitDim greater
+ // than splitVal are on the right side of splitCol.
+ size_t splitCol = GetSplitIndex(data, splitDim, splitVal);
+
// Now that we know the split column, we will recursively split the children
// by calling their constructors (which perform this splitting process).
- left_ = new BinarySpaceTree<Bound, Statistic>(data, begin_,
- split_col - begin_);
- right_ = new BinarySpaceTree<Bound, Statistic>(data, split_col,
- begin_ + count_ - split_col);
+ left = new BinarySpaceTree<BoundType, StatisticType>(data, begin,
+ splitCol - begin, leafSize);
+ right = new BinarySpaceTree<BoundType, StatisticType>(data, splitCol,
+ begin + count - splitCol, leafSize);
}
-template<typename Bound, typename Statistic>
-void BinarySpaceTree<Bound, Statistic>::SplitNode(
+template<typename BoundType, typename StatisticType>
+void BinarySpaceTree<BoundType, StatisticType>::SplitNode(
arma::mat& data,
- std::vector<size_t>& old_from_new)
+ std::vector<size_t>& oldFromNew)
{
// This should be a single function for Bound.
// We need to expand the bounds of this node properly.
- for (size_t i = begin_; i < (begin_ + count_); i++)
- bound_ |= data.unsafe_col(i);
+ for (size_t i = begin; i < (begin + count); i++)
+ bound |= data.unsafe_col(i);
// First, check if we need to split at all.
- if (count_ <= (size_t) CLI::GetParam<int>("tree/leaf_size"))
+ if (count <= leafSize)
return; // We can't split this.
// Figure out which dimension to split on.
- size_t split_dim = data.n_rows; // Indicate invalid by max_dim + 1.
- double max_width = -DBL_MAX;
+ size_t splitDim = data.n_rows; // Indicate invalid by max_dim + 1.
+ double maxWidth = -1;
// Find the split dimension.
for (size_t d = 0; d < data.n_rows; d++)
{
- double width = bound_[d].width();
+ double width = bound[d].Width();
- if (width > max_width)
+ if (width > maxWidth)
{
- max_width = width;
- split_dim = d;
+ maxWidth = width;
+ splitDim = d;
}
}
- if (max_width == 0) // All these points are the same. We can't split.
- return;
-
// Split in the middle of that dimension.
- size_t split_col = -1;
- double split_value = -DBL_MAX;
+ double splitVal = bound[splitDim].Mid();
- split_value = bound_[split_dim].mid();
+ if (maxWidth == 0) // All these points are the same. We can't split.
+ return;
+
// Perform the actual splitting. This will order the dataset such that points
- // with value in dimension split_dim less than or equal to split_value are on
- // the left of split_col, and points with value in dimension split_dim greater
- // than split_value are on the right side of split_col.
- split_col = GetSplitIndex(data, split_dim, split_value, old_from_new);
+ // with value in dimension split_dim less than or equal to splitVal are on
+ // the left of splitCol, and points with value in dimension splitDim greater
+ // than splitVal are on the right side of splitCol.
+ size_t splitCol = GetSplitIndex(data, splitDim, splitVal, oldFromNew);
// Now that we know the split column, we will recursively split the children
// by calling their constructors (which perform this splitting process).
- left_ = new BinarySpaceTree<Bound, Statistic>(data, begin_,
- split_col - begin_, old_from_new);
- right_ = new BinarySpaceTree<Bound, Statistic>(data, split_col,
- begin_ + count_ - split_col, old_from_new);
+ left = new BinarySpaceTree<BoundType, StatisticType>(data, begin,
+ splitCol - begin, oldFromNew, leafSize);
+ right = new BinarySpaceTree<BoundType, StatisticType>(data, splitCol,
+ begin + count - splitCol, oldFromNew, leafSize);
}
-template<typename Bound, typename Statistic>
-size_t BinarySpaceTree<Bound, Statistic>::GetSplitIndex(
+template<typename BoundType, typename StatisticType>
+size_t BinarySpaceTree<BoundType, StatisticType>::GetSplitIndex(
arma::mat& data,
- int split_dim,
- double split_val)
+ int splitDim,
+ double splitVal)
{
// This method modifies the input dataset. We loop both from the left and
// right sides of the points contained in this node. The points less than
// split_val should be on the left side of the matrix, and the points greater
// than split_val should be on the right side of the matrix.
- size_t left = begin_;
- size_t right = begin_ + count_ - 1;
+ size_t left = begin;
+ size_t right = begin + count - 1;
// First half-iteration of the loop is out here because the termination
// condition is in the middle.
- while ((data(split_dim, left) < split_val) && (left <= right))
+ while ((data(splitDim, left) < splitVal) && (left <= right))
left++;
- while ((data(split_dim, right) >= split_val) && (left <= right))
+ while ((data(splitDim, right) >= splitVal) && (left <= right))
right--;
while(left <= right)
@@ -520,14 +503,14 @@
// See how many points on the left are correct. When they are correct,
// increase the left counter accordingly. When we encounter one that isn't
// correct, stop. We will switch it later.
- while ((data(split_dim, left) < split_val) && (left <= right))
+ while ((data(splitDim, left) < splitVal) && (left <= right))
left++;
// Now see how many points on the right are correct. When they are correct,
// decrease the right counter accordingly. When we encounter one that isn't
// correct, stop. We will switch it with the wrong point we found in the
// previous loop.
- while ((data(split_dim, right) >= split_val) && (left <= right))
+ while ((data(splitDim, right) >= splitVal) && (left <= right))
right--;
}
@@ -536,25 +519,25 @@
return left;
}
-template<typename Bound, typename Statistic>
-size_t BinarySpaceTree<Bound, Statistic>::GetSplitIndex(
+template<typename BoundType, typename StatisticType>
+size_t BinarySpaceTree<BoundType, StatisticType>::GetSplitIndex(
arma::mat& data,
- int split_dim,
- double split_val,
- std::vector<size_t>& old_from_new)
+ int splitDim,
+ double splitVal,
+ std::vector<size_t>& oldFromNew)
{
// This method modifies the input dataset. We loop both from the left and
// right sides of the points contained in this node. The points less than
// split_val should be on the left side of the matrix, and the points greater
// than split_val should be on the right side of the matrix.
- size_t left = begin_;
- size_t right = begin_ + count_ -1;
+ size_t left = begin;
+ size_t right = begin + count - 1;
// First half-iteration of the loop is out here because the termination
// condition is in the middle.
- while ((data(split_dim, left) < split_val) && (left <= right))
+ while ((data(splitDim, left) < splitVal) && (left <= right))
left++;
- while ((data(split_dim, right) >= split_val) && (left <= right))
+ while ((data(splitDim, right) >= splitVal) && (left <= right))
right--;
while(left <= right)
@@ -563,21 +546,21 @@
data.swap_cols(left, right);
// Update the indices for what we changed.
- size_t t = old_from_new[left];
- old_from_new[left] = old_from_new[right];
- old_from_new[right] = t;
+ size_t t = oldFromNew[left];
+ oldFromNew[left] = oldFromNew[right];
+ oldFromNew[right] = t;
// See how many points on the left are correct. When they are correct,
// increase the left counter accordingly. When we encounter one that isn't
// correct, stop. We will switch it later.
- while ((data(split_dim, left) < split_val) && (left <= right))
+ while ((data(splitDim, left) < splitVal) && (left <= right))
left++;
// Now see how many points on the right are correct. When they are correct,
// decrease the right counter accordingly. When we encounter one that isn't
// correct, stop. We will switch it with the wrong point we found in the
// previous loop.
- while ((data(split_dim, right) >= split_val) && (left <= right))
+ while ((data(splitDim, right) >= splitVal) && (left <= right))
right--;
}
Modified: mlpack/trunk/src/mlpack/core/tree/hrectbound.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/hrectbound.hpp 2011-11-30 02:16:36 UTC (rev 10460)
+++ mlpack/trunk/src/mlpack/core/tree/hrectbound.hpp 2011-11-30 05:36:16 UTC (rev 10461)
@@ -35,7 +35,7 @@
* Initializes to specified dimensionality with each dimension the empty
* set.
*/
- HRectBound(size_t dimension);
+ HRectBound(const size_t dimension);
/***
* Copy constructor; necessary to prevent memory leaks.
@@ -55,13 +55,13 @@
void Clear();
/** Gets the dimensionality */
- size_t dim() const { return dim_; }
+ size_t Dim() const { return dim; }
/**
* Sets and gets the range for a particular dimension.
*/
- math::Range& operator[](size_t i);
- const math::Range operator[](size_t i) const;
+ math::Range& operator[](const size_t i);
+ const math::Range& operator[](const size_t i) const;
/**
* Calculates the centroid of the range, placing it into the given vector.
@@ -140,8 +140,8 @@
bool Contains(const arma::vec& point) const;
private:
- size_t dim_;
- math::Range *bounds_;
+ size_t dim;
+ math::Range* bounds;
};
}; // namespace bound
Modified: mlpack/trunk/src/mlpack/core/tree/hrectbound_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/hrectbound_impl.hpp 2011-11-30 02:16:36 UTC (rev 10460)
+++ mlpack/trunk/src/mlpack/core/tree/hrectbound_impl.hpp 2011-11-30 05:36:16 UTC (rev 10461)
@@ -24,8 +24,8 @@
*/
template<int t_pow>
HRectBound<t_pow>::HRectBound() :
- dim_(0),
- bounds_(NULL)
+ dim(0),
+ bounds(NULL)
{ /* nothing to do */ }
/**
@@ -33,9 +33,9 @@
* set.
*/
template<int t_pow>
-HRectBound<t_pow>::HRectBound(size_t dimension) :
- dim_(dimension),
- bounds_(new math::Range[dim_])
+HRectBound<t_pow>::HRectBound(const size_t dimension) :
+ dim(dimension),
+ bounds(new math::Range[dim])
{ /* nothing to do */ }
/***
@@ -43,12 +43,12 @@
*/
template<int t_pow>
HRectBound<t_pow>::HRectBound(const HRectBound& other) :
- dim_(other.dim()),
- bounds_(new math::Range[dim_])
+ dim(other.Dim()),
+ bounds(new math::Range[dim])
{
// Copy other bounds over.
- for (size_t i = 0; i < dim_; i++)
- bounds_[i] = other[i];
+ for (size_t i = 0; i < dim; i++)
+ bounds[i] = other[i];
}
/***
@@ -57,15 +57,15 @@
template<int t_pow>
HRectBound<t_pow>& HRectBound<t_pow>::operator=(const HRectBound& other)
{
- if (bounds_)
- delete[] bounds_;
+ if (bounds)
+ delete[] bounds;
// We can't just copy the bounds_ pointer like the default copy constructor
// will!
- dim_ = other.dim();
- bounds_ = new math::Range[dim_];
- for (size_t i = 0; i < dim_; i++)
- bounds_[i] = other[i];
+ dim = other.Dim();
+ bounds = new math::Range[dim];
+ for (size_t i = 0; i < dim; i++)
+ bounds[i] = other[i];
return *this;
}
@@ -76,8 +76,8 @@
template<int t_pow>
HRectBound<t_pow>::~HRectBound()
{
- if (bounds_)
- delete[] bounds_;
+ if (bounds)
+ delete[] bounds;
}
/**
@@ -86,26 +86,26 @@
template<int t_pow>
void HRectBound<t_pow>::Clear()
{
- for (size_t i = 0; i < dim_; i++)
- bounds_[i] = math::Range();
+ for (size_t i = 0; i < dim; i++)
+ bounds[i] = math::Range();
}
/**
* Gets the range for a particular dimension.
*/
template<int t_pow>
-const math::Range HRectBound<t_pow>::operator[](size_t i) const
+inline const math::Range& HRectBound<t_pow>::operator[](const size_t i) const
{
- return bounds_[i];
+ return bounds[i];
}
/**
* Sets the range for the given dimension.
*/
template<int t_pow>
-math::Range& HRectBound<t_pow>::operator[](size_t i)
+inline math::Range& HRectBound<t_pow>::operator[](const size_t i)
{
- return bounds_[i];
+ return bounds[i];
}
/***
@@ -117,11 +117,11 @@
void HRectBound<t_pow>::Centroid(arma::vec& centroid) const
{
// set size correctly if necessary
- if (!(centroid.n_elem == dim_))
- centroid.set_size(dim_);
+ if (!(centroid.n_elem == dim))
+ centroid.set_size(dim);
- for (size_t i = 0; i < dim_; i++)
- centroid(i) = bounds_[i].mid();
+ for (size_t i = 0; i < dim; i++)
+ centroid(i) = bounds[i].Mid();
}
/**
@@ -130,25 +130,25 @@
template<int t_pow>
double HRectBound<t_pow>::MinDistance(const arma::vec& point) const
{
- Log::Assert(point.n_elem == dim_);
+ Log::Assert(point.n_elem == dim);
double sum = 0;
double lower, higher;
- for (size_t dimension = 0; dimension < dim_; dimension++)
+ for (size_t d = 0; d < dim; d++)
{
- lower = bounds_[dimension].lo - point[dimension];
- higher = point[dimension] - bounds_[dimension].hi;
+ lower = bounds[d].lo - point[d];
+ higher = point[d] - bounds[d].hi;
- // since only one of 'lower' or 'higher' is negative, if we add each's
+ // Since only one of 'lower' or 'higher' is negative, if we add each's
// absolute value to itself and then sum those two, our result is the
- // nonnegative half of the equation times two; then we raise to power t_pow
+ // nonnegative half of the equation times two; then we raise to power t_pow.
sum += pow((lower + fabs(lower)) + (higher + fabs(higher)), (double) t_pow);
}
- // now take the t_pow'th root (but make sure our result is squared); then
+ // Now take the t_pow'th root (but make sure our result is squared); then
// divide by four to cancel out the constant of 2 (which has been squared now)
- // that was introduced earlier
+ // that was introduced earlier.
return pow(sum, 2.0 / (double) t_pow) / 4.0;
}
@@ -160,7 +160,7 @@
double HRectBound<t_pow>::MinDistance(const arma::vec& point,
const std::vector<size_t>& indices) const
{
- Log::Assert(point.n_elem == dim_);
+ Log::Assert(point.n_elem == dim);
double sum = 0.0;
@@ -168,20 +168,21 @@
for (size_t index = 0; index < indices.size(); index++)
{
size_t dimension = indices[index];
- lower = bounds_[dimension].lo - point[dimension];
- higher = point[dimension] - bounds_[dimension].hi;
+ lower = bounds[dimension].lo - point[dimension];
+ higher = point[dimension] - bounds[dimension].hi;
- // since at least one of 'lower' or 'higher' is negative, if we add each's
+ // Since at least one of 'lower' or 'higher' is negative, if we add each's
// absolute value to itself and then sum those two, our result is the
- // nonnegative half of the equation times two; then we raise to power t_pow
+ // nonnegative half of the equation times two; then we raise to power t_pow.
sum += pow((lower + fabs(lower)) + (higher + fabs(higher)), (double) t_pow);
}
- // now take the t_pow'th root (but make sure our result is squared); then
+ // Now take the t_pow'th root (but make sure our result is squared); then
// divide by four to cancel out the constant of 2 (which has been squared now)
- // that was introduced earlier
+ // that was introduced earlier.
return pow(sum, 2.0 / (double) t_pow) / 4.0;
}
+
/**
* Calculates minimum bound-to-bound squared distance.
*
@@ -190,28 +191,32 @@
template<int t_pow>
double HRectBound<t_pow>::MinDistance(const HRectBound& other) const
{
- Log::Assert(dim_ == other.dim_);
+ Log::Assert(dim == other.dim);
- double sum = 0.0;
- double lower = 0.0;
- double higher = 0.0;
+ double sum = 0;
+ const math::Range* mbound = bounds;
+ const math::Range* obound = other.bounds;
- for(size_t dimension = 0; dimension < dim_; dimension++)
+ double lower, higher;
+ for (size_t d = 0; d < dim; d++)
{
- lower = bounds_[dimension].lo - other.bounds_[dimension].hi;
- higher = other.bounds_[dimension].lo - bounds_[dimension].hi;
+ lower = obound->lo - mbound->hi;
+ higher = mbound->lo - obound->hi;
+ // We invoke the following:
+ // x + fabs(x) = max(x * 2, 0)
+ // (x * 2)^2 / 4 = x^2
+ sum += pow((lower + fabs(lower)) + (higher + fabs(higher)), (double) t_pow);
- // since at least one of 'lower' or 'higher' is negative, if we add each's
- // absolute value to itself and then sum those two, our result is the
- // nonnegative half of the equation times two; then we raise to power t_pow
- sum += pow((lower + fabs(lower)) + (higher + fabs(higher)), (double) t_pow);
+ // Move bound pointers.
+ mbound++;
+ obound++;
}
return pow(sum, 2.0 / (double) t_pow) / 4.0;
}
+
/**
- * Calculates minimum bound-to-bound squared distance,
- * filtered by indices.
+ * Calculates minimum bound-to-bound squared distance, filtered by indices.
*
* Example: bound1.MinDistanceSq(other, indices) for minimum squared distance.
*/
@@ -219,21 +224,20 @@
double HRectBound<t_pow>::MinDistance(const HRectBound& other,
const std::vector<size_t>& indices) const
{
- Log::Assert(dim_ == other.dim_);
+ Log::Assert(dim == other.dim);
double sum = 0.0;
- double lower = 0.0;
- double higher = 0.0;
+ double lower, higher;
- for(size_t index = 0; index < indices.size(); index++)
+ for (size_t index = 0; index < indices.size(); index++)
{
size_t dimension = indices[index];
- lower = bounds_[dimension].lo - other.bounds_[dimension].hi;
- higher = other.bounds_[dimension].lo - bounds_[dimension].hi;
+ lower = bounds[dimension].lo - other.bounds[dimension].hi;
+ higher = other.bounds[dimension].lo - bounds[dimension].hi;
- // since only one of 'lower' or 'higher' is negative, if we add each's
+ // Since only one of 'lower' or 'higher' is negative, if we add each's
// absolute value to itself and then sum those two, our result is the
- // nonnegative half of the equation times two; then we raise to power t_pow
+ // nonnegative half of the equation times two; then we raise to power t_pow.
sum += pow((lower + fabs(lower)) + (higher + fabs(higher)), (double) t_pow);
}
@@ -246,24 +250,22 @@
template<int t_pow>
double HRectBound<t_pow>::MaxDistance(const arma::vec& point) const
{
- double sum = 0.0;
- double lower, higher;
+ double sum = 0;
- Log::Assert(point.n_elem == dim_);
+ Log::Assert(point.n_elem == dim);
- for (size_t dimension = 0; dimension < dim_; dimension++)
+ for (size_t d = 0; d < dim; d++)
{
- lower = fabs(point[dimension] - bounds_[dimension].lo);
- higher = fabs(point[dimension] - bounds_[dimension].hi);
-
- sum += pow(fabs(higher-lower) + higher + lower, (double) t_pow);
+ double v = fabs(std::max(point[d] - bounds[d].lo,
+ bounds[d].hi - point[d]));
+ sum += pow(v, (double) t_pow);
}
- return pow(sum, 2.0 / (double) t_pow) / 4.0;
+ return pow(sum, 2.0 / (double) t_pow);
}
+
/**
- * Calculates maximum bound-to-point squared distance,
- * filtered by indices.
+ * Calculates maximum bound-to-point squared distance, filtered by indices.
*/
template<int t_pow>
double HRectBound<t_pow>::MaxDistance(const arma::vec& point,
@@ -272,15 +274,15 @@
double sum = 0.0;
double lower, higher;
- Log::Assert(point.n_elem == dim_);
+ Log::Assert(point.n_elem == dim);
for (size_t index = 0; index < indices.size(); index++)
{
size_t dimension = indices[index];
- lower = fabs(point[dimension] - bounds_[dimension].lo);
- higher = fabs(point[dimension] - bounds_[dimension].hi);
+ lower = fabs(point[dimension] - bounds[dimension].lo);
+ higher = fabs(point[dimension] - bounds[dimension].hi);
- sum += pow(fabs(higher-lower) + higher + lower, (double) t_pow);
+ sum += pow(fabs(higher - lower) + higher + lower, (double) t_pow);
}
return pow(sum, 2.0 / (double) t_pow) / 4.0;
@@ -292,20 +294,19 @@
template<int t_pow>
double HRectBound<t_pow>::MaxDistance(const HRectBound& other) const
{
- double sum = 0.0;
- double lower, higher;
+ double sum = 0;
- Log::Assert(other.dim_ == dim_);
+ Log::Assert(dim == other.dim);
- for (size_t dimension = 0; dimension < dim_; dimension++)
+ double v;
+ for (size_t d = 0; d < dim; d++)
{
- lower = fabs(other.bounds_[dimension].hi - bounds_[dimension].lo);
- higher = fabs(other.bounds_[dimension].lo - bounds_[dimension].hi);
-
- sum += pow(fabs(higher-lower) + higher + lower, (double) t_pow);
+ v = fabs(std::max(other.bounds[d].hi - bounds[d].lo,
+ bounds[d].hi - other.bounds[d].lo));
+ sum += pow(v, (double) t_pow); // v is non-negative.
}
- return pow(sum, 2.0 / (double) t_pow) / 4.0;
+ return pow(sum, 2.0 / (double) t_pow);
}
/**
@@ -319,53 +320,54 @@
double sum = 0.0;
double lower, higher;
- Log::Assert(other.dim_ == dim_);
+ Log::Assert(other.dim == dim);
for (size_t index = 0; index < indices.size(); index++)
{
size_t dimension = indices[index];
- lower = fabs(other.bounds_[dimension].hi - bounds_[dimension].lo);
- higher = fabs(other.bounds_[dimension].lo - bounds_[dimension].hi);
+ lower = fabs(other.bounds[dimension].hi - bounds[dimension].lo);
+ higher = fabs(other.bounds[dimension].lo - bounds[dimension].hi);
sum += pow(fabs(higher-lower) + higher + lower, (double) t_pow);
}
return pow(sum, 2.0 / (double) t_pow) / 4.0;
}
+
/**
* Calculates minimum and maximum bound-to-bound squared distance.
*/
template<int t_pow>
math::Range HRectBound<t_pow>::RangeDistance(const HRectBound& other) const
{
- double sum_lo = 0;
- double sum_hi = 0;
+ double loSum = 0;
+ double hiSum = 0;
- Log::Assert(dim_ == other.dim_);
+ Log::Assert(dim == other.dim);
- double v1, v2, v_lo, v_hi;
- for (size_t d = 0; d < dim_; d++)
+ double v1, v2, vLo, vHi;
+ for (size_t d = 0; d < dim; d++)
{
- v1 = other.bounds_[d].lo - bounds_[d].hi;
- v2 = bounds_[d].lo - other.bounds_[d].hi;
+ v1 = other.bounds[d].lo - bounds[d].hi;
+ v2 = bounds[d].lo - other.bounds[d].hi;
// One of v1 or v2 is negative.
if (v1 >= v2)
{
- v_hi = -v2; // Make it nonnegative.
- v_lo = (v1 > 0) ? v1 : 0; // Force to be 0 if negative.
+ vHi = -v2; // Make it nonnegative.
+ vLo = (v1 > 0) ? v1 : 0; // Force to be 0 if negative.
}
else
{
- v_hi = -v1; // Make it nonnegative.
- v_lo = (v2 > 0) ? v2 : 0; // Force to be 0 if negative.
+ vHi = -v1; // Make it nonnegative.
+ vLo = (v2 > 0) ? v2 : 0; // Force to be 0 if negative.
}
- sum_lo += pow(v_lo, (double) t_pow);
- sum_hi += pow(v_hi, (double) t_pow);
+ loSum += pow(vLo, (double) t_pow);
+ hiSum += pow(vHi, (double) t_pow);
}
- return math::Range(pow(sum_lo, 2.0 / (double) t_pow),
- pow(sum_hi, 2.0 / (double) t_pow));
+ return math::Range(pow(loSum, 2.0 / (double) t_pow),
+ pow(hiSum, 2.0 / (double) t_pow));
}
/**
@@ -374,42 +376,42 @@
template<int t_pow>
math::Range HRectBound<t_pow>::RangeDistance(const arma::vec& point) const
{
- double sum_lo = 0;
- double sum_hi = 0;
+ double loSum = 0;
+ double hiSum = 0;
- Log::Assert(point.n_elem == dim_);
+ Log::Assert(point.n_elem == dim);
- double v1, v2, v_lo, v_hi;
- for(size_t d = 0; d < dim_; d++)
+ double v1, v2, vLo, vHi;
+ for (size_t d = 0; d < dim; d++)
{
- v1 = bounds_[d].lo - point[d]; // Negative if point[d] > lo.
- v2 = point[d] - bounds_[d].hi; // Negative if point[d] < hi.
+ v1 = bounds[d].lo - point[d]; // Negative if point[d] > lo.
+ v2 = point[d] - bounds[d].hi; // Negative if point[d] < hi.
// One of v1 or v2 (or both) is negative.
if (v1 >= 0) // point[d] <= bounds_[d].lo.
{
- v_hi = -v2; // v2 will be larger but must be negated.
- v_lo = v1;
+ vHi = -v2; // v2 will be larger but must be negated.
+ vLo = v1;
}
else // point[d] is between lo and hi, or greater than hi.
{
if (v2 >= 0)
{
- v_hi = -v1; // v1 will be larger, but must be negated.
- v_lo = v2;
+ vHi = -v1; // v1 will be larger, but must be negated.
+ vLo = v2;
}
else
{
- v_hi = -std::min(v1, v2); // Both are negative, but we need the larger.
- v_lo = 0;
+ vHi = -std::min(v1, v2); // Both are negative, but we need the larger.
+ vLo = 0;
}
}
- sum_lo += pow(v_lo, (double) t_pow);
- sum_hi += pow(v_hi, (double) t_pow);
+ loSum += pow(vLo, (double) t_pow);
+ hiSum += pow(vHi, (double) t_pow);
}
- return math::Range(pow(sum_lo, 2.0 / (double) t_pow),
- pow(sum_hi, 2.0 / (double) t_pow));
+ return math::Range(pow(loSum, 2.0 / (double) t_pow),
+ pow(hiSum, 2.0 / (double) t_pow));
}
/**
@@ -418,10 +420,10 @@
template<int t_pow>
HRectBound<t_pow>& HRectBound<t_pow>::operator|=(const arma::vec& vector)
{
- Log::Assert(vector.n_elem == dim_);
+ Log::Assert(vector.n_elem == dim);
- for (size_t i = 0; i < dim_; i++)
- bounds_[i] |= vector[i];
+ for (size_t i = 0; i < dim; i++)
+ bounds[i] |= vector[i];
return *this;
}
@@ -432,10 +434,10 @@
template<int t_pow>
HRectBound<t_pow>& HRectBound<t_pow>::operator|=(const HRectBound& other)
{
- Log::Assert(other.dim_ == dim_);
+ assert(other.dim == dim);
- for (size_t i = 0; i < dim_; i++)
- bounds_[i] |= other.bounds_[i];
+ for (size_t i = 0; i < dim; i++)
+ bounds[i] |= other.bounds[i];
return *this;
}
@@ -448,7 +450,7 @@
{
for (size_t i = 0; i < point.n_elem; i++)
{
- if (!bounds_[i].Contains(point(i)))
+ if (!bounds[i].Contains(point(i)))
return false;
}
Modified: mlpack/trunk/src/mlpack/core/tree/periodichrectbound.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/periodichrectbound.hpp 2011-11-30 02:16:36 UTC (rev 10460)
+++ mlpack/trunk/src/mlpack/core/tree/periodichrectbound.hpp 2011-11-30 05:36:16 UTC (rev 10461)
@@ -62,7 +62,7 @@
void Clear();
/** Gets the dimensionality */
- size_t dim() const { return dim_; }
+ size_t Dim() const { return dim_; }
/**
* Sets and gets the range for a particular dimension.
Modified: mlpack/trunk/src/mlpack/core/tree/periodichrectbound_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/periodichrectbound_impl.hpp 2011-11-30 02:16:36 UTC (rev 10460)
+++ mlpack/trunk/src/mlpack/core/tree/periodichrectbound_impl.hpp 2011-11-30 05:36:16 UTC (rev 10461)
@@ -115,7 +115,7 @@
centroid.set_size(dim_);
for (size_t i = 0; i < dim_; i++)
- centroid(i) = bounds_[i].mid();
+ centroid(i) = bounds_[i].Mid();
}
/**
More information about the mlpack-svn
mailing list