roaring/bitmap/
iter.rs

1use alloc::vec;
2use core::iter::FusedIterator;
3use core::ops::RangeBounds;
4use core::slice;
5
6use super::container::Container;
7use super::{container, util};
8use crate::{NonSortedIntegers, RoaringBitmap};
9
10#[cfg(not(feature = "std"))]
11use alloc::vec::Vec;
12
13/// An iterator for `RoaringBitmap`.
14#[derive(Clone)]
15pub struct Iter<'a> {
16    front: Option<container::Iter<'a>>,
17    containers: slice::Iter<'a, Container>,
18    back: Option<container::Iter<'a>>,
19}
20
21/// An iterator for `RoaringBitmap`.
22#[derive(Clone)]
23pub struct IntoIter {
24    front: Option<container::Iter<'static>>,
25    containers: vec::IntoIter<Container>,
26    back: Option<container::Iter<'static>>,
27}
28
29#[inline]
30fn and_then_or_clear<T, U>(opt: &mut Option<T>, f: impl FnOnce(&mut T) -> Option<U>) -> Option<U> {
31    let x = f(opt.as_mut()?);
32    if x.is_none() {
33        *opt = None;
34    }
35    x
36}
37
38fn advance_to_impl<'a, It>(
39    n: u32,
40    front_iter: &mut Option<container::Iter<'a>>,
41    containers: &mut It,
42    back_iter: &mut Option<container::Iter<'a>>,
43) where
44    It: Iterator,
45    It: AsRef<[Container]>,
46    It::Item: IntoIterator<IntoIter = container::Iter<'a>>,
47{
48    let (key, index) = util::split(n);
49    if let Some(iter) = front_iter {
50        match key.cmp(&iter.key) {
51            core::cmp::Ordering::Less => return,
52            core::cmp::Ordering::Equal => {
53                iter.advance_to(index);
54                return;
55            }
56            core::cmp::Ordering::Greater => {
57                *front_iter = None;
58            }
59        }
60    }
61    let containers_slice = containers.as_ref();
62    let containers_len = containers_slice.len();
63    let to_skip = match containers_slice.binary_search_by_key(&key, |c| c.key) {
64        Ok(n) => {
65            let container = containers.nth(n).expect("binary search returned a valid index");
66            let mut container_iter = container.into_iter();
67            container_iter.advance_to(index);
68            *front_iter = Some(container_iter);
69            return;
70        }
71        Err(n) => n,
72    };
73
74    if let Some(n) = to_skip.checked_sub(1) {
75        containers.nth(n);
76    }
77    if to_skip != containers_len {
78        // There are still containers with keys greater than the key we are looking for,
79        // the key we're looking _can't_ be in the back iterator.
80        return;
81    }
82    if let Some(iter) = back_iter {
83        match key.cmp(&iter.key) {
84            core::cmp::Ordering::Less => {}
85            core::cmp::Ordering::Equal => {
86                iter.advance_to(index);
87            }
88            core::cmp::Ordering::Greater => {
89                *back_iter = None;
90            }
91        }
92    }
93}
94
95fn advance_back_to_impl<'a, It>(
96    n: u32,
97    front_iter: &mut Option<container::Iter<'a>>,
98    containers: &mut It,
99    back_iter: &mut Option<container::Iter<'a>>,
100) where
101    It: DoubleEndedIterator,
102    It: AsRef<[Container]>,
103    It::Item: IntoIterator<IntoIter = container::Iter<'a>>,
104{
105    let (key, index) = util::split(n);
106    if let Some(iter) = back_iter {
107        match key.cmp(&iter.key) {
108            core::cmp::Ordering::Greater => return,
109            core::cmp::Ordering::Equal => {
110                iter.advance_back_to(index);
111                return;
112            }
113            core::cmp::Ordering::Less => {
114                *back_iter = None;
115            }
116        }
117    }
118    let containers_slice = containers.as_ref();
119    let containers_len = containers_slice.len();
120    let to_skip = match containers_slice.binary_search_by_key(&key, |c| c.key) {
121        Ok(n) => {
122            // n must be less than containers_len, so this can never underflow
123            let n = containers_len - n - 1;
124            let container = containers.nth_back(n).expect("binary search returned a valid index");
125            let mut container_iter = container.into_iter();
126            container_iter.advance_back_to(index);
127            *back_iter = Some(container_iter);
128            return;
129        }
130        Err(n) => containers_len - n,
131    };
132
133    if let Some(n) = to_skip.checked_sub(1) {
134        containers.nth_back(n);
135    }
136    if to_skip != containers_len {
137        // There are still containers with keys less than the key we are looking for,
138        // the key we're looking _can't_ be in the front iterator.
139        return;
140    }
141    if let Some(iter) = front_iter {
142        match key.cmp(&iter.key) {
143            core::cmp::Ordering::Greater => {}
144            core::cmp::Ordering::Equal => {
145                iter.advance_back_to(index);
146            }
147            core::cmp::Ordering::Less => {
148                *front_iter = None;
149            }
150        }
151    }
152}
153
154impl Iter<'_> {
155    fn new(containers: &'_ [Container]) -> Iter<'_> {
156        Iter { front: None, containers: containers.iter(), back: None }
157    }
158
159    fn empty() -> Self {
160        Self::new(&[])
161    }
162
163    /// Advance the iterator to the first position where the item has a value >= `n`
164    ///
165    /// # Examples
166    ///
167    /// ```rust
168    /// use roaring::RoaringBitmap;
169    /// use core::iter::FromIterator;
170    ///
171    /// let bitmap = (1..3).collect::<RoaringBitmap>();
172    /// let mut iter = bitmap.iter();
173    /// iter.advance_to(2);
174    ///
175    /// assert_eq!(iter.next(), Some(2));
176    /// assert_eq!(iter.next(), None);
177    /// ```
178    pub fn advance_to(&mut self, n: u32) {
179        advance_to_impl(n, &mut self.front, &mut self.containers, &mut self.back);
180    }
181
182    /// Advance the back of the iterator to the first position where the item has a value <= `n`
183    ///
184    /// # Examples
185    ///
186    /// ```rust
187    /// use roaring::RoaringBitmap;
188    /// use core::iter::FromIterator;
189    ///
190    /// let bitmap = (1..3).collect::<RoaringBitmap>();
191    /// let mut iter = bitmap.iter();
192    /// iter.advance_back_to(1);
193    ///
194    /// assert_eq!(iter.next_back(), Some(1));
195    /// assert_eq!(iter.next_back(), None);
196    /// ```
197    pub fn advance_back_to(&mut self, n: u32) {
198        advance_back_to_impl(n, &mut self.front, &mut self.containers, &mut self.back);
199    }
200}
201
202impl IntoIter {
203    fn new(containers: Vec<Container>) -> IntoIter {
204        IntoIter { front: None, containers: containers.into_iter(), back: None }
205    }
206
207    fn empty() -> Self {
208        Self::new(Vec::new())
209    }
210
211    /// Advance the iterator to the first position where the item has a value >= `n`
212    ///
213    /// # Examples
214    ///
215    /// ```rust
216    /// use roaring::RoaringBitmap;
217    /// use core::iter::FromIterator;
218    ///
219    /// let bitmap = (1..3).collect::<RoaringBitmap>();
220    /// let mut iter = bitmap.iter();
221    /// iter.advance_to(2);
222    ///
223    /// assert_eq!(iter.next(), Some(2));
224    /// assert_eq!(iter.next(), None);
225    /// ```
226    pub fn advance_to(&mut self, n: u32) {
227        advance_to_impl(n, &mut self.front, &mut self.containers, &mut self.back);
228    }
229
230    /// Advance the back of the iterator to the first position where the item has a value <= `n`
231    ///
232    /// # Examples
233    ///
234    /// ```rust
235    /// use roaring::RoaringBitmap;
236    /// use core::iter::FromIterator;
237    ///
238    /// let bitmap = (1..3).collect::<RoaringBitmap>();
239    /// let mut iter = bitmap.into_iter();
240    /// iter.advance_back_to(1);
241    ///
242    /// assert_eq!(iter.next_back(), Some(1));
243    /// assert_eq!(iter.next_back(), None);
244    /// ```
245    pub fn advance_back_to(&mut self, n: u32) {
246        advance_back_to_impl(n, &mut self.front, &mut self.containers, &mut self.back);
247    }
248}
249
250fn size_hint_impl(
251    front: &Option<container::Iter<'_>>,
252    containers: &impl AsRef<[Container]>,
253    back: &Option<container::Iter<'_>>,
254) -> (usize, Option<usize>) {
255    let first_size = front.as_ref().map_or(0, |it| it.len());
256    let last_size = back.as_ref().map_or(0, |it| it.len());
257    let mut size = first_size + last_size;
258    for container in containers.as_ref() {
259        match size.checked_add(container.len() as usize) {
260            Some(new_size) => size = new_size,
261            None => return (usize::MAX, None),
262        }
263    }
264    (size, Some(size))
265}
266
267impl Iterator for Iter<'_> {
268    type Item = u32;
269
270    fn next(&mut self) -> Option<u32> {
271        loop {
272            if let Some(x) = and_then_or_clear(&mut self.front, Iterator::next) {
273                return Some(x);
274            }
275            self.front = match self.containers.next() {
276                Some(inner) => Some(inner.into_iter()),
277                None => return and_then_or_clear(&mut self.back, Iterator::next),
278            }
279        }
280    }
281
282    fn size_hint(&self) -> (usize, Option<usize>) {
283        size_hint_impl(&self.front, &self.containers, &self.back)
284    }
285
286    #[inline]
287    fn fold<B, F>(mut self, mut init: B, mut f: F) -> B
288    where
289        Self: Sized,
290        F: FnMut(B, Self::Item) -> B,
291    {
292        if let Some(iter) = &mut self.front {
293            init = iter.fold(init, &mut f);
294        }
295        init = self.containers.fold(init, |acc, container| {
296            let iter = <&Container>::into_iter(container);
297            iter.fold(acc, &mut f)
298        });
299        if let Some(iter) = &mut self.back {
300            init = iter.fold(init, &mut f);
301        };
302        init
303    }
304
305    fn count(self) -> usize
306    where
307        Self: Sized,
308    {
309        let mut count = self.front.map_or(0, Iterator::count);
310        count += self.containers.map(|container| container.len() as usize).sum::<usize>();
311        count += self.back.map_or(0, Iterator::count);
312        count
313    }
314
315    fn nth(&mut self, n: usize) -> Option<Self::Item> {
316        let mut n = n;
317        let nth_advance = |it: &mut container::Iter| {
318            let len = it.len();
319            if n < len {
320                it.nth(n)
321            } else {
322                n -= len;
323                None
324            }
325        };
326        if let Some(x) = and_then_or_clear(&mut self.front, nth_advance) {
327            return Some(x);
328        }
329        for container in self.containers.by_ref() {
330            let len = container.len() as usize;
331            if n < len {
332                let mut front_iter = container.into_iter();
333                let result = front_iter.nth(n);
334                self.front = Some(front_iter);
335                return result;
336            }
337            n -= len;
338        }
339        and_then_or_clear(&mut self.back, |it| it.nth(n))
340    }
341}
342
343impl DoubleEndedIterator for Iter<'_> {
344    fn next_back(&mut self) -> Option<Self::Item> {
345        loop {
346            if let Some(x) = and_then_or_clear(&mut self.back, DoubleEndedIterator::next_back) {
347                return Some(x);
348            }
349            self.back = match self.containers.next_back() {
350                Some(inner) => Some(inner.into_iter()),
351                None => return and_then_or_clear(&mut self.front, DoubleEndedIterator::next_back),
352            }
353        }
354    }
355
356    #[inline]
357    fn rfold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
358    where
359        Fold: FnMut(Acc, Self::Item) -> Acc,
360    {
361        if let Some(iter) = &mut self.back {
362            init = iter.rfold(init, &mut fold);
363        }
364        init = self.containers.rfold(init, |acc, container| {
365            let iter = container.into_iter();
366            iter.rfold(acc, &mut fold)
367        });
368        if let Some(iter) = &mut self.front {
369            init = iter.rfold(init, &mut fold);
370        };
371        init
372    }
373
374    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
375        let mut n = n;
376        let nth_advance = |it: &mut container::Iter| {
377            let len = it.len();
378            if n < len {
379                it.nth_back(n)
380            } else {
381                n -= len;
382                None
383            }
384        };
385        if let Some(x) = and_then_or_clear(&mut self.back, nth_advance) {
386            return Some(x);
387        }
388        for container in self.containers.by_ref().rev() {
389            let len = container.len() as usize;
390            if n < len {
391                let mut front_iter = container.into_iter();
392                let result = front_iter.nth_back(n);
393                self.back = Some(front_iter);
394                return result;
395            }
396            n -= len;
397        }
398        and_then_or_clear(&mut self.front, |it| it.nth_back(n))
399    }
400}
401
402#[cfg(target_pointer_width = "64")]
403impl ExactSizeIterator for Iter<'_> {}
404impl FusedIterator for Iter<'_> {}
405
406impl Iterator for IntoIter {
407    type Item = u32;
408
409    fn next(&mut self) -> Option<u32> {
410        loop {
411            if let Some(x) = and_then_or_clear(&mut self.front, Iterator::next) {
412                return Some(x);
413            }
414            match self.containers.next() {
415                Some(inner) => self.front = Some(inner.into_iter()),
416                None => return and_then_or_clear(&mut self.back, Iterator::next),
417            }
418        }
419    }
420
421    fn size_hint(&self) -> (usize, Option<usize>) {
422        size_hint_impl(&self.front, &self.containers, &self.back)
423    }
424
425    #[inline]
426    fn fold<B, F>(mut self, mut init: B, mut f: F) -> B
427    where
428        Self: Sized,
429        F: FnMut(B, Self::Item) -> B,
430    {
431        if let Some(iter) = &mut self.front {
432            init = iter.fold(init, &mut f);
433        }
434        init = self.containers.fold(init, |acc, container| {
435            let iter = <Container>::into_iter(container);
436            iter.fold(acc, &mut f)
437        });
438        if let Some(iter) = &mut self.back {
439            init = iter.fold(init, &mut f);
440        };
441        init
442    }
443
444    fn count(self) -> usize
445    where
446        Self: Sized,
447    {
448        let mut count = self.front.map_or(0, Iterator::count);
449        count += self.containers.map(|container| container.len() as usize).sum::<usize>();
450        count += self.back.map_or(0, Iterator::count);
451        count
452    }
453
454    fn nth(&mut self, n: usize) -> Option<Self::Item> {
455        let mut n = n;
456        let nth_advance = |it: &mut container::Iter| {
457            let len = it.len();
458            if n < len {
459                it.nth(n)
460            } else {
461                n -= len;
462                None
463            }
464        };
465        if let Some(x) = and_then_or_clear(&mut self.front, nth_advance) {
466            return Some(x);
467        }
468        for container in self.containers.by_ref() {
469            let len = container.len() as usize;
470            if n < len {
471                let mut front_iter = container.into_iter();
472                let result = front_iter.nth(n);
473                self.front = Some(front_iter);
474                return result;
475            }
476            n -= len;
477        }
478        and_then_or_clear(&mut self.back, |it| it.nth(n))
479    }
480}
481
482impl DoubleEndedIterator for IntoIter {
483    fn next_back(&mut self) -> Option<Self::Item> {
484        loop {
485            if let Some(x) = and_then_or_clear(&mut self.back, DoubleEndedIterator::next_back) {
486                return Some(x);
487            }
488            match self.containers.next_back() {
489                Some(inner) => self.back = Some(inner.into_iter()),
490                None => return and_then_or_clear(&mut self.front, DoubleEndedIterator::next_back),
491            }
492        }
493    }
494
495    #[inline]
496    fn rfold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
497    where
498        Fold: FnMut(Acc, Self::Item) -> Acc,
499    {
500        if let Some(iter) = &mut self.back {
501            init = iter.rfold(init, &mut fold);
502        }
503        init = self.containers.rfold(init, |acc, container| {
504            let iter = container.into_iter();
505            iter.rfold(acc, &mut fold)
506        });
507        if let Some(iter) = &mut self.front {
508            init = iter.rfold(init, &mut fold);
509        };
510        init
511    }
512
513    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
514        let mut n = n;
515        let nth_advance = |it: &mut container::Iter| {
516            let len = it.len();
517            if n < len {
518                it.nth_back(n)
519            } else {
520                n -= len;
521                None
522            }
523        };
524        if let Some(x) = and_then_or_clear(&mut self.back, nth_advance) {
525            return Some(x);
526        }
527        for container in self.containers.by_ref().rev() {
528            let len = container.len() as usize;
529            if n < len {
530                let mut front_iter = container.into_iter();
531                let result = front_iter.nth_back(n);
532                self.back = Some(front_iter);
533                return result;
534            }
535            n -= len;
536        }
537        and_then_or_clear(&mut self.front, |it| it.nth_back(n))
538    }
539}
540
541#[cfg(target_pointer_width = "64")]
542impl ExactSizeIterator for IntoIter {}
543impl FusedIterator for IntoIter {}
544
545impl RoaringBitmap {
546    /// Iterator over each value stored in the RoaringBitmap, guarantees values are ordered by value.
547    ///
548    /// # Examples
549    ///
550    /// ```rust
551    /// use roaring::RoaringBitmap;
552    /// use core::iter::FromIterator;
553    ///
554    /// let bitmap = (1..3).collect::<RoaringBitmap>();
555    /// let mut iter = bitmap.iter();
556    ///
557    /// assert_eq!(iter.next(), Some(1));
558    /// assert_eq!(iter.next(), Some(2));
559    /// assert_eq!(iter.next(), None);
560    /// ```
561    pub fn iter(&'_ self) -> Iter<'_> {
562        Iter::new(&self.containers)
563    }
564
565    /// Iterator over values within a range stored in the RoaringBitmap.
566    ///
567    /// # Examples
568    ///
569    /// ```rust
570    /// use core::ops::Bound;
571    /// use roaring::RoaringBitmap;
572    ///
573    /// let bitmap = RoaringBitmap::from([0, 1, 2, 3, 4, 5, 10, 11, 12, 20, 21, u32::MAX]);
574    /// let mut iter = bitmap.range(10..20);
575    ///
576    /// assert_eq!(iter.next(), Some(10));
577    /// assert_eq!(iter.next(), Some(11));
578    /// assert_eq!(iter.next(), Some(12));
579    /// assert_eq!(iter.next(), None);
580    ///
581    /// let mut iter = bitmap.range(100..);
582    /// assert_eq!(iter.next(), Some(u32::MAX));
583    /// assert_eq!(iter.next(), None);
584    ///
585    /// let mut iter = bitmap.range((Bound::Excluded(0), Bound::Included(10)));
586    /// assert_eq!(iter.next(), Some(1));
587    /// assert_eq!(iter.next(), Some(2));
588    /// assert_eq!(iter.next(), Some(3));
589    /// assert_eq!(iter.next(), Some(4));
590    /// assert_eq!(iter.next(), Some(5));
591    /// assert_eq!(iter.next(), Some(10));
592    /// assert_eq!(iter.next(), None);
593    /// ```
594    pub fn range<R>(&self, range: R) -> Iter<'_>
595    where
596        R: RangeBounds<u32>,
597    {
598        let range = match util::convert_range_to_inclusive(range) {
599            Ok(range) => range,
600            Err(util::ConvertRangeError::Empty) => return Iter::empty(),
601            Err(util::ConvertRangeError::StartGreaterThanEnd) => {
602                panic!("range start is greater than range end")
603            }
604            Err(util::ConvertRangeError::StartAndEndEqualExcluded) => {
605                panic!("range start and end are equal and excluded")
606            }
607        };
608        let (start, end) = (*range.start(), *range.end());
609        let mut iter = self.iter();
610        if start != 0 {
611            iter.advance_to(start);
612        }
613        if end != u32::MAX {
614            iter.advance_back_to(end);
615        }
616        iter
617    }
618
619    /// Iterator over values within a range stored in the RoaringBitmap.
620    ///
621    /// # Examples
622    ///
623    /// ```rust
624    /// use core::ops::Bound;
625    /// use roaring::RoaringBitmap;
626    ///
627    /// fn bitmap() -> RoaringBitmap {
628    ///     RoaringBitmap::from([0, 1, 2, 3, 4, 5, 10, 11, 12, 20, 21, u32::MAX])
629    /// }
630    ///
631    /// let mut iter = bitmap().into_range(10..20);
632    ///
633    /// assert_eq!(iter.next(), Some(10));
634    /// assert_eq!(iter.next(), Some(11));
635    /// assert_eq!(iter.next(), Some(12));
636    /// assert_eq!(iter.next(), None);
637    ///
638    /// let mut iter = bitmap().into_range(100..);
639    /// assert_eq!(iter.next(), Some(u32::MAX));
640    /// assert_eq!(iter.next(), None);
641    ///
642    /// let mut iter = bitmap().into_range((Bound::Excluded(0), Bound::Included(10)));
643    /// assert_eq!(iter.next(), Some(1));
644    /// assert_eq!(iter.next(), Some(2));
645    /// assert_eq!(iter.next(), Some(3));
646    /// assert_eq!(iter.next(), Some(4));
647    /// assert_eq!(iter.next(), Some(5));
648    /// assert_eq!(iter.next(), Some(10));
649    /// assert_eq!(iter.next(), None);
650    /// ```
651    pub fn into_range<R>(self, range: R) -> IntoIter
652    where
653        R: RangeBounds<u32>,
654    {
655        let range = match util::convert_range_to_inclusive(range) {
656            Ok(range) => range,
657            Err(util::ConvertRangeError::Empty) => return IntoIter::empty(),
658            Err(util::ConvertRangeError::StartGreaterThanEnd) => {
659                panic!("range start is greater than range end")
660            }
661            Err(util::ConvertRangeError::StartAndEndEqualExcluded) => {
662                panic!("range start and end are equal and excluded")
663            }
664        };
665        let (start, end) = (*range.start(), *range.end());
666        let mut iter = self.into_iter();
667        if start != 0 {
668            iter.advance_to(start);
669        }
670        if end != u32::MAX {
671            iter.advance_back_to(end);
672        }
673        iter
674    }
675}
676
677impl<'a> IntoIterator for &'a RoaringBitmap {
678    type Item = u32;
679    type IntoIter = Iter<'a>;
680
681    fn into_iter(self) -> Iter<'a> {
682        self.iter()
683    }
684}
685
686impl IntoIterator for RoaringBitmap {
687    type Item = u32;
688    type IntoIter = IntoIter;
689
690    fn into_iter(self) -> IntoIter {
691        IntoIter::new(self.containers)
692    }
693}
694
695impl<const N: usize> From<[u32; N]> for RoaringBitmap {
696    fn from(arr: [u32; N]) -> Self {
697        RoaringBitmap::from_iter(arr)
698    }
699}
700
701impl FromIterator<u32> for RoaringBitmap {
702    fn from_iter<I: IntoIterator<Item = u32>>(iterator: I) -> RoaringBitmap {
703        let mut rb = RoaringBitmap::new();
704        rb.extend(iterator);
705        rb
706    }
707}
708
709impl<'a> FromIterator<&'a u32> for RoaringBitmap {
710    fn from_iter<I: IntoIterator<Item = &'a u32>>(iterator: I) -> RoaringBitmap {
711        let mut rb = RoaringBitmap::new();
712        rb.extend(iterator);
713        rb
714    }
715}
716
717impl Extend<u32> for RoaringBitmap {
718    /// Inserts multiple values and returns the count of new additions.
719    /// This is expected to be faster than calling [`RoaringBitmap::insert`] on each value.
720    ///
721    /// The provided integers values don't have to be in sorted order, but it may be preferable
722    /// to sort them from a performance point of view.
723    ///
724    /// # Examples
725    ///
726    /// ```rust
727    /// use roaring::RoaringBitmap;
728    ///
729    /// let mut rb = RoaringBitmap::new();
730    /// rb.extend([1, 2, 3, 4, 1500, 1508, 1507, 1509]);
731    /// assert!(rb.contains(2));
732    /// assert!(rb.contains(1508));
733    /// assert!(!rb.contains(5));
734    /// ```
735    #[inline]
736    fn extend<I: IntoIterator<Item = u32>>(&mut self, values: I) {
737        let mut values = values.into_iter();
738        let value = match values.next() {
739            Some(value) => value,
740            None => return,
741        };
742
743        let (mut currenthb, lowbit) = util::split(value);
744        let mut current_container_index = self.find_container_by_key(currenthb);
745        let mut current_cont = &mut self.containers[current_container_index];
746        current_cont.insert(lowbit);
747
748        for val in values {
749            let (newhb, lowbit) = util::split(val);
750            if currenthb == newhb {
751                // easy case, this could be quite frequent
752                current_cont.insert(lowbit);
753            } else {
754                currenthb = newhb;
755                current_container_index = self.find_container_by_key(currenthb);
756                current_cont = &mut self.containers[current_container_index];
757                current_cont.insert(lowbit);
758            }
759        }
760    }
761}
762
763impl<'a> Extend<&'a u32> for RoaringBitmap {
764    /// Inserts multiple values and returns the count of new additions.
765    /// This is expected to be faster than calling [`RoaringBitmap::insert`] on each value.
766    ///
767    /// The provided integers values don't have to be in sorted order, but it may be preferable
768    /// to sort them from a performance point of view.
769    ///
770    /// # Examples
771    ///
772    /// ```rust
773    /// use roaring::RoaringBitmap;
774    ///
775    /// let mut rb = RoaringBitmap::new();
776    /// rb.extend([1, 2, 3, 4, 1500, 1508, 1507, 1509]);
777    /// assert!(rb.contains(2));
778    /// assert!(rb.contains(1508));
779    /// assert!(!rb.contains(5));
780    /// ```
781    #[inline]
782    fn extend<I: IntoIterator<Item = &'a u32>>(&mut self, values: I) {
783        self.extend(values.into_iter().copied());
784    }
785}
786
787impl RoaringBitmap {
788    /// Create the set from a sorted iterator. Values must be sorted and deduplicated.
789    ///
790    /// The values of the iterator must be ordered and strictly greater than the greatest value
791    /// in the set. If a value in the iterator doesn't satisfy this requirement, it is not added
792    /// and the append operation is stopped.
793    ///
794    /// Returns `Ok` with the requested `RoaringBitmap`, `Err` with the number of elements
795    /// that were correctly appended before failure.
796    ///
797    /// # Example: Create a set from an ordered list of integers.
798    ///
799    /// ```rust
800    /// use roaring::RoaringBitmap;
801    ///
802    /// let mut rb = RoaringBitmap::from_sorted_iter(0..10).unwrap();
803    ///
804    /// assert!(rb.iter().eq(0..10));
805    /// ```
806    ///
807    /// # Example: Try to create a set from a non-ordered list of integers.
808    ///
809    /// ```rust
810    /// use roaring::RoaringBitmap;
811    ///
812    /// let integers = 0..10u32;
813    /// let error = RoaringBitmap::from_sorted_iter(integers.rev()).unwrap_err();
814    ///
815    /// assert_eq!(error.valid_until(), 1);
816    /// ```
817    pub fn from_sorted_iter<I: IntoIterator<Item = u32>>(
818        iterator: I,
819    ) -> Result<RoaringBitmap, NonSortedIntegers> {
820        let mut rb = RoaringBitmap::new();
821        rb.append(iterator).map(|_| rb)
822    }
823
824    /// Extend the set with a sorted iterator.
825    ///
826    /// The values of the iterator must be ordered and strictly greater than the greatest value
827    /// in the set. If a value in the iterator doesn't satisfy this requirement, it is not added
828    /// and the append operation is stopped.
829    ///
830    /// Returns `Ok` with the number of elements appended to the set, `Err` with
831    /// the number of elements we effectively appended before an error occurred.
832    ///
833    /// # Examples
834    ///
835    /// ```rust
836    /// use roaring::RoaringBitmap;
837    ///
838    /// let mut rb = RoaringBitmap::new();
839    /// assert_eq!(rb.append(0..10), Ok(10));
840    ///
841    /// assert!(rb.iter().eq(0..10));
842    /// ```
843    pub fn append<I: IntoIterator<Item = u32>>(
844        &mut self,
845        iterator: I,
846    ) -> Result<u64, NonSortedIntegers> {
847        // Name shadowed to prevent accidentally referencing the param
848        let mut iterator = iterator.into_iter();
849
850        let mut prev = match (iterator.next(), self.max()) {
851            (None, _) => return Ok(0),
852            (Some(first), Some(max)) if first <= max => {
853                return Err(NonSortedIntegers { valid_until: 0 })
854            }
855            (Some(first), _) => first,
856        };
857
858        // It is now guaranteed that so long as the values of the iterator are
859        // monotonically increasing they must also be the greatest in the set.
860
861        self.push_unchecked(prev);
862
863        let mut count = 1;
864
865        for value in iterator {
866            if value <= prev {
867                return Err(NonSortedIntegers { valid_until: count });
868            } else {
869                self.push_unchecked(value);
870                prev = value;
871                count += 1;
872            }
873        }
874
875        Ok(count)
876    }
877}
roaring/bitmap/iter.rs

roaring/bitmap/
iter.rs
