radixTreeMap

1 version(showAssertTags) dbg();
2    import std.algorithm.comparison : equal;
3    alias Key = string;
4    auto set = radixTreeSet!(Key);
5 
6    set.clear();
7    set.insert(`-----1`);
8    assert(set.prefix(`-----`).equal([`1`]));
9    assert(set.prefix(`-----_`).empty);
10    assert(set.prefix(`-----____`).empty);
11    set.insert(`-----2`);
12    assert(set.prefix(`-----`).equal([`1`, `2`]));
13    assert(set.prefix(`-----_`).empty);
14    assert(set.prefix(`-----____`).empty);
15    set.insert(`-----3`);
16    assert(set.prefix(`-----`).equal([`1`, `2`, `3`]));
17    assert(set.prefix(`-----_`).empty);
18    assert(set.prefix(`-----____`).empty);
19    set.insert(`-----4`);
20    assert(set.prefix(`-----`).equal([`1`, `2`, `3`, `4`]));
21    assert(set.prefix(`-----_`).empty);
22    assert(set.prefix(`-----____`).empty);
23    set.insert(`-----5`);
24    assert(set.prefix(`-----`).equal([`1`, `2`, `3`, `4`, `5`]));
25    assert(set.prefix(`-----_`).empty);
26    assert(set.prefix(`-----____`).empty);
27    set.insert(`-----6`);
28    assert(set.prefix(`-----`).equal([`1`, `2`, `3`, `4`, `5`, `6`]));
29    assert(set.prefix(`-----_`).empty);
30    assert(set.prefix(`-----____`).empty);
31    set.insert(`-----7`);
32    assert(set.prefix(`-----`).equal([`1`, `2`, `3`, `4`, `5`, `6`, `7`]));
33    assert(set.prefix(`-----_`).empty);
34    assert(set.prefix(`-----____`).empty);
35    set.insert(`-----8`);
36    assert(set.prefix(`-----`).equal([`1`, `2`, `3`, `4`, `5`, `6`, `7`, `8`]));
37    assert(set.prefix(`-----_`).empty);
38    assert(set.prefix(`-----____`).empty);
39    set.insert(`-----11`);
40    assert(set.prefix(`-----`).equal([`1`, `11`, `2`, `3`, `4`, `5`, `6`, `7`, `8`]));
41    set.insert(`-----22`);
42    assert(set.prefix(`-----`).equal([`1`, `11`, `2`, `22`, `3`, `4`, `5`, `6`, `7`, `8`]));
43    set.insert(`-----33`);
44    assert(set.prefix(`-----`).equal([`1`, `11`, `2`, `22`, `3`, `33`, `4`, `5`, `6`, `7`, `8`]));
45    set.insert(`-----44`);
46    assert(set.prefix(`-----`).equal([`1`, `11`, `2`, `22`, `3`, `33`, `4`, `44`, `5`, `6`, `7`, `8`]));
47 
48    set.clear();
49    set.insert(`-----11`);
50    assert(set.prefix(`-----`).equal([`11`]));
51    set.insert(`-----22`);
52    assert(set.prefix(`-----`).equal([`11`, `22`]));
53    assert(set.prefix(`-----_`).empty);
54    assert(set.prefix(`-----___`).empty);
55 
56    set.clear();
57    set.insert(`-----111`);
58    assert(set.prefix(`-----`).equal([`111`]));
59    set.insert(`-----122`);
60    assert(set.prefix(`-----`).equal([`111`, `122`]));
61    set.insert(`-----133`);
62    assert(set.prefix(`-----`).equal([`111`, `122`, `133`]));
63    assert(set.prefix(`-----1`).equal([`11`, `22`, `33`]));
64    assert(set.prefix(`-----1_`).empty);
65    assert(set.prefix(`-----1___`).empty);
66 
67    set.clear();
68    set.insert(`-----1111`);
69    assert(set.prefix(`-----`).equal([`1111`]));
70    assert(set.prefix(`-----_`).empty);
71    assert(set.prefix(`-----___`).empty);
72 
73    set.clear();
74    set.insert(`-----11111`);
75    assert(set.prefix(`-----`).equal([`11111`]));
76    assert(set.prefix(`-----_`).empty);
77    assert(set.prefix(`-----___`).empty);
78    set.insert(`-----12222`);
79    assert(set.prefix(`-----`).equal([`11111`, `12222`]));
80    assert(set.prefix(`-----_`).empty);
81    assert(set.prefix(`-----___`).empty);
82    assert(set.prefix(`-----12`).equal([`222`]));
83    assert(set.prefix(`-----12_`).empty);
84    assert(set.prefix(`-----12____`).empty);

version(showAssertTags) dbg();
   alias T = double;

   auto set = radixTreeSet!(T);

   import std.range: isForwardRange;
   static assert(isForwardRange!(typeof(set[])));

   set.insert(-1.1e6);
   set.insert(-2.2e9);
   set.insert(-1.1);
   set.insert(+2.2);
   set.insert(T.max);
   set.insert(-T.max);
   set.insert(-3.3);
   set.insert(-4.4);
   set.insert(+4.4);
   set.insert(+3.3);
   set.insert(+1.1e6);
   set.insert(+2.2e9);

   import std.algorithm.sorting : isSorted;
   assert(set[].isSorted);