[indexer] Do not stop ForClosestToPoint at the middle of the central cell processing.

2 files changed, 75 insertions, 24 deletions

diff --git a/indexer/indexer_tests/locality_index_test.cpp b/indexer/indexer_tests/locality_index_test.cpp
index fc115ba97f..811313a49d 100644
--- a/indexer/indexer_tests/locality_index_test.cpp
+++ b/indexer/indexer_tests/locality_index_test.cpp
@@ -125,11 +125,17 @@ UNIT_TEST(LocalityIndexRankTest)
 UNIT_TEST(LocalityIndexTopSizeTest)
 {
   LocalityObjectVector objects;
-  objects.m_objects.resize(4);
-  objects.m_objects[0].SetForTests(1, m2::PointD{1, 0});
-  objects.m_objects[1].SetForTests(2, m2::PointD{1, 0});
-  objects.m_objects[2].SetForTests(3, m2::PointD{1, 0});
-  objects.m_objects[3].SetForTests(4, m2::PointD{1, 0});
+  objects.m_objects.resize(7);
+  // Same cell.
+  objects.m_objects[0].SetForTests(1, m2::PointD{1.0, 0.0});
+  objects.m_objects[1].SetForTests(2, m2::PointD{1.0, 0.0});
+  objects.m_objects[2].SetForTests(3, m2::PointD{1.0, 0.0});
+  objects.m_objects[3].SetForTests(4, m2::PointD{1.0, 0.0});
+  // Another close cell.
+  objects.m_objects[4].SetForTests(5, m2::PointD{1.0, 1.0});
+  objects.m_objects[5].SetForTests(6, m2::PointD{1.0, 1.0});
+  // Far cell.
+  objects.m_objects[6].SetForTests(7, m2::PointD{10.0, 10.0});
 
   vector<char> localityIndex;
   MemWriter<vector<char>> writer(localityIndex);
@@ -137,18 +143,35 @@ UNIT_TEST(LocalityIndexTopSizeTest)
   MemReader reader(localityIndex.data(), localityIndex.size());
 
   indexer::GeoObjectsIndex<MemReader> index(reader);
-  TEST_EQUAL(GetRankedIds(index, m2::PointD{1, 0} /* center */, m2::PointD{0, 0} /* border */,
-                          4 /* topSize */)
+  TEST_EQUAL(GetRankedIds(index, m2::PointD{1.0, 0.0} /* center */,
+                          m2::PointD{10.0, 10.0} /* border */, 4 /* topSize */)
                  .size(),
              4, ());
-  TEST_EQUAL(GetRankedIds(index, m2::PointD{1, 0} /* center */, m2::PointD{0, 0} /* border */,
-                          3 /* topSize */)
+
+  // 4 objects are indexed at the central cell. Index does not guarantee the order but must
+  // return 4 objects.
+  TEST_EQUAL(GetRankedIds(index, m2::PointD{1.0, 0.0} /* center */,
+                          m2::PointD{10.0, 10.0} /* border */, 3 /* topSize */)
                  .size(),
-             3, ());
-  TEST_EQUAL(GetRankedIds(index, m2::PointD{4, 0} /* center */, m2::PointD{0, 0} /* border */,
-                          1 /* topSize */)
+             4, ());
+
+  // At the {1.0, 1.0} point there are also 2 objects, but it's not a central cell, index must
+  // return 5 (topSize) objects.
+  TEST_EQUAL(GetRankedIds(index, m2::PointD{1.0, 0.0} /* center */,
+                          m2::PointD{10.0, 10.0} /* border */, 5 /* topSize */)
                  .size(),
-             1, ());
-}
+             5, ());
+
+  // The same here. There are not too many objects in central cell. Index must return 5 (topSize)
+  // objects.
+  TEST_EQUAL(GetRankedIds(index, m2::PointD{4.0, 0.0} /* center */,
+                          m2::PointD{10.0, 10.0} /* border */, 5 /* topSize */)
+                 .size(),
+             5, ());
 
+  TEST_EQUAL(GetRankedIds(index, m2::PointD{4.0, 0.0} /* center */,
+                          m2::PointD{10.0, 10.0} /* border */, 7 /* topSize */)
+                 .size(),
+             7, ());
+}
 }  // namespace
diff --git a/indexer/locality_index.hpp b/indexer/locality_index.hpp
index ab9a3f1184..3066a527cf 100644
--- a/indexer/locality_index.hpp
+++ b/indexer/locality_index.hpp
@@ -52,27 +52,55 @@ public:
     }
   }
 
-  // Applies |processObject| to at most |topSize| object closest to |center| with maximal distance |sizeM|.
-  // Closest objects are first. Due to perfomance reasons far objects have approximate order.
-  void ForClosestToPoint(ProcessObject const & processObject, m2::PointD const & center, double sizeM,
-                         uint32_t topSize) const
+  // Applies |processObject| to the objects located within |radiusM| meters from |center|.
+  // Application to the closest objects and only to them is not guaranteed and the order
+  // of the objects is not specified.
+  // However, the method attempts to process objects that are closer to |center| first
+  // and stop after |sizeHint| objects have been processed. For stability, if an object from
+  // an index cell has been processed, all other objects from this cell will be processed too,
+  // thus probably overflowing the |sizeHint| limit.
+  void ForClosestToPoint(ProcessObject const & processObject, m2::PointD const & center,
+                         double radiusM, uint32_t sizeHint) const
   {
     auto const rect =
-        MercatorBounds::RectByCenterXYAndSizeInMeters(center, sizeM);
+        MercatorBounds::RectByCenterXYAndSizeInMeters(center, radiusM);
     covering::CoveringGetter cov(rect, covering::CoveringMode::Spiral);
     covering::Intervals const & intervals = cov.Get<DEPTH_LEVELS>(scales::GetUpperScale());
 
     std::set<uint64_t> objects;
-    auto process = [topSize, &objects, &processObject](uint64_t storedId) {
-      if (objects.insert(storedId).second && objects.size() <= topSize)
+    auto processAll = [&objects, &processObject](uint64_t storedId) {
+      if (objects.insert(storedId).second)
         processObject(LocalityObject::FromStoredId(storedId));
     };
 
+    auto process = [&](uint64_t storedId) {
+      if (objects.size() < sizeHint)
+        processAll(storedId);
+    };
+
+    CHECK_EQUAL(intervals.begin()->first, intervals.begin()->second - 1, ());
+    auto cellDepth = covering::GetCodingDepth<DEPTH_LEVELS>(scales::GetUpperScale());
+    auto bestCell = m2::CellId<DEPTH_LEVELS>::FromInt64(intervals.begin()->first, cellDepth);
+    std::set<int64_t> bestCells;
+    while (bestCell.Level() > 0)
+    {
+      bestCells.insert(bestCell.ToInt64(cellDepth));
+      bestCell = bestCell.Parent();
+      --cellDepth;
+    }
+
     for (auto const & i : intervals)
     {
-      if (objects.size() >= topSize)
-        return;
-      m_intervalIndex->ForEach(process, i.first, i.second);
+      if (bestCells.find(i.first) != bestCells.end())
+      {
+        m_intervalIndex->ForEach(processAll, i.first, i.second);
+      }
+      else
+      {
+        m_intervalIndex->ForEach(process, i.first, i.second);
+        if (objects.size() >= sizeHint)
+          return;
+      }
     }
   }