diff options
author | Konstantin Käfer <mail@kkaefer.com> | 2016-03-08 13:59:31 +0100 |
---|---|---|
committer | Konstantin Käfer <mail@kkaefer.com> | 2016-05-10 14:50:56 +0200 |
commit | ecc8e018faff02e8f0bb2a6c11db361f454c555e (patch) | |
tree | 0aefbbfd24263e0cbc711a2a081ae9fc4aed5147 | |
parent | 82ebcfa14e2eb8d13c3eca9c2eb5adaa229f4182 (diff) | |
download | qtlocation-mapboxgl-ecc8e018faff02e8f0bb2a6c11db361f454c555e.tar.gz |
[core] add algorithm for detecting whether an ordered map contains covering children
-rw-r--r-- | src/mbgl/algorithm/covered_by_children.hpp | 34 | ||||
-rw-r--r-- | test/algorithm/covered_by_children.cpp | 61 | ||||
-rw-r--r-- | test/test.gypi | 2 | ||||
-rw-r--r-- | test/tile/tile_id.cpp | 2 |
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> |