[bookmarks] Review fixes. MAPSME-14916

4 files changed, 79 insertions, 59 deletions

diff --git a/kml/kml_tests/minzoom_quadtree_tests.cpp b/kml/kml_tests/minzoom_quadtree_tests.cpp
index 9f01f072b0..57e32b4e4f 100644
--- a/kml/kml_tests/minzoom_quadtree_tests.cpp
+++ b/kml/kml_tests/minzoom_quadtree_tests.cpp
@@ -13,7 +13,7 @@
 
 namespace
 {
-constexpr double kEps = std::numeric_limits<double>::epsilon();
+double constexpr kEps = std::numeric_limits<double>::epsilon();
 
 m2::PointD MakeGlobalPoint(double x, double y)
 {
@@ -48,7 +48,7 @@ UNIT_TEST(Kml_MinzoomQuadtree_PopulationGrowthRate)
       ++populationCount[zoom];
     };
     minZoomQuadtree.SetMinZoom(kCountPerTile, scales::GetUpperStyleScale(), incZoomPopulation);
-    TEST_EQUAL(populationCount.size(), kMaxDepth + 1, ());
+    TEST_EQUAL(populationCount.size(), kMaxDepth + 1, (populationCount));
 
     auto p = populationCount.cbegin();
     ASSERT(p != populationCount.cend(), ());
@@ -58,32 +58,32 @@ UNIT_TEST(Kml_MinzoomQuadtree_PopulationGrowthRate)
       partialSums.push_back(partialSums.back() + p->second);
     TEST_EQUAL(partialSums.front(), 1, ());
     TEST_EQUAL(partialSums.back(), (1 << (kMaxDepth * 2)), ());
-    auto const isGrowthExponential = [](size_t lhs, size_t rhs) { return rhs == 4 * lhs; };
-    TEST(std::is_sorted(partialSums.cbegin(), partialSums.cend(), isGrowthExponential),
-         (partialSums));
+    auto const isGrowthExponential = [](size_t lhs, size_t rhs) { return rhs != 4 * lhs; };
+    TEST(std::adjacent_find(partialSums.cbegin(), partialSums.cend(), isGrowthExponential) ==
+         partialSums.cend(), (partialSums));
   }
 
-  std::mt19937 gen(0);
+  std::mt19937 g(0);
 
-  auto const generate_canonical = [&gen]
+  auto const gen = [&g]
   {
-    return std::generate_canonical<double, std::numeric_limits<uint32_t>::digits>(gen);
+    return std::generate_canonical<double, std::numeric_limits<uint32_t>::digits>(g);
   };
 
   for (int i = 0; i < 5; ++i)
   {
     kml::MinZoomQuadtree<double /* rank */, std::less<double>> minZoomQuadtree{{} /* less */};
 
-    size_t const kTotalCount = 1 + gen() % 10000;
+    size_t const kTotalCount = 1 + g() % 10000;
     for (size_t i = 0; i < kTotalCount; ++i)
     {
-      auto const x = generate_canonical();
-      auto const y = generate_canonical();
-      auto const rank = generate_canonical();
+      auto const x = gen();
+      auto const y = gen();
+      auto const rank = gen();
       minZoomQuadtree.Add(MakeGlobalPoint(x, y), rank);
     }
 
-    double const kCountPerTile = 1.0 + kTotalCount * generate_canonical() / 2.0;
+    double const kCountPerTile = 1.0 + kTotalCount * gen() / 2.0;
     std::map<int /* zoom */, size_t> populationCount;
     auto const incZoomPopulation = [&](double & /* rank */, int zoom) { ++populationCount[zoom]; };
     minZoomQuadtree.SetMinZoom(kCountPerTile, scales::GetUpperStyleScale(), incZoomPopulation);
@@ -150,7 +150,7 @@ UNIT_TEST(Kml_MinzoomQuadtree_MaxZoom)
   };
   int const kMaxZoom = 4;
   minZoomQuadtree.SetMinZoom(kCountPerTile, kMaxZoom, incZoomPopulation);
-  TEST_EQUAL(populationCount.size(), kMaxZoom, ());
+  TEST_EQUAL(populationCount.size(), kMaxZoom, (populationCount));
 
   auto p = populationCount.cbegin();
   ASSERT(p != populationCount.cend(), ());
@@ -160,8 +160,8 @@ UNIT_TEST(Kml_MinzoomQuadtree_MaxZoom)
     partialSums.push_back(partialSums.back() + p->second);
   TEST_EQUAL(partialSums.front(), 1, ());
   TEST_EQUAL(partialSums.back(), (1 << (kMaxDepth * 2)), ());
-  auto const isGrowthExponential = [](size_t lhs, size_t rhs) { return rhs == 4 * lhs; };
-  TEST(std::is_sorted(partialSums.cbegin(), std::prev(partialSums.cend()), isGrowthExponential),
-       (partialSums));
+  auto const isGrowthExponential = [](size_t lhs, size_t rhs) { return rhs != 4 * lhs; };
+  TEST(std::adjacent_find(partialSums.cbegin(), std::prev(partialSums.cend()), isGrowthExponential) ==
+       std::prev(partialSums.cend()), (partialSums));
   TEST_LESS_OR_EQUAL(4 * *std::prev(partialSums.cend(), 2), partialSums.back(), ());
 }
diff --git a/kml/minzoom_quadtree.hpp b/kml/minzoom_quadtree.hpp
index 91ae6e5a1e..36715bc599 100644
--- a/kml/minzoom_quadtree.hpp
+++ b/kml/minzoom_quadtree.hpp
@@ -1,4 +1,5 @@
 #pragma once
+
 #include "kml/types.hpp"
 
 #include "indexer/scales.hpp"
@@ -20,18 +21,20 @@ namespace kml
 {
 // Builds linear quadtree of input values using coordinates provided
 // then walks through the quadtree elevating minZoom of those values
-// which are greater (in sense of Less) then others on a quadtree level.
+// which are greater (in sense of Less) than others at the same
+// quadtree level.
 // To encode each quadtree level uses two bits. One from ordinate and
 // another from abscissa. Both components are mapped to a coordinate
-// system that uses the full range of uint32_t inside the bounding (square) box.
+// system that uses the full range of uint32_t inside the bounding
+// (squared) box.
 template <typename Value, typename Less>
 class MinZoomQuadtree
 {
 public:
   MinZoomQuadtree(Less const & less) : m_less{less} {}
 
-  template <typename ValueType>
-  void Add(m2::PointD const & point, ValueType && value) { m_quadtree.push_back({point, std::forward<ValueType>(value)}); }
+  template <typename V>
+  void Add(m2::PointD const & point, V && value) { m_quadtree.emplace_back(point, std::forward<V>(value)); }
 
   void Clear() { m_quadtree.clear(); }
 
@@ -49,60 +52,74 @@ public:
     for (auto const & elem : m_quadtree)
       bbox.Add(elem.m_point);
 
-    if (bbox.IsEmptyInterior())
+    if (!(bbox.SizeX() > 0.0 || bbox.SizeY() > 0.0))
       return;
 
-    auto spacing = std::max(bbox.SizeX() / mercator::Bounds::kRangeX,
-                            bbox.SizeY() / mercator::Bounds::kRangeY);
-    spacing *= std::sqrt(countPerTile);
-
+    // `spacing` is an characteristic interval between values on the map as if they spaced
+    // uniformly across the map providing required density (i.e. "count per tile area").
+    double spacing = std::min(mercator::Bounds::kRangeX / bbox.SizeX(),
+                              mercator::Bounds::kRangeY / bbox.SizeY());
+    spacing /= std::sqrt(countPerTile);
+
+    // `spacing` value decomposed into a normalized fraction and an integral power of two.
+    // Normalized fraction `scale` (in [1, 2)) used to slightly enlarge bounding box.
+    // Integral power of two `baseZoom` is biased exponent of inverse value. It has
+    // a meaning exactly the same as the other "zoomLevel"s in the project.
+    // Scaling (enlarging) the size of bbox by `scale` is required so that one can
+    // set arbitrary values for `countPerTile`, not only powers of four.
     int baseZoom;
-    auto const scale = std::frexp(spacing, &baseZoom);
-    baseZoom = 1 - baseZoom;
+    double const scale = 2.0 * std::frexp(spacing, &baseZoom);
 
+    auto const setMaxZoom = [&](auto const treeBeg, auto const treeEnd)
+    {
+      auto const topRanked = std::max_element(treeBeg, treeEnd, [&](auto const & lhs, auto const & rhs)
+      {
+        return m_less(lhs.m_value, rhs.m_value);
+      });
+      auto const setMaxZoom = [&](auto & elem) { setMinZoom(elem.m_value, maxZoom); };
+      std::for_each(treeBeg, topRanked, setMaxZoom);
+      std::for_each(std::next(topRanked), treeEnd, setMaxZoom);
+      return &*topRanked;
+    };
     if (baseZoom >= maxZoom)
+    {
+      // At least one element is visible from lowest zoom level.
+      setMinZoom(setMaxZoom(m_quadtree.begin(), m_quadtree.end())->m_value, 1);
       return;
+    }
 
-    auto const size = std::max(bbox.SizeX(), bbox.SizeY()) / scale;
+    double const size = std::max(bbox.SizeX(), bbox.SizeY()) * scale;
     bbox.SetSizes(size, size);
 
     // Calculate coordinate along z-order curve.
     auto const [minX, minY] = bbox.LeftBottom();
-    auto const gridScale = std::numeric_limits<uint32_t>::max() / size;
+    double const gridScale = std::numeric_limits<uint32_t>::max() / size;
     for (auto & elem : m_quadtree)
     {
       auto const [x, y] = elem.m_point;
-      auto const gridX = static_cast<uint32_t>(std::trunc((x - minX) * gridScale));
-      auto const gridY = static_cast<uint32_t>(std::trunc((y - minY) * gridScale));
-      // Sacrifice one of 32 possible levels for simplicity of traversing.
-      elem.m_zCurveCoord = bits::BitwiseMerge(gridX, gridY) >> 2;
+      uint32_t const gridX = static_cast<uint32_t>(std::trunc((x - minX) * gridScale));
+      uint32_t const gridY = static_cast<uint32_t>(std::trunc((y - minY) * gridScale));
+      elem.m_zCurveCoord = bits::BitwiseMerge(gridX, gridY);
     }
 
     std::sort(m_quadtree.begin(), m_quadtree.end());
 
+    int constexpr depthMax = std::numeric_limits<uint32_t>::digits;
+    uint64_t constexpr firstLevelMask = uint64_t{0b11} << ((depthMax - 1) * 2);
     auto const traverse = [&](auto const & traverse, auto const treeBeg, auto const treeEnd,
-                              uint64_t treeLevelMask, int zoom) -> Element *
+                              int depth) -> Element *
     {
       if (treeBeg == treeEnd)
         return nullptr;
       if (std::next(treeBeg) == treeEnd)
         return &*treeBeg;
-      if (++zoom >= maxZoom)
-      {
-        auto const rankLess = [&](auto const & lhs, auto const & rhs) -> bool
-        {
-          return m_less(lhs.m_value, rhs.m_value);
-        };
-        auto const result = std::max_element(treeBeg, treeEnd, rankLess);
-        auto const setMaxZoom = [&](auto & elem) { setMinZoom(elem.m_value, maxZoom); };
-        std::for_each(treeBeg, result, setMaxZoom);
-        std::for_each(std::next(result), treeEnd, setMaxZoom);
-        return &*result;
-      }
+      int const zoom = baseZoom + depth;
+      if (zoom >= maxZoom)
+        return setMaxZoom(treeBeg, treeEnd);
 
       Element * topRanked = nullptr;
-      treeLevelMask >>= 2;
-      CHECK_NOT_EQUAL(treeLevelMask, 0, ());
+      CHECK_LESS_OR_EQUAL(depth, depthMax, ("Quadtree is too deep, try to decrease maxZoom", maxZoom));
+      uint64_t const treeLevelMask = firstLevelMask >> ((depth - 1) * 2);
       uint64_t const quadIncrement = treeLevelMask & (treeLevelMask >> 1);
       uint64_t quadIndex = 0;
       auto const quadMaskEqual = [&](auto const & elem) -> bool
@@ -114,7 +131,7 @@ public:
       {
         ASSERT(std::is_partitioned(quadBeg, treeEnd, quadMaskEqual), ());
         auto const quadEnd = std::partition_point(quadBeg, treeEnd, quadMaskEqual);
-        if (auto const elem = traverse(traverse, quadBeg, quadEnd, treeLevelMask, zoom))
+        if (auto const elem = traverse(traverse, quadBeg, quadEnd, depth + 1))
         {
           if (topRanked == nullptr)
             topRanked = elem;
@@ -129,9 +146,9 @@ public:
       ASSERT(quadBeg == treeEnd, ());
       return topRanked;
     };
-    auto const rootMask = uint64_t{0b11} << (std::numeric_limits<uint64_t>::digits - 2);
-    if (auto const elem = traverse(traverse, m_quadtree.begin(), m_quadtree.end(), rootMask, baseZoom))
-      setMinZoom(elem->m_value, 1);
+    // Root level is not encoded, so start depth from 1
+    if (auto const elem = traverse(traverse, m_quadtree.begin(), m_quadtree.end(), 1 /* depth */))
+      setMinZoom(elem->m_value, 1 /* zoom */);  // at least one element is visible from lowest zoom level
     else
       CHECK(false, (m_quadtree.size()));
   }
@@ -139,6 +156,12 @@ public:
 private:
   struct Element
   {
+    template <typename V>
+    Element(m2::PointD const & point, V && value)
+      : m_point{point}
+      , m_value{std::forward<V>(value)}
+    {}
+
     bool operator<(Element const & rhs) const { return m_zCurveCoord < rhs.m_zCurveCoord; }
 
     m2::PointD m_point;
diff --git a/kml/types.cpp b/kml/types.cpp
index bed680ad44..52501edb75 100644
--- a/kml/types.cpp
+++ b/kml/types.cpp
@@ -11,10 +11,7 @@ namespace kml
 void SetBookmarksMinZoom(FileData & fileData, double countPerTile, int maxZoom)
 {
   using ValueType = std::pair<BookmarkData *, int /* score */>;
-  auto const scoreLess = [](ValueType const & lhs, ValueType const & rhs) -> bool
-  {
-    return lhs.second < rhs.second;
-  };
+  auto const scoreLess = base::LessBy(&ValueType::second);
   MinZoomQuadtree<ValueType, decltype(scoreLess)> minZoomQuadtree{scoreLess};
   for (auto & bm : fileData.m_bookmarksData)
   {
diff --git a/kml/types_v8.hpp b/kml/types_v8.hpp
index b27d149ebb..299193b858 100644
--- a/kml/types_v8.hpp
+++ b/kml/types_v8.hpp
@@ -44,6 +44,8 @@ struct BookmarkDataV8
            m_compilations == data.m_compilations;
   }
 
+  bool operator!=(BookmarkDataV8 const & data) const { return !operator==(data); }
+
   BookmarkData ConvertToLatestVersion()
   {
     BookmarkData data;
@@ -65,8 +67,6 @@ struct BookmarkDataV8
     return data;
   }
 
-  bool operator!=(BookmarkDataV8 const & data) const { return !operator==(data); }
-
   // Unique id (it will not be serialized in text files).
   MarkId m_id = kInvalidMarkId;
   // Bookmark's name.