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