From 1a3d0d9c797148669fd9f7085953de44d0074d1a Mon Sep 17 00:00:00 2001 From: tatiana-yan Date: Fri, 26 Oct 2018 17:42:58 +0300 Subject: [indexer] Do not stop ForClosestToPoint at the middle of the central cell processing. --- indexer/indexer_tests/locality_index_test.cpp | 51 +++++++++++++++++++-------- indexer/locality_index.hpp | 48 +++++++++++++++++++------ 2 files changed, 75 insertions(+), 24 deletions(-) (limited to 'indexer') 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 localityIndex; MemWriter> writer(localityIndex); @@ -137,18 +143,35 @@ UNIT_TEST(LocalityIndexTopSizeTest) MemReader reader(localityIndex.data(), localityIndex.size()); indexer::GeoObjectsIndex 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(scales::GetUpperScale()); std::set 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(scales::GetUpperScale()); + auto bestCell = m2::CellId::FromInt64(intervals.begin()->first, cellDepth); + std::set 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; + } } } -- cgit v1.2.3