roaring/bitmap/
inherent.rs

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    /// Creates an empty `RoaringBitmap`.
16    ///
17    /// # Examples
18    ///
19    /// ```rust
20    /// use roaring::RoaringBitmap;
21    /// let rb = RoaringBitmap::new();
22    /// ```
23    pub fn new() -> RoaringBitmap {
24        RoaringBitmap { containers: Vec::new() }
25    }
26
27    /// Creates a full `RoaringBitmap`.
28    ///
29    /// # Examples
30    ///
31    /// ```rust
32    /// use roaring::RoaringBitmap;
33    /// let rb = RoaringBitmap::full();
34    /// ```
35    pub fn full() -> RoaringBitmap {
36        RoaringBitmap { containers: (0..=u16::MAX).map(Container::full).collect() }
37    }
38
39    /// Creates a `RoaringBitmap` from a byte slice, interpreting the bytes as a bitmap with a specified offset.
40    ///
41    /// # Arguments
42    ///
43    /// - `offset: u32` - The starting position in the bitmap where the byte slice will be applied, specified in bits.
44    ///                   This means that if `offset` is `n`, the first byte in the slice will correspond to the `n`th bit(0-indexed) in the bitmap.
45    /// - `bytes: &[u8]` - The byte slice containing the bitmap data. The bytes are interpreted in "Least-Significant-First" bit order.
46    ///
47    /// # Interpretation of `bytes`
48    ///
49    /// The `bytes` slice is interpreted in "Least-Significant-First" bit order. Each byte is read from least significant bit (LSB) to most significant bit (MSB).
50    /// For example, the byte `0b00000101` represents the bits `1, 0, 1, 0, 0, 0, 0, 0` in that order (see Examples section).
51    ///
52    ///
53    /// # Panics
54    ///
55    /// This function will panic if `bytes.len() + offset` is greater than 2^32.
56    ///
57    ///
58    /// # Examples
59    ///
60    /// ```rust
61    /// use roaring::RoaringBitmap;
62    ///
63    /// let bytes = [0b00000101, 0b00000010, 0b00000000, 0b10000000];
64    /// //             ^^^^^^^^    ^^^^^^^^    ^^^^^^^^    ^^^^^^^^
65    /// //             76543210          98
66    /// let rb = RoaringBitmap::from_lsb0_bytes(0, &bytes);
67    /// assert!(rb.contains(0));
68    /// assert!(!rb.contains(1));
69    /// assert!(rb.contains(2));
70    /// assert!(rb.contains(9));
71    /// assert!(rb.contains(31));
72    ///
73    /// let rb = RoaringBitmap::from_lsb0_bytes(8, &bytes);
74    /// assert!(rb.contains(8));
75    /// assert!(!rb.contains(9));
76    /// assert!(rb.contains(10));
77    /// assert!(rb.contains(17));
78    /// assert!(rb.contains(39));
79    ///
80    /// let rb = RoaringBitmap::from_lsb0_bytes(3, &bytes);
81    /// assert!(rb.contains(3));
82    /// assert!(!rb.contains(4));
83    /// assert!(rb.contains(5));
84    /// assert!(rb.contains(12));
85    /// assert!(rb.contains(34));
86    /// ```
87    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        // Using inclusive range avoids overflow: the max exclusive value is 2^32 (u32::MAX + 1).
115        let end_bit_inc = u32::try_from(bytes.len())
116            .ok()
117            .and_then(|len_bytes| len_bytes.checked_mul(8))
118            // `bytes` is non-empty, so len_bits is > 0
119            .and_then(|len_bits| offset.checked_add(len_bits - 1))
120            .expect("offset + bytes.len() must be <= 2^32");
121
122        // offsets are in bytes
123        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        // Handle a partial first container
132        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        // Handle all full containers
152        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        // Handle a last container
162        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    /// Adds a value to the set.
173    ///
174    /// Returns whether the value was absent from the set.
175    ///
176    /// # Examples
177    ///
178    /// ```rust
179    /// use roaring::RoaringBitmap;
180    ///
181    /// let mut rb = RoaringBitmap::new();
182    /// assert_eq!(rb.insert(3), true);
183    /// assert_eq!(rb.insert(3), false);
184    /// assert_eq!(rb.contains(3), true);
185    /// ```
186    #[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    /// Searches for the specific container by the given key.
200    /// Creates a new container if it doesn't exist.
201    ///
202    /// Return the index of the target container.
203    #[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    /// Searches and then modifies a specific container with `M` by the given key.
215    /// Creates a new container using `B` if it doesn't exist.
216    ///
217    /// Returns `R` based on `M` or `B`.
218    #[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    /// Inserts a range of values.
240    /// Returns the number of inserted values.
241    ///
242    /// # Examples
243    ///
244    /// ```rust
245    /// use roaring::RoaringBitmap;
246    ///
247    /// let mut rb = RoaringBitmap::new();
248    /// rb.insert_range(2..4);
249    /// assert!(rb.contains(2));
250    /// assert!(rb.contains(3));
251    /// assert!(!rb.contains(4));
252    /// ```
253    #[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 the end range value is in the same container, just call into
275        // the one container.
276        if start_container_key == end_container_key {
277            return modify_container_range(self, start_container_key, start_index..=end_index);
278        }
279
280        // For the first container, insert start_index..=u16::MAX, with
281        // subsequent containers inserting 0..MAX.
282        //
283        // The last container (end_container_key) is handled explicitly outside
284        // the loop.
285        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            // After the first container, always fill the containers.
292            low = 0;
293        }
294
295        // Handle the last container
296        inserted += modify_container_range(self, end_container_key, 0..=end_index);
297
298        inserted
299    }
300
301    /// Pushes `value` in the bitmap only if it is greater than the current maximum value.
302    ///
303    /// Returns whether the value was inserted.
304    ///
305    /// # Examples
306    ///
307    /// ```rust
308    /// use roaring::RoaringBitmap;
309    ///
310    /// let mut rb = RoaringBitmap::new();
311    /// assert!(rb.push(1));
312    /// assert!(rb.push(3));
313    /// assert_eq!(rb.push(3), false);
314    /// assert!(rb.push(5));
315    ///
316    /// assert_eq!(rb.iter().collect::<Vec<u32>>(), vec![1, 3, 5]);
317    /// ```
318    #[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    /// Pushes `value` in the bitmap only if it is greater than the current maximum value.
325    ///
326    /// Returns an error if the value is not greater than the current maximum value.
327    ///
328    /// # Examples
329    ///
330    /// ```rust
331    /// use roaring::{RoaringBitmap, IntegerTooSmall};
332    ///
333    /// let mut rb = RoaringBitmap::new();
334    /// assert!(rb.try_push(1).is_ok());
335    /// assert!(rb.try_push(3).is_ok());
336    /// assert_eq!(rb.try_push(3), Err(IntegerTooSmall));
337    /// assert!(rb.try_push(5).is_ok());
338    ///
339    /// assert_eq!(rb.iter().collect::<Vec<u32>>(), vec![1, 3, 5]);
340    /// ```
341    #[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    /// Pushes `value` at the end of the bitmap.
364    /// It is up to the caller to have validated index > self.max()
365    ///
366    /// # Panics
367    ///
368    /// If debug_assertions enabled and index is > self.max()
369    #[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    /// Removes a value from the set. Returns `true` if the value was present in the set.
387    ///
388    /// # Examples
389    ///
390    /// ```rust
391    /// use roaring::RoaringBitmap;
392    ///
393    /// let mut rb = RoaringBitmap::new();
394    /// rb.insert(3);
395    /// assert_eq!(rb.remove(3), true);
396    /// assert_eq!(rb.remove(3), false);
397    /// assert_eq!(rb.contains(3), false);
398    /// ```
399    #[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    /// Removes a range of values.
418    /// Returns the number of removed values.
419    ///
420    /// # Examples
421    ///
422    /// ```rust
423    /// use roaring::RoaringBitmap;
424    ///
425    /// let mut rb = RoaringBitmap::new();
426    /// rb.insert(2);
427    /// rb.insert(3);
428    /// assert_eq!(rb.remove_range(2..4), 2);
429    /// ```
430    #[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    /// Returns `true` if this set contains the specified integer.
462    ///
463    /// # Examples
464    ///
465    /// ```rust
466    /// use roaring::RoaringBitmap;
467    ///
468    /// let mut rb = RoaringBitmap::new();
469    /// rb.insert(1);
470    /// assert_eq!(rb.contains(0), false);
471    /// assert_eq!(rb.contains(1), true);
472    /// assert_eq!(rb.contains(100), false);
473    /// ```
474    #[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    /// Returns `true` if all values in the range are present in this set.
484    ///
485    /// # Examples
486    ///
487    /// ```
488    /// use roaring::RoaringBitmap;
489    ///
490    /// let mut rb = RoaringBitmap::new();
491    /// // An empty range is always contained
492    /// assert!(rb.contains_range(7..7));
493    ///
494    /// rb.insert_range(1..0xFFF);
495    /// assert!(rb.contains_range(1..0xFFF));
496    /// assert!(rb.contains_range(2..0xFFF));
497    /// // 0 is not contained
498    /// assert!(!rb.contains_range(0..2));
499    /// // 0xFFF is not contained
500    /// assert!(!rb.contains_range(1..=0xFFF));
501    /// ```
502    #[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            // Empty/Invalid ranges are always contained
510            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        // If this contains everything in the range, there should be a container for every item in the span
528        // and the container that many items away should be the high key
529        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    /// Returns the number of elements in this set which are in the passed range.
545    ///
546    /// # Examples
547    ///
548    /// ```
549    /// use roaring::RoaringBitmap;
550    ///
551    /// let mut rb = RoaringBitmap::new();
552    /// rb.insert_range(0x10000..0x40000);
553    /// rb.insert(0x50001);
554    /// rb.insert(0x50005);
555    /// rb.insert(u32::MAX);
556    ///
557    /// assert_eq!(rb.range_cardinality(0..0x10000), 0);
558    /// assert_eq!(rb.range_cardinality(0x10000..0x40000), 0x30000);
559    /// assert_eq!(rb.range_cardinality(0x50000..0x60000), 2);
560    /// assert_eq!(rb.range_cardinality(0x10000..0x10000), 0);
561    /// assert_eq!(rb.range_cardinality(0x50000..=u32::MAX), 3);
562    /// ```
563    #[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            // Empty/invalid ranges have 0 bits set in them
571            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    /// Clears all integers in this set.
611    ///
612    /// # Examples
613    ///
614    /// ```rust
615    /// use roaring::RoaringBitmap;
616    ///
617    /// let mut rb = RoaringBitmap::new();
618    /// rb.insert(1);
619    /// assert_eq!(rb.contains(1), true);
620    /// rb.clear();
621    /// assert_eq!(rb.contains(1), false);
622    /// ```
623    #[inline]
624    pub fn clear(&mut self) {
625        self.containers.clear();
626    }
627
628    /// Returns `true` if there are no integers in this set.
629    ///
630    /// # Examples
631    ///
632    /// ```rust
633    /// use roaring::RoaringBitmap;
634    ///
635    /// let mut rb = RoaringBitmap::new();
636    /// assert_eq!(rb.is_empty(), true);
637    ///
638    /// rb.insert(3);
639    /// assert_eq!(rb.is_empty(), false);
640    /// ```
641    #[inline]
642    pub fn is_empty(&self) -> bool {
643        self.containers.is_empty()
644    }
645
646    /// Returns `true` if there are every possible integers in this set.
647    ///
648    /// # Examples
649    ///
650    /// ```rust
651    /// use roaring::RoaringBitmap;
652    ///
653    /// let mut rb = RoaringBitmap::full();
654    /// assert!(!rb.is_empty());
655    /// assert!(rb.is_full());
656    /// ```
657    #[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    /// Returns the number of distinct integers added to the set.
664    ///
665    /// # Examples
666    ///
667    /// ```rust
668    /// use roaring::RoaringBitmap;
669    ///
670    /// let mut rb = RoaringBitmap::new();
671    /// assert_eq!(rb.len(), 0);
672    ///
673    /// rb.insert(3);
674    /// assert_eq!(rb.len(), 1);
675    ///
676    /// rb.insert(3);
677    /// rb.insert(4);
678    /// assert_eq!(rb.len(), 2);
679    /// ```
680    #[inline]
681    pub fn len(&self) -> u64 {
682        self.containers.iter().map(|container| container.len()).sum()
683    }
684
685    /// Returns the minimum value in the set (if the set is non-empty).
686    ///
687    /// # Examples
688    ///
689    /// ```rust
690    /// use roaring::RoaringBitmap;
691    ///
692    /// let mut rb = RoaringBitmap::new();
693    /// assert_eq!(rb.min(), None);
694    ///
695    /// rb.insert(3);
696    /// rb.insert(4);
697    /// assert_eq!(rb.min(), Some(3));
698    /// ```
699    #[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    /// Returns the maximum value in the set (if the set is non-empty).
705    ///
706    /// # Examples
707    ///
708    /// ```rust
709    /// use roaring::RoaringBitmap;
710    ///
711    /// let mut rb = RoaringBitmap::new();
712    /// assert_eq!(rb.max(), None);
713    ///
714    /// rb.insert(3);
715    /// rb.insert(4);
716    /// assert_eq!(rb.max(), Some(4));
717    /// ```
718    #[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    /// Returns the number of integers that are <= value. rank(u32::MAX) == len()
724    ///
725    /// # Examples
726    ///
727    /// ```rust
728    /// use roaring::RoaringBitmap;
729    ///
730    /// let mut rb = RoaringBitmap::new();
731    /// assert_eq!(rb.rank(0), 0);
732    ///
733    /// rb.insert(3);
734    /// rb.insert(4);
735    /// assert_eq!(rb.rank(3), 1);
736    /// assert_eq!(rb.rank(10), 2)
737    /// ```
738    #[inline]
739    pub fn rank(&self, value: u32) -> u64 {
740        // if len becomes cached for RoaringBitmap: return len if len > value
741
742        let (key, index) = util::split(value);
743
744        match self.containers.binary_search_by_key(&key, |c| c.key) {
745            Ok(i) => {
746                // For optimal locality of reference:
747                //  * container[i] should be a cache hit after binary search, rank it first
748                //  * sum in reverse to avoid cache misses near i
749                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    /// Returns the `n`th integer in the set or `None` if `n >= len()`
757    ///
758    /// # Examples
759    ///
760    /// ```rust
761    /// use roaring::RoaringBitmap;
762    ///
763    /// let mut rb = RoaringBitmap::new();
764    /// assert_eq!(rb.select(0), None);
765    ///
766    /// rb.append(vec![0, 10, 100]);
767    ///
768    /// assert_eq!(rb.select(0), Some(0));
769    /// assert_eq!(rb.select(1), Some(10));
770    /// assert_eq!(rb.select(2), Some(100));
771    /// assert_eq!(rb.select(3), None);
772    /// ```
773    #[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    /// Removes the `n` smallests values from this bitmap.
792    ///
793    /// # Examples
794    ///
795    /// ```rust
796    /// use roaring::RoaringBitmap;
797    ///
798    /// let mut rb = RoaringBitmap::from_iter([1, 5, 7, 9]);
799    /// rb.remove_smallest(2);
800    /// assert_eq!(rb, RoaringBitmap::from_iter([7, 9]));
801    ///
802    /// let mut rb = RoaringBitmap::from_iter([1, 3, 7, 9]);
803    /// rb.remove_smallest(2);
804    /// assert_eq!(rb, RoaringBitmap::from_iter([7, 9]));
805    #[inline]
806    pub fn remove_smallest(&mut self, mut n: u64) {
807        // remove containers up to the front of the target
808        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        // remove data in containers if there are still targets for deletion
822        if n > 0 && !self.containers.is_empty() {
823            // container immediately before should have been deleted, so the target is 0 index
824            self.containers[0].remove_smallest(n);
825        }
826    }
827
828    /// Removes the `n` biggests values from this bitmap.
829    ///
830    /// # Examples
831    ///
832    /// ```rust
833    /// use roaring::RoaringBitmap;
834    ///
835    /// let mut rb = RoaringBitmap::from_iter([1, 5, 7, 9]);
836    /// rb.remove_biggest(2);
837    /// assert_eq!(rb, RoaringBitmap::from_iter([1, 5]));
838    /// rb.remove_biggest(1);
839    /// assert_eq!(rb, RoaringBitmap::from_iter([1]));
840    #[inline]
841    pub fn remove_biggest(&mut self, mut n: u64) {
842        // remove containers up to the back of the target
843        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        // It is checked at the beginning of the function, so it is usually never an Err
853        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    /// Optimizes the container storage for this bitmap.
864    /// Returns true if the container storage was modified, false if not.
865    ///
866    /// # Examples
867    ///
868    /// ```
869    /// use roaring::RoaringBitmap;
870    ///
871    /// let mut rb = RoaringBitmap::from_iter(1000..100000);
872    /// rb.optimize();
873    /// ```
874    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    /// Removes run-length encoding even when it is more space efficient.
883    ///
884    /// Returns true if the container storage was modified, false if not.
885    ///
886    /// # Examples
887    ///
888    /// ```
889    /// use roaring::RoaringBitmap;
890    ///
891    /// let mut rb = RoaringBitmap::from_iter(0..=10000);
892    /// rb.optimize();
893    /// assert!(rb.remove_run_compression());
894    /// ```
895    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    /// Ensure the bitmap is internally valid
904    ///
905    /// This is useful for development, but is not needed for normal use:
906    /// bitmaps should _always_ be internally valid.
907    ///
908    /// # Errors
909    ///
910    /// Returns an error if the bitmap is not valid, with a description of the problem.
911    #[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            // Assert all values in the range are present
965            for i in r.clone() {
966                assert!(b.contains(i), "does not contain {i}");
967            }
968
969            // Run the check values looking for any false positives
970            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        // We are allowed to add u32::MAX
1017        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        // removed bit to vec
1113        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}