[mlpack-git] master: Remove some crufty unused functions from BinarySpaceTree. (a6709aa)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Thu Jul 16 12:16:43 EDT 2015
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/b4659b668021db631b3c8a48e3d735b513706fdc...015d79104286231ef70ea0ba1d99a6c397025b3e
>---------------------------------------------------------------
commit a6709aaea2434844b890f510b2797a18b56f84ab
Author: Ryan Curtin <ryan at ratml.org>
Date: Wed Jul 15 14:27:40 2015 +0000
Remove some crufty unused functions from BinarySpaceTree.
>---------------------------------------------------------------
a6709aaea2434844b890f510b2797a18b56f84ab
.../tree/binary_space_tree/binary_space_tree.hpp | 43 --------
.../binary_space_tree/binary_space_tree_impl.hpp | 114 ---------------------
.../breadth_first_dual_tree_traverser_impl.hpp | 7 +-
.../binary_space_tree/dual_tree_traverser_impl.hpp | 6 +-
.../single_tree_traverser_impl.hpp | 3 +-
src/mlpack/tests/tree_test.cpp | 8 --
6 files changed, 10 insertions(+), 171 deletions(-)
diff --git a/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp b/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
index c90b0de..ce8edf3 100644
--- a/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
+++ b/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
@@ -229,33 +229,6 @@ class BinarySpaceTree
*/
~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 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,
- size_t count) 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 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, size_t count);
-
//! Return the bound object for this node.
const BoundType& Bound() const { return bound; }
//! Return the bound object for this node.
@@ -408,27 +381,11 @@ class BinarySpaceTree
return bound.RangeDistance(point);
}
- /**
- * 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.
- */
- size_t TreeDepth() const;
-
//! Return the index of the beginning point of this subset.
size_t Begin() const { return begin; }
//! Modify the index of the beginning point of this subset.
size_t& Begin() { return begin; }
- /**
- * Gets the index one beyond the last index in the subset.
- */
- size_t End() const;
-
//! Return the number of points in this subset.
size_t Count() const { return count; }
//! Modify the number of points in this subset.
diff --git a/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp b/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp
index 7ad8298..2e37440 100644
--- a/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp
+++ b/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp
@@ -298,107 +298,6 @@ BinarySpaceTree<BoundType, StatisticType, MatType, SplitType>::
delete dataset;
}
-/**
- * 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 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 BoundType,
- typename StatisticType,
- typename MatType,
- typename SplitType>
-const BinarySpaceTree<BoundType, StatisticType, MatType, SplitType>*
-BinarySpaceTree<BoundType, StatisticType, MatType, SplitType>::FindByBeginCount(
- size_t queryBegin,
- size_t queryCount) const
-{
- Log::Assert(queryBegin >= begin);
- Log::Assert(queryCount <= count);
-
- if (begin == queryBegin && count == queryCount)
- return this;
- else if (IsLeaf())
- return NULL;
- else if (queryBegin < right->Begin())
- return left->FindByBeginCount(queryBegin, queryCount);
- else
- return right->FindByBeginCount(queryBegin, queryCount);
-}
-
-/**
- * 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 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 BoundType,
- typename StatisticType,
- typename MatType,
- typename SplitType>
-BinarySpaceTree<BoundType, StatisticType, MatType, SplitType>*
-BinarySpaceTree<BoundType, StatisticType, MatType, SplitType>::FindByBeginCount(
- const size_t queryBegin,
- const size_t queryCount)
-{
- mlpack::Log::Assert(begin >= queryBegin);
- mlpack::Log::Assert(count <= queryCount);
-
- if (begin == queryBegin && count == queryCount)
- return this;
- else if (IsLeaf())
- return NULL;
- else if (queryBegin < left->End())
- return left->FindByBeginCount(queryBegin, queryCount);
- else if (right)
- return right->FindByBeginCount(queryBegin, queryCount);
- else
- return NULL;
-}
-
-/* TODO: we can likely calculate this earlier, then store the
- * result in a private member variable; for now, we can
- * just calculate as needed...
- *
- * Also, perhaps we should rewrite these recursive functions
- * to avoid exceeding the stack limit
- */
-
-template<typename BoundType,
- typename StatisticType,
- typename MatType,
- typename SplitType>
-size_t BinarySpaceTree<BoundType, StatisticType, MatType, SplitType>::
- TreeSize() const
-{
- // 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 BoundType,
- typename StatisticType,
- typename MatType,
- typename SplitType>
-size_t BinarySpaceTree<BoundType, StatisticType, MatType, SplitType>::
- TreeDepth() const
-{
- // 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 BoundType,
typename StatisticType,
typename MatType,
@@ -545,19 +444,6 @@ inline size_t BinarySpaceTree<BoundType, StatisticType, MatType, SplitType>::
return (begin + index);
}
-/**
- * Gets the index one beyond the last index in the series.
- */
-template<typename BoundType,
- typename StatisticType,
- typename MatType,
- typename SplitType>
-inline size_t BinarySpaceTree<BoundType, StatisticType, MatType, SplitType>::
- End() const
-{
- return begin + count;
-}
-
template<typename BoundType,
typename StatisticType,
typename MatType,
diff --git a/src/mlpack/core/tree/binary_space_tree/breadth_first_dual_tree_traverser_impl.hpp b/src/mlpack/core/tree/binary_space_tree/breadth_first_dual_tree_traverser_impl.hpp
index f48bf95..4ae92c1 100644
--- a/src/mlpack/core/tree/binary_space_tree/breadth_first_dual_tree_traverser_impl.hpp
+++ b/src/mlpack/core/tree/binary_space_tree/breadth_first_dual_tree_traverser_impl.hpp
@@ -117,7 +117,9 @@ BreadthFirstDualTreeTraverser<RuleType>::Traverse(
if (queryNode.IsLeaf() && referenceNode.IsLeaf())
{
// Loop through each of the points in each node.
- for (size_t query = queryNode.Begin(); query < queryNode.End(); ++query)
+ const size_t queryEnd = queryNode.Begin() + queryNode.Count();
+ const size_t refEnd = referenceNode.Begin() + referenceNode.Count();
+ for (size_t query = queryNode.Begin(); query < queryEnd; ++query)
{
// See if we need to investigate this point (this function should be
// implemented for the single-tree recursion too). Restore the
@@ -127,8 +129,7 @@ BreadthFirstDualTreeTraverser<RuleType>::Traverse(
// if (childScore == DBL_MAX)
// continue; // We can't improve this particular point.
- for (size_t ref = referenceNode.Begin(); ref < referenceNode.End();
- ++ref)
+ for (size_t ref = referenceNode.Begin(); ref < refEnd; ++ref)
rule.BaseCase(query, ref);
numBaseCases += referenceNode.Count();
diff --git a/src/mlpack/core/tree/binary_space_tree/dual_tree_traverser_impl.hpp b/src/mlpack/core/tree/binary_space_tree/dual_tree_traverser_impl.hpp
index a226cc0..7769dca 100644
--- a/src/mlpack/core/tree/binary_space_tree/dual_tree_traverser_impl.hpp
+++ b/src/mlpack/core/tree/binary_space_tree/dual_tree_traverser_impl.hpp
@@ -50,7 +50,9 @@ DualTreeTraverser<RuleType>::Traverse(
if (queryNode.IsLeaf() && referenceNode.IsLeaf())
{
// Loop through each of the points in each node.
- for (size_t query = queryNode.Begin(); query < queryNode.End(); ++query)
+ const size_t queryEnd = queryNode.Begin() + queryNode.Count();
+ const size_t refEnd = referenceNode.Begin() + referenceNode.Count();
+ for (size_t query = queryNode.Begin(); query < queryEnd; ++query)
{
// See if we need to investigate this point (this function should be
// implemented for the single-tree recursion too). Restore the traversal
@@ -61,7 +63,7 @@ DualTreeTraverser<RuleType>::Traverse(
if (childScore == DBL_MAX)
continue; // We can't improve this particular point.
- for (size_t ref = referenceNode.Begin(); ref < referenceNode.End(); ++ref)
+ for (size_t ref = referenceNode.Begin(); ref < refEnd; ++ref)
rule.BaseCase(query, ref);
numBaseCases += referenceNode.Count();
diff --git a/src/mlpack/core/tree/binary_space_tree/single_tree_traverser_impl.hpp b/src/mlpack/core/tree/binary_space_tree/single_tree_traverser_impl.hpp
index 7b559e0..7826957 100644
--- a/src/mlpack/core/tree/binary_space_tree/single_tree_traverser_impl.hpp
+++ b/src/mlpack/core/tree/binary_space_tree/single_tree_traverser_impl.hpp
@@ -42,7 +42,8 @@ SingleTreeTraverser<RuleType>::Traverse(
// If we are a leaf, run the base case as necessary.
if (referenceNode.IsLeaf())
{
- for (size_t i = referenceNode.Begin(); i < referenceNode.End(); ++i)
+ const size_t refEnd = referenceNode.Begin() + referenceNode.Count();
+ for (size_t i = referenceNode.Begin(); i < refEnd; ++i)
rule.BaseCase(queryIndex, i);
}
else
diff --git a/src/mlpack/tests/tree_test.cpp b/src/mlpack/tests/tree_test.cpp
index 69265c7..8d4e6d3 100644
--- a/src/mlpack/tests/tree_test.cpp
+++ b/src/mlpack/tests/tree_test.cpp
@@ -1316,10 +1316,6 @@ BOOST_AUTO_TEST_CASE(KdTreeTest)
dataset(row, col) = row + col;
TreeType root(dataset);
- // Check the tree size.
- BOOST_REQUIRE_EQUAL(root.TreeSize(), 127);
- // Check the tree depth.
- BOOST_REQUIRE_EQUAL(root.TreeDepth(), 7);
}
// Recursively checks that each node contains all points that it claims to have.
@@ -1523,10 +1519,6 @@ BOOST_AUTO_TEST_CASE(ExhaustiveSparseKDTreeTest)
dataset(row, col) = row + col;
TreeType root(dataset);
- // Check the tree size.
- BOOST_REQUIRE_EQUAL(root.TreeSize(), 127);
- // Check the tree depth.
- BOOST_REQUIRE_EQUAL(root.TreeDepth(), 7);
}
#endif // Using Armadillo 3.4.
More information about the mlpack-git
mailing list