diff options
author | Yuri Gorshenin <y@maps.me> | 2015-07-27 15:38:23 +0300 |
---|---|---|
committer | Alex Zolotarev <alex@maps.me> | 2015-09-23 02:58:04 +0300 |
commit | 83c5d7e6f40063c2d41d378f35accd2885e1caf8 (patch) | |
tree | 0c864cefb987c4d942d3cd8e2a872e43f36c0834 /search | |
parent | be7aecb7efa171aa67ac20397794a217f9421dc3 (diff) |
Review fixes.
Diffstat (limited to 'search')
-rw-r--r-- | search/feature_offset_match.hpp | 48 | ||||
-rw-r--r-- | search/integration_tests/retrieval_test.cpp | 19 | ||||
-rw-r--r-- | search/retrieval.cpp | 67 | ||||
-rw-r--r-- | search/retrieval.hpp | 24 | ||||
-rw-r--r-- | search/search_query.cpp | 15 | ||||
-rw-r--r-- | search/search_query.hpp | 4 |
6 files changed, 100 insertions, 77 deletions
diff --git a/search/feature_offset_match.hpp b/search/feature_offset_match.hpp index 370c1356ac..79fd776f18 100644 --- a/search/feature_offset_match.hpp +++ b/search/feature_offset_match.hpp @@ -265,55 +265,55 @@ public: void Resize(size_t count) { m_holder.resize(count); } - void StartNew(size_t index) + void SwitchTo(size_t index) { ASSERT_LESS(index, m_holder.size(), ()); m_index = index; } - void operator()(Query::TrieValueT const & v) + void operator()(Query::TTrieValue const & v) { if (m_filter(v.m_featureId)) m_holder[m_index].push_back(v); } template <class ToDo> - void GetValues(size_t index, ToDo && toDo) const + void ForEachValue(size_t index, ToDo && toDo) const { for (auto const & value : m_holder[index]) toDo(value); } private: - vector<vector<Query::TrieValueT> > m_holder; + vector<vector<Query::TTrieValue>> m_holder; size_t m_index; TFilter const & m_filter; }; -// Calls toDo for each feature corresponding to at least one sym. +// Calls toDo for each feature corresponding to at least one synonym. // *NOTE* toDo may be called several times for the same feature. template <typename ToDo> -void MatchTokenInTrie(SearchQueryParams::TSynonymsVector const & syms, +void MatchTokenInTrie(SearchQueryParams::TSynonymsVector const & syns, TrieRootPrefix const & trieRoot, ToDo && toDo) { - for (auto const & sym : syms) + for (auto const & syn : syns) { - ASSERT(!sym.empty(), ()); - impl::FullMatchInTrie(trieRoot.m_root, trieRoot.m_prefix, trieRoot.m_prefixSize, sym, toDo); + ASSERT(!syn.empty(), ()); + impl::FullMatchInTrie(trieRoot.m_root, trieRoot.m_prefix, trieRoot.m_prefixSize, syn, toDo); } } -// Calls toDo for each feature whose tokens contains at least one sym -// as a prefix. +// Calls toDo for each feature whose tokens contains at least one +// synonym as a prefix. // *NOTE* toDo may be called serveral times for the same feature. template <typename ToDo> -void MatchTokenPrefixInTrie(SearchQueryParams::TSynonymsVector const & syms, +void MatchTokenPrefixInTrie(SearchQueryParams::TSynonymsVector const & syns, TrieRootPrefix const & trieRoot, ToDo && toDo) { - for (auto const & sym : syms) + for (auto const & syn : syns) { - ASSERT(!sym.empty(), ()); - impl::PrefixMatchInTrie(trieRoot.m_root, trieRoot.m_prefix, trieRoot.m_prefixSize, sym, toDo); + ASSERT(!syn.empty(), ()); + impl::PrefixMatchInTrie(trieRoot.m_root, trieRoot.m_prefix, trieRoot.m_prefixSize, syn, toDo); } } @@ -326,7 +326,7 @@ void MatchTokensInTrie(vector<SearchQueryParams::TSynonymsVector> const & tokens holder.Resize(tokens.size()); for (size_t i = 0; i < tokens.size(); ++i) { - holder.StartNew(i); + holder.SwitchTo(i); MatchTokenInTrie(tokens[i], trieRoot, holder); } } @@ -342,7 +342,7 @@ void MatchTokensAndPrefixInTrie(vector<SearchQueryParams::TSynonymsVector> const MatchTokensInTrie(tokens, trieRoot, holder); holder.Resize(tokens.size() + 1); - holder.StartNew(tokens.size()); + holder.SwitchTo(tokens.size()); MatchTokenPrefixInTrie(prefixTokens, trieRoot, holder); } @@ -364,10 +364,11 @@ bool MatchCategoriesInTrie(SearchQueryParams const & params, TrieIterator const unique_ptr<TrieIterator> const catRoot(trieRoot.GoToEdge(langIx)); MatchTokensInTrie(params.m_tokens, TrieRootPrefix(*catRoot, edge), holder); - // Last token's prefix is used as a complete token here, to limit a number of - // features in the last bucket of a holder. Probably, this is a false optimization. + // Last token's prefix is used as a complete token here, to + // limit the number of features in the last bucket of a + // holder. Probably, this is a false optimization. holder.Resize(params.m_tokens.size() + 1); - holder.StartNew(params.m_tokens.size()); + holder.SwitchTo(params.m_tokens.size()); MatchTokenInTrie(params.m_prefixTokens, TrieRootPrefix(*catRoot, edge), holder); return true; } @@ -375,7 +376,8 @@ bool MatchCategoriesInTrie(SearchQueryParams const & params, TrieIterator const return false; } -// Calls toDo with trie root prefix and language code on each languagу allowed by params. +// Calls toDo with trie root prefix and language code on each language +// allowed by params. template <typename ToDo> void ForEachLangPrefix(SearchQueryParams const & params, TrieIterator const & trieRoot, ToDo && toDo) @@ -412,7 +414,7 @@ void MatchFeaturesInTrie(SearchQueryParams const & params, TrieIterator const & { MatchTokenInTrie(params.m_tokens[i], langRoot, intersecter); }); - categoriesHolder.GetValues(i, intersecter); + categoriesHolder.ForEachValue(i, intersecter); intersecter.NextStep(); } @@ -422,7 +424,7 @@ void MatchFeaturesInTrie(SearchQueryParams const & params, TrieIterator const & { MatchTokenPrefixInTrie(params.m_prefixTokens, langRoot, intersecter); }); - categoriesHolder.GetValues(params.m_tokens.size(), intersecter); + categoriesHolder.ForEachValue(params.m_tokens.size(), intersecter); intersecter.NextStep(); } diff --git a/search/integration_tests/retrieval_test.cpp b/search/integration_tests/retrieval_test.cpp index 3cfad01ce5..08511a1f7b 100644 --- a/search/integration_tests/retrieval_test.cpp +++ b/search/integration_tests/retrieval_test.cpp @@ -147,16 +147,16 @@ UNIT_TEST(Retrieval_Smoke) callback.Offsets().size(), ()); } - // Retrieve at least than 8 whiskey bars from the center. + // Retrieve exactly 8 whiskey bars from the center. { TestCallback callback(handle.GetId()); search::Retrieval::Limits limits; - limits.SetMinNumFeatures(8); + limits.SetMaxNumFeatures(8); retrieval.Init(index, m2::RectD(m2::PointD(4.9, 4.9), m2::PointD(5.1, 5.1)), params, limits); retrieval.Go(callback); TEST(callback.WasTriggered(), ()); - TEST_GREATER_OR_EQUAL(callback.Offsets().size(), 8, ()); + TEST_EQUAL(callback.Offsets().size(), 8, ()); } } @@ -210,7 +210,7 @@ UNIT_TEST(Retrieval_3Mwms) { TestCallback callback(mskHandle.GetId()); search::Retrieval::Limits limits; - limits.SetMinNumFeatures(1); + limits.SetMaxNumFeatures(1); retrieval.Init(index, m2::RectD(m2::PointD(-1.0, -1.0), m2::PointD(1.0, 1.0)), params, limits); retrieval.Go(callback); @@ -219,6 +219,17 @@ UNIT_TEST(Retrieval_3Mwms) } { + TestCallback callback(mskHandle.GetId()); + search::Retrieval::Limits limits; + limits.SetMaxNumFeatures(10 /* more than total number of features in all these mwms */); + + retrieval.Init(index, m2::RectD(m2::PointD(-1.0, -1.0), m2::PointD(1.0, 1.0)), params, limits); + retrieval.Go(callback); + TEST(callback.WasTriggered(), ()); + TEST_EQUAL(callback.Offsets().size(), 3 /* total number of features in all these mwms */, ()); + } + + { MultiMwmCallback callback({mskHandle.GetId(), mtvHandle.GetId(), zrhHandle.GetId()}); search::Retrieval::Limits limits; diff --git a/search/retrieval.cpp b/search/retrieval.cpp index db47039fc1..ba8dc33769 100644 --- a/search/retrieval.cpp +++ b/search/retrieval.cpp @@ -9,6 +9,7 @@ #include "base/stl_add.hpp" +#include "std/algorithm.hpp" #include "std/cmath.hpp" namespace search @@ -21,7 +22,7 @@ struct EmptyFilter }; void RetrieveAddressFeatures(MwmSet::MwmHandle const & handle, SearchQueryParams const & params, - vector<uint32_t> & offsets) + vector<uint32_t> & featureIds) { auto * value = handle.GetValue<MwmValue>(); ASSERT(value, ()); @@ -31,16 +32,16 @@ void RetrieveAddressFeatures(MwmSet::MwmHandle const & handle, SearchQueryParams ::trie::reader::ReadTrie(SubReaderWrapper<Reader>(searchReader.GetPtr()), trie::ValueReader(codingParams), trie::EdgeValueReader())); - offsets.clear(); + featureIds.clear(); auto collector = [&](trie::ValueReader::ValueType const & value) { - offsets.push_back(value.m_featureId); + featureIds.push_back(value.m_featureId); }; MatchFeaturesInTrie(params, *trieRoot, EmptyFilter(), collector); } void RetrieveGeometryFeatures(MwmSet::MwmHandle const & handle, m2::RectD const & viewport, - SearchQueryParams const & params, vector<uint32_t> & offsets) + SearchQueryParams const & params, vector<uint32_t> & featureIds) { auto * value = handle.GetValue<MwmValue>(); ASSERT(value, ()); @@ -54,8 +55,8 @@ void RetrieveGeometryFeatures(MwmSet::MwmHandle const & handle, m2::RectD const covering::IntervalsT const & intervals = covering.Get(scale); ScaleIndex<ModelReaderPtr> index(value->m_cont.GetReader(INDEX_FILE_TAG), value->m_factory); - offsets.clear(); - auto collector = MakeBackInsertFunctor(offsets); + featureIds.clear(); + auto collector = MakeBackInsertFunctor(featureIds); for (auto const & interval : intervals) { index.ForEachInIntervalAndScale(collector, interval.first, interval.second, scale); @@ -64,23 +65,23 @@ void RetrieveGeometryFeatures(MwmSet::MwmHandle const & handle, m2::RectD const } // namespace Retrieval::Limits::Limits() - : m_minNumFeatures(0), + : m_maxNumFeatures(0), m_maxViewportScale(0.0), - m_minNumFeaturesSet(false), + m_maxNumFeaturesSet(false), m_maxViewportScaleSet(false) { } -void Retrieval::Limits::SetMinNumFeatures(uint64_t minNumFeatures) +void Retrieval::Limits::SetMaxNumFeatures(uint64_t maxNumFeatures) { - m_minNumFeatures = minNumFeatures; - m_minNumFeaturesSet = true; + m_maxNumFeatures = maxNumFeatures; + m_maxNumFeaturesSet = true; } -uint64_t Retrieval::Limits::GetMinNumFeatures() const +uint64_t Retrieval::Limits::GetMaxNumFeatures() const { - ASSERT(IsMinNumFeaturesSet(), ()); - return m_minNumFeatures; + ASSERT(IsMaxNumFeaturesSet(), ()); + return m_maxNumFeatures; } void Retrieval::Limits::SetMaxViewportScale(double maxViewportScale) @@ -95,7 +96,7 @@ double Retrieval::Limits::GetMaxViewportScale() const return m_maxViewportScale; } -Retrieval::FeatureBucket::FeatureBucket(MwmSet::MwmHandle && handle) +Retrieval::Bucket::Bucket(MwmSet::MwmHandle && handle) : m_handle(move(handle)), m_intersectsWithViewport(false), m_coveredByViewport(false), @@ -107,7 +108,7 @@ Retrieval::FeatureBucket::FeatureBucket(MwmSet::MwmHandle && handle) m_bounds = header.GetBounds(); } -Retrieval::Retrieval() : m_index(nullptr) {} +Retrieval::Retrieval() : m_index(nullptr), m_featuresReported(0) {} void Retrieval::Init(Index & index, m2::RectD const & viewport, SearchQueryParams const & params, Limits const & limits) @@ -116,6 +117,7 @@ void Retrieval::Init(Index & index, m2::RectD const & viewport, SearchQueryParam m_viewport = viewport; m_params = params; m_limits = limits; + m_featuresReported = 0; vector<shared_ptr<MwmInfo>> infos; index.GetMwmsInfo(infos); @@ -123,8 +125,7 @@ void Retrieval::Init(Index & index, m2::RectD const & viewport, SearchQueryParam m_buckets.clear(); for (auto const & info : infos) { - MwmSet::MwmHandle handle = - index.GetMwmHandleByCountryFile(info->GetLocalFile().GetCountryFile()); + MwmSet::MwmHandle handle = index.GetMwmHandleById(MwmSet::MwmId(info)); if (!handle.IsAlive()) continue; auto * value = handle.GetValue<MwmValue>(); @@ -154,7 +155,7 @@ void Retrieval::Go(Callback & callback) break; if (m_limits.IsMaxViewportScaleSet() && scale >= m_limits.GetMaxViewportScale()) break; - if (m_limits.IsMinNumFeaturesSet() && CountRetrievedFeatures() >= m_limits.GetMinNumFeatures()) + if (m_limits.IsMaxNumFeaturesSet() && m_featuresReported >= m_limits.GetMaxNumFeatures()) break; } @@ -165,8 +166,7 @@ void Retrieval::Go(Callback & callback) // The bucket is not covered by viewport, thus all matching // features were not reported. bucket.m_finished = true; - if (!bucket.m_intersection.empty()) - callback.OnMwmProcessed(bucket.m_handle.GetId(), bucket.m_intersection); + ReportFeatures(bucket, callback); } } @@ -200,11 +200,11 @@ void Retrieval::RetrieveForViewport(m2::RectD const & viewport, Callback & callb if (!bucket.m_coveredByViewport && viewport.IsRectInside(bucket.m_bounds)) { - // Next time we will skip the bucket, so it's better to report all it's features now. + // Next time we will skip the bucket, so it's better to report + // all its features now. bucket.m_coveredByViewport = true; bucket.m_finished = true; - if (!bucket.m_intersection.empty()) - callback.OnMwmProcessed(bucket.m_handle.GetId(), bucket.m_intersection); + ReportFeatures(bucket, callback); } } } @@ -219,12 +219,19 @@ bool Retrieval::ViewportCoversAllMwms() const return true; } -uint64_t Retrieval::CountRetrievedFeatures() const +void Retrieval::ReportFeatures(Bucket & bucket, Callback & callback) { - static_assert(sizeof(size_t) <= sizeof(uint64_t), "uint64_t must be not less than size_t"); - uint64_t count = 0; - for (auto const & bucket : m_buckets) - count += bucket.m_intersection.size(); - return count; + ASSERT(!m_limits.IsMaxNumFeaturesSet() || m_featuresReported <= m_limits.GetMaxNumFeatures(), ()); + if (m_limits.IsMaxNumFeaturesSet()) + { + uint64_t const delta = m_limits.GetMaxNumFeatures() - m_featuresReported; + if (bucket.m_intersection.size() > delta) + bucket.m_intersection.resize(delta); + } + if (!bucket.m_intersection.empty()) + { + callback.OnMwmProcessed(bucket.m_handle.GetId(), bucket.m_intersection); + m_featuresReported += bucket.m_intersection.size(); + } } } // namespace search diff --git a/search/retrieval.hpp b/search/retrieval.hpp index 97f94d39a9..3750e5adba 100644 --- a/search/retrieval.hpp +++ b/search/retrieval.hpp @@ -21,7 +21,7 @@ public: public: virtual ~Callback() = default; - virtual void OnMwmProcessed(MwmSet::MwmId const & id, vector<uint32_t> const & offsets) = 0; + virtual void OnMwmProcessed(MwmSet::MwmId const & id, vector<uint32_t> const & featureIds) = 0; }; // Following class represents a set of retrieval's limits. @@ -30,22 +30,23 @@ public: public: Limits(); - // Sets lower bound on number of features to be retrieved. - void SetMinNumFeatures(uint64_t minNumFeatures); - uint64_t GetMinNumFeatures() const; + // Sets upper bound (inclusive) on a number of features to be + // retrieved. + void SetMaxNumFeatures(uint64_t minNumFeatures); + uint64_t GetMaxNumFeatures() const; // Sets upper bound on a maximum viewport's scale. void SetMaxViewportScale(double maxViewportScale); double GetMaxViewportScale() const; - inline bool IsMinNumFeaturesSet() const { return m_minNumFeaturesSet; } + inline bool IsMaxNumFeaturesSet() const { return m_maxNumFeaturesSet; } inline bool IsMaxViewportScaleSet() const { return m_maxViewportScaleSet; } private: - uint64_t m_minNumFeatures; + uint64_t m_maxNumFeatures; double m_maxViewportScale; - bool m_minNumFeaturesSet : 1; + bool m_maxNumFeaturesSet : 1; bool m_maxViewportScaleSet : 1; }; @@ -57,9 +58,9 @@ public: void Go(Callback & callback); private: - struct FeatureBucket + struct Bucket { - FeatureBucket(MwmSet::MwmHandle && handle); + Bucket(MwmSet::MwmHandle && handle); MwmSet::MwmHandle m_handle; vector<uint32_t> m_addressFeatures; @@ -77,13 +78,14 @@ private: bool ViewportCoversAllMwms() const; - uint64_t CountRetrievedFeatures() const; + void ReportFeatures(Bucket & bucket, Callback & callback); Index * m_index; m2::RectD m_viewport; SearchQueryParams m_params; Limits m_limits; + uint64_t m_featuresReported; - vector<FeatureBucket> m_buckets; + vector<Bucket> m_buckets; }; } // namespace search diff --git a/search/search_query.cpp b/search/search_query.cpp index 85eeee4e29..5579035eca 100644 --- a/search/search_query.cpp +++ b/search/search_query.cpp @@ -931,7 +931,7 @@ template <class T> void Query::ProcessSuggestions(vector<T> & vec, Results & res } } -void Query::AddResultFromTrie(TrieValueT const & val, MwmSet::MwmId const & mwmID, +void Query::AddResultFromTrie(TTrieValue const & val, MwmSet::MwmId const & mwmID, ViewportID vID /*= DEFAULT_V*/) { impl::PreResult1 res(FeatureID(mwmID, val.m_featureId), val.m_rank, @@ -1266,14 +1266,14 @@ namespace impl struct Locality { string m_name, m_enName; ///< native name and english name of locality - Query::TrieValueT m_value; + Query::TTrieValue m_value; vector<size_t> m_matchedTokens; ///< indexes of matched tokens for locality ftypes::Type m_type; double m_radius; Locality() : m_type(ftypes::NONE) {} - Locality(Query::TrieValueT const & val, ftypes::Type type) + Locality(Query::TTrieValue const & val, ftypes::Type type) : m_value(val), m_type(type), m_radius(0) { } @@ -1633,9 +1633,10 @@ namespace impl } void Resize(size_t) {} - void StartNew(size_t ind) { m_index = ind; } - void operator() (Query::TrieValueT const & v) + void SwitchTo(size_t ind) { m_index = ind; } + + void operator() (Query::TTrieValue const & v) { if (m_query.IsCancelled()) throw Query::CancelException(); @@ -1752,7 +1753,7 @@ void Query::SearchLocality(MwmValue * pMwm, impl::Locality & res1, impl::Region // Last token's prefix is used as a complete token here, to limit number of results. doFind.Resize(params.m_tokens.size() + 1); - doFind.StartNew(params.m_tokens.size()); + doFind.SwitchTo(params.m_tokens.size()); MatchTokenInTrie(params.m_prefixTokens, langRoot, doFind); doFind.SortLocalities(); @@ -1858,7 +1859,7 @@ void Query::SearchInMWM(Index::MwmHandle const & mwmHandle, SearchQueryParams co MwmSet::MwmId const mwmId = mwmHandle.GetId(); FeaturesFilter filter( (viewportId == DEFAULT_V || isWorld) ? 0 : &m_offsetsInViewport[viewportId][mwmId], *this); - MatchFeaturesInTrie(params, *trieRoot, filter, [&](TrieValueT const & value) + MatchFeaturesInTrie(params, *trieRoot, filter, [&](TTrieValue const & value) { AddResultFromTrie(value, mwmId, viewportId); }); diff --git a/search/search_query.hpp b/search/search_query.hpp index 043f0b7564..5b930cfc90 100644 --- a/search/search_query.hpp +++ b/search/search_query.hpp @@ -115,7 +115,7 @@ public: /// @name This stuff is public for implementation classes in search_query.cpp /// Do not use it in client code. //@{ - typedef trie::ValueReader::ValueType TrieValueT; + using TTrieValue = trie::ValueReader::ValueType; void InitParams(bool localitySearch, SearchQueryParams & params); @@ -149,7 +149,7 @@ private: COUNT_V = 2 // Should always be the last }; - void AddResultFromTrie(TrieValueT const & val, MwmSet::MwmId const & mwmID, + void AddResultFromTrie(TTrieValue const & val, MwmSet::MwmId const & mwmID, ViewportID vID = DEFAULT_V); template <class T> void MakePreResult2(vector<T> & cont, vector<FeatureID> & streets); |