1#include <roaring/array_util.h>
2#include <roaring/containers/mixed_subset.h>
3
4bool array_container_is_subset_bitset(const array_container_t* container1,
5 const bitset_container_t* container2) {
6 if (container2->cardinality != BITSET_UNKNOWN_CARDINALITY) {
7 if (container2->cardinality < container1->cardinality) {
8 return false;
9 }
10 }
11 for (int i = 0; i < container1->cardinality; ++i) {
12 if (!bitset_container_contains(container2, container1->array[i])) {
13 return false;
14 }
15 }
16 return true;
17}
18
19bool run_container_is_subset_array(const run_container_t* container1,
20 const array_container_t* container2) {
21 if (run_container_cardinality(container1) > container2->cardinality)
22 return false;
23 int32_t start_pos = -1, stop_pos = -1;
24 for (int i = 0; i < container1->n_runs; ++i) {
25 int32_t start = container1->runs[i].value;
26 int32_t stop = start + container1->runs[i].length;
27 start_pos = advanceUntil(container2->array, stop_pos,
28 container2->cardinality, start);
29 stop_pos = advanceUntil(container2->array, stop_pos,
30 container2->cardinality, stop);
31 if (start_pos == container2->cardinality) {
32 return false;
33 } else if (stop_pos - start_pos != stop - start ||
34 container2->array[start_pos] != start ||
35 container2->array[stop_pos] != stop) {
36 return false;
37 }
38 }
39 return true;
40}
41
42bool array_container_is_subset_run(const array_container_t* container1,
43 const run_container_t* container2) {
44 if (container1->cardinality > run_container_cardinality(container2))
45 return false;
46 int i_array = 0, i_run = 0;
47 while (i_array < container1->cardinality && i_run < container2->n_runs) {
48 uint32_t start = container2->runs[i_run].value;
49 uint32_t stop = start + container2->runs[i_run].length;
50 if (container1->array[i_array] < start) {
51 return false;
52 } else if (container1->array[i_array] > stop) {
53 i_run++;
54 } else { // the value of the array is in the run
55 i_array++;
56 }
57 }
58 if (i_array == container1->cardinality) {
59 return true;
60 } else {
61 return false;
62 }
63}
64
65bool run_container_is_subset_bitset(const run_container_t* container1,
66 const bitset_container_t* container2) {
67 // todo: this code could be much faster
68 if (container2->cardinality != BITSET_UNKNOWN_CARDINALITY) {
69 if (container2->cardinality < run_container_cardinality(container1)) {
70 return false;
71 }
72 } else {
73 int32_t card = bitset_container_compute_cardinality(
74 container2); // modify container2?
75 if (card < run_container_cardinality(container1)) {
76 return false;
77 }
78 }
79 for (int i = 0; i < container1->n_runs; ++i) {
80 uint32_t run_start = container1->runs[i].value;
81 uint32_t le = container1->runs[i].length;
82 for (uint32_t j = run_start; j <= run_start + le; ++j) {
83 if (!bitset_container_contains(container2, j)) {
84 return false;
85 }
86 }
87 }
88 return true;
89}
90
91bool bitset_container_is_subset_run(const bitset_container_t* container1,
92 const run_container_t* container2) {
93 // todo: this code could be much faster
94 if (container1->cardinality != BITSET_UNKNOWN_CARDINALITY) {
95 if (container1->cardinality > run_container_cardinality(container2)) {
96 return false;
97 }
98 }
99 int32_t i_bitset = 0, i_run = 0;
100 while (i_bitset < BITSET_CONTAINER_SIZE_IN_WORDS &&
101 i_run < container2->n_runs) {
102 uint64_t w = container1->array[i_bitset];
103 while (w != 0 && i_run < container2->n_runs) {
104 uint32_t start = container2->runs[i_run].value;
105 uint32_t stop = start + container2->runs[i_run].length;
106 uint64_t t = w & (~w + 1);
107 uint16_t r = i_bitset * 64 + __builtin_ctzll(w);
108 if (r < start) {
109 return false;
110 } else if (r > stop) {
111 i_run++;
112 continue;
113 } else {
114 w ^= t;
115 }
116 }
117 if (w == 0) {
118 i_bitset++;
119 } else {
120 return false;
121 }
122 }
123 if (i_bitset < BITSET_CONTAINER_SIZE_IN_WORDS) {
124 // terminated iterating on the run containers, check that rest of bitset
125 // is empty
126 for (; i_bitset < BITSET_CONTAINER_SIZE_IN_WORDS; i_bitset++) {
127 if (container1->array[i_bitset] != 0) {
128 return false;
129 }
130 }
131 }
132 return true;
133}
134