Welcome to mirror list, hosted at ThFree Co, Russian Federation.

github.com/mapsme/omim.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--base/internal/message.hpp6
-rw-r--r--map/framework.cpp10
-rw-r--r--search/nearby_points_sweeper.cpp33
-rw-r--r--search/nearby_points_sweeper.hpp124
-rw-r--r--search/pre_ranker.cpp195
-rw-r--r--search/pre_ranker.hpp19
-rw-r--r--search/pre_ranking_info.hpp5
-rw-r--r--search/processor.cpp11
-rw-r--r--search/processor.hpp5
-rw-r--r--search/search.pro2
-rw-r--r--search/search_integration_tests/pre_ranker_test.cpp19
-rw-r--r--search/search_params.cpp1
-rw-r--r--search/search_params.hpp4
-rw-r--r--search/search_tests/nearby_points_sweeper_test.cpp83
-rw-r--r--search/search_tests/search_tests.pro1
15 files changed, 469 insertions, 49 deletions
diff --git a/base/internal/message.hpp b/base/internal/message.hpp
index a378fdce11..ee6487b9cd 100644
--- a/base/internal/message.hpp
+++ b/base/internal/message.hpp
@@ -27,6 +27,7 @@ template <typename U, typename V> inline string DebugPrint(pair<U, V> const & p)
template <typename T> inline string DebugPrint(list<T> const & v);
template <typename T> inline string DebugPrint(vector<T> const & v);
template <typename T, typename C = less<T>> inline string DebugPrint(set<T, C> const & v);
+template <typename T, typename C = less<T>> inline string DebugPrint(multiset<T, C> const & v);
template <typename U, typename V, typename C = less<U>> inline string DebugPrint(map<U, V, C> const & v);
template <typename T> inline string DebugPrint(initializer_list<T> const & v);
template <typename T> inline string DebugPrint(unique_ptr<T> const & v);
@@ -109,6 +110,11 @@ template <typename T, typename C> inline string DebugPrint(set<T, C> const & v)
return ::my::impl::DebugPrintSequence(v.begin(), v.end());
}
+template <typename T, typename C> inline string DebugPrint(multiset<T, C> const & v)
+{
+ return ::my::impl::DebugPrintSequence(v.begin(), v.end());
+}
+
template <typename U, typename V, typename C> inline string DebugPrint(map<U, V, C> const & v)
{
return ::my::impl::DebugPrintSequence(v.begin(), v.end());
diff --git a/map/framework.cpp b/map/framework.cpp
index f56eb3ef39..e22f8843b6 100644
--- a/map/framework.cpp
+++ b/map/framework.cpp
@@ -2,6 +2,7 @@
#include "map/ge0_parser.hpp"
#include "map/geourl_process.hpp"
#include "map/gps_tracker.hpp"
+#include "map/user_mark.hpp"
#include "defines.hpp"
@@ -1349,6 +1350,15 @@ bool Framework::Search(search::SearchParams const & params)
// Cancels previous search request (if any) and initiates new search request.
CancelQuery(intent.m_handle);
+
+ {
+ m2::PointD const defaultMarkSize = GetSearchMarkSize(SearchMarkType::DefaultSearchMark);
+ m2::PointD const bookingMarkSize = GetSearchMarkSize(SearchMarkType::BookingSearchMark);
+ double const eps =
+ max(max(defaultMarkSize.x, defaultMarkSize.y), max(bookingMarkSize.x, bookingMarkSize.y));
+ intent.m_params.m_minDistanceOnMapBetweenResults = eps;
+ }
+
intent.m_handle = m_searchEngine->Search(intent.m_params, intent.m_viewport);
return true;
diff --git a/search/nearby_points_sweeper.cpp b/search/nearby_points_sweeper.cpp
new file mode 100644
index 0000000000..cc7b92712e
--- /dev/null
+++ b/search/nearby_points_sweeper.cpp
@@ -0,0 +1,33 @@
+#include "search/nearby_points_sweeper.hpp"
+
+namespace search
+{
+// NearbyPointsSweeper::Event ----------------------------------------------------------------------
+NearbyPointsSweeper::Event::Event(Type type, double y, double x, size_t index)
+ : m_type(type), m_y(y), m_x(x), m_index(index)
+{
+}
+
+bool NearbyPointsSweeper::Event::operator<(Event const & rhs) const
+{
+ if (m_y != rhs.m_y)
+ return m_y < rhs.m_y;
+
+ if (m_type != rhs.m_type)
+ return m_type < rhs.m_type;
+
+ if (m_x != rhs.m_x)
+ return m_x < rhs.m_x;
+
+ return m_index < rhs.m_index;
+}
+
+// NearbyPointsSweeper -----------------------------------------------------------------------------
+NearbyPointsSweeper::NearbyPointsSweeper(double eps) : m_eps(eps) {}
+
+void NearbyPointsSweeper::Add(double x, double y, size_t index)
+{
+ m_events.emplace_back(Event::TYPE_SEGMENT_START, y - m_eps * 0.5, x, index);
+ m_events.emplace_back(Event::TYPE_SEGMENT_END, y + m_eps * 0.5, x, index);
+}
+} // namespace search
diff --git a/search/nearby_points_sweeper.hpp b/search/nearby_points_sweeper.hpp
new file mode 100644
index 0000000000..9fbeef7228
--- /dev/null
+++ b/search/nearby_points_sweeper.hpp
@@ -0,0 +1,124 @@
+#pragma once
+
+#include "base/assert.hpp"
+
+#include "std/algorithm.hpp"
+#include "std/cstdint.hpp"
+#include "std/limits.hpp"
+#include "std/set.hpp"
+#include "std/utility.hpp"
+#include "std/vector.hpp"
+
+namespace search
+{
+// This class can be used to sweep points on a plane that are too
+// close to each other. Two points are considered to be "too close"
+// when Manhattan distance between them is less than or equal to some
+// preselected epsilon.
+class NearbyPointsSweeper
+{
+public:
+ explicit NearbyPointsSweeper(double eps);
+
+ // Adds a new point (|x|, |y|) on the plane. |index| is used to
+ // identify individual points, and will be reported for survived
+ // points during the Sweep phase.
+ void Add(double x, double y, size_t index);
+
+ // Emits indexes of all survived points. Complexity: O(n * log(n)),
+ // where n is the number of already added points.
+ template <typename TEmitter>
+ void Sweep(TEmitter && emitter)
+ {
+ sort(m_events.begin(), m_events.end());
+
+ set<pair<double, size_t>> line;
+
+ for (auto const & event : m_events)
+ {
+ switch (event.m_type)
+ {
+ case Event::TYPE_SEGMENT_START:
+ {
+ if (line.empty())
+ {
+ line.emplace(event.m_x, event.m_index);
+ break;
+ }
+
+ auto it = line.upper_bound(make_pair(event.m_x, numeric_limits<size_t>::max()));
+
+ bool add = true;
+ while (true)
+ {
+ if (line.empty())
+ break;
+
+ if (it == line.end())
+ {
+ --it;
+ continue;
+ }
+
+ double const x = it->first;
+ if (fabs(x - event.m_x) <= m_eps)
+ {
+ add = false;
+ break;
+ }
+
+ if (x + m_eps < event.m_x)
+ break;
+
+ if (it == line.begin())
+ break;
+
+ --it;
+ }
+
+ if (add)
+ line.emplace(event.m_x, event.m_index);
+
+ break;
+ }
+
+ case Event::TYPE_SEGMENT_END:
+ {
+ auto it = line.find(make_pair(event.m_x, event.m_index));
+ if (it != line.end())
+ {
+ emitter(event.m_index);
+ line.erase(it);
+ }
+ break;
+ }
+ };
+ }
+
+ ASSERT(line.empty(), ("Sweep line must be empty after events processing:", line));
+ }
+
+private:
+ struct Event
+ {
+ enum Type
+ {
+ TYPE_SEGMENT_START,
+ TYPE_SEGMENT_END
+ };
+
+ Event(Type type, double y, double x, size_t index);
+
+ bool operator<(Event const & rhs) const;
+
+ Type m_type;
+
+ double m_y;
+ double m_x;
+ size_t m_index;
+ };
+
+ vector<Event> m_events;
+ double const m_eps;
+};
+} // namespace search
diff --git a/search/pre_ranker.cpp b/search/pre_ranker.cpp
index d0d985bb9e..ed006f9eb3 100644
--- a/search/pre_ranker.cpp
+++ b/search/pre_ranker.cpp
@@ -2,16 +2,16 @@
#include "search/dummy_rank_table.hpp"
#include "search/lazy_centers_table.hpp"
+#include "search/nearby_points_sweeper.hpp"
#include "search/pre_ranking_info.hpp"
#include "indexer/mwm_set.hpp"
#include "indexer/rank_table.hpp"
+#include "indexer/scales.hpp"
#include "base/stl_helpers.hpp"
#include "std/iterator.hpp"
-#include "std/random.hpp"
-#include "std/set.hpp"
namespace search
{
@@ -45,6 +45,40 @@ struct ComparePreResult1
return linfo.m_startToken < rinfo.m_startToken;
}
};
+
+// Selects a fair random subset of size min(|n|, |k|) from [0, 1, 2, ..., n - 1].
+vector<size_t> RandomSample(size_t n, size_t k, minstd_rand & rng)
+{
+ vector<size_t> result(std::min(k, n));
+ iota(result.begin(), result.end(), 0);
+
+ for (size_t i = k; i < n; ++i)
+ {
+ size_t const j = rng() % (i + 1);
+ if (j < k)
+ result[j] = i;
+ }
+
+ return result;
+}
+
+void SweepNearbyResults(double eps, vector<PreResult1> & results)
+{
+ NearbyPointsSweeper sweeper(eps);
+ for (size_t i = 0; i < results.size(); ++i)
+ {
+ auto const & p = results[i].GetInfo().m_center;
+ sweeper.Add(p.x, p.y, i);
+ }
+
+ vector<PreResult1> filtered;
+ sweeper.Sweep([&filtered, &results](size_t i)
+ {
+ filtered.push_back(results[i]);
+ });
+
+ results.swap(filtered);
+}
} // namespace
PreRanker::PreRanker(Index const & index, Ranker & ranker, size_t limit)
@@ -57,6 +91,7 @@ void PreRanker::Init(Params const & params)
m_numSentResults = 0;
m_results.clear();
m_params = params;
+ m_currEmit.clear();
}
void PreRanker::FillMissingFieldsInPreResults()
@@ -98,6 +133,8 @@ void PreRanker::FillMissingFieldsInPreResults()
{
info.m_distanceToPivot =
MercatorBounds::DistanceOnEarth(m_params.m_accuratePivotCenter, center);
+ info.m_center = center;
+ info.m_centerLoaded = true;
}
else
{
@@ -116,40 +153,52 @@ void PreRanker::Filter(bool viewportSearch)
m_results.erase(unique(m_results.begin(), m_results.end(), my::EqualsBy(&PreResult1::GetId)),
m_results.end());
- sort(m_results.begin(), m_results.end(), &PreResult1::LessDistance);
-
if (m_results.size() > BatchSize())
{
- // Priority is some kind of distance from the viewport or
- // position, therefore if we have a bunch of results with the same
- // priority, we have no idea here which results are relevant. To
- // prevent bias from previous search routines (like sorting by
- // feature id) this code randomly selects tail of the
- // sorted-by-priority list of pre-results.
-
- double const last = m_results[BatchSize()].GetDistance();
-
- auto b = m_results.begin() + BatchSize();
- for (; b != m_results.begin() && b->GetDistance() == last; --b)
- ;
- if (b->GetDistance() != last)
- ++b;
-
- auto e = m_results.begin() + BatchSize();
- for (; e != m_results.end() && e->GetDistance() == last; ++e)
- ;
-
- // The main reason of shuffling here is to select a random subset
- // from the low-priority results. We're using a linear
- // congruential method with default seed because it is fast,
- // simple and doesn't need an external entropy source.
- //
- // TODO (@y, @m, @vng): consider to take some kind of hash from
- // features and then select a subset with smallest values of this
- // hash. In this case this subset of results will be persistent
- // to small changes in the original set.
- minstd_rand engine;
- shuffle(b, e, engine);
+ bool const centersLoaded =
+ all_of(m_results.begin(), m_results.end(),
+ [](PreResult1 const & result) { return result.GetInfo().m_centerLoaded; });
+ if (viewportSearch && centersLoaded)
+ {
+ FilterForViewportSearch();
+ ASSERT_LESS_OR_EQUAL(m_results.size(), BatchSize(), ());
+ for (auto const & result : m_results)
+ m_currEmit.insert(result.GetId());
+ }
+ else
+ {
+ sort(m_results.begin(), m_results.end(), &PreResult1::LessDistance);
+
+ // Priority is some kind of distance from the viewport or
+ // position, therefore if we have a bunch of results with the same
+ // priority, we have no idea here which results are relevant. To
+ // prevent bias from previous search routines (like sorting by
+ // feature id) this code randomly selects tail of the
+ // sorted-by-priority list of pre-results.
+
+ double const last = m_results[BatchSize()].GetDistance();
+
+ auto b = m_results.begin() + BatchSize();
+ for (; b != m_results.begin() && b->GetDistance() == last; --b)
+ ;
+ if (b->GetDistance() != last)
+ ++b;
+
+ auto e = m_results.begin() + BatchSize();
+ for (; e != m_results.end() && e->GetDistance() == last; ++e)
+ ;
+
+ // The main reason of shuffling here is to select a random subset
+ // from the low-priority results. We're using a linear
+ // congruential method with default seed because it is fast,
+ // simple and doesn't need an external entropy source.
+ //
+ // TODO (@y, @m, @vng): consider to take some kind of hash from
+ // features and then select a subset with smallest values of this
+ // hash. In this case this subset of results will be persistent
+ // to small changes in the original set.
+ shuffle(b, e, m_rng);
+ }
}
filtered.insert(m_results.begin(), m_results.begin() + min(m_results.size(), BatchSize()));
@@ -162,6 +211,7 @@ void PreRanker::Filter(bool viewportSearch)
m_results.reserve(filtered.size());
m_results.clear();
+
copy(filtered.begin(), filtered.end(), back_inserter(m_results));
}
@@ -173,7 +223,84 @@ void PreRanker::UpdateResults(bool lastUpdate)
m_ranker.SetPreResults1(move(m_results));
m_results.clear();
m_ranker.UpdateResults(lastUpdate);
+
+ if (lastUpdate)
+ m_currEmit.swap(m_prevEmit);
}
void PreRanker::ClearCaches() { m_pivotFeatures.Clear(); }
+
+void PreRanker::FilterForViewportSearch()
+{
+ auto const & viewport = m_params.m_viewport;
+
+ my::EraseIf(m_results, [&viewport](PreResult1 const & result) {
+ auto const & info = result.GetInfo();
+ return !viewport.IsPointInside(info.m_center);
+ });
+
+ SweepNearbyResults(m_params.m_minDistanceOnMapBetweenResults, m_results);
+
+ size_t const n = m_results.size();
+
+ if (n <= BatchSize())
+ return;
+
+ size_t const kNumXSlots = 5;
+ size_t const kNumYSlots = 5;
+ size_t const kNumBuckets = kNumXSlots * kNumYSlots;
+ vector<size_t> buckets[kNumBuckets];
+
+ double const sizeX = viewport.SizeX();
+ double const sizeY = viewport.SizeY();
+
+ for (size_t i = 0; i < m_results.size(); ++i)
+ {
+ auto const & p = m_results[i].GetInfo().m_center;
+ int dx = static_cast<int>((p.x - viewport.minX()) / sizeX * kNumXSlots);
+ dx = my::clamp(dx, 0, kNumXSlots - 1);
+
+ int dy = static_cast<int>((p.y - viewport.minY()) / sizeY * kNumYSlots);
+ dy = my::clamp(dy, 0, kNumYSlots - 1);
+
+ buckets[dx * kNumYSlots + dy].push_back(i);
+ }
+
+ vector<PreResult1> results;
+ double const density = static_cast<double>(BatchSize()) / static_cast<double>(n);
+ for (auto & bucket : buckets)
+ {
+ size_t const m = std::min(static_cast<size_t>(ceil(density * bucket.size())), bucket.size());
+
+ size_t const old =
+ partition(bucket.begin(), bucket.end(),
+ [this](size_t i) { return m_prevEmit.count(m_results[i].GetId()) != 0; }) -
+ bucket.begin();
+
+ if (m <= old)
+ {
+ for (size_t i : RandomSample(old, m, m_rng))
+ results.push_back(m_results[bucket[i]]);
+ }
+ else
+ {
+ for (size_t i = 0; i < old; ++i)
+ results.push_back(m_results[bucket[i]]);
+
+ for (size_t i : RandomSample(bucket.size() - old, m - old, m_rng))
+ results.push_back(m_results[bucket[old + i]]);
+ }
+ }
+
+ if (results.size() <= BatchSize())
+ {
+ m_results.swap(results);
+ }
+ else
+ {
+ m_results.clear();
+ for (size_t i : RandomSample(results.size(), BatchSize(), m_rng))
+ m_results.push_back(results[i]);
+ }
+}
} // namespace search
diff --git a/search/pre_ranker.hpp b/search/pre_ranker.hpp
index aa2622ef27..1e51574cf2 100644
--- a/search/pre_ranker.hpp
+++ b/search/pre_ranker.hpp
@@ -7,11 +7,14 @@
#include "indexer/index.hpp"
#include "geometry/point2d.hpp"
+#include "geometry/rect2d.hpp"
#include "base/macros.hpp"
#include "std/algorithm.hpp"
#include "std/cstdint.hpp"
+#include "std/random.hpp"
+#include "std/set.hpp"
#include "std/utility.hpp"
#include "std/vector.hpp"
@@ -23,6 +26,9 @@ class PreRanker
public:
struct Params
{
+ m2::RectD m_viewport;
+ double m_minDistanceOnMapBetweenResults = 0.0;
+
// This is different from geocoder's pivot because pivot is
// usually a rectangle created by radius and center and, due to
// precision loss, its center may differ from
@@ -74,6 +80,8 @@ public:
void ClearCaches();
private:
+ void FilterForViewportSearch();
+
Index const & m_index;
Ranker & m_ranker;
vector<PreResult1> m_results;
@@ -87,6 +95,17 @@ private:
// Cache of nested rects used to estimate distance from a feature to the pivot.
NestedRectsCache m_pivotFeatures;
+ // A set of ids for features that are emit during the current search session.
+ set<FeatureID> m_currEmit;
+
+ // A set of ids for features that were emit during the previous
+ // search session. They're used for filtering of current search in
+ // viewport results, because we need to give more priority to
+ // results that were on map previously.
+ set<FeatureID> m_prevEmit;
+
+ minstd_rand m_rng;
+
DISALLOW_COPY_AND_MOVE(PreRanker);
};
} // namespace search
diff --git a/search/pre_ranking_info.hpp b/search/pre_ranking_info.hpp
index 58b0e07041..43aada03ab 100644
--- a/search/pre_ranking_info.hpp
+++ b/search/pre_ranking_info.hpp
@@ -2,6 +2,8 @@
#include "search/model.hpp"
+#include "geometry/point2d.hpp"
+
#include "std/cstdint.hpp"
namespace search
@@ -14,6 +16,9 @@ struct PreRankingInfo
// units do not matter here.
double m_distanceToPivot = 0;
+ m2::PointD m_center = m2::PointD::Zero();
+ bool m_centerLoaded = false;
+
// Tokens [m_startToken, m_endToken) match to the feature name or
// house number.
size_t m_startToken = 0;
diff --git a/search/processor.cpp b/search/processor.cpp
index 0a7c40b146..4b016ab9c0 100644
--- a/search/processor.cpp
+++ b/search/processor.cpp
@@ -142,6 +142,7 @@ Processor::Processor(Index const & index, CategoriesHolder const & categories,
: m_categories(categories)
, m_infoGetter(infoGetter)
, m_position(0, 0)
+ , m_minDistanceOnMapBetweenResults(0.0)
, m_mode(Mode::Everywhere)
, m_suggestsEnabled(true)
, m_preRanker(index, m_ranker, kPreResultsCount)
@@ -393,6 +394,8 @@ void Processor::Search(SearchParams const & params, m2::RectD const & viewport)
else
SetPosition(viewport.Center());
+ SetMinDistanceOnMapBetweenResults(params.m_minDistanceOnMapBetweenResults);
+
SetMode(params.GetMode());
SetSuggestsEnabled(params.GetSuggestsEnabled());
SetInputLocale(params.m_inputLocale);
@@ -680,10 +683,18 @@ void Processor::InitGeocoder(Geocoder::Params & params)
void Processor::InitPreRanker(Geocoder::Params const & geocoderParams)
{
+ bool const viewportSearch = m_mode == Mode::Viewport;
+
PreRanker::Params params;
+ if (viewportSearch)
+ {
+ params.m_viewport = GetViewport();
+ params.m_minDistanceOnMapBetweenResults = m_minDistanceOnMapBetweenResults;
+ }
params.m_accuratePivotCenter = GetPivotPoint();
params.m_scale = geocoderParams.m_scale;
+
m_preRanker.Init(params);
}
diff --git a/search/processor.hpp b/search/processor.hpp
index d28c43c4ab..e71d5e1a55 100644
--- a/search/processor.hpp
+++ b/search/processor.hpp
@@ -84,6 +84,10 @@ public:
inline void SetMode(Mode mode) { m_mode = mode; }
inline void SetSuggestsEnabled(bool enabled) { m_suggestsEnabled = enabled; }
inline void SetPosition(m2::PointD const & position) { m_position = position; }
+ inline void SetMinDistanceOnMapBetweenResults(double distance)
+ {
+ m_minDistanceOnMapBetweenResults = distance;
+ }
inline void SetOnResults(SearchParams::TOnResults const & onResults) { m_onResults = onResults; }
inline string const & GetPivotRegion() const { return m_region; }
inline m2::PointD const & GetPosition() const { return m_position; }
@@ -150,6 +154,7 @@ protected:
m2::RectD m_viewport[COUNT_V];
m2::PointD m_pivot;
m2::PointD m_position;
+ double m_minDistanceOnMapBetweenResults;
Mode m_mode;
bool m_suggestsEnabled;
SearchParams::TOnResults m_onResults;
diff --git a/search/search.pro b/search/search.pro
index 6827455004..1eabe6ec22 100644
--- a/search/search.pro
+++ b/search/search.pro
@@ -43,6 +43,7 @@ HEADERS += \
mode.hpp \
model.hpp \
mwm_context.hpp \
+ nearby_points_sweeper.hpp \
nested_rects_cache.hpp \
pre_ranker.hpp \
pre_ranking_info.hpp \
@@ -102,6 +103,7 @@ SOURCES += \
mode.cpp \
model.cpp \
mwm_context.cpp \
+ nearby_points_sweeper.cpp \
nested_rects_cache.cpp \
pre_ranker.cpp \
pre_ranking_info.cpp \
diff --git a/search/search_integration_tests/pre_ranker_test.cpp b/search/search_integration_tests/pre_ranker_test.cpp
index 50eb2f5502..d97c79758f 100644
--- a/search/search_integration_tests/pre_ranker_test.cpp
+++ b/search/search_integration_tests/pre_ranker_test.cpp
@@ -39,17 +39,6 @@ namespace search
{
namespace
{
-// Returns the boundary such that at least |size| elements from
-// |distance| are less than or equal to the boundary.
-double GetBoundary(vector<double> const & distances, size_t size)
-{
- CHECK_LESS_OR_EQUAL(size, distances.size(), ());
- my::limited_priority_queue<double> queue(size);
- for (auto const & distance : distances)
- queue.push(distance);
- return queue.empty() ? 0.0 : queue.top();
-}
-
class TestRanker : public Ranker
{
public:
@@ -96,7 +85,9 @@ UNIT_CLASS_TEST(PreRankerTest, Smoke)
// number of results is larger than batch size, and that PreRanker
// emits results nearest to the pivot.
- m2::PointD const kPivot(0.5, 0.5);
+ m2::PointD const kPivot(0, 0);
+ m2::RectD const kViewport(m2::PointD(-5, -5), m2::PointD(5, 5));
+
size_t const kBatchSize = 50;
vector<TestPOI> pois;
@@ -122,6 +113,7 @@ UNIT_CLASS_TEST(PreRankerTest, Smoke)
PreRanker preRanker(m_engine, ranker, pois.size());
PreRanker::Params params;
+ params.m_viewport = kViewport;
params.m_accuratePivotCenter = kPivot;
params.m_scale = scales::GetUpperScale();
params.m_batchSize = kBatchSize;
@@ -152,8 +144,6 @@ UNIT_CLASS_TEST(PreRankerTest, Smoke)
TEST(ranker.Finished(), ());
TEST_EQUAL(results.size(), kBatchSize, ());
- double const boundary = GetBoundary(distances, kBatchSize);
-
vector<bool> checked(pois.size());
for (size_t i = 0; i < results.size(); ++i)
{
@@ -161,7 +151,6 @@ UNIT_CLASS_TEST(PreRankerTest, Smoke)
TEST_LESS(index, pois.size(), ());
TEST(!checked[index], (index));
- TEST_LESS_OR_EQUAL(results[i].GetDistance(), boundary, ());
TEST(my::AlmostEqualAbs(distances[index], results[i].GetDistance(), 1e-3),
(distances[index], results[i].GetDistance()));
checked[index] = true;
diff --git a/search/search_params.cpp b/search/search_params.cpp
index aa8d490dd9..fe9da94d89 100644
--- a/search/search_params.cpp
+++ b/search/search_params.cpp
@@ -9,6 +9,7 @@ namespace search
SearchParams::SearchParams()
: m_lat(0.0)
, m_lon(0.0)
+ , m_minDistanceOnMapBetweenResults(0.0)
, m_searchRadiusM(-1.0)
, m_mode(Mode::Everywhere)
, m_forceSearch(false)
diff --git a/search/search_params.hpp b/search/search_params.hpp
index d3de882ee9..235595998f 100644
--- a/search/search_params.hpp
+++ b/search/search_params.hpp
@@ -49,6 +49,10 @@ public:
double m_lat, m_lon;
+ // A minimum distance between search results in mercator, needed for
+ // pre-ranking of viewport search results.
+ double m_minDistanceOnMapBetweenResults;
+
friend string DebugPrint(SearchParams const & params);
private:
diff --git a/search/search_tests/nearby_points_sweeper_test.cpp b/search/search_tests/nearby_points_sweeper_test.cpp
new file mode 100644
index 0000000000..9cf99f8c3f
--- /dev/null
+++ b/search/search_tests/nearby_points_sweeper_test.cpp
@@ -0,0 +1,83 @@
+#include "testing/testing.hpp"
+
+#include "search/nearby_points_sweeper.hpp"
+
+#include "geometry/point2d.hpp"
+
+#include "base/stl_add.hpp"
+
+#include "std/set.hpp"
+#include "std/vector.hpp"
+
+namespace search
+{
+namespace
+{
+// Multiset is used here to catch situations when some index is reported more than once.
+using TIndexSet = multiset<size_t>;
+
+UNIT_TEST(NearbyPointsSweeper_Smoke)
+{
+ {
+ NearbyPointsSweeper sweeper(0.0);
+ for (size_t i = 0; i < 10; ++i)
+ sweeper.Add(10.0, 10.0, i);
+
+ TIndexSet expected = {0};
+
+ TIndexSet actual;
+ sweeper.Sweep(MakeInsertFunctor(actual));
+
+ TEST_EQUAL(expected, actual, ());
+ }
+
+ {
+ vector<double> const coords = {0.0, 0.5, 1.0, 1.5, 1.4, 1.6};
+
+ {
+ NearbyPointsSweeper sweeper(0.5);
+
+ for (size_t i = 0; i < coords.size(); ++i)
+ sweeper.Add(coords[i], 0.0, i);
+
+ TIndexSet expected = {0, 2, 5};
+
+ TIndexSet actual;
+ sweeper.Sweep(MakeInsertFunctor(actual));
+
+ TEST_EQUAL(expected, actual, ());
+ }
+
+ {
+ NearbyPointsSweeper sweeper(0.5);
+
+ for (size_t i = 0; i < coords.size(); ++i)
+ sweeper.Add(0.0, coords[i], i);
+
+ TIndexSet expected = {0, 2, 5};
+
+ TIndexSet actual;
+ sweeper.Sweep(MakeInsertFunctor(actual));
+
+ TEST_EQUAL(expected, actual, ());
+ }
+ }
+
+ {
+ vector<m2::PointD> const points = {m2::PointD(0.0, 0.0), m2::PointD(1.0, 1.0),
+ m2::PointD(1.5, 0.0), m2::PointD(1.5 + 1.01, 1.5 + 1.0)};
+ NearbyPointsSweeper sweeper(1.0);
+
+ for (size_t i = 0; i < points.size(); ++i)
+ sweeper.Add(points[i].x, points[i].y, i);
+
+ TIndexSet expected = {0, 2, 3};
+
+ TIndexSet actual;
+ sweeper.Sweep(MakeInsertFunctor(actual));
+
+ TEST_EQUAL(expected, actual, ());
+ }
+}
+} // namespace
+} // namespace search
diff --git a/search/search_tests/search_tests.pro b/search/search_tests/search_tests.pro
index 45dfe33dd6..b08d6416e4 100644
--- a/search/search_tests/search_tests.pro
+++ b/search/search_tests/search_tests.pro
@@ -27,6 +27,7 @@ SOURCES += \
latlon_match_test.cpp \
locality_finder_test.cpp \
locality_scorer_test.cpp \
+ nearby_points_sweeper_test.cpp \
query_saver_tests.cpp \
ranking_tests.cpp \
string_intersection_test.cpp \
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-29 14:21:05 +0300