[search] Fixed viewport filter.

Viewport filter is fuzzy now as it allows a limited number of features
outside the viewport.

6 files changed, 105 insertions, 57 deletions

diff --git a/search/v2/cbv_ptr.cpp b/search/v2/cbv_ptr.cpp
index 6343ac663f..98e97241c9 100644
--- a/search/v2/cbv_ptr.cpp
+++ b/search/v2/cbv_ptr.cpp
@@ -29,6 +29,11 @@ void CBVPtr::Set(coding::CompressedBitVector const * p, bool isOwner/* = false*/
   m_isOwner = p && isOwner;
 }
 
+void CBVPtr::Set(unique_ptr<coding::CompressedBitVector> p)
+{
+  Set(p.release(), true /* isOwner */);
+}
+
 void CBVPtr::Union(coding::CompressedBitVector const * p)
 {
   if (!p || m_isFull)
diff --git a/search/v2/cbv_ptr.hpp b/search/v2/cbv_ptr.hpp
index 910ef22332..1d5a1f870c 100644
--- a/search/v2/cbv_ptr.hpp
+++ b/search/v2/cbv_ptr.hpp
@@ -35,10 +35,12 @@ public:
   }
 
   void Set(coding::CompressedBitVector const * p, bool isOwner = false);
+  void Set(unique_ptr<coding::CompressedBitVector> p);
 
   inline coding::CompressedBitVector const * Get() const { return m_ptr; }
 
   coding::CompressedBitVector const & operator*() const { return *m_ptr; }
+  coding::CompressedBitVector const * operator->() const { return m_ptr; }
 
   bool IsEmpty() const;
 
diff --git a/search/v2/features_filter.cpp b/search/v2/features_filter.cpp
index 1772bd4c15..1e2bce62ae 100644
--- a/search/v2/features_filter.cpp
+++ b/search/v2/features_filter.cpp
@@ -2,14 +2,15 @@
 
 #include "coding/compressed_bit_vector.hpp"
 
+#include "std/algorithm.hpp"
+
 namespace search
 {
 namespace v2
 {
-FeaturesFilter::FeaturesFilter() : m_filter(nullptr), m_threshold(0) {}
-
+// FeaturesFilter ----------------------------------------------------------------------------------
 FeaturesFilter::FeaturesFilter(coding::CompressedBitVector const & filter, uint32_t threshold)
-  : m_filter(&filter), m_threshold(threshold)
+  : m_filter(filter), m_threshold(threshold)
 {
 }
 
@@ -18,13 +19,39 @@ bool FeaturesFilter::NeedToFilter(coding::CompressedBitVector const & cbv) const
   return cbv.PopCount() > m_threshold;
 }
 
-unique_ptr<coding::CompressedBitVector> FeaturesFilter::Filter(
+// LocalityFilter ----------------------------------------------------------------------------------
+LocalityFilter::LocalityFilter(coding::CompressedBitVector const & filter)
+  : FeaturesFilter(filter, 0 /* threshold */)
+{
+}
+
+unique_ptr<coding::CompressedBitVector> LocalityFilter::Filter(
     coding::CompressedBitVector const & cbv) const
 {
-  if (!m_filter)
-    return make_unique<coding::SparseCBV>();
-  return coding::CompressedBitVector::Intersect(*m_filter, cbv);
+  return coding::CompressedBitVector::Intersect(m_filter, cbv);
+}
+
+// ViewportFilter ----------------------------------------------------------------------------------
+ViewportFilter::ViewportFilter(coding::CompressedBitVector const & filter, uint32_t threshold)
+  : FeaturesFilter(filter, threshold)
+{
 }
 
+unique_ptr<coding::CompressedBitVector> ViewportFilter::Filter(
+    coding::CompressedBitVector const & cbv) const
+{
+  auto result = coding::CompressedBitVector::Intersect(m_filter, cbv);
+  if (!coding::CompressedBitVector::IsEmpty(result))
+    return result;
+
+  uint64_t limit = std::min(static_cast<uint64_t>(m_threshold), cbv.PopCount());
+  vector<uint64_t> positions;
+  for (uint64_t pos = 0; positions.size() != limit; ++pos)
+  {
+    if (cbv.GetBit(pos))
+      positions.push_back(pos);
+  }
+  return coding::CompressedBitVectorBuilder::FromBitPositions(move(positions));
+}
 }  // namespace v2
 }  // namespace search
diff --git a/search/v2/features_filter.hpp b/search/v2/features_filter.hpp
index d4caed9739..8ccb9b044e 100644
--- a/search/v2/features_filter.hpp
+++ b/search/v2/features_filter.hpp
@@ -13,26 +13,49 @@ namespace v2
 {
 // A lightweight filter of features.
 //
-// NOTE: this class *IS NOT* thread-safe.
+// NOTE: this class and it's subclasses *ARE* thread-safe.
 class FeaturesFilter
 {
 public:
-  FeaturesFilter();
-
   FeaturesFilter(coding::CompressedBitVector const & filter, uint32_t threshold);
 
-  inline void SetFilter(coding::CompressedBitVector const * filter) { m_filter = filter; }
-
-  inline void SetThreshold(uint32_t threshold) { m_threshold = threshold; }
+  virtual ~FeaturesFilter() = default;
 
   bool NeedToFilter(coding::CompressedBitVector const & features) const;
-  unique_ptr<coding::CompressedBitVector> Filter(coding::CompressedBitVector const & cbv) const;
 
-private:
-  // Non-owning ptr.
-  coding::CompressedBitVector const * m_filter;
-  uint32_t m_threshold;
+  virtual unique_ptr<coding::CompressedBitVector> Filter(
+      coding::CompressedBitVector const & cbv) const = 0;
+
+protected:
+  coding::CompressedBitVector const & m_filter;
+  uint32_t const m_threshold;
+};
+
+// Exact filter - leaves only features belonging to the set it had
+// been constructed from.
+class LocalityFilter : public FeaturesFilter
+{
+public:
+  LocalityFilter(coding::CompressedBitVector const & filter);
+
+  // FeaturesFilter overrides:
+  unique_ptr<coding::CompressedBitVector> Filter(
+      coding::CompressedBitVector const & cbv) const override;
 };
 
+// Fuzzy filter - tries to leave only features belonging to the set it
+// had been constructed from, but if the result is empty, leaves at
+// most first |threshold| features. This property is quite useful when
+// there are no matching features in viewport but it's ok to process a
+// limited number of features outside the viewport.
+class ViewportFilter : public FeaturesFilter
+{
+public:
+  ViewportFilter(coding::CompressedBitVector const & filter, uint32_t threshold);
+
+  // FeaturesFilter overrides:
+  unique_ptr<coding::CompressedBitVector> Filter(
+      coding::CompressedBitVector const & cbv) const override;
+};
 }  // namespace v2
 }  // namespace search
diff --git a/search/v2/geocoder.cpp b/search/v2/geocoder.cpp
index c5a2c35c3b..f8fb2048a3 100644
--- a/search/v2/geocoder.cpp
+++ b/search/v2/geocoder.cpp
@@ -5,6 +5,7 @@
 #include "search/search_delimiters.hpp"
 #include "search/search_string_utils.hpp"
 #include "search/v2/cbv_ptr.hpp"
+#include "search/v2/features_filter.hpp"
 #include "search/v2/features_layer_matcher.hpp"
 #include "search/v2/locality_scorer.hpp"
 
@@ -370,6 +371,7 @@ Geocoder::Geocoder(Index & index, storage::CountryInfoGetter const & infoGetter)
   , m_model(SearchModel::Instance())
   , m_streets(nullptr)
   , m_villages(nullptr)
+  , m_filter(nullptr)
   , m_matcher(nullptr)
   , m_finder(static_cast<my::Cancellable const &>(*this))
   , m_lastMatchedRegion(nullptr)
@@ -921,8 +923,8 @@ void Geocoder::MatchCities()
       if (coding::CompressedBitVector::IsEmpty(cityFeatures))
         continue;
 
-      // Filter will be applied for all non-empty bit vectors.
-      LimitedSearch(cityFeatures, 0 /* filterThreshold */);
+      LocalityFilter filter(*cityFeatures);
+      LimitedSearch(filter);
     }
   }
 }
@@ -944,16 +946,17 @@ void Geocoder::MatchViewportAndPosition()
     allFeatures.Union(RetrieveGeometryFeatures(*m_context, rect, POSITION_ID));
   }
 
-  // Filter will be applied only for large bit vectors.
-  LimitedSearch(allFeatures.Get(), m_params.m_maxNumResults /* filterThreshold */);
+  if (!allFeatures.Get())
+    return;
+
+  ViewportFilter filter(*allFeatures, m_params.m_maxNumResults /* threshold */);
+  LimitedSearch(filter);
 }
 
-void Geocoder::LimitedSearch(coding::CompressedBitVector const * filter, size_t filterThreshold)
+void Geocoder::LimitedSearch(FeaturesFilter const & filter)
 {
-  m_filter.SetFilter(filter);
-  MY_SCOPE_GUARD(resetFilter, [&]() { m_filter.SetFilter(nullptr); });
-
-  m_filter.SetThreshold(filterThreshold);
+  m_filter = &filter;
+  MY_SCOPE_GUARD(resetFilter, [&]() { m_filter = nullptr; });
 
   // The order is rather important. Match streets first, then all other stuff.
   GreedilyMatchStreets();
@@ -1021,8 +1024,8 @@ void Geocoder::CreateStreetsLayerAndMatchLowerLayers(
     return;
 
   CBVPtr filtered(features.get(), false /* isOwner */);
-  if (m_filter.NeedToFilter(*features))
-    filtered.Set(m_filter.Filter(*features).release(), true /* isOwner */);
+  if (m_filter->NeedToFilter(*features))
+    filtered.Set(m_filter->Filter(*features).release(), true /* isOwner */);
 
   m_layers.emplace_back();
   MY_SCOPE_GUARD(cleanupGuard, bind(&vector<FeaturesLayer>::pop_back, &m_layers));
@@ -1064,15 +1067,15 @@ void Geocoder::MatchPOIsAndBuildings(size_t curToken)
   // list of ids.
   vector<uint32_t> clusters[SearchModel::SEARCH_TYPE_STREET];
 
-  unique_ptr<coding::CompressedBitVector> intersection;
-  coding::CompressedBitVector * features = nullptr;
+  CBVPtr features;
+  features.SetFull();
 
   // Try to consume [curToken, m_numTokens) tokens range.
   for (size_t n = 1; curToken + n <= m_numTokens && !m_usedTokens[curToken + n - 1]; ++n)
   {
-    // At this point |intersection| is the intersection of
-    // m_addressFeatures[curToken], m_addressFeatures[curToken + 1], ...,
-    // m_addressFeatures[curToken + n - 2], iff n > 2.
+    // At this point |features| is the intersection of
+    // m_addressFeatures[curToken], m_addressFeatures[curToken + 1],
+    // ..., m_addressFeatures[curToken + n - 2].
 
     BailIfCancelled();
 
@@ -1085,26 +1088,14 @@ void Geocoder::MatchPOIsAndBuildings(size_t curToken)
                       layer.m_subQuery);
     }
 
-    if (n == 1)
-    {
-      features = m_addressFeatures[curToken].get();
-      if (m_filter.NeedToFilter(*features))
-      {
-        intersection = m_filter.Filter(*features);
-        features = intersection.get();
-      }
-    }
-    else
-    {
-      intersection =
-          coding::CompressedBitVector::Intersect(*features, *m_addressFeatures[curToken + n - 1]);
-      features = intersection.get();
-    }
-    ASSERT(features, ());
+    features.Intersect(m_addressFeatures[curToken + n - 1].get());
+    if (m_filter->NeedToFilter(*features))
+      features.Set(m_filter->Filter(*features));
+    ASSERT(features.Get(), ());
 
     bool const looksLikeHouseNumber = feature::IsHouseNumber(m_layers.back().m_subQuery);
 
-    if (coding::CompressedBitVector::IsEmpty(features) && !looksLikeHouseNumber)
+    if (coding::CompressedBitVector::IsEmpty(features.Get()) && !looksLikeHouseNumber)
       break;
 
     if (n == 1)
@@ -1247,8 +1238,8 @@ void Geocoder::MatchUnclassified(size_t curToken)
     allFeatures.Intersect(m_addressFeatures[curToken].get());
   }
 
-  if (m_filter.NeedToFilter(*allFeatures))
-    allFeatures.Set(m_filter.Filter(*allFeatures).release(), true /* isOwner */);
+  if (m_filter->NeedToFilter(*allFeatures))
+    allFeatures.Set(m_filter->Filter(*allFeatures).release(), true /* isOwner */);
 
   if (allFeatures.IsEmpty())
     return;
diff --git a/search/v2/geocoder.hpp b/search/v2/geocoder.hpp
index 8fe56628a4..1d1fd33c6f 100644
--- a/search/v2/geocoder.hpp
+++ b/search/v2/geocoder.hpp
@@ -2,7 +2,6 @@
 
 #include "search/cancel_exception.hpp"
 #include "search/search_query_params.hpp"
-#include "search/v2/features_filter.hpp"
 #include "search/v2/features_layer.hpp"
 #include "search/v2/features_layer_path_finder.hpp"
 #include "search/v2/mwm_context.hpp"
@@ -44,6 +43,7 @@ namespace search
 {
 namespace v2
 {
+class FeaturesFilter;
 class FeaturesLayerMatcher;
 class SearchModel;
 
@@ -188,9 +188,9 @@ private:
   void MatchViewportAndPosition();
 
   // Tries to do geocoding in a limited scope, assuming that knowledge
-  // about high-level features, like cities or countries, is
+  // about high-level features, like cities or countries, is somehow
   // incorporated into |filter|.
-  void LimitedSearch(coding::CompressedBitVector const * filter, size_t filterThreshold);
+  void LimitedSearch(FeaturesFilter const & filter);
 
   // Tries to match some adjacent tokens in the query as streets and
   // then performs geocoding in street vicinities.
@@ -303,7 +303,7 @@ private:
   vector<bool> m_usedTokens;
 
   // This filter is used to throw away excess features.
-  FeaturesFilter m_filter;
+  FeaturesFilter const * m_filter;
 
   // Features matcher for layers intersection.
   map<MwmSet::MwmId, unique_ptr<FeaturesLayerMatcher>> m_matchersCache;