Merge pull request #10642 from cc-engineering/generator.region.region-level

[generator:regions] Refactor: class LevelRegion for region tree

15 files changed, 220 insertions, 159 deletions

diff --git a/generator/CMakeLists.txt b/generator/CMakeLists.txt
index b1be4492c2..f63dc82f58 100644
--- a/generator/CMakeLists.txt
+++ b/generator/CMakeLists.txt
@@ -147,6 +147,7 @@ set(SRC
   regions/city.hpp
   regions/collector_region_info.cpp
   regions/collector_region_info.hpp
+  regions/level_region.hpp
   regions/node.cpp
   regions/node.hpp
   regions/region.cpp
diff --git a/generator/generator_tests/regions_tests.cpp b/generator/generator_tests/regions_tests.cpp
index d2b55568b8..dba5c11f0a 100644
--- a/generator/generator_tests/regions_tests.cpp
+++ b/generator/generator_tests/regions_tests.cpp
@@ -202,8 +202,7 @@ UNIT_TEST(RegionsBuilderTest_GetCountryTrees)
   std::vector<std::string> bankOfNames;
   RegionsBuilder builder(MakeTestDataSet1(collector));
   builder.ForEachNormalizedCountry([&](std::string const & name, Node::Ptr const & tree) {
-    Visit(tree, [&](Node::Ptr const & node) {
-      auto const path = MakeNodePath(node);
+    ForEachLevelPath(tree, [&](NodePath const & path) {
       StringJoinPolicy stringifier;
       bankOfNames.push_back(stringifier.ToString(path));
     });
diff --git a/generator/regions/collector_region_info.cpp b/generator/regions/collector_region_info.cpp
index fcdc495ab0..ac2720eaef 100644
--- a/generator/regions/collector_region_info.cpp
+++ b/generator/regions/collector_region_info.cpp
@@ -35,6 +35,30 @@ PlaceType EncodePlaceType(std::string const & place)
   return it == m.end() ? PlaceType::Unknown : it->second;
 }
 
+char const * GetLabel(PlaceLevel level)
+{
+  switch (level)
+  {
+  case PlaceLevel::Country:
+    return "country";
+  case PlaceLevel::Region:
+    return "region";
+  case PlaceLevel:: Subregion:
+    return "subregion";
+  case PlaceLevel::Locality:
+    return "locality";
+  case PlaceLevel::Suburb:
+    return "suburb";
+  case PlaceLevel::Sublocality:
+    return "sublocality";
+  case PlaceLevel::Unknown:
+    return nullptr;
+  case PlaceLevel::Count:
+    UNREACHABLE();
+  }
+  UNREACHABLE();
+}
+
 CollectorRegionInfo::CollectorRegionInfo(std::string const & filename) : m_filename(filename) {}
 
 void CollectorRegionInfo::CollectFeature(const FeatureBuilder1 &, OsmElement const & el)
diff --git a/generator/regions/collector_region_info.hpp b/generator/regions/collector_region_info.hpp
index 33bfaf62ba..423df4644a 100644
--- a/generator/regions/collector_region_info.hpp
+++ b/generator/regions/collector_region_info.hpp
@@ -41,7 +41,6 @@ enum class AdminLevel : uint8_t
 };
 
 // https://wiki.openstreetmap.org/wiki/Key:place
-// Warning: values are important, be careful they are used in Region::GetRank() in regions.cpp
 enum class PlaceType: uint8_t
 {
   Unknown = 0,
@@ -57,6 +56,20 @@ enum class PlaceType: uint8_t
 
 PlaceType EncodePlaceType(std::string const & place);
 
+enum class PlaceLevel : uint8_t
+{
+  Unknown = 0,
+  Country = 1,
+  Region = 2,
+  Subregion = 3,
+  Locality = 4,
+  Suburb = 5,
+  Sublocality = 6,
+  Count,
+};
+
+char const * GetLabel(PlaceLevel level);
+
 // Codes for the names of countries, dependent territories, and special areas of geographical
 // interest.
 // https://en.wikipedia.org/wiki/ISO_3166-1
diff --git a/generator/regions/level_region.hpp b/generator/regions/level_region.hpp
new file mode 100644
index 0000000000..2988223523
--- /dev/null
+++ b/generator/regions/level_region.hpp
@@ -0,0 +1,27 @@
+#pragma once
+
+#include "generator/regions/collector_region_info.hpp"
+#include "generator/regions/region.hpp"
+
+namespace generator
+{
+namespace regions
+{
+class LevelRegion : public Region
+{
+public:
+  LevelRegion(PlaceLevel level, Region const & region)
+      : Region(region), m_level{level} { }
+
+  PlaceLevel GetLevel() const noexcept { return m_level; }
+  void SetLevel(PlaceLevel level) { m_level = level; }
+
+  // Absolute rank values do not mean anything. But if the rank of the first object is more than the
+  // rank of the second object, then the first object is considered more nested.
+  uint8_t GetRank() const { return static_cast<uint8_t>(m_level); }
+
+private:
+  PlaceLevel m_level;
+};
+}  // namespace regions
+}  // namespace generator
diff --git a/generator/regions/node.cpp b/generator/regions/node.cpp
index 9bbf2567d0..909039004a 100644
--- a/generator/regions/node.cpp
+++ b/generator/regions/node.cpp
@@ -2,6 +2,7 @@
 
 #include "geometry/mercator.hpp"
 
+#include <array>
 #include <algorithm>
 #include <iomanip>
 #include <numeric>
@@ -96,18 +97,39 @@ size_t MaxDepth(Node::Ptr node)
   return depth;
 }
 
-NodePath MakeNodePath(Node::Ptr const & node)
+NodePath MakeLevelPath(Node::Ptr const & node)
 {
-  NodePath path;
+  CHECK(node->GetData().GetLevel() != PlaceLevel::Unknown, ());
 
-  auto current = node;
-  while (current)
+  std::array<bool, static_cast<std::size_t>(PlaceLevel::Count)> skipLevels{};
+  NodePath path{node};
+  for (auto p = node->GetParent(); p; p = p->GetParent())
   {
-    path.push_back(current);
-    current = current->GetParent();
+    auto const level = p->GetData().GetLevel();
+    if (PlaceLevel::Unknown == level)
+      continue;
+
+    auto levelIndex = static_cast<std::size_t>(level);
+    if (skipLevels.at(levelIndex))
+      continue;
+
+    skipLevels[levelIndex] = true;
+    if (PlaceLevel::Locality == level)
+    {
+      // To ignore covered locality.
+      skipLevels[static_cast<std::size_t>(PlaceLevel::Suburb)] = true;
+      skipLevels[static_cast<std::size_t>(PlaceLevel::Sublocality)] = true;
+    }
+
+    path.push_back(p);
   }
   std::reverse(path.begin(), path.end());
 
+  // Sort by level in case that megapolis (PlaceLevel::Locality) contains subregions
+  // (PlaceLevel::Subregions).
+  std::sort(path.begin(), path.end(), [] (Node::Ptr const & l, Node::Ptr const & r) {
+    return l->GetData().GetLevel() < r->GetData().GetLevel();
+  });
   return path;
 }
 
@@ -130,9 +152,10 @@ void PrintTree(Node::Ptr node, std::ostream & stream = std::cout, std::string pr
   auto const & d = node->GetData();
   auto const point = d.GetCenter();
   auto const center = MercatorBounds::ToLatLon({point.get<0>(), point.get<1>()});
+  auto const label = GetLabel(d.GetLevel());
   stream << d.GetName() << "<" << d.GetEnglishOrTransliteratedName() << "> ("
          << DebugPrint(d.GetId())
-         << ";" << d.GetLabel()
+         << ";" << (label ? label : "-")
          << ";" << static_cast<size_t>(d.GetRank())
          << ";[" << std::fixed << std::setprecision(7) << center.lat << "," << center.lon << "])"
          << std::endl;
diff --git a/generator/regions/node.hpp b/generator/regions/node.hpp
index cbafc15254..1ce292ea1b 100644
--- a/generator/regions/node.hpp
+++ b/generator/regions/node.hpp
@@ -1,7 +1,7 @@
 #pragma once
 
 #include "generator/place_node.hpp"
-#include "generator/regions/region.hpp"
+#include "generator/regions/level_region.hpp"
 
 #include <iostream>
 
@@ -9,15 +9,30 @@ namespace generator
 {
 namespace regions
 {
-using Node = PlaceNode<Region>;
+using Node = PlaceNode<LevelRegion>;
 using NodePath = std::vector<Node::Ptr>;
 
+NodePath MakeLevelPath(Node::Ptr const & node);
+
+// The function has formally quadratic time complexity: depth * size of tree.
+// In fact, tree depth is low value and thus the function time complexity is linear.
+template <typename Fn>
+void ForEachLevelPath(Node::Ptr const & tree, Fn && fn)
+{
+  if (!tree)
+    return;
+
+  if (tree->GetData().GetLevel() != PlaceLevel::Unknown)
+    fn(MakeLevelPath(tree));
+
+  for (auto const & subtree : tree->GetChildren())
+    ForEachLevelPath(subtree, fn);
+}
+
 size_t TreeSize(Node::Ptr node);
 
 size_t MaxDepth(Node::Ptr node);
 
-NodePath MakeNodePath(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.
diff --git a/generator/regions/region.cpp b/generator/regions/region.cpp
index e0a4ab0652..ae8e75d75f 100644
--- a/generator/regions/region.cpp
+++ b/generator/regions/region.cpp
@@ -94,12 +94,12 @@ void Region::FillPolygon(FeatureBuilder1 const & fb)
 bool Region::IsCountry() const
 {
   static auto const kAdminLevelCountry = AdminLevel::Two;
-  return !HasPlaceType() && GetAdminLevel() == kAdminLevelCountry;
+  return GetPlaceType() == PlaceType::Unknown && GetAdminLevel() == kAdminLevelCountry;
 }
 
 bool Region::IsLocality() const
 {
-  return HasPlaceType();
+  return GetPlaceType() != PlaceType::Unknown;
 }
 
 bool Region::Contains(Region const & smaller) const
diff --git a/generator/regions/region_base.cpp b/generator/regions/region_base.cpp
index 795d8fcb43..797ff56ff7 100644
--- a/generator/regions/region_base.cpp
+++ b/generator/regions/region_base.cpp
@@ -60,114 +60,5 @@ std::string RegionWithData::GetIsoCode() const
 {
   return m_regionData.GetIsoCodeAlpha2();
 }
-
-// The values ​​of the administrative level and place are indirectly dependent.
-// This is used when calculating the rank.
-uint8_t RegionWithData::GetRank() const
-{
-  auto const adminLevel = GetAdminLevel();
-  auto const placeType = GetPlaceType();
-
-  switch (placeType)
-  {
-  case PlaceType::City:
-  case PlaceType::Town:
-  case PlaceType::Village:
-  case PlaceType::Hamlet:
-  case PlaceType::Suburb:
-  case PlaceType::Neighbourhood:
-  case PlaceType::Locality:
-  case PlaceType::IsolatedDwelling:
-    return static_cast<uint8_t>(placeType);
-  default:
-    break;
-  }
-
-  switch (adminLevel)
-  {
-  case AdminLevel::Two:
-  case AdminLevel::Four:
-  case AdminLevel::Six:
-    return static_cast<uint8_t>(adminLevel);
-  default:
-    break;
-  }
-
-  return kNoRank;
-}
-
-std::string RegionWithData::GetLabel() const
-{
-  auto const adminLevel = GetAdminLevel();
-  auto const placeType = GetPlaceType();
-
-  switch (placeType)
-  {
-  case PlaceType::City:
-  case PlaceType::Town:
-  case PlaceType::Village:
-  case PlaceType::Hamlet:
-    return "locality";
-  case PlaceType::Suburb:
-  case PlaceType::Neighbourhood:
-    return "suburb";
-  case PlaceType::Locality:
-  case PlaceType::IsolatedDwelling:
-    return "sublocality";
-  default:
-    break;
-  }
-
-  switch (adminLevel)
-  {
-  case AdminLevel::Two:
-    return "country";
-  case AdminLevel::Four:
-    return "region";
-  case AdminLevel::Six:
-    return "subregion";
-  default:
-    break;
-  }
-
-  return "";
-}
-
-size_t RegionWithData::GetWeight() const
-{
-  auto const adminLevel = GetAdminLevel();
-  auto const placeType = GetPlaceType();
-
-  switch (placeType)
-  {
-  case PlaceType::City:
-  case PlaceType::Town:
-  case PlaceType::Village:
-  case PlaceType::Hamlet:
-    return 3;
-  case PlaceType::Suburb:
-  case PlaceType::Neighbourhood:
-    return 2;
-  case PlaceType::Locality:
-  case PlaceType::IsolatedDwelling:
-    return 1;
-  default:
-    break;
-  }
-
-  switch (adminLevel)
-  {
-  case AdminLevel::Two:
-    return 6;
-  case AdminLevel::Four:
-    return 5;
-  case AdminLevel::Six:
-    return 4;
-  default:
-    break;
-  }
-
-  return 0;
-}
 }  // namespace regions
 }  // namespace generator
diff --git a/generator/regions/region_base.hpp b/generator/regions/region_base.hpp
index 0143e2292f..2198b28f0d 100644
--- a/generator/regions/region_base.hpp
+++ b/generator/regions/region_base.hpp
@@ -44,29 +44,18 @@ protected:
 class RegionWithData
 {
 public:
-  static uint8_t constexpr kNoRank = 0;
-
   RegionWithData(RegionDataProxy const & regionData) : m_regionData(regionData) {}
 
   base::GeoObjectId GetId() const;
   bool HasIsoCode() const;
   std::string GetIsoCode() const;
 
-  // Absolute rank values do not mean anything. But if the rank of the first object is more than the
-  // rank of the second object, then the first object is considered more nested.
-  uint8_t GetRank() const;
-  std::string GetLabel() const;
-  size_t GetWeight() const;
-
   AdminLevel GetAdminLevel() const { return m_regionData.GetAdminLevel(); }
   PlaceType GetPlaceType() const { return m_regionData.GetPlaceType(); }
 
   void SetAdminLevel(AdminLevel adminLevel) { m_regionData.SetAdminLevel(adminLevel); }
   void SetPlaceType(PlaceType placeType) { m_regionData.SetPlaceType(placeType); }
 
-  bool HasAdminLevel() const { return m_regionData.HasAdminLevel(); }
-  bool HasPlaceType() const { return m_regionData.HasPlaceType(); }
-
   RegionDataProxy const & GetRegionData() const { return m_regionData; }
 
 protected:
diff --git a/generator/regions/regions.cpp b/generator/regions/regions.cpp
index 8595b1afc0..c925855f8d 100644
--- a/generator/regions/regions.cpp
+++ b/generator/regions/regions.cpp
@@ -79,9 +79,9 @@ private:
       LOG(LINFO, ("Processing country", name));
 
       auto jsonPolicy = JsonPolicy{m_verbose};
-      Visit(tree, [&](auto && node) {
+      ForEachLevelPath(tree, [&](auto && path) {
+        auto const & node = path.back();
         auto const id = node->GetData().GetId();
-        auto const path = MakeNodePath(node);
         regionsKv << static_cast<int64_t>(id.GetEncodedId()) << " " << jsonPolicy.ToString(path) << "\n";
         ++countIds;
         if (!setIds.insert(id).second)
@@ -136,9 +136,12 @@ private:
   void FilterRegions(RegionsBuilder::Regions & regions)
   {
     auto const pred = [](Region const & region) {
-      auto const & label = region.GetLabel();
       auto const & name = region.GetName();
-      return label.empty() || name.empty();
+      if (name.empty())
+        return false;
+
+      auto const level = RegionsBuilder::GetLevel(region);
+      return level != PlaceLevel::Unknown;
     };
 
     base::EraseIf(regions, pred);
diff --git a/generator/regions/regions_builder.cpp b/generator/regions/regions_builder.cpp
index 02deee9e8c..21637cae28 100644
--- a/generator/regions/regions_builder.cpp
+++ b/generator/regions/regions_builder.cpp
@@ -65,13 +65,14 @@ RegionsBuilder::StringsList RegionsBuilder::GetCountryNames() const
 Node::PtrList RegionsBuilder::MakeSelectedRegionsByCountry(Region const & country,
                                                            Regions const & allRegions)
 {
-  Regions regionsInCountry;
-  auto filterCopy = [&country] (const Region & r) { return country.ContainsRect(r); };
-  std::copy_if(std::begin(allRegions), std::end(allRegions),
-               std::back_inserter(regionsInCountry), filterCopy);
+  std::vector<LevelRegion> regionsInCountry{{PlaceLevel::Country, country}};
+  for (auto const & region : allRegions)
+  {
+    if (country.ContainsRect(region))
+      regionsInCountry.emplace_back(GetLevel(region), region);
+  }
 
-  regionsInCountry.emplace_back(country);
-  auto const comp = [](const Region & l, const Region & r) {
+  auto const comp = [](LevelRegion const & l, LevelRegion const & r) {
     auto const lArea = l.GetArea();
     auto const rArea = r.GetArea();
     return lArea != rArea ? lArea > rArea : l.GetRank() < r.GetRank();
@@ -99,7 +100,7 @@ Node::Ptr RegionsBuilder::BuildCountryRegionTree(Region const & country,
     {
       auto const & currRegion = (*itCurr)->GetData();
       if (currRegion.Contains(firstRegion) ||
-          (firstRegion.GetWeight() < currRegion.GetWeight() &&
+          (GetWeight(firstRegion) < GetWeight(currRegion) &&
            currRegion.Contains(firstRegion.GetCenter()) &&
            currRegion.CalculateOverlapPercentage(firstRegion) > 50.0))
       {
@@ -152,5 +153,75 @@ std::vector<Node::Ptr> RegionsBuilder::BuildCountryRegionTrees(RegionsBuilder::R
                  std::back_inserter(res), [](auto & f) { return f.get(); });
   return res;
 }
+
+// static
+PlaceLevel RegionsBuilder::GetLevel(Region const & region)
+{
+  switch (region.GetPlaceType())
+  {
+  case PlaceType::City:
+  case PlaceType::Town:
+  case PlaceType::Village:
+  case PlaceType::Hamlet:
+    return PlaceLevel::Locality;
+  case PlaceType::Suburb:
+  case PlaceType::Neighbourhood:
+    return PlaceLevel::Suburb;
+  case PlaceType::Locality:
+  case PlaceType::IsolatedDwelling:
+    return PlaceLevel::Sublocality;
+  case PlaceType::Unknown:
+    break;
+  }
+
+  switch (region.GetAdminLevel())
+  {
+  case AdminLevel::Two:
+    return PlaceLevel::Country;
+  case AdminLevel::Four:
+    return PlaceLevel::Region;
+  case AdminLevel::Six:
+    return PlaceLevel::Subregion;
+  default:
+    break;
+  }
+
+  return PlaceLevel::Unknown;
+}
+
+// static
+size_t RegionsBuilder::GetWeight(Region const & region)
+{
+  switch (region.GetPlaceType())
+  {
+  case PlaceType::City:
+  case PlaceType::Town:
+  case PlaceType::Village:
+  case PlaceType::Hamlet:
+    return 3;
+  case PlaceType::Suburb:
+  case PlaceType::Neighbourhood:
+    return 2;
+  case PlaceType::Locality:
+  case PlaceType::IsolatedDwelling:
+    return 1;
+  case PlaceType::Unknown:
+    break;
+  }
+
+  switch (region.GetAdminLevel())
+  {
+  case AdminLevel::Two:
+    return 6;
+  case AdminLevel::Four:
+    return 5;
+  case AdminLevel::Six:
+    return 4;
+  default:
+    break;
+  }
+
+  return 0;
+}
 }  // namespace regions
 }  // namespace generator
diff --git a/generator/regions/regions_builder.hpp b/generator/regions/regions_builder.hpp
index aae712c2c1..1bed2f3c7a 100644
--- a/generator/regions/regions_builder.hpp
+++ b/generator/regions/regions_builder.hpp
@@ -30,6 +30,10 @@ public:
   Regions const & GetCountries() const;
   StringsList GetCountryNames() const;
   void ForEachNormalizedCountry(NormalizedCountryFn fn);
+
+  static PlaceLevel GetLevel(Region const & region);
+  static size_t GetWeight(Region const & region);
+
 private:
   static Node::PtrList MakeSelectedRegionsByCountry(Region const & country,
                                                     Regions const & allRegions);
diff --git a/generator/regions/regions_fixer.cpp b/generator/regions/regions_fixer.cpp
index bca79bf486..7bab7cdac6 100644
--- a/generator/regions/regions_fixer.cpp
+++ b/generator/regions/regions_fixer.cpp
@@ -35,11 +35,12 @@ public:
 
   bool CityExistsAsRegion(City const & city)
   {
+    auto const cityType = city.GetPlaceType();
     auto const range = m_nameRegionMap.equal_range(city.GetName());
     for (auto it = range.first; it != range.second; ++it)
     {
       Region const & r = it->second;
-      if (city.GetRank() == r.GetRank() && r.Contains(city))
+      if (r.GetPlaceType() == cityType && r.Contains(city))
         return true;
     }
 
@@ -66,7 +67,7 @@ public:
     for (auto const & cityKeyValue : m_pointCitiesMap)
     {
       auto const & city = cityKeyValue.second;
-      if (!regionsChecker.CityExistsAsRegion(city) && NeedCity(city))
+      if (NeedCity(city) && !regionsChecker.CityExistsAsRegion(city))
       {
         approximatedRegions.push_back(Region(city));
         ++countOfFixedRegions;
@@ -82,7 +83,8 @@ public:
 private:
   bool NeedCity(const City & city)
   {
-    return city.HasPlaceType() && city.GetPlaceType() != PlaceType::Locality;
+    auto const placeType = city.GetPlaceType();
+    return placeType >= PlaceType::City && placeType != PlaceType::Locality;
   }
 
   RegionsBuilder::Regions m_regions;
diff --git a/generator/regions/to_string_policy.cpp b/generator/regions/to_string_policy.cpp
index a9203aade6..a06bd680c4 100644
--- a/generator/regions/to_string_policy.cpp
+++ b/generator/regions/to_string_policy.cpp
@@ -15,9 +15,7 @@ namespace regions
 {
 std::string JsonPolicy::ToString(NodePath const & path) const
 {
-  auto const & country = path.front()->GetData();
   auto const & main = path.back()->GetData();
-
   auto geometry = base::NewJSONObject();
   ToJSONObject(*geometry, "type", "Point");
   auto coordinates = base::NewJSONArray();
@@ -29,23 +27,23 @@ std::string JsonPolicy::ToString(NodePath const & path) const
 
   auto localeEn = base::NewJSONObject();
   auto address = base::NewJSONObject();
-  auto const mainLabel = main.GetLabel();
   boost::optional<int64_t> pid;
   for (auto const & p : path)
   {
-
     auto const & region = p->GetData();
-    auto const label = region.GetLabel();
+    CHECK(region.GetLevel() != PlaceLevel::Unknown, ());
+    auto const label = GetLabel(region.GetLevel());
+    CHECK(label, ());
     ToJSONObject(*address, label, region.GetName());
     if (m_extendedOutput)
     {
-      ToJSONObject(*address, label + "_i", DebugPrint(region.GetId()));
-      ToJSONObject(*address, label + "_a", region.GetArea());
-      ToJSONObject(*address, label + "_r", region.GetRank());
+      ToJSONObject(*address, std::string{label} + "_i", DebugPrint(region.GetId()));
+      ToJSONObject(*address, std::string{label} + "_a", region.GetArea());
+      ToJSONObject(*address, std::string{label} + "_r", region.GetRank());
     }
 
     ToJSONObject(*localeEn, label, region.GetEnglishOrTransliteratedName());
-    if (label != mainLabel)
+    if (!pid && region.GetId() != main.GetId())
       pid = static_cast<int64_t>(region.GetId().GetEncodedId());
   }
 
@@ -62,6 +60,7 @@ std::string JsonPolicy::ToString(NodePath const & path) const
   else
     ToJSONObject(*properties, "pid", base::NewJSONNull());
 
+  auto const & country = path.front()->GetData();
   if (country.HasIsoCode())
     ToJSONObject(*properties, "code", country.GetIsoCode());