[geometry] Clarified the z-order interpretation in CellId.

2 files changed, 88 insertions, 24 deletions

diff --git a/geometry/cellid.hpp b/geometry/cellid.hpp
index 2af9231d7c..5f7d9964ac 100644
--- a/geometry/cellid.hpp
+++ b/geometry/cellid.hpp
@@ -51,7 +51,7 @@ public:
   {
     ASSERT(IsValid(), (m_bits, m_level));
     ASSERT_GREATER_OR_EQUAL(m_level, level, ());
-    return CellId(m_bits >> ((m_level - level) << 1), level);
+    return CellId(m_bits >> (2 * (m_level - level)), level);
   }
 
   CellId Child(int8_t c) const
@@ -203,8 +203,8 @@ public:
   {
     bool operator()(CellId<DEPTH_LEVELS> const & id1, CellId<DEPTH_LEVELS> const & id2) const
     {
-      int64_t const n1 = id1.ToInt64LevelZOrder(DEPTH_LEVELS);
-      int64_t const n2 = id2.ToInt64LevelZOrder(DEPTH_LEVELS);
+      int64_t const n1 = id1.ToInt64ZOrder(DEPTH_LEVELS);
+      int64_t const n2 = id2.ToInt64ZOrder(DEPTH_LEVELS);
       ASSERT_EQUAL(n1 < n2, id1.ToString() < id2.ToString(), (id1, id2));
       return n1 < n2;
     }
@@ -214,25 +214,39 @@ public:
   // Numbering
 
   // Default ToInt64().
-  int64_t ToInt64(int depth) const { return ToInt64LevelZOrder(depth); }
+  int64_t ToInt64(int depth) const { return ToInt64ZOrder(depth); }
 
   // Default FromInt64().
-  static CellId FromInt64(int64_t v, int depth) { return FromInt64LevelZOrder(v, depth); }
+  static CellId FromInt64(int64_t v, int depth) { return FromInt64ZOrder(v, depth); }
 
-  // Level order, numbering by Z-curve.
-  int64_t ToInt64LevelZOrder(int depth) const
+  // Returns the 1-based number this cell would get in the Z-curve ordering (pre-order
+  // traversal of the quadtree) of all the cells in the tree of depth |depth|.
+  // The tree of one vertex is assumed to have depth 1.
+  int64_t ToInt64ZOrder(int depth) const
   {
     ASSERT(0 < depth && depth <= DEPTH_LEVELS, (m_bits, m_level, depth));
     ASSERT(IsValid(), (m_bits, m_level));
 
     if (m_level >= depth)
-      return AncestorAtLevel(depth - 1).ToInt64(depth);
+      return AncestorAtLevel(depth - 1).ToInt64ZOrder(depth);
 
     uint64_t bits = m_bits;
     uint64_t res = 0;
-    for (int i = 0; i <= m_level; ++i, bits >>= 2)
+    // When counting, group the nodes by their level.
+    // All nodes to the left of the current one at its level
+    // and, for every ancestor, all nodes to the left of the ancestor
+    // at the ancestor's level will show up earlier during the traversal.
+    // All ancestors are visited before the current node, so add +1 for them.
+    // The result is 1-based, so add +1 for the node itself too.
+    for (int i = 0; i <= m_level; ++i)
+    {
       res += bits + 1;
+      bits >>= 2;
+    }
 
+    // By the same reasoning, if the children of every node are ordered
+    // left to right, then all nodes at deeper levels that
+    // are strictly to the left will be visited before the current one.
     bits = m_bits;
     for (int i = m_level + 1; i < depth; ++i)
     {
@@ -245,8 +259,10 @@ public:
     return static_cast<int64_t>(res);
   }
 
-  // Level order, numbering by Z-curve.
-  static CellId FromInt64LevelZOrder(int64_t v, int depth)
+  // Returns the CellId with the 1-based number |v| in the Z-curve ordering (pre-order
+  // traversal of the quadtree) of all the cells in the tree of depth |depth|.
+  // The tree of one vertex is assumed to have depth 1.
+  static CellId FromInt64ZOrder(int64_t v, int depth)
   {
     ASSERT_GREATER(v, 0, ());
     ASSERT(0 < depth && depth <= DEPTH_LEVELS, (v, depth));
@@ -266,6 +282,9 @@ public:
   }
 
 private:
+  // Returns the total number of nodes in the tree of depth |depth|.
+  // The tree of one vertex is assumed to have depth 1.
+  // The first few values are 1, 5, 21, 85.
   static uint64_t TreeSizeForDepth(int depth)
   {
     ASSERT(0 < depth && depth <= DEPTH_LEVELS, (depth));
diff --git a/geometry/geometry_tests/cellid_test.cpp b/geometry/geometry_tests/cellid_test.cpp
index 7c27a10304..564561c5b2 100644
--- a/geometry/geometry_tests/cellid_test.cpp
+++ b/geometry/geometry_tests/cellid_test.cpp
@@ -2,19 +2,21 @@
 
 #include "geometry/cellid.hpp"
 
+#include "base/logging.hpp"
+
 #include <algorithm>
 #include <string>
 #include <vector>
 
 using namespace std;
 
-UNIT_TEST(CellID_Parent)
+UNIT_TEST(CellId_Parent)
 {
   TEST_EQUAL(m2::CellId<3>("1").Parent(), m2::CellId<3>(""), ());
   TEST_EQUAL(m2::CellId<4>("032").Parent(), m2::CellId<4>("03"), ());
 }
 
-UNIT_TEST(CellID_AncestorAtLevel)
+UNIT_TEST(CellId_AncestorAtLevel)
 {
   TEST_EQUAL(m2::CellId<3>("1").AncestorAtLevel(0), m2::CellId<3>(""), ());
   TEST_EQUAL(m2::CellId<4>("032").AncestorAtLevel(2), m2::CellId<4>("03"), ());
@@ -150,7 +152,7 @@ UNIT_TEST(CellId_SubTreeSize)
   TEST_EQUAL(m2::CellId<3>("").SubTreeSize(3), 21, ());
 }
 
-UNIT_TEST(CellID_LessQueueOrder)
+UNIT_TEST(CellId_LessQueueOrder)
 {
   vector<string> v;
   v.push_back("0");
@@ -163,7 +165,7 @@ UNIT_TEST(CellID_LessQueueOrder)
   vector<string> e = v;
   do
   {
-    vector<m2::CellId<4> > tst, exp;
+    vector<m2::CellId<4>> tst, exp;
     for (size_t i = 0; i < v.size(); ++i)
     {
       tst.push_back(m2::CellId<4>(e[i]));
@@ -174,7 +176,7 @@ UNIT_TEST(CellID_LessQueueOrder)
   } while (next_permutation(e.begin(), e.end()));
 }
 
-UNIT_TEST(CellID_LessStackOrder)
+UNIT_TEST(CellId_LessStackOrder)
 {
   vector<string> v;
   v.push_back("0");
@@ -187,7 +189,7 @@ UNIT_TEST(CellID_LessStackOrder)
   vector<string> e = v;
   do
   {
-    vector<m2::CellId<4> > tst, exp;
+    vector<m2::CellId<4>> tst, exp;
     for (size_t i = 0; i < v.size(); ++i)
     {
       tst.push_back(m2::CellId<4>(e[i]));
@@ -198,12 +200,55 @@ UNIT_TEST(CellID_LessStackOrder)
   } while (next_permutation(e.begin(), e.end()));
 }
 
-UNIT_TEST(CellID_IsStringValid)
+UNIT_TEST(CellId_IsStringValid)
+{
+  using Id = m2::CellId<9>;
+  TEST(Id::IsCellId("0123132"), ());
+  TEST(Id::IsCellId(""), ());
+  TEST(!Id::IsCellId("-1332"), ());
+  TEST(!Id::IsCellId("023."), ());
+  TEST(!Id::IsCellId("121832"), ());
+}
+
+UNIT_TEST(CellId_ToAndFromInt64ZOrder)
 {
-  typedef m2::CellId<9> TId;
-  TEST( TId::IsCellId("0123132"), () );
-  TEST( TId::IsCellId(""), () );
-  TEST( !TId::IsCellId("-1332"), () );
-  TEST( !TId::IsCellId("023."), () );
-  TEST( !TId::IsCellId("121832"), () );
+  int const kMaxDepth = 4;
+  using Id = m2::CellId<kMaxDepth>;
+  for (int depth = 1; depth <= kMaxDepth; ++depth)
+  {
+    uint64_t const treeSize = ((uint64_t{1} << (2 * depth)) - 1) / 3;
+    LOG(LINFO, ("Depth =", depth, " TreeSize =", treeSize));
+    for (uint64_t id = 1; id <= treeSize; ++id)
+    {
+      auto const cell = Id::FromInt64ZOrder(id, depth);
+      TEST_EQUAL(id, cell.ToInt64ZOrder(depth), ());
+    }
+  }
+
+  vector<string> const atDepth3 = {
+    "",
+    "0",
+    "00",
+    "01",
+    "02",
+    "03",
+    "1",
+    "10",
+    "11",
+    "12",
+    "13",
+    "2",
+    "20",
+    "21",
+    "22",
+    "23",
+    "3",
+    "30",
+    "31",
+    "32",
+    "33",
+  };
+
+  for (uint64_t id = 1; id <= atDepth3.size(); ++id)
+    TEST_EQUAL(Id::FromInt64(id, 3), Id(atDepth3[id - 1]), ());
 }