[core] add algorithm for detecting whether an ordered map contains covering children

4 files changed, 98 insertions, 1 deletions

diff --git a/src/mbgl/algorithm/covered_by_children.hpp b/src/mbgl/algorithm/covered_by_children.hpp
new file mode 100644
index 0000000000..766a67acac
--- /dev/null
+++ b/src/mbgl/algorithm/covered_by_children.hpp
@@ -0,0 +1,34 @@
+#ifndef MBGL_ALGORITHM_COVERED_BY_CHILDREN
+#define MBGL_ALGORITHM_COVERED_BY_CHILDREN
+
+#include <mbgl/tile/tile_id.hpp>
+
+namespace mbgl {
+namespace algorithm {
+
+template <typename Iterator>
+bool coveredByChildren(const UnwrappedTileID& id, Iterator it, const Iterator& end) {
+    for (const auto& child : id.children()) {
+        it = std::lower_bound(it, end, child, [](auto& a, auto& b) { return std::get<0>(a) < b; });
+        if (it == end) {
+            return false;
+        } else if (std::get<0>(*it) != child) {
+            return coveredByChildren(child, it, end);
+        }
+    }
+
+    // We looked at all four immediate children and verified that they're covered.
+    return true;
+}
+
+template <typename Container>
+bool coveredByChildren(const UnwrappedTileID& id, const Container& container) {
+    return coveredByChildren(
+        id, container.upper_bound(id),
+        container.lower_bound(UnwrappedTileID{ static_cast<int16_t>(id.wrap + 1), { 0, 0, 0 } }));
+}
+
+} // namespace algorithm
+} // namespace mbgl
+
+#endif
\ No newline at end of file
diff --git a/test/algorithm/covered_by_children.cpp b/test/algorithm/covered_by_children.cpp
new file mode 100644
index 0000000000..b2a219bf29
--- /dev/null
+++ b/test/algorithm/covered_by_children.cpp
@@ -0,0 +1,61 @@
+#include <mbgl/test/util.hpp>
+
+#include <mbgl/algorithm/covered_by_children.hpp>
+
+#include <map>
+
+using namespace mbgl;
+
+using List = std::map<UnwrappedTileID, bool>;
+
+TEST(CoveredByChildren, NotCovered) {
+    const List list1;
+    EXPECT_FALSE(algorithm::coveredByChildren(UnwrappedTileID{ 0, 0, 0 }, list1));
+
+    const List list2{
+        { UnwrappedTileID{ 0, 0, 0 }, true },
+        // 3 out of 4 child tiles
+        { UnwrappedTileID{ 1, 0, 0 }, true },
+        { UnwrappedTileID{ 1, 0, 1 }, true },
+        // missing 1/1/0
+        { UnwrappedTileID{ 1, 1, 1 }, true },
+    };
+    EXPECT_FALSE(algorithm::coveredByChildren(UnwrappedTileID{ 0, 0, 0 }, list2));
+
+    const List list3{
+        { UnwrappedTileID{ 0, 0, 0 }, true },
+        // all four child tiles, with with a different wrap index
+        { UnwrappedTileID{ 1, { 1, 0, 0 } }, true },
+        { UnwrappedTileID{ 1, { 1, 0, 1 } }, true },
+        { UnwrappedTileID{ 1, { 1, 1, 0 } }, true },
+        { UnwrappedTileID{ 1, { 1, 1, 1 } }, true },
+    };
+    EXPECT_FALSE(algorithm::coveredByChildren(UnwrappedTileID{ 0, 0, 0 }, list3));
+}
+
+TEST(CoveredByChildren, Covered) {
+    const List list1{
+        { UnwrappedTileID{ 0, 0, 0 }, true },
+        // all four child tiles
+        { UnwrappedTileID{ 1, 0, 0 }, true },
+        { UnwrappedTileID{ 1, 0, 1 }, true },
+        { UnwrappedTileID{ 1, 1, 0 }, true },
+        { UnwrappedTileID{ 1, 1, 1 }, true },
+    };
+    EXPECT_TRUE(algorithm::coveredByChildren(UnwrappedTileID{ 0, 0, 0 }, list1));
+
+    const List list2{
+        { UnwrappedTileID{ 0, 0, 0 }, true },
+        // missing 1/0/0
+        { UnwrappedTileID{ 1, 0, 1 }, true },
+        { UnwrappedTileID{ 1, 1, 0 }, true },
+        { UnwrappedTileID{ 1, 1, 1 }, true },
+        { UnwrappedTileID{ 2, 0, 0 }, true },
+        { UnwrappedTileID{ 2, 0, 1 }, true },
+        { UnwrappedTileID{ 2, 1, 0 }, true },
+        { UnwrappedTileID{ 2, 1, 1 }, true },
+    };
+    EXPECT_TRUE(algorithm::coveredByChildren(UnwrappedTileID{ 0, 0, 0 }, list2));
+    EXPECT_TRUE(algorithm::coveredByChildren(UnwrappedTileID{ 1, 0, 0 }, list2));
+    EXPECT_FALSE(algorithm::coveredByChildren(UnwrappedTileID{ 2, 0, 0 }, list2));
+}
diff --git a/test/test.gypi b/test/test.gypi
index 7c1d48f2fa..4635c888c3 100644
--- a/test/test.gypi
+++ b/test/test.gypi
@@ -34,6 +34,8 @@
         'util/token.cpp',
         'util/work_queue.cpp',
 
+        'algorithm/covered_by_children.cpp',
+
         'api/annotations.cpp',
         'api/api_misuse.cpp',
         'api/repeated_render.cpp',
diff --git a/test/tile/tile_id.cpp b/test/tile/tile_id.cpp
index 145ce93f49..e5a1403d20 100644
--- a/test/tile/tile_id.cpp
+++ b/test/tile/tile_id.cpp
@@ -1,4 +1,4 @@
-#include "../fixtures/util.hpp"
+#include <mbgl/test/util.hpp>
 
 #include <mbgl/tile/tile_id.hpp>