[mlpack-svn] r10048 - mlpack/trunk/src/mlpack/core/tree
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Wed Oct 26 20:14:52 EDT 2011
Author: rcurtin
Date: 2011-10-26 20:14:52 -0400 (Wed, 26 Oct 2011)
New Revision: 10048
Added:
mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp
mlpack/trunk/src/mlpack/core/tree/binary_space_tree_impl.hpp
Removed:
mlpack/trunk/src/mlpack/core/tree/spacetree.hpp
mlpack/trunk/src/mlpack/core/tree/spacetree_impl.hpp
Modified:
mlpack/trunk/src/mlpack/core/tree/tree_test.cpp
Log:
Move spacetree.hpp to binary_space_tree.hpp (better name) and comment it all.
Copied: mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp (from rev 10030, mlpack/trunk/src/mlpack/core/tree/spacetree.h)
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp (rev 0)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp 2011-10-27 00:14:52 UTC (rev 10048)
@@ -0,0 +1,291 @@
+/**
+ * @file spacetree.h
+ *
+ * Definition of generalized binary space partitioning tree (BinarySpaceTree).
+ */
+#ifndef __MLPACK_CORE_TREE_BINARY_SPACE_TREE_HPP
+#define __MLPACK_CORE_TREE_BINARY_SPACE_TREE_HPP
+
+#include "statistic.hpp"
+
+#include <armadillo>
+
+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
+ * the constructor with the dataset to build the tree on, and the entire tree
+ * will be built.
+ *
+ * This particular tree does not allow growth, so you cannot add or delete nodes
+ * from it. If you need to add or delete a node, the better procedure is to
+ * rebuild the tree entirely.
+ *
+ * This tree does take one parameter, which is the leaf size to be used. You
+ * can set this at runtime with --tree/leaf_size [leaf_size]. You can also set
+ * it in your program using CLI:
+ *
+ * @code
+ * CLI::GetParam<int>("tree/leaf_size") = target_leaf_size;
+ * @endcode
+ *
+ * @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.
+ */
+template<typename Bound,
+ typename Statistic = EmptyStatistic>
+class BinarySpaceTree {
+ private:
+ //! The left child node.
+ BinarySpaceTree *left_;
+ //! The right child node.
+ BinarySpaceTree *right_;
+ //! The index of the first point in the dataset contained in this node (and
+ //! its children).
+ size_t begin_;
+ //! The number of points of the dataset contained in this node (and its
+ //! children).
+ size_t count_;
+ //! The bound object for this node.
+ Bound bound_;
+ //! Any extra data contained in the node.
+ Statistic stat_;
+
+ public:
+ /**
+ * Construct this as the root node of a binary space tree using the given
+ * dataset. This will modify the ordering of the points in the dataset!
+ *
+ * @param data Dataset to create tree from. This will be modified!
+ */
+ BinarySpaceTree(arma::mat& data);
+
+ /**
+ * Construct this as the root node of a binary space tree using the given
+ * dataset. This will modify the ordering of points in 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 modified!
+ * @param old_from_new 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.
+ */
+ BinarySpaceTree(arma::mat& data, std::vector<size_t>& old_from_new);
+
+ /**
+ * Construct this as the root node of a binary space tree using the given
+ * dataset. This will modify the ordering of points in the dataset! A
+ * mapping of the old point indices to the new point indices is filled, as
+ * 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
+ * each new point.
+ * @param new_from_old Vector which will be filled with the new positions for
+ * each old point.
+ */
+ BinarySpaceTree(arma::mat& data,
+ std::vector<size_t>& old_from_new,
+ std::vector<size_t>& new_from_old);
+
+ /**
+ * 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
+ * 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.
+ */
+ BinarySpaceTree(arma::mat& data,
+ size_t begin_in,
+ size_t count_in);
+
+ /**
+ * 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
+ * will be modified! This is used for recursive tree-building by the other
+ * constructors which 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_in + count_in), and if that is not true, invalid memory
+ * 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
+ * each new point.
+ */
+ BinarySpaceTree(arma::mat& data,
+ size_t begin_in,
+ size_t count_in,
+ std::vector<size_t>& old_from_new);
+
+ /**
+ * 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
+ * will be modified! This is used for recursive tree-building by the other
+ * constructors which don't specify point indices.
+ *
+ * A mapping of the old point indices to the new point indices is filled, as
+ * well as a mapping of the new point indices to the old point indices. It is
+ * expected that the vector is already allocated with size greater than or
+ * equal to (begin_in + count_in), and if that is not true, invalid memory
+ * 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
+ * each new point.
+ * @param new_from_old Vector which will be filled with the new positions for
+ * each old point.
+ */
+ 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);
+
+ /**
+ * Create an empty tree node.
+ */
+ BinarySpaceTree();
+
+ /**
+ * Deletes this node, deallocating the memory for the children and calling
+ * their destructors in turn. This will invalidate any pointers or references
+ * to any nodes which are children of this one.
+ */
+ ~BinarySpaceTree();
+
+ /**
+ * Find a node in this tree by its begin and count (const).
+ *
+ * Every node is uniquely identified by these two numbers.
+ * 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 if not found.
+ */
+ const BinarySpaceTree* FindByBeginCount(size_t begin_q,
+ size_t count_q) const;
+
+ /**
+ * Find a node in this tree by its begin and count.
+ *
+ * Every node is uniquely identified by these two numbers.
+ * 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 if not found.
+ */
+ BinarySpaceTree* FindByBeginCount(size_t begin_q, size_t count_q);
+
+ //! Return the bound object for this node.
+ const Bound& bound() const;
+ //! Return the bound object for this node.
+ Bound& bound();
+
+ //! Return the statistic object for this node.
+ const Statistic& stat() const;
+ //! Return the statistic object for this node.
+ Statistic& stat();
+
+ //! Return whether or not this node is a leaf (true if it has no children).
+ bool is_leaf() const;
+
+ /**
+ * Gets the left child of this node.
+ */
+ BinarySpaceTree *left() const;
+
+ /**
+ * Gets the right child of this node.
+ */
+ BinarySpaceTree *right() const;
+
+ /**
+ * Gets the index of the beginning point of this subset.
+ */
+ size_t begin() const;
+
+ /**
+ * Gets the index one beyond the last index in the subset.
+ */
+ size_t end() const;
+
+ /**
+ * Gets the number of points in this subset.
+ */
+ size_t count() const;
+
+ void Print() const;
+
+ private:
+ /**
+ * Splits the current node, assigning its left and right children recursively.
+ *
+ * @param data Dataset which we are using.
+ */
+ void SplitNode(arma::mat& data);
+
+ /**
+ * Splits the current node, assigning its left and right children recursively.
+ * Also returns a list of the changed indices.
+ *
+ * @param data Dataset which we are using.
+ * @param old_from_new Vector holding permuted indices.
+ */
+ void SplitNode(arma::mat& data, std::vector<size_t>& old_from_new);
+
+ /**
+ * 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.
+ */
+ size_t GetSplitIndex(arma::mat& data, int split_dim, double split_val);
+
+ /**
+ * Find the index to split on for this node, given that we are splitting in
+ * the given split dimension on the specified split value. Also returns a
+ * 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.
+ */
+ size_t GetSplitIndex(arma::mat& data, int split_dim, double split_val,
+ std::vector<size_t>& old_from_new);
+
+};
+
+}; // namespace tree
+}; // namespace mlpack
+
+// Include implementation.
+#include "binary_space_tree_impl.hpp"
+
+#endif
Copied: mlpack/trunk/src/mlpack/core/tree/binary_space_tree_impl.hpp (from rev 10030, mlpack/trunk/src/mlpack/core/tree/spacetree_impl.h)
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree_impl.hpp (rev 0)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree_impl.hpp 2011-10-27 00:14:52 UTC (rev 10048)
@@ -0,0 +1,481 @@
+/**
+ * @file binary_space_tree_impl.hpp
+ *
+ * Implementation of generalized space partitioning tree.
+ */
+#ifndef __MLPACK_CORE_TREE_BINARY_SPACE_TREE_IMPL_HPP
+#define __MLPACK_CORE_TREE_BINARY_SPACE_TREE_IMPL_HPP
+
+// In case it wasn't included already for some reason.
+#include "binary_space_tree.hpp"
+
+#include <mlpack/core/io/cli.hpp>
+#include <mlpack/core/io/log.hpp>
+
+namespace mlpack {
+namespace tree {
+
+// 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_() {
+ // Do the actual splitting of this node.
+ SplitNode(data);
+}
+
+template<typename Bound, typename Statistic>
+BinarySpaceTree<Bound, Statistic>::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_() {
+ // Initialize old_from_new correctly.
+ old_from_new.resize(data.n_cols);
+ for (size_t i = 0; i < data.n_cols; i++)
+ old_from_new[i] = i; // Fill with unharmed indices.
+
+ // Now do the actual splitting.
+ SplitNode(data, old_from_new);
+}
+
+template<typename Bound, typename Statistic>
+BinarySpaceTree<Bound, Statistic>::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_() {
+ // Initialize the old_from_new vector correctly.
+ old_from_new.resize(data.n_cols);
+ for (size_t i = 0; i < data.n_cols; i++)
+ old_from_new[i] = i; // Fill with unharmed indices.
+
+ // Now do the actual splitting.
+ SplitNode(data, old_from_new);
+
+ // Map the new_from_old indices correctly.
+ new_from_old.resize(data.n_cols);
+ for (size_t i = 0; i < data.n_cols; i++)
+ new_from_old[old_from_new[i]] = i;
+}
+
+template<typename Bound, typename Statistic>
+BinarySpaceTree<Bound, Statistic>::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_() {
+ // Perform the actual splitting.
+ SplitNode(data);
+}
+
+template<typename Bound, typename Statistic>
+BinarySpaceTree<Bound, Statistic>::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_() {
+ // Hopefully the vector is initialized correctly! We can't check that
+ // entirely but we can do a minor sanity check.
+ assert(old_from_new.size() == data.n_cols);
+
+ // Perform the actual splitting.
+ SplitNode(data, old_from_new);
+}
+
+template<typename Bound, typename Statistic>
+BinarySpaceTree<Bound, Statistic>::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_() {
+ // Hopefully the vector is initialized correctly! We can't check that
+ // entirely but we can do a minor sanity check.
+ assert(old_from_new.size() == data.n_cols);
+
+ // Perform the actual splitting.
+ SplitNode(data, old_from_new);
+
+ // Map the new_from_old indices correctly.
+ new_from_old.resize(data.n_cols);
+ for (size_t i = 0; i < data.n_cols; i++)
+ new_from_old[old_from_new[i]] = i;
+}
+
+template<typename Bound, typename Statistic>
+BinarySpaceTree<Bound, Statistic>::BinarySpaceTree() :
+ left_(NULL),
+ right_(NULL),
+ begin_(0),
+ count_(0),
+ bound_(),
+ stat_() {
+ // Nothing to do.
+}
+
+/**
+ * Deletes this node, deallocating the memory for the children and calling their
+ * 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() {
+ if (left_)
+ delete left_;
+ if (right_)
+ delete right_;
+}
+
+/**
+ * Find a node in this tree by its begin and count.
+ *
+ * Every node is uniquely identified by these two numbers.
+ * 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
+ */
+template<typename Bound, typename Statistic>
+const BinarySpaceTree<Bound, Statistic>*
+BinarySpaceTree<Bound, Statistic>::FindByBeginCount(size_t begin_q,
+ size_t count_q) const {
+
+ mlpack::Log::Assert(begin_q >= begin_);
+ mlpack::Log::Assert(count_q <= count_);
+ if (begin_ == begin_q && count_ == count_q)
+ return this;
+ else if (is_leaf())
+ return NULL;
+ else if (begin_q < right_->begin_)
+ return left_->FindByBeginCount(begin_q, count_q);
+ else
+ return right_->FindByBeginCount(begin_q, count_q);
+}
+
+/**
+ * Find a node in this tree by its begin and count (const).
+ *
+ * Every node is uniquely identified by these two numbers.
+ * 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
+ */
+template<typename Bound, typename Statistic>
+BinarySpaceTree<Bound, Statistic>*
+BinarySpaceTree<Bound, Statistic>::FindByBeginCount(size_t begin_q,
+ size_t count_q) {
+
+ mlpack::Log::Assert(begin_q >= begin_);
+ mlpack::Log::Assert(count_q <= count_);
+ if (begin_ == begin_q && count_ == count_q)
+ return this;
+ else if (is_leaf())
+ return NULL;
+ else if (begin_q < right_->begin_)
+ return left_->FindByBeginCount(begin_q, count_q);
+ else
+ return right_->FindByBeginCount(begin_q, count_q);
+}
+
+template<typename Bound, typename Statistic>
+const Bound& BinarySpaceTree<Bound, Statistic>::bound() const {
+ return bound_;
+}
+
+template<typename Bound, typename Statistic>
+Bound& BinarySpaceTree<Bound, Statistic>::bound() {
+ return bound_;
+}
+
+template<typename Bound, typename Statistic>
+const Statistic& BinarySpaceTree<Bound, Statistic>::stat() const {
+ return stat_;
+}
+
+template<typename Bound, typename Statistic>
+Statistic& BinarySpaceTree<Bound, Statistic>::stat() {
+ return stat_;
+}
+
+template<typename Bound, typename Statistic>
+bool BinarySpaceTree<Bound, Statistic>::is_leaf() const {
+ return !left_;
+}
+
+/**
+ * Gets the left branch of the tree.
+ */
+template<typename Bound, typename Statistic>
+BinarySpaceTree<Bound, Statistic>*
+BinarySpaceTree<Bound, Statistic>::left() const {
+ // TODO: Const correctness
+ return left_;
+}
+
+/**
+ * Gets the right branch.
+ */
+template<typename Bound, typename Statistic>
+BinarySpaceTree<Bound, Statistic>*
+BinarySpaceTree<Bound, Statistic>::right() const {
+ // TODO: Const correctness
+ return right_;
+}
+
+/**
+ * Gets the index of the begin point of this subset.
+ */
+template<typename Bound, typename Statistic>
+size_t BinarySpaceTree<Bound, Statistic>::begin() const {
+ return begin_;
+}
+
+/**
+ * Gets the index one beyond the last index in the series.
+ */
+template<typename Bound, typename Statistic>
+size_t BinarySpaceTree<Bound, Statistic>::end() const {
+ return begin_ + count_;
+}
+
+/**
+ * Gets the number of points in this subset.
+ */
+template<typename Bound, typename Statistic>
+size_t BinarySpaceTree<Bound, Statistic>::count() const {
+ 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();
+ right_->Print();
+ }
+}
+
+template<typename Bound, typename Statistic>
+void BinarySpaceTree<Bound, Statistic>::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);
+
+ // Now, check if we need to split at all.
+ if (count_ <= (size_t) CLI::GetParam<int>("tree/leaf_size"))
+ 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;
+
+ // Find the split dimension.
+ for (size_t d = 0; d < data.n_rows; d++) {
+ double width = bound_[d].width();
+
+ if (width > max_width) {
+ max_width = width;
+ split_dim = d;
+ }
+ }
+
+ // Split in the middle of that dimension.
+ double split_val = bound_[split_dim].mid();
+
+ if (max_width == 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_val are on
+ // the left of split_col, and points with value in dimension split_dim greater
+ // than split_val are on the right side of split_col.
+ size_t split_col = GetSplitIndex(data, split_dim, split_val);
+
+ // 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);
+}
+
+template<typename Bound, typename Statistic>
+void BinarySpaceTree<Bound, Statistic>::SplitNode(
+ arma::mat& data,
+ std::vector<size_t>& old_from_new) {
+ // 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);
+
+ // First, check if we need to split at all.
+ if (count_ <= (size_t) CLI::GetParam<int>("tree/leaf_size"))
+ 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;
+
+ // Find the split dimension.
+ for (size_t d = 0; d < data.n_rows; d++) {
+ double width = bound_[d].width();
+
+ if (width > max_width) {
+ max_width = width;
+ split_dim = d;
+ }
+ }
+
+ // Split in the middle of that dimension.
+ double split_val = bound_[split_dim].mid();
+
+ if (max_width == 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_val are on
+ // the left of split_col, and points with value in dimension split_dim greater
+ // than split_val are on the right side of split_col.
+ size_t split_col = GetSplitIndex(data, split_dim, split_val, old_from_new);
+
+ // 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);
+}
+
+template<typename Bound, typename Statistic>
+size_t BinarySpaceTree<Bound, Statistic>::GetSplitIndex(
+ arma::mat& data,
+ int split_dim,
+ double split_val) {
+ // 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;
+
+ // 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))
+ left++;
+ while ((data(split_dim, right) >= split_val) && (left <= right))
+ right--;
+
+ while(left <= right) {
+ // Swap columns.
+ data.swap_cols(left, right);
+
+ // 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))
+ 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))
+ right--;
+ }
+
+ assert(left == right + 1);
+
+ return left;
+}
+
+template<typename Bound, typename Statistic>
+size_t BinarySpaceTree<Bound, Statistic>::GetSplitIndex(
+ arma::mat& data,
+ int split_dim,
+ double split_val,
+ std::vector<size_t>& old_from_new) {
+ // 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;
+
+ // 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))
+ left++;
+ while ((data(split_dim, right) >= split_val) && (left <= right))
+ right--;
+
+ while(left <= right) {
+ // Swap columns.
+ 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;
+
+ // 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))
+ 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))
+ right--;
+ }
+
+ assert(left == right + 1);
+
+ return left;
+}
+
+}; // namespace tree
+}; // namespace mlpack
+
+#endif
Deleted: mlpack/trunk/src/mlpack/core/tree/spacetree.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/spacetree.hpp 2011-10-27 00:10:53 UTC (rev 10047)
+++ mlpack/trunk/src/mlpack/core/tree/spacetree.hpp 2011-10-27 00:14:52 UTC (rev 10048)
@@ -1,201 +0,0 @@
-/**
- * @file spacetree.hpp
- *
- * Generalized space partitioning tree.
- *
- * @experimental
- */
-
-#ifndef __MLPACK_CORE_TREE_SPACETREE_HPP
-#define __MLPACK_CORE_TREE_SPACETREE_HPP
-
-#include "statistic.hpp"
-
-#include <armadillo>
-
-namespace mlpack {
-namespace tree {
-
-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
- * the constructor with the dataset to build the tree on, and the entire tree
- * will be built.
- *
- * This particular tree does not allow growth, so you cannot add or delete nodes
- * from it. If you need to add or delete a node, the better procedure is to
- * rebuild the tree entirely.
- *
- * This tree does take one command line parameter, which is the leaf size to be
- * used. You can set this at runtime with --tree/leaf_size [leaf_size]. You
- * can also set it in your program using CLI:
- *
- * @code
- * CLI::GetParam<int>("tree/leaf_size") = target_leaf_size;
- * @endcode
- *
- * @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.
- */
-template<typename Bound,
- typename Statistic = EmptyStatistic>
-class BinarySpaceTree {
- private:
- BinarySpaceTree *left_; //< The left child node.
- BinarySpaceTree *right_; //< The right child node.
- size_t begin_; //< The first point in the dataset contained in this node.
- size_t count_; //< The count of points in the dataset contained in this node.
- Bound bound_; //< The bound object for this node.
- Statistic stat_; //< The extra data contained in the node.
-
- public:
- /***
- * Construct this as the head node of a binary space tree using the given
- * dataset. This will modify the ordering of the points in the dataset!
- *
- * Optionally, pass in vectors which represent a mapping from the old
- * dataset's point ordering to the new ordering, and vice versa.
- *
- * @param data Dataset to create tree from.
- * @param leaf_size Leaf size of the tree.
- * @param old_from_new 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.
- */
- BinarySpaceTree(arma::mat& data);
- BinarySpaceTree(arma::mat& data, std::vector<size_t>& old_from_new);
- BinarySpaceTree(arma::mat& data,
- std::vector<size_t>& old_from_new,
- std::vector<size_t>& new_from_old);
-
- BinarySpaceTree(arma::mat& data,
- size_t begin_in,
- size_t count_in);
- BinarySpaceTree(arma::mat& data,
- size_t begin_in,
- size_t count_in,
- std::vector<size_t>& old_from_new);
- 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);
-
- BinarySpaceTree();
-
- /***
- * Deletes this node, deallocating the memory for the children and calling
- * their destructors in turn. This will invalidate any pointers or references
- * to any nodes which are children of this one.
- */
- ~BinarySpaceTree();
-
- /**
- * Find a node in this tree by its begin and count.
- *
- * Every node is uniquely identified by these two numbers.
- * 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
- */
- const BinarySpaceTree* FindByBeginCount(size_t begin_q,
- size_t count_q) const;
-
- /**
- * Find a node in this tree by its begin and count (const).
- *
- * Every node is uniquely identified by these two numbers.
- * 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
- */
- BinarySpaceTree* FindByBeginCount(size_t begin_q, size_t count_q);
-
- // TODO: Not const correct
-
- const Bound& bound() const;
- Bound& bound();
-
- const Statistic& stat() const;
- Statistic& stat();
-
- bool is_leaf() const;
-
- /**
- * Gets the left branch of the tree.
- */
- BinarySpaceTree *left() const;
-
- /**
- * Gets the right branch.
- */
- BinarySpaceTree *right() const;
-
- /**
- * Gets the index of the begin point of this subset.
- */
- size_t begin() const;
-
- /**
- * Gets the index one beyond the last index in the series.
- */
- size_t end() const;
-
- /**
- * Gets the number of points in this subset.
- */
- size_t count() const;
-
- void Print() const;
-
- private:
-
- /***
- * Splits the current node, assigning its left and right children recursively.
- *
- * Optionally, return a list of the changed indices.
- *
- * @param data Dataset which we are using.
- * @param leaf_size Leaf size to split with.
- * @param old_from_new Vector holding permuted indices.
- */
- void SplitNode(arma::mat& data);
- void SplitNode(arma::mat& data, std::vector<size_t>& old_from_new);
-
- /***
- * Find the index to split on for this node, given that we are splitting in
- * the given split dimension on the specified split value.
- *
- * Optionally, return a 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.
- */
- size_t GetSplitIndex(arma::mat& data, int split_dim, double split_val);
- size_t GetSplitIndex(arma::mat& data, int split_dim, double split_val,
- std::vector<size_t>& old_from_new);
-
-};
-
-}; // namespace tree
-}; // namespace mlpack
-
-// Include implementation.
-#include "spacetree_impl.hpp"
-
-#endif // __MLPACK_CORE_TREE_SPACETREE_HPP
Deleted: mlpack/trunk/src/mlpack/core/tree/spacetree_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/spacetree_impl.hpp 2011-10-27 00:10:53 UTC (rev 10047)
+++ mlpack/trunk/src/mlpack/core/tree/spacetree_impl.hpp 2011-10-27 00:14:52 UTC (rev 10048)
@@ -1,485 +0,0 @@
-/**
- * @file spacetree_impl.h
- *
- * Implementation of generalized space partitioning tree.
- *
- * @experimental
- */
-
-#ifndef __MLPACK_CORE_TREE_SPACETREE_IMPL_HPP
-#define __MLPACK_CORE_TREE_SPACETREE_IMPL_HPP
-
-// Try to prevent direct inclusion
-#ifndef __MLPACK_CORE_TREE_SPACETREE_HPP
-#error "Do not include this header directly."
-#endif
-
-#include "mlpack/core/io/log.hpp"
-
-namespace mlpack {
-namespace tree {
-
-// 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_() {
- // Do the actual splitting of this node.
- SplitNode(data);
-}
-
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>::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_() {
- // Initialize old_from_new correctly.
- old_from_new.resize(data.n_cols);
- for (size_t i = 0; i < data.n_cols; i++)
- old_from_new[i] = i; // Fill with unharmed indices.
-
- // Now do the actual splitting.
- SplitNode(data, old_from_new);
-}
-
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>::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_() {
- // Initialize the old_from_new vector correctly.
- old_from_new.resize(data.n_cols);
- for (size_t i = 0; i < data.n_cols; i++)
- old_from_new[i] = i; // Fill with unharmed indices.
-
- // Now do the actual splitting.
- SplitNode(data, old_from_new);
-
- // Map the new_from_old indices correctly.
- new_from_old.resize(data.n_cols);
- for (size_t i = 0; i < data.n_cols; i++)
- new_from_old[old_from_new[i]] = i;
-}
-
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>::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_() {
- // Perform the actual splitting.
- SplitNode(data);
-}
-
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>::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_() {
- // Hopefully the vector is initialized correctly! We can't check that
- // entirely but we can do a minor sanity check.
- assert(old_from_new.size() == data.n_cols);
-
- // Perform the actual splitting.
- SplitNode(data, old_from_new);
-}
-
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>::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_() {
- // Hopefully the vector is initialized correctly! We can't check that
- // entirely but we can do a minor sanity check.
- assert(old_from_new.size() == data.n_cols);
-
- // Perform the actual splitting.
- SplitNode(data, old_from_new);
-
- // Map the new_from_old indices correctly.
- new_from_old.resize(data.n_cols);
- for (size_t i = 0; i < data.n_cols; i++)
- new_from_old[old_from_new[i]] = i;
-}
-
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>::BinarySpaceTree() :
- left_(NULL),
- right_(NULL),
- begin_(0),
- count_(0),
- bound_(),
- stat_() {
- // Nothing to do.
-}
-
-/***
- * Deletes this node, deallocating the memory for the children and calling their
- * 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() {
- if (left_)
- delete left_;
- if (right_)
- delete right_;
-}
-
-/**
- * Find a node in this tree by its begin and count.
- *
- * Every node is uniquely identified by these two numbers.
- * 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
- */
-template<typename Bound, typename Statistic>
-const BinarySpaceTree<Bound, Statistic>*
-BinarySpaceTree<Bound, Statistic>::FindByBeginCount(size_t begin_q,
- size_t count_q) const {
-
- mlpack::Log::Assert(begin_q >= begin_);
- mlpack::Log::Assert(count_q <= count_);
- if (begin_ == begin_q && count_ == count_q)
- return this;
- else if (is_leaf())
- return NULL;
- else if (begin_q < right_->begin_)
- return left_->FindByBeginCount(begin_q, count_q);
- else
- return right_->FindByBeginCount(begin_q, count_q);
-}
-
-/**
- * Find a node in this tree by its begin and count (const).
- *
- * Every node is uniquely identified by these two numbers.
- * 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
- */
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>*
-BinarySpaceTree<Bound, Statistic>::FindByBeginCount(size_t begin_q,
- size_t count_q) {
-
- mlpack::Log::Assert(begin_q >= begin_);
- mlpack::Log::Assert(count_q <= count_);
- if (begin_ == begin_q && count_ == count_q)
- return this;
- else if (is_leaf())
- return NULL;
- else if (begin_q < right_->begin_)
- return left_->FindByBeginCount(begin_q, count_q);
- else
- return right_->FindByBeginCount(begin_q, count_q);
-}
-
-template<typename Bound, typename Statistic>
-const Bound& BinarySpaceTree<Bound, Statistic>::bound() const {
- return bound_;
-}
-
-template<typename Bound, typename Statistic>
-Bound& BinarySpaceTree<Bound, Statistic>::bound() {
- return bound_;
-}
-
-template<typename Bound, typename Statistic>
-const Statistic& BinarySpaceTree<Bound, Statistic>::stat() const {
- return stat_;
-}
-
-template<typename Bound, typename Statistic>
-Statistic& BinarySpaceTree<Bound, Statistic>::stat() {
- return stat_;
-}
-
-template<typename Bound, typename Statistic>
-bool BinarySpaceTree<Bound, Statistic>::is_leaf() const {
- return !left_;
-}
-
-/**
- * Gets the left branch of the tree.
- */
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>*
-BinarySpaceTree<Bound, Statistic>::left() const {
- // TODO: Const correctness
- return left_;
-}
-
-/**
- * Gets the right branch.
- */
-template<typename Bound, typename Statistic>
-BinarySpaceTree<Bound, Statistic>*
-BinarySpaceTree<Bound, Statistic>::right() const {
- // TODO: Const correctness
- return right_;
-}
-
-/**
- * Gets the index of the begin point of this subset.
- */
-template<typename Bound, typename Statistic>
-size_t BinarySpaceTree<Bound, Statistic>::begin() const {
- return begin_;
-}
-
-/**
- * Gets the index one beyond the last index in the series.
- */
-template<typename Bound, typename Statistic>
-size_t BinarySpaceTree<Bound, Statistic>::end() const {
- return begin_ + count_;
-}
-
-/**
- * Gets the number of points in this subset.
- */
-template<typename Bound, typename Statistic>
-size_t BinarySpaceTree<Bound, Statistic>::count() const {
- 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();
- right_->Print();
- }
-}
-
-template<typename Bound, typename Statistic>
-void BinarySpaceTree<Bound, Statistic>::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);
-
- // Now, check if we need to split at all.
- if (count_ <= (size_t) CLI::GetParam<int>("tree/leaf_size"))
- 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;
-
- // Find the split dimension.
- for (size_t d = 0; d < data.n_rows; d++) {
- double width = bound_[d].width();
-
- if (width > max_width) {
- max_width = width;
- split_dim = d;
- }
- }
-
- // Split in the middle of that dimension.
- double split_val = bound_[split_dim].mid();
-
- if (max_width == 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_val are on
- // the left of split_col, and points with value in dimension split_dim greater
- // than split_val are on the right side of split_col.
- size_t split_col = GetSplitIndex(data, split_dim, split_val);
-
- // 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);
-}
-
-template<typename Bound, typename Statistic>
-void BinarySpaceTree<Bound, Statistic>::SplitNode(
- arma::mat& data,
- std::vector<size_t>& old_from_new) {
- // 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);
-
- // First, check if we need to split at all.
- if (count_ <= (size_t) CLI::GetParam<int>("tree/leaf_size"))
- 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;
-
- // Find the split dimension.
- for (size_t d = 0; d < data.n_rows; d++) {
- double width = bound_[d].width();
-
- if (width > max_width) {
- max_width = width;
- split_dim = d;
- }
- }
-
- // Split in the middle of that dimension.
- double split_val = bound_[split_dim].mid();
-
- if (max_width == 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_val are on
- // the left of split_col, and points with value in dimension split_dim greater
- // than split_val are on the right side of split_col.
- size_t split_col = GetSplitIndex(data, split_dim, split_val, old_from_new);
-
- // 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);
-}
-
-template<typename Bound, typename Statistic>
-size_t BinarySpaceTree<Bound, Statistic>::GetSplitIndex(
- arma::mat& data,
- int split_dim,
- double split_val) {
- // 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;
-
- // 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))
- left++;
- while ((data(split_dim, right) >= split_val) && (left <= right))
- right--;
-
- while(left <= right) {
- // Swap columns.
- data.swap_cols(left, right);
-
- // 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))
- 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))
- right--;
- }
-
- assert(left == right + 1);
-
- return left;
-}
-
-template<typename Bound, typename Statistic>
-size_t BinarySpaceTree<Bound, Statistic>::GetSplitIndex(
- arma::mat& data,
- int split_dim,
- double split_val,
- std::vector<size_t>& old_from_new) {
- // 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;
-
- // 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))
- left++;
- while ((data(split_dim, right) >= split_val) && (left <= right))
- right--;
-
- while(left <= right) {
- // Swap columns.
- 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;
-
- // 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))
- 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))
- right--;
- }
-
- assert(left == right + 1);
-
- return left;
-}
-
-}; // namespace tree
-}; // namespace mlpack
-
-#endif // __MLPACK_CORE_TREE_SPACETREE_IMPL_HPP
Modified: mlpack/trunk/src/mlpack/core/tree/tree_test.cpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/tree_test.cpp 2011-10-27 00:10:53 UTC (rev 10047)
+++ mlpack/trunk/src/mlpack/core/tree/tree_test.cpp 2011-10-27 00:14:52 UTC (rev 10048)
@@ -5,7 +5,7 @@
*/
#include "bounds.hpp"
-#include "spacetree.hpp"
+#include "binary_space_tree.hpp"
#include <mlpack/core/kernels/lmetric.hpp>
#include <vector>
More information about the mlpack-svn
mailing list