9#ifndef INCLUDE_ROARING_64_MAP_HH_
10#define INCLUDE_ROARING_64_MAP_HH_
19#include <initializer_list>
35class Roaring64MapSetBitBiDirectionalIterator;
39typedef Roaring64MapSetBitBiDirectionalIterator
43 typedef api::roaring_bitmap_t roaring_bitmap_t;
117 for (
size_t i = 0; i < n; i++) {
118 ans.
add(va_arg(vl, uint64_t));
130 ans.
addMany(l.size(), l.begin());
137 void add(uint32_t x) { lookupOrCreateInner(0).
add(x); }
142 void add(uint64_t x) { lookupOrCreateInner(highBytes(x)).
add(lowBytes(x)); }
157 return lookupOrCreateInner(highBytes(x)).
addChecked(lowBytes(x));
184 uint32_t start_high = highBytes(min);
185 uint32_t start_low = lowBytes(min);
186 uint32_t end_high = highBytes(max);
187 uint32_t end_low = lowBytes(max);
191 const uint32_t uint32_max = (std::numeric_limits<uint32_t>::max)();
196 auto current_iter = ensureRangePopulated(start_high, end_high);
200 if (start_high == end_high) {
201 auto &bitmap = current_iter->second;
202 bitmap.addRangeClosed(start_low, end_low);
213 auto num_intermediate_bitmaps = end_high - start_high - 1;
217 auto &bitmap = current_iter->second;
218 bitmap.addRangeClosed(start_low, uint32_max);
223 if (num_intermediate_bitmaps != 0) {
224 auto &first_intermediate = current_iter->second;
225 first_intermediate.addRangeClosed(0, uint32_max);
229 for (uint32_t i = 1; i != num_intermediate_bitmaps; ++i) {
230 auto &next_intermediate = current_iter->second;
231 next_intermediate = first_intermediate;
237 auto &bitmap = current_iter->second;
238 bitmap.addRangeClosed(0, end_low);
244 void addMany(
size_t n_args,
const uint32_t *vals) {
245 lookupOrCreateInner(0).
addMany(n_args, vals);
251 void addMany(
size_t n_args,
const uint64_t *vals) {
254 Roaring *last_inner_bitmap =
nullptr;
255 uint32_t last_value_high = 0;
257 for (
size_t lcv = 0; lcv < n_args; lcv++) {
258 auto value = vals[lcv];
259 auto value_high = highBytes(value);
260 auto value_low = lowBytes(value);
261 if (last_inner_bitmap ==
nullptr || value_high != last_value_high) {
262 last_inner_bitmap = &lookupOrCreateInner(value_high);
263 last_value_high = value_high;
266 last_inner_bitmap->
addBulk(last_bulk_context, value_low);
274 auto iter = roarings.begin();
277 if (iter == roarings.end() || iter->first != 0) {
280 auto &bitmap = iter->second;
289 auto iter = roarings.find(highBytes(x));
290 if (iter == roarings.end()) {
293 auto &bitmap = iter->second;
294 bitmap.remove(lowBytes(x));
304 auto iter = roarings.begin();
307 if (iter == roarings.end() || iter->first != 0) {
310 auto &bitmap = iter->second;
311 if (!bitmap.removeChecked(x)) {
324 auto iter = roarings.find(highBytes(x));
325 if (iter == roarings.end()) {
328 auto &bitmap = iter->second;
329 if (!bitmap.removeChecked(lowBytes(x))) {
350 auto iter = roarings.begin();
354 if (iter == roarings.end() || iter->first != 0) {
357 auto &bitmap = iter->second;
358 bitmap.removeRangeClosed(min, max);
369 uint32_t start_high = highBytes(min);
370 uint32_t start_low = lowBytes(min);
371 uint32_t end_high = highBytes(max);
372 uint32_t end_low = lowBytes(max);
376 const uint32_t uint32_max = (std::numeric_limits<uint32_t>::max)();
381 if (roarings.empty() || end_high < roarings.cbegin()->first ||
382 start_high > (roarings.crbegin())->first) {
390 auto start_iter = roarings.lower_bound(start_high);
393 auto end_iter = roarings.lower_bound(end_high);
414 if (start_iter->first == start_high) {
415 auto &start_inner = start_iter->second;
417 if (start_iter == end_iter) {
418 start_inner.removeRangeClosed(start_low, end_low);
419 eraseIfEmpty(start_iter);
424 start_inner.removeRangeClosed(start_low, uint32_max);
427 auto temp = start_iter++;
432 roarings.erase(start_iter, end_iter);
435 if (end_iter != roarings.end() && end_iter->first == end_high) {
436 auto &end_inner = end_iter->second;
437 end_inner.removeRangeClosed(0, end_low);
438 eraseIfEmpty(end_iter);
451 for (
auto roaring_iter = roarings.crbegin();
452 roaring_iter != roarings.crend(); ++roaring_iter) {
453 if (!roaring_iter->second.isEmpty()) {
454 return uniteBytes(roaring_iter->first,
455 roaring_iter->second.maximum());
460 return (std::numeric_limits<uint64_t>::min)();
467 for (
auto roaring_iter = roarings.cbegin();
468 roaring_iter != roarings.cend(); ++roaring_iter) {
469 if (!roaring_iter->second.isEmpty()) {
470 return uniteBytes(roaring_iter->first,
471 roaring_iter->second.minimum());
476 return (std::numeric_limits<uint64_t>::max)();
483 auto iter = roarings.find(0);
484 if (iter == roarings.end()) {
487 return iter->second.contains(x);
490 auto iter = roarings.find(highBytes(x));
491 if (iter == roarings.end()) {
494 return iter->second.contains(lowBytes(x));
508 if (
this == &other) {
527 decltype(roarings.begin()) self_next;
528 for (
auto self_iter = roarings.begin(); self_iter != roarings.end();
529 self_iter = self_next) {
532 self_next = std::next(self_iter);
534 auto self_key = self_iter->first;
535 auto &self_bitmap = self_iter->second;
537 auto other_iter = other.roarings.find(self_key);
538 if (other_iter == other.roarings.end()) {
542 roarings.erase(self_iter);
549 const auto &other_bitmap = other_iter->second;
550 self_bitmap &= other_bitmap;
551 if (self_bitmap.isEmpty()) {
553 roarings.erase(self_iter);
565 if (
this == &other) {
586 auto self_iter = roarings.begin();
587 auto other_iter = other.roarings.cbegin();
589 while (self_iter != roarings.end() &&
590 other_iter != other.roarings.cend()) {
591 auto self_key = self_iter->first;
592 auto other_key = other_iter->first;
593 if (self_key < other_key) {
596 self_iter = roarings.lower_bound(other_key);
600 if (self_key > other_key) {
603 other_iter = other.roarings.lower_bound(self_key);
610 auto &self_bitmap = self_iter->second;
611 const auto &other_bitmap = other_iter->second;
612 self_bitmap -= other_bitmap;
614 if (self_bitmap.isEmpty()) {
616 self_iter = roarings.erase(self_iter);
633 if (
this == &other) {
651 for (
const auto &other_entry : other.roarings) {
652 const auto &other_bitmap = other_entry.second;
657 auto insert_result = roarings.insert(other_entry);
658 auto self_iter = insert_result.first;
659 auto insert_happened = insert_result.second;
660 auto &self_bitmap = self_iter->second;
662 if (insert_happened) {
668 self_bitmap.setCopyOnWrite(copyOnWrite);
675 self_bitmap |= other_bitmap;
685 if (
this == &other) {
705 for (
const auto &other_entry : other.roarings) {
706 const auto &other_bitmap = other_entry.second;
711 auto insert_result = roarings.insert(other_entry);
712 auto self_iter = insert_result.first;
713 auto insert_happened = insert_result.second;
714 auto &self_bitmap = self_iter->second;
716 if (insert_happened) {
722 self_bitmap.setCopyOnWrite(copyOnWrite);
729 self_bitmap ^= other_bitmap;
731 if (self_bitmap.isEmpty()) {
733 roarings.erase(self_iter);
752#if ROARING_EXCEPTIONS
753 throw std::length_error(
754 "bitmap is full, cardinality is 2^64, "
755 "unable to represent in a 64-bit integer");
758 "bitmap is full, cardinality is 2^64, "
759 "unable to represent in a 64-bit integer");
762 return std::accumulate(
763 roarings.cbegin(), roarings.cend(), (uint64_t)0,
764 [](uint64_t previous,
765 const std::pair<const uint32_t, Roaring> &map_entry) {
766 return previous + map_entry.second.cardinality();
775 roarings.cbegin(), roarings.cend(),
776 [](
const std::pair<const uint32_t, Roaring> &map_entry) {
777 return map_entry.second.isEmpty();
787#if SIZE_MAX >= UINT64_MAX
792 return roarings.size() ==
793 ((uint64_t)(std::numeric_limits<uint32_t>::max)()) + 1
794 ? std::all_of(roarings.cbegin(), roarings.cend(),
795 [](
const std::pair<const uint32_t, Roaring>
796 &roaring_map_entry) {
797 return roaring_map_entry.second.isFull();
811 for (
const auto &map_entry : roarings) {
812 if (map_entry.second.isEmpty()) {
815 auto roaring_iter = r.roarings.find(map_entry.first);
816 if (roaring_iter == r.roarings.cend())
818 else if (!map_entry.second.isSubset(roaring_iter->second))
842 (void)std::accumulate(
843 roarings.cbegin(), roarings.cend(), ans,
844 [](uint64_t *previous,
845 const std::pair<const uint32_t, Roaring> &map_entry) {
846 for (uint32_t low_bits : map_entry.second)
847 *previous++ = uniteBytes(map_entry.first, low_bits);
858 auto lhs_iter = roarings.cbegin();
859 auto lhs_cend = roarings.cend();
860 auto rhs_iter = r.roarings.cbegin();
861 auto rhs_cend = r.roarings.cend();
862 while (lhs_iter != lhs_cend && rhs_iter != rhs_cend) {
863 auto lhs_key = lhs_iter->first, rhs_key = rhs_iter->first;
864 const auto &lhs_map = lhs_iter->second, &rhs_map = rhs_iter->second;
865 if (lhs_map.isEmpty()) {
869 if (rhs_map.isEmpty()) {
873 if (!(lhs_key == rhs_key)) {
876 if (!(lhs_map == rhs_map)) {
882 while (lhs_iter != lhs_cend) {
883 if (!lhs_iter->second.isEmpty()) {
888 while (rhs_iter != rhs_cend) {
889 if (!rhs_iter->second.isEmpty()) {
901 void flip(uint64_t min, uint64_t max) {
913 auto iter = roarings.begin();
917 if (iter == roarings.end() || iter->first != 0) {
918 iter = roarings.emplace_hint(iter, std::piecewise_construct,
919 std::forward_as_tuple(0),
920 std::forward_as_tuple());
921 auto &bitmap = iter->second;
922 bitmap.setCopyOnWrite(copyOnWrite);
924 auto &bitmap = iter->second;
925 bitmap.flipClosed(min, max);
937 uint32_t start_high = highBytes(min);
938 uint32_t start_low = lowBytes(min);
939 uint32_t end_high = highBytes(max);
940 uint32_t end_low = lowBytes(max);
944 const uint32_t uint32_max = (std::numeric_limits<uint32_t>::max)();
949 auto current_iter = ensureRangePopulated(start_high, end_high);
953 if (start_high == end_high) {
954 auto &bitmap = current_iter->second;
955 bitmap.flipClosed(start_low, end_low);
956 eraseIfEmpty(current_iter);
968 auto num_intermediate_bitmaps = end_high - start_high - 1;
972 auto &bitmap = current_iter->second;
973 bitmap.flipClosed(start_low, uint32_max);
974 auto temp = current_iter++;
979 for (uint32_t i = 0; i != num_intermediate_bitmaps; ++i) {
980 auto &bitmap = current_iter->second;
981 bitmap.flipClosed(0, uint32_max);
982 auto temp = current_iter++;
987 auto &bitmap = current_iter->second;
988 bitmap.flipClosed(0, end_low);
989 eraseIfEmpty(current_iter);
997 return std::accumulate(
998 roarings.begin(), roarings.end(),
true,
999 [](
bool previous, std::pair<const uint32_t, Roaring> &map_entry) {
1000 return map_entry.second.removeRunCompression() && previous;
1011 return std::accumulate(
1012 roarings.begin(), roarings.end(),
true,
1013 [](
bool previous, std::pair<const uint32_t, Roaring> &map_entry) {
1014 return map_entry.second.runOptimize() && previous;
1023 size_t savedBytes = 0;
1024 auto iter = roarings.begin();
1025 while (iter != roarings.cend()) {
1026 if (iter->second.isEmpty()) {
1029 roarings.erase(iter++);
1031 savedBytes += iter->second.shrinkToFit();
1049 void iterate(api::roaring_iterator64 iterator,
void *ptr)
const {
1050 for (
const auto &map_entry : roarings) {
1051 bool should_continue =
1053 uint64_t(map_entry.first) << 32, ptr);
1054 if (!should_continue) {
1067 for (
const auto &map_entry : roarings) {
1068 auto key = map_entry.first;
1069 const auto &bitmap = map_entry.second;
1071 uint64_t sub_cardinality = bitmap.cardinality();
1072 if (
rank < sub_cardinality) {
1076 if (!bitmap.select((uint32_t)
rank, &low_bytes)) {
1078 "Logic error: bitmap.select() "
1079 "returned false despite rank < cardinality()");
1081 *element = uniteBytes(key, low_bytes);
1084 rank -= sub_cardinality;
1093 uint64_t result = 0;
1098 auto end = roarings.lower_bound(highBytes(x));
1099 if (
end != roarings.cend() &&
end->first == highBytes(x)) {
1100 result +=
end->second.rank(lowBytes(x));
1102 for (
auto iter = roarings.cbegin(); iter !=
end; ++iter) {
1103 result += iter->second.cardinality();
1117 auto roaring_destination = roarings.find(highBytes(x));
1118 if (roaring_destination != roarings.cend()) {
1119 for (
auto roaring_iter = roarings.cbegin();
1120 roaring_iter != roaring_destination; ++roaring_iter) {
1121 index += roaring_iter->second.cardinality();
1123 auto low_idx = roaring_destination->second.getIndex(lowBytes(x));
1124 if (low_idx < 0)
return -1;
1140 size_t write(
char *buf,
bool portable =
true)
const {
1141 const char *orig = buf;
1143 uint64_t map_size = roarings.size();
1144 std::memcpy(buf, &map_size,
sizeof(uint64_t));
1145 buf +=
sizeof(uint64_t);
1146 std::for_each(roarings.cbegin(), roarings.cend(),
1148 const std::pair<const uint32_t, Roaring> &map_entry) {
1150 std::memcpy(buf, &map_entry.first, sizeof(uint32_t));
1154 buf += sizeof(uint32_t);
1156 buf += map_entry.second.write(buf, portable);
1177 std::memcpy(&map_size, buf,
sizeof(uint64_t));
1178 buf +=
sizeof(uint64_t);
1179 for (uint64_t lcv = 0; lcv < map_size; lcv++) {
1182 std::memcpy(&key, buf,
sizeof(uint32_t));
1185 buf +=
sizeof(uint32_t);
1190 result.emplaceOrInsert(key, std::move(read_var));
1203 if (maxbytes <
sizeof(uint64_t)) {
1208 std::memcpy(&map_size, buf,
sizeof(uint64_t));
1209 buf +=
sizeof(uint64_t);
1210 maxbytes -=
sizeof(uint64_t);
1211 for (uint64_t lcv = 0; lcv < map_size; lcv++) {
1212 if (maxbytes <
sizeof(uint32_t)) {
1216 std::memcpy(&key, buf,
sizeof(uint32_t));
1219 buf +=
sizeof(uint32_t);
1220 maxbytes -=
sizeof(uint32_t);
1227 result.emplaceOrInsert(key, std::move(read_var));
1242 return std::accumulate(
1243 roarings.cbegin(), roarings.cend(),
1244 sizeof(uint64_t) + roarings.size() *
sizeof(uint32_t),
1245 [=](
size_t previous,
1246 const std::pair<const uint32_t, Roaring> &map_entry) {
1248 return previous + map_entry.second.getSizeInBytes(portable);
1254 const size_t metadata_size =
sizeof(size_t) +
sizeof(uint32_t);
1260 memcpy(&map_size, buf,
sizeof(uint64_t));
1261 buf +=
sizeof(uint64_t);
1263 for (uint64_t lcv = 0; lcv < map_size; lcv++) {
1265 while (((uintptr_t)buf + metadata_size) % 32 != 0) buf++;
1269 memcpy(&len, buf,
sizeof(
size_t));
1270 buf +=
sizeof(size_t);
1274 memcpy(&key, buf,
sizeof(uint32_t));
1275 buf +=
sizeof(uint32_t);
1279 result.emplaceOrInsert(key,
read);
1291 std::memcpy(&map_size, buf,
sizeof(uint64_t));
1292 buf +=
sizeof(uint64_t);
1293 for (uint64_t lcv = 0; lcv < map_size; lcv++) {
1296 std::memcpy(&key, buf,
sizeof(uint32_t));
1297 buf +=
sizeof(uint32_t);
1302 result.emplaceOrInsert(key, std::move(read_var));
1318 const size_t metadata_size =
sizeof(size_t) +
sizeof(uint32_t);
1321 uint64_t map_size = roarings.size();
1322 memcpy(buf, &map_size,
sizeof(uint64_t));
1323 buf +=
sizeof(uint64_t);
1325 for (
auto &map_entry : roarings) {
1326 size_t frozenSizeInBytes = map_entry.second.getFrozenSizeInBytes();
1329 while (((uintptr_t)buf + metadata_size) % 32 != 0) buf++;
1332 memcpy(buf, &frozenSizeInBytes,
sizeof(
size_t));
1333 buf +=
sizeof(size_t);
1336 memcpy(buf, &map_entry.first,
sizeof(uint32_t));
1337 buf +=
sizeof(uint32_t);
1340 map_entry.second.writeFrozen(buf);
1341 buf += map_entry.second.getFrozenSizeInBytes();
1347 const size_t metadata_size =
sizeof(size_t) +
sizeof(uint32_t);
1351 ret +=
sizeof(uint64_t);
1353 for (
auto &map_entry : roarings) {
1355 while ((ret + metadata_size) % 32 != 0) ret++;
1356 ret += metadata_size;
1359 ret += map_entry.second.getFrozenSizeInBytes();
1405 if (copyOnWrite == val)
return;
1407 std::for_each(roarings.begin(), roarings.end(),
1408 [=](std::pair<const uint32_t, Roaring> &map_entry) {
1409 map_entry.second.setCopyOnWrite(val);
1418 auto sink = [](
const std::string &s) { fputs(s.c_str(), stdout); };
1428 auto sink = [&result](
const std::string &s) { result += s; };
1462 roarings_t::const_iterator iterator;
1463 roarings_t::const_iterator end;
1467 auto pq_comp = [](
const pq_entry &lhs,
const pq_entry &rhs) {
1468 auto left_key = lhs.iterator->first;
1469 auto right_key = rhs.iterator->first;
1474 return left_key > right_key;
1478 std::priority_queue<pq_entry, std::vector<pq_entry>,
decltype(pq_comp)>
1480 for (
size_t i = 0; i < n; ++i) {
1481 const auto &roarings = inputs[i]->roarings;
1482 if (roarings.begin() != roarings.end()) {
1483 pq.push({roarings.begin(), roarings.end()});
1489 std::vector<const roaring_bitmap_t *> group_bitmaps;
1507 while (!pq.empty()) {
1509 auto group_key = pq.top().iterator->first;
1516 group_bitmaps.
clear();
1517 while (!pq.empty()) {
1518 auto candidate_current_iter = pq.top().iterator;
1519 auto candidate_end_iter = pq.top().end;
1521 auto candidate_key = candidate_current_iter->first;
1522 const auto &candidate_bitmap = candidate_current_iter->second;
1529 if (candidate_key != group_key) {
1538 group_bitmaps.push_back(&candidate_bitmap.roaring);
1547 ++candidate_current_iter;
1548 if (candidate_current_iter != candidate_end_iter) {
1549 pq.push({candidate_current_iter, candidate_end_iter});
1555 group_bitmaps.data());
1558 result.roarings.insert(
1559 result.roarings.end(),
1560 std::make_pair(group_key,
Roaring(inner_result)));
1588 typedef std::map<uint32_t, Roaring> roarings_t;
1589 roarings_t roarings{};
1591 bool copyOnWrite{
false};
1592 static constexpr uint32_t highBytes(
const uint64_t in) {
1593 return uint32_t(in >> 32);
1595 static constexpr uint32_t lowBytes(
const uint64_t in) {
1596 return uint32_t(in);
1598 static constexpr uint64_t uniteBytes(
const uint32_t highBytes,
1599 const uint32_t lowBytes) {
1600 return (uint64_t(highBytes) << 32) | uint64_t(lowBytes);
1604 void emplaceOrInsert(
const uint32_t key,
const Roaring &value) {
1605#if defined(__GLIBCXX__) && __GLIBCXX__ < 20130322
1606 roarings.insert(std::make_pair(key, value));
1608 roarings.emplace(std::make_pair(key, value));
1612 void emplaceOrInsert(
const uint32_t key, Roaring &&value) {
1613#if defined(__GLIBCXX__) && __GLIBCXX__ < 20130322
1614 roarings.insert(std::make_pair(key, std::move(value)));
1616 roarings.emplace(key, std::move(value));
1625 Roaring &lookupOrCreateInner(uint32_t key) {
1626 auto &bitmap = roarings[key];
1627 bitmap.setCopyOnWrite(copyOnWrite);
1635 const std::function<
void(
const std::string &)> &sink)
const {
1641 const char *separator =
"";
1643 std::string callback_string;
1644 for (
const auto &entry : roarings) {
1645 auto high_bits = entry.first;
1646 const auto &bitmap = entry.second;
1647 for (
const auto low_bits : bitmap) {
1648 auto value = uniteBytes(high_bits, low_bits);
1649 snprintf(buffer,
sizeof(buffer),
"%" PRIu64, value);
1650 callback_string = separator;
1651 callback_string.append(buffer);
1652 sink(callback_string);
1665 roarings_t::iterator ensureRangePopulated(uint32_t start_high,
1666 uint32_t end_high) {
1667 if (start_high > end_high) {
1672 auto next_populated_iter = roarings.lower_bound(start_high);
1675 roarings_t::iterator start_iter{};
1676 for (uint64_t slot = start_high; slot <= end_high; ++slot) {
1677 roarings_t::iterator slot_iter;
1678 if (next_populated_iter != roarings.end() &&
1679 next_populated_iter->first == slot) {
1682 slot_iter = next_populated_iter++;
1689 slot_iter = roarings.emplace_hint(
1690 next_populated_iter, std::piecewise_construct,
1691 std::forward_as_tuple(uint32_t(slot)),
1692 std::forward_as_tuple());
1693 auto &bitmap = slot_iter->second;
1694 bitmap.setCopyOnWrite(copyOnWrite);
1699 if (slot == start_high) {
1700 start_iter = slot_iter;
1710 void eraseIfEmpty(roarings_t::iterator iter) {
1711 const auto &bitmap = iter->second;
1712 if (bitmap.isEmpty()) {
1713 roarings.erase(iter);
1733 bool exhausted =
false)
1734 : p(&parent.roarings) {
1735 if (exhausted || parent.roarings.empty()) {
1736 map_iter = p->cend();
1738 map_iter = parent.roarings.cbegin();
1740 while (!i.has_value) {
1742 if (map_iter == p->cend())
return;
1752 return Roaring64Map::uniteBytes(map_iter->first, i.current_value);
1756 if (map_iter == p->cend())
return false;
1757 if (o.map_iter == o.p->cend())
return true;
1762 if (o.map_iter == o.p->cend())
return true;
1763 if (map_iter == p->cend())
return false;
1764 return **
this <= *o;
1768 if (o.map_iter == o.p->cend())
return false;
1769 if (map_iter == p->cend())
return true;
1774 if (map_iter == p->cend())
return true;
1775 if (o.map_iter == o.p->cend())
return false;
1776 return **
this >= *o;
1781 while (!i.has_value) {
1783 if (map_iter == p->cend())
return *
this;
1792 while (!i.has_value) {
1794 if (map_iter == p->cend())
return orig;
1805 map_iter = p->lower_bound(Roaring64Map::highBytes(x));
1806 if (map_iter != p->cend()) {
1808 if (map_iter->first == Roaring64Map::highBytes(x)) {
1810 &i, Roaring64Map::lowBytes(x)))
1813 if (map_iter == p->cend())
return false;
1827 if (map_iter == p->cend()) {
1830 if (i.has_value)
return *
this;
1834 while (!i.has_value) {
1835 if (map_iter == p->cbegin())
return *
this;
1844 if (map_iter == p->cend()) {
1851 while (!i.has_value) {
1852 if (map_iter == p->cbegin())
return orig;
1860 if (map_iter == p->cend() && o.map_iter == o.p->cend())
return true;
1861 if (o.map_iter == o.p->cend())
return false;
1862 return **
this == *o;
1866 if (map_iter == p->cend() && o.map_iter == o.p->cend())
return false;
1867 if (o.map_iter == o.p->cend())
return true;
1868 return **
this != *o;
1872 const std::map<uint32_t, Roaring> *p{
nullptr};
1873 std::map<uint32_t, Roaring>::const_iterator
1876 api::roaring_uint32_iterator_t
type_of_iterator & operator++()
type_of_iterator operator++(int)
bool operator<(const type_of_iterator &o) const
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
CROARING_DEPRECATED 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
bool move_equalorlarger(const value_type &x)
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
Roaring64Map & operator^=(const Roaring64Map &other)
uint64_t cardinality() const
const_iterator end() const
Roaring64Map & operator|=(const Roaring64Map &other)
bool contains(uint64_t x) const
Roaring64Map(size_t n, const uint32_t *data)
std::string toString() const
Roaring64Map(const Roaring &r)
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)
Roaring64Map & operator-=(const Roaring64Map &other)
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=(Roaring64Map &&r) noexcept=default
Roaring64Map & operator=(std::initializer_list< uint64_t > l)
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)
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
Roaring64Map & operator&=(const Roaring64Map &other)
void removeRange(uint64_t min, uint64_t max)
void iterate(api::roaring_iterator64 iterator, void *ptr) const
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 & operator=(const Roaring64Map &r)=default
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)
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)
roaring_bitmap_t * roaring_bitmap_or_many(size_t number, const roaring_bitmap_t **rs)
bool roaring_uint32_iterator_move_equalorlarger(roaring_uint32_iterator_t *it, uint32_t val)
bool roaring_uint32_iterator_previous(roaring_uint32_iterator_t *it)
bool roaring_uint32_iterator_advance(roaring_uint32_iterator_t *it)
#define ROARING_TERMINATE(_s)