1 #include <cstdint>
2 #include <utility>
3 #include <iterator>
4 #include <algorithm>
5 #include <functional>
6 #include <type_traits>
7 #include <gtest/gtest.h>
8 #include <entt/entity/entity.hpp>
9 #include <entt/entity/sparse_set.hpp>
10 #include <entt/entity/fwd.hpp>
11 #include "throwing_allocator.hpp"
12 
13 struct empty_type {};
14 struct boxed_int { int value; };
15 
TEST(SparseSet,Functionalities)16 TEST(SparseSet, Functionalities) {
17     entt::sparse_set set;
18 
19     set.reserve(42);
20 
21     ASSERT_EQ(set.capacity(), 42u);
22     ASSERT_TRUE(set.empty());
23     ASSERT_EQ(set.size(), 0u);
24     ASSERT_EQ(std::as_const(set).begin(), std::as_const(set).end());
25     ASSERT_EQ(set.begin(), set.end());
26     ASSERT_FALSE(set.contains(entt::entity{0}));
27     ASSERT_FALSE(set.contains(entt::entity{42}));
28 
29     set.reserve(0);
30 
31     ASSERT_EQ(set.capacity(), 42u);
32     ASSERT_TRUE(set.empty());
33 
34     ASSERT_EQ(set.emplace(entt::entity{42}), 0u);
35 
36     ASSERT_FALSE(set.empty());
37     ASSERT_EQ(set.size(), 1u);
38     ASSERT_NE(std::as_const(set).begin(), std::as_const(set).end());
39     ASSERT_NE(set.begin(), set.end());
40     ASSERT_FALSE(set.contains(entt::entity{0}));
41     ASSERT_TRUE(set.contains(entt::entity{42}));
42     ASSERT_EQ(set.index(entt::entity{42}), 0u);
43     ASSERT_EQ(set.at(0u), entt::entity{42});
44     ASSERT_EQ(set.at(1u), static_cast<entt::entity>(entt::null));
45     ASSERT_EQ(set[0u], entt::entity{42});
46 
47     set.erase(entt::entity{42});
48 
49     ASSERT_TRUE(set.empty());
50     ASSERT_EQ(set.size(), 0u);
51     ASSERT_EQ(std::as_const(set).begin(), std::as_const(set).end());
52     ASSERT_EQ(set.begin(), set.end());
53     ASSERT_FALSE(set.contains(entt::entity{0}));
54     ASSERT_FALSE(set.contains(entt::entity{42}));
55     ASSERT_EQ(set.at(0u), static_cast<entt::entity>(entt::null));
56     ASSERT_EQ(set.at(1u), static_cast<entt::entity>(entt::null));
57 
58     ASSERT_EQ(set.emplace(entt::entity{42}), 0u);
59 
60     ASSERT_FALSE(set.empty());
61     ASSERT_EQ(set.index(entt::entity{42}), 0u);
62     ASSERT_EQ(set.at(0u), entt::entity{42});
63     ASSERT_EQ(set.at(1u), static_cast<entt::entity>(entt::null));
64     ASSERT_EQ(set[0u], entt::entity{42});
65 
66     set.clear();
67 
68     ASSERT_TRUE(set.empty());
69     ASSERT_EQ(set.size(), 0u);
70     ASSERT_EQ(std::as_const(set).begin(), std::as_const(set).end());
71     ASSERT_EQ(set.begin(), set.end());
72     ASSERT_FALSE(set.contains(entt::entity{0}));
73     ASSERT_FALSE(set.contains(entt::entity{42}));
74 }
75 
TEST(SparseSet,Contains)76 TEST(SparseSet, Contains) {
77     entt::sparse_set set{entt::deletion_policy::in_place};
78 
79     set.emplace(entt::entity{0});
80     set.emplace(entt::entity{3});
81     set.emplace(entt::entity{42});
82     set.emplace(entt::entity{99});
83 
84     set.emplace(entt::entity{1});
85 
86     ASSERT_TRUE(set.contains(entt::entity{0}));
87     ASSERT_TRUE(set.contains(entt::entity{3}));
88     ASSERT_TRUE(set.contains(entt::entity{42}));
89     ASSERT_TRUE(set.contains(entt::entity{99}));
90     ASSERT_TRUE(set.contains(entt::entity{1}));
91 
92     set.erase(entt::entity{0});
93     set.erase(entt::entity{3});
94 
95     set.remove(entt::entity{42});
96     set.remove(entt::entity{99});
97 
98     ASSERT_FALSE(set.contains(entt::entity{0}));
99     ASSERT_FALSE(set.contains(entt::entity{3}));
100     ASSERT_FALSE(set.contains(entt::entity{42}));
101     ASSERT_FALSE(set.contains(entt::entity{99}));
102     ASSERT_TRUE(set.contains(entt::entity{1}));
103 
104     ASSERT_DEATH(static_cast<void>(set.contains(entt::null)), "");
105     ASSERT_DEATH(static_cast<void>(set.contains(entt::tombstone)), "");
106     ASSERT_DEATH(static_cast<void>(set.contains(entt::tombstone | entt::entity{1u})), "");
107     ASSERT_DEATH(static_cast<void>(set.contains(entt::null | entt::entity{1u})), "");
108 }
109 
TEST(SparseSet,Move)110 TEST(SparseSet, Move) {
111     entt::sparse_set set;
112     set.emplace(entt::entity{42});
113 
114     ASSERT_TRUE(std::is_move_constructible_v<decltype(set)>);
115     ASSERT_TRUE(std::is_move_assignable_v<decltype(set)>);
116 
117     entt::sparse_set other{std::move(set)};
118 
119     ASSERT_TRUE(set.empty());
120     ASSERT_FALSE(other.empty());
121     ASSERT_EQ(set.at(0u), static_cast<entt::entity>(entt::null));
122     ASSERT_EQ(other.at(0u), entt::entity{42});
123 
124     set = std::move(other);
125 
126     ASSERT_FALSE(set.empty());
127     ASSERT_TRUE(other.empty());
128     ASSERT_EQ(set.at(0u), entt::entity{42});
129     ASSERT_EQ(other.at(0u), static_cast<entt::entity>(entt::null));
130 
131     other = entt::sparse_set{};
132     other.emplace(entt::entity{3});
133     other = std::move(set);
134 
135     ASSERT_TRUE(set.empty());
136     ASSERT_FALSE(other.empty());
137     ASSERT_EQ(set.at(0u), static_cast<entt::entity>(entt::null));
138     ASSERT_EQ(other.at(0u), entt::entity{42});
139 }
140 
TEST(SparseSet,Pagination)141 TEST(SparseSet, Pagination) {
142     entt::sparse_set set;
143 
144     ASSERT_EQ(set.extent(), 0u);
145 
146     set.emplace(entt::entity{ENTT_SPARSE_PAGE-1u});
147 
148     ASSERT_EQ(set.extent(), ENTT_SPARSE_PAGE);
149     ASSERT_TRUE(set.contains(entt::entity{ENTT_SPARSE_PAGE-1u}));
150 
151     set.emplace(entt::entity{ENTT_SPARSE_PAGE});
152 
153     ASSERT_EQ(set.extent(), 2 * ENTT_SPARSE_PAGE);
154     ASSERT_TRUE(set.contains(entt::entity{ENTT_SPARSE_PAGE-1u}));
155     ASSERT_TRUE(set.contains(entt::entity{ENTT_SPARSE_PAGE}));
156     ASSERT_FALSE(set.contains(entt::entity{ENTT_SPARSE_PAGE+1u}));
157 
158     set.erase(entt::entity{ENTT_SPARSE_PAGE-1u});
159 
160     ASSERT_EQ(set.extent(), 2 * ENTT_SPARSE_PAGE);
161     ASSERT_FALSE(set.contains(entt::entity{ENTT_SPARSE_PAGE-1u}));
162     ASSERT_TRUE(set.contains(entt::entity{ENTT_SPARSE_PAGE}));
163 
164     set.shrink_to_fit();
165     set.erase(entt::entity{ENTT_SPARSE_PAGE});
166 
167     ASSERT_EQ(set.extent(), 2 * ENTT_SPARSE_PAGE);
168     ASSERT_FALSE(set.contains(entt::entity{ENTT_SPARSE_PAGE-1u}));
169     ASSERT_FALSE(set.contains(entt::entity{ENTT_SPARSE_PAGE}));
170 
171     set.shrink_to_fit();
172 
173     ASSERT_EQ(set.extent(), 2 * ENTT_SPARSE_PAGE);
174 }
175 
TEST(SparseSet,Emplace)176 TEST(SparseSet, Emplace) {
177     entt::sparse_set set{entt::deletion_policy::in_place};
178     entt::entity entities[2u];
179 
180     entities[0u] = entt::entity{3};
181     entities[1u] = entt::entity{42};
182 
183     ASSERT_TRUE(set.empty());
184 
185     set.emplace(entities[0u]);
186     set.erase(entities[0u]);
187 
188     set.emplace_back(entities[0u]);
189     set.emplace(entities[1u]);
190 
191     ASSERT_DEATH(set.emplace_back(entities[1u]), "");
192     ASSERT_DEATH(set.emplace(entities[0u]), "");
193 
194     ASSERT_EQ(set.at(0u), entities[1u]);
195     ASSERT_EQ(set.at(1u), entities[0u]);
196     ASSERT_EQ(set.index(entities[0u]), 1u);
197     ASSERT_EQ(set.index(entities[1u]), 0u);
198 
199     set.erase(std::begin(entities), std::end(entities));
200     set.emplace(entities[1u]);
201     set.emplace_back(entities[0u]);
202 
203     ASSERT_EQ(set.at(0u), entities[1u]);
204     ASSERT_EQ(set.at(1u), static_cast<entt::entity>(entt::null));
205     ASSERT_EQ(set.at(2u), entities[0u]);
206     ASSERT_EQ(set.index(entities[0u]), 2u);
207     ASSERT_EQ(set.index(entities[1u]), 0u);
208 }
209 
TEST(SparseSet,EmplaceOutOfBounds)210 TEST(SparseSet, EmplaceOutOfBounds) {
211     entt::sparse_set set{entt::deletion_policy::in_place};
212     entt::entity entities[2u]{entt::entity{0}, entt::entity{ENTT_SPARSE_PAGE}};
213 
214     ASSERT_EQ(set.emplace(entities[0u]), 0u);
215     ASSERT_EQ(set.extent(), ENTT_SPARSE_PAGE);
216 
217     set.erase(entities[0u]);
218 
219     ASSERT_EQ(set.emplace(entities[1u]), 0u);
220     ASSERT_EQ(set.extent(), 2u * ENTT_SPARSE_PAGE);
221 }
222 
TEST(SparseSet,Insert)223 TEST(SparseSet, Insert) {
224     entt::sparse_set set{entt::deletion_policy::in_place};
225     entt::entity entities[2u];
226 
227     entities[0u] = entt::entity{3};
228     entities[1u] = entt::entity{42};
229 
230     set.emplace(entt::entity{12});
231     set.insert(std::end(entities), std::end(entities));
232     set.insert(std::begin(entities), std::end(entities));
233     set.emplace(entt::entity{24});
234 
235     ASSERT_TRUE(set.contains(entities[0u]));
236     ASSERT_TRUE(set.contains(entities[1u]));
237     ASSERT_FALSE(set.contains(entt::entity{0}));
238     ASSERT_FALSE(set.contains(entt::entity{9}));
239     ASSERT_TRUE(set.contains(entt::entity{12}));
240     ASSERT_TRUE(set.contains(entt::entity{24}));
241 
242     ASSERT_FALSE(set.empty());
243     ASSERT_EQ(set.size(), 4u);
244     ASSERT_EQ(set.index(entt::entity{12}), 0u);
245     ASSERT_EQ(set.index(entities[0u]), 1u);
246     ASSERT_EQ(set.index(entities[1u]), 2u);
247     ASSERT_EQ(set.index(entt::entity{24}), 3u);
248     ASSERT_EQ(set.data()[set.index(entt::entity{12})], entt::entity{12});
249     ASSERT_EQ(set.data()[set.index(entities[0u])], entities[0u]);
250     ASSERT_EQ(set.data()[set.index(entities[1u])], entities[1u]);
251     ASSERT_EQ(set.data()[set.index(entt::entity{24})], entt::entity{24});
252 
253     set.erase(std::begin(entities), std::end(entities));
254     set.insert(std::rbegin(entities), std::rend(entities));
255 
256     ASSERT_EQ(set.size(), 6u);
257     ASSERT_TRUE(set.at(1u) == entt::tombstone);
258     ASSERT_TRUE(set.at(2u) == entt::tombstone);
259     ASSERT_EQ(set.at(4u), entities[1u]);
260     ASSERT_EQ(set.at(5u), entities[0u]);
261     ASSERT_EQ(set.index(entities[0u]), 5u);
262     ASSERT_EQ(set.index(entities[1u]), 4u);
263 }
264 
TEST(SparseSet,Erase)265 TEST(SparseSet, Erase) {
266     entt::sparse_set set;
267     entt::entity entities[3u];
268 
269     entities[0u] = entt::entity{3};
270     entities[1u] = entt::entity{42};
271     entities[2u] = entt::entity{9};
272 
273     ASSERT_EQ(set.policy(), entt::deletion_policy::swap_and_pop);
274     ASSERT_TRUE(set.empty());
275 
276     ASSERT_DEATH(set.erase(std::begin(entities), std::end(entities)), "");
277     ASSERT_DEATH(set.erase(entities[1u]), "");
278 
279     ASSERT_TRUE(set.empty());
280 
281     set.insert(std::begin(entities), std::end(entities));
282     set.erase(set.begin(), set.end());
283 
284     ASSERT_TRUE(set.empty());
285 
286     set.insert(std::begin(entities), std::end(entities));
287     set.erase(entities, entities + 2u);
288 
289     ASSERT_FALSE(set.empty());
290     ASSERT_EQ(*set.begin(), entities[2u]);
291 
292     set.erase(entities[2u]);
293 
294     ASSERT_DEATH(set.erase(entities[2u]), "");
295     ASSERT_TRUE(set.empty());
296 
297     set.insert(std::begin(entities), std::end(entities));
298     std::swap(entities[1u], entities[2u]);
299     set.erase(entities, entities + 2u);
300 
301     ASSERT_FALSE(set.empty());
302     ASSERT_EQ(*set.begin(), entities[2u]);
303 }
304 
TEST(SparseSet,StableErase)305 TEST(SparseSet, StableErase) {
306     entt::sparse_set set{entt::deletion_policy::in_place};
307     entt::entity entities[3u];
308 
309     entities[0u] = entt::entity{3};
310     entities[1u] = entt::entity{42};
311     entities[2u] = entt::entity{9};
312 
313     ASSERT_EQ(set.policy(), entt::deletion_policy::in_place);
314     ASSERT_TRUE(set.empty());
315     ASSERT_EQ(set.size(), 0u);
316 
317     ASSERT_DEATH(set.erase(std::begin(entities), std::end(entities)), "");
318     ASSERT_DEATH(set.erase(entities[1u]), "");
319 
320     ASSERT_TRUE(set.empty());
321     ASSERT_EQ(set.size(), 0u);
322 
323     set.insert(std::begin(entities), std::end(entities));
324     set.erase(set.begin(), set.end());
325 
326     ASSERT_FALSE(set.empty());
327     ASSERT_EQ(set.size(), 3u);
328     ASSERT_TRUE(set.at(0u) == entt::tombstone);
329     ASSERT_TRUE(set.at(1u) == entt::tombstone);
330     ASSERT_TRUE(set.at(2u) == entt::tombstone);
331     ASSERT_EQ(set.slot(), 0u);
332 
333     set.insert(std::begin(entities), std::end(entities));
334     set.erase(entities, entities + 2u);
335 
336     ASSERT_FALSE(set.empty());
337     ASSERT_EQ(set.size(), 6u);
338     ASSERT_EQ(*set.begin(), entities[2u]);
339     ASSERT_TRUE(set.at(3u) == entt::tombstone);
340     ASSERT_TRUE(set.at(4u) == entt::tombstone);
341     ASSERT_EQ(set.slot(), 4u);
342 
343     set.erase(entities[2u]);
344 
345     ASSERT_DEATH(set.erase(entities[2u]), "");
346     ASSERT_FALSE(set.empty());
347     ASSERT_EQ(set.size(), 6u);
348     ASSERT_EQ(set.slot(), 5u);
349 
350     set.insert(std::begin(entities), std::end(entities));
351     std::swap(entities[1u], entities[2u]);
352     set.erase(entities, entities + 2u);
353 
354     ASSERT_FALSE(set.empty());
355     ASSERT_EQ(set.size(), 9u);
356     ASSERT_TRUE(set.at(6u) == entt::tombstone);
357     ASSERT_EQ(set.at(7u), entities[2u]);
358     ASSERT_EQ(*++set.begin(), entities[2u]);
359     ASSERT_TRUE(set.at(8u) == entt::tombstone);
360     ASSERT_EQ(set.slot(), 8u);
361 
362     set.compact();
363 
364     ASSERT_FALSE(set.empty());
365     ASSERT_EQ(set.size(), 1u);
366     ASSERT_EQ(*set.begin(), entities[2u]);
367     ASSERT_EQ(set.slot(), 1u);
368 
369     set.clear();
370 
371     ASSERT_EQ(set.size(), 0u);
372     ASSERT_EQ(set.slot(), 0u);
373 
374     set.insert(std::begin(entities), std::end(entities));
375     set.erase(entities[2u]);
376 
377     ASSERT_DEATH(set.erase(entities[2u]), "");
378     ASSERT_EQ(set.slot(), 2u);
379 
380     set.erase(entities[0u]);
381     set.erase(entities[1u]);
382 
383     ASSERT_DEATH(set.erase(entities, entities + 2u), "");
384     ASSERT_EQ(set.size(), 3u);
385     ASSERT_TRUE(*set.begin() == entt::tombstone);
386     ASSERT_EQ(set.slot(), 1u);
387 
388     ASSERT_EQ(set.emplace(entities[0u]), 1u);
389     ASSERT_EQ(*++set.begin(), entities[0u]);
390 
391     ASSERT_EQ(set.emplace(entities[1u]), 0u);
392     ASSERT_EQ(set.emplace(entities[2u]), 2u);
393     ASSERT_EQ(set.emplace(entt::entity{0}), 3u);
394 
395     ASSERT_EQ(set.size(), 4u);
396     ASSERT_EQ(*set.begin(), entt::entity{0});
397     ASSERT_EQ(set.at(0u), entities[1u]);
398     ASSERT_EQ(set.at(1u), entities[0u]);
399     ASSERT_EQ(set.at(2u), entities[2u]);
400 }
401 
TEST(SparseSet,Remove)402 TEST(SparseSet, Remove) {
403     entt::sparse_set set;
404     entt::entity entities[3u];
405 
406     entities[0u] = entt::entity{3};
407     entities[1u] = entt::entity{42};
408     entities[2u] = entt::entity{9};
409 
410     ASSERT_EQ(set.policy(), entt::deletion_policy::swap_and_pop);
411     ASSERT_TRUE(set.empty());
412 
413     ASSERT_EQ(set.remove(std::begin(entities), std::end(entities)), 0u);
414     ASSERT_EQ(set.remove(entities[1u]), 0u);
415 
416     ASSERT_TRUE(set.empty());
417 
418     set.insert(std::begin(entities), std::end(entities));
419 
420     ASSERT_EQ(set.remove(set.begin(), set.end()), 3u);
421     ASSERT_TRUE(set.empty());
422 
423     set.insert(std::begin(entities), std::end(entities));
424 
425     ASSERT_EQ(set.remove(entities, entities + 2u), 2u);
426     ASSERT_FALSE(set.empty());
427     ASSERT_EQ(*set.begin(), entities[2u]);
428 
429     ASSERT_EQ(set.remove(entities[2u]), 1u);
430     ASSERT_EQ(set.remove(entities[2u]), 0u);
431     ASSERT_TRUE(set.empty());
432 
433     set.insert(entities, entities + 2u);
434 
435     ASSERT_EQ(set.remove(std::begin(entities), std::end(entities)), 2u);
436     ASSERT_TRUE(set.empty());
437 
438     set.insert(std::begin(entities), std::end(entities));
439     std::swap(entities[1u], entities[2u]);
440 
441     ASSERT_EQ(set.remove(entities, entities + 2u), 2u);
442     ASSERT_FALSE(set.empty());
443     ASSERT_EQ(*set.begin(), entities[2u]);
444 }
445 
TEST(SparseSet,StableRemove)446 TEST(SparseSet, StableRemove) {
447     entt::sparse_set set{entt::deletion_policy::in_place};
448     entt::entity entities[3u];
449 
450     entities[0u] = entt::entity{3};
451     entities[1u] = entt::entity{42};
452     entities[2u] = entt::entity{9};
453 
454     ASSERT_EQ(set.policy(), entt::deletion_policy::in_place);
455     ASSERT_TRUE(set.empty());
456     ASSERT_EQ(set.size(), 0u);
457 
458     ASSERT_EQ(set.remove(std::begin(entities), std::end(entities)), 0u);
459     ASSERT_EQ(set.remove(entities[1u]), 0u);
460 
461     ASSERT_TRUE(set.empty());
462     ASSERT_EQ(set.size(), 0u);
463 
464     set.insert(std::begin(entities), std::end(entities));
465 
466     ASSERT_EQ(set.remove(set.begin(), set.end()), 3u);
467     ASSERT_FALSE(set.empty());
468     ASSERT_EQ(set.size(), 3u);
469     ASSERT_TRUE(set.at(0u) == entt::tombstone);
470     ASSERT_TRUE(set.at(1u) == entt::tombstone);
471     ASSERT_TRUE(set.at(2u) == entt::tombstone);
472     ASSERT_EQ(set.slot(), 0u);
473 
474     set.insert(std::begin(entities), std::end(entities));
475 
476     ASSERT_EQ(set.remove(entities, entities + 2u), 2u);
477     ASSERT_FALSE(set.empty());
478     ASSERT_EQ(set.size(), 6u);
479     ASSERT_EQ(*set.begin(), entt::entity{9});
480     ASSERT_TRUE(set.at(3u) == entt::tombstone);
481     ASSERT_TRUE(set.at(4u) == entt::tombstone);
482     ASSERT_EQ(set.slot(), 4u);
483 
484     ASSERT_EQ(set.remove(entities[2u]), 1u);
485     ASSERT_EQ(set.remove(entities[2u]), 0u);
486     ASSERT_EQ(set.remove(entities[2u]), 0u);
487     ASSERT_EQ(set.remove(entities[2u]), 0u);
488     ASSERT_FALSE(set.empty());
489     ASSERT_EQ(set.size(), 6u);
490     ASSERT_TRUE(*set.begin() == entt::tombstone);
491     ASSERT_EQ(set.slot(), 5u);
492 
493     set.insert(entities, entities + 2u);
494 
495     ASSERT_EQ(set.remove(std::begin(entities), std::end(entities)), 2u);
496     ASSERT_FALSE(set.empty());
497     ASSERT_EQ(set.size(), 8u);
498     ASSERT_TRUE(set.at(6u) == entt::tombstone);
499     ASSERT_TRUE(set.at(7u) == entt::tombstone);
500     ASSERT_EQ(set.slot(), 7u);
501 
502     set.insert(std::begin(entities), std::end(entities));
503     std::swap(entities[1u], entities[2u]);
504 
505     ASSERT_EQ(set.remove(entities, entities + 2u), 2u);
506     ASSERT_FALSE(set.empty());
507     ASSERT_EQ(set.size(), 11u);
508     ASSERT_TRUE(set.at(8u) == entt::tombstone);
509     ASSERT_EQ(set.at(9u), entities[2u]);
510     ASSERT_EQ(*++set.begin(), entities[2u]);
511     ASSERT_TRUE(set.at(10u) == entt::tombstone);
512     ASSERT_EQ(set.slot(), 10u);
513 
514     set.compact();
515 
516     ASSERT_FALSE(set.empty());
517     ASSERT_EQ(set.size(), 1u);
518     ASSERT_EQ(*set.begin(), entities[2u]);
519     ASSERT_EQ(set.slot(), 1u);
520 
521     set.clear();
522 
523     ASSERT_EQ(set.size(), 0u);
524     ASSERT_EQ(set.slot(), 0u);
525 
526     set.insert(std::begin(entities), std::end(entities));
527 
528     ASSERT_EQ(set.remove(entities[2u]), 1u);
529     ASSERT_EQ(set.remove(entities[2u]), 0u);
530 
531     ASSERT_EQ(set.remove(entities[0u]), 1u);
532     ASSERT_EQ(set.remove(entities[1u]), 1u);
533     ASSERT_EQ(set.remove(entities, entities + 2u), 0u);
534 
535     ASSERT_EQ(set.size(), 3u);
536     ASSERT_TRUE(*set.begin() == entt::tombstone);
537     ASSERT_EQ(set.slot(), 1u);
538 
539     ASSERT_EQ(set.emplace(entities[0u]), 1u);
540     ASSERT_EQ(*++set.begin(), entities[0u]);
541 
542     ASSERT_EQ(set.emplace(entities[1u]), 0u);
543     ASSERT_EQ(set.emplace(entities[2u]), 2u);
544     ASSERT_EQ(set.emplace(entt::entity{0}), 3u);
545 
546     ASSERT_EQ(set.size(), 4u);
547     ASSERT_EQ(*set.begin(), entt::entity{0});
548     ASSERT_EQ(set.at(0u), entities[1u]);
549     ASSERT_EQ(set.at(1u), entities[0u]);
550     ASSERT_EQ(set.at(2u), entities[2u]);
551 }
552 
TEST(SparseSet,Compact)553 TEST(SparseSet, Compact) {
554     entt::sparse_set set{entt::deletion_policy::in_place};
555 
556     ASSERT_TRUE(set.empty());
557     ASSERT_EQ(set.size(), 0u);
558 
559     set.compact();
560 
561     ASSERT_TRUE(set.empty());
562     ASSERT_EQ(set.size(), 0u);
563 
564     set.emplace(entt::entity{0});
565     set.compact();
566 
567     ASSERT_FALSE(set.empty());
568     ASSERT_EQ(set.size(), 1u);
569 
570     set.emplace(entt::entity{42});
571     set.erase(entt::entity{0});
572 
573     ASSERT_EQ(set.size(), 2u);
574     ASSERT_EQ(set.index(entt::entity{42}), 1u);
575 
576     set.compact();
577 
578     ASSERT_EQ(set.size(), 1u);
579     ASSERT_EQ(set.index(entt::entity{42}), 0u);
580 
581     set.emplace(entt::entity{0});
582     set.compact();
583 
584     ASSERT_EQ(set.size(), 2u);
585     ASSERT_EQ(set.index(entt::entity{42}), 0u);
586     ASSERT_EQ(set.index(entt::entity{0}), 1u);
587 
588     set.erase(entt::entity{0});
589     set.erase(entt::entity{42});
590     set.compact();
591 
592     ASSERT_TRUE(set.empty());
593 }
594 
TEST(SparseSet,Clear)595 TEST(SparseSet, Clear) {
596     entt::sparse_set set;
597 
598     set.emplace(entt::entity{3});
599     set.emplace(entt::entity{42});
600     set.emplace(entt::entity{9});
601 
602     ASSERT_FALSE(set.empty());
603 
604     set.clear();
605 
606     ASSERT_TRUE(set.empty());
607 }
608 
TEST(SparseSet,Iterator)609 TEST(SparseSet, Iterator) {
610     using iterator = typename entt::sparse_set::iterator;
611 
612     entt::sparse_set set;
613     set.emplace(entt::entity{3});
614 
615     iterator end{set.begin()};
616     iterator begin{};
617     begin = set.end();
618     std::swap(begin, end);
619 
620     ASSERT_EQ(begin, set.begin());
621     ASSERT_EQ(end, set.end());
622     ASSERT_NE(begin, end);
623 
624     ASSERT_EQ(begin++, set.begin());
625     ASSERT_EQ(begin--, set.end());
626 
627     ASSERT_EQ(begin+1, set.end());
628     ASSERT_EQ(end-1, set.begin());
629 
630     ASSERT_EQ(++begin, set.end());
631     ASSERT_EQ(--begin, set.begin());
632 
633     ASSERT_EQ(begin += 1, set.end());
634     ASSERT_EQ(begin -= 1, set.begin());
635 
636     ASSERT_EQ(begin + (end - begin), set.end());
637     ASSERT_EQ(begin - (begin - end), set.end());
638 
639     ASSERT_EQ(end - (end - begin), set.begin());
640     ASSERT_EQ(end + (begin - end), set.begin());
641 
642     ASSERT_EQ(begin[0u], *set.begin());
643 
644     ASSERT_LT(begin, end);
645     ASSERT_LE(begin, set.begin());
646 
647     ASSERT_GT(end, begin);
648     ASSERT_GE(end, set.end());
649 
650     ASSERT_EQ(*begin, entt::entity{3});
651     ASSERT_EQ(*begin.operator->(), entt::entity{3});
652 }
653 
TEST(SparseSet,ReverseIterator)654 TEST(SparseSet, ReverseIterator) {
655     using reverse_iterator = typename entt::sparse_set::reverse_iterator;
656 
657     entt::sparse_set set;
658     set.emplace(entt::entity{3});
659 
660     reverse_iterator end{set.rbegin()};
661     reverse_iterator begin{};
662     begin = set.rend();
663     std::swap(begin, end);
664 
665     ASSERT_EQ(begin, set.rbegin());
666     ASSERT_EQ(end, set.rend());
667     ASSERT_NE(begin, end);
668 
669     ASSERT_EQ(begin++, set.rbegin());
670     ASSERT_EQ(begin--, set.rend());
671 
672     ASSERT_EQ(begin+1, set.rend());
673     ASSERT_EQ(end-1, set.rbegin());
674 
675     ASSERT_EQ(++begin, set.rend());
676     ASSERT_EQ(--begin, set.rbegin());
677 
678     ASSERT_EQ(begin += 1, set.rend());
679     ASSERT_EQ(begin -= 1, set.rbegin());
680 
681     ASSERT_EQ(begin + (end - begin), set.rend());
682     ASSERT_EQ(begin - (begin - end), set.rend());
683 
684     ASSERT_EQ(end - (end - begin), set.rbegin());
685     ASSERT_EQ(end + (begin - end), set.rbegin());
686 
687     ASSERT_EQ(begin[0u], *set.rbegin());
688 
689     ASSERT_LT(begin, end);
690     ASSERT_LE(begin, set.rbegin());
691 
692     ASSERT_GT(end, begin);
693     ASSERT_GE(end, set.rend());
694 
695     ASSERT_EQ(*begin, entt::entity{3});
696 }
697 
TEST(SparseSet,Find)698 TEST(SparseSet, Find) {
699     entt::sparse_set set;
700     set.emplace(entt::entity{3});
701     set.emplace(entt::entity{42});
702     set.emplace(entt::entity{99});
703 
704     ASSERT_NE(set.find(entt::entity{3}), set.end());
705     ASSERT_NE(set.find(entt::entity{42}), set.end());
706     ASSERT_NE(set.find(entt::entity{99}), set.end());
707     ASSERT_EQ(set.find(entt::entity{0}), set.end());
708 
709     auto it = set.find(entt::entity{99});
710 
711     ASSERT_EQ(*it, entt::entity{99});
712     ASSERT_EQ(*(++it), entt::entity{42});
713     ASSERT_EQ(*(++it), entt::entity{3});
714     ASSERT_EQ(++it, set.end());
715     ASSERT_EQ(++set.find(entt::entity{3}), set.end());
716 }
717 
TEST(SparseSet,Data)718 TEST(SparseSet, Data) {
719     entt::sparse_set set;
720 
721     set.emplace(entt::entity{3});
722     set.emplace(entt::entity{12});
723     set.emplace(entt::entity{42});
724 
725     ASSERT_EQ(set.index(entt::entity{3}), 0u);
726     ASSERT_EQ(set.index(entt::entity{12}), 1u);
727     ASSERT_EQ(set.index(entt::entity{42}), 2u);
728 
729     ASSERT_EQ(set.data()[0u], entt::entity{3});
730     ASSERT_EQ(set.data()[1u], entt::entity{12});
731     ASSERT_EQ(set.data()[2u], entt::entity{42});
732 }
733 
TEST(SparseSet,SortOrdered)734 TEST(SparseSet, SortOrdered) {
735     entt::sparse_set set;
736     entt::entity entities[5u]{entt::entity{42}, entt::entity{12}, entt::entity{9}, entt::entity{7}, entt::entity{3}};
737 
738     set.insert(std::begin(entities), std::end(entities));
739     set.sort(std::less{});
740 
741     ASSERT_TRUE(std::equal(std::rbegin(entities), std::rend(entities), set.begin(), set.end()));
742 }
743 
TEST(SparseSet,SortReverse)744 TEST(SparseSet, SortReverse) {
745     entt::sparse_set set;
746     entt::entity entities[5u]{entt::entity{3}, entt::entity{7}, entt::entity{9}, entt::entity{12}, entt::entity{42}};
747 
748     set.insert(std::begin(entities), std::end(entities));
749     set.sort(std::less{});
750 
751     ASSERT_TRUE(std::equal(std::begin(entities), std::end(entities), set.begin(), set.end()));
752 }
753 
TEST(SparseSet,SortUnordered)754 TEST(SparseSet, SortUnordered) {
755     entt::sparse_set set;
756     entt::entity entities[5u]{entt::entity{9}, entt::entity{7}, entt::entity{3}, entt::entity{12}, entt::entity{42}};
757 
758     set.insert(std::begin(entities), std::end(entities));
759     set.sort(std::less{});
760 
761     auto begin = set.begin();
762     auto end = set.end();
763 
764     ASSERT_EQ(*(begin++), entt::entity{3});
765     ASSERT_EQ(*(begin++), entt::entity{7});
766     ASSERT_EQ(*(begin++), entt::entity{9});
767     ASSERT_EQ(*(begin++), entt::entity{12});
768     ASSERT_EQ(*(begin++), entt::entity{42});
769     ASSERT_EQ(begin, end);
770 }
771 
TEST(SparseSet,SortRange)772 TEST(SparseSet, SortRange) {
773     entt::sparse_set set;
774     entt::entity entities[5u]{entt::entity{7}, entt::entity{9}, entt::entity{3}, entt::entity{12}, entt::entity{42}};
775 
776     set.insert(std::begin(entities), std::end(entities));
777     set.sort_n(0u, std::less{});
778 
779     ASSERT_TRUE(std::equal(std::rbegin(entities), std::rend(entities), set.begin(), set.end()));
780 
781     set.sort_n(2u, std::less{});
782 
783     ASSERT_EQ(set.data()[0u], entt::entity{9});
784     ASSERT_EQ(set.data()[1u], entt::entity{7});
785     ASSERT_EQ(set.data()[2u], entt::entity{3});
786 
787     set.sort_n(5u, std::less{});
788 
789     auto begin = set.begin();
790     auto end = set.end();
791 
792     ASSERT_EQ(*(begin++), entt::entity{3});
793     ASSERT_EQ(*(begin++), entt::entity{7});
794     ASSERT_EQ(*(begin++), entt::entity{9});
795     ASSERT_EQ(*(begin++), entt::entity{12});
796     ASSERT_EQ(*(begin++), entt::entity{42});
797     ASSERT_EQ(begin, end);
798 }
799 
TEST(SparseSet,RespectDisjoint)800 TEST(SparseSet, RespectDisjoint) {
801     entt::sparse_set lhs;
802     entt::sparse_set rhs;
803 
804     entt::entity lhs_entities[3u]{entt::entity{3}, entt::entity{12}, entt::entity{42}};
805     lhs.insert(std::begin(lhs_entities), std::end(lhs_entities));
806 
807     ASSERT_TRUE(std::equal(std::rbegin(lhs_entities), std::rend(lhs_entities), lhs.begin(), lhs.end()));
808 
809     lhs.respect(rhs);
810 
811     ASSERT_TRUE(std::equal(std::rbegin(lhs_entities), std::rend(lhs_entities), lhs.begin(), lhs.end()));
812 }
813 
TEST(SparseSet,RespectOverlap)814 TEST(SparseSet, RespectOverlap) {
815     entt::sparse_set lhs;
816     entt::sparse_set rhs;
817 
818     entt::entity lhs_entities[3u]{entt::entity{3}, entt::entity{12}, entt::entity{42}};
819     lhs.insert(std::begin(lhs_entities), std::end(lhs_entities));
820 
821     entt::entity rhs_entities[1u]{entt::entity{12}};
822     rhs.insert(std::begin(rhs_entities), std::end(rhs_entities));
823 
824     ASSERT_TRUE(std::equal(std::rbegin(lhs_entities), std::rend(lhs_entities), lhs.begin(), lhs.end()));
825     ASSERT_TRUE(std::equal(std::rbegin(rhs_entities), std::rend(rhs_entities), rhs.begin(), rhs.end()));
826 
827     lhs.respect(rhs);
828 
829     auto begin = lhs.begin();
830     auto end = lhs.end();
831 
832     ASSERT_EQ(*(begin++), entt::entity{12});
833     ASSERT_EQ(*(begin++), entt::entity{42});
834     ASSERT_EQ(*(begin++), entt::entity{3});
835     ASSERT_EQ(begin, end);
836 }
837 
TEST(SparseSet,RespectOrdered)838 TEST(SparseSet, RespectOrdered) {
839     entt::sparse_set lhs;
840     entt::sparse_set rhs;
841 
842     entt::entity lhs_entities[5u]{entt::entity{1}, entt::entity{2}, entt::entity{3}, entt::entity{4}, entt::entity{5}};
843     lhs.insert(std::begin(lhs_entities), std::end(lhs_entities));
844 
845     entt::entity rhs_entities[6u]{entt::entity{6}, entt::entity{1}, entt::entity{2}, entt::entity{3}, entt::entity{4}, entt::entity{5}};
846     rhs.insert(std::begin(rhs_entities), std::end(rhs_entities));
847 
848     ASSERT_TRUE(std::equal(std::rbegin(lhs_entities), std::rend(lhs_entities), lhs.begin(), lhs.end()));
849     ASSERT_TRUE(std::equal(std::rbegin(rhs_entities), std::rend(rhs_entities), rhs.begin(), rhs.end()));
850 
851     rhs.respect(lhs);
852 
853     ASSERT_TRUE(std::equal(std::rbegin(rhs_entities), std::rend(rhs_entities), rhs.begin(), rhs.end()));
854 }
855 
TEST(SparseSet,RespectReverse)856 TEST(SparseSet, RespectReverse) {
857     entt::sparse_set lhs;
858     entt::sparse_set rhs;
859 
860     entt::entity lhs_entities[5u]{entt::entity{1}, entt::entity{2}, entt::entity{3}, entt::entity{4}, entt::entity{5}};
861     lhs.insert(std::begin(lhs_entities), std::end(lhs_entities));
862 
863     entt::entity rhs_entities[6u]{entt::entity{5}, entt::entity{4}, entt::entity{3}, entt::entity{2}, entt::entity{1}, entt::entity{6}};
864     rhs.insert(std::begin(rhs_entities), std::end(rhs_entities));
865 
866     ASSERT_TRUE(std::equal(std::rbegin(lhs_entities), std::rend(lhs_entities), lhs.begin(), lhs.end()));
867     ASSERT_TRUE(std::equal(std::rbegin(rhs_entities), std::rend(rhs_entities), rhs.begin(), rhs.end()));
868 
869     rhs.respect(lhs);
870 
871     auto begin = rhs.begin();
872     auto end = rhs.end();
873 
874     ASSERT_EQ(*(begin++), entt::entity{5});
875     ASSERT_EQ(*(begin++), entt::entity{4});
876     ASSERT_EQ(*(begin++), entt::entity{3});
877     ASSERT_EQ(*(begin++), entt::entity{2});
878     ASSERT_EQ(*(begin++), entt::entity{1});
879     ASSERT_EQ(*(begin++), entt::entity{6});
880     ASSERT_EQ(begin, end);
881 }
882 
TEST(SparseSet,RespectUnordered)883 TEST(SparseSet, RespectUnordered) {
884     entt::sparse_set lhs;
885     entt::sparse_set rhs;
886 
887     entt::entity lhs_entities[5u]{entt::entity{1}, entt::entity{2}, entt::entity{3}, entt::entity{4}, entt::entity{5}};
888     lhs.insert(std::begin(lhs_entities), std::end(lhs_entities));
889 
890     entt::entity rhs_entities[6u]{entt::entity{3}, entt::entity{2}, entt::entity{6}, entt::entity{1}, entt::entity{4}, entt::entity{5}};
891     rhs.insert(std::begin(rhs_entities), std::end(rhs_entities));
892 
893     ASSERT_TRUE(std::equal(std::rbegin(lhs_entities), std::rend(lhs_entities), lhs.begin(), lhs.end()));
894     ASSERT_TRUE(std::equal(std::rbegin(rhs_entities), std::rend(rhs_entities), rhs.begin(), rhs.end()));
895 
896     rhs.respect(lhs);
897 
898     auto begin = rhs.begin();
899     auto end = rhs.end();
900 
901     ASSERT_EQ(*(begin++), entt::entity{5});
902     ASSERT_EQ(*(begin++), entt::entity{4});
903     ASSERT_EQ(*(begin++), entt::entity{3});
904     ASSERT_EQ(*(begin++), entt::entity{2});
905     ASSERT_EQ(*(begin++), entt::entity{1});
906     ASSERT_EQ(*(begin++), entt::entity{6});
907     ASSERT_EQ(begin, end);
908 }
909 
TEST(SparseSet,CanModifyDuringIteration)910 TEST(SparseSet, CanModifyDuringIteration) {
911     entt::sparse_set set;
912     set.emplace(entt::entity{0});
913 
914     ASSERT_EQ(set.capacity(), 1u);
915 
916     const auto it = set.begin();
917     set.reserve(2u);
918 
919     ASSERT_EQ(set.capacity(), 2u);
920 
921     // this should crash with asan enabled if we break the constraint
922     const auto entity = *it;
923     (void)entity;
924 }
925 
TEST(SparseSet,ThrowingAllocator)926 TEST(SparseSet, ThrowingAllocator) {
927     entt::basic_sparse_set<entt::entity, test::throwing_allocator<entt::entity>> set{};
928 
929     test::throwing_allocator<entt::entity>::trigger_on_allocate = true;
930 
931     // strong exception safety
932     ASSERT_THROW(set.reserve(1u), test::throwing_allocator<entt::entity>::exception_type);
933     ASSERT_EQ(set.capacity(), 0u);
934     ASSERT_EQ(set.extent(), 0u);
935 
936     test::throwing_allocator<entt::entity>::trigger_on_allocate = true;
937 
938     // strong exception safety
939     ASSERT_THROW(set.emplace(entt::entity{0}), test::throwing_allocator<entt::entity>::exception_type);
940     ASSERT_EQ(set.capacity(), 0u);
941     ASSERT_EQ(set.extent(), 0u);
942 
943     set.emplace(entt::entity{0});
944     test::throwing_allocator<entt::entity>::trigger_on_allocate = true;
945 
946     // strong exception safety
947     ASSERT_THROW(set.reserve(2u), test::throwing_allocator<entt::entity>::exception_type);
948     ASSERT_EQ(set.capacity(), 1u);
949     ASSERT_EQ(set.extent(), ENTT_SPARSE_PAGE);
950     ASSERT_TRUE(set.contains(entt::entity{0}));
951 
952     entt::entity entities[2u]{entt::entity{1}, entt::entity{ENTT_SPARSE_PAGE}};
953     test::throwing_allocator<entt::entity>::trigger_after_allocate = true;
954 
955     // basic exception safety
956     ASSERT_THROW(set.insert(std::begin(entities), std::end(entities)), test::throwing_allocator<entt::entity>::exception_type);
957     ASSERT_EQ(set.capacity(), 3u);
958     ASSERT_EQ(set.size(), 2u);
959     ASSERT_EQ(set.extent(), 2 * ENTT_SPARSE_PAGE);
960     ASSERT_TRUE(set.contains(entt::entity{0}));
961     ASSERT_TRUE(set.contains(entt::entity{1}));
962     ASSERT_FALSE(set.contains(entt::entity{ENTT_SPARSE_PAGE}));
963 
964     set.emplace(entities[1u]);
965 
966     ASSERT_TRUE(set.contains(entt::entity{ENTT_SPARSE_PAGE}));
967 
968     // unnecessary but they test a bit of template machinery :)
969     set.clear();
970     set.shrink_to_fit();
971     set = decltype(set){};
972 }
973