Merge pull request #11007 from cc-engineering/generator.regions.built-geometry

[generator:regions] Generate features with build geometry

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