diff options
Diffstat (limited to 'search/locality_finder.cpp')
| -rw-r--r-- | search/locality_finder.cpp | 246 |
1 files changed, 128 insertions, 118 deletions
diff --git a/search/locality_finder.cpp b/search/locality_finder.cpp index 92bc5251a5..5774b267a4 100644 --- a/search/locality_finder.cpp +++ b/search/locality_finder.cpp @@ -1,5 +1,7 @@ #include "search/locality_finder.hpp" +#include "search/categories_cache.hpp" +#include "search/cbv.hpp" #include "search/dummy_rank_table.hpp" #include "search/mwm_context.hpp" @@ -16,20 +18,55 @@ namespace search namespace { double const kMaxCityRadiusMeters = 30000.0; -double const kInflateRectMercator = 0.001; + +struct Filter +{ +public: + virtual ~Filter() = default; + virtual bool IsGood(uint32_t id) const = 0; +}; + +class CityFilter : public Filter +{ +public: + CityFilter(RankTable const & ranks) : m_ranks(ranks) {} + + // Filter overrides: + bool IsGood(uint32_t id) const override { return m_ranks.Get(id) != 0; } + +private: + RankTable const & m_ranks; +}; + +class VillageFilter : public Filter +{ +public: + VillageFilter(MwmContext const & ctx, VillagesCache & villages) : m_cbv(villages.Get(ctx)) {} + + // Filter overrides: + bool IsGood(uint32_t id) const override { return m_cbv.HasBit(id); } + +private: + CBV m_cbv; +}; class DoLoader { public: - 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) + DoLoader(MwmContext const & ctx, Filter const & filter, int8_t lang, + m4::Tree<LocalityFinder::Item> & localities, + map<MwmSet::MwmId, unordered_set<uint32_t>> & loadedIds) + : m_ctx(ctx), m_filter(filter), m_lang(lang), m_localities(localities), m_loadedIds(loadedIds) { } void operator()(uint32_t id) const { - if (m_ranks.Get(id) == 0) + auto const & mwmId = m_ctx.GetId(); + if (m_loadedIds[mwmId].count(id) != 0) + return; + + if (!m_filter.IsGood(id)) return; FeatureType ft; @@ -43,77 +80,53 @@ public: switch (IsLocalityChecker::Instance().GetType(ft)) { case CITY: - case TOWN: break; + case TOWN: + case VILLAGE: + break; default: // cache only cities and towns at this moment return; } - if (m_cache.m_loadedIds.count(id) > 0) - return; - uint32_t const population = ftypes::GetPopulation(ft); if (population == 0) return; + auto const center = ft.GetCenter(); double const radius = ftypes::GetRadiusByPopulation(population); - m2::RectD const rect = MercatorBounds::RectByCenterXYAndSizeInMeters(ft.GetCenter(), radius); - if (!rect.IsIntersect(m_cache.m_rect)) - return; + m2::RectD const rect = MercatorBounds::RectByCenterXYAndSizeInMeters(center, radius); // read item string name; if (!ft.GetName(m_lang, name) && !ft.GetName(0, name)) return; - LocalityItem item(name, population, id); - m_cache.m_tree.Add(item, rect); - m_cache.m_loadedIds.insert(id); + LocalityFinder::Item item(name, center, population); + m_localities.Add(item, rect); + m_loadedIds[mwmId].insert(id); } private: MwmContext const & m_ctx; - LocalityFinder::Cache & m_cache; - RankTable const & m_ranks; + Filter const & m_filter; int8_t const m_lang; -}; - -class DoSelectLocality -{ -public: - 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) - { - // 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_bestScore = score; - m_name = item.m_name; - } - } -private: - string & m_name; - m2::PointD m_pt; - double m_bestScore; + m4::Tree<LocalityFinder::Item> & m_localities; + map<MwmSet::MwmId, unordered_set<uint32_t>> & m_loadedIds; }; } // namespace -// LocalityItem ------------------------------------------------------------------------------------ -LocalityItem::LocalityItem(string const & name, uint32_t population, uint32_t id) - : m_name(name), m_population(population), m_id(id) +// LocalityFinder::Item +// ------------------------------------------------------------------------------------ +LocalityFinder::Item::Item(string const & name, m2::PointD const & center, uint32_t population) + : m_name(name), m_center(center), m_population(population) { } // LocalityFinder ---------------------------------------------------------------------------------- -LocalityFinder::LocalityFinder(Index const & index) : m_index(index), m_lang(0) {} +LocalityFinder::LocalityFinder(Index const & index, VillagesCache & villagesCache) + : m_index(index), m_villagesCache(villagesCache), m_lang(0) +{ +} void LocalityFinder::SetLanguage(int8_t lang) { @@ -124,101 +137,98 @@ void LocalityFinder::SetLanguage(int8_t lang) m_lang = lang; } -void LocalityFinder::UpdateCache(Cache & cache, m2::PointD const & pt) +void LocalityFinder::GetLocality(m2::PointD const & pt, string & name) { - m2::RectD rect = MercatorBounds::RectByCenterXYAndSizeInMeters(pt, kMaxCityRadiusMeters); - if (cache.m_rect.IsRectInside(rect)) - return; + m2::RectD const rect = MercatorBounds::RectByCenterXYAndSizeInMeters(pt, kMaxCityRadiusMeters); - rect.Add(cache.m_rect); - rect.Inflate(kInflateRectMercator, kInflateRectMercator); + bool covered = false; + m_coverage.ForEachInRect(rect, [&covered](bool) { covered = true; }); + if (!covered) + LoadVicinity(pt); - if (!m_worldId.IsAlive()) - { - m_worldId.Reset(); - m_ranks.reset(); - - vector<shared_ptr<MwmInfo>> mwmsInfo; - m_index.GetMwmsInfo(mwmsInfo); - for (auto const & info : mwmsInfo) - { - 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; + m_localities.ForEachInRect(rect, LocalitySelector(name, pt)); +} - cache.m_rect = rect; - MwmContext ctx(move(handle)); - ctx.ForEachIndex(rect, DoLoader(ctx, cache, *m_ranks, m_lang)); +void LocalityFinder::ClearCache() +{ + m_ranks.reset(); + m_coverage.Clear(); + m_localities.Clear(); + m_loadedIds.clear(); } -void LocalityFinder::GetLocality(m2::PointD const & pt, string & name) +void LocalityFinder::LoadVicinity(m2::PointD const & pt) { - Cache * working = nullptr; + m2::RectD const drect = + MercatorBounds::RectByCenterXYAndSizeInMeters(pt, 2 * kMaxCityRadiusMeters); - // Find suitable cache that includes needed point. - for (auto & cache : m_caches) + vector<shared_ptr<MwmInfo>> mwmsInfo; + m_index.GetMwmsInfo(mwmsInfo); + for (auto const & info : mwmsInfo) { - if (cache.m_rect.IsPointInside(pt)) + MwmSet::MwmId id(info); + Index::MwmHandle handle = m_index.GetMwmHandleById(id); + + if (!handle.IsAlive()) + continue; + + MwmValue const & value = *handle.GetValue<MwmValue>(); + auto const & header = value.GetHeader(); + switch (header.GetType()) + { + case feature::DataHeader::world: { - working = &cache; + if (!m_ranks) + m_ranks = RankTable::Load(value.m_cont); + if (!m_ranks) + m_ranks = make_unique<DummyRankTable>(); + + MwmContext ctx(move(handle)); + ctx.ForEachIndex(drect, + DoLoader(ctx, CityFilter(*m_ranks), m_lang, m_localities, m_loadedIds)); break; } + case feature::DataHeader::country: + if (header.GetBounds().IsPointInside(pt)) + { + MwmContext ctx(move(handle)); + ctx.ForEachIndex(drect, DoLoader(ctx, VillageFilter(ctx, m_villagesCache), m_lang, + m_localities, m_loadedIds)); + } + break; + case feature::DataHeader::worldcoasts: break; + } } - if (working == nullptr) - { - // Find most unused cache. - working = - &*min_element(begin(m_caches), end(m_caches), my::LessBy(&LocalityFinder::Cache::m_usage)); - working->Clear(); - } - - UpdateCache(*working, pt); - working->GetLocality(pt, name); + m_coverage.Add(true, m2::RectD(pt, pt)); } -void LocalityFinder::ClearCache() +// LocalitySelector -------------------------------------------------------------------------------- +LocalitySelector::LocalitySelector(string & name, m2::PointD const & pt) + : m_name(name), m_pt(pt), m_bestScore(numeric_limits<double>::max()) { - for (auto & cache : m_caches) - cache.Clear(); } -// LocalityFinder::Cache --------------------------------------------------------------------------- -void LocalityFinder::Cache::Clear() +void LocalitySelector::operator()(LocalityFinder::Item const & item) { - m_usage = 0; - m_tree.Clear(); - m_loadedIds.clear(); - m_rect.MakeEmpty(); -} + // TODO (@y, @m): replace this naive score by p-values on + // multivariate Gaussian. + double const distance = MercatorBounds::DistanceOnEarth(item.m_center, m_pt); -void LocalityFinder::Cache::GetLocality(m2::PointD const & pt, string & name) -{ - ++m_usage; - m_tree.ForEachInRectEx(m2::RectD(pt, pt), DoSelectLocality(name, pt)); + double const score = + ftypes::GetPopulationByRadius(distance) / static_cast<double>(item.m_population); + if (score < m_bestScore) + { + m_bestScore = score; + m_name = item.m_name; + } } -string DebugPrint(LocalityItem const & item) +string DebugPrint(LocalityFinder::Item const & item) { stringstream ss; - ss << "Name = " << item.m_name << "Population = " << item.m_population << "ID = " << item.m_id; + ss << "Name = " << item.m_name << ", Center = " << DebugPrint(item.m_center) + << ", Population = " << item.m_population; return ss.str(); } } // namespace search |