dual_tree_traverser.hpp

Go to the documentation of this file.

 
#ifndef MLPACK_CORE_TREE_COVER_TREE_DUAL_TREE_TRAVERSER_HPP
#define MLPACK_CORE_TREE_COVER_TREE_DUAL_TREE_TRAVERSER_HPP
 
#include <mlpack/prereqs.hpp>
#include <queue>
 
namespace mlpack {
namespace tree {
 
template<
    typename MetricType,
    typename StatisticType,
    typename MatType,
    typename RootPointPolicy
>
template<typename RuleType>
class CoverTree<MetricType, StatisticType, MatType, RootPointPolicy>::
    DualTreeTraverser
{
 public:
  DualTreeTraverser(RuleType& rule);
 
  void Traverse(CoverTree& queryNode, CoverTree& referenceNode);
 
  size_t NumPrunes() const { return numPrunes; }
  size_t& NumPrunes() { return numPrunes; }
 
  size_t NumVisited() const { return 0; }
  size_t NumScores() const { return 0; }
  size_t NumBaseCases() const { return 0; }
 
 private:
  RuleType& rule;
 
  size_t numPrunes;
 
  struct DualCoverTreeMapEntry
  {
    CoverTree<MetricType, StatisticType, MatType, RootPointPolicy>*
        referenceNode;
    double score;
    double baseCase;
    typename RuleType::TraversalInfoType traversalInfo;
 
    bool operator<(const DualCoverTreeMapEntry& other) const
    {
      if (score == other.score)
        return (baseCase < other.baseCase);
      else
        return (score < other.score);
    }
  };
 
  void Traverse(CoverTree& queryNode,
                std::map<int, std::vector<DualCoverTreeMapEntry> >&
                    referenceMap);
 
  void PruneMap(CoverTree& queryNode,
                std::map<int, std::vector<DualCoverTreeMapEntry> >&
                    referenceMap,
                std::map<int, std::vector<DualCoverTreeMapEntry> >&
                    childMap);
 
  void ReferenceRecursion(CoverTree& queryNode,
                          std::map<int, std::vector<DualCoverTreeMapEntry> >&
                              referenceMap);
};
 
} // namespace tree
} // namespace mlpack
 
// Include implementation.
#include "dual_tree_traverser_impl.hpp"
 
#endif