summaryrefslogtreecommitdiff
path: root/test/algorithm/generate_clip_ids.test.cpp
blob: 8ca0191b3a83973eb5d667e7525ff78e103a56c5 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
#include <mbgl/test/util.hpp>

#include <mbgl/algorithm/generate_clip_ids_impl.hpp>

using namespace mbgl;

struct Renderable {
    ClipID clip;
    bool used = true;

    bool operator==(const Renderable& rhs) const {
        return clip == rhs.clip;
    }
};

::std::ostream& operator<<(::std::ostream& os, const Renderable& rhs) {
    return os << "ClipID(" << rhs.clip << ")";
}

namespace {

// void print(const std::map<UnwrappedTileID, Renderable>& renderables) {
//     std::cout << "    EXPECT_EQ(decltype(renderables)({" << std::endl;
//     for (auto& pair : renderables) {
//         std::cout << "              { UnwrappedTileID{ " << int(pair.first.canonical.z) << ", "
//                   << (int64_t(pair.first.canonical.x) +
//                       pair.first.wrap * (1ll << pair.first.canonical.z))
//                   << ", " << pair.first.canonical.y << " }, Renderable{ ClipID{ \""
//                   << pair.second.clip.mask << "\", \"" << pair.second.clip.reference << "\" } } },"
//                   << std::endl;
//     }
//     std::cout << "          })," << std::endl;
//     std::cout << "          renderables);" << std::endl;
// }

// void print(const std::map<UnwrappedTileID, ClipID>& stencils) {
//     std::cout << "    EXPECT_EQ(decltype(stencils)({" << std::endl;
//     for (auto& pair : stencils) {
//         std::cout << "              { UnwrappedTileID{ " << int(pair.first.canonical.z) << ", "
//                   << (int64_t(pair.first.canonical.x) +
//                       pair.first.wrap * (1ll << pair.first.canonical.z))
//                   << ", " << pair.first.canonical.y << " }, ClipID{ \"" << pair.second.mask
//                   << "\", \"" << pair.second.reference << "\" } }," << std::endl;
//     }
//     std::cout << "          })," << std::endl;
//     std::cout << "          stencils);" << std::endl;
// }

} // end namespace

TEST(GenerateClipIDs, ParentAndFourChildren) {
    std::map<UnwrappedTileID, Renderable> renderables{
        { UnwrappedTileID{ 0, 0, 0 }, Renderable{ {} } },
        // All four covering children
        { UnwrappedTileID{ 1, 0, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 1, 0, 1 }, Renderable{ {} } },
        { UnwrappedTileID{ 1, 1, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 1, 1, 1 }, Renderable{ {} } },
    };

    algorithm::ClipIDGenerator generator;
    generator.update(renderables);

    EXPECT_EQ(decltype(renderables)({
                  { UnwrappedTileID{ 0, 0, 0 }, Renderable{ ClipID{ "00000111", "00000001" } } },
                  { UnwrappedTileID{ 1, 0, 0 }, Renderable{ ClipID{ "00000111", "00000010" } } },
                  { UnwrappedTileID{ 1, 0, 1 }, Renderable{ ClipID{ "00000111", "00000011" } } },
                  { UnwrappedTileID{ 1, 1, 0 }, Renderable{ ClipID{ "00000111", "00000100" } } },
                  { UnwrappedTileID{ 1, 1, 1 }, Renderable{ ClipID{ "00000111", "00000101" } } },
              }),
              renderables);

    const auto stencils = generator.getStencils();
    EXPECT_EQ(decltype(stencils)({
                  // 0/0/0 is missing because it is covered by children.
                  { UnwrappedTileID{ 1, 0, 0 }, ClipID{ "00000111", "00000010" } },
                  { UnwrappedTileID{ 1, 0, 1 }, ClipID{ "00000111", "00000011" } },
                  { UnwrappedTileID{ 1, 1, 0 }, ClipID{ "00000111", "00000100" } },
                  { UnwrappedTileID{ 1, 1, 1 }, ClipID{ "00000111", "00000101" } },
              }),
              stencils);
}

TEST(GenerateClipIDs, ParentAndFourChildrenNegative) {
    std::map<UnwrappedTileID, Renderable> renderables{
        { UnwrappedTileID{ 1, -2, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 1, -2, 1 }, Renderable{ {} } },
        { UnwrappedTileID{ 1, -1, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 1, -1, 1 }, Renderable{ {} } },
        { UnwrappedTileID{ 0, -1, 0 }, Renderable{ {} } },
    };

    algorithm::ClipIDGenerator generator;
    generator.update(renderables);

    EXPECT_EQ(decltype(renderables)({
                  { UnwrappedTileID{ 0, -1, 0 }, Renderable{ ClipID{ "00000111", "00000001" } } },
                  { UnwrappedTileID{ 1, -2, 0 }, Renderable{ ClipID{ "00000111", "00000010" } } },
                  { UnwrappedTileID{ 1, -2, 1 }, Renderable{ ClipID{ "00000111", "00000011" } } },
                  { UnwrappedTileID{ 1, -1, 0 }, Renderable{ ClipID{ "00000111", "00000100" } } },
                  { UnwrappedTileID{ 1, -1, 1 }, Renderable{ ClipID{ "00000111", "00000101" } } },
              }),
              renderables);

    const auto stencils = generator.getStencils();
    EXPECT_EQ(decltype(stencils)({
                  { UnwrappedTileID{ 1, -2, 0 }, ClipID{ "00000111", "00000010" } },
                  { UnwrappedTileID{ 1, -2, 1 }, ClipID{ "00000111", "00000011" } },
                  { UnwrappedTileID{ 1, -1, 0 }, ClipID{ "00000111", "00000100" } },
                  { UnwrappedTileID{ 1, -1, 1 }, ClipID{ "00000111", "00000101" } },
              }),
              stencils);
}

TEST(GenerateClipIDs, NegativeParentAndMissingLevel) {
    std::map<UnwrappedTileID, Renderable> renderables{
        { UnwrappedTileID{ 1, -1, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 2, -1, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 2, -2, 1 }, Renderable{ {} } },
        { UnwrappedTileID{ 2, -1, 1 }, Renderable{ {} } },
        { UnwrappedTileID{ 2, -2, 0 }, Renderable{ {} } },
    };

    algorithm::ClipIDGenerator generator;
    generator.update(renderables);

    EXPECT_EQ(decltype(renderables)({
                  { UnwrappedTileID{ 1, -1, 0 }, Renderable{ ClipID{ "00000111", "00000001" } } },
                  { UnwrappedTileID{ 2, -2, 0 }, Renderable{ ClipID{ "00000111", "00000010" } } },
                  { UnwrappedTileID{ 2, -2, 1 }, Renderable{ ClipID{ "00000111", "00000011" } } },
                  { UnwrappedTileID{ 2, -1, 0 }, Renderable{ ClipID{ "00000111", "00000100" } } },
                  { UnwrappedTileID{ 2, -1, 1 }, Renderable{ ClipID{ "00000111", "00000101" } } },
              }),
              renderables);

    const auto stencils = generator.getStencils();
    EXPECT_EQ(decltype(stencils)({
                  { UnwrappedTileID{ 2, -2, 0 }, ClipID{ "00000111", "00000010" } },
                  { UnwrappedTileID{ 2, -2, 1 }, ClipID{ "00000111", "00000011" } },
                  { UnwrappedTileID{ 2, -1, 0 }, ClipID{ "00000111", "00000100" } },
                  { UnwrappedTileID{ 2, -1, 1 }, ClipID{ "00000111", "00000101" } },
              }),
              stencils);
}

TEST(GenerateClipIDs, SevenOnSameLevel) {
    std::map<UnwrappedTileID, Renderable> renderables{
        // first column
        { UnwrappedTileID{ 2, 0, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 2, 0, 1 }, Renderable{ {} } },
        { UnwrappedTileID{ 2, 0, 2 }, Renderable{ {} } },
        // second column
        { UnwrappedTileID{ 2, 1, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 2, 1, 1 }, Renderable{ {} } },
        { UnwrappedTileID{ 2, 1, 2 }, Renderable{ {} } },
        // third column
        { UnwrappedTileID{ 2, 2, 0 }, Renderable{ {} } },
    };

    algorithm::ClipIDGenerator generator;
    generator.update(renderables);
    EXPECT_EQ(decltype(renderables)({
                  { UnwrappedTileID{ 2, 0, 0 }, Renderable{ ClipID{ "00000111", "00000001" } } },
                  { UnwrappedTileID{ 2, 0, 1 }, Renderable{ ClipID{ "00000111", "00000010" } } },
                  { UnwrappedTileID{ 2, 0, 2 }, Renderable{ ClipID{ "00000111", "00000011" } } },
                  { UnwrappedTileID{ 2, 1, 0 }, Renderable{ ClipID{ "00000111", "00000100" } } },
                  { UnwrappedTileID{ 2, 1, 1 }, Renderable{ ClipID{ "00000111", "00000101" } } },
                  { UnwrappedTileID{ 2, 1, 2 }, Renderable{ ClipID{ "00000111", "00000110" } } },
                  { UnwrappedTileID{ 2, 2, 0 }, Renderable{ ClipID{ "00000111", "00000111" } } },
              }),
              renderables);

    const auto stencils = generator.getStencils();
    EXPECT_EQ(decltype(stencils)({
                  { UnwrappedTileID{ 2, 0, 0 }, ClipID{ "00000111", "00000001" } },
                  { UnwrappedTileID{ 2, 0, 1 }, ClipID{ "00000111", "00000010" } },
                  { UnwrappedTileID{ 2, 0, 2 }, ClipID{ "00000111", "00000011" } },
                  { UnwrappedTileID{ 2, 1, 0 }, ClipID{ "00000111", "00000100" } },
                  { UnwrappedTileID{ 2, 1, 1 }, ClipID{ "00000111", "00000101" } },
                  { UnwrappedTileID{ 2, 1, 2 }, ClipID{ "00000111", "00000110" } },
                  { UnwrappedTileID{ 2, 2, 0 }, ClipID{ "00000111", "00000111" } },
              }),
              stencils);
}

TEST(GenerateClipIDs, MultipleLevels) {
    std::map<UnwrappedTileID, Renderable> renderables{
        { UnwrappedTileID{ 2, 0, 0 }, Renderable{ {} } },
        // begin subtiles of (2/0/0)
        { UnwrappedTileID{ 3, 0, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 3, 0, 1 }, Renderable{ {} } },
        // begin subtiles of (3/0/1)
        { UnwrappedTileID{ 4, 0, 2 }, Renderable{ {} } },
        { UnwrappedTileID{ 4, 1, 2 }, Renderable{ {} } },
        { UnwrappedTileID{ 4, 0, 3 }, Renderable{ {} } },
        { UnwrappedTileID{ 4, 1, 3 }, Renderable{ {} } },
        // end subtiles of (3/0/1)
        { UnwrappedTileID{ 3, 1, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 3, 1, 1 }, Renderable{ {} } },
        // end subtiles of (2/0/0)
        { UnwrappedTileID{ 2, 1, 0 }, Renderable{ {} } },
        // begin subtiles of (2/1/0)
        { UnwrappedTileID{ 3, 2, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 3, 2, 1 }, Renderable{ {} } },
        // end subtiles of (2/1/0)
    };

    algorithm::ClipIDGenerator generator;
    generator.update(renderables);
    ASSERT_EQ(decltype(renderables)({
                  { UnwrappedTileID{ 2, 0, 0 }, Renderable{ ClipID{ "00001111", "00000001" } } },
                  { UnwrappedTileID{ 2, 1, 0 }, Renderable{ ClipID{ "00001111", "00000010" } } },
                  { UnwrappedTileID{ 3, 0, 0 }, Renderable{ ClipID{ "00001111", "00000011" } } },
                  { UnwrappedTileID{ 3, 0, 1 }, Renderable{ ClipID{ "00001111", "00000100" } } },
                  { UnwrappedTileID{ 3, 1, 0 }, Renderable{ ClipID{ "00001111", "00000101" } } },
                  { UnwrappedTileID{ 3, 1, 1 }, Renderable{ ClipID{ "00001111", "00000110" } } },
                  { UnwrappedTileID{ 3, 2, 0 }, Renderable{ ClipID{ "00001111", "00000111" } } },
                  { UnwrappedTileID{ 3, 2, 1 }, Renderable{ ClipID{ "00001111", "00001000" } } },
                  { UnwrappedTileID{ 4, 0, 2 }, Renderable{ ClipID{ "00001111", "00001001" } } },
                  { UnwrappedTileID{ 4, 0, 3 }, Renderable{ ClipID{ "00001111", "00001010" } } },
                  { UnwrappedTileID{ 4, 1, 2 }, Renderable{ ClipID{ "00001111", "00001011" } } },
                  { UnwrappedTileID{ 4, 1, 3 }, Renderable{ ClipID{ "00001111", "00001100" } } },
              }),
              renderables);

    const auto stencils = generator.getStencils();
    EXPECT_EQ(decltype(stencils)({
                  { UnwrappedTileID{ 2, 1, 0 }, ClipID{ "00001111", "00000010" } },
                  { UnwrappedTileID{ 3, 0, 0 }, ClipID{ "00001111", "00000011" } },
                  { UnwrappedTileID{ 3, 1, 0 }, ClipID{ "00001111", "00000101" } },
                  { UnwrappedTileID{ 3, 1, 1 }, ClipID{ "00001111", "00000110" } },
                  { UnwrappedTileID{ 3, 2, 0 }, ClipID{ "00001111", "00000111" } },
                  { UnwrappedTileID{ 3, 2, 1 }, ClipID{ "00001111", "00001000" } },
                  { UnwrappedTileID{ 4, 0, 2 }, ClipID{ "00001111", "00001001" } },
                  { UnwrappedTileID{ 4, 0, 3 }, ClipID{ "00001111", "00001010" } },
                  { UnwrappedTileID{ 4, 1, 2 }, ClipID{ "00001111", "00001011" } },
                  { UnwrappedTileID{ 4, 1, 3 }, ClipID{ "00001111", "00001100" } },
              }),
              stencils);
}

TEST(GenerateClipIDs, Bug206) {
    std::map<UnwrappedTileID, Renderable> renderables{
        { UnwrappedTileID{ 10, 162, 395 }, Renderable{ {} } },
        { UnwrappedTileID{ 10, 162, 396 }, Renderable{ {} } },
        { UnwrappedTileID{ 10, 163, 395 }, Renderable{ {} } },
        // begin subtiles of (10/163/395)
        { UnwrappedTileID{ 11, 326, 791 }, Renderable{ {} } },
        { UnwrappedTileID{ 12, 654, 1582 }, Renderable{ {} } },
        { UnwrappedTileID{ 12, 654, 1583 }, Renderable{ {} } },
        { UnwrappedTileID{ 12, 655, 1582 }, Renderable{ {} } },
        { UnwrappedTileID{ 12, 655, 1583 }, Renderable{ {} } },
        // end subtiles of (10/163/395)
        { UnwrappedTileID{ 10, 163, 396 }, Renderable{ {} } },
        { UnwrappedTileID{ 10, 164, 395 }, Renderable{ {} } },
        { UnwrappedTileID{ 10, 164, 396 }, Renderable{ {} } },
    };

    algorithm::ClipIDGenerator generator;
    generator.update(renderables);
    EXPECT_EQ(
        decltype(renderables)({
            { UnwrappedTileID{ 10, 162, 395 }, Renderable{ ClipID{ "00001111", "00000001" } } },
            { UnwrappedTileID{ 10, 162, 396 }, Renderable{ ClipID{ "00001111", "00000010" } } },
            { UnwrappedTileID{ 10, 163, 395 }, Renderable{ ClipID{ "00001111", "00000011" } } },
            { UnwrappedTileID{ 10, 163, 396 }, Renderable{ ClipID{ "00001111", "00000100" } } },
            { UnwrappedTileID{ 10, 164, 395 }, Renderable{ ClipID{ "00001111", "00000101" } } },
            { UnwrappedTileID{ 10, 164, 396 }, Renderable{ ClipID{ "00001111", "00000110" } } },
            { UnwrappedTileID{ 11, 326, 791 }, Renderable{ ClipID{ "00001111", "00000111" } } },
            { UnwrappedTileID{ 12, 654, 1582 }, Renderable{ ClipID{ "00001111", "00001000" } } },
            { UnwrappedTileID{ 12, 654, 1583 }, Renderable{ ClipID{ "00001111", "00001001" } } },
            { UnwrappedTileID{ 12, 655, 1582 }, Renderable{ ClipID{ "00001111", "00001010" } } },
            { UnwrappedTileID{ 12, 655, 1583 }, Renderable{ ClipID{ "00001111", "00001011" } } },
        }),
        renderables);

    const auto stencils = generator.getStencils();
    EXPECT_EQ(decltype(stencils)({
                  { UnwrappedTileID{ 10, 162, 395 }, ClipID{ "00001111", "00000001" } },
                  { UnwrappedTileID{ 10, 162, 396 }, ClipID{ "00001111", "00000010" } },
                  { UnwrappedTileID{ 10, 163, 395 }, ClipID{ "00001111", "00000011" } },
                  { UnwrappedTileID{ 10, 163, 396 }, ClipID{ "00001111", "00000100" } },
                  { UnwrappedTileID{ 10, 164, 395 }, ClipID{ "00001111", "00000101" } },
                  { UnwrappedTileID{ 10, 164, 396 }, ClipID{ "00001111", "00000110" } },
                  { UnwrappedTileID{ 11, 326, 791 }, ClipID{ "00001111", "00000111" } },
                  { UnwrappedTileID{ 12, 654, 1582 }, ClipID{ "00001111", "00001000" } },
                  { UnwrappedTileID{ 12, 654, 1583 }, ClipID{ "00001111", "00001001" } },
                  { UnwrappedTileID{ 12, 655, 1582 }, ClipID{ "00001111", "00001010" } },
                  { UnwrappedTileID{ 12, 655, 1583 }, ClipID{ "00001111", "00001011" } },
              }),
              stencils);
}

TEST(GenerateClipIDs, MultipleSources) {
    std::map<UnwrappedTileID, Renderable> renderables1{
        { UnwrappedTileID{ 0, 0, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 1, 1, 1 }, Renderable{ {} } },
        // Differing children
        { UnwrappedTileID{ 2, 2, 1 }, Renderable{ {} } },
        { UnwrappedTileID{ 2, 2, 2 }, Renderable{ {} } },
    };
    std::map<UnwrappedTileID, Renderable> renderables2{
        { UnwrappedTileID{ 0, 0, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 1, 1, 1 }, Renderable{ {} } },
        // Differing children
        { UnwrappedTileID{ 2, 1, 1 }, Renderable{ {} } },
        { UnwrappedTileID{ 2, 2, 2 }, Renderable{ {} } },
    };
    std::map<UnwrappedTileID, Renderable> renderables3{
        { UnwrappedTileID{ 1, 0, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 1, 0, 1 }, Renderable{ {} } },
        { UnwrappedTileID{ 1, 1, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 1, 1, 1 }, Renderable{ {} } },
        // Differing children
        { UnwrappedTileID{ 2, 1, 1 }, Renderable{ {} } },
    };

    algorithm::ClipIDGenerator generator;
    generator.update(renderables1);
    generator.update(renderables2);
    generator.update(renderables3);
    EXPECT_EQ(decltype(renderables1)({
                  { UnwrappedTileID{ 0, 0, 0 }, Renderable{ ClipID{ "00000111", "00000001" } } },
                  { UnwrappedTileID{ 1, 1, 1 }, Renderable{ ClipID{ "00000111", "00000010" } } },
                  { UnwrappedTileID{ 2, 2, 1 }, Renderable{ ClipID{ "00000111", "00000011" } } },
                  { UnwrappedTileID{ 2, 2, 2 }, Renderable{ ClipID{ "00000111", "00000100" } } },
              }),
              renderables1);
    EXPECT_EQ(decltype(renderables2)({
                  { UnwrappedTileID{ 0, 0, 0 }, Renderable{ ClipID{ "00011000", "00001000" } } },
                  { UnwrappedTileID{ 1, 1, 1 }, Renderable{ ClipID{ "00011111", "00000010" } } },
                  { UnwrappedTileID{ 2, 1, 1 }, Renderable{ ClipID{ "00011000", "00010000" } } },
                  { UnwrappedTileID{ 2, 2, 2 }, Renderable{ ClipID{ "00011111", "00000100" } } },
              }),
              renderables2);
    EXPECT_EQ(decltype(renderables3)({
                  { UnwrappedTileID{ 1, 0, 0 }, Renderable{ ClipID{ "11100000", "00100000" } } },
                  { UnwrappedTileID{ 1, 0, 1 }, Renderable{ ClipID{ "11100000", "01000000" } } },
                  { UnwrappedTileID{ 1, 1, 0 }, Renderable{ ClipID{ "11100000", "01100000" } } },
                  { UnwrappedTileID{ 1, 1, 1 }, Renderable{ ClipID{ "11100000", "10000000" } } },
                  { UnwrappedTileID{ 2, 1, 1 }, Renderable{ ClipID{ "11111000", "00010000" } } },
              }),
              renderables3);

    const auto stencils = generator.getStencils();
    EXPECT_EQ(decltype(stencils)({
                  { UnwrappedTileID{ 1, 0, 0 }, ClipID{ "11111111", "00101001" } },
                  { UnwrappedTileID{ 1, 0, 1 }, ClipID{ "11111111", "01001001" } },
                  { UnwrappedTileID{ 1, 1, 0 }, ClipID{ "11111111", "01101001" } },
                  { UnwrappedTileID{ 1, 1, 1 }, ClipID{ "11111111", "10000010" } },
                  { UnwrappedTileID{ 2, 1, 1 }, ClipID{ "11111111", "00010001" } },
                  { UnwrappedTileID{ 2, 2, 1 }, ClipID{ "11111111", "01101011" } },
                  { UnwrappedTileID{ 2, 2, 2 }, ClipID{ "11111111", "10000100" } },
              }),
              stencils);
}

TEST(GenerateClipIDs, DuplicateIDs) {
    std::map<UnwrappedTileID, Renderable> renderables1{
        { UnwrappedTileID{ 2, 0, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 2, 0, 1 }, Renderable{ {} } },
    };
    std::map<UnwrappedTileID, Renderable> renderables2{
        { UnwrappedTileID{ 2, 0, 0 }, Renderable{ {} } },
        { UnwrappedTileID{ 2, 0, 1 }, Renderable{ {} } },
        { UnwrappedTileID{ 2, 0, 1 }, Renderable{ {} } },
    };

    algorithm::ClipIDGenerator generator;
    generator.update(renderables1);
    generator.update(renderables2);
    EXPECT_EQ(decltype(renderables1)({
                  { UnwrappedTileID{ 2, 0, 0 }, Renderable{ ClipID{ "00000011", "00000001" } } },
                  { UnwrappedTileID{ 2, 0, 1 }, Renderable{ ClipID{ "00000011", "00000010" } } },
              }),
              renderables1);
    EXPECT_EQ(decltype(renderables2)({
                  { UnwrappedTileID{ 2, 0, 0 }, Renderable{ ClipID{ "00000011", "00000001" } } },
                  { UnwrappedTileID{ 2, 0, 1 }, Renderable{ ClipID{ "00000011", "00000010" } } },
              }),
              renderables2);

    const auto stencils = generator.getStencils();
    EXPECT_EQ(decltype(stencils)({
                  { UnwrappedTileID{ 2, 0, 0 }, ClipID{ "00000011", "00000001" } },
                  { UnwrappedTileID{ 2, 0, 1 }, ClipID{ "00000011", "00000010" } },
              }),
              stencils);
}

TEST(GenerateClipIDs, SecondSourceHasParentOfFirstSource) {
    std::map<UnwrappedTileID, Renderable> renderables1{
        { UnwrappedTileID{ 1, 0, 0 }, Renderable{ {} } },
    };
    std::map<UnwrappedTileID, Renderable> renderables2{
        { UnwrappedTileID{ 0, 0, 0 }, Renderable{ {} } },
        // Same as in renderables1, but has a parent that it knocks out.
        { UnwrappedTileID{ 1, 0, 0 }, Renderable{ {} } },
    };
    std::map<UnwrappedTileID, Renderable> renderables3{
        { UnwrappedTileID{ 0, 0, 0 }, Renderable{ {} } },
    };

    algorithm::ClipIDGenerator generator;
    generator.update(renderables1);
    generator.update(renderables2);
    generator.update(renderables3);
    EXPECT_EQ(decltype(renderables1)({
                  { UnwrappedTileID{ 1, 0, 0 }, Renderable{ ClipID{ "00000001", "00000001" } } },
              }),
              renderables1);
    EXPECT_EQ(decltype(renderables2)({
                  { UnwrappedTileID{ 0, 0, 0 }, Renderable{ ClipID{ "00000010", "00000010" } } },
                  { UnwrappedTileID{ 1, 0, 0 }, Renderable{ ClipID{ "00000011", "00000001" } } },
              }),
              renderables2);
    EXPECT_EQ(decltype(renderables3)({
                  { UnwrappedTileID{ 0, 0, 0 }, Renderable{ ClipID{ "00000100", "00000100" } } },
              }),
              renderables3);

    const auto stencils = generator.getStencils();
    EXPECT_EQ(decltype(stencils)({
                  { UnwrappedTileID{ 0, 0, 0 }, ClipID{ "00000110", "00000110" } },
                  { UnwrappedTileID{ 1, 0, 0 }, ClipID{ "00000111", "00000101" } },
              }),
              stencils);
}