1use core::cmp::Ordering;
2use core::mem::size_of;
3use core::ops::{RangeBounds, RangeInclusive};
4
5use crate::bitmap::store::BITMAP_LENGTH;
6use crate::{IntegerTooSmall, RoaringBitmap};
7
8use super::container::Container;
9use super::util;
10
11#[cfg(not(feature = "std"))]
12use alloc::vec::Vec;
13
14impl RoaringBitmap {
15 pub fn new() -> RoaringBitmap {
24 RoaringBitmap { containers: Vec::new() }
25 }
26
27 pub fn full() -> RoaringBitmap {
36 RoaringBitmap { containers: (0..=u16::MAX).map(Container::full).collect() }
37 }
38
39 pub fn from_lsb0_bytes(offset: u32, mut bytes: &[u8]) -> RoaringBitmap {
88 fn shift_bytes(bytes: &[u8], amount: usize) -> Vec<u8> {
89 let mut result = Vec::with_capacity(bytes.len() + 1);
90 let mut carry = 0u8;
91
92 for &byte in bytes {
93 let shifted = (byte << amount) | carry;
94 carry = byte >> (8 - amount);
95 result.push(shifted);
96 }
97
98 if carry != 0 {
99 result.push(carry);
100 }
101
102 result
103 }
104 if offset % 8 != 0 {
105 let shift = offset as usize % 8;
106 let shifted_bytes = shift_bytes(bytes, shift);
107 return RoaringBitmap::from_lsb0_bytes(offset - shift as u32, &shifted_bytes);
108 }
109
110 if bytes.is_empty() {
111 return RoaringBitmap::new();
112 }
113
114 let end_bit_inc = u32::try_from(bytes.len())
116 .ok()
117 .and_then(|len_bytes| len_bytes.checked_mul(8))
118 .and_then(|len_bits| offset.checked_add(len_bits - 1))
120 .expect("offset + bytes.len() must be <= 2^32");
121
122 let (mut start_container, start_offset) =
124 (offset as usize >> 16, (offset as usize % 0x1_0000) / 8);
125 let (end_container_inc, end_offset) =
126 (end_bit_inc as usize >> 16, (end_bit_inc as usize % 0x1_0000 + 1) / 8);
127
128 let n_containers_needed = end_container_inc + 1 - start_container;
129 let mut containers = Vec::with_capacity(n_containers_needed);
130
131 if start_offset != 0 {
133 let end_byte = if end_container_inc == start_container {
134 end_offset
135 } else {
136 BITMAP_LENGTH * size_of::<u64>()
137 };
138
139 let (src, rest) = bytes.split_at(end_byte - start_offset);
140 bytes = rest;
141
142 if let Some(container) =
143 Container::from_lsb0_bytes(start_container as u16, src, start_offset)
144 {
145 containers.push(container);
146 }
147
148 start_container += 1;
149 }
150
151 for full_container_key in start_container..end_container_inc {
153 let (src, rest) = bytes.split_at(BITMAP_LENGTH * size_of::<u64>());
154 bytes = rest;
155
156 if let Some(container) = Container::from_lsb0_bytes(full_container_key as u16, src, 0) {
157 containers.push(container);
158 }
159 }
160
161 if !bytes.is_empty() {
163 if let Some(container) = Container::from_lsb0_bytes(end_container_inc as u16, bytes, 0)
164 {
165 containers.push(container);
166 }
167 }
168
169 RoaringBitmap { containers }
170 }
171
172 #[inline]
187 pub fn insert(&mut self, value: u32) -> bool {
188 let (key, index) = util::split(value);
189 let container = match self.containers.binary_search_by_key(&key, |c| c.key) {
190 Ok(loc) => &mut self.containers[loc],
191 Err(loc) => {
192 self.containers.insert(loc, Container::new(key));
193 &mut self.containers[loc]
194 }
195 };
196 container.insert(index)
197 }
198
199 #[inline]
204 pub(crate) fn find_container_by_key(&mut self, key: u16) -> usize {
205 match self.containers.binary_search_by_key(&key, |c| c.key) {
206 Ok(loc) => loc,
207 Err(loc) => {
208 self.containers.insert(loc, Container::new(key));
209 loc
210 }
211 }
212 }
213
214 #[inline]
219 pub(crate) fn mod_or_build_container_by_key<
220 R,
221 M: FnMut(&mut Container) -> R,
222 B: FnMut(u16) -> (Container, R),
223 >(
224 &mut self,
225 key: u16,
226 mut modifier: M,
227 mut builder: B,
228 ) -> R {
229 match self.containers.binary_search_by_key(&key, |c| c.key) {
230 Ok(loc) => modifier(&mut self.containers[loc]),
231 Err(loc) => {
232 let build_value = builder(key);
233 self.containers.insert(loc, build_value.0);
234 build_value.1
235 }
236 }
237 }
238
239 #[inline]
254 pub fn insert_range<R>(&mut self, range: R) -> u64
255 where
256 R: RangeBounds<u32>,
257 {
258 let (start, end) = match util::convert_range_to_inclusive(range) {
259 Ok(range) => (*range.start(), *range.end()),
260 Err(_) => return 0,
261 };
262
263 let (start_container_key, start_index) = util::split(start);
264 let (end_container_key, end_index) = util::split(end);
265 let modify_container_range =
266 |bitmap: &mut Self, container_key: u16, range: RangeInclusive<u16>| {
267 bitmap.mod_or_build_container_by_key(
268 container_key,
269 |container| container.insert_range(range.clone()),
270 |key| (Container::new_with_range(key, range.clone()), range.len() as u64),
271 )
272 };
273
274 if start_container_key == end_container_key {
277 return modify_container_range(self, start_container_key, start_index..=end_index);
278 }
279
280 let mut low = start_index;
286 let mut inserted = 0;
287
288 for i in start_container_key..end_container_key {
289 inserted += modify_container_range(self, i, low..=u16::MAX);
290
291 low = 0;
293 }
294
295 inserted += modify_container_range(self, end_container_key, 0..=end_index);
297
298 inserted
299 }
300
301 #[inline]
319 #[deprecated(since = "0.11.0", note = "use `try_push` instead")]
320 pub fn push(&mut self, value: u32) -> bool {
321 self.try_push(value).is_ok()
322 }
323
324 #[inline]
342 pub fn try_push(&mut self, value: u32) -> Result<(), IntegerTooSmall> {
343 let (key, index) = util::split(value);
344
345 match self.containers.last_mut() {
346 Some(container) if container.key == key => {
347 if container.push(index) {
348 Ok(())
349 } else {
350 Err(IntegerTooSmall)
351 }
352 }
353 Some(container) if container.key > key => Err(IntegerTooSmall),
354 _otherwise => {
355 let mut container = Container::new(key);
356 container.push(index);
357 self.containers.push(container);
358 Ok(())
359 }
360 }
361 }
362
363 #[inline]
370 pub(crate) fn push_unchecked(&mut self, value: u32) {
371 let (key, index) = util::split(value);
372
373 match self.containers.last_mut() {
374 Some(container) if container.key == key => container.push_unchecked(index),
375 Some(container) if cfg!(debug_assertions) && container.key > key => {
376 panic!("last container key > key of value")
377 }
378 _otherwise => {
379 let mut container = Container::new(key);
380 container.push_unchecked(index);
381 self.containers.push(container);
382 }
383 }
384 }
385
386 #[inline]
400 pub fn remove(&mut self, value: u32) -> bool {
401 let (key, index) = util::split(value);
402 match self.containers.binary_search_by_key(&key, |c| c.key) {
403 Ok(loc) => {
404 if self.containers[loc].remove(index) {
405 if self.containers[loc].is_empty() {
406 self.containers.remove(loc);
407 }
408 true
409 } else {
410 false
411 }
412 }
413 _ => false,
414 }
415 }
416
417 #[inline]
431 pub fn remove_range<R>(&mut self, range: R) -> u64
432 where
433 R: RangeBounds<u32>,
434 {
435 let (start, end) = match util::convert_range_to_inclusive(range) {
436 Ok(range) => (*range.start(), *range.end()),
437 Err(_) => return 0,
438 };
439
440 let (start_container_key, start_index) = util::split(start);
441 let (end_container_key, end_index) = util::split(end);
442
443 let mut index = 0;
444 let mut removed = 0;
445 while index < self.containers.len() {
446 let key = self.containers[index].key;
447 if key >= start_container_key && key <= end_container_key {
448 let a = if key == start_container_key { start_index } else { 0 };
449 let b = if key == end_container_key { end_index } else { u16::MAX };
450 removed += self.containers[index].remove_range(a..=b);
451 if self.containers[index].is_empty() {
452 self.containers.remove(index);
453 continue;
454 }
455 }
456 index += 1;
457 }
458 removed
459 }
460
461 #[inline]
475 pub fn contains(&self, value: u32) -> bool {
476 let (key, index) = util::split(value);
477 match self.containers.binary_search_by_key(&key, |c| c.key) {
478 Ok(loc) => self.containers[loc].contains(index),
479 Err(_) => false,
480 }
481 }
482
483 #[inline]
503 pub fn contains_range<R>(&self, range: R) -> bool
504 where
505 R: RangeBounds<u32>,
506 {
507 let (start, end) = match util::convert_range_to_inclusive(range) {
508 Ok(range) => (*range.start(), *range.end()),
509 Err(_) => return true,
511 };
512 let (start_high, start_low) = util::split(start);
513 let (end_high, end_low) = util::split(end);
514 debug_assert!(start_high <= end_high);
515
516 let containers =
517 match self.containers.binary_search_by_key(&start_high, |container| container.key) {
518 Ok(i) => &self.containers[i..],
519 Err(_) => return false,
520 };
521
522 if start_high == end_high {
523 return containers[0].contains_range(start_low..=end_low);
524 }
525
526 let high_span = usize::from(end_high - start_high);
527 let containers = match containers.get(high_span) {
530 Some(c) if c.key == end_high => &containers[..=high_span],
531 _ => return false,
532 };
533
534 match containers {
535 [first, rest @ .., last] => {
536 first.contains_range(start_low..=u16::MAX)
537 && rest.iter().all(|container| container.is_full())
538 && last.contains_range(0..=end_low)
539 }
540 _ => unreachable!("already validated containers has at least 2 items"),
541 }
542 }
543
544 #[inline]
564 pub fn range_cardinality<R>(&self, range: R) -> u64
565 where
566 R: RangeBounds<u32>,
567 {
568 let (start, end) = match util::convert_range_to_inclusive(range) {
569 Ok(range) => (*range.start(), *range.end()),
570 Err(_) => return 0,
572 };
573
574 let (start_key, start_low) = util::split(start);
575 let (end_key, end_low) = util::split(end);
576
577 let mut cardinality = 0;
578
579 let i = match self.containers.binary_search_by_key(&start_key, |c| c.key) {
580 Ok(i) => {
581 let container = &self.containers[i];
582 if start_key == end_key {
583 cardinality += container.rank(end_low)
584 } else {
585 cardinality += container.len();
586 }
587 if start_low != 0 {
588 cardinality -= container.rank(start_low - 1);
589 }
590 i + 1
591 }
592 Err(i) => i,
593 };
594 for container in &self.containers[i..] {
595 match container.key.cmp(&end_key) {
596 Ordering::Less => cardinality += container.len(),
597 Ordering::Equal => {
598 cardinality += container.rank(end_low);
599 break;
600 }
601 Ordering::Greater => {
602 break;
603 }
604 }
605 }
606
607 cardinality
608 }
609
610 #[inline]
624 pub fn clear(&mut self) {
625 self.containers.clear();
626 }
627
628 #[inline]
642 pub fn is_empty(&self) -> bool {
643 self.containers.is_empty()
644 }
645
646 #[inline]
658 pub fn is_full(&self) -> bool {
659 self.containers.len() == (u16::MAX as usize + 1)
660 && self.containers.iter().all(Container::is_full)
661 }
662
663 #[inline]
681 pub fn len(&self) -> u64 {
682 self.containers.iter().map(|container| container.len()).sum()
683 }
684
685 #[inline]
700 pub fn min(&self) -> Option<u32> {
701 self.containers.first().and_then(|tail| tail.min().map(|min| util::join(tail.key, min)))
702 }
703
704 #[inline]
719 pub fn max(&self) -> Option<u32> {
720 self.containers.last().and_then(|tail| tail.max().map(|max| util::join(tail.key, max)))
721 }
722
723 #[inline]
739 pub fn rank(&self, value: u32) -> u64 {
740 let (key, index) = util::split(value);
743
744 match self.containers.binary_search_by_key(&key, |c| c.key) {
745 Ok(i) => {
746 unsafe { self.containers.get_unchecked(i) }.rank(index)
750 + self.containers[..i].iter().rev().map(|c| c.len()).sum::<u64>()
751 }
752 Err(i) => self.containers[..i].iter().map(|c| c.len()).sum(),
753 }
754 }
755
756 #[inline]
774 pub fn select(&self, n: u32) -> Option<u32> {
775 let mut n = n as u64;
776
777 for container in &self.containers {
778 let len = container.len();
779 if len > n {
780 return container
781 .store
782 .select(n as u16)
783 .map(|index| util::join(container.key, index));
784 }
785 n -= len;
786 }
787
788 None
789 }
790
791 #[inline]
806 pub fn remove_smallest(&mut self, mut n: u64) {
807 let position = self.containers.iter().position(|container| {
809 let container_len = container.len();
810 if container_len <= n {
811 n -= container_len;
812 false
813 } else {
814 true
815 }
816 });
817 let position = position.unwrap_or(self.containers.len());
818 if position > 0 {
819 self.containers.drain(..position);
820 }
821 if n > 0 && !self.containers.is_empty() {
823 self.containers[0].remove_smallest(n);
825 }
826 }
827
828 #[inline]
841 pub fn remove_biggest(&mut self, mut n: u64) {
842 let position = self.containers.iter().rposition(|container| {
844 let container_len = container.len();
845 if container_len <= n {
846 n -= container_len;
847 false
848 } else {
849 true
850 }
851 });
852 if let Some(position) = position {
854 self.containers.drain(position + 1..);
855 if n > 0 && !self.containers.is_empty() {
856 self.containers[position].remove_biggest(n);
857 }
858 } else {
859 self.containers.clear();
860 }
861 }
862
863 pub fn optimize(&mut self) -> bool {
875 let mut changed = false;
876 for container in &mut self.containers {
877 changed |= container.optimize()
878 }
879 changed
880 }
881
882 pub fn remove_run_compression(&mut self) -> bool {
896 let mut changed = false;
897 for container in &mut self.containers {
898 changed |= container.remove_run_compression()
899 }
900 changed
901 }
902
903 #[doc(hidden)]
912 pub fn internal_validate(&self) -> Result<(), &'static str> {
913 for window in self.containers.windows(2) {
914 let [first, second] = window else { unreachable!() };
915 if second.key <= first.key {
916 return Err("keys are not strictly increasing");
917 }
918 }
919 for container in &self.containers {
920 container.store.internal_validate()?;
921 }
922 Ok(())
923 }
924}
925
926impl Default for RoaringBitmap {
927 fn default() -> RoaringBitmap {
928 RoaringBitmap::new()
929 }
930}
931
932impl Clone for RoaringBitmap {
933 fn clone(&self) -> Self {
934 RoaringBitmap { containers: self.containers.clone() }
935 }
936
937 fn clone_from(&mut self, other: &Self) {
938 self.containers.clone_from(&other.containers);
939 }
940}
941
942#[cfg(test)]
943mod tests {
944 use proptest::collection::vec;
945 use proptest::prelude::*;
946
947 use super::*;
948
949 proptest! {
950 #[test]
951 fn insert_range(
952 lo in 0u32..=65535, hi in 65536u32..=131071,
953 checks in vec(0u32..=262143, 1000)
954 ){
955 let r = lo..hi;
956 let mut b = RoaringBitmap::new();
957 let inserted = b.insert_range(r.clone());
958 if r.end > r.start {
959 assert_eq!(inserted, r.end as u64 - r.start as u64);
960 } else {
961 assert_eq!(inserted, 0);
962 }
963
964 for i in r.clone() {
966 assert!(b.contains(i), "does not contain {i}");
967 }
968
969 for i in checks {
971 let bitmap_has = b.contains(i);
972 let range_has = r.contains(&i);
973 assert_eq!(
974 bitmap_has, range_has,
975 "value {i} in bitmap={bitmap_has} and range={range_has}"
976 );
977 }
978 }
979 }
980
981 #[test]
982 fn test_insert_remove_range_same_container() {
983 let mut b = RoaringBitmap::new();
984 let inserted = b.insert_range(1..5);
985 assert_eq!(inserted, 4);
986
987 for i in 1..5 {
988 assert!(b.contains(i));
989 }
990
991 let removed = b.remove_range(2..10);
992 assert_eq!(removed, 3);
993 assert!(b.contains(1));
994 for i in 2..5 {
995 assert!(!b.contains(i));
996 }
997 }
998
999 #[test]
1000 fn test_insert_remove_range_pre_populated() {
1001 let mut b = RoaringBitmap::new();
1002 let inserted = b.insert_range(1..20_000);
1003 assert_eq!(inserted, 19_999);
1004
1005 let removed = b.remove_range(10_000..21_000);
1006 assert_eq!(removed, 10_000);
1007
1008 let inserted = b.insert_range(1..20_000);
1009 assert_eq!(inserted, 10_000);
1010 }
1011
1012 #[test]
1013 fn test_insert_max_u32() {
1014 let mut b = RoaringBitmap::new();
1015 let inserted = b.insert(u32::MAX);
1016 assert!(inserted);
1018 }
1019
1020 #[test]
1021 fn test_insert_remove_across_container() {
1022 let mut b = RoaringBitmap::new();
1023 let inserted = b.insert_range(u16::MAX as u32..=u16::MAX as u32 + 1);
1024 assert_eq!(inserted, 2);
1025
1026 assert_eq!(b.containers.len(), 2);
1027
1028 let removed = b.remove_range(u16::MAX as u32 + 1..=u16::MAX as u32 + 1);
1029 assert_eq!(removed, 1);
1030
1031 assert_eq!(b.containers.len(), 1);
1032 }
1033
1034 #[test]
1035 fn test_insert_remove_single_element() {
1036 let mut b = RoaringBitmap::new();
1037 let inserted = b.insert_range(u16::MAX as u32 + 1..=u16::MAX as u32 + 1);
1038 assert_eq!(inserted, 1);
1039
1040 assert_eq!(b.containers[0].len(), 1);
1041 assert_eq!(b.containers.len(), 1);
1042
1043 let removed = b.remove_range(u16::MAX as u32 + 1..=u16::MAX as u32 + 1);
1044 assert_eq!(removed, 1);
1045
1046 assert_eq!(b.containers.len(), 0);
1047 }
1048
1049 #[test]
1050 fn test_insert_remove_range_multi_container() {
1051 let mut bitmap = RoaringBitmap::new();
1052 assert_eq!(bitmap.insert_range(0..((1_u32 << 16) + 1)), (1_u64 << 16) + 1);
1053 assert_eq!(bitmap.containers.len(), 2);
1054 assert_eq!(bitmap.containers[0].key, 0);
1055 assert_eq!(bitmap.containers[1].key, 1);
1056 assert_eq!(bitmap.insert_range(0..((1_u32 << 16) + 1)), 0);
1057
1058 assert!(bitmap.insert((1_u32 << 16) * 4));
1059 assert_eq!(bitmap.containers.len(), 3);
1060 assert_eq!(bitmap.containers[2].key, 4);
1061
1062 assert_eq!(bitmap.remove_range(((1_u32 << 16) * 3)..=((1_u32 << 16) * 4)), 1);
1063 assert_eq!(bitmap.containers.len(), 2);
1064 }
1065
1066 #[test]
1067 fn insert_range_single() {
1068 let mut bitmap = RoaringBitmap::new();
1069 assert_eq!(bitmap.insert_range((1_u32 << 16)..(2_u32 << 16)), 1_u64 << 16);
1070 assert_eq!(bitmap.containers.len(), 1);
1071 assert_eq!(bitmap.containers[0].key, 1);
1072 }
1073
1074 #[test]
1075 fn remove_smallest_for_vec() {
1076 let mut bitmap = RoaringBitmap::from_iter([1, 2, 3, 7, 9, 11]);
1077 bitmap.remove_smallest(3);
1078 assert_eq!(bitmap.len(), 3);
1079 assert_eq!(bitmap, RoaringBitmap::from_iter([7, 9, 11]));
1080
1081 bitmap = RoaringBitmap::from_iter([1, 2, 5, 7, 9, 11]);
1082 bitmap.remove_smallest(3);
1083 assert_eq!(bitmap.len(), 3);
1084 assert_eq!(bitmap, RoaringBitmap::from_iter([7, 9, 11]));
1085
1086 bitmap = RoaringBitmap::from_iter([1, 3]);
1087 bitmap.remove_smallest(2);
1088 assert_eq!(bitmap.len(), 0);
1089
1090 bitmap = RoaringBitmap::from_iter([1, 2, 3, 7, 9, 11]);
1091 bitmap.remove_smallest(0);
1092 assert_eq!(bitmap.len(), 6);
1093 assert_eq!(bitmap, RoaringBitmap::from_iter([1, 2, 3, 7, 9, 11]));
1094
1095 bitmap = RoaringBitmap::new();
1096 bitmap.insert_range(0..(1_u32 << 16) + 5);
1097 bitmap.remove_smallest(65537);
1098 assert_eq!(bitmap.len(), 4);
1099 assert_eq!(bitmap, RoaringBitmap::from_iter([65537, 65538, 65539, 65540]));
1100
1101 bitmap = RoaringBitmap::from_iter([1, 2, 5, 7, 9, 11]);
1102 bitmap.remove_smallest(7);
1103 assert_eq!(bitmap, RoaringBitmap::default());
1104 }
1105
1106 #[test]
1107 fn remove_smallest_for_bit() {
1108 let mut bitmap = RoaringBitmap::new();
1109 bitmap.insert_range(0..4098);
1110 bitmap.remove_smallest(4095);
1111 assert_eq!(bitmap.len(), 3);
1112 assert_eq!(bitmap, RoaringBitmap::from_iter([4095, 4096, 4097]));
1114
1115 bitmap = RoaringBitmap::new();
1116 bitmap.insert_range(0..6000);
1117 bitmap.remove_smallest(999);
1118 assert_eq!(bitmap.len(), 5001);
1119
1120 bitmap = RoaringBitmap::new();
1121 bitmap.insert_range(0..8000);
1122 bitmap.remove_smallest(10);
1123 assert_eq!(bitmap.len(), 7990);
1124
1125 bitmap = RoaringBitmap::new();
1126 bitmap.insert_range(0..200000);
1127 bitmap.remove_smallest(2000);
1128 assert_eq!(bitmap.len(), 198000);
1129 assert_eq!(bitmap, RoaringBitmap::from_iter(2000..200000));
1130
1131 bitmap = RoaringBitmap::new();
1132 bitmap.insert_range(0..2);
1133 bitmap.insert_range(4..7);
1134 bitmap.insert_range(1000..6000);
1135 bitmap.remove_smallest(30);
1136 assert_eq!(bitmap.len(), 4975);
1137
1138 bitmap = RoaringBitmap::new();
1139 bitmap.insert_range(0..65535);
1140 bitmap.remove_smallest(0);
1141 assert_eq!(bitmap.len(), 65535);
1142 }
1143
1144 #[test]
1145 fn remove_biggest_for_bit() {
1146 let mut bitmap = RoaringBitmap::new();
1147 bitmap.insert_range(0..5000);
1148 bitmap.remove_biggest(1000);
1149 assert_eq!(bitmap.len(), 4000);
1150
1151 bitmap = RoaringBitmap::new();
1152 bitmap.insert_range(0..6000);
1153 bitmap.remove_biggest(1000);
1154 assert_eq!(bitmap.len(), 5000);
1155
1156 bitmap = RoaringBitmap::new();
1157 bitmap.insert_range(0..200000);
1158 bitmap.remove_biggest(196000);
1159 assert_eq!(bitmap.len(), 4000);
1160
1161 bitmap = RoaringBitmap::new();
1162 bitmap.insert_range(0..200000);
1163 bitmap.remove_biggest(2000);
1164 assert_eq!(bitmap.len(), 198000);
1165 assert_eq!(bitmap, RoaringBitmap::from_iter(0..198000));
1166
1167 bitmap = RoaringBitmap::new();
1168 bitmap.insert_range(0..65535);
1169 bitmap.remove_biggest(0);
1170 assert_eq!(bitmap.len(), 65535);
1171 }
1172
1173 #[test]
1174 fn remove_biggest_for_vec() {
1175 let mut bitmap = RoaringBitmap::from_iter([1, 2, 3, 7, 9, 11]);
1176 bitmap.remove_biggest(2);
1177 assert_eq!(bitmap, RoaringBitmap::from_iter([1, 2, 3, 7]));
1178
1179 bitmap = RoaringBitmap::from_iter([1, 2, 3, 7, 9, 11]);
1180 bitmap.remove_biggest(6);
1181 assert_eq!(bitmap.len(), 0);
1182
1183 bitmap = RoaringBitmap::from_iter([1, 2, 3, 7, 9, 11]);
1184 bitmap.remove_biggest(0);
1185 assert_eq!(bitmap.len(), 6);
1186 assert_eq!(bitmap, RoaringBitmap::from_iter([1, 2, 3, 7, 9, 11]));
1187
1188 bitmap = RoaringBitmap::new();
1189 bitmap.insert_range(0..(1_u32 << 16) + 5);
1190 bitmap.remove_biggest(65537);
1191 assert_eq!(bitmap.len(), 4);
1192 assert_eq!(bitmap, RoaringBitmap::from_iter([0, 1, 2, 3]));
1193
1194 let mut bitmap = RoaringBitmap::from_iter([1, 2, 3]);
1195 bitmap.remove_biggest(4);
1196 assert_eq!(bitmap, RoaringBitmap::default());
1197 }
1198}