diff options
author | Sergey Yershov <syershov@maps.me> | 2019-06-13 12:48:35 +0300 |
---|---|---|
committer | GitHub <noreply@github.com> | 2019-06-13 12:48:35 +0300 |
commit | aad0fd0de0014b7adfdc6166b107721c232ca1ea (patch) | |
tree | 868fb41889a8c47f65859320ccdfbe1d4f9029c6 /generator | |
parent | a976e892ab2308eb3c139fd67b64ecf70f589851 (diff) | |
parent | 90c178a86c1299351c11459576f1f3e0b5ca470a (diff) |
Merge pull request #11007 from cc-engineering/generator.regions.built-geometry
[generator:regions] Generate features with build geometry
Diffstat (limited to 'generator')
-rw-r--r-- | generator/generator_tests/regions_tests.cpp | 17 | ||||
-rw-r--r-- | generator/place_node.hpp | 6 | ||||
-rw-r--r-- | generator/popularity.hpp | 1 | ||||
-rw-r--r-- | generator/regions/node.cpp | 100 | ||||
-rw-r--r-- | generator/regions/node.hpp | 11 | ||||
-rw-r--r-- | generator/regions/region.cpp | 49 | ||||
-rw-r--r-- | generator/regions/region.hpp | 6 | ||||
-rw-r--r-- | generator/regions/regions.cpp | 160 | ||||
-rw-r--r-- | generator/regions/regions_builder.cpp | 105 | ||||
-rw-r--r-- | generator/regions/regions_builder.hpp | 20 |
10 files changed, 202 insertions, 273 deletions
diff --git a/generator/generator_tests/regions_tests.cpp b/generator/generator_tests/regions_tests.cpp index 49d559040c..647832e794 100644 --- a/generator/generator_tests/regions_tests.cpp +++ b/generator/generator_tests/regions_tests.cpp @@ -185,7 +185,7 @@ UNIT_TEST(RegionsBuilderTest_GetCountryNames) auto const filename = MakeCollectorData(); RegionInfo collector(filename); RegionsBuilder builder(MakeTestDataSet1(collector)); - auto const countryNames = builder.GetCountryNames(); + auto const & countryNames = builder.GetCountryNames(); TEST_EQUAL(countryNames.size(), 2, ()); TEST(std::count(std::begin(countryNames), std::end(countryNames), "Country_1"), ()); TEST(std::count(std::begin(countryNames), std::end(countryNames), "Country_2"), ()); @@ -196,7 +196,7 @@ UNIT_TEST(RegionsBuilderTest_GetCountries) auto const filename = MakeCollectorData(); RegionInfo collector(filename); RegionsBuilder builder(MakeTestDataSet1(collector)); - auto const countries = builder.GetCountries(); + auto const & countries = builder.GetCountriesOuters(); TEST_EQUAL(countries.size(), 3, ()); TEST_EQUAL(std::count_if(std::begin(countries), std::end(countries), [](const Region & r) {return r.GetName() == "Country_1"; }), 1, ()); @@ -210,11 +210,14 @@ UNIT_TEST(RegionsBuilderTest_GetCountryTrees) RegionInfo collector(filename); std::vector<std::string> bankOfNames; RegionsBuilder builder(MakeTestDataSet1(collector)); - builder.ForEachNormalizedCountry([&](std::string const & name, Node::Ptr const & tree) { - ForEachLevelPath(tree, [&](NodePath const & path) { - StringJoinPolicy stringifier; - bankOfNames.push_back(stringifier.ToString(path)); - }); + builder.ForEachCountry([&](std::string const & name, Node::PtrList const & outers) { + for (auto const & tree : outers) + { + ForEachLevelPath(tree, [&](NodePath const & path) { + StringJoinPolicy stringifier; + bankOfNames.push_back(stringifier.ToString(path)); + }); + } }); TEST(NameExists(bankOfNames, "Country_2"), ()); diff --git a/generator/place_node.hpp b/generator/place_node.hpp index e3f6a101c6..8334f39fc3 100644 --- a/generator/place_node.hpp +++ b/generator/place_node.hpp @@ -32,12 +32,6 @@ public: Data & GetData() { return m_data; } Data const & GetData() const { return m_data; } - void ShrinkToFitChildren() - { - if (m_children.capacity() != m_children.size()) - PtrList(m_children).swap(m_children); - } - private: Data m_data; PtrList m_children; diff --git a/generator/popularity.hpp b/generator/popularity.hpp index f5758fcbfc..33ecfbfa5e 100644 --- a/generator/popularity.hpp +++ b/generator/popularity.hpp @@ -53,7 +53,6 @@ public: bool Contains(PopularityGeomPlace const & smaller) const; bool Contains(m2::PointD const & point) const; feature::FeatureBuilder const & GetFeature() const { return m_feature; } - void DeletePolygon() { m_polygon = nullptr; } double GetArea() const { return m_area; } base::GeoObjectId GetId() const { return m_id; } diff --git a/generator/regions/node.cpp b/generator/regions/node.cpp index 6d54bd7cb0..68749a37c7 100644 --- a/generator/regions/node.cpp +++ b/generator/regions/node.cpp @@ -11,69 +11,7 @@ namespace generator { namespace regions { -namespace -{ -using MergeFunc = std::function<Node::Ptr(Node::Ptr, Node::Ptr)>; - -bool LessNodePtrById(Node::Ptr l, Node::Ptr r) -{ - auto const & lRegion = l->GetData(); - auto const & rRegion = r->GetData(); - return lRegion.GetId() < rRegion.GetId(); -} - -Node::PtrList MergeChildren(Node::PtrList const & l, Node::PtrList const & r, Node::Ptr newParent) -{ - Node::PtrList result(l); - std::copy(std::begin(r), std::end(r), std::back_inserter(result)); - for (auto & p : result) - p->SetParent(newParent); - - std::sort(std::begin(result), std::end(result), LessNodePtrById); - return result; -} - -Node::PtrList NormalizeChildren(Node::PtrList const & children, MergeFunc mergeTree) -{ - Node::PtrList uniqueChildren; - auto const pred = [](Node::Ptr l, Node::Ptr r) - { - auto const & lRegion = l->GetData(); - auto const & rRegion = r->GetData(); - return lRegion.GetId() == rRegion.GetId(); - }; - std::unique_copy(std::begin(children), std::end(children), - std::back_inserter(uniqueChildren), pred); - Node::PtrList result; - for (auto const & ch : uniqueChildren) - { - auto const bounds = std::equal_range(std::begin(children), std::end(children), ch, - LessNodePtrById); - auto merged = std::accumulate(bounds.first, bounds.second, Node::Ptr(), mergeTree); - result.emplace_back(std::move(merged)); - } - - return result; -} - -Node::Ptr MergeHelper(Node::Ptr l, Node::Ptr r, MergeFunc mergeTree) -{ - auto const & lChildren = l->GetChildren(); - auto const & rChildren = r->GetChildren(); - auto const children = MergeChildren(lChildren, rChildren, l); - if (children.empty()) - return l; - - auto resultChildren = NormalizeChildren(children, mergeTree); - l->SetChildren(std::move(resultChildren)); - l->ShrinkToFitChildren(); - r->RemoveChildren(); - r->ShrinkToFitChildren(); - return l; -} -} // nmespace - -size_t TreeSize(Node::Ptr node) +size_t TreeSize(Node::Ptr const & node) { if (node == nullptr) return 0; @@ -85,7 +23,7 @@ size_t TreeSize(Node::Ptr node) return size; } -size_t MaxDepth(Node::Ptr node) +size_t MaxDepth(Node::Ptr const & node) { if (node == nullptr) return 0; @@ -133,7 +71,7 @@ NodePath MakeLevelPath(Node::Ptr const & node) return path; } -void PrintTree(Node::Ptr node, std::ostream & stream = std::cout, std::string prefix = "", +void PrintTree(Node::Ptr const & node, std::ostream & stream = std::cout, std::string prefix = "", bool isTail = true) { auto const & children = node->GetChildren(); @@ -171,37 +109,5 @@ void DebugPrintTree(Node::Ptr const & tree, std::ostream & stream) PrintTree(tree, stream); stream << std::endl; } - -Node::Ptr MergeTree(Node::Ptr l, Node::Ptr r) -{ - if (l == nullptr) - return r; - - if (r == nullptr) - return l; - - auto const & lRegion = l->GetData(); - auto const & rRegion = r->GetData(); - if (lRegion.GetId() != rRegion.GetId()) - return nullptr; - - if (lRegion.GetArea() > rRegion.GetArea()) - return MergeHelper(l, r, MergeTree); - else - return MergeHelper(r, l, MergeTree); -} - -void NormalizeTree(Node::Ptr tree) -{ - if (tree == nullptr) - return; - - auto & children = tree->GetChildren(); - std::sort(std::begin(children), std::end(children), LessNodePtrById); - auto newChildren = NormalizeChildren(children, MergeTree); - tree->SetChildren(std::move(newChildren)); - for (auto const & ch : tree->GetChildren()) - NormalizeTree(ch); -} } // namespace regions } // namespace generator diff --git a/generator/regions/node.hpp b/generator/regions/node.hpp index 1ce292ea1b..caae7db477 100644 --- a/generator/regions/node.hpp +++ b/generator/regions/node.hpp @@ -29,17 +29,10 @@ void ForEachLevelPath(Node::Ptr const & tree, Fn && fn) ForEachLevelPath(subtree, fn); } -size_t TreeSize(Node::Ptr node); +size_t TreeSize(Node::Ptr const & node); -size_t MaxDepth(Node::Ptr node); +size_t MaxDepth(Node::Ptr const & node); void DebugPrintTree(Node::Ptr const & tree, std::ostream & stream = std::cout); - -// This function merges two trees if the roots have the same ids. -Node::Ptr MergeTree(Node::Ptr l, Node::Ptr r); - -// This function corrects the tree. It traverses the whole node and unites children with -// the same ids. -void NormalizeTree(Node::Ptr tree); } // namespace regions } // namespace generator diff --git a/generator/regions/region.cpp b/generator/regions/region.cpp index 83efaa9a00..4d6267fb89 100644 --- a/generator/regions/region.cpp +++ b/generator/regions/region.cpp @@ -19,7 +19,6 @@ namespace generator { namespace regions { - BoostPolygon MakePolygonWithRadius(BoostPoint const & point, double radius, size_t numPoints = 16) { boost::geometry::strategy::buffer::point_circle point_strategy(numPoints); @@ -35,6 +34,7 @@ BoostPolygon MakePolygonWithRadius(BoostPoint const & point, double radius, size CHECK_EQUAL(result.size(), 1, ()); return std::move(result.front()); } + Region::Region(FeatureBuilder const & fb, RegionDataProxy const & rd) : RegionWithName(fb.GetParams().name) , RegionWithData(rd) @@ -81,26 +81,15 @@ double Region::GetRadiusByPlaceType(PlaceType place) UNREACHABLE(); } -void Region::DeletePolygon() -{ - m_polygon = nullptr; -} - void Region::FillPolygon(FeatureBuilder const & fb) { CHECK(m_polygon, ()); boost_helpers::FillPolygon(*m_polygon, fb); } -bool Region::IsCountry() const -{ - static auto const kAdminLevelCountry = AdminLevel::Two; - return GetPlaceType() == PlaceType::Unknown && GetAdminLevel() == kAdminLevelCountry; -} - bool Region::IsLocality() const { - return GetPlaceType() != PlaceType::Unknown; + return GetPlaceType() >= PlaceType::City; } bool Region::Contains(Region const & smaller) const @@ -156,33 +145,15 @@ bool Region::Contains(BoostPoint const & point) const boost::geometry::covered_by(point, *m_polygon); } -bool FeaturePlacePointToRegion(RegionInfo const & regionInfo, FeatureBuilder & feature) +std::string GetRegionNotation(Region const & region) { - if (!feature.IsPoint()) - return false; - - auto const center = feature.GetKeyPoint(); - BoostPolygon polygon; - auto info = regionInfo.Get(feature.GetMostGenericOsmId()); - if (!info.HasPlaceType()) - return false; - - auto const placeType = info.GetPlaceType(); - if (placeType == PlaceType::Unknown) - return false; - - auto const radius = Region::GetRadiusByPlaceType(placeType); - polygon = MakePolygonWithRadius({center.x, center.y}, radius); - auto const & outer = polygon.outer(); - FeatureBuilder::PointSeq seq; - std::transform(std::begin(outer), std::end(outer), std::back_inserter(seq), [](BoostPoint const & p) { - return m2::PointD(p.get<0>(), p.get<1>()); - }); - feature.ResetGeometry(); - feature.AddPolygon(seq); - feature.SetRank(0); - feature.SetArea(); - return true; + auto notation = region.GetEnglishOrTransliteratedName(); + if (notation.empty()) + return region.GetName(); + + if (notation != region.GetName()) + notation += " / " + region.GetName(); + return notation; } } // namespace regions } // namespace generator diff --git a/generator/regions/region.hpp b/generator/regions/region.hpp index 95013be5fa..507ccc7341 100644 --- a/generator/regions/region.hpp +++ b/generator/regions/region.hpp @@ -27,17 +27,15 @@ public: // Build a region and its boundary based on the heuristic. explicit Region(PlacePoint const & place); - // After calling DeletePolygon, you cannot use Contains, ContainsRect, CalculateOverlapPercentage. - void DeletePolygon(); bool Contains(Region const & smaller) const; bool ContainsRect(Region const & smaller) const; bool Contains(PlacePoint const & place) const; bool Contains(BoostPoint const & point) const; double CalculateOverlapPercentage(Region const & other) const; BoostPoint GetCenter() const; - bool IsCountry() const; bool IsLocality() const; BoostRect const & GetRect() const { return m_rect; } + std::shared_ptr<BoostPolygon> const & GetPolygon() const noexcept { return m_polygon; } double GetArea() const { return m_area; } // This function uses heuristics and assigns a radius according to the tag place. // The radius will be returned in mercator units. @@ -51,6 +49,6 @@ private: double m_area; }; -bool FeaturePlacePointToRegion(RegionInfo const & regionInfo, feature::FeatureBuilder & feature); +std::string GetRegionNotation(Region const & region); } // namespace regions } // namespace generator diff --git a/generator/regions/regions.cpp b/generator/regions/regions.cpp index 31fa33426a..37481d2fd4 100644 --- a/generator/regions/regions.cpp +++ b/generator/regions/regions.cpp @@ -23,6 +23,7 @@ #include <algorithm> #include <fstream> #include <numeric> +#include <map> #include <memory> #include <queue> #include <set> @@ -53,6 +54,7 @@ public: , m_pathOutRepackedRegionsTmpMwm{pathOutRepackedRegionsTmpMwm} , m_verbose{verbose} , m_regionsInfoCollector{pathInRegionsCollector} + , m_regionsKv{pathOutRegionsKv, std::ofstream::out} { LOG(LINFO, ("Start generating regions from", m_pathInRegionsTmpMwm)); auto timer = base::Timer{}; @@ -68,38 +70,62 @@ public: private: void GenerateRegions(RegionsBuilder & builder) { - std::ofstream regionsKv{m_pathOutRegionsKv, std::ofstream::out}; - std::set<base::GeoObjectId> setIds; - size_t countIds = 0; - builder.ForEachNormalizedCountry([&](std::string const & name, Node::Ptr const & tree) { - if (!tree) - return; + builder.ForEachCountry([&](std::string const & name, Node::PtrList const & outers) { + auto const & countryPlace = outers.front()->GetData(); + auto const & countryName = countryPlace.GetEnglishOrTransliteratedName(); + GenerateKv(countryName, outers); + }); + + LOG(LINFO, ("Regions objects key-value for", builder.GetCountryNames().size(), + "countries storage saved to", m_pathOutRegionsKv)); + LOG(LINFO, (m_objectsRegions.size(), "total regions.", + m_regionsCountries.size(), "total objects.")); + + RepackTmpMwm(); + } + + void GenerateKv(std::string const & countryName, Node::PtrList const & outers) + { + LOG(LINFO, ("Generate country", countryName)); + auto country = std::make_shared<std::string>(countryName); + size_t countryRegionsCount = 0; + size_t countryObjectCount = 0; + + auto jsonPolicy = std::make_unique<JsonPolicy>(m_verbose); + for (auto const & tree : outers) + { if (m_verbose) DebugPrintTree(tree); - LOG(LINFO, ("Processing country", name)); - - auto jsonPolicy = JsonPolicy{m_verbose}; - ForEachLevelPath(tree, [&](auto && path) { + ForEachLevelPath(tree, [&] (NodePath const & path) { auto const & node = path.back(); - auto const id = node->GetData().GetId(); - regionsKv << static_cast<int64_t>(id.GetEncodedId()) << " " << jsonPolicy.ToString(path) << "\n"; - ++countIds; - if (!setIds.insert(id).second) - LOG(LWARNING, ("Id alredy exists:", id)); - }); - }); + auto const & region = node->GetData(); + auto const & objectId = region.GetId(); + auto const & regionCountryEmplace = m_regionsCountries.emplace(objectId, country); + if (!regionCountryEmplace.second && regionCountryEmplace.first->second != country) + { + LOG(LWARNING, ("Failed to place", GetLabel(region.GetLevel()), "region", objectId, + "(", GetRegionNotation(region), ")", + "into", *country, + ": region already exists in", *regionCountryEmplace.first->second)); + return; + } - LOG(LINFO, ("Regions objects key-value for", builder.GetCountryNames().size(), - "countries storage saved to", m_pathOutRegionsKv)); - LOG(LINFO, (countIds, "total ids.", setIds.size(), "unique ids.")); + m_objectsRegions.emplace(objectId, node); + ++countryRegionsCount; + + if (regionCountryEmplace.second) + { + m_regionsKv << static_cast<int64_t>(objectId.GetEncodedId()) << " " << jsonPolicy->ToString(path) + << "\n"; + ++countryObjectCount; + } + }); + } - // todo(maksimandrianov1): Perhaps this is not the best solution. This is a hot fix. Perhaps it - // is better to transfer this to index generation(function GenerateRegionsData), - // or to combine index generation and key-value storage generation in - // generator_tool(generator_tool.cpp). - RepackTmpMwm(setIds); + LOG(LINFO, ("Country regions of", *country, "has built:", countryRegionsCount, "total regions.", + countryObjectCount, "objects.")); } std::tuple<RegionsBuilder::Regions, PlacePointsMap> @@ -112,12 +138,25 @@ private: { auto const id = fb.GetMostGenericOsmId(); auto region = Region(fb, collector.Get(id)); + + auto const & name = region.GetName(); + auto const level = RegionsBuilder::GetLevel(region); + if (name.empty() || level == PlaceLevel::Unknown) + return; + regions.emplace_back(std::move(region)); } else if (fb.IsPoint()) { auto const id = fb.GetMostGenericOsmId(); - placePointsMap.emplace(id, PlacePoint{fb, collector.Get(id)}); + auto place = PlacePoint{fb, collector.Get(id)}; + + auto const & name = place.GetName(); + auto const placeType = place.GetPlaceType(); + if (name.empty() || placeType == PlaceType::Unknown) + return; + + placePointsMap.emplace(id, std::move(place)); } }; @@ -131,41 +170,61 @@ private: PlacePointsMap placePointsMap; std::tie(regions, placePointsMap) = ReadDatasetFromTmpMwm(m_pathInRegionsTmpMwm, m_regionsInfoCollector); FixRegionsWithPlacePointApproximation(placePointsMap, regions); - FilterRegions(regions); return regions; } - void FilterRegions(RegionsBuilder::Regions & regions) + void RepackTmpMwm() { - auto const pred = [](Region const & region) { - auto const & name = region.GetName(); - if (name.empty()) - return false; + feature::FeaturesCollector featuresCollector{m_pathOutRepackedRegionsTmpMwm}; + std::set<base::GeoObjectId> processedObjects; + auto const toDo = [&](FeatureBuilder & fb, uint64_t /* currPos */) { + auto const id = fb.GetMostGenericOsmId(); + auto objectRegions = m_objectsRegions.equal_range(id); + if (objectRegions.first == objectRegions.second) + return; + if (!processedObjects.insert(id).second) + return; - auto const level = RegionsBuilder::GetLevel(region); - return level != PlaceLevel::Unknown; + for (auto item = objectRegions.first; item != objectRegions.second; ++item) + { + auto const & region = item->second->GetData(); + ResetGeometry(fb, region); + fb.SetOsmId(region.GetId()); + fb.SetRank(0); + featuresCollector.Collect(fb); + } }; - base::EraseIf(regions, pred); + LOG(LINFO, ("Start regions repacking from", m_pathInRegionsTmpMwm)); + feature::ForEachFromDatRawFormat(m_pathInRegionsTmpMwm, toDo); + LOG(LINFO, ("Repacked regions temporary mwm saved to", m_pathOutRepackedRegionsTmpMwm)); } - void RepackTmpMwm(std::set<base::GeoObjectId> const & ids) + void ResetGeometry(FeatureBuilder & fb, Region const & region) { - FeaturesCollector collector(m_pathOutRepackedRegionsTmpMwm); - auto const toDo = [this, &collector, &ids](FeatureBuilder & fb, uint64_t /* currPos */) { - if (ids.count(fb.GetMostGenericOsmId()) == 0 || - (fb.IsPoint() && !FeaturePlacePointToRegion(m_regionsInfoCollector, fb))) - { - return; - } + fb.ResetGeometry(); - CHECK(fb.IsArea(), ()); - collector.Collect(fb); - }; + auto const & polygon = region.GetPolygon(); + auto outer = GetPointSeq(polygon->outer()); + fb.AddPolygon(outer); + FeatureBuilder::Geometry holes; + auto const & inners = polygon->inners(); + std::transform(std::begin(inners), std::end(inners), std::back_inserter(holes), + [this](auto && polygon) { return this->GetPointSeq(polygon); }); + fb.SetHoles(std::move(holes)); + fb.SetArea(); - ForEachFromDatRawFormat(m_pathInRegionsTmpMwm, toDo); + CHECK(fb.IsArea(), ()); + CHECK(fb.IsGeometryClosed(), ()); + } - LOG(LINFO, ("Repacked regions temporary mwm saved to", m_pathOutRepackedRegionsTmpMwm)); + template <typename Polygon> + FeatureBuilder::PointSeq GetPointSeq(Polygon const & polygon) + { + FeatureBuilder::PointSeq seq; + std::transform(std::begin(polygon), std::end(polygon), std::back_inserter(seq), + [] (BoostPoint const & p) { return m2::PointD(p.get<0>(), p.get<1>()); }); + return seq; } std::string m_pathInRegionsTmpMwm; @@ -175,6 +234,11 @@ private: bool m_verbose{false}; RegionInfo m_regionsInfoCollector; + + std::ofstream m_regionsKv; + + std::multimap<base::GeoObjectId, Node::Ptr> m_objectsRegions; + std::map<base::GeoObjectId, std::shared_ptr<std::string>> m_regionsCountries; }; } // namespace diff --git a/generator/regions/regions_builder.cpp b/generator/regions/regions_builder.cpp index 252a1f9099..3db728cb95 100644 --- a/generator/regions/regions_builder.cpp +++ b/generator/regions/regions_builder.cpp @@ -18,43 +18,49 @@ namespace generator { namespace regions { -namespace -{ -Node::Ptr ShrinkToFit(Node::Ptr p) +RegionsBuilder::RegionsBuilder(Regions && regions, size_t threadsCount) + : m_threadsCount(threadsCount) { - p->ShrinkToFitChildren(); - for (auto ptr : p->GetChildren()) - ShrinkToFit(ptr); + ASSERT(m_threadsCount != 0, ()); - return p; + m_regionsInAreaOrder = FormRegionsInAreaOrder(std::move(regions)); + m_countriesOuters = ExtractCountriesOuters(m_regionsInAreaOrder); } -} // namespace -RegionsBuilder::RegionsBuilder(Regions && regions, size_t threadsCount) - : m_regions(std::move(regions)) - , m_threadsCount(threadsCount) +RegionsBuilder::Regions RegionsBuilder::FormRegionsInAreaOrder(Regions && regions) { - ASSERT(m_threadsCount != 0, ()); - - auto const isCountry = [](Region const & r) { return r.IsCountry(); }; - std::copy_if(std::begin(m_regions), std::end(m_regions), std::back_inserter(m_countries), isCountry); - base::EraseIf(m_regions, isCountry); auto const cmp = [](Region const & l, Region const & r) { return l.GetArea() > r.GetArea(); }; - std::sort(std::begin(m_countries), std::end(m_countries), cmp); + std::sort(std::begin(regions), std::end(regions), cmp); + return std::move(regions); +} + +RegionsBuilder::Regions RegionsBuilder::ExtractCountriesOuters(Regions & regions) +{ + Regions countriesOuters; + + auto const isCountry = [](Region const & region) { + return AdminLevel::Two == region.GetAdminLevel(); + }; + std::copy_if(std::begin(regions), std::end(regions), std::back_inserter(countriesOuters), + isCountry); + + base::EraseIf(regions, isCountry); + + return countriesOuters; } -RegionsBuilder::Regions const & RegionsBuilder::GetCountries() const +RegionsBuilder::Regions const & RegionsBuilder::GetCountriesOuters() const { - return m_countries; + return m_countriesOuters; } RegionsBuilder::StringsList RegionsBuilder::GetCountryNames() const { StringsList result; std::unordered_set<std::string> set; - for (auto const & c : GetCountries()) + for (auto const & c : GetCountriesOuters()) { - auto name = c.GetName(); + auto const & name = c.GetName(); if (set.insert(name).second) result.emplace_back(std::move(name)); } @@ -62,13 +68,13 @@ RegionsBuilder::StringsList RegionsBuilder::GetCountryNames() const return result; } -Node::PtrList RegionsBuilder::MakeSelectedRegionsByCountry(Region const & country, +Node::PtrList RegionsBuilder::MakeSelectedRegionsByCountry(Region const & outer, Regions const & allRegions) { - std::vector<LevelRegion> regionsInCountry{{PlaceLevel::Country, country}}; + std::vector<LevelRegion> regionsInCountry{{PlaceLevel::Country, outer}}; for (auto const & region : allRegions) { - if (country.ContainsRect(region)) + if (outer.ContainsRect(region)) regionsInCountry.emplace_back(GetLevel(region), region); } @@ -87,10 +93,10 @@ Node::PtrList RegionsBuilder::MakeSelectedRegionsByCountry(Region const & countr return nodes; } -Node::Ptr RegionsBuilder::BuildCountryRegionTree(Region const & country, +Node::Ptr RegionsBuilder::BuildCountryRegionTree(Region const & outer, Regions const & allRegions) { - auto nodes = MakeSelectedRegionsByCountry(country, allRegions); + auto nodes = MakeSelectedRegionsByCountry(outer, allRegions); while (nodes.size() > 1) { auto itFirstNode = std::rbegin(nodes); @@ -106,52 +112,47 @@ Node::Ptr RegionsBuilder::BuildCountryRegionTree(Region const & country, { (*itFirstNode)->SetParent(*itCurr); (*itCurr)->AddChild(*itFirstNode); - // We want to free up memory. - firstRegion.DeletePolygon(); - nodes.pop_back(); break; } } - if (itCurr == std::rend(nodes)) - nodes.pop_back(); + nodes.pop_back(); } - return nodes.empty() ? std::shared_ptr<Node>() : ShrinkToFit(nodes.front()); + return nodes.front(); } -void RegionsBuilder::ForEachNormalizedCountry(NormalizedCountryFn fn) +void RegionsBuilder::ForEachCountry(CountryFn fn) { for (auto const & countryName : GetCountryNames()) { - RegionsBuilder::Regions country; - auto const & countries = GetCountries(); - auto const pred = [&](const Region & r) { return countryName == r.GetName(); }; - std::copy_if(std::begin(countries), std::end(countries), std::back_inserter(country), pred); - auto const countryTrees = BuildCountryRegionTrees(country); - auto mergedTree = std::accumulate(std::begin(countryTrees), std::end(countryTrees), - Node::Ptr(), MergeTree); - NormalizeTree(mergedTree); - fn(countryName, mergedTree); + Regions outers; + auto const & countries = GetCountriesOuters(); + auto const pred = [&](Region const & country) { return countryName == country.GetName(); }; + std::copy_if(std::begin(countries), std::end(countries), std::back_inserter(outers), pred); + auto countryTrees = BuildCountryRegionTrees(outers); + + fn(countryName, countryTrees); } } -std::vector<Node::Ptr> RegionsBuilder::BuildCountryRegionTrees(RegionsBuilder::Regions const & countries) +Node::PtrList RegionsBuilder::BuildCountryRegionTrees(Regions const & outers) { - std::vector<std::future<Node::Ptr>> tmp; + std::vector<std::future<Node::Ptr>> buildingTasks; { base::thread_pool::computational::ThreadPool threadPool(m_threadsCount); - for (auto const & country : countries) + for (auto const & outer : outers) { - auto result = threadPool.Submit(&RegionsBuilder::BuildCountryRegionTree, country, m_regions); - tmp.emplace_back(std::move(result)); + auto result = threadPool.Submit( + &RegionsBuilder::BuildCountryRegionTree, std::cref(outer), std::cref(m_regionsInAreaOrder)); + buildingTasks.emplace_back(std::move(result)); } } - std::vector<Node::Ptr> res; - res.reserve(tmp.size()); - std::transform(std::begin(tmp), std::end(tmp), - std::back_inserter(res), [](auto & f) { return f.get(); }); - return res; + std::vector<Node::Ptr> trees; + trees.reserve(buildingTasks.size()); + std::transform(std::begin(buildingTasks), std::end(buildingTasks), + std::back_inserter(trees), [](auto & f) { return f.get(); }); + return trees; } // static diff --git a/generator/regions/regions_builder.hpp b/generator/regions/regions_builder.hpp index 1bed2f3c7a..3a77bfceab 100644 --- a/generator/regions/regions_builder.hpp +++ b/generator/regions/regions_builder.hpp @@ -21,27 +21,27 @@ class RegionsBuilder public: using Regions = std::vector<Region>; using StringsList = std::vector<std::string>; - using IdStringList = std::vector<std::pair<base::GeoObjectId, std::string>>; - using CountryTrees = std::multimap<std::string, Node::Ptr>; - using NormalizedCountryFn = std::function<void(std::string const &, Node::Ptr const &)>; + using CountryFn = std::function<void(std::string const &, Node::PtrList const &)>; explicit RegionsBuilder(Regions && regions, size_t threadsCount = 1); - Regions const & GetCountries() const; + Regions const & GetCountriesOuters() const; StringsList GetCountryNames() const; - void ForEachNormalizedCountry(NormalizedCountryFn fn); + void ForEachCountry(CountryFn fn); static PlaceLevel GetLevel(Region const & region); static size_t GetWeight(Region const & region); private: - static Node::PtrList MakeSelectedRegionsByCountry(Region const & country, + Regions FormRegionsInAreaOrder(Regions && regions); + Regions ExtractCountriesOuters(Regions & regions); + Node::PtrList BuildCountryRegionTrees(Regions const & outers); + static Node::Ptr BuildCountryRegionTree(Region const & outer, Regions const & allRegions); + static Node::PtrList MakeSelectedRegionsByCountry(Region const & outer, Regions const & allRegions); - static Node::Ptr BuildCountryRegionTree(Region const & country, Regions const & allRegions); - std::vector<Node::Ptr> BuildCountryRegionTrees(RegionsBuilder::Regions const & countries); - Regions m_countries; - Regions m_regions; + Regions m_countriesOuters; + Regions m_regionsInAreaOrder; size_t m_threadsCount; }; } // namespace regions |