1 /** 2 * @file core/tree/binary_space_tree/dual_tree_traverser.hpp 3 * @author Ryan Curtin 4 * 5 * Defines the DualTreeTraverser for the BinarySpaceTree tree type. This is a 6 * nested class of BinarySpaceTree which traverses two trees in a depth-first 7 * manner with a given set of rules which indicate the branches which can be 8 * pruned and the order in which to recurse. 9 * 10 * mlpack is free software; you may redistribute it and/or modify it under the 11 * terms of the 3-clause BSD license. You should have received a copy of the 12 * 3-clause BSD license along with mlpack. If not, see 13 * http://www.opensource.org/licenses/BSD-3-Clause for more information. 14 */ 15 #ifndef MLPACK_CORE_TREE_BINARY_SPACE_TREE_DUAL_TREE_TRAVERSER_HPP 16 #define MLPACK_CORE_TREE_BINARY_SPACE_TREE_DUAL_TREE_TRAVERSER_HPP 17 18 #include <mlpack/prereqs.hpp> 19 20 #include "binary_space_tree.hpp" 21 22 namespace mlpack { 23 namespace tree { 24 25 template<typename MetricType, 26 typename StatisticType, 27 typename MatType, 28 template<typename BoundMetricType, typename...> class BoundType, 29 template<typename SplitBoundType, typename SplitMatType> 30 class SplitType> 31 template<typename RuleType> 32 class BinarySpaceTree<MetricType, StatisticType, MatType, BoundType, 33 SplitType>::DualTreeTraverser 34 { 35 public: 36 /** 37 * Instantiate the dual-tree traverser with the given rule set. 38 */ 39 DualTreeTraverser(RuleType& rule); 40 41 /** 42 * Traverse the two trees. This does not reset the number of prunes. 43 * 44 * @param queryNode The query node to be traversed. 45 * @param referenceNode The reference node to be traversed. 46 */ 47 void Traverse(BinarySpaceTree& queryNode, 48 BinarySpaceTree& referenceNode); 49 50 //! Get the number of prunes. NumPrunes() const51 size_t NumPrunes() const { return numPrunes; } 52 //! Modify the number of prunes. NumPrunes()53 size_t& NumPrunes() { return numPrunes; } 54 55 //! Get the number of visited combinations. NumVisited() const56 size_t NumVisited() const { return numVisited; } 57 //! Modify the number of visited combinations. NumVisited()58 size_t& NumVisited() { return numVisited; } 59 60 //! Get the number of times a node combination was scored. NumScores() const61 size_t NumScores() const { return numScores; } 62 //! Modify the number of times a node combination was scored. NumScores()63 size_t& NumScores() { return numScores; } 64 65 //! Get the number of times a base case was calculated. NumBaseCases() const66 size_t NumBaseCases() const { return numBaseCases; } 67 //! Modify the number of times a base case was calculated. NumBaseCases()68 size_t& NumBaseCases() { return numBaseCases; } 69 70 private: 71 //! Reference to the rules with which the trees will be traversed. 72 RuleType& rule; 73 74 //! The number of prunes. 75 size_t numPrunes; 76 77 //! The number of node combinations that have been visited during traversal. 78 size_t numVisited; 79 80 //! The number of times a node combination was scored. 81 size_t numScores; 82 83 //! The number of times a base case was calculated. 84 size_t numBaseCases; 85 86 //! Traversal information, held in the class so that it isn't continually 87 //! being reallocated. 88 typename RuleType::TraversalInfoType traversalInfo; 89 }; 90 91 } // namespace tree 92 } // namespace mlpack 93 94 // Include implementation. 95 #include "dual_tree_traverser_impl.hpp" 96 97 #endif // MLPACK_CORE_TREE_BINARY_SPACE_TREE_DUAL_TREE_TRAVERSER_HPP 98