9 #ifndef INCLUDE_ROARING_64_MAP_HH_
10 #define INCLUDE_ROARING_64_MAP_HH_
18 #include <initializer_list>
34 class Roaring64MapSetBitBiDirectionalIterator;
38 typedef Roaring64MapSetBitBiDirectionalIterator
116 for (
size_t i = 0; i < n; i++) {
117 ans.
add(va_arg(vl, uint64_t));
129 ans.
addMany(l.size(), l.begin());
136 void add(uint32_t x) { lookupOrCreateInner(0).
add(x); }
141 void add(uint64_t x) { lookupOrCreateInner(highBytes(x)).
add(lowBytes(x)); }
156 return lookupOrCreateInner(highBytes(x)).
addChecked(lowBytes(x));
183 uint32_t start_high = highBytes(min);
184 uint32_t start_low = lowBytes(min);
185 uint32_t end_high = highBytes(max);
186 uint32_t end_low = lowBytes(max);
190 const uint32_t uint32_max = (std::numeric_limits<uint32_t>::max)();
195 auto current_iter = ensureRangePopulated(start_high, end_high);
199 if (start_high == end_high) {
200 auto &bitmap = current_iter->second;
201 bitmap.addRangeClosed(start_low, end_low);
212 auto num_intermediate_bitmaps = end_high - start_high - 1;
216 auto &bitmap = current_iter->second;
217 bitmap.addRangeClosed(start_low, uint32_max);
222 if (num_intermediate_bitmaps != 0) {
223 auto &first_intermediate = current_iter->second;
224 first_intermediate.addRangeClosed(0, uint32_max);
228 for (uint32_t i = 1; i != num_intermediate_bitmaps; ++i) {
229 auto &next_intermediate = current_iter->second;
230 next_intermediate = first_intermediate;
236 auto &bitmap = current_iter->second;
237 bitmap.addRangeClosed(0, end_low);
243 void addMany(
size_t n_args,
const uint32_t *vals) {
244 lookupOrCreateInner(0).
addMany(n_args, vals);
250 void addMany(
size_t n_args,
const uint64_t *vals) {
253 Roaring *last_inner_bitmap =
nullptr;
254 uint32_t last_value_high = 0;
256 for (
size_t lcv = 0; lcv < n_args; lcv++) {
257 auto value = vals[lcv];
258 auto value_high = highBytes(value);
259 auto value_low = lowBytes(value);
260 if (last_inner_bitmap ==
nullptr || value_high != last_value_high) {
261 last_inner_bitmap = &lookupOrCreateInner(value_high);
262 last_value_high = value_high;
265 last_inner_bitmap->
addBulk(last_bulk_context, value_low);
273 auto iter = roarings.begin();
276 if (iter == roarings.end() || iter->first != 0) {
279 auto &bitmap = iter->second;
288 auto iter = roarings.find(highBytes(x));
289 if (iter == roarings.end()) {
292 auto &bitmap = iter->second;
293 bitmap.remove(lowBytes(x));
303 auto iter = roarings.begin();
306 if (iter == roarings.end() || iter->first != 0) {
309 auto &bitmap = iter->second;
310 if (!bitmap.removeChecked(x)) {
323 auto iter = roarings.find(highBytes(x));
324 if (iter == roarings.end()) {
327 auto &bitmap = iter->second;
328 if (!bitmap.removeChecked(lowBytes(x))) {
349 auto iter = roarings.begin();
353 if (iter == roarings.end() || iter->first != 0) {
356 auto &bitmap = iter->second;
357 bitmap.removeRangeClosed(min, max);
368 uint32_t start_high = highBytes(min);
369 uint32_t start_low = lowBytes(min);
370 uint32_t end_high = highBytes(max);
371 uint32_t end_low = lowBytes(max);
375 const uint32_t uint32_max = (std::numeric_limits<uint32_t>::max)();
380 if (roarings.empty() || end_high < roarings.cbegin()->first ||
381 start_high > (roarings.crbegin())->first) {
389 auto start_iter = roarings.lower_bound(start_high);
392 auto end_iter = roarings.lower_bound(end_high);
413 if (start_iter->first == start_high) {
414 auto &start_inner = start_iter->second;
416 if (start_iter == end_iter) {
417 start_inner.removeRangeClosed(start_low, end_low);
418 eraseIfEmpty(start_iter);
423 start_inner.removeRangeClosed(start_low, uint32_max);
426 auto temp = start_iter++;
431 roarings.erase(start_iter, end_iter);
434 if (end_iter != roarings.end() && end_iter->first == end_high) {
435 auto &end_inner = end_iter->second;
436 end_inner.removeRangeClosed(0, end_low);
437 eraseIfEmpty(end_iter);
450 for (
auto roaring_iter = roarings.crbegin();
451 roaring_iter != roarings.crend(); ++roaring_iter) {
452 if (!roaring_iter->second.isEmpty()) {
453 return uniteBytes(roaring_iter->first,
454 roaring_iter->second.maximum());
459 return (std::numeric_limits<uint64_t>::min)();
466 for (
auto roaring_iter = roarings.cbegin();
467 roaring_iter != roarings.cend(); ++roaring_iter) {
468 if (!roaring_iter->second.isEmpty()) {
469 return uniteBytes(roaring_iter->first,
470 roaring_iter->second.minimum());
475 return (std::numeric_limits<uint64_t>::max)();
482 auto iter = roarings.find(0);
483 if (iter == roarings.end()) {
486 return iter->second.contains(x);
489 auto iter = roarings.find(highBytes(x));
490 if (iter == roarings.end()) {
493 return iter->second.contains(lowBytes(x));
505 if (
this == &other) {
524 decltype(roarings.begin()) self_next;
525 for (
auto self_iter = roarings.begin(); self_iter != roarings.end();
526 self_iter = self_next) {
529 self_next = std::next(self_iter);
531 auto self_key = self_iter->first;
532 auto &self_bitmap = self_iter->second;
534 auto other_iter = other.roarings.find(self_key);
535 if (other_iter == other.roarings.end()) {
539 roarings.erase(self_iter);
546 const auto &other_bitmap = other_iter->second;
547 self_bitmap &= other_bitmap;
548 if (self_bitmap.isEmpty()) {
550 roarings.erase(self_iter);
562 if (
this == &other) {
583 auto self_iter = roarings.begin();
584 auto other_iter = other.roarings.cbegin();
586 while (self_iter != roarings.end() &&
587 other_iter != other.roarings.cend()) {
588 auto self_key = self_iter->first;
589 auto other_key = other_iter->first;
590 if (self_key < other_key) {
593 self_iter = roarings.lower_bound(other_key);
597 if (self_key > other_key) {
600 other_iter = other.roarings.lower_bound(self_key);
607 auto &self_bitmap = self_iter->second;
608 const auto &other_bitmap = other_iter->second;
609 self_bitmap -= other_bitmap;
611 if (self_bitmap.isEmpty()) {
613 self_iter = roarings.erase(self_iter);
630 if (
this == &other) {
648 for (
const auto &other_entry : other.roarings) {
649 const auto &other_bitmap = other_entry.second;
654 auto insert_result = roarings.insert(other_entry);
655 auto self_iter = insert_result.first;
656 auto insert_happened = insert_result.second;
657 auto &self_bitmap = self_iter->second;
659 if (insert_happened) {
665 self_bitmap.setCopyOnWrite(copyOnWrite);
672 self_bitmap |= other_bitmap;
682 if (
this == &other) {
702 for (
const auto &other_entry : other.roarings) {
703 const auto &other_bitmap = other_entry.second;
708 auto insert_result = roarings.insert(other_entry);
709 auto self_iter = insert_result.first;
710 auto insert_happened = insert_result.second;
711 auto &self_bitmap = self_iter->second;
713 if (insert_happened) {
719 self_bitmap.setCopyOnWrite(copyOnWrite);
726 self_bitmap ^= other_bitmap;
728 if (self_bitmap.isEmpty()) {
730 roarings.erase(self_iter);
749 #if ROARING_EXCEPTIONS
750 throw std::length_error(
751 "bitmap is full, cardinality is 2^64, "
752 "unable to represent in a 64-bit integer");
755 "bitmap is full, cardinality is 2^64, "
756 "unable to represent in a 64-bit integer");
759 return std::accumulate(
760 roarings.cbegin(), roarings.cend(), (uint64_t)0,
761 [](uint64_t previous,
762 const std::pair<const uint32_t, Roaring> &map_entry) {
763 return previous + map_entry.second.cardinality();
772 roarings.cbegin(), roarings.cend(),
773 [](
const std::pair<const uint32_t, Roaring> &map_entry) {
774 return map_entry.second.isEmpty();
786 return roarings.size() ==
787 ((uint64_t)(std::numeric_limits<uint32_t>::max)()) + 1
789 roarings.cbegin(), roarings.cend(),
790 [](
const std::pair<const uint32_t, Roaring>
791 &roaring_map_entry) {
794 return roaring_map_entry.second.cardinality() ==
795 ((uint64_t)(std::numeric_limits<
806 for (
const auto &map_entry : roarings) {
807 if (map_entry.second.isEmpty()) {
810 auto roaring_iter = r.roarings.find(map_entry.first);
811 if (roaring_iter == r.roarings.cend())
813 else if (!map_entry.second.isSubset(roaring_iter->second))
837 (void)std::accumulate(
838 roarings.cbegin(), roarings.cend(), ans,
839 [](uint64_t *previous,
840 const std::pair<const uint32_t, Roaring> &map_entry) {
841 for (uint32_t low_bits : map_entry.second)
842 *previous++ = uniteBytes(map_entry.first, low_bits);
853 auto lhs_iter = roarings.cbegin();
854 auto lhs_cend = roarings.cend();
855 auto rhs_iter = r.roarings.cbegin();
856 auto rhs_cend = r.roarings.cend();
857 while (lhs_iter != lhs_cend && rhs_iter != rhs_cend) {
858 auto lhs_key = lhs_iter->first, rhs_key = rhs_iter->first;
859 const auto &lhs_map = lhs_iter->second, &rhs_map = rhs_iter->second;
860 if (lhs_map.isEmpty()) {
864 if (rhs_map.isEmpty()) {
868 if (!(lhs_key == rhs_key)) {
871 if (!(lhs_map == rhs_map)) {
877 while (lhs_iter != lhs_cend) {
878 if (!lhs_iter->second.isEmpty()) {
883 while (rhs_iter != rhs_cend) {
884 if (!rhs_iter->second.isEmpty()) {
896 void flip(uint64_t min, uint64_t max) {
908 auto iter = roarings.begin();
912 if (iter == roarings.end() || iter->first != 0) {
913 iter = roarings.emplace_hint(iter, std::piecewise_construct,
914 std::forward_as_tuple(0),
915 std::forward_as_tuple());
916 auto &bitmap = iter->second;
917 bitmap.setCopyOnWrite(copyOnWrite);
919 auto &bitmap = iter->second;
920 bitmap.flipClosed(min, max);
932 uint32_t start_high = highBytes(min);
933 uint32_t start_low = lowBytes(min);
934 uint32_t end_high = highBytes(max);
935 uint32_t end_low = lowBytes(max);
939 const uint32_t uint32_max = (std::numeric_limits<uint32_t>::max)();
944 auto current_iter = ensureRangePopulated(start_high, end_high);
948 if (start_high == end_high) {
949 auto &bitmap = current_iter->second;
950 bitmap.flipClosed(start_low, end_low);
951 eraseIfEmpty(current_iter);
963 auto num_intermediate_bitmaps = end_high - start_high - 1;
967 auto &bitmap = current_iter->second;
968 bitmap.flipClosed(start_low, uint32_max);
969 auto temp = current_iter++;
974 for (uint32_t i = 0; i != num_intermediate_bitmaps; ++i) {
975 auto &bitmap = current_iter->second;
976 bitmap.flipClosed(0, uint32_max);
977 auto temp = current_iter++;
982 auto &bitmap = current_iter->second;
983 bitmap.flipClosed(0, end_low);
984 eraseIfEmpty(current_iter);
992 return std::accumulate(
993 roarings.begin(), roarings.end(),
true,
994 [](
bool previous, std::pair<const uint32_t, Roaring> &map_entry) {
995 return map_entry.second.removeRunCompression() && previous;
1006 return std::accumulate(
1007 roarings.begin(), roarings.end(),
true,
1008 [](
bool previous, std::pair<const uint32_t, Roaring> &map_entry) {
1009 return map_entry.second.runOptimize() && previous;
1018 size_t savedBytes = 0;
1019 auto iter = roarings.begin();
1020 while (iter != roarings.cend()) {
1021 if (iter->second.isEmpty()) {
1024 roarings.erase(iter++);
1026 savedBytes += iter->second.shrinkToFit();
1044 void iterate(api::roaring_iterator64 iterator,
void *ptr)
const {
1045 for (
const auto &map_entry : roarings) {
1046 bool should_continue =
1048 uint64_t(map_entry.first) << 32, ptr);
1049 if (!should_continue) {
1062 for (
const auto &map_entry : roarings) {
1063 auto key = map_entry.first;
1064 const auto &bitmap = map_entry.second;
1066 uint64_t sub_cardinality = bitmap.cardinality();
1067 if (
rank < sub_cardinality) {
1071 if (!bitmap.select((uint32_t)
rank, &low_bytes)) {
1073 "Logic error: bitmap.select() "
1074 "returned false despite rank < cardinality()");
1076 *element = uniteBytes(key, low_bytes);
1079 rank -= sub_cardinality;
1088 uint64_t result = 0;
1093 auto end = roarings.lower_bound(highBytes(x));
1094 if (
end != roarings.cend() &&
end->first == highBytes(x)) {
1095 result +=
end->second.rank(lowBytes(x));
1097 for (
auto iter = roarings.cbegin(); iter !=
end; ++iter) {
1098 result += iter->second.cardinality();
1112 auto roaring_destination = roarings.find(highBytes(x));
1113 if (roaring_destination != roarings.cend()) {
1114 for (
auto roaring_iter = roarings.cbegin();
1115 roaring_iter != roaring_destination; ++roaring_iter) {
1116 index += roaring_iter->second.cardinality();
1118 auto low_idx = roaring_destination->second.getIndex(lowBytes(x));
1119 if (low_idx < 0)
return -1;
1135 size_t write(
char *buf,
bool portable =
true)
const {
1136 const char *orig = buf;
1138 uint64_t map_size = roarings.size();
1139 std::memcpy(buf, &map_size,
sizeof(uint64_t));
1140 buf +=
sizeof(uint64_t);
1141 std::for_each(roarings.cbegin(), roarings.cend(),
1143 const std::pair<const uint32_t, Roaring> &map_entry) {
1145 std::memcpy(buf, &map_entry.first, sizeof(uint32_t));
1149 buf += sizeof(uint32_t);
1151 buf += map_entry.second.write(buf, portable);
1172 std::memcpy(&map_size, buf,
sizeof(uint64_t));
1173 buf +=
sizeof(uint64_t);
1174 for (uint64_t lcv = 0; lcv < map_size; lcv++) {
1177 std::memcpy(&key, buf,
sizeof(uint32_t));
1180 buf +=
sizeof(uint32_t);
1185 result.emplaceOrInsert(key, std::move(read_var));
1198 if (maxbytes <
sizeof(uint64_t)) {
1203 std::memcpy(&map_size, buf,
sizeof(uint64_t));
1204 buf +=
sizeof(uint64_t);
1205 maxbytes -=
sizeof(uint64_t);
1206 for (uint64_t lcv = 0; lcv < map_size; lcv++) {
1207 if (maxbytes <
sizeof(uint32_t)) {
1211 std::memcpy(&key, buf,
sizeof(uint32_t));
1214 buf +=
sizeof(uint32_t);
1215 maxbytes -=
sizeof(uint32_t);
1222 result.emplaceOrInsert(key, std::move(read_var));
1237 return std::accumulate(
1238 roarings.cbegin(), roarings.cend(),
1239 sizeof(uint64_t) + roarings.size() *
sizeof(uint32_t),
1240 [=](
size_t previous,
1241 const std::pair<const uint32_t, Roaring> &map_entry) {
1243 return previous + map_entry.second.getSizeInBytes(portable);
1249 const size_t metadata_size =
sizeof(size_t) +
sizeof(uint32_t);
1255 memcpy(&map_size, buf,
sizeof(uint64_t));
1256 buf +=
sizeof(uint64_t);
1258 for (uint64_t lcv = 0; lcv < map_size; lcv++) {
1260 while (((uintptr_t)buf + metadata_size) % 32 != 0) buf++;
1264 memcpy(&len, buf,
sizeof(
size_t));
1265 buf +=
sizeof(size_t);
1269 memcpy(&key, buf,
sizeof(uint32_t));
1270 buf +=
sizeof(uint32_t);
1274 result.emplaceOrInsert(key,
read);
1286 std::memcpy(&map_size, buf,
sizeof(uint64_t));
1287 buf +=
sizeof(uint64_t);
1288 for (uint64_t lcv = 0; lcv < map_size; lcv++) {
1291 std::memcpy(&key, buf,
sizeof(uint32_t));
1292 buf +=
sizeof(uint32_t);
1297 result.emplaceOrInsert(key, std::move(read_var));
1313 const size_t metadata_size =
sizeof(size_t) +
sizeof(uint32_t);
1316 uint64_t map_size = roarings.size();
1317 memcpy(buf, &map_size,
sizeof(uint64_t));
1318 buf +=
sizeof(uint64_t);
1320 for (
auto &map_entry : roarings) {
1321 size_t frozenSizeInBytes = map_entry.second.getFrozenSizeInBytes();
1324 while (((uintptr_t)buf + metadata_size) % 32 != 0) buf++;
1327 memcpy(buf, &frozenSizeInBytes,
sizeof(
size_t));
1328 buf +=
sizeof(size_t);
1331 memcpy(buf, &map_entry.first,
sizeof(uint32_t));
1332 buf +=
sizeof(uint32_t);
1335 map_entry.second.writeFrozen(buf);
1336 buf += map_entry.second.getFrozenSizeInBytes();
1342 const size_t metadata_size =
sizeof(size_t) +
sizeof(uint32_t);
1346 ret +=
sizeof(uint64_t);
1348 for (
auto &map_entry : roarings) {
1350 while ((ret + metadata_size) % 32 != 0) ret++;
1351 ret += metadata_size;
1354 ret += map_entry.second.getFrozenSizeInBytes();
1400 if (copyOnWrite == val)
return;
1402 std::for_each(roarings.begin(), roarings.end(),
1403 [=](std::pair<const uint32_t, Roaring> &map_entry) {
1404 map_entry.second.setCopyOnWrite(val);
1413 auto sink = [](
const std::string &s) { fputs(s.c_str(), stdout); };
1423 auto sink = [&result](
const std::string &s) { result += s; };
1457 roarings_t::const_iterator iterator;
1458 roarings_t::const_iterator
end;
1462 auto pq_comp = [](
const pq_entry &lhs,
const pq_entry &rhs) {
1463 auto left_key = lhs.iterator->first;
1464 auto right_key = rhs.iterator->first;
1469 return left_key > right_key;
1473 std::priority_queue<pq_entry, std::vector<pq_entry>, decltype(pq_comp)>
1475 for (
size_t i = 0; i < n; ++i) {
1476 const auto &roarings = inputs[i]->roarings;
1477 if (roarings.begin() != roarings.end()) {
1478 pq.push({roarings.begin(), roarings.end()});
1484 std::vector<const roaring_bitmap_t *> group_bitmaps;
1502 while (!pq.empty()) {
1504 auto group_key = pq.top().iterator->first;
1511 group_bitmaps.
clear();
1512 while (!pq.empty()) {
1513 auto candidate_current_iter = pq.top().iterator;
1514 auto candidate_end_iter = pq.top().end;
1516 auto candidate_key = candidate_current_iter->first;
1517 const auto &candidate_bitmap = candidate_current_iter->second;
1524 if (candidate_key != group_key) {
1533 group_bitmaps.push_back(&candidate_bitmap.roaring);
1542 ++candidate_current_iter;
1543 if (candidate_current_iter != candidate_end_iter) {
1544 pq.push({candidate_current_iter, candidate_end_iter});
1550 group_bitmaps.data());
1553 result.roarings.insert(
1554 result.roarings.end(),
1555 std::make_pair(group_key,
Roaring(inner_result)));
1583 typedef std::map<uint32_t, Roaring> roarings_t;
1584 roarings_t roarings{};
1586 bool copyOnWrite{
false};
1587 static constexpr uint32_t highBytes(
const uint64_t in) {
1588 return uint32_t(in >> 32);
1590 static constexpr uint32_t lowBytes(
const uint64_t in) {
1591 return uint32_t(in);
1593 static constexpr uint64_t uniteBytes(
const uint32_t highBytes,
1594 const uint32_t lowBytes) {
1595 return (uint64_t(highBytes) << 32) | uint64_t(lowBytes);
1599 void emplaceOrInsert(
const uint32_t key,
const Roaring &value) {
1600 #if defined(__GLIBCXX__) && __GLIBCXX__ < 20130322
1601 roarings.insert(std::make_pair(key, value));
1603 roarings.emplace(std::make_pair(key, value));
1607 void emplaceOrInsert(
const uint32_t key, Roaring &&value) {
1608 #if defined(__GLIBCXX__) && __GLIBCXX__ < 20130322
1609 roarings.insert(std::make_pair(key, std::move(value)));
1611 roarings.emplace(key, std::move(value));
1620 Roaring &lookupOrCreateInner(uint32_t key) {
1621 auto &bitmap = roarings[key];
1622 bitmap.setCopyOnWrite(copyOnWrite);
1630 const std::function<
void(
const std::string &)> &sink)
const {
1636 const char *separator =
"";
1638 std::string callback_string;
1639 for (
const auto &entry : roarings) {
1640 auto high_bits = entry.first;
1641 const auto &bitmap = entry.second;
1642 for (
const auto low_bits : bitmap) {
1643 auto value = uniteBytes(high_bits, low_bits);
1644 snprintf(buffer,
sizeof(buffer),
"%" PRIu64, value);
1645 callback_string = separator;
1646 callback_string.append(buffer);
1647 sink(callback_string);
1660 roarings_t::iterator ensureRangePopulated(uint32_t start_high,
1661 uint32_t end_high) {
1662 if (start_high > end_high) {
1667 auto next_populated_iter = roarings.lower_bound(start_high);
1670 roarings_t::iterator start_iter{};
1671 for (uint64_t slot = start_high; slot <= end_high; ++slot) {
1672 roarings_t::iterator slot_iter;
1673 if (next_populated_iter != roarings.end() &&
1674 next_populated_iter->first == slot) {
1677 slot_iter = next_populated_iter++;
1684 slot_iter = roarings.emplace_hint(
1685 next_populated_iter, std::piecewise_construct,
1686 std::forward_as_tuple(uint32_t(slot)),
1687 std::forward_as_tuple());
1688 auto &bitmap = slot_iter->second;
1689 bitmap.setCopyOnWrite(copyOnWrite);
1694 if (slot == start_high) {
1695 start_iter = slot_iter;
1705 void eraseIfEmpty(roarings_t::iterator iter) {
1706 const auto &bitmap = iter->second;
1707 if (bitmap.isEmpty()) {
1708 roarings.erase(iter);
1726 bool exhausted =
false)
1727 : p(&parent.roarings) {
1728 if (exhausted || parent.roarings.empty()) {
1729 map_iter = p->cend();
1731 map_iter = parent.roarings.cbegin();
1733 while (!i.has_value) {
1735 if (map_iter == p->cend())
return;
1745 return Roaring64Map::uniteBytes(map_iter->first, i.current_value);
1749 if (map_iter == p->cend())
return false;
1750 if (o.map_iter == o.p->cend())
return true;
1755 if (o.map_iter == o.p->cend())
return true;
1756 if (map_iter == p->cend())
return false;
1757 return **
this <= *o;
1761 if (o.map_iter == o.p->cend())
return false;
1762 if (map_iter == p->cend())
return true;
1767 if (map_iter == p->cend())
return true;
1768 if (o.map_iter == o.p->cend())
return false;
1769 return **
this >= *o;
1774 while (!i.has_value) {
1776 if (map_iter == p->cend())
return *
this;
1785 while (!i.has_value) {
1787 if (map_iter == p->cend())
return orig;
1794 map_iter = p->lower_bound(Roaring64Map::highBytes(x));
1795 if (map_iter != p->cend()) {
1797 if (map_iter->first == Roaring64Map::highBytes(x)) {
1799 &i, Roaring64Map::lowBytes(x)))
1802 if (map_iter == p->cend())
return false;
1811 if (map_iter == p->cend()) {
1814 if (i.has_value)
return *
this;
1818 while (!i.has_value) {
1819 if (map_iter == p->cbegin())
return *
this;
1828 if (map_iter == p->cend()) {
1835 while (!i.has_value) {
1836 if (map_iter == p->cbegin())
return orig;
1844 if (map_iter == p->cend() && o.map_iter == o.p->cend())
return true;
1845 if (o.map_iter == o.p->cend())
return false;
1846 return **
this == *o;
1850 if (map_iter == p->cend() && o.map_iter == o.p->cend())
return false;
1851 if (o.map_iter == o.p->cend())
return true;
1852 return **
this != *o;
1856 const std::map<uint32_t, Roaring> *p{
nullptr};
1857 std::map<uint32_t, Roaring>::const_iterator
type_of_iterator operator++(int)
bool operator<(const type_of_iterator &o) const
type_of_iterator & operator--()
bool operator<=(const type_of_iterator &o) const
bool operator!=(const Roaring64MapSetBitBiDirectionalIterator &o) const
Roaring64MapSetBitBiDirectionalIterator(const Roaring64Map &parent, bool exhausted=false)
bool operator>(const type_of_iterator &o) const
bool move(const value_type &x)
value_type operator*() const
std::bidirectional_iterator_tag iterator_category
type_of_iterator operator--(int)
bool operator==(const Roaring64MapSetBitBiDirectionalIterator &o) const
Roaring64MapSetBitBiDirectionalIterator type_of_iterator
bool operator>=(const type_of_iterator &o) const
type_of_iterator & operator++()
void addMany(size_t n_args, const uint32_t *vals)
bool removeRunCompression()
void flip(uint64_t min, uint64_t max)
friend class Roaring64MapSetBitBiDirectionalIterator
Roaring64Map(size_t n, const uint64_t *data)
uint64_t rank(uint64_t x) const
size_t getFrozenSizeInBytes() const
Roaring64Map operator-(const Roaring64Map &o) const
void flipClosed(uint32_t min, uint32_t max)
bool contains(uint32_t x) const
uint64_t cardinality() const
const_iterator end() const
bool contains(uint64_t x) const
Roaring64Map(size_t n, const uint32_t *data)
Roaring64Map & operator|=(const Roaring64Map &other)
Roaring64Map & operator=(std::initializer_list< uint64_t > l)
Roaring64Map & operator&=(const Roaring64Map &other)
std::string toString() const
Roaring64Map(const Roaring &r)
Roaring64Map & operator=(const Roaring64Map &r)=default
Roaring64MapSetBitBiDirectionalIterator const_iterator
bool operator==(const Roaring64Map &r) const
bool isSubset(const Roaring64Map &r) const
const_iterator begin() const
size_t write(char *buf, bool portable=true) const
void removeRangeClosed(uint64_t min, uint64_t max)
bool removeChecked(uint32_t x)
Roaring64Map operator|(const Roaring64Map &o) const
bool addChecked(uint64_t x)
void addRangeClosed(uint64_t min, uint64_t max)
bool getCopyOnWrite() const
Roaring64Map(Roaring &&r)
static Roaring64Map readSafe(const char *buf, size_t maxbytes)
static Roaring64Map fastunion(size_t n, const Roaring64Map **inputs)
Roaring64Map & operator^=(const Roaring64Map &other)
Roaring64Map(const Roaring64Map &r)=default
Roaring64Map operator^(const Roaring64Map &o) const
static const Roaring64Map frozenView(const char *buf)
static Roaring64Map read(const char *buf, bool portable=true)
void addMany(size_t n_args, const uint64_t *vals)
static Roaring64Map bitmapOfList(std::initializer_list< uint64_t > l)
void addRange(uint64_t min, uint64_t max)
Roaring64Map operator&(const Roaring64Map &o) const
static Roaring64Map bitmapOf(size_t n...)
bool removeChecked(uint64_t x)
Roaring64Map(roaring_bitmap_t *s)
Roaring64Map & operator-=(const Roaring64Map &other)
Roaring64MapSetBitBiDirectionalIterator const_bidirectional_iterator
void setCopyOnWrite(bool val)
Roaring64Map(Roaring64Map &&r) noexcept=default
void flipClosed(uint64_t min, uint64_t max)
void toUint64Array(uint64_t *ans) const
static const Roaring64Map portableDeserializeFrozen(const char *buf)
size_t getSizeInBytes(bool portable=true) const
void removeRange(uint64_t min, uint64_t max)
void iterate(api::roaring_iterator64 iterator, void *ptr) const
Roaring64Map & operator=(Roaring64Map &&r) noexcept=default
void removeRangeClosed(uint32_t min, uint32_t max)
void swap(Roaring64Map &r)
void addRangeClosed(uint32_t min, uint32_t max)
bool select(uint64_t rank, uint64_t *element) const
void writeFrozen(char *buf) const
Roaring64Map(std::initializer_list< uint64_t > l)
bool isStrictSubset(const Roaring64Map &r) const
bool addChecked(uint32_t x)
int64_t getIndex(uint64_t x) const
static Roaring readSafe(const char *buf, size_t maxbytes)
bool addChecked(uint32_t x) noexcept
void addRangeClosed(const uint32_t min, const uint32_t max) noexcept
static Roaring read(const char *buf, bool portable=true)
void add(uint32_t x) noexcept
void addBulk(BulkContext &context, uint32_t x) noexcept
void addMany(size_t n_args, const uint32_t *vals) noexcept
static const Roaring frozenView(const char *buf, size_t length)
static const Roaring portableDeserializeFrozen(const char *buf)
size_t getSizeInBytes(bool portable=true) const noexcept
Roaring64MapSetBitBiDirectionalIterator Roaring64MapSetBitForwardIterator
void roaring_iterator_init_last(const roaring_bitmap_t *r, roaring_uint32_iterator_t *newit)
roaring_bitmap_t * roaring_bitmap_or_many(size_t number, const roaring_bitmap_t **rs)
bool roaring_iterate64(const roaring_bitmap_t *r, roaring_iterator64 iterator, uint64_t high_bits, void *ptr)
void roaring_iterator_init(const roaring_bitmap_t *r, roaring_uint32_iterator_t *newit)
bool roaring_uint32_iterator_move_equalorlarger(roaring_uint32_iterator_t *it, uint32_t val)
bool roaring_uint32_iterator_previous(roaring_uint32_iterator_t *it)
struct roaring_bitmap_s roaring_bitmap_t
struct roaring_uint32_iterator_s roaring_uint32_iterator_t
bool roaring_uint32_iterator_advance(roaring_uint32_iterator_t *it)
#define ROARING_TERMINATE(_s)