compute unique clip ids per tile, taking covering children into account

fixes #206
fixes #220
refs #229

1 files changed, 214 insertions, 268 deletions

diff --git a/test/clip_ids.cpp b/test/clip_ids.cpp
index f2e8be98bc..18ef9658e5 100644
--- a/test/clip_ids.cpp
+++ b/test/clip_ids.cpp
@@ -8,298 +8,244 @@
 
 using namespace mbgl;
 
-TEST(ClipIDs, ClipMasks) {
-    ASSERT_EQ(0, clipMask[0]);
-    ASSERT_EQ(0x80, clipMask[1]);
-    ASSERT_EQ(0xC0, clipMask[2]);
-    ASSERT_EQ(0xE0, clipMask[3]);
-    ASSERT_EQ(0xF0, clipMask[4]);
-    ASSERT_EQ(0xF8, clipMask[5]);
-    ASSERT_EQ(0xFC, clipMask[6]);
-    ASSERT_EQ(0xFE, clipMask[7]);
-    ASSERT_EQ(0xFF, clipMask[8]);
+template <typename T> void generate(const T &sources) {
+    ClipIDGenerator generator;
+
+    for (size_t j = 0; j < sources.size(); j++) {
+        std::forward_list<Tile *> tile_ptrs;
+        std::transform(sources[j].begin(), sources[j].end(), std::front_inserter(tile_ptrs), [](const std::shared_ptr<Tile> &tile) { return tile.get(); });
+        generator.update(tile_ptrs);
+    }
 }
 
+template <typename T> void print(const T &sources) {
+    for (size_t j = 0; j < sources.size(); j++) {
+        for (size_t i = 0; i < sources[j].size(); i++) {
+            std::cout << "    ASSERT_EQ(ClipID(\"" << sources[j][i]->clip.mask << "\", \"" << sources[j][i]->clip.reference << "\"), sources[" << j << "][" << i << "]->clip);\n";
+        }
+    }
+}
 
 TEST(ClipIDs, ParentAndFourChildren) {
-    std::array<std::unique_ptr<Tile>, 5> tiles {{
-        std::make_unique<Tile>(Tile::ID { 1, 0, 0 }), // 1/0/0: 11000000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, 0, 1 }), // 1/0/1: 11100000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, 1, 0 }), // 1/1/0: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, 1, 1 }), // 1/1/1: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 0, 0, 0 }), // 0/0/0: 10000000 (1)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[4]->clip.mask); ASSERT_EQ(1, tiles[4]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 1, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 0, 1 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 0, 0, 0 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][4]->clip);
 }
 
 TEST(ClipIDs, ParentAndFourChildrenNegative) {
-    std::array<std::unique_ptr<Tile>, 5> tiles {{
-        std::make_unique<Tile>(Tile::ID { 1, -2, 0 }), // 1/0/0: 11000000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, -2, 1 }), // 1/0/1: 11100000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, -1, 0 }), // 1/1/0: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 1, -1, 1 }), // 1/1/1: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 0, -1, 0 }), // 0/0/0: 10000000 (1)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[4]->clip.mask); ASSERT_EQ(1, tiles[4]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 1, -2, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, -2, 1 }),
+            std::make_shared<Tile>(Tile::ID { 1, -1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, -1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 0, -1, 0 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][4]->clip);
 }
 
 TEST(ClipIDs, NegativeParentAndMissingLevel) {
-    std::array<std::unique_ptr<Tile>, 5> tiles {{
-        std::make_unique<Tile>(Tile::ID { 1, -1, 0 }), // 1/-1/0: 10000000 (1)
-        std::make_unique<Tile>(Tile::ID { 2, -1, 0 }), // 2/-1/0: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, -2, 1 }), // 2/-2/1: 11100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, -1, 1 }), // 2/-1/1: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, -2, 0 }), // 2/-2/0: 11000000 (3)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask); ASSERT_EQ(1, tiles[0]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[4]->clip.mask); ASSERT_EQ(3, tiles[4]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 1, -1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, -1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, -2, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, -1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, -2, 0 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][4]->clip);
 }
 
 
 TEST(ClipIDs, SevenOnSameLevel) {
-    std::array<std::unique_ptr<Tile>, 7> tiles {{
-        std::make_unique<Tile>(Tile::ID { 2, 0, 0 }), // 2/0/0: 11000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 0, 1 }), // 2/0/1: 11100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 0, 2 }), // 2/0/2: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 1, 0 }), // 2/1/0: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 1, 1 }), // 2/1/1: 01000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 1, 2 }), // 2/1/2: 01100000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 2, 0 }), // 2/2/0: 00100000 (3)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length);
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length);
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length);
-    ASSERT_EQ(std::bitset<8>("01000000"), tiles[4]->clip.mask); ASSERT_EQ(3, tiles[4]->clip.length);
-    ASSERT_EQ(std::bitset<8>("01100000"), tiles[5]->clip.mask); ASSERT_EQ(3, tiles[5]->clip.length);
-    ASSERT_EQ(std::bitset<8>("00100000"), tiles[6]->clip.mask); ASSERT_EQ(3, tiles[6]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 2, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 2 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 2 }),
+            std::make_shared<Tile>(Tile::ID { 2, 2, 0 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][4]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000110"), sources[0][5]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000111"), sources[0][6]->clip);
 }
 
 TEST(ClipIDs, MultipleLevels) {
-    std::array<std::unique_ptr<Tile>, 12> tiles {{
-        std::make_unique<Tile>(Tile::ID { 2, 0, 0 }),           // 2/0/0: 10000000 (1)
-            std::make_unique<Tile>(Tile::ID { 3, 0, 0 }),       //     3/0/0: 10000000 (3)
-            std::make_unique<Tile>(Tile::ID { 3, 0, 1 }),       //     3/0/1: 11100000 (3)
-                std::make_unique<Tile>(Tile::ID { 4, 0, 2 }),   //         4/0/2: 11110000 (5)
-                std::make_unique<Tile>(Tile::ID { 4, 1, 2 }),   //         4/0/3: 11111000 (5)
-                std::make_unique<Tile>(Tile::ID { 4, 0, 3 }),   //         4/1/2: 11100000 (5)
-                std::make_unique<Tile>(Tile::ID { 4, 1, 3 }),   //         4/1/3: 11101000 (5)
-            std::make_unique<Tile>(Tile::ID { 3, 1, 0 }),       //     3/1/0: 10100000 (3)
-            std::make_unique<Tile>(Tile::ID { 3, 1, 1 }),       //     3/1/1: 11000000 (3)
-        std::make_unique<Tile>(Tile::ID { 2, 1, 0 }),           // 2/1/0: 01000000 (2)
-            std::make_unique<Tile>(Tile::ID { 3, 2, 0 }),       //     3/2/0: 01010000 (4)
-            std::make_unique<Tile>(Tile::ID { 3, 2, 1 }),       //     3/2/1: 01100000 (3)
-    }};
-
-    // Use a random order to verify that the result of this algorithm is independent of the
-    std::random_shuffle(tiles.begin(), tiles.end());
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // Sort them by tile ID so that we know what order we have to test in.
-    std::sort(tiles.begin(), tiles.end(), [](const std::unique_ptr<Tile> &a, const std::unique_ptr<Tile> &b) {
-        return a->id < b->id;
-    });
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::string("2/0/0"), std::string(tiles[0]->id));
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask);
-    ASSERT_EQ(1, tiles[0]->clip.length);
-
-    ASSERT_EQ(std::string("2/1/0"), std::string(tiles[1]->id));
-    ASSERT_EQ(std::bitset<8>("01000000"), tiles[1]->clip.mask);
-    ASSERT_EQ(2, tiles[1]->clip.length);
-
-    ASSERT_EQ(std::string("3/0/0"), std::string(tiles[2]->id));
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask);
-    ASSERT_EQ(3, tiles[2]->clip.length);
-
-    ASSERT_EQ(std::string("3/0/1"), std::string(tiles[3]->id));
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[3]->clip.mask);
-    ASSERT_EQ(3, tiles[3]->clip.length);
-
-    ASSERT_EQ(std::string("3/1/0"), std::string(tiles[4]->id));
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[4]->clip.mask);
-    ASSERT_EQ(3, tiles[4]->clip.length);
-
-    ASSERT_EQ(std::string("3/1/1"), std::string(tiles[5]->id));
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[5]->clip.mask);
-    ASSERT_EQ(3, tiles[5]->clip.length);
-
-    ASSERT_EQ(std::string("3/2/0"), std::string(tiles[6]->id));
-    ASSERT_EQ(std::bitset<8>("01010000"), tiles[6]->clip.mask);
-    ASSERT_EQ(4, tiles[6]->clip.length);
-
-    ASSERT_EQ(std::string("3/2/1"), std::string(tiles[7]->id));
-    ASSERT_EQ(std::bitset<8>("01100000"), tiles[7]->clip.mask);
-    ASSERT_EQ(3, tiles[7]->clip.length);
-
-    ASSERT_EQ(std::string("4/0/2"), std::string(tiles[8]->id));
-    ASSERT_EQ(std::bitset<8>("11110000"), tiles[8]->clip.mask);
-    ASSERT_EQ(5, tiles[8]->clip.length);
-
-    ASSERT_EQ(std::string("4/0/3"), std::string(tiles[9]->id));
-    ASSERT_EQ(std::bitset<8>("11111000"), tiles[9]->clip.mask);
-    ASSERT_EQ(5, tiles[9]->clip.length);
-
-    ASSERT_EQ(std::string("4/1/2"), std::string(tiles[10]->id));
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[10]->clip.mask);
-    ASSERT_EQ(5, tiles[10]->clip.length);
-
-    ASSERT_EQ(std::string("4/1/3"), std::string(tiles[11]->id));
-    ASSERT_EQ(std::bitset<8>("11101000"), tiles[11]->clip.mask);
-    ASSERT_EQ(5, tiles[11]->clip.length);
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 2, 0, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 0, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 0, 1 }),
+                    std::make_shared<Tile>(Tile::ID { 4, 0, 2 }),
+                    std::make_shared<Tile>(Tile::ID { 4, 1, 2 }),
+                    std::make_shared<Tile>(Tile::ID { 4, 0, 3 }),
+                    std::make_shared<Tile>(Tile::ID { 4, 1, 3 }),
+                std::make_shared<Tile>(Tile::ID { 3, 1, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 2, 0 }),
+                std::make_shared<Tile>(Tile::ID { 3, 2, 1 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00001111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000011"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000100"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001001"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001011"), sources[0][4]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001010"), sources[0][5]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001100"), sources[0][6]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000101"), sources[0][7]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000110"), sources[0][8]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000010"), sources[0][9]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000111"), sources[0][10]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001000"), sources[0][11]->clip);
 }
 
 
 TEST(ClipIDs, Bug206) {
-    std::array<std::unique_ptr<Tile>, 11> tiles {{
-        std::make_unique<Tile>(Tile::ID { 10, 162, 395 }),      // 10/162/395: 10000000 (3)
-        std::make_unique<Tile>(Tile::ID { 10, 162, 396 }),      // 10/162/396: 10100000 (3)
-        std::make_unique<Tile>(Tile::ID { 10, 163, 395 }),      // 10/163/395: 11000000 (2)
-            std::make_unique<Tile>(Tile::ID { 11, 326, 791 }),  //     11/326/791: 11100000 (4)
-            std::make_unique<Tile>(Tile::ID { 12, 654, 1582 }), //     12/654/1582: 11001000 (5)
-            std::make_unique<Tile>(Tile::ID { 12, 654, 1583 }), //     12/654/1583: 11010000 (4)
-            std::make_unique<Tile>(Tile::ID { 12, 655, 1582 }), //     12/655/1582: 11110000 (5)
-            std::make_unique<Tile>(Tile::ID { 12, 655, 1583 }), //     12/655/1583: 11111000 (5)
-        std::make_unique<Tile>(Tile::ID { 10, 163, 396 }),      // 10/163/396: 01000000 (3)
-        std::make_unique<Tile>(Tile::ID { 10, 164, 395 }),      // 10/164/395: 01100000 (3)
-        std::make_unique<Tile>(Tile::ID { 10, 164, 396 }),      // 10/164/396: 00100000 (3)
-    }};
-
-    std::list<Tile *> tile_ptrs;
-    std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); });
-
-    updateClipIDs(tile_ptrs);
-
-    // for (const auto &it : tiles) {
-    //     std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl;
-    // }
-
-    ASSERT_EQ(std::string("10/162/395"), std::string(tiles[0]->id));
-    ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask);
-    ASSERT_EQ(3, tiles[0]->clip.length);
-
-    ASSERT_EQ(std::string("10/162/396"), std::string(tiles[1]->id));
-    ASSERT_EQ(std::bitset<8>("10100000"), tiles[1]->clip.mask);
-    ASSERT_EQ(3, tiles[1]->clip.length);
-
-    ASSERT_EQ(std::string("10/163/395"), std::string(tiles[2]->id));
-    ASSERT_EQ(std::bitset<8>("11000000"), tiles[2]->clip.mask);
-    ASSERT_EQ(2, tiles[2]->clip.length);
-
-    ASSERT_EQ(std::string("11/326/791"), std::string(tiles[3]->id));
-    ASSERT_EQ(std::bitset<8>("11100000"), tiles[3]->clip.mask);
-    ASSERT_EQ(4, tiles[3]->clip.length);
-
-    ASSERT_EQ(std::string("12/654/1582"), std::string(tiles[4]->id));
-    ASSERT_EQ(std::bitset<8>("11001000"), tiles[4]->clip.mask);
-    ASSERT_EQ(5, tiles[4]->clip.length);
-
-    ASSERT_EQ(std::string("12/654/1583"), std::string(tiles[5]->id));
-    ASSERT_EQ(std::bitset<8>("11010000"), tiles[5]->clip.mask);
-    ASSERT_EQ(4, tiles[5]->clip.length);
-
-    ASSERT_EQ(std::string("12/655/1582"), std::string(tiles[6]->id));
-    ASSERT_EQ(std::bitset<8>("11110000"), tiles[6]->clip.mask);
-    ASSERT_EQ(5, tiles[6]->clip.length);
-
-    ASSERT_EQ(std::string("12/655/1583"), std::string(tiles[7]->id));
-    ASSERT_EQ(std::bitset<8>("11111000"), tiles[7]->clip.mask);
-    ASSERT_EQ(5, tiles[7]->clip.length);
-
-    ASSERT_EQ(std::string("10/163/396"), std::string(tiles[8]->id));
-    ASSERT_EQ(std::bitset<8>("01000000"), tiles[8]->clip.mask);
-    ASSERT_EQ(3, tiles[8]->clip.length);
-
-    ASSERT_EQ(std::string("10/164/395"), std::string(tiles[9]->id));
-    ASSERT_EQ(std::bitset<8>("01100000"), tiles[9]->clip.mask);
-    ASSERT_EQ(3, tiles[9]->clip.length);
-
-    ASSERT_EQ(std::string("10/164/396"), std::string(tiles[10]->id));
-    ASSERT_EQ(std::bitset<8>("00100000"), tiles[10]->clip.mask);
-    ASSERT_EQ(3, tiles[10]->clip.length);
-
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 10, 162, 395 }),
+            std::make_shared<Tile>(Tile::ID { 10, 162, 396 }),
+            std::make_shared<Tile>(Tile::ID { 10, 163, 395 }),
+                std::make_shared<Tile>(Tile::ID { 11, 326, 791 }),
+                std::make_shared<Tile>(Tile::ID { 12, 654, 1582 }),
+                std::make_shared<Tile>(Tile::ID { 12, 654, 1583 }),
+                std::make_shared<Tile>(Tile::ID { 12, 655, 1582 }),
+                std::make_shared<Tile>(Tile::ID { 12, 655, 1583 }),
+            std::make_shared<Tile>(Tile::ID { 10, 163, 396 }),
+            std::make_shared<Tile>(Tile::ID { 10, 164, 395 }),
+            std::make_shared<Tile>(Tile::ID { 10, 164, 396 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00001111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000010"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000011"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000111"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001000"), sources[0][4]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001001"), sources[0][5]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001010"), sources[0][6]->clip);
+    ASSERT_EQ(ClipID("00001111", "00001011"), sources[0][7]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000100"), sources[0][8]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000101"), sources[0][9]->clip);
+    ASSERT_EQ(ClipID("00001111", "00000110"), sources[0][10]->clip);
 }
 
-TEST(ClipIDs, DuplicateIDs) {
-
-    std::forward_list<Tile::ID> tiles {{
-        Tile::ID { 2, 0, 0 },
-        Tile::ID { 2, 0, 1 },
-        Tile::ID { 2, 0, 0 },
-        Tile::ID { 2, 0, 1 },
-        Tile::ID { 2, 0, 1 },
-    }};
 
-    std::map<Tile::ID, ClipID> mapping = computeClipIDs(tiles);
-
-    ASSERT_EQ(2ull, mapping.size());
-
-    // for (const auto &it : mapping) {
-    //     std::cout << std::string(it.first) << "(" << it.first << ")" << ": " << it.second.mask << " (" << (int)it.second.length << ")" << std::endl;
-    // }
+TEST(ClipIDs, MultipleSources) {
+    const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 0, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 2, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 2, 2 }),
+        },
+        {
+            std::make_shared<Tile>(Tile::ID { 0, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 2, 2 }),
+        },
+        {
+            std::make_shared<Tile>(Tile::ID { 1, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 0, 1 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 0 }),
+            std::make_shared<Tile>(Tile::ID { 1, 1, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 1, 1 }),
+        },
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][3]->clip);
+    ASSERT_EQ(ClipID("00011000", "00001000"), sources[1][0]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000010"), sources[1][1]->clip);
+    ASSERT_EQ(ClipID("00011000", "00010000"), sources[1][2]->clip);
+    ASSERT_EQ(ClipID("00000111", "00000100"), sources[1][3]->clip);
+    ASSERT_EQ(ClipID("11100000", "00100000"), sources[2][0]->clip);
+    ASSERT_EQ(ClipID("11100000", "01000000"), sources[2][1]->clip);
+    ASSERT_EQ(ClipID("11100000", "01100000"), sources[2][2]->clip);
+    ASSERT_EQ(ClipID("11100000", "10000000"), sources[2][3]->clip);
+    ASSERT_EQ(ClipID("00011000", "00010000"), sources[2][4]->clip);
+}
 
-    ASSERT_EQ(std::bitset<8>("01000000"), mapping[Tile::ID(2, 0, 0)].mask);
-    ASSERT_EQ(2, mapping[Tile::ID(2, 0, 0)].length);
 
-    ASSERT_EQ(std::bitset<8>("10000000"), mapping[Tile::ID(2, 0, 1)].mask);
-    ASSERT_EQ(1, mapping[Tile::ID(2, 0, 1)].length);
+TEST(ClipIDs, DuplicateIDs) {
+        const std::vector<std::vector<std::shared_ptr<Tile>>> sources = {
+        {
+            std::make_shared<Tile>(Tile::ID { 2, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 1 }),
+        },
+        {
+            std::make_shared<Tile>(Tile::ID { 2, 0, 0 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 1 }),
+            std::make_shared<Tile>(Tile::ID { 2, 0, 1 }),
+        }
+    };
+
+    generate(sources);
+    // print(sources);
+
+    ASSERT_EQ(ClipID("00000011", "00000001"), sources[0][0]->clip);
+    ASSERT_EQ(ClipID("00000011", "00000010"), sources[0][1]->clip);
+    ASSERT_EQ(ClipID("00000011", "00000001"), sources[1][0]->clip);
+    ASSERT_EQ(ClipID("00000011", "00000010"), sources[1][1]->clip);
+    ASSERT_EQ(ClipID("00000011", "00000010"), sources[1][2]->clip);
 }