1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#pragma once
#include "search/features_layer.hpp"
#include "search/intersection_result.hpp"
#include <utility>
#include <vector>
#if defined(DEBUG)
#include "base/logging.hpp"
#include "base/timer.hpp"
#endif // defined(DEBUG)
class FeaturesVector;
class MwmValue;
namespace base
{
class Cancellable;
}
namespace search
{
class FeaturesLayerMatcher;
// This class is able to find all paths through a layered graph, with
// vertices as features, and edges as pairs of vertices satisfying
// belongs-to relation. For more details on belongs-to relation see
// documentation for FeaturesLayerMatcher.
//
// In short, this class is able to find all features matching to a
// given interpretation of a search query.
//
// NOTE: this class *IS* thread-safe.
class FeaturesLayerPathFinder
{
public:
// An internal mode. The modes should produce similar results
// and differ only in efficiency: a mode that is faster
// for a search query may be slower for another.
// Modes other than MODE_AUTO should be used only by the testing code.
enum Mode
{
MODE_AUTO,
MODE_TOP_DOWN,
MODE_BOTTOM_UP
};
FeaturesLayerPathFinder(base::Cancellable const & cancellable);
template <typename TFn>
void ForEachReachableVertex(FeaturesLayerMatcher & matcher,
std::vector<FeaturesLayer const *> const & layers, TFn && fn)
{
if (layers.empty())
return;
// TODO (@y): remove following code as soon as
// FindReachableVertices() will work fast for most cases
// (significantly less than 1 second).
#if defined(DEBUG)
for (auto const * layer : layers)
LOG(LINFO, (DebugPrint(*layer)));
base::Timer timer;
#endif // defined(DEBUG)
std::vector<IntersectionResult> results;
FindReachableVertices(matcher, layers, results);
#if defined(DEBUG)
LOG(LINFO, ("Found:", results.size(), "elapsed:", timer.ElapsedSeconds(), "seconds"));
#endif // defined(DEBUG)
for_each(results.begin(), results.end(), std::forward<TFn>(fn));
}
static void SetModeForTesting(Mode mode) { m_mode = mode; }
private:
void FindReachableVertices(FeaturesLayerMatcher & matcher,
std::vector<FeaturesLayer const *> const & layers,
std::vector<IntersectionResult> & results);
// Tries to find all |reachable| features from the lowest layer in a
// high level -> low level pass.
void FindReachableVerticesTopDown(FeaturesLayerMatcher & matcher,
std::vector<FeaturesLayer const *> const & layers,
std::vector<IntersectionResult> & results);
// Tries to find all |reachable| features from the lowest layer in a
// low level -> high level pass.
void FindReachableVerticesBottomUp(FeaturesLayerMatcher & matcher,
std::vector<FeaturesLayer const *> const & layers,
std::vector<IntersectionResult> & results);
base::Cancellable const & m_cancellable;
static Mode m_mode;
};
} // namespace search
|