souffle  2.0.2-371-g6315b36
brie_test.cpp
Go to the documentation of this file.
1 /*
2  * Souffle - A Datalog Compiler
3  * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved
4  * Licensed under the Universal Permissive License v 1.0 as shown at:
5  * - https://opensource.org/licenses/UPL
6  * - <souffle root>/licenses/SOUFFLE-UPL.txt
7  */
8 
9 /************************************************************************
10  *
11  * @file brie_test.cpp
12  *
13  * A test case testing the trie implementation.
14  *
15  ***********************************************************************/
16 
17 #include "tests/test.h"
18 
19 #include "souffle/RamTypes.h"
20 #include "souffle/datastructure/Brie.h"
21 #include "souffle/utility/ContainerUtil.h"
22 #include "souffle/utility/StreamUtil.h"
23 #include "souffle/utility/StringUtil.h"
24 #include <algorithm>
25 #include <bitset>
26 #include <cstdint>
27 #include <cstdlib>
28 #include <iostream>
29 #include <limits>
30 #include <random>
31 #include <set>
32 #include <string>
33 #include <type_traits>
34 #include <utility>
35 #include <vector>
36 
37 namespace souffle {
38 
39 TEST(SparseArray, Basic) {
40  SparseArray<int> map;
41 
42  EXPECT_EQ(0, map[10]);
43  EXPECT_EQ(0, map[12]);
44  EXPECT_EQ(0, map[14]);
45  EXPECT_EQ(0, map[120]);
46 
47  EXPECT_EQ(0, map[10]);
48  EXPECT_EQ(0, map[12]);
49  EXPECT_EQ(0, map[14]);
50  EXPECT_EQ(0, map[120]);
51 
52  map.update(12, 1);
53 
54  EXPECT_EQ(0, map[10]);
55  EXPECT_EQ(1, map[12]);
56  EXPECT_EQ(0, map[14]);
57  EXPECT_EQ(0, map[120]);
58 
59  map.update(14, 8);
60 
61  EXPECT_EQ(0, map[10]);
62  EXPECT_EQ(1, map[12]);
63  EXPECT_EQ(8, map[14]);
64  EXPECT_EQ(0, map[120]);
65 
66  map.update(120, 4);
67 
68  EXPECT_EQ(0, map[10]);
69  EXPECT_EQ(1, map[12]);
70  EXPECT_EQ(8, map[14]);
71  EXPECT_EQ(4, map[120]);
72 }
73 
74 TEST(SparseArray, Limits) {
75  SparseArray<int> map;
76 
77  map.update(std::numeric_limits<typename SparseArray<int>::index_type>::min(), 10);
78  map.update(std::numeric_limits<typename SparseArray<int>::index_type>::max(), 20);
79 
80  map.dump();
81 
82  std::vector<std::pair<uint32_t, int>> present;
83  for (const auto& cur : map) {
84  present.push_back(cur);
85  }
86 
87  EXPECT_EQ("[(0,10),(4294967295,20)]", toString(present));
88 }
89 
90 TEST(SparseArray, Iterator) {
91  SparseArray<int> map;
92 
93  std::set<std::pair<int, int>> should;
94  should.insert(std::make_pair(14, 4));
95  should.insert(std::make_pair(0, 1));
96  should.insert(std::make_pair(4, 2));
97  should.insert(std::make_pair(38, 5));
98  should.insert(std::make_pair(12, 3));
99  should.insert(std::make_pair(120, 6));
100 
101  for (const auto& cur : should) {
102  map.update(cur.first, cur.second);
103  }
104 
105  std::set<std::pair<int, int>> is;
106  for (const auto& cur : map) {
107  is.insert(cur);
108  }
109 
110  EXPECT_EQ(should, is);
111 }
112 
113 TEST(SparseArray, IteratorStress) {
114  const static int N = 10000;
115 
116  SparseArray<int> map;
117 
118  std::vector<int> pos;
119  while (pos.size() < N) {
120  int n = random() % (N * 10);
121  if (!contains(pos, n)) {
122  pos.push_back(n);
123  }
124  }
125 
126  std::set<std::pair<int, int>> should;
127  for (int i = 0; i < N; i++) {
128  should.insert(std::make_pair(pos[i], i + 1));
129  }
130 
131  for (const auto& cur : should) {
132  map.update(cur.first, cur.second);
133  ASSERT_TRUE(map[cur.first] == cur.second);
134  }
135 
136  std::set<std::pair<int, int>> is;
137  for (const auto& cur : map) {
138  is.insert(cur);
139  }
140 
141  EXPECT_EQ(should, is);
142 }
143 
144 TEST(SparseArray, IteratorStress2) {
145  const static int N = 1000;
146 
147  bool log = false;
148 
149  for (unsigned j = 0; j < N; j++) {
150  SparseArray<int> map;
151 
152  if (log) std::cout << "Creating " << j << " random numbers ..\n";
153  std::vector<int> pos;
154  while (pos.size() < j) {
155  int n = random() % (N * 10);
156  if (!contains(pos, n)) {
157  pos.push_back(n);
158  }
159  }
160 
161  if (log) std::cout << "Creating input list ..\n";
162  std::set<std::pair<int, int>> should;
163  for (unsigned i = 0; i < j; i++) {
164  should.insert(std::make_pair(pos[i], i + 1));
165  }
166 
167  if (log) std::cout << "Filling in input list ..\n";
168  for (const auto& cur : should) {
169  map.update(cur.first, cur.second);
170  ASSERT_TRUE(map[cur.first] == cur.second);
171  }
172 
173  if (log) std::cout << "Sort should list ..\n";
174 
175  if (log) std::cout << "Collect is list ..\n";
176  std::set<std::pair<int, int>> is;
177  unsigned i = 0;
178  for (const auto& cur : map) {
179  is.insert(cur);
180  i++;
181  ASSERT_LE(i, j);
182  }
183 
184  if (log) std::cout << "Comparing lists ..\n";
185  EXPECT_EQ(should, is);
186  if (log) std::cout << "Done\n\n";
187  }
188 }
189 
190 TEST(SparseArray, Find) {
191  SparseArray<int> map;
192 
193  EXPECT_EQ(map.end(), map.find(1));
194  EXPECT_EQ(map.end(), map.find(12));
195  EXPECT_EQ(map.end(), map.find(1400));
196 
197  map.update(1400, 1);
198 
199  EXPECT_EQ(map.end(), map.find(1));
200  EXPECT_EQ(map.end(), map.find(12));
201  EXPECT_NE(map.end(), map.find(1400));
202 
203  EXPECT_EQ("(1400,1)", toString(*map.find(1400)));
204 
205  map.update(12, 2);
206 
207  EXPECT_EQ(map.end(), map.find(1));
208  EXPECT_NE(map.end(), map.find(12));
209  EXPECT_NE(map.end(), map.find(1400));
210 
211  EXPECT_EQ("(12,2)", toString(*map.find(12)));
212  EXPECT_EQ("(1400,1)", toString(*map.find(1400)));
213 
214  auto it = map.find(12);
215  EXPECT_EQ("(12,2)", toString(*it));
216  ++it;
217  EXPECT_EQ("(1400,1)", toString(*it));
218 }
219 
220 TEST(SparseArray, Find2) {
221  SparseArray<int> a;
222 
223  EXPECT_EQ(a.end(), a.find(12));
224  EXPECT_EQ(a.end(), a.find(14));
225  EXPECT_EQ(a.end(), a.find(16));
226 
227  a.update(14, 4);
228 
229  EXPECT_EQ(a.end(), a.find(12));
230  EXPECT_NE(a.end(), a.find(14));
231  EXPECT_EQ(a.end(), a.find(16));
232 
233  a.update(16, 6);
234 
235  EXPECT_EQ(a.end(), a.find(12));
236  EXPECT_NE(a.end(), a.find(14));
237  EXPECT_NE(a.end(), a.find(16));
238 }
239 
240 TEST(SparseArray, Copy) {
241  SparseArray<int> m;
242 
243  m.update(12, 1);
244  m.update(14, 2);
245  m.update(16, 3);
246 
247  auto a = m;
248 
249  EXPECT_EQ(1, m[12]);
250  EXPECT_EQ(2, m[14]);
251  EXPECT_EQ(3, m[16]);
252 
253  EXPECT_EQ(1, a[12]);
254  EXPECT_EQ(2, a[14]);
255  EXPECT_EQ(3, a[16]);
256 
257  m = a;
258 
259  EXPECT_EQ(1, m[12]);
260  EXPECT_EQ(2, m[14]);
261  EXPECT_EQ(3, m[16]);
262 
263  EXPECT_EQ(1, a[12]);
264  EXPECT_EQ(2, a[14]);
265  EXPECT_EQ(3, a[16]);
266 }
267 
268 TEST(SparseArray, Merge) {
269  // tests whether the first reference is properly updated while merging sets
270 
271  SparseArray<int> m1;
272  SparseArray<int> m2;
273 
274  m1.update(500, 2);
275  m2.update(100, 1);
276 
277  m1.addAll(m2);
278 
279  std::vector<std::pair<int, int>> data;
280  for (const auto& it : m1) {
281  data.push_back(it);
282  }
283  EXPECT_EQ("[(100,1),(500,2)]", toString(data));
284 }
285 
286 TEST(SparseArray, LowerBound) {
287  SparseArray<int> m;
288 
289  EXPECT_EQ(m.end(), m.lowerBound(0));
290  EXPECT_EQ(m.end(), m.lowerBound(10));
291  EXPECT_EQ(m.end(), m.lowerBound(12));
292  EXPECT_EQ(m.end(), m.lowerBound(14));
293  EXPECT_EQ(m.end(), m.lowerBound(400));
294  EXPECT_EQ(m.end(), m.lowerBound(500));
295 
296  m.update(11, 120);
297  m.dump();
298  EXPECT_EQ(m.begin(), m.lowerBound(0));
299  EXPECT_EQ(m.find(11), m.lowerBound(10));
300  EXPECT_EQ(m.end(), m.lowerBound(12));
301  EXPECT_EQ(m.end(), m.lowerBound(14));
302  EXPECT_EQ(m.end(), m.lowerBound(400));
303  EXPECT_EQ(m.end(), m.lowerBound(500));
304 
305  m.update(12, 140);
306  m.dump();
307  EXPECT_EQ(m.begin(), m.lowerBound(0));
308  EXPECT_EQ(m.find(11), m.lowerBound(10));
309  EXPECT_EQ(m.find(12), m.lowerBound(12));
310  EXPECT_EQ(m.end(), m.lowerBound(14));
311  EXPECT_EQ(m.end(), m.lowerBound(400));
312  EXPECT_EQ(m.end(), m.lowerBound(500));
313 
314  m.update(300, 150);
315  m.dump();
316  EXPECT_EQ(m.begin(), m.lowerBound(0));
317  EXPECT_EQ(m.find(11), m.lowerBound(10));
318  EXPECT_EQ(m.find(12), m.lowerBound(12));
319  EXPECT_EQ(m.find(300), m.lowerBound(14));
320  EXPECT_EQ(m.end(), m.lowerBound(400));
321  EXPECT_EQ(m.end(), m.lowerBound(500));
322 
323  m.update(450, 160);
324  m.dump();
325  EXPECT_EQ(m.begin(), m.lowerBound(0));
326  EXPECT_EQ(m.find(11), m.lowerBound(10));
327  EXPECT_EQ(m.find(12), m.lowerBound(12));
328  EXPECT_EQ(m.find(300), m.lowerBound(14));
329  std::cout << "\n";
330  EXPECT_EQ(m.find(450), m.lowerBound(400));
331  EXPECT_EQ(m.end(), m.lowerBound(500));
332 }
333 
334 TEST(SparseArray, LowerBound2) {
335  for (uint32_t m = 0; m < 256; ++m) {
336  SparseArray<uint32_t> a;
337  std::set<uint32_t> r;
338 
339  for (uint32_t i = 0; i < 8; i++) {
340  if (!(m & (1 << i))) {
341  continue;
342  }
343  a.update(i * 100, 10);
344  r.insert(i * 100);
345  }
346 
347  for (uint32_t i = 0; i < 10; i++) {
348  auto a_res = a.lowerBound(i * 100);
349  auto r_res = r.lower_bound(i * 100);
350 
351  EXPECT_EQ(a_res == a.end(), r_res == r.end()) << "\nm=" << std::bitset<8>(m) << "\ni=" << i;
352 
353  if (a_res == a.end()) {
354  continue;
355  }
356 
357  EXPECT_EQ(a_res->first, *r_res) << "\nm=" << std::bitset<8>(m) << "\ni=" << i;
358  }
359  }
360 }
361 
362 TEST(SparseArray, UpperBound) {
363  SparseArray<int> m;
364 
365  EXPECT_EQ(m.end(), m.upperBound(0));
366  EXPECT_EQ(m.end(), m.upperBound(10));
367  EXPECT_EQ(m.end(), m.upperBound(12));
368  EXPECT_EQ(m.end(), m.upperBound(14));
369  EXPECT_EQ(m.end(), m.upperBound(400));
370  EXPECT_EQ(m.end(), m.upperBound(500));
371 
372  m.update(11, 120);
373  m.dump();
374  EXPECT_EQ(m.begin(), m.upperBound(0));
375  EXPECT_EQ(m.find(11), m.upperBound(10));
376  EXPECT_EQ(m.end(), m.upperBound(11));
377  EXPECT_EQ(m.end(), m.upperBound(12));
378  EXPECT_EQ(m.end(), m.upperBound(14));
379  EXPECT_EQ(m.end(), m.upperBound(400));
380  EXPECT_EQ(m.end(), m.upperBound(500));
381 
382  m.update(12, 140);
383  m.dump();
384  EXPECT_EQ(m.begin(), m.upperBound(0));
385  EXPECT_EQ(m.find(11), m.upperBound(10));
386  EXPECT_EQ(m.find(12), m.upperBound(11));
387  EXPECT_EQ(m.end(), m.upperBound(12));
388  EXPECT_EQ(m.end(), m.upperBound(14));
389  EXPECT_EQ(m.end(), m.upperBound(400));
390  EXPECT_EQ(m.end(), m.upperBound(500));
391 
392  m.update(300, 150);
393  m.dump();
394  EXPECT_EQ(m.begin(), m.upperBound(0));
395  EXPECT_EQ(m.find(11), m.upperBound(10));
396  EXPECT_EQ(m.find(12), m.upperBound(11));
397  EXPECT_EQ(m.find(300), m.upperBound(12));
398  EXPECT_EQ(m.find(300), m.upperBound(14));
399  EXPECT_EQ(m.end(), m.upperBound(400));
400  EXPECT_EQ(m.end(), m.upperBound(500));
401 
402  m.update(450, 160);
403  m.dump();
404  EXPECT_EQ(m.begin(), m.upperBound(0));
405  EXPECT_EQ(m.find(11), m.upperBound(10));
406  EXPECT_EQ(m.find(12), m.upperBound(11));
407  EXPECT_EQ(m.find(300), m.upperBound(12));
408  EXPECT_EQ(m.find(300), m.upperBound(14));
409  std::cout << "\n";
410  EXPECT_EQ(m.find(450), m.upperBound(400));
411  EXPECT_EQ(m.end(), m.upperBound(500));
412 }
413 
414 TEST(SparseArray, UpperBound2) {
415  for (uint32_t m = 0; m < 256; ++m) {
416  SparseArray<uint32_t> a;
417  std::set<uint32_t> r;
418 
419  for (uint32_t i = 0; i < 8; i++) {
420  if (!(m & (1 << i))) {
421  continue;
422  }
423  a.update(i * 100, 10);
424  r.insert(i * 100);
425  }
426 
427  for (uint32_t i = 0; i < 10; i++) {
428  auto a_res = a.upperBound(i * 100);
429  auto r_res = r.upper_bound(i * 100);
430 
431  EXPECT_EQ(a_res == a.end(), r_res == r.end()) << "\nm=" << std::bitset<8>(m) << "\ni=" << i;
432 
433  if (a_res == a.end()) {
434  continue;
435  }
436 
437  EXPECT_EQ(a_res->first, *r_res) << "\nm=" << std::bitset<8>(m) << "\ni=" << i;
438  }
439  }
440 }
441 
442 TEST(SparseArray, MemoryUsage) {
443  if (sizeof(void*) > 4) {
444  SparseArray<int> a;
445 
446  // an empty one should be small
447  EXPECT_TRUE(a.empty());
448  // EXPECT_EQ(56, a.getMemoryUsage());
449  EXPECT_EQ(40, a.getMemoryUsage());
450 
451  // a single element should have the same size as an empty one
452  a.update(12, 15);
453  EXPECT_FALSE(a.empty());
454  // EXPECT_EQ(56, a.getMemoryUsage());
455  EXPECT_EQ(560, a.getMemoryUsage());
456 
457  // more than one => there are nodes
458  a.update(14, 18);
459  EXPECT_FALSE(a.empty());
460 
461  // EXPECT_EQ(576, a.getMemoryUsage());
462  EXPECT_EQ(560, a.getMemoryUsage());
463  } else {
464  SparseArray<int> a;
465 
466  // an empty one should be small
467  EXPECT_TRUE(a.empty());
468  EXPECT_EQ(28, a.getMemoryUsage());
469 
470  // a single element should have the same size as an empty one
471  a.update(12, 15);
472  EXPECT_FALSE(a.empty());
473  EXPECT_EQ(288, a.getMemoryUsage());
474 
475  // more than one => there are nodes
476  a.update(14, 18);
477  EXPECT_FALSE(a.empty());
478  EXPECT_EQ(288, a.getMemoryUsage());
479  }
480 }
481 
482 TEST(SparseBitMap, Basic) {
483  SparseBitMap<> map;
484 
485  EXPECT_EQ(sizeof(std::bitset<sizeof(void*) * 8>), sizeof(void*));
486 
487  EXPECT_FALSE(map[12]);
488  EXPECT_FALSE(map[120]);
489  EXPECT_FALSE(map[84]);
490 
491  map.set(12);
492 
493  EXPECT_TRUE(map[12]);
494  EXPECT_FALSE(map[120]);
495  EXPECT_FALSE(map[84]);
496 
497  map.set(120);
498 
499  EXPECT_TRUE(map[12]);
500  EXPECT_TRUE(map[120]);
501  EXPECT_FALSE(map[84]);
502 
503  map.set(84);
504 
505  EXPECT_TRUE(map[12]);
506  EXPECT_TRUE(map[120]);
507  EXPECT_TRUE(map[84]);
508 }
509 
510 TEST(SparseBitMap, Stress) {
511  const static int N = 10000;
512 
513  SparseBitMap<> map;
514 
515  std::vector<int> should;
516  while (should.size() < N) {
517  int n = random() % (N * 10);
518  if (!contains(should, n)) {
519  should.push_back(n);
520  }
521  }
522 
523  for (const auto& cur : should) {
524  map.set(cur);
525  ASSERT_TRUE(map[cur]);
526  }
527 
528  // check all the entries
529  for (int i = 0; i < N * 10; i++) {
530  EXPECT_EQ(map[i], contains(should, i));
531  }
532 }
533 
534 TEST(SparseBitMap, Iterator) {
535  SparseBitMap<> map;
536 
537  std::set<int> vals;
538  for (const auto& cur : map) {
539  vals.insert(cur);
540  }
541 
542  EXPECT_EQ("{}", toString(vals));
543 
544  map.set(12);
545 
546  vals.clear();
547  for (const auto& cur : map) {
548  vals.insert(cur);
549  }
550 
551  EXPECT_EQ("{12}", toString(vals));
552 
553  map.set(12);
554  map.set(120);
555 
556  vals.clear();
557  for (const auto& cur : map) {
558  vals.insert(cur);
559  }
560 
561  EXPECT_EQ("{12,120}", toString(vals));
562 
563  map.set(1234);
564 
565  vals.clear();
566  for (const auto& cur : map) {
567  vals.insert(cur);
568  }
569 
570  EXPECT_EQ("{12,120,1234}", toString(vals));
571 }
572 
573 TEST(SparseBitMap, IteratorStress2) {
574  const static int N = 1000;
575 
576  bool log = false;
577 
578  for (unsigned j = 0; j < N; j++) {
579  SparseBitMap<> map;
580 
581  if (log) std::cout << "Creating " << j << " random numbers ..\n";
582  std::set<int> should;
583  while (should.size() < j) {
584  int n = random() % (N * 10);
585  if (!contains(should, n)) {
586  should.insert(n);
587  }
588  }
589 
590  if (log) std::cout << "Filling in input list ..\n";
591  for (const auto& cur : should) {
592  map.set(cur);
593  ASSERT_TRUE(map[cur]);
594  }
595 
596  if (log) std::cout << "Collect is list ..\n";
597  std::set<int> is;
598  unsigned i = 0;
599  for (const auto& cur : map) {
600  is.insert(cur);
601  i++;
602 
603  if (i > j) {
604  map.dump();
605  std::cout << "Should: " << should << "\n";
606  std::cout << " Is: " << is << "\n";
607  }
608 
609  ASSERT_LE(i, j);
610  }
611 
612  if (log) std::cout << "Comparing lists ..\n";
613  EXPECT_EQ(should, is);
614  if (log) std::cout << "Done\n\n";
615  }
616 }
617 
618 TEST(SparseBitMap, Find) {
619  SparseBitMap<> map;
620 
621  EXPECT_EQ(map.end(), map.find(1));
622  EXPECT_EQ(map.end(), map.find(12));
623  EXPECT_EQ(map.end(), map.find(1400));
624 
625  map.set(1400);
626 
627  EXPECT_EQ(map.end(), map.find(1));
628  EXPECT_EQ(map.end(), map.find(12));
629  EXPECT_NE(map.end(), map.find(1400));
630 
631  EXPECT_EQ("1400", toString(*map.find(1400)));
632 
633  map.set(12);
634 
635  EXPECT_EQ(map.end(), map.find(1));
636  EXPECT_NE(map.end(), map.find(12));
637  EXPECT_NE(map.end(), map.find(1400));
638 
639  EXPECT_EQ("12", toString(*map.find(12)));
640  EXPECT_EQ("1400", toString(*map.find(1400)));
641 
642  auto it = map.find(12);
643  EXPECT_EQ("12", toString(*it));
644  ++it;
645  EXPECT_EQ("1400", toString(*it));
646 }
647 
648 TEST(SparseBitMap, Size) {
649  SparseBitMap<> map;
650  EXPECT_EQ(0, map.size());
651  map.set(3);
652  EXPECT_EQ(1, map.size());
653  map.set(5);
654  EXPECT_EQ(2, map.size());
655  map.set(3);
656  EXPECT_EQ(2, map.size());
657  map.set(1000);
658  EXPECT_EQ(3, map.size());
659 }
660 
661 TEST(SparseBitMap, CopyAndMerge) {
662  SparseBitMap<> mapA;
663  SparseBitMap<> mapB;
664  SparseBitMap<> mapC;
665 
666  mapA.set(3);
667  mapA.set(4);
668  mapA.set(5);
669 
670  mapB.set(10000000);
671  mapB.set(10000001);
672  mapB.set(10000002);
673 
674  mapC.set(3);
675  mapC.set(7);
676  mapC.set(10000000);
677  mapC.set(10000007);
678 
679  auto m = mapA;
680  EXPECT_EQ(3, m.size());
681 
682  for (const auto& cur : m) {
683  EXPECT_TRUE(mapA.test(cur));
684  }
685 
686  m.addAll(mapA);
687  EXPECT_EQ(3, m.size());
688 
689  for (const auto& cur : m) {
690  EXPECT_TRUE(mapA.test(cur));
691  }
692 
693  m.addAll(mapB);
694  EXPECT_EQ(6, m.size());
695 
696  for (const auto& cur : m) {
697  EXPECT_TRUE(mapA.test(cur) || mapB.test(cur));
698  }
699 
700  m.addAll(mapC);
701  EXPECT_EQ(8, m.size());
702 
703  for (const auto& cur : m) {
704  EXPECT_TRUE(mapA.test(cur) || mapB.test(cur) || mapC.test(cur));
705  }
706 }
707 
708 TEST(Trie, Basic) {
709  Trie<1> set;
710 
711  EXPECT_TRUE(set.empty());
712  EXPECT_FALSE(set.contains({1}));
713  EXPECT_FALSE(set.contains({2}));
714  EXPECT_FALSE(set.contains({3}));
715 
716  set.insert({1});
717 
718  EXPECT_TRUE(set.contains({1}));
719  EXPECT_FALSE(set.contains({2}));
720  EXPECT_FALSE(set.contains({3}));
721 
722  set.insert({2});
723 
724  EXPECT_TRUE(set.contains({1}));
725  EXPECT_TRUE(set.contains({2}));
726  EXPECT_FALSE(set.contains({3}));
727 }
728 
729 namespace {
730 
731 template <typename Iter>
732 int card(const range<Iter>& r) {
733  int res = 0;
734  for (auto it = r.begin(); it != r.end(); ++it) {
735  res++;
736  }
737  return res;
738 }
739 
740 template <typename Container>
741 int card(const Container& c) {
742  return card(make_range(c.begin(), c.end()));
743 }
744 } // namespace
745 
746 TEST(Trie, Iterator) {
747  Trie<2> set;
748 
749  EXPECT_EQ(set.begin(), set.end());
750 
751  set.insert({1, 2});
752 
753  EXPECT_NE(set.begin(), set.end());
754 
755  set.insert({4, 3});
756  set.insert({5, 2});
757 
758  EXPECT_NE(set.begin(), set.end());
759 
760  EXPECT_EQ(3, card(set));
761 }
762 
763 namespace {
764 
765 RamDomain rand(RamDomain max) {
766  return random() % max;
767 }
768 } // namespace
769 
770 TEST(Trie, IteratorStress_1D) {
771  using tuple = std::array<RamDomain, 1>;
772 
773  const int N = 10000;
774 
775  Trie<1> set;
776 
777  std::set<tuple> data;
778  while (data.size() < N) {
779  tuple cur{(RamDomain)(rand(N * 10))};
780  if (data.insert(cur).second) {
781  EXPECT_FALSE(set.contains(cur));
782  set.insert(cur);
783  EXPECT_TRUE(set.contains(cur));
784  }
785  }
786 
787  std::set<tuple> is;
788  for (const auto& cur : set) {
789  is.insert(cur);
790  }
791 
792  EXPECT_EQ(N, set.size());
793  EXPECT_EQ(data, is);
794 }
795 
796 TEST(Trie, IteratorStress_2D) {
797  using tuple = std::array<RamDomain, 2>;
798 
799  const int N = 10000;
800 
801  Trie<2> set;
802 
803  std::set<tuple> data;
804  while (data.size() < N) {
805  tuple cur;
806  cur[0] = (RamDomain)(rand(N * 10));
807  cur[1] = (RamDomain)(rand(N * 10));
808  if (data.insert(cur).second) {
809  EXPECT_FALSE(set.contains(cur));
810  set.insert(cur);
811  EXPECT_TRUE(set.contains(cur));
812  }
813  }
814 
815  std::set<tuple> is;
816  for (const auto& cur : set) {
817  is.insert(cur);
818  }
819 
820  EXPECT_EQ(N, set.size());
821  EXPECT_EQ(data, is);
822 }
823 
824 TEST(Trie, IteratorStress_3D) {
825  using tuple = std::array<RamDomain, 3>;
826 
827  const int N = 10000;
828 
829  Trie<3> set;
830 
831  std::set<tuple> data;
832  while (data.size() < N) {
833  tuple cur;
834  cur[0] = (RamDomain)(rand(N * 10));
835  cur[1] = (RamDomain)(rand(N * 10));
836  cur[2] = (RamDomain)(rand(N * 10));
837  if (data.insert(cur).second) {
838  EXPECT_FALSE(set.contains(cur));
839  set.insert(cur);
840  EXPECT_TRUE(set.contains(cur));
841  }
842  }
843 
844  std::set<tuple> is;
845  for (const auto& cur : set) {
846  is.insert(cur);
847  }
848 
849  EXPECT_EQ(N, set.size());
850  EXPECT_EQ(data, is);
851 }
852 
853 TEST(Trie, IteratorStress_4D) {
854  using tuple = std::array<RamDomain, 4>;
855 
856  const int N = 10000;
857 
858  Trie<4> set;
859 
860  std::set<tuple> data;
861  while (data.size() < N) {
862  tuple cur;
863  cur[0] = (RamDomain)(rand(N * 10));
864  cur[1] = (RamDomain)(rand(N * 10));
865  cur[2] = (RamDomain)(rand(N * 10));
866  cur[3] = (RamDomain)(rand(N * 10));
867  if (data.insert(cur).second) {
868  EXPECT_FALSE(set.contains(cur));
869  set.insert(cur);
870  EXPECT_TRUE(set.contains(cur));
871  }
872  }
873 
874  std::set<tuple> is;
875  for (const auto& cur : set) {
876  is.insert(cur);
877  }
878 
879  EXPECT_EQ(N, set.size());
880  EXPECT_EQ(data, is);
881 }
882 
883 TEST(Trie, BoundaryTest_1D) {
884  using test_set = Trie<1>;
885 
886  test_set t;
887 
888  for (int i = 0; i < 10; i++) {
889  t.insert({i});
890  }
891 
892  auto a = t.lower_bound({5});
893  EXPECT_EQ(5, (*a)[0]);
894 
895  auto b = t.upper_bound({5});
896  EXPECT_EQ(6, (*b)[0]);
897 
898  // add duplicates
899 
900  t.insert({5});
901  t.insert({5});
902  t.insert({5});
903 
904  // test again ..
905  a = t.lower_bound({5});
906  EXPECT_EQ(5, (*a)[0]);
907 
908  b = t.upper_bound({5});
909  EXPECT_EQ(6, (*b)[0]);
910 
911  // check the distance
912  EXPECT_EQ(++a, b);
913 }
914 
915 TEST(Trie, BoundaryTest_1D_2) {
916  using test_set = Trie<1>;
917 
918  test_set t;
919 
920  for (int i = 0; i < 10; i++) {
921  t.insert({i * 100});
922  }
923 
924  auto a = t.lower_bound({500});
925  EXPECT_EQ(500, (*a)[0]);
926 
927  auto b = t.upper_bound({500});
928  EXPECT_EQ(600, (*b)[0]);
929 
930  // add duplicates
931 
932  t.insert({500});
933  t.insert({500});
934  t.insert({500});
935 
936  // test again ..
937  a = t.lower_bound({500});
938  EXPECT_EQ(500, (*a)[0]);
939 
940  b = t.upper_bound({500});
941  EXPECT_EQ(600, (*b)[0]);
942 
943  // check the distance
944  EXPECT_EQ(++a, b);
945 }
946 
947 TEST(Trie, BoundaryTest_1D_Stress) {
948  using value_type = typename Trie<1>::element_type;
949  using test_set = Trie<1>;
950  using ref_set = std::set<value_type>;
951 
952  test_set t;
953  ref_set r;
954 
955  for (int i = 5; i < 10; i++) {
956  t.insert({i * 100});
957  r.insert({i * 100});
958  }
959 
960  // Check various lookup points
961  for (int i = 0; i < 30; i++) {
962  value_type key{i * 50};
963 
964  auto t_lb = t.lower_bound(key);
965  auto r_lb = r.lower_bound(key);
966 
967  EXPECT_EQ(t_lb == t.end(), r_lb == r.end());
968  if (t_lb != t.end() && r_lb != r.end()) {
969  EXPECT_EQ(*t_lb, *r_lb);
970  }
971 
972  auto t_ub = t.upper_bound(key);
973  auto r_ub = r.upper_bound(key);
974 
975  EXPECT_EQ(t_ub == t.end(), r_ub == r.end());
976  if (t_ub != t.end() && r_ub != r.end()) {
977  EXPECT_EQ(*t_ub, *r_ub);
978  }
979  }
980 }
981 
982 TEST(Trie, BoundaryTest_1D_Stress_Dense) {
983  using value_type = typename Trie<1>::element_type;
984  using test_set = Trie<1>;
985  using ref_set = std::set<value_type>;
986 
987  test_set t;
988  ref_set r;
989 
990  for (int i = 100; i < 2000; i++) {
991  t.insert({i});
992  r.insert({i});
993  }
994 
995  // Check various lookup points
996  for (int i = 0; i < 2500; i++) {
997  value_type key{i};
998 
999  auto t_lb = t.lower_bound(key);
1000  auto r_lb = r.lower_bound(key);
1001 
1002  EXPECT_EQ(t_lb == t.end(), r_lb == r.end());
1003  if (t_lb != t.end() && r_lb != r.end()) {
1004  EXPECT_EQ(*t_lb, *r_lb);
1005  }
1006 
1007  auto t_ub = t.upper_bound(key);
1008  auto r_ub = r.upper_bound(key);
1009 
1010  EXPECT_EQ(t_ub == t.end(), r_ub == r.end());
1011  if (t_ub != t.end() && r_ub != r.end()) {
1012  EXPECT_EQ(*t_ub, *r_ub);
1013  }
1014  }
1015 }
1016 
1017 TEST(Trie, BoundaryTest_2D) {
1018  using test_set = Trie<2>;
1019 
1020  test_set t;
1021 
1022  for (int i = 0; i < 10; i++) {
1023  for (int j = 0; j < 10; j++) {
1024  t.insert({i, j});
1025  }
1026  }
1027 
1028  auto a = t.lower_bound({5, 5});
1029  EXPECT_EQ(5, (*a)[0]);
1030  EXPECT_EQ(5, (*a)[1]);
1031 
1032  auto b = t.upper_bound({5, 5});
1033  EXPECT_EQ(5, (*b)[0]);
1034  EXPECT_EQ(6, (*b)[1]);
1035 
1036  // add duplicates
1037 
1038  t.insert({5, 5});
1039  t.insert({5, 5});
1040  t.insert({5, 5});
1041 
1042  // test again ..
1043  a = t.lower_bound({5, 5});
1044  EXPECT_EQ(5, (*a)[0]);
1045  EXPECT_EQ(5, (*a)[1]);
1046 
1047  b = t.upper_bound({5, 5});
1048  EXPECT_EQ(5, (*b)[0]);
1049  EXPECT_EQ(6, (*b)[1]);
1050 
1051  // check the distance
1052  EXPECT_EQ(++a, b);
1053 }
1054 
1055 TEST(Trie, BoundaryTest_2D_2) {
1056  using test_set = Trie<2>;
1057 
1058  test_set t;
1059 
1060  for (int i = 0; i < 10; i++) {
1061  for (int j = 0; j < 10; j++) {
1062  t.insert({i * 100, j * 100});
1063  }
1064  }
1065 
1066  auto a = t.lower_bound({500, 500});
1067  EXPECT_EQ(500, (*a)[0]);
1068  EXPECT_EQ(500, (*a)[1]);
1069 
1070  auto b = t.upper_bound({500, 500});
1071  EXPECT_EQ(500, (*b)[0]);
1072  EXPECT_EQ(600, (*b)[1]);
1073 
1074  // add duplicates
1075 
1076  t.insert({500, 500});
1077  t.insert({500, 500});
1078  t.insert({500, 500});
1079 
1080  // test again ..
1081  a = t.lower_bound({500, 500});
1082  EXPECT_EQ(500, (*a)[0]);
1083  EXPECT_EQ(500, (*a)[1]);
1084 
1085  b = t.upper_bound({500, 500});
1086  EXPECT_EQ(500, (*b)[0]);
1087  EXPECT_EQ(600, (*b)[1]);
1088 
1089  // check the distance
1090  EXPECT_EQ(++a, b);
1091 }
1092 
1093 TEST(Trie, BoundaryTest_2D_Stress) {
1094  using value_type = typename Trie<2>::element_type;
1095  using test_set = Trie<2>;
1096  using ref_set = std::set<value_type>;
1097 
1098  test_set t;
1099  ref_set r;
1100 
1101  for (int i = 5; i < 10; i++) {
1102  for (int j = 5; j < 10; j++) {
1103  t.insert({i * 100, j * 100});
1104  r.insert({i * 100, j * 100});
1105  }
1106  }
1107 
1108  // Check various lookup points
1109  for (int i = 0; i < 30; i++) {
1110  for (int j = 0; j < 30; j++) {
1111  value_type key{i * 50, j * 50};
1112 
1113  auto t_lb = t.lower_bound(key);
1114  auto r_lb = r.lower_bound(key);
1115 
1116  EXPECT_EQ(t_lb == t.end(), r_lb == r.end());
1117  if (t_lb != t.end() && r_lb != r.end()) {
1118  EXPECT_EQ(*t_lb, *r_lb);
1119  }
1120 
1121  auto t_ub = t.upper_bound(key);
1122  auto r_ub = r.upper_bound(key);
1123 
1124  EXPECT_EQ(t_ub == t.end(), r_ub == r.end());
1125  if (t_ub != t.end() && r_ub != r.end()) {
1126  EXPECT_EQ(*t_ub, *r_ub);
1127  }
1128  }
1129  }
1130 }
1131 
1132 TEST(Trie, BoundaryTest_2D_Stress_Dense) {
1133  using value_type = typename Trie<2>::element_type;
1134  using test_set = Trie<2>;
1135  using ref_set = std::set<value_type>;
1136 
1137  test_set t;
1138  ref_set r;
1139 
1140  for (int i = 100; i < 200; i++) {
1141  for (int j = 50; j < 250; j++) {
1142  t.insert({i, j});
1143  r.insert({i, j});
1144  }
1145  }
1146 
1147  // Check various lookup points
1148  for (int i = 0; i < 250; i++) {
1149  for (int j = 0; j < 300; j++) {
1150  value_type key{i, j};
1151 
1152  auto t_lb = t.lower_bound(key);
1153  auto r_lb = r.lower_bound(key);
1154 
1155  EXPECT_EQ(t_lb == t.end(), r_lb == r.end());
1156  if (t_lb != t.end() && r_lb != r.end()) {
1157  EXPECT_EQ(*t_lb, *r_lb);
1158  }
1159 
1160  auto t_ub = t.upper_bound(key);
1161  auto r_ub = r.upper_bound(key);
1162 
1163  EXPECT_EQ(t_ub == t.end(), r_ub == r.end());
1164  if (t_ub != t.end() && r_ub != r.end()) {
1165  EXPECT_EQ(*t_ub, *r_ub);
1166  }
1167  }
1168  }
1169 }
1170 
1171 TEST(Trie, BoundaryTest_3D) {
1172  using test_set = Trie<3>;
1173 
1174  test_set t;
1175 
1176  for (int i = 0; i < 10; i++) {
1177  for (int j = 0; j < 10; j++) {
1178  for (int k = 0; k < 10; k++) {
1179  t.insert({i, j, k});
1180  }
1181  }
1182  }
1183 
1184  auto a = t.lower_bound({5, 5, 5});
1185  EXPECT_EQ(5, (*a)[0]);
1186  EXPECT_EQ(5, (*a)[1]);
1187  EXPECT_EQ(5, (*a)[2]);
1188 
1189  auto b = t.upper_bound({5, 5, 5});
1190  EXPECT_EQ(5, (*b)[0]);
1191  EXPECT_EQ(5, (*b)[1]);
1192  EXPECT_EQ(6, (*b)[2]);
1193 
1194  // check the distance
1195  EXPECT_EQ(++a, b);
1196 }
1197 
1198 TEST(Trie, BoundaryTest_3D_2) {
1199  using test_set = Trie<3>;
1200 
1201  test_set t;
1202 
1203  for (int i = 0; i < 10; i++) {
1204  for (int j = 0; j < 10; j++) {
1205  for (int k = 0; k < 10; k++) {
1206  t.insert({i * 100, j * 100, k * 100});
1207  }
1208  }
1209  }
1210 
1211  auto a = t.lower_bound({500, 500, 500});
1212  EXPECT_EQ(500, (*a)[0]);
1213  EXPECT_EQ(500, (*a)[1]);
1214  EXPECT_EQ(500, (*a)[2]);
1215 
1216  auto b = t.upper_bound({500, 500, 500});
1217  EXPECT_EQ(500, (*b)[0]);
1218  EXPECT_EQ(500, (*b)[1]);
1219  EXPECT_EQ(600, (*b)[2]);
1220 
1221  // check the distance
1222  EXPECT_EQ(++a, b);
1223 }
1224 
1225 TEST(Trie, BoundaryTest_3D_Stress) {
1226  using value_type = typename Trie<3>::element_type;
1227  using test_set = Trie<3>;
1228  using ref_set = std::set<value_type>;
1229 
1230  test_set t;
1231  ref_set r;
1232 
1233  for (int i = 5; i < 10; i++) {
1234  for (int j = 5; j < 10; j++) {
1235  for (int k = 5; k < 10; k++) {
1236  t.insert({i * 100, j * 100, k * 100});
1237  r.insert({i * 100, j * 100, k * 100});
1238  }
1239  }
1240  }
1241 
1242  // Check various lookup points
1243  for (int i = 0; i < 30; i++) {
1244  for (int j = 0; j < 30; j++) {
1245  for (int k = 0; k < 30; k++) {
1246  value_type key{i * 50, j * 50, k * 50};
1247 
1248  auto t_lb = t.lower_bound(key);
1249  auto r_lb = r.lower_bound(key);
1250 
1251  EXPECT_EQ(t_lb == t.end(), r_lb == r.end());
1252  if (t_lb != t.end() && r_lb != r.end()) {
1253  EXPECT_EQ(*t_lb, *r_lb);
1254  }
1255 
1256  auto t_ub = t.upper_bound(key);
1257  auto r_ub = r.upper_bound(key);
1258 
1259  EXPECT_EQ(t_ub == t.end(), r_ub == r.end());
1260  if (t_ub != t.end() && r_ub != r.end()) {
1261  EXPECT_EQ(*t_ub, *r_ub);
1262  }
1263  }
1264  }
1265  }
1266 }
1267 
1268 TEST(Trie, RangeQuery) {
1269  Trie<3> set;
1270 
1271  for (int i = 0; i < 10; i++) {
1272  for (int j = 0; j < 10; j++) {
1273  for (int k = 0; k < 10; k++) {
1274  set.insert({i, j, k});
1275  }
1276  }
1277  }
1278 
1279  EXPECT_EQ(1000, set.size());
1280 
1281  // Range [*,*,*]
1282  EXPECT_EQ(1000, card(set.getBoundaries<0>({3, 4, 5})));
1283 
1284  // Range [3,*,*]
1285  EXPECT_EQ(100, card(set.getBoundaries<1>({3, 4, 5})));
1286 
1287  // Range [3,4,*]
1288  EXPECT_EQ(10, card(set.getBoundaries<2>({3, 4, 5})));
1289 
1290  // Range [3,4,5]
1291  EXPECT_EQ(1, card(set.getBoundaries<3>({3, 4, 5})));
1292 }
1293 
1294 TEST(Trie, RangeQuery_1D) {
1295  Trie<1> set;
1296 
1297  // empty set
1298  EXPECT_EQ(0, card(set.getBoundaries<0>({3})));
1299  EXPECT_EQ(0, card(set.getBoundaries<1>({3})));
1300 
1301  // add some elements
1302  for (int i = 0; i < 5; i++) {
1303  set.insert({i});
1304  }
1305 
1306  EXPECT_EQ(5, card(set.getBoundaries<0>({3})));
1307  EXPECT_EQ(5, card(set.getBoundaries<0>({7})));
1308 
1309  EXPECT_EQ(1, card(set.getBoundaries<1>({3})));
1310  EXPECT_EQ(0, card(set.getBoundaries<1>({7})));
1311 }
1312 
1313 TEST(Trie, RangeQuery_2D) {
1314  Trie<2> set;
1315 
1316  // empty set
1317  EXPECT_EQ(0, card(set.getBoundaries<0>({3, 4})));
1318  EXPECT_EQ(0, card(set.getBoundaries<1>({3, 4})));
1319  EXPECT_EQ(0, card(set.getBoundaries<2>({3, 4})));
1320 
1321  // add some elements
1322  for (int i = 0; i < 5; i++) {
1323  for (int j = 0; j < 5; j++) {
1324  set.insert({i, j});
1325  }
1326  }
1327 
1328  EXPECT_EQ(25, card(set.getBoundaries<0>({3, 4})));
1329  EXPECT_EQ(25, card(set.getBoundaries<0>({7, 4})));
1330  EXPECT_EQ(25, card(set.getBoundaries<0>({3, 7})));
1331 
1332  EXPECT_EQ(5, card(set.getBoundaries<1>({3, 4})));
1333  EXPECT_EQ(0, card(set.getBoundaries<1>({7, 4})));
1334  EXPECT_EQ(5, card(set.getBoundaries<1>({3, 7})));
1335 
1336  EXPECT_EQ(1, card(set.getBoundaries<2>({3, 4})));
1337  EXPECT_EQ(0, card(set.getBoundaries<2>({7, 4})));
1338  EXPECT_EQ(0, card(set.getBoundaries<2>({3, 7})));
1339 }
1340 
1341 TEST(Trie, RangeQuery_3D) {
1342  Trie<3> set;
1343 
1344  // empty set
1345  EXPECT_EQ(0, card(set.getBoundaries<0>({3, 4, 2})));
1346  EXPECT_EQ(0, card(set.getBoundaries<1>({3, 4, 2})));
1347  EXPECT_EQ(0, card(set.getBoundaries<2>({3, 4, 2})));
1348  EXPECT_EQ(0, card(set.getBoundaries<3>({3, 4, 2})));
1349 
1350  // add some elements
1351  for (int i = 0; i < 5; i++) {
1352  for (int j = 0; j < 5; j++) {
1353  for (int k = 0; k < 5; k++) {
1354  set.insert({i, j, k});
1355  }
1356  }
1357  }
1358 
1359  EXPECT_EQ(125, card(set.getBoundaries<0>({3, 4, 2})));
1360  EXPECT_EQ(125, card(set.getBoundaries<0>({7, 4, 2})));
1361  EXPECT_EQ(125, card(set.getBoundaries<0>({3, 7, 2})));
1362  EXPECT_EQ(125, card(set.getBoundaries<0>({3, 7, 8})));
1363 
1364  EXPECT_EQ(25, card(set.getBoundaries<1>({3, 4, 2})));
1365  EXPECT_EQ(0, card(set.getBoundaries<1>({7, 4, 2})));
1366  EXPECT_EQ(25, card(set.getBoundaries<1>({3, 7, 2})));
1367  EXPECT_EQ(25, card(set.getBoundaries<1>({3, 7, 8})));
1368 
1369  EXPECT_EQ(5, card(set.getBoundaries<2>({3, 4, 2})));
1370  EXPECT_EQ(0, card(set.getBoundaries<2>({7, 4, 2})));
1371  EXPECT_EQ(0, card(set.getBoundaries<2>({3, 7, 2})));
1372  EXPECT_EQ(0, card(set.getBoundaries<2>({3, 7, 8})));
1373  EXPECT_EQ(5, card(set.getBoundaries<2>({3, 2, 8})));
1374 
1375  EXPECT_EQ(1, card(set.getBoundaries<3>({3, 4, 2})));
1376  EXPECT_EQ(0, card(set.getBoundaries<3>({7, 4, 2})));
1377  EXPECT_EQ(0, card(set.getBoundaries<3>({3, 7, 2})));
1378  EXPECT_EQ(0, card(set.getBoundaries<3>({3, 7, 8})));
1379 }
1380 
1381 TEST(Trie, RangeQueryStress) {
1382  Trie<3> set;
1383 
1384  for (int i = 0; i < 10; i++) {
1385  for (int j = 0; j < 10; j++) {
1386  for (int k = 0; k < 10; k++) {
1387  set.insert({i, j, k});
1388  }
1389  }
1390  }
1391 
1392  EXPECT_EQ(1000, set.size());
1393 
1394  // Range [*,*,*]
1395  EXPECT_EQ(1000, card(set.getBoundaries<0>({3, 4, 5})));
1396 
1397  // Range [x,*,*]
1398  for (RamDomain x = 0; x < 10; x++) {
1399  EXPECT_EQ(100, card(set.getBoundaries<1>({x, 4, 5})));
1400  }
1401 
1402  // Range [x,y,*]
1403  for (RamDomain x = 0; x < 10; x++) {
1404  for (RamDomain y = 0; y < 10; y++) {
1405  EXPECT_EQ(10, card(set.getBoundaries<2>({x, y, 5})));
1406  }
1407  }
1408 
1409  // Range [x,y,*]
1410  for (RamDomain x = 0; x < 10; x++) {
1411  for (RamDomain y = 0; y < 10; y++) {
1412  for (RamDomain z = 0; z < 10; z++) {
1413  EXPECT_EQ(1, card(set.getBoundaries<3>({x, y, z})));
1414  }
1415  }
1416  }
1417 }
1418 
1419 TEST(Trie, Merge_1D) {
1420  Trie<1> e;
1421  Trie<1> a;
1422  Trie<1> b;
1423 
1424  for (int i = 0; i < 5; i++) {
1425  a.insert({i});
1426  b.insert({i + 5});
1427  }
1428 
1429  {
1430  Trie<1> c = e;
1431  c.insertAll(a);
1432  for (int i = 0; i < 10; i++) {
1433  EXPECT_EQ(a.contains({i}), c.contains({i}));
1434  }
1435  }
1436 
1437  {
1438  Trie<1> c = e;
1439  c.insertAll(b);
1440  for (int i = 0; i < 10; i++) {
1441  EXPECT_EQ(b.contains({i}), c.contains({i}));
1442  }
1443  }
1444 
1445  {
1446  Trie<1> c = e;
1447  c.insertAll(a);
1448  c.insertAll(b);
1449  for (int i = 0; i < 10; i++) {
1450  EXPECT_EQ(a.contains({i}) || b.contains({i}), c.contains({i}));
1451  }
1452  }
1453 }
1454 
1455 TEST(Trie, Merge_2D) {
1456  Trie<2> e;
1457  Trie<2> a;
1458  Trie<2> b;
1459 
1460  for (int i = 0; i < 5; i++) {
1461  for (int j = 0; j < 5; j++) {
1462  a.insert({i, j});
1463  b.insert({i + 5, j + 5});
1464  }
1465  }
1466 
1467  {
1468  Trie<2> c = e;
1469  c.insertAll(a);
1470  for (int i = 0; i < 10; i++) {
1471  for (int j = 0; j < 10; j++) {
1472  EXPECT_EQ(a.contains({i, j}), c.contains({i, j}));
1473  }
1474  }
1475  }
1476 
1477  {
1478  Trie<2> c = e;
1479  c.insertAll(b);
1480  for (int i = 0; i < 10; i++) {
1481  for (int j = 0; j < 10; j++) {
1482  EXPECT_EQ(b.contains({i, j}), c.contains({i, j}));
1483  }
1484  }
1485  }
1486 
1487  {
1488  Trie<2> c = e;
1489  c.insertAll(a);
1490  c.insertAll(b);
1491  for (int i = 0; i < 10; i++) {
1492  for (int j = 0; j < 10; j++) {
1493  EXPECT_EQ(a.contains({i, j}) || b.contains({i, j}), c.contains({i, j}));
1494  }
1495  }
1496  }
1497 }
1498 
1499 TEST(Trie, Merge_3D) {
1500  Trie<3> e;
1501  Trie<3> a;
1502  Trie<3> b;
1503 
1504  for (int i = 0; i < 5; i++) {
1505  for (int j = 0; j < 5; j++) {
1506  for (int k = 0; k < 5; k++) {
1507  a.insert({i, j, k});
1508  b.insert({i + 5, j + 5, k + 5});
1509  }
1510  }
1511  }
1512 
1513  {
1514  Trie<3> c = e;
1515  c.insertAll(a);
1516  for (int i = 0; i < 10; i++) {
1517  for (int j = 0; j < 10; j++) {
1518  for (int k = 0; k < 5; k++) {
1519  EXPECT_EQ(a.contains({i, j, k}), c.contains({i, j, k}));
1520  }
1521  }
1522  }
1523  }
1524 
1525  {
1526  Trie<3> c = e;
1527  c.insertAll(b);
1528  for (int i = 0; i < 10; i++) {
1529  for (int j = 0; j < 10; j++) {
1530  for (int k = 0; k < 5; k++) {
1531  EXPECT_EQ(b.contains({i, j, k}), c.contains({i, j, k}));
1532  }
1533  }
1534  }
1535  }
1536 
1537  {
1538  Trie<3> c = e;
1539  c.insertAll(a);
1540  c.insertAll(b);
1541  for (int i = 0; i < 10; i++) {
1542  for (int j = 0; j < 10; j++) {
1543  for (int k = 0; k < 5; k++) {
1544  EXPECT_EQ(a.contains({i, j, k}) || b.contains({i, j, k}), c.contains({i, j, k}));
1545  }
1546  }
1547  }
1548  }
1549 }
1550 
1551 TEST(Trie, Merge_Stress) {
1552  using entry_t = typename Trie<2>::entry_type;
1553 
1554  const int N = 1000;
1555  const int M = 100;
1556 
1557  std::set<entry_t> ref;
1558  Trie<2> a;
1559 
1560  for (int i = 0; i < M; i++) {
1561  Trie<2> b;
1562  for (int i = 0; i < N; i++) {
1563  RamDomain x = rand(N / 2);
1564  RamDomain y = rand(N / 2);
1565  if (!a.contains({x, y})) {
1566  b.insert({x, y});
1567  ref.insert(entry_t{x, y});
1568  }
1569  }
1570 
1571  a.insertAll(b);
1572 
1573  std::set<entry_t> is(a.begin(), a.end());
1574  std::set<entry_t> should(ref.begin(), ref.end());
1575  EXPECT_EQ(should, is);
1576  }
1577 }
1578 
1579 TEST(Trie, Merge_Bug) {
1580  // having this set ...
1581  Trie<2> a;
1582  a.insert({25129, 67714});
1583  a.insert({25132, 67714});
1584  a.insert({84808, 68457});
1585 
1586  // a.getStore().dump();
1587 
1588  // ... merged with an empty set ...
1589  Trie<2> b;
1590  a.insertAll(b);
1591 
1592  // a.getStore().dump();
1593 
1594  // and later on merged with a third set
1595  Trie<2> c;
1596  c.insert({133, 455});
1597  c.insert({10033, 455});
1598  a.insertAll(c);
1599 
1600  // a.getStore().dump();
1601 
1602  // ... caused the first element to be missing in the iterator
1603  int count = 0;
1604  for (auto it = a.begin(); it != a.end(); ++it) {
1605  count++;
1606  }
1607 
1608  // if there are 5 elements, everything is fine
1609  EXPECT_EQ(5, count);
1610 }
1611 
1612 TEST(Trie, Size) {
1613  Trie<2> t;
1614 
1615  EXPECT_TRUE(t.empty());
1616  EXPECT_EQ(0, t.size());
1617 
1618  t.insert({1, 2});
1619 
1620  EXPECT_FALSE(t.empty());
1621  EXPECT_EQ(1, t.size());
1622 
1623  t.insert({1, 2});
1624 
1625  EXPECT_FALSE(t.empty());
1626  EXPECT_EQ(1, t.size());
1627 
1628  t.insert({2, 1});
1629 
1630  EXPECT_FALSE(t.empty());
1631  EXPECT_EQ(2, t.size());
1632 
1633  Trie<2> t2;
1634 
1635  t2.insert({1, 2});
1636  t2.insert({1, 3});
1637  t2.insert({1, 4});
1638  t2.insert({3, 2});
1639 
1640  EXPECT_EQ(4, t2.size());
1641 
1642  t.insertAll(t2);
1643  EXPECT_FALSE(t.empty());
1644  EXPECT_EQ(5, t.size());
1645 }
1646 
1647 TEST(Trie, Limits) {
1648  Trie<2> data;
1649 
1650  EXPECT_EQ(0, data.size());
1651  data.insert({10, 15});
1652  EXPECT_EQ(1, data.size());
1653 
1654  data.insert({(1 << 31) + (1 << 30), 18});
1655  EXPECT_EQ(2, data.size());
1656 
1657  Trie<2> a;
1658  a.insert({140, 15});
1659 
1660  Trie<2> b;
1661  b.insert({25445, 18});
1662 
1663  b.insertAll(a);
1664 
1665  EXPECT_EQ(2, b.size());
1666 
1667  int counter = 0;
1668  for (auto it = b.begin(); it != b.end(); ++it) {
1669  counter++;
1670  }
1671  EXPECT_EQ(2, counter);
1672 }
1673 
1674 TEST(Trie, Parallel) {
1675  const int N = 10000;
1676 
1677  // get a unordered list of test data
1678  using entry_t = typename Trie<2>::entry_type;
1679  std::vector<entry_t> list;
1680  Trie<2> filter;
1681 
1682  while (filter.size() < N) {
1683  entry_t entry{(RamDomain)(random() % N), (RamDomain)(random() % N)};
1684  if (filter.insert(entry)) {
1685  list.push_back(entry);
1686  }
1687  }
1688 
1689  // the number of times duplicates show up in the input set
1690  for (int dup = 1; dup < 4; dup++) {
1691  // now duplicate this list
1692  std::vector<entry_t> full;
1693  for (int i = 0; i < dup; i++) {
1694  for (const auto& cur : list) {
1695  full.push_back(cur);
1696  }
1697  }
1698 
1699  // shuffle data
1700  std::random_device rd;
1701  std::mt19937 generator(rd());
1702 
1703  std::shuffle(full.begin(), full.end(), generator);
1704 
1705  // now insert all those values into a new set - in parallel
1706  Trie<2> res;
1707 #pragma omp parallel for
1708  for (auto it = full.begin(); it < full.end(); ++it) {
1709  res.insert(*it);
1710  }
1711 
1712  // check resulting values
1713  EXPECT_EQ(N, res.size());
1714 
1715  std::set<entry_t> should(full.begin(), full.end());
1716  std::set<entry_t> is(res.begin(), res.end());
1717 
1718  for (const auto& cur : should) {
1719  EXPECT_TRUE(res.contains(cur)) << "Missing: " << cur << "\n";
1720  }
1721 
1722  for (const auto& cur : res) {
1723  EXPECT_TRUE(should.find(cur) != should.end()) << "Additional: " << cur << "\n"
1724  << "Contained: " << res.contains(cur) << "\n";
1725  }
1726 
1727  std::vector<entry_t> extra;
1728  for (const auto& cur : is) {
1729  if (should.find(cur) == should.end()) extra.push_back(cur);
1730  }
1731  EXPECT_TRUE(extra.empty()) << "Extra elments: " << extra << "\n";
1732 
1733  std::vector<entry_t> missing;
1734  for (const auto& cur : should) {
1735  if (is.find(cur) == is.end()) missing.push_back(cur);
1736  }
1737  EXPECT_TRUE(missing.empty()) << "Missing elments: " << missing << "\n"
1738  << "All Elements: " << should << "\n";
1739 
1740  EXPECT_EQ(N, should.size());
1741  EXPECT_EQ(N, is.size());
1742  EXPECT_EQ(should, is);
1743  }
1744 }
1745 
1746 } // namespace souffle
souffle::Trie::contains
bool contains(const_entry_span_type tuple, op_context &ctxt) const
Definition: Brie.h:2778
EXPECT_TRUE
#define EXPECT_TRUE(a)
Definition: test.h:189
souffle::Trie::begin
iterator begin() const
Obtains an iterator referencing the first element stored within this trie.
Definition: Brie.h:2082
m
var m
Definition: htmlJsChartistMin.h:15
souffle::RamDomain
int32_t RamDomain
Definition: RamTypes.h:56
ASSERT_LE
#define ASSERT_LE(a, b)
Definition: test.h:213
souffle::contains
bool contains(const C &container, const typename C::value_type &element)
A utility to check generically whether a given element is contained in a given container.
Definition: ContainerUtil.h:75
EXPECT_EQ
#define EXPECT_EQ(a, b)
Definition: test.h:191
e
l j a showGridBackground &&c b raw series this eventEmitter e
Definition: htmlJsChartistMin.h:15
souffle::map
auto map(const std::vector< A > &xs, F &&f)
Applies a function to each element of a vector and returns the results.
Definition: ContainerUtil.h:158
souffle::SparseArray
A sparse array simulates an array associating to every element of uint32_t an element of a generic ty...
Definition: Brie.h:339
Brie.h
souffle::Trie
Definition: Brie.h:79
n
var n
Definition: htmlJsChartistMin.h:15
j
var j
Definition: htmlJsChartistMin.h:15
souffle::Trie::element_type
entry_type element_type
Definition: Brie.h:2675
souffle::SparseBitMap
A sparse bit-map is a bit map virtually assigning a bit value to every value if the uint32_t domain.
Definition: Brie.h:1637
souffle::toString
const std::string & toString(const std::string &str)
A generic function converting strings into strings (trivial case).
Definition: StringUtil.h:234
souffle::Trie::insert
bool insert(const_entry_span_type tuple, op_context &ctxt)
Inserts a new entry.
Definition: Brie.h:2736
i
size_t i
Definition: json11.h:663
souffle::filter
std::vector< A > filter(std::vector< A > xs, F &&f)
Filter a vector to include certain elements.
Definition: FunctionalUtil.h:155
ContainerUtil.h
souffle::TEST
TEST(SparseArray, Basic)
Definition: brie_test.cpp:45
souffle::make_range
range< Iter > make_range(const Iter &a, const Iter &b)
A utility function enabling the construction of ranges without explicitly specifying the iterator typ...
Definition: ContainerUtil.h:389
StringUtil.h
souffle::test::count
int count(const C &c)
Definition: table_test.cpp:40
test.h
ASSERT_TRUE
#define ASSERT_TRUE(a)
Definition: test.h:212
k
var k
Definition: htmlJsChartistMin.h:15
EXPECT_NE
#define EXPECT_NE(a, b)
Definition: test.h:195
b
l j a showGridBackground &&c b raw series this eventEmitter b
Definition: htmlJsChartistMin.h:15
souffle::Trie::end
iterator end() const
Obtains an iterator referencing the position after the last element stored within this trie.
Definition: Brie.h:2090
RamTypes.h
StreamUtil.h
souffle
Definition: AggregateOp.h:25
TCB_SPAN_NAMESPACE_NAME::detail::data
constexpr auto data(C &c) -> decltype(c.data())
Definition: span.h:210
souffle::tuple
Defines a tuple for the OO interface such that relations with varying columns can be accessed.
Definition: SouffleInterface.h:443
souffle::Trie::entry_type
typename types::entry_type entry_type
Definition: Brie.h:2669
EXPECT_FALSE
#define EXPECT_FALSE(a)
Definition: test.h:190
souffle::SparseArray::index_type
key_type index_type
Definition: Brie.h:353
Generated by   doxygen 1.8.17