diff options
author | vng <viktor.govako@gmail.com> | 2015-05-28 19:08:59 +0300 |
---|---|---|
committer | Alex Zolotarev <alex@maps.me> | 2015-09-23 02:50:06 +0300 |
commit | fd3eb0e4f19e9db963ed8160d3beef804683295a (patch) | |
tree | c3cafbd89cd4faf667f83ab4c13f3a10e3876b8a /search | |
parent | df3e973fe84aa1a5d866190755aa75280396ca18 (diff) |
[search] Logic refactoring: search only in current viewport (or only around position for watches), including world search.
Diffstat (limited to 'search')
-rw-r--r-- | search/geometry_utils.cpp | 33 | ||||
-rw-r--r-- | search/geometry_utils.hpp | 9 | ||||
-rw-r--r-- | search/house_detector.hpp | 2 | ||||
-rw-r--r-- | search/intermediate_result.cpp | 96 | ||||
-rw-r--r-- | search/intermediate_result.hpp | 26 | ||||
-rw-r--r-- | search/params.cpp | 31 | ||||
-rw-r--r-- | search/params.hpp | 21 | ||||
-rw-r--r-- | search/search_engine.cpp | 213 | ||||
-rw-r--r-- | search/search_engine.hpp | 20 | ||||
-rw-r--r-- | search/search_query.cpp | 171 | ||||
-rw-r--r-- | search/search_query.hpp | 42 |
11 files changed, 235 insertions, 429 deletions
diff --git a/search/geometry_utils.cpp b/search/geometry_utils.cpp index 90a137e11d..27a7e420fc 100644 --- a/search/geometry_utils.cpp +++ b/search/geometry_utils.cpp @@ -1,6 +1,7 @@ -#include "search/geometry_utils.hpp" +#include "geometry_utils.hpp" #include "indexer/mercator.hpp" +#include "indexer/scales.hpp" namespace search @@ -11,22 +12,28 @@ double PointDistance(m2::PointD const & a, m2::PointD const & b) return MercatorBounds::DistanceOnEarth(a, b); } -uint8_t ViewportDistance(m2::RectD const & viewport, m2::PointD const & p) +bool IsEqualMercator(m2::RectD const & r1, m2::RectD const & r2, double epsMeters) { - if (viewport.IsPointInside(p)) - return 0; + double const eps = epsMeters * MercatorBounds::degreeInMetres; + return m2::IsEqual(r1, r2, eps, eps); +} - m2::RectD r = viewport; - r.Scale(3); - if (r.IsPointInside(p)) - return 1; +// 12.5 - lower bound for rect when we need to inflate it +// 1.5 - inflate delta for viewport scale +// 7 - query scale depth to cache viewport features - r = viewport; - r.Scale(5); - if (r.IsPointInside(p)) - return 2; +m2::RectD GetInflatedViewport(m2::RectD const & viewport) +{ + double const level = scales::GetScaleLevelD(viewport); + if (level < 12.5) + return viewport; - return 3; + return scales::GetRectForLevel(level - 1.5, viewport.Center()); +} + +int GetQueryIndexScale(m2::RectD const & viewport) +{ + return scales::GetScaleLevel(viewport) + 7; } } diff --git a/search/geometry_utils.hpp b/search/geometry_utils.hpp index 19c83e2cba..ab13536d14 100644 --- a/search/geometry_utils.hpp +++ b/search/geometry_utils.hpp @@ -7,8 +7,13 @@ namespace search { +// Distance between 2 mercator points in meters. double PointDistance(m2::PointD const & a, m2::PointD const & b); - -uint8_t ViewportDistance(m2::RectD const & viewport, m2::PointD const & p); +// Test for equal rects with epsilon in meters. +bool IsEqualMercator(m2::RectD const & r1, m2::RectD const & r2, double epsMeters); +// Get inflated viewport rect for search query. +m2::RectD GetInflatedViewport(m2::RectD const & viewport); +// Get scale level to make geometry index query for current viewport. +int GetQueryIndexScale(m2::RectD const & viewport); } diff --git a/search/house_detector.hpp b/search/house_detector.hpp index ff90ecdf6d..013bea68d6 100644 --- a/search/house_detector.hpp +++ b/search/house_detector.hpp @@ -202,7 +202,7 @@ inline void swap(MergedStreet & s1, MergedStreet & s2) s1.Swap(s2); } -struct HouseResult : public IndexedValueBase<2> +struct HouseResult : public IndexedValueBase<1> { House const * m_house; MergedStreet const * m_street; diff --git a/search/intermediate_result.cpp b/search/intermediate_result.cpp index 2f99fd9c58..4b11c9e4fe 100644 --- a/search/intermediate_result.cpp +++ b/search/intermediate_result.cpp @@ -1,5 +1,5 @@ -#include "search/intermediate_result.hpp" -#include "search/geometry_utils.hpp" +#include "intermediate_result.hpp" +#include "geometry_utils.hpp" #include "storage/country_info.hpp" @@ -27,29 +27,12 @@ double const DIST_SAME_STREET = 5000.0; namespace impl { -template <class T> bool LessViewportDistanceT(T const & r1, T const & r2) -{ - if (r1.m_viewportDistance != r2.m_viewportDistance) - return (r1.m_viewportDistance < r2.m_viewportDistance); - - if (r1.m_rank != r2.m_rank) - return (r1.m_rank > r2.m_rank); - - return (r1.m_distanceFromViewportCenter < r2.m_distanceFromViewportCenter); -} - template <class T> bool LessRankT(T const & r1, T const & r2) { if (r1.m_rank != r2.m_rank) return (r1.m_rank > r2.m_rank); - if (r1.m_viewportDistance != r2.m_viewportDistance) - return (r1.m_viewportDistance < r2.m_viewportDistance); - - if (r1.m_distance != r2.m_distance) - return (r1.m_distance < r2.m_distance); - - return (r1.m_distanceFromViewportCenter < r2.m_distanceFromViewportCenter); + return (r1.m_distance < r2.m_distance); } template <class T> bool LessDistanceT(T const & r1, T const & r2) @@ -57,14 +40,11 @@ template <class T> bool LessDistanceT(T const & r1, T const & r2) if (r1.m_distance != r2.m_distance) return (r1.m_distance < r2.m_distance); - if (r1.m_rank != r2.m_rank) - return (r1.m_rank > r2.m_rank); - - return (r1.m_distanceFromViewportCenter < r2.m_distanceFromViewportCenter); + return (r1.m_rank > r2.m_rank); } PreResult1::PreResult1(FeatureID const & fID, uint8_t rank, m2::PointD const & center, - m2::PointD const & pos, m2::RectD const & viewport, int8_t viewportID) + m2::PointD const & pivot, int8_t viewportID) : m_id(fID), m_center(center), m_rank(rank), @@ -72,13 +52,13 @@ PreResult1::PreResult1(FeatureID const & fID, uint8_t rank, m2::PointD const & c { ASSERT(m_id.IsValid(), ()); - CalcParams(viewport, pos); + CalcParams(pivot); } -PreResult1::PreResult1(m2::PointD const & center, m2::PointD const & pos, m2::RectD const & viewport) +PreResult1::PreResult1(m2::PointD const & center, m2::PointD const & pivot) : m_center(center) { - CalcParams(viewport, pos); + CalcParams(pivot); } namespace @@ -92,24 +72,10 @@ void AssertValid(m2::PointD const & p) } -void PreResult1::CalcParams(m2::RectD const & viewport, m2::PointD const & pos) +void PreResult1::CalcParams(m2::PointD const & pivot) { AssertValid(m_center); - - // Check if point is valid (see Query::empty_pos_value). - if (pos.x > -500 && pos.y > -500) - { - AssertValid(pos); - m_distance = PointDistance(m_center, pos); - } - else - { - // empty distance - m_distance = -1.0; - } - - m_viewportDistance = ViewportDistance(viewport, m_center); - m_distanceFromViewportCenter = PointDistance(m_center, viewport.Center()); + m_distance = PointDistance(m_center, pivot); } bool PreResult1::LessRank(PreResult1 const & r1, PreResult1 const & r2) @@ -122,28 +88,17 @@ bool PreResult1::LessDistance(PreResult1 const & r1, PreResult1 const & r2) return LessDistanceT(r1, r2); } -bool PreResult1::LessViewportDistance(PreResult1 const & r1, PreResult1 const & r2) -{ - return LessViewportDistanceT(r1, r2); -} - bool PreResult1::LessPointsForViewport(PreResult1 const & r1, PreResult1 const & r2) { return r1.m_id < r2.m_id; } -void PreResult2::CalcParams(m2::RectD const & viewport, m2::PointD const & pos) +void PreResult2::CalcParams(m2::PointD const & pivot) { - // dummy object to avoid copy-paste - PreResult1 res(GetCenter(), pos, viewport); - - m_distance = res.m_distance; - m_distanceFromViewportCenter = res.m_distanceFromViewportCenter; - m_viewportDistance = res.m_viewportDistance; + m_distance = PointDistance(GetCenter(), pivot); } -PreResult2::PreResult2(FeatureType const & f, PreResult1 const * p, - m2::RectD const & viewport, m2::PointD const & pos, +PreResult2::PreResult2(FeatureType const & f, PreResult1 const * p, m2::PointD const & pivot, string const & displayName, string const & fileName) : m_id(f.GetID()), m_types(f), @@ -168,7 +123,7 @@ PreResult2::PreResult2(FeatureType const & f, PreResult1 const * p, fCenter = f.GetLimitRect(FeatureType::WORST_GEOMETRY).Center(); m_region.SetParams(fileName, fCenter); - CalcParams(viewport, pos); + CalcParams(pivot); } PreResult2::PreResult2(double lat, double lon) @@ -236,7 +191,7 @@ Result PreResult2::GenerateFinalResult( case RESULT_FEATURE: return Result(m_id, GetCenter(), m_str, info.m_name, ReadableFeatureType(pCat, pTypes, locale) #ifdef DEBUG - + ' ' + strings::to_string(static_cast<int>(m_rank)) + + ' ' + strings::to_string(int(m_rank)) #endif , type); @@ -267,11 +222,6 @@ bool PreResult2::LessDistance(PreResult2 const & r1, PreResult2 const & r2) return LessDistanceT(r1, r2); } -bool PreResult2::LessViewportDistance(PreResult2 const & r1, PreResult2 const & r2) -{ - return LessViewportDistanceT(r1, r2); -} - bool PreResult2::StrictEqualF::operator() (PreResult2 const & r) const { if (m_r.m_resultType == r.m_resultType && m_r.m_resultType == RESULT_FEATURE) @@ -297,8 +247,6 @@ bool PreResult2::LessLinearTypesF::operator() (PreResult2 const & r1, PreResult2 return (t1 < t2); // Should stay the best feature, after unique, so add this criteria: - if (r1.m_viewportDistance != r2.m_viewportDistance) - return (r1.m_viewportDistance < r2.m_viewportDistance); return (r1.m_distance < r2.m_distance); } @@ -326,13 +274,13 @@ bool PreResult2::IsStreet() const string PreResult2::DebugPrint() const { - string res("IntermediateResult: "); - res += "Name: " + m_str; - res += "; Type: " + ::DebugPrint(GetBestType()); - res += "; Rank: " + ::DebugPrint(m_rank); - res += "; Viewport distance: " + ::DebugPrint(m_viewportDistance); - res += "; Distance: " + ::DebugPrint(m_distance); - return res; + stringstream ss; + ss << "{ IntermediateResult: " << + "Name: " << m_str << + "; Type: " << GetBestType() << + "; Rank: " << int(m_rank) << + "; Distance: " << m_distance << " }"; + return ss.str(); } uint32_t PreResult2::GetBestType(set<uint32_t> const * pPrefferedTypes) const diff --git a/search/intermediate_result.hpp b/search/intermediate_result.hpp index 1626f2f5c1..85987cd303 100644 --- a/search/intermediate_result.hpp +++ b/search/intermediate_result.hpp @@ -1,5 +1,5 @@ #pragma once -#include "search/result.hpp" +#include "result.hpp" #include "indexer/feature_data.hpp" @@ -19,7 +19,6 @@ namespace impl { template <class T> bool LessRankT(T const & r1, T const & r2); -template <class T> bool LessViewportDistanceT(T const & r1, T const & r2); template <class T> bool LessDistanceT(T const & r1, T const & r2); /// First pass results class. Objects are creating during search in trie. @@ -28,26 +27,23 @@ class PreResult1 { friend class PreResult2; template <class T> friend bool LessRankT(T const & r1, T const & r2); - template <class T> friend bool LessViewportDistanceT(T const & r1, T const & r2); template <class T> friend bool LessDistanceT(T const & r1, T const & r2); FeatureID m_id; m2::PointD m_center; - double m_distance, m_distanceFromViewportCenter; - uint8_t m_viewportDistance; + double m_distance; uint8_t m_rank; int8_t m_viewportID; - void CalcParams(m2::RectD const & viewport, m2::PointD const & pos); + void CalcParams(m2::PointD const & pivot); public: PreResult1(FeatureID const & fID, uint8_t rank, m2::PointD const & center, - m2::PointD const & pos, m2::RectD const & viewport, int8_t viewportID); - PreResult1(m2::PointD const & center, m2::PointD const & pos, m2::RectD const & viewport); + m2::PointD const & pivot, int8_t viewportID); + PreResult1(m2::PointD const & center, m2::PointD const & pivot); static bool LessRank(PreResult1 const & r1, PreResult1 const & r2); static bool LessDistance(PreResult1 const & r1, PreResult1 const & r2); - static bool LessViewportDistance(PreResult1 const & r1, PreResult1 const & r2); static bool LessPointsForViewport(PreResult1 const & r1, PreResult1 const & r2); inline FeatureID GetID() const { return m_id; } @@ -63,7 +59,7 @@ class PreResult2 { friend class PreResult2Maker; - void CalcParams(m2::RectD const & viewport, m2::PointD const & pos); + void CalcParams(m2::PointD const & pivot); public: enum ResultType @@ -74,8 +70,7 @@ public: }; /// For RESULT_FEATURE. - PreResult2(FeatureType const & f, PreResult1 const * p, - m2::RectD const & viewport, m2::PointD const & pos, + PreResult2(FeatureType const & f, PreResult1 const * p, m2::PointD const & pivot, string const & displayName, string const & fileName); /// For RESULT_LATLON. @@ -99,7 +94,6 @@ public: static bool LessRank(PreResult2 const & r1, PreResult2 const & r2); static bool LessDistance(PreResult2 const & r1, PreResult2 const & r2); - static bool LessViewportDistance(PreResult2 const & r1, PreResult2 const & r2); /// Filter equal features for different mwm's. class StrictEqualF @@ -133,7 +127,6 @@ public: private: template <class T> friend bool LessRankT(T const & r1, T const & r2); - template <class T> friend bool LessViewportDistanceT(T const & r1, T const & r2); template <class T> friend bool LessDistanceT(T const & r1, T const & r2); bool IsEqualCommon(PreResult2 const & r) const; @@ -166,10 +159,9 @@ private: m2::PointD GetCenter() const { return m_region.m_point; } - double m_distance, m_distanceFromViewportCenter; + double m_distance; ResultType m_resultType; - uint16_t m_rank; - uint8_t m_viewportDistance; + uint8_t m_rank; feature::EGeomType m_geomType; }; diff --git a/search/params.cpp b/search/params.cpp index 0a66004588..78a2683cc3 100644 --- a/search/params.cpp +++ b/search/params.cpp @@ -1,4 +1,6 @@ -#include "search/params.hpp" +#include "params.hpp" + +#include "indexer/mercator.hpp" #include "coding/multilang_utf8_string.hpp" @@ -6,7 +8,9 @@ namespace search { -SearchParams::SearchParams() : m_searchMode(ALL), m_forceSearch(false), m_validPos(false) +SearchParams::SearchParams() + : m_searchRadiusM(-1.0), m_searchMode(ALL), + m_forceSearch(false), m_validPos(false) { } @@ -17,21 +21,32 @@ void SearchParams::SetPosition(double lat, double lon) m_validPos = true; } +bool SearchParams::GetSearchRect(m2::RectD & rect) const +{ + if (IsSearchAroundPosition()) + { + rect = MercatorBounds::MetresToXY(m_lon, m_lat, m_searchRadiusM); + return true; + } + return false; +} + bool SearchParams::IsEqualCommon(SearchParams const & rhs) const { return (m_query == rhs.m_query && m_inputLocale == rhs.m_inputLocale && m_validPos == rhs.m_validPos && - m_searchMode == rhs.m_searchMode); + m_searchMode == rhs.m_searchMode && + m_searchRadiusM == rhs.m_searchRadiusM); } string DebugPrint(SearchParams const & params) { - ostringstream stream; - stream << "{ Query = " << params.m_query << - ", Locale = " << params.m_inputLocale << - ", Mode = " << params.m_searchMode << " }"; - return stream.str(); + ostringstream ss; + ss << "{ SearchParams: Query = " << params.m_query << + ", Locale = " << params.m_inputLocale << + ", Mode = " << params.m_searchMode << " }"; + return ss.str(); } } // namespace search diff --git a/search/params.hpp b/search/params.hpp index 13ac8feca7..09fa48c5bd 100644 --- a/search/params.hpp +++ b/search/params.hpp @@ -1,6 +1,7 @@ #pragma once #include "geometry/point2d.hpp" +#include "geometry/rect2d.hpp" #include "std/function.hpp" #include "std/string.hpp" @@ -26,20 +27,25 @@ namespace search //@{ enum SearchModeT { - AROUND_POSITION = 1, - IN_VIEWPORT = 2, - SEARCH_WORLD = 4, - SEARCH_ADDRESS = 8, - ALL = AROUND_POSITION | IN_VIEWPORT | SEARCH_WORLD | SEARCH_ADDRESS + IN_VIEWPORT_ONLY = 1, + SEARCH_WORLD = 2, + SEARCH_ADDRESS = 4, + ALL = SEARCH_WORLD | SEARCH_ADDRESS }; inline void SetSearchMode(int mode) { m_searchMode = mode; } - inline bool NeedSearch(SearchModeT mode) const { return ((m_searchMode & mode) != 0); } - inline bool IsSortByViewport() const { return m_searchMode == IN_VIEWPORT; } + inline bool HasSearchMode(SearchModeT mode) const { return ((m_searchMode & mode) != 0); } //@} void SetPosition(double lat, double lon); bool IsValidPosition() const { return m_validPos; } + bool IsSearchAroundPosition() const + { + return (m_searchRadiusM > 0 && IsValidPosition()); + } + + void SetSearchRadius(double radiusM) { m_searchRadiusM = radiusM; } + bool GetSearchRect(m2::RectD & rect) const; /// @param[in] locale can be "fr", "en-US", "ru_RU" etc. void SetInputLocale(string const & locale) { m_inputLocale = locale; } @@ -59,6 +65,7 @@ namespace search friend string DebugPrint(SearchParams const & params); private: + double m_searchRadiusM; int m_searchMode; bool m_forceSearch, m_validPos; }; diff --git a/search/search_engine.cpp b/search/search_engine.cpp index f9669b248f..21a768405e 100644 --- a/search/search_engine.cpp +++ b/search/search_engine.cpp @@ -1,5 +1,6 @@ -#include "search/search_engine.hpp" -#include "search/search_query.hpp" +#include "search_engine.hpp" +#include "search_query.hpp" +#include "geometry_utils.hpp" #include "storage/country_info.hpp" @@ -25,6 +26,8 @@ namespace search { +double const DIST_EQUAL_QUERY = 100.0; + typedef vector<Query::SuggestT> SuggestsContainerT; class EngineData @@ -75,9 +78,10 @@ public: Engine::Engine(IndexType const * pIndex, Reader * pCategoriesR, ModelReaderPtr polyR, ModelReaderPtr countryR, string const & locale) - : m_readyThread(false), - m_pData(new EngineData(pCategoriesR, polyR, countryR)) + : m_pData(new EngineData(pCategoriesR, polyR, countryR)) { + m_isReadyThread.clear(); + InitSuggestions doInit; m_pData->m_categories.ForEachName(bind<void>(ref(doInit), _1)); doInit.GetSuggests(m_pData->m_stringsToSuggest); @@ -98,66 +102,32 @@ void Engine::SupportOldFormat(bool b) m_pQuery->SupportOldFormat(b); } -namespace -{ - m2::PointD GetViewportXY(double lat, double lon) - { - return MercatorBounds::FromLatLon(lat, lon); - } - m2::RectD GetViewportRect(double lat, double lon, double radius = 20000) - { - return MercatorBounds::MetresToXY(lon, lat, radius); - } - - enum { VIEWPORT_RECT = 0, NEARME_RECT = 1 }; - - // X metres in mercator (lon, lat) units. - double const epsEqualRects = 100.0 * MercatorBounds::degreeInMetres; - - /// Check rects for optimal search (avoid duplicating). - void AnalyzeRects(m2::RectD arrRects[2]) - { - if (arrRects[NEARME_RECT].IsRectInside(arrRects[VIEWPORT_RECT]) && - arrRects[NEARME_RECT].Center().EqualDxDy(arrRects[VIEWPORT_RECT].Center(), epsEqualRects)) - { - arrRects[VIEWPORT_RECT].MakeEmpty(); - } - else - { - if (arrRects[VIEWPORT_RECT].IsRectInside(arrRects[NEARME_RECT]) && - (scales::GetScaleLevel(arrRects[VIEWPORT_RECT]) + Query::SCALE_SEARCH_DEPTH >= scales::GetUpperScale())) - { - arrRects[NEARME_RECT].MakeEmpty(); - } - } - } -} - -void Engine::PrepareSearch(m2::RectD const & viewport, - bool hasPt, double lat, double lon) +void Engine::PrepareSearch(m2::RectD const & viewport) { - m2::RectD const nearby = (hasPt ? GetViewportRect(lat, lon) : m2::RectD()); - // bind does copy of all rects - GetPlatform().RunAsync(bind(&Engine::SetViewportAsync, this, viewport, nearby)); + GetPlatform().RunAsync(bind(&Engine::SetViewportAsync, this, viewport)); } -bool Engine::Search(SearchParams const & params, m2::RectD const & viewport, bool viewportPoints/* = false*/) +bool Engine::Search(SearchParams const & params, m2::RectD const & viewport) { // Check for equal query. - // There is no need to put synch here for reading m_params, + // There is no need to synchronize here for reading m_params, // because this function is always called from main thread (one-by-one for queries). if (!params.IsForceSearch() && m_params.IsEqualCommon(params) && - m2::IsEqual(m_viewport, viewport, epsEqualRects, epsEqualRects)) + (m_viewport.IsValid() && IsEqualMercator(m_viewport, viewport, DIST_EQUAL_QUERY))) { - if (!m_params.IsValidPosition()) - return false; - - // Check distance between previous and current user's position. - if (ms::DistanceOnEarth(m_params.m_lat, m_params.m_lon, params.m_lat, params.m_lon) < 500.0) + if (m_params.IsSearchAroundPosition() && + ms::DistanceOnEarth(m_params.m_lat, m_params.m_lon, params.m_lat, params.m_lon) > DIST_EQUAL_QUERY) + { + // Go forward only if we search around position and it's changed significantly. + } + else + { + // Skip this query in all other cases. return false; + } } { @@ -169,7 +139,7 @@ bool Engine::Search(SearchParams const & params, m2::RectD const & viewport, boo } // Run task. - GetPlatform().RunAsync(bind(&Engine::SearchAsync, this, viewportPoints)); + GetPlatform().RunAsync(bind(&Engine::SearchAsync, this)); return true; } @@ -180,7 +150,7 @@ void Engine::GetResults(Results & res) res = m_searchResults; } -void Engine::SetViewportAsync(m2::RectD const & viewport, m2::RectD const & nearby) +void Engine::SetViewportAsync(m2::RectD const & viewport) { // First of all - cancel previous query. m_pQuery->DoCancel(); @@ -188,109 +158,76 @@ void Engine::SetViewportAsync(m2::RectD const & viewport, m2::RectD const & near // Enter to run new search. threads::MutexGuard searchGuard(m_searchMutex); - m2::RectD arrRects[] = { viewport, nearby }; - AnalyzeRects(arrRects); - - m_pQuery->SetViewport(arrRects, ARRAY_SIZE(arrRects)); -} - -/* -namespace -{ - bool LessByDistance(Result const & r1, Result const & r2) - { - bool const isSuggest1 = r1.GetResultType() == Result::RESULT_SUGGESTION; - bool const isNotSuggest2 = r2.GetResultType() != Result::RESULT_SUGGESTION; - - if (isSuggest1) - { - // suggestions should always be on top - return isNotSuggest2; - } - else if (isNotSuggest2) - { - // we can't call GetDistance for suggestions - return (r1.GetDistance() < r2.GetDistance()); - } - else - return false; - } + m_pQuery->SetViewport(GetInflatedViewport(viewport)); } -*/ void Engine::EmitResults(SearchParams const & params, Results & res) { -// if (params.IsValidPosition() && -// params.NeedSearch(SearchParams::AROUND_POSITION) && -// !params.NeedSearch(SearchParams::IN_VIEWPORT) && -// !params.NeedSearch(SearchParams::SEARCH_WORLD)) -// { -// res.Sort(&LessByDistance); -// } - m_searchResults = res; + // Basic test of our statistics engine. alohalytics::LogEvent("searchEmitResults", alohalytics::TStringMap({{params.m_query, strings::to_string(res.GetCount())}})); + params.m_callback(res); } -void Engine::SearchAsync(bool viewportPoints) +void Engine::SetRankPivot(SearchParams const & params, m2::RectD const & viewport) { + if (!params.HasSearchMode(SearchParams::IN_VIEWPORT_ONLY) && params.IsValidPosition()) { - // Avoid many threads waiting in search mutex. One is enough. - threads::MutexGuard readyGuard(m_readyMutex); - if (m_readyThread) + m2::PointD const pos = MercatorBounds::FromLatLon(params.m_lat, params.m_lon); + if (m2::Inflate(viewport, viewport.SizeX() / 4.0, viewport.SizeY() / 4.0).IsPointInside(pos)) + { + m_pQuery->SetRankPivot(pos); return; - m_readyThread = true; + } } + m_pQuery->SetRankPivot(viewport.Center()); +} + +void Engine::SearchAsync() +{ + if (m_isReadyThread.test_and_set()) + return; + // First of all - cancel previous query. m_pQuery->DoCancel(); // Enter to run new search. threads::MutexGuard searchGuard(m_searchMutex); - { - threads::MutexGuard readyGuard(m_readyMutex); - m_readyThread = false; - } + m_isReadyThread.clear(); // Get current search params. SearchParams params; - m2::RectD arrRects[2]; + m2::RectD viewport; + bool viewportPoints; { threads::MutexGuard updateGuard(m_updateMutex); params = m_params; - arrRects[VIEWPORT_RECT] = m_viewport; - } - // Initialize query. - m_pQuery->Init(viewportPoints); + viewportPoints = params.HasSearchMode(SearchParams::IN_VIEWPORT_ONLY); - // Set search viewports according to search params. - if (params.IsValidPosition()) - { - if (params.NeedSearch(SearchParams::AROUND_POSITION)) + if (!params.GetSearchRect(viewport)) { - m_pQuery->SetPosition(GetViewportXY(params.m_lat, params.m_lon)); - arrRects[NEARME_RECT] = GetViewportRect(params.m_lat, params.m_lon); + if (viewportPoints) + viewport = m_viewport; + else + viewport = GetInflatedViewport(m_viewport); } } - else - m_pQuery->NullPosition(); - if (!params.NeedSearch(SearchParams::IN_VIEWPORT)) - arrRects[VIEWPORT_RECT].MakeEmpty(); + // Initialize query. + m_pQuery->Init(viewportPoints); - if (arrRects[NEARME_RECT].IsValid() && arrRects[VIEWPORT_RECT].IsValid()) - AnalyzeRects(arrRects); + SetRankPivot(params, viewport); - m_pQuery->SetViewport(arrRects, 2); + m_pQuery->SetViewport(viewport); - m_pQuery->SetSearchInWorld(params.NeedSearch(SearchParams::SEARCH_WORLD)); - m_pQuery->SetSortByViewport(params.IsSortByViewport()); + m_pQuery->SetSearchInWorld(params.HasSearchMode(SearchParams::SEARCH_WORLD)); // Language validity is checked inside m_pQuery->SetInputLocale(params.m_inputLocale); @@ -307,34 +244,13 @@ void Engine::SearchAsync(bool viewportPoints) try { - /* - if (emptyQuery) - { - // Search for empty query only around viewport. - if (params.IsValidPosition()) - { - double arrR[] = { 500, 1000, 2000 }; - for (size_t i = 0; i < ARRAY_SIZE(arrR); ++i) - { - res.Clear(); - m_pQuery->SearchAllInViewport(GetViewportRect(params.m_lat, params.m_lon, arrR[i]), - res, 3*RESULTS_COUNT); - - if (m_pQuery->IsCanceled() || res.GetCount() >= 2*RESULTS_COUNT) - break; - } - } - } + // Do search for address in all modes. + // params.HasSearchMode(SearchParams::SEARCH_ADDRESS) + + if (viewportPoints) + m_pQuery->SearchViewportPoints(res); else - */ - { - // Do search for address in all modes. - // params.NeedSearch(SearchParams::SEARCH_ADDRESS) - if (viewportPoints) - m_pQuery->SearchViewportPoints(res); - else - m_pQuery->Search(res, RESULTS_COUNT); - } + m_pQuery->Search(res, RESULTS_COUNT); } catch (Query::CancelException const &) { @@ -350,10 +266,7 @@ void Engine::SearchAsync(bool viewportPoints) { try { - m_pQuery->SearchAdditional(res, - params.NeedSearch(SearchParams::AROUND_POSITION), - params.NeedSearch(SearchParams::IN_VIEWPORT), - RESULTS_COUNT); + m_pQuery->SearchAdditional(res, RESULTS_COUNT); } catch (Query::CancelException const &) { diff --git a/search/search_engine.hpp b/search/search_engine.hpp index 6242bd7e23..5a93ccdae2 100644 --- a/search/search_engine.hpp +++ b/search/search_engine.hpp @@ -1,7 +1,7 @@ #pragma once -#include "search/params.hpp" -#include "search/result.hpp" +#include "params.hpp" +#include "result.hpp" #include "geometry/rect2d.hpp" @@ -12,6 +12,7 @@ #include "std/unique_ptr.hpp" #include "std/string.hpp" #include "std/function.hpp" +#include "std/atomic.hpp" class Index; @@ -39,9 +40,8 @@ public: void SupportOldFormat(bool b); - void PrepareSearch(m2::RectD const & viewport, - bool hasPt, double lat, double lon); - bool Search(SearchParams const & params, m2::RectD const & viewport, bool viewportPoints = false); + void PrepareSearch(m2::RectD const & viewport); + bool Search(SearchParams const & params, m2::RectD const & viewport); void GetResults(Results & res); @@ -66,14 +66,14 @@ public: private: static const int RESULTS_COUNT = 30; - void SetViewportAsync(m2::RectD const & viewport, m2::RectD const & nearby); - void SearchAsync(bool viewportPoints); + void SetRankPivot(SearchParams const & params, m2::RectD const & viewport); + void SetViewportAsync(m2::RectD const & viewport); + void SearchAsync(); void EmitResults(SearchParams const & params, Results & res); - threads::Mutex m_searchMutex, m_updateMutex, m_readyMutex; - - volatile bool m_readyThread; + threads::Mutex m_searchMutex, m_updateMutex; + atomic_flag m_isReadyThread; SearchParams m_params; m2::RectD m_viewport; diff --git a/search/search_query.cpp b/search/search_query.cpp index e4abb0b496..dae4676488 100644 --- a/search/search_query.cpp +++ b/search/search_query.cpp @@ -1,10 +1,10 @@ -#include "search/search_query.hpp" -#include "search/feature_offset_match.hpp" -#include "search/latlon_match.hpp" -#include "search/search_common.hpp" -#include "search/indexed_value.hpp" -#include "search/geometry_utils.hpp" -#include "search/search_string_intersection.hpp" +#include "search_query.hpp" +#include "feature_offset_match.hpp" +#include "latlon_match.hpp" +#include "search_common.hpp" +#include "indexed_value.hpp" +#include "geometry_utils.hpp" +#include "search_string_intersection.hpp" #include "storage/country_info.hpp" @@ -40,16 +40,14 @@ namespace CompareFunctionT1 g_arrCompare1[] = { + &impl::PreResult1::LessDistance, &impl::PreResult1::LessRank, - &impl::PreResult1::LessViewportDistance, - &impl::PreResult1::LessDistance }; CompareFunctionT2 g_arrCompare2[] = { + &impl::PreResult2::LessDistance, &impl::PreResult2::LessRank, - &impl::PreResult2::LessViewportDistance, - &impl::PreResult2::LessDistance }; /// This indexes should match the initialization routine below. @@ -86,9 +84,7 @@ Query::Query(Index const * pIndex, #ifdef FIND_LOCALITY_TEST m_locality(pIndex), #endif - m_worldSearch(true), - m_sortByViewport(false), - m_position(empty_pos_value, empty_pos_value) + m_worldSearch(true) { // m_viewport is initialized as empty rects @@ -131,26 +127,14 @@ int8_t Query::GetLanguage(int id) const return m_keywordsScorer.GetLanguage(GetLangIndex(id)); } -namespace -{ - inline bool IsEqualMercator(m2::RectD const & r1, m2::RectD const & r2, double epsMeters) - { - double const eps = epsMeters * MercatorBounds::degreeInMetres; - return m2::IsEqual(r1, r2, eps, eps); - } -} - -void Query::SetViewport(m2::RectD viewport[], size_t count) +void Query::SetViewport(m2::RectD const & viewport) { - ASSERT(count < COUNT_V, (count)); - m_cancel = false; MWMVectorT mwmsInfo; m_pIndex->GetMwmsInfo(mwmsInfo); - for (size_t i = 0; i < count; ++i) - SetViewportByIndex(mwmsInfo, viewport[i], i); + SetViewportByIndex(mwmsInfo, viewport, CURRENT_V); } void Query::SetViewportByIndex(MWMVectorT const & mwmsInfo, m2::RectD const & viewport, size_t idx) @@ -180,22 +164,16 @@ void Query::SetViewportByIndex(MWMVectorT const & mwmsInfo, m2::RectD const & vi } } -void Query::SetPosition(m2::PointD const & pos) +void Query::SetRankPivot(m2::PointD const & pivot) { - if (!m2::AlmostEqualULPs(pos, m_position)) + if (!m2::AlmostEqualULPs(pivot, m_pivot)) { storage::CountryInfo ci; - m_pInfoGetter->GetRegionInfo(pos, ci); + m_pInfoGetter->GetRegionInfo(pivot, ci); m_region.swap(ci.m_name); } - m_position = pos; -} - -void Query::NullPosition() -{ - m_position = m2::PointD(empty_pos_value, empty_pos_value); - m_region.clear(); + m_pivot = pivot; } void Query::SetPreferredLocale(string const & locale) @@ -254,7 +232,7 @@ void Query::UpdateViewportOffsets(MWMVectorT const & mwmsInfo, m2::RectD const & { offsets.clear(); - int const viewScale = scales::GetScaleLevel(rect); + int const queryScale = GetQueryIndexScale(rect); covering::CoveringGetter cov(rect, covering::ViewportWithLowLevels); for (shared_ptr<MwmInfo> const & info : mwmsInfo) @@ -270,7 +248,7 @@ void Query::UpdateViewportOffsets(MWMVectorT const & mwmsInfo, m2::RectD const & if (header.GetType() == FHeaderT::country) { pair<int, int> const scaleR = header.GetScaleRange(); - int const scale = min(max(viewScale + SCALE_SEARCH_DEPTH, scaleR.first), scaleR.second); + int const scale = min(max(queryScale, scaleR.first), scaleR.second); covering::IntervalsT const & interval = cov.Get(header.GetLastScale()); @@ -320,13 +298,16 @@ void Query::Init(bool viewportPoints) if (viewportPoints) { + // Special case to change comparator in viewport search + // (more uniform results distribution on the map). + m_queuesCount = 1; m_results[0] = QueueT(PRE_RESULTS_COUNT, QueueCompareT(&impl::PreResult1::LessPointsForViewport)); } else { - m_results[0] = QueueT(PRE_RESULTS_COUNT, QueueCompareT(g_arrCompare1[0])); m_queuesCount = QUEUES_COUNT; + m_results[0] = QueueT(PRE_RESULTS_COUNT, QueueCompareT(g_arrCompare1[0])); } } @@ -524,7 +505,7 @@ namespace } }; - static size_t const SIZE = 3; + static size_t const SIZE = 2; CompT Get(size_t i) { return CompT(g_arrCompare2[i]); } }; @@ -607,7 +588,7 @@ namespace impl Query::ViewportID const viewportID = static_cast<Query::ViewportID>(res.GetViewportID()); impl::PreResult2 * res2 = new impl::PreResult2(feature, &res, - m_query.GetViewport(viewportID), m_query.GetPosition(viewportID), + m_query.GetPosition(viewportID), name, country); /// @todo: add exluding of states (without USA states), continents @@ -626,7 +607,7 @@ namespace impl { storage::CountryInfo ci; res2->m_region.GetRegion(m_query.m_pInfoGetter, ci); - if (ci.IsNotEmpty() && ci.m_name == m_query.GetPositionRegion()) + if (ci.IsNotEmpty() && ci.m_name == m_query.GetPivotRegion()) res2->m_rank *= 1.7; } break; @@ -647,11 +628,7 @@ namespace impl LoadFeature(id, feature, name, country); if (!name.empty() && !country.empty()) - { - return new impl::PreResult2(feature, 0, - m_query.GetViewport(), m_query.GetPosition(), - name, country); - } + return new impl::PreResult2(feature, 0, m_query.GetPosition(), name, country); else return 0; } @@ -661,25 +638,10 @@ namespace impl { Query const & m_query; - bool LessViewport(HouseResult const & r1, HouseResult const & r2) const - { - m2::RectD const & v = m_query.GetViewport(); - - uint8_t const d1 = ViewportDistance(v, r1.GetOrg()); - uint8_t const d2 = ViewportDistance(v, r2.GetOrg()); - - return (d1 != d2 ? d1 < d2 : LessDistance(r1, r2)); - } - bool LessDistance(HouseResult const & r1, HouseResult const & r2) const { - if (m_query.IsValidPosition()) - { - return (PointDistance(m_query.m_position, r1.GetOrg()) < - PointDistance(m_query.m_position, r2.GetOrg())); - } - else - return false; + return (PointDistance(m_query.m_pivot, r1.GetOrg()) < + PointDistance(m_query.m_pivot, r2.GetOrg())); } public: @@ -688,21 +650,17 @@ namespace impl struct CompT { HouseCompFactory const * m_parent; - size_t m_alg; - CompT(HouseCompFactory const * parent, size_t alg) : m_parent(parent), m_alg(alg) {} + CompT(HouseCompFactory const * parent) : m_parent(parent) {} bool operator() (HouseResult const & r1, HouseResult const & r2) const { - if (m_alg == 0) - return m_parent->LessViewport(r1, r2); - else - return m_parent->LessDistance(r1, r2); + return m_parent->LessDistance(r1, r2); } }; - static size_t const SIZE = 2; + static size_t const SIZE = 1; - CompT Get(size_t i) { return CompT(this, i); } + CompT Get(size_t) { return CompT(this); } }; } @@ -945,8 +903,8 @@ template <class T> void Query::ProcessSuggestions(vector<T> & vec, Results & res void Query::AddResultFromTrie(TrieValueT const & val, MwmSet::MwmId const & mwmID, ViewportID vID /*= DEFAULT_V*/) { - impl::PreResult1 res(FeatureID(mwmID, val.m_featureId), val.m_rank, val.m_pt, - GetPosition(vID), GetViewport(vID), vID); + impl::PreResult1 res(FeatureID(mwmID, val.m_featureId), val.m_rank, + val.m_pt, GetPosition(vID), vID); for (size_t i = 0; i < m_queuesCount; ++i) { @@ -1087,8 +1045,6 @@ public: FeatureLoader(Query & query, MwmSet::MwmId const & mwmID, Query::ViewportID viewportID) : m_query(query), m_mwmID(mwmID), m_count(0), m_viewportID(viewportID) { - if (query.m_sortByViewport) - m_viewportID = Query::CURRENT_V; } void operator()(Query::TrieValueT const & value) @@ -1562,12 +1518,13 @@ namespace impl string DebugPrint(Locality const & l) { - string res("Locality: "); - res += "Name: " + l.m_name; - res += "; Name English: " + l.m_enName; - res += "; Rank: " + ::DebugPrint(l.m_value.m_rank); - res += "; Matched: " + ::DebugPrint(l.m_matchedTokens.size()); - return res; + stringstream ss; + ss << "{ Locality: " << + "Name = " + l.m_name << + "; Name English = " << l.m_enName << + "; Rank = " << int(l.m_value.m_rank) << + "; Matched: " << l.m_matchedTokens.size() << " }"; + return ss.str(); } struct Region @@ -2177,14 +2134,8 @@ m2::RectD const & Query::GetViewport(ViewportID vID /*= DEFAULT_V*/) const return m_viewport[vID]; } - // return first valid actual viewport - if (m_viewport[0].IsValid()) - return m_viewport[0]; - else - { - ASSERT ( m_viewport[1].IsValid(), () ); - return m_viewport[1]; - } + ASSERT(m_viewport[CURRENT_V].IsValid(), ()); + return m_viewport[CURRENT_V]; } m2::PointD Query::GetPosition(ViewportID vID /*= DEFAULT_V*/) const @@ -2193,13 +2144,8 @@ m2::PointD Query::GetPosition(ViewportID vID /*= DEFAULT_V*/) const { case LOCALITY_V: // center of the founded locality return m_viewport[vID].Center(); - - case CURRENT_V: // center of viewport for special sort mode - if (m_sortByViewport) - return m_viewport[vID].Center(); - default: - return m_position; + return m_pivot; } } @@ -2256,29 +2202,15 @@ void Query::SearchAllInViewport(m2::RectD const & viewport, Results & res, unsig } } -bool Query::IsValidPosition() const -{ - return (m_position.x > empty_pos_value && m_position.y > empty_pos_value); -} - -void Query::SearchAdditional(Results & res, bool nearMe, bool inViewport, size_t resCount) +void Query::SearchAdditional(Results & res, size_t resCount) { ClearQueues(); - string name[2]; - - // search in mwm with position ... - if (nearMe && IsValidPosition()) - name[0] = m_pInfoGetter->GetRegionFile(m_position); - - // ... and in mwm with viewport - if (inViewport) - name[1] = m_pInfoGetter->GetRegionFile(GetViewport().Center()); - - LOG(LDEBUG, ("Additional MWM search: ", name[0], name[1])); - - if (!(name[0].empty() && name[1].empty())) + string const fileName = m_pInfoGetter->GetRegionFile(m_pivot); + if (!fileName.empty()) { + LOG(LDEBUG, ("Additional MWM search: ", fileName)); + MWMVectorT mwmsInfo; m_pIndex->GetMwmsInfo(mwmsInfo); @@ -2287,10 +2219,7 @@ void Query::SearchAdditional(Results & res, bool nearMe, bool inViewport, size_t for (shared_ptr<MwmInfo> const & info : mwmsInfo) { Index::MwmLock const mwmLock(const_cast<Index &>(*m_pIndex), MwmSet::MwmId(info)); - string fileName; - if (mwmLock.IsLocked()) - fileName = mwmLock.GetValue<MwmValue>()->GetFileName(); - if (fileName == name[0] || fileName == name[1]) + if (mwmLock.IsLocked() && mwmLock.GetValue<MwmValue>()->GetFileName() == fileName) SearchInMWM(mwmLock, params); } diff --git a/search/search_query.hpp b/search/search_query.hpp index 70caff5bc3..ec67cd05f6 100644 --- a/search/search_query.hpp +++ b/search/search_query.hpp @@ -1,10 +1,10 @@ #pragma once -#include "search/intermediate_result.hpp" -#include "search/keyword_lang_matcher.hpp" +#include "intermediate_result.hpp" +#include "keyword_lang_matcher.hpp" #include "indexer/ftypes_matcher.hpp" #include "indexer/search_trie.hpp" -#include "../indexer/index.hpp" // for Index::MwmLock +#include "indexer/index.hpp" // for Index::MwmLock #include "geometry/rect2d.hpp" @@ -52,9 +52,6 @@ namespace impl class Query { public: - static int const SCALE_SEARCH_DEPTH = 7; - static int const ADDRESS_SCALE = 10; - struct SuggestT { strings::UniString m_name; @@ -80,15 +77,11 @@ public: void Init(bool viewportPoints); - void SetViewport(m2::RectD viewport[], size_t count); - - static const int empty_pos_value = -1000; - void SetPosition(m2::PointD const & pos); - void NullPosition(); - inline string const & GetPositionRegion() const { return m_region; } + void SetViewport(m2::RectD const & viewport); + void SetRankPivot(m2::PointD const & pivot); + inline string const & GetPivotRegion() const { return m_region; } inline void SetSearchInWorld(bool b) { m_worldSearch = b; } - inline void SetSortByViewport(bool b) { m_sortByViewport = b; } /// Suggestions language code, not the same as we use in mwm data int8_t m_inputLocaleCode, m_currentLocaleCode; @@ -104,7 +97,7 @@ public: void SearchCoordinates(string const & query, Results & res) const; void Search(Results & res, size_t resCount); void SearchAllInViewport(m2::RectD const & viewport, Results & res, unsigned int resultsNeeded = 30); - void SearchAdditional(Results & res, bool nearMe, bool inViewport, size_t resCount); + void SearchAdditional(Results & res, size_t resCount); void SearchViewportPoints(Results & res); //@} @@ -171,12 +164,12 @@ private: OffsetsVectorT & offsets); void ClearCache(size_t ind); - enum ViewportID { + enum ViewportID + { DEFAULT_V = -1, CURRENT_V = 0, - POSITION_V = 1, - LOCALITY_V = 2, - COUNT_V = 3 // Should always be the last + LOCALITY_V = 1, + COUNT_V = 2 // Should always be the last }; void AddResultFromTrie(TrieValueT const & val, MwmSet::MwmId const & mwmID, @@ -244,7 +237,8 @@ private: static int const MAX_SUGGESTS_COUNT = 5; m2::RectD m_viewport[COUNT_V]; - bool m_worldSearch, m_sortByViewport; + m2::PointD m_pivot; + bool m_worldSearch; /// @name Get ranking params. //@{ @@ -254,9 +248,6 @@ private: m2::PointD GetPosition(ViewportID vID = DEFAULT_V) const; //@} - m2::PointD m_position; - bool IsValidPosition() const; - void SetLanguage(int id, int8_t lang); int8_t GetLanguage(int id) const; @@ -284,11 +275,10 @@ private: typedef my::limited_priority_queue<impl::PreResult1, QueueCompareT> QueueT; public: - enum { QUEUES_COUNT = 3 }; + enum { QUEUES_COUNT = 2 }; private: - // 0 - LessRank - // 1 - LessViewportDistance - // 2 - LessDistance + // 0 - LessDistance + // 1 - LessRank QueueT m_results[QUEUES_COUNT]; size_t m_queuesCount; }; |