[search] Fixed slooow locality matching.

Locality matching code haven't supported a lot of mwms, and iterated
over the whole mwms set on each search result (sic!).  Moreover, for
locality selection it directly read all features in the rect instead of
RankTable usage.

This CL significantly speeds up search results generation stage, when
there're a lot of maps and a lot of search results.

8 files changed, 139 insertions, 120 deletions

diff --git a/search/intermediate_result.cpp b/search/intermediate_result.cpp
index f460cce513..0a983e036c 100644
--- a/search/intermediate_result.cpp
+++ b/search/intermediate_result.cpp
@@ -193,12 +193,18 @@ Result PreResult2::GenerateFinalResult(storage::CountryInfoGetter const & infoGe
                                        set<uint32_t> const * pTypes, int8_t locale,
                                        ReverseGeocoder const * coder) const
 {
+  ReverseGeocoder::Address addr;
+  bool addrComputed = false;
+
   string name = m_str;
   if (coder && name.empty())
   {
     // Insert exact address (street and house number) instead of empty result name.
-    ReverseGeocoder::Address addr;
-    coder->GetNearbyAddress(GetCenter(), addr);
+    if (!addrComputed)
+    {
+      coder->GetNearbyAddress(GetCenter(), addr);
+      addrComputed = true;
+    }
     if (addr.GetDistance() == 0)
       name = FormatStreetAndHouse(addr);
   }
@@ -212,8 +218,11 @@ Result PreResult2::GenerateFinalResult(storage::CountryInfoGetter const & infoGe
     address = GetRegionName(infoGetter, type);
     if (ftypes::IsAddressObjectChecker::Instance()(m_types))
     {
-      ReverseGeocoder::Address addr;
-      coder->GetNearbyAddress(GetCenter(), addr);
+      if (!addrComputed)
+      {
+        coder->GetNearbyAddress(GetCenter(), addr);
+        addrComputed = true;
+      }
       address = FormatFullAddress(addr, address);
     }
   }
diff --git a/search/locality_finder.cpp b/search/locality_finder.cpp
index 4df74233d2..92bc5251a5 100644
--- a/search/locality_finder.cpp
+++ b/search/locality_finder.cpp
@@ -1,26 +1,41 @@
 #include "search/locality_finder.hpp"
 
+#include "search/dummy_rank_table.hpp"
 #include "search/mwm_context.hpp"
 
 #include "indexer/ftypes_matcher.hpp"
+#include "indexer/index.hpp"
 
+#include "base/assert.hpp"
+#include "base/stl_helpers.hpp"
+
+#include "std/algorithm.hpp"
 
 namespace search
 {
-
+namespace
+{
 double const kMaxCityRadiusMeters = 30000.0;
-double const kInflateRectMercator = 1.0E-3;
+double const kInflateRectMercator = 0.001;
 
 class DoLoader
 {
 public:
-  DoLoader(LocalityFinder const & finder, LocalityFinder::Cache & cache)
-    : m_finder(finder), m_cache(cache)
+  DoLoader(MwmContext const & ctx, LocalityFinder::Cache & cache, RankTable const & ranks,
+           int8_t lang)
+    : m_ctx(ctx), m_cache(cache), m_ranks(ranks), m_lang(lang)
   {
   }
 
-  void operator() (FeatureType & ft) const
+  void operator()(uint32_t id) const
   {
+    if (m_ranks.Get(id) == 0)
+      return;
+
+    FeatureType ft;
+    if (!m_ctx.GetFeature(id, ft))
+      return;
+
     if (ft.GetFeatureType() != feature::GEOM_POINT)
       return;
 
@@ -28,15 +43,12 @@ public:
     switch (IsLocalityChecker::Instance().GetType(ft))
     {
     case CITY:
-    case TOWN:
-      break;
+    case TOWN: break;
     default:  // cache only cities and towns at this moment
       return;
     }
 
-    uint32_t const id = ft.GetID().m_index;
-
-    if (m_cache.m_loaded.count(id) > 0)
+    if (m_cache.m_loadedIds.count(id) > 0)
       return;
 
     uint32_t const population = ftypes::GetPopulation(ft);
@@ -50,66 +62,69 @@ public:
 
     // read item
     string name;
-    if (!ft.GetName(m_finder.m_lang, name))
-      if (!ft.GetName(0, name))
-        return;
+    if (!ft.GetName(m_lang, name) && !ft.GetName(0, name))
+      return;
 
-    LocalityItem item(population, id, name);
+    LocalityItem item(name, population, id);
     m_cache.m_tree.Add(item, rect);
-    m_cache.m_loaded.insert(id);
+    m_cache.m_loadedIds.insert(id);
   }
 
 private:
-  LocalityFinder const & m_finder;
+  MwmContext const & m_ctx;
   LocalityFinder::Cache & m_cache;
+  RankTable const & m_ranks;
+  int8_t const m_lang;
 };
 
-
 class DoSelectLocality
 {
 public:
-  DoSelectLocality(string & name, m2::PointD const & p)
-    : m_name(name) , m_point(p), m_bestValue(numeric_limits<double>::max())
+  DoSelectLocality(string & name, m2::PointD const & pt)
+    : m_name(name), m_pt(pt), m_bestScore(numeric_limits<double>::max())
   {
   }
 
-  void operator() (m2::RectD const & rect, LocalityItem const & item)
+  void operator()(m2::RectD const & rect, LocalityItem const & item)
   {
-    double const d = MercatorBounds::DistanceOnEarth(rect.Center(), m_point);
-    double const value = ftypes::GetPopulationByRadius(d) / static_cast<double>(item.m_population);
-    if (value < m_bestValue)
+    // TODO (@y, @m): replace this naive score by p-values on
+    // multivariate Gaussian.
+    double const distanceMeters = MercatorBounds::DistanceOnEarth(rect.Center(), m_pt);
+    double const score =
+        ftypes::GetPopulationByRadius(distanceMeters) / static_cast<double>(item.m_population);
+    if (score < m_bestScore)
     {
-      m_bestValue = value;
+      m_bestScore = score;
       m_name = item.m_name;
     }
   }
 
 private:
   string & m_name;
-  m2::PointD m_point;
-  double m_bestValue;
+  m2::PointD m_pt;
+  double m_bestScore;
 };
+}  // namespace
 
-
-LocalityItem::LocalityItem(uint32_t population, ID id, string const & name)
+// LocalityItem ------------------------------------------------------------------------------------
+LocalityItem::LocalityItem(string const & name, uint32_t population, uint32_t id)
   : m_name(name), m_population(population), m_id(id)
 {
 }
 
-string DebugPrint(LocalityItem const & item)
-{
-  stringstream ss;
-  ss << "Name = " << item.m_name << "Population = " << item.m_population << "ID = " << item.m_id;
-  return ss.str();
-}
-
+// LocalityFinder ----------------------------------------------------------------------------------
+LocalityFinder::LocalityFinder(Index const & index) : m_index(index), m_lang(0) {}
 
-LocalityFinder::LocalityFinder(Index const * pIndex)
-  : m_pIndex(pIndex), m_lang(0)
+void LocalityFinder::SetLanguage(int8_t lang)
 {
+  if (m_lang == lang)
+    return;
+
+  ClearCache();
+  m_lang = lang;
 }
 
-void LocalityFinder::UpdateCache(Cache & cache, m2::PointD const & pt) const
+void LocalityFinder::UpdateCache(Cache & cache, m2::PointD const & pt)
 {
   m2::RectD rect = MercatorBounds::RectByCenterXYAndSizeInMeters(pt, kMaxCityRadiusMeters);
   if (cache.m_rect.IsRectInside(rect))
@@ -118,19 +133,39 @@ void LocalityFinder::UpdateCache(Cache & cache, m2::PointD const & pt) const
   rect.Add(cache.m_rect);
   rect.Inflate(kInflateRectMercator, kInflateRectMercator);
 
-  vector<shared_ptr<MwmInfo>> mwmsInfo;
-  m_pIndex->GetMwmsInfo(mwmsInfo);
-  for (auto const & info : mwmsInfo)
+  if (!m_worldId.IsAlive())
   {
-    Index::MwmHandle handle = m_pIndex->GetMwmHandleById(info);
-    MwmValue const * value = handle.GetValue<MwmValue>();
-    if (handle.IsAlive() && value->GetHeader().GetType() == feature::DataHeader::world)
+    m_worldId.Reset();
+    m_ranks.reset();
+
+    vector<shared_ptr<MwmInfo>> mwmsInfo;
+    m_index.GetMwmsInfo(mwmsInfo);
+    for (auto const & info : mwmsInfo)
     {
-      cache.m_rect = rect;
-      MwmContext(move(handle)).ForEachFeature(rect, DoLoader(*this, cache));
-      break;
+      MwmSet::MwmId id(info);
+      Index::MwmHandle handle = m_index.GetMwmHandleById(id);
+      MwmValue const * value = handle.GetValue<MwmValue>();
+      if (handle.IsAlive() && value->GetHeader().GetType() == feature::DataHeader::world)
+      {
+        m_worldId = id;
+        m_ranks = RankTable::Load(value->m_cont);
+        break;
+      }
     }
+
+    if (!m_ranks)
+      m_ranks = make_unique<DummyRankTable>();
   }
+
+  ASSERT(m_ranks.get(), ());
+
+  Index::MwmHandle handle = m_index.GetMwmHandleById(m_worldId);
+  if (!handle.IsAlive())
+    return;
+
+  cache.m_rect = rect;
+  MwmContext ctx(move(handle));
+  ctx.ForEachIndex(rect, DoLoader(ctx, cache, *m_ranks, m_lang));
 }
 
 void LocalityFinder::GetLocality(m2::PointD const & pt, string & name)
@@ -150,17 +185,8 @@ void LocalityFinder::GetLocality(m2::PointD const & pt, string & name)
   if (working == nullptr)
   {
     // Find most unused cache.
-    size_t minUsage = numeric_limits<size_t>::max();
-    for (auto & cache : m_caches)
-    {
-      if (cache.m_usage < minUsage)
-      {
-        working = &cache;
-        minUsage = cache.m_usage;
-      }
-    }
-
-    ASSERT(working, ());
+    working =
+        &*min_element(begin(m_caches), end(m_caches), my::LessBy(&LocalityFinder::Cache::m_usage));
     working->Clear();
   }
 
@@ -174,11 +200,12 @@ void LocalityFinder::ClearCache()
     cache.Clear();
 }
 
+// LocalityFinder::Cache ---------------------------------------------------------------------------
 void LocalityFinder::Cache::Clear()
 {
   m_usage = 0;
   m_tree.Clear();
-  m_loaded.clear();
+  m_loadedIds.clear();
   m_rect.MakeEmpty();
 }
 
@@ -188,4 +215,10 @@ void LocalityFinder::Cache::GetLocality(m2::PointD const & pt, string & name)
   m_tree.ForEachInRectEx(m2::RectD(pt, pt), DoSelectLocality(name, pt));
 }
 
+string DebugPrint(LocalityItem const & item)
+{
+  stringstream ss;
+  ss << "Name = " << item.m_name << "Population = " << item.m_population << "ID = " << item.m_id;
+  return ss.str();
 }
+}  // namespace search
diff --git a/search/locality_finder.hpp b/search/locality_finder.hpp
index 0b3cae1af7..bef8c5b5be 100644
--- a/search/locality_finder.hpp
+++ b/search/locality_finder.hpp
@@ -1,73 +1,58 @@
 #pragma once
 
-#include "indexer/index.hpp"
+#include "indexer/mwm_set.hpp"
+#include "indexer/rank_table.hpp"
 
 #include "geometry/point2d.hpp"
 #include "geometry/rect2d.hpp"
 #include "geometry/tree4d.hpp"
 
 #include "std/set.hpp"
-
+#include "std/unique_ptr.hpp"
 
 class Index;
 
 namespace search
 {
-
 struct LocalityItem
 {
+  LocalityItem(string const & name, uint32_t population, uint32_t id);
+
   string m_name;
   uint32_t m_population;
-
-  typedef uint32_t ID;
-  ID m_id;
-
-  LocalityItem(uint32_t population, ID id, string const & name);
-
-  friend string DebugPrint(LocalityItem const & item);
+  uint32_t m_id;
 };
 
 class LocalityFinder
 {
+public:
   struct Cache
   {
-    m4::Tree<LocalityItem> m_tree;
-    set<LocalityItem::ID> m_loaded;
-    size_t m_usage;
-    m2::RectD m_rect;
-
-    Cache() : m_usage(0) {}
-
     void Clear();
     void GetLocality(m2::PointD const & pt, string & name);
-  };
 
-public:
-  LocalityFinder(Index const * pIndex);
+    m4::Tree<LocalityItem> m_tree;
+    set<uint32_t> m_loadedIds;
+    size_t m_usage = 0;
+    m2::RectD m_rect;
+  };
 
-  void SetLanguage(int8_t lang)
-  {
-    if (m_lang != lang)
-    {
-      ClearCache();
-      m_lang = lang;
-    }
-  }
+  LocalityFinder(Index const & index);
 
+  void SetLanguage(int8_t lang);
   void GetLocality(m2::PointD const & pt, string & name);
   void ClearCache();
 
-protected:
-  void UpdateCache(Cache & cache, m2::PointD const & pt) const;
-
 private:
-  friend class DoLoader;
+  void UpdateCache(Cache & cache, m2::PointD const & pt);
 
-  Index const * m_pIndex;
+  Index const & m_index;
+  MwmSet::MwmId m_worldId;
+  unique_ptr<RankTable> m_ranks;
 
   Cache m_caches[10];
-
   int8_t m_lang;
 };
 
-} // namespace search
+string DebugPrint(LocalityItem const & item);
+}  // namespace search
diff --git a/search/mwm_context.hpp b/search/mwm_context.hpp
index ca9b50b524..6038c9188c 100644
--- a/search/mwm_context.hpp
+++ b/search/mwm_context.hpp
@@ -36,7 +36,7 @@ public:
   inline string const & GetName() const { return GetInfo()->GetCountryName(); }
   inline shared_ptr<MwmInfo> const & GetInfo() const { return GetId().GetInfo(); }
 
-  template <class TFn>
+  template <typename TFn>
   void ForEachIndex(covering::IntervalsT const & intervals, uint32_t scale, TFn && fn) const
   {
     ForEachIndexImpl(intervals, scale, [&](uint32_t index)
@@ -48,7 +48,16 @@ public:
                      });
   }
 
-  template <class TFn>
+  template <typename TFn>
+  void ForEachIndex(m2::RectD const & rect, TFn && fn) const
+  {
+    uint32_t const scale = m_value.GetHeader().GetLastScale();
+    covering::IntervalsT intervals;
+    CoverRect(rect, scale, intervals);
+    ForEachIndex(intervals, scale, forward<TFn>(fn));
+  }
+
+  template <typename TFn>
   void ForEachFeature(m2::RectD const & rect, TFn && fn) const
   {
     uint32_t const scale = m_value.GetHeader().GetLastScale();
diff --git a/search/processor.cpp b/search/processor.cpp
index 930cfbe1a0..b3cc1e97f0 100644
--- a/search/processor.cpp
+++ b/search/processor.cpp
@@ -188,9 +188,7 @@ void Processor::SetPreferredLocale(string const & locale)
   // Default initialization.
   // If you want to reset input language, call SetInputLocale before search.
   SetInputLocale(locale);
-#ifdef FIND_LOCALITY_TEST
   m_ranker.SetLocalityFinderLanguage(code);
-#endif  // FIND_LOCALITY_TEST
 }
 
 void Processor::SetInputLocale(string const & locale)
diff --git a/search/ranker.cpp b/search/ranker.cpp
index c833532b88..1b12aecb38 100644
--- a/search/ranker.cpp
+++ b/search/ranker.cpp
@@ -276,9 +276,7 @@ Ranker::Ranker(Index const & index, storage::CountryInfoGetter const & infoGette
                my::Cancellable const & cancellable)
   : m_reverseGeocoder(index)
   , m_cancellable(cancellable)
-#ifdef FIND_LOCALITY_TEST
-  , m_locality(&index)
-#endif  // FIND_LOCALITY_TEST
+  , m_locality(index)
   , m_index(index)
   , m_infoGetter(infoGetter)
   , m_categories(categories)
@@ -332,14 +330,12 @@ Result Ranker::MakeResult(PreResult2 const & r) const
   Result res = r.GenerateFinalResult(m_infoGetter, &m_categories, &m_params.m_preferredTypes,
                                      m_params.m_currentLocaleCode, &m_reverseGeocoder);
   MakeResultHighlight(res);
-#ifdef FIND_LOCALITY_TEST
   if (ftypes::IsLocalityChecker::Instance().GetType(r.GetTypes()) == ftypes::NONE)
   {
     string city;
     m_locality.GetLocality(res.GetFeatureCenter(), city);
     res.AppendCity(city);
   }
-#endif  // FIND_LOCALITY_TEST
 
   res.SetRankingInfo(r.GetRankingInfo());
   return res;
@@ -533,8 +529,6 @@ void Ranker::FlushViewportResults(Geocoder::Params const & geocoderParams)
 
 void Ranker::ClearCaches()
 {
-#ifdef FIND_LOCALITY_TEST
   m_locality.ClearCache();
-#endif  // FIND_LOCALITY_TEST
 }
 }  // namespace search
diff --git a/search/ranker.hpp b/search/ranker.hpp
index 7eedba902c..f753c8e984 100644
--- a/search/ranker.hpp
+++ b/search/ranker.hpp
@@ -4,6 +4,7 @@
 #include "search/geocoder.hpp"
 #include "search/intermediate_result.hpp"
 #include "search/keyword_lang_matcher.hpp"
+#include "search/locality_finder.hpp"
 #include "search/mode.hpp"
 #include "search/params.hpp"
 #include "search/result.hpp"
@@ -23,12 +24,6 @@
 #include "std/utility.hpp"
 #include "std/vector.hpp"
 
-#define FIND_LOCALITY_TEST
-
-#ifdef FIND_LOCALITY_TEST
-#include "search/locality_finder.hpp"
-#endif  // FIND_LOCALITY_TEST
-
 class CategoriesHolder;
 class Index;
 
@@ -102,9 +97,7 @@ public:
   void SetPreResults1(vector<PreResult1> && preResults1) { m_preResults1 = move(preResults1); }
   void ClearCaches();
 
-#ifdef FIND_LOCALITY_TEST
   inline void SetLocalityFinderLanguage(int8_t code) { m_locality.SetLanguage(code); }
-#endif  // FIND_LOCALITY_TEST
 
   inline void SetLanguage(pair<int, int> const & ind, int8_t lang)
   {
@@ -137,9 +130,7 @@ private:
   my::Cancellable const & m_cancellable;
   KeywordLangMatcher m_keywordsScorer;
 
-#ifdef FIND_LOCALITY_TEST
   mutable LocalityFinder m_locality;
-#endif  // FIND_LOCALITY_TEST
 
   Index const & m_index;
   storage::CountryInfoGetter const & m_infoGetter;
diff --git a/search/search_tests/locality_finder_test.cpp b/search/search_tests/locality_finder_test.cpp
index ba1f6e621a..3a615fe2c4 100644
--- a/search/search_tests/locality_finder_test.cpp
+++ b/search/search_tests/locality_finder_test.cpp
@@ -23,7 +23,7 @@ class LocalityFinderTest
   m2::RectD m_worldRect;
 
 public:
-  LocalityFinderTest() : m_finder(&m_index)
+  LocalityFinderTest() : m_finder(m_index)
   {
     classificator::Load();
     m_worldFile = platform::LocalCountryFile::MakeForTesting("World");