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 next_range_impl<'a, It>(
96    front_iter: &mut Option<container::Iter<'a>>,
97    containers: &mut It,
98    back_iter: &mut Option<container::Iter<'a>>,
99) -> Option<core::ops::RangeInclusive<u32>>
100where
101    It: Iterator + Clone,
102    It: AsRef<[Container]>,
103    It::Item: IntoIterator<IntoIter = container::Iter<'a>>,
104{
105    let range = loop {
106        if let Some(r) = and_then_or_clear(front_iter, container::Iter::next_range) {
107            break r;
108        }
109        *front_iter = match containers.next() {
110            Some(inner) => Some(inner.into_iter()),
111            None => return and_then_or_clear(back_iter, container::Iter::next_range),
112        }
113    };
114    let (range_start, mut range_end) = (*range.start(), *range.end());
115    while range_end & 0xFFFF == 0xFFFF {
116        let Some(after_end) = range_end.checked_add(1) else {
117            return Some(range_start..=range_end);
118        };
119        let (next_key, _) = util::split(after_end);
120
121        if containers.as_ref().first().is_some_and(|c| c.key == next_key && c.contains(0)) {
122            let mut iter = containers.next().unwrap().into_iter();
123            let next_range = iter.next_range().unwrap();
124            *front_iter = Some(iter);
125            debug_assert_eq!(*next_range.start(), after_end);
126            range_end = *next_range.end();
127        } else {
128            if let Some(iter) = back_iter {
129                if iter.peek() == Some(after_end) {
130                    let next_range = iter.next_range().unwrap();
131                    debug_assert_eq!(*next_range.start(), after_end);
132                    range_end = *next_range.end();
133                }
134            }
135            break;
136        }
137    }
138
139    Some(range_start..=range_end)
140}
141
142fn next_range_back_impl<'a, It>(
143    front_iter: &mut Option<container::Iter<'a>>,
144    containers: &mut It,
145    back_iter: &mut Option<container::Iter<'a>>,
146) -> Option<core::ops::RangeInclusive<u32>>
147where
148    It: DoubleEndedIterator,
149    It: AsRef<[Container]>,
150    It::Item: IntoIterator<IntoIter = container::Iter<'a>>,
151{
152    let range = loop {
153        if let Some(r) = and_then_or_clear(back_iter, container::Iter::next_range_back) {
154            break r;
155        }
156        *back_iter = match containers.next_back() {
157            Some(inner) => Some(inner.into_iter()),
158            None => return and_then_or_clear(front_iter, container::Iter::next_range_back),
159        }
160    };
161    let (mut range_start, range_end) = (*range.start(), *range.end());
162    while range_start & 0xFFFF == 0 {
163        let Some(before_start) = range_start.checked_sub(1) else {
164            return Some(range_start..=range_end);
165        };
166        let (prev_key, _) = util::split(before_start);
167
168        if containers.as_ref().last().is_some_and(|c| c.key == prev_key && c.contains(u16::MAX)) {
169            let mut iter = containers.next_back().unwrap().into_iter();
170            let next_range = iter.next_range_back().unwrap();
171            *back_iter = Some(iter);
172            debug_assert_eq!(*next_range.end(), before_start);
173            range_start = *next_range.start();
174        } else {
175            if let Some(iter) = front_iter {
176                if iter.key == prev_key && iter.peek_back() == Some(before_start) {
177                    let next_range = iter.next_range_back().unwrap();
178                    debug_assert_eq!(*next_range.end(), before_start);
179                    range_start = *next_range.start();
180                }
181            }
182            break;
183        }
184    }
185
186    Some(range_start..=range_end)
187}
188
189fn advance_back_to_impl<'a, It>(
190    n: u32,
191    front_iter: &mut Option<container::Iter<'a>>,
192    containers: &mut It,
193    back_iter: &mut Option<container::Iter<'a>>,
194) where
195    It: DoubleEndedIterator,
196    It: AsRef<[Container]>,
197    It::Item: IntoIterator<IntoIter = container::Iter<'a>>,
198{
199    let (key, index) = util::split(n);
200    if let Some(iter) = back_iter {
201        match key.cmp(&iter.key) {
202            core::cmp::Ordering::Greater => return,
203            core::cmp::Ordering::Equal => {
204                iter.advance_back_to(index);
205                return;
206            }
207            core::cmp::Ordering::Less => {
208                *back_iter = None;
209            }
210        }
211    }
212    let containers_slice = containers.as_ref();
213    let containers_len = containers_slice.len();
214    let to_skip = match containers_slice.binary_search_by_key(&key, |c| c.key) {
215        Ok(n) => {
216            // n must be less than containers_len, so this can never underflow
217            let n = containers_len - n - 1;
218            let container = containers.nth_back(n).expect("binary search returned a valid index");
219            let mut container_iter = container.into_iter();
220            container_iter.advance_back_to(index);
221            *back_iter = Some(container_iter);
222            return;
223        }
224        Err(n) => containers_len - n,
225    };
226
227    if let Some(n) = to_skip.checked_sub(1) {
228        containers.nth_back(n);
229    }
230    if to_skip != containers_len {
231        // There are still containers with keys less than the key we are looking for,
232        // the key we're looking _can't_ be in the front iterator.
233        return;
234    }
235    if let Some(iter) = front_iter {
236        match key.cmp(&iter.key) {
237            core::cmp::Ordering::Greater => {}
238            core::cmp::Ordering::Equal => {
239                iter.advance_back_to(index);
240            }
241            core::cmp::Ordering::Less => {
242                *front_iter = None;
243            }
244        }
245    }
246}
247
248impl Iter<'_> {
249    fn new(containers: &'_ [Container]) -> Iter<'_> {
250        Iter { front: None, containers: containers.iter(), back: None }
251    }
252
253    fn empty() -> Self {
254        Self::new(&[])
255    }
256
257    /// Advance the iterator to the first position where the item has a value >= `n`
258    ///
259    /// # Examples
260    ///
261    /// ```rust
262    /// use roaring::RoaringBitmap;
263    /// use core::iter::FromIterator;
264    ///
265    /// let bitmap = (1..3).collect::<RoaringBitmap>();
266    /// let mut iter = bitmap.iter();
267    /// iter.advance_to(2);
268    ///
269    /// assert_eq!(iter.next(), Some(2));
270    /// assert_eq!(iter.next(), None);
271    /// ```
272    pub fn advance_to(&mut self, n: u32) {
273        advance_to_impl(n, &mut self.front, &mut self.containers, &mut self.back);
274    }
275
276    /// Advance the back of the iterator to the first position where the item has a value <= `n`
277    ///
278    /// # Examples
279    ///
280    /// ```rust
281    /// use roaring::RoaringBitmap;
282    /// use core::iter::FromIterator;
283    ///
284    /// let bitmap = (1..3).collect::<RoaringBitmap>();
285    /// let mut iter = bitmap.iter();
286    /// iter.advance_back_to(1);
287    ///
288    /// assert_eq!(iter.next_back(), Some(1));
289    /// assert_eq!(iter.next_back(), None);
290    /// ```
291    pub fn advance_back_to(&mut self, n: u32) {
292        advance_back_to_impl(n, &mut self.front, &mut self.containers, &mut self.back);
293    }
294
295    /// Returns the range of consecutive set bits from the current position to the end of the current run
296    ///
297    /// After this call, the iterator will be positioned at the first item after the returned range.
298    /// Returns `None` if the iterator is exhausted.
299    ///
300    /// # Examples
301    ///
302    /// ```rust
303    /// use roaring::RoaringBitmap;
304    ///
305    /// let bm = RoaringBitmap::from([1, 2, 4, 5]);
306    /// let mut iter = bm.iter();
307    /// assert_eq!(iter.next_range(), Some(1..=2));
308    /// assert_eq!(iter.next(), Some(4));
309    /// assert_eq!(iter.next_range(), Some(5..=5));
310    /// ```
311    pub fn next_range(&mut self) -> Option<core::ops::RangeInclusive<u32>> {
312        next_range_impl(&mut self.front, &mut self.containers, &mut self.back)
313    }
314
315    /// Returns the range of consecutive set bits from the start of the current run to the current back position
316    ///
317    /// After this call, the back of the iterator will be positioned at the last item before the returned range.
318    /// Returns `None` if the iterator is exhausted.
319    ///
320    /// # Examples
321    ///
322    /// ```rust
323    /// use roaring::RoaringBitmap;
324    ///
325    /// let bm = RoaringBitmap::from([1, 2, 4, 5]);
326    /// let mut iter = bm.iter();
327    /// assert_eq!(iter.next_range_back(), Some(4..=5));
328    /// assert_eq!(iter.next_back(), Some(2));
329    /// assert_eq!(iter.next_range_back(), Some(1..=1));
330    /// ```
331    pub fn next_range_back(&mut self) -> Option<core::ops::RangeInclusive<u32>> {
332        next_range_back_impl(&mut self.front, &mut self.containers, &mut self.back)
333    }
334}
335
336impl IntoIter {
337    fn new(containers: Vec<Container>) -> IntoIter {
338        IntoIter { front: None, containers: containers.into_iter(), back: None }
339    }
340
341    fn empty() -> Self {
342        Self::new(Vec::new())
343    }
344
345    /// Advance the iterator to the first position where the item has a value >= `n`
346    ///
347    /// # Examples
348    ///
349    /// ```rust
350    /// use roaring::RoaringBitmap;
351    /// use core::iter::FromIterator;
352    ///
353    /// let bitmap = (1..3).collect::<RoaringBitmap>();
354    /// let mut iter = bitmap.iter();
355    /// iter.advance_to(2);
356    ///
357    /// assert_eq!(iter.next(), Some(2));
358    /// assert_eq!(iter.next(), None);
359    /// ```
360    pub fn advance_to(&mut self, n: u32) {
361        advance_to_impl(n, &mut self.front, &mut self.containers, &mut self.back);
362    }
363
364    /// Advance the back of the iterator to the first position where the item has a value <= `n`
365    ///
366    /// # Examples
367    ///
368    /// ```rust
369    /// use roaring::RoaringBitmap;
370    /// use core::iter::FromIterator;
371    ///
372    /// let bitmap = (1..3).collect::<RoaringBitmap>();
373    /// let mut iter = bitmap.into_iter();
374    /// iter.advance_back_to(1);
375    ///
376    /// assert_eq!(iter.next_back(), Some(1));
377    /// assert_eq!(iter.next_back(), None);
378    /// ```
379    pub fn advance_back_to(&mut self, n: u32) {
380        advance_back_to_impl(n, &mut self.front, &mut self.containers, &mut self.back);
381    }
382
383    /// Returns the range of consecutive set bits from the current position to the end of the current run
384    ///
385    /// After this call, the iterator will be positioned at the first item after the returned range.
386    /// Returns `None` if the iterator is exhausted.
387    ///
388    /// # Examples
389    ///
390    /// ```rust
391    /// use roaring::RoaringBitmap;
392    ///
393    /// let bm = RoaringBitmap::from([1, 2, 4, 5]);
394    /// let mut iter = bm.into_iter();
395    /// assert_eq!(iter.next_range(), Some(1..=2));
396    /// assert_eq!(iter.next(), Some(4));
397    /// assert_eq!(iter.next_range(), Some(5..=5));
398    /// ```
399    pub fn next_range(&mut self) -> Option<core::ops::RangeInclusive<u32>> {
400        next_range_impl(&mut self.front, &mut self.containers, &mut self.back)
401    }
402
403    /// Returns the range of consecutive set bits from the start of the current run to the current back position
404    ///
405    /// After this call, the back of the iterator will be positioned at the last item before the returned range.
406    /// Returns `None` if the iterator is exhausted.
407    ///
408    /// # Examples
409    ///
410    /// ```rust
411    /// use roaring::RoaringBitmap;
412    ///
413    /// let bm = RoaringBitmap::from([1, 2, 4, 5]);
414    /// let mut iter = bm.into_iter();
415    /// assert_eq!(iter.next_range_back(), Some(4..=5));
416    /// assert_eq!(iter.next_back(), Some(2));
417    /// assert_eq!(iter.next_range_back(), Some(1..=1));
418    /// ```
419    pub fn next_range_back(&mut self) -> Option<core::ops::RangeInclusive<u32>> {
420        next_range_back_impl(&mut self.front, &mut self.containers, &mut self.back)
421    }
422}
423
424fn size_hint_impl(
425    front: &Option<container::Iter<'_>>,
426    containers: &impl AsRef<[Container]>,
427    back: &Option<container::Iter<'_>>,
428) -> (usize, Option<usize>) {
429    let first_size = front.as_ref().map_or(0, |it| it.len());
430    let last_size = back.as_ref().map_or(0, |it| it.len());
431    let mut size = first_size + last_size;
432    for container in containers.as_ref() {
433        match size.checked_add(container.len() as usize) {
434            Some(new_size) => size = new_size,
435            None => return (usize::MAX, None),
436        }
437    }
438    (size, Some(size))
439}
440
441impl Iterator for Iter<'_> {
442    type Item = u32;
443
444    fn next(&mut self) -> Option<u32> {
445        loop {
446            if let Some(x) = and_then_or_clear(&mut self.front, Iterator::next) {
447                return Some(x);
448            }
449            self.front = match self.containers.next() {
450                Some(inner) => Some(inner.into_iter()),
451                None => return and_then_or_clear(&mut self.back, Iterator::next),
452            }
453        }
454    }
455
456    fn size_hint(&self) -> (usize, Option<usize>) {
457        size_hint_impl(&self.front, &self.containers, &self.back)
458    }
459
460    #[inline]
461    fn fold<B, F>(mut self, mut init: B, mut f: F) -> B
462    where
463        Self: Sized,
464        F: FnMut(B, Self::Item) -> B,
465    {
466        if let Some(iter) = &mut self.front {
467            init = iter.fold(init, &mut f);
468        }
469        init = self.containers.fold(init, |acc, container| {
470            let iter = <&Container>::into_iter(container);
471            iter.fold(acc, &mut f)
472        });
473        if let Some(iter) = &mut self.back {
474            init = iter.fold(init, &mut f);
475        };
476        init
477    }
478
479    fn count(self) -> usize
480    where
481        Self: Sized,
482    {
483        let mut count = self.front.map_or(0, Iterator::count);
484        count += self.containers.map(|container| container.len() as usize).sum::<usize>();
485        count += self.back.map_or(0, Iterator::count);
486        count
487    }
488
489    fn nth(&mut self, n: usize) -> Option<Self::Item> {
490        let mut n = n;
491        let nth_advance = |it: &mut container::Iter| {
492            let len = it.len();
493            if n < len {
494                it.nth(n)
495            } else {
496                n -= len;
497                None
498            }
499        };
500        if let Some(x) = and_then_or_clear(&mut self.front, nth_advance) {
501            return Some(x);
502        }
503        for container in self.containers.by_ref() {
504            let len = container.len() as usize;
505            if n < len {
506                let mut front_iter = container.into_iter();
507                let result = front_iter.nth(n);
508                self.front = Some(front_iter);
509                return result;
510            }
511            n -= len;
512        }
513        and_then_or_clear(&mut self.back, |it| it.nth(n))
514    }
515}
516
517impl DoubleEndedIterator for Iter<'_> {
518    fn next_back(&mut self) -> Option<Self::Item> {
519        loop {
520            if let Some(x) = and_then_or_clear(&mut self.back, DoubleEndedIterator::next_back) {
521                return Some(x);
522            }
523            self.back = match self.containers.next_back() {
524                Some(inner) => Some(inner.into_iter()),
525                None => return and_then_or_clear(&mut self.front, DoubleEndedIterator::next_back),
526            }
527        }
528    }
529
530    #[inline]
531    fn rfold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
532    where
533        Fold: FnMut(Acc, Self::Item) -> Acc,
534    {
535        if let Some(iter) = &mut self.back {
536            init = iter.rfold(init, &mut fold);
537        }
538        init = self.containers.rfold(init, |acc, container| {
539            let iter = container.into_iter();
540            iter.rfold(acc, &mut fold)
541        });
542        if let Some(iter) = &mut self.front {
543            init = iter.rfold(init, &mut fold);
544        };
545        init
546    }
547
548    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
549        let mut n = n;
550        let nth_advance = |it: &mut container::Iter| {
551            let len = it.len();
552            if n < len {
553                it.nth_back(n)
554            } else {
555                n -= len;
556                None
557            }
558        };
559        if let Some(x) = and_then_or_clear(&mut self.back, nth_advance) {
560            return Some(x);
561        }
562        for container in self.containers.by_ref().rev() {
563            let len = container.len() as usize;
564            if n < len {
565                let mut front_iter = container.into_iter();
566                let result = front_iter.nth_back(n);
567                self.back = Some(front_iter);
568                return result;
569            }
570            n -= len;
571        }
572        and_then_or_clear(&mut self.front, |it| it.nth_back(n))
573    }
574}
575
576#[cfg(target_pointer_width = "64")]
577impl ExactSizeIterator for Iter<'_> {}
578impl FusedIterator for Iter<'_> {}
579
580impl Iterator for IntoIter {
581    type Item = u32;
582
583    fn next(&mut self) -> Option<u32> {
584        loop {
585            if let Some(x) = and_then_or_clear(&mut self.front, Iterator::next) {
586                return Some(x);
587            }
588            match self.containers.next() {
589                Some(inner) => self.front = Some(inner.into_iter()),
590                None => return and_then_or_clear(&mut self.back, Iterator::next),
591            }
592        }
593    }
594
595    fn size_hint(&self) -> (usize, Option<usize>) {
596        size_hint_impl(&self.front, &self.containers, &self.back)
597    }
598
599    #[inline]
600    fn fold<B, F>(mut self, mut init: B, mut f: F) -> B
601    where
602        Self: Sized,
603        F: FnMut(B, Self::Item) -> B,
604    {
605        if let Some(iter) = &mut self.front {
606            init = iter.fold(init, &mut f);
607        }
608        init = self.containers.fold(init, |acc, container| {
609            let iter = <Container>::into_iter(container);
610            iter.fold(acc, &mut f)
611        });
612        if let Some(iter) = &mut self.back {
613            init = iter.fold(init, &mut f);
614        };
615        init
616    }
617
618    fn count(self) -> usize
619    where
620        Self: Sized,
621    {
622        let mut count = self.front.map_or(0, Iterator::count);
623        count += self.containers.map(|container| container.len() as usize).sum::<usize>();
624        count += self.back.map_or(0, Iterator::count);
625        count
626    }
627
628    fn nth(&mut self, n: usize) -> Option<Self::Item> {
629        let mut n = n;
630        let nth_advance = |it: &mut container::Iter| {
631            let len = it.len();
632            if n < len {
633                it.nth(n)
634            } else {
635                n -= len;
636                None
637            }
638        };
639        if let Some(x) = and_then_or_clear(&mut self.front, nth_advance) {
640            return Some(x);
641        }
642        for container in self.containers.by_ref() {
643            let len = container.len() as usize;
644            if n < len {
645                let mut front_iter = container.into_iter();
646                let result = front_iter.nth(n);
647                self.front = Some(front_iter);
648                return result;
649            }
650            n -= len;
651        }
652        and_then_or_clear(&mut self.back, |it| it.nth(n))
653    }
654}
655
656impl DoubleEndedIterator for IntoIter {
657    fn next_back(&mut self) -> Option<Self::Item> {
658        loop {
659            if let Some(x) = and_then_or_clear(&mut self.back, DoubleEndedIterator::next_back) {
660                return Some(x);
661            }
662            match self.containers.next_back() {
663                Some(inner) => self.back = Some(inner.into_iter()),
664                None => return and_then_or_clear(&mut self.front, DoubleEndedIterator::next_back),
665            }
666        }
667    }
668
669    #[inline]
670    fn rfold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
671    where
672        Fold: FnMut(Acc, Self::Item) -> Acc,
673    {
674        if let Some(iter) = &mut self.back {
675            init = iter.rfold(init, &mut fold);
676        }
677        init = self.containers.rfold(init, |acc, container| {
678            let iter = container.into_iter();
679            iter.rfold(acc, &mut fold)
680        });
681        if let Some(iter) = &mut self.front {
682            init = iter.rfold(init, &mut fold);
683        };
684        init
685    }
686
687    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
688        let mut n = n;
689        let nth_advance = |it: &mut container::Iter| {
690            let len = it.len();
691            if n < len {
692                it.nth_back(n)
693            } else {
694                n -= len;
695                None
696            }
697        };
698        if let Some(x) = and_then_or_clear(&mut self.back, nth_advance) {
699            return Some(x);
700        }
701        for container in self.containers.by_ref().rev() {
702            let len = container.len() as usize;
703            if n < len {
704                let mut front_iter = container.into_iter();
705                let result = front_iter.nth_back(n);
706                self.back = Some(front_iter);
707                return result;
708            }
709            n -= len;
710        }
711        and_then_or_clear(&mut self.front, |it| it.nth_back(n))
712    }
713}
714
715#[cfg(target_pointer_width = "64")]
716impl ExactSizeIterator for IntoIter {}
717impl FusedIterator for IntoIter {}
718
719impl RoaringBitmap {
720    /// Iterator over each value stored in the RoaringBitmap, guarantees values are ordered by value.
721    ///
722    /// # Examples
723    ///
724    /// ```rust
725    /// use roaring::RoaringBitmap;
726    /// use core::iter::FromIterator;
727    ///
728    /// let bitmap = (1..3).collect::<RoaringBitmap>();
729    /// let mut iter = bitmap.iter();
730    ///
731    /// assert_eq!(iter.next(), Some(1));
732    /// assert_eq!(iter.next(), Some(2));
733    /// assert_eq!(iter.next(), None);
734    /// ```
735    pub fn iter(&'_ self) -> Iter<'_> {
736        Iter::new(&self.containers)
737    }
738
739    /// Iterator over values within a range stored in the RoaringBitmap.
740    ///
741    /// # Examples
742    ///
743    /// ```rust
744    /// use core::ops::Bound;
745    /// use roaring::RoaringBitmap;
746    ///
747    /// let bitmap = RoaringBitmap::from([0, 1, 2, 3, 4, 5, 10, 11, 12, 20, 21, u32::MAX]);
748    /// let mut iter = bitmap.range(10..20);
749    ///
750    /// assert_eq!(iter.next(), Some(10));
751    /// assert_eq!(iter.next(), Some(11));
752    /// assert_eq!(iter.next(), Some(12));
753    /// assert_eq!(iter.next(), None);
754    ///
755    /// let mut iter = bitmap.range(100..);
756    /// assert_eq!(iter.next(), Some(u32::MAX));
757    /// assert_eq!(iter.next(), None);
758    ///
759    /// let mut iter = bitmap.range((Bound::Excluded(0), Bound::Included(10)));
760    /// assert_eq!(iter.next(), Some(1));
761    /// assert_eq!(iter.next(), Some(2));
762    /// assert_eq!(iter.next(), Some(3));
763    /// assert_eq!(iter.next(), Some(4));
764    /// assert_eq!(iter.next(), Some(5));
765    /// assert_eq!(iter.next(), Some(10));
766    /// assert_eq!(iter.next(), None);
767    /// ```
768    pub fn range<R>(&self, range: R) -> Iter<'_>
769    where
770        R: RangeBounds<u32>,
771    {
772        let range = match util::convert_range_to_inclusive(range) {
773            Ok(range) => range,
774            Err(util::ConvertRangeError::Empty) => return Iter::empty(),
775            Err(util::ConvertRangeError::StartGreaterThanEnd) => {
776                panic!("range start is greater than range end")
777            }
778            Err(util::ConvertRangeError::StartAndEndEqualExcluded) => {
779                panic!("range start and end are equal and excluded")
780            }
781        };
782        let (start, end) = (*range.start(), *range.end());
783        let mut iter = self.iter();
784        if start != 0 {
785            iter.advance_to(start);
786        }
787        if end != u32::MAX {
788            iter.advance_back_to(end);
789        }
790        iter
791    }
792
793    /// Iterator over values within a range stored in the RoaringBitmap.
794    ///
795    /// # Examples
796    ///
797    /// ```rust
798    /// use core::ops::Bound;
799    /// use roaring::RoaringBitmap;
800    ///
801    /// fn bitmap() -> RoaringBitmap {
802    ///     RoaringBitmap::from([0, 1, 2, 3, 4, 5, 10, 11, 12, 20, 21, u32::MAX])
803    /// }
804    ///
805    /// let mut iter = bitmap().into_range(10..20);
806    ///
807    /// assert_eq!(iter.next(), Some(10));
808    /// assert_eq!(iter.next(), Some(11));
809    /// assert_eq!(iter.next(), Some(12));
810    /// assert_eq!(iter.next(), None);
811    ///
812    /// let mut iter = bitmap().into_range(100..);
813    /// assert_eq!(iter.next(), Some(u32::MAX));
814    /// assert_eq!(iter.next(), None);
815    ///
816    /// let mut iter = bitmap().into_range((Bound::Excluded(0), Bound::Included(10)));
817    /// assert_eq!(iter.next(), Some(1));
818    /// assert_eq!(iter.next(), Some(2));
819    /// assert_eq!(iter.next(), Some(3));
820    /// assert_eq!(iter.next(), Some(4));
821    /// assert_eq!(iter.next(), Some(5));
822    /// assert_eq!(iter.next(), Some(10));
823    /// assert_eq!(iter.next(), None);
824    /// ```
825    pub fn into_range<R>(self, range: R) -> IntoIter
826    where
827        R: RangeBounds<u32>,
828    {
829        let range = match util::convert_range_to_inclusive(range) {
830            Ok(range) => range,
831            Err(util::ConvertRangeError::Empty) => return IntoIter::empty(),
832            Err(util::ConvertRangeError::StartGreaterThanEnd) => {
833                panic!("range start is greater than range end")
834            }
835            Err(util::ConvertRangeError::StartAndEndEqualExcluded) => {
836                panic!("range start and end are equal and excluded")
837            }
838        };
839        let (start, end) = (*range.start(), *range.end());
840        let mut iter = self.into_iter();
841        if start != 0 {
842            iter.advance_to(start);
843        }
844        if end != u32::MAX {
845            iter.advance_back_to(end);
846        }
847        iter
848    }
849}
850
851impl<'a> IntoIterator for &'a RoaringBitmap {
852    type Item = u32;
853    type IntoIter = Iter<'a>;
854
855    fn into_iter(self) -> Iter<'a> {
856        self.iter()
857    }
858}
859
860impl IntoIterator for RoaringBitmap {
861    type Item = u32;
862    type IntoIter = IntoIter;
863
864    fn into_iter(self) -> IntoIter {
865        IntoIter::new(self.containers)
866    }
867}
868
869impl<const N: usize> From<[u32; N]> for RoaringBitmap {
870    fn from(arr: [u32; N]) -> Self {
871        RoaringBitmap::from_iter(arr)
872    }
873}
874
875impl FromIterator<u32> for RoaringBitmap {
876    fn from_iter<I: IntoIterator<Item = u32>>(iterator: I) -> RoaringBitmap {
877        let mut rb = RoaringBitmap::new();
878        rb.extend(iterator);
879        rb
880    }
881}
882
883impl<'a> FromIterator<&'a u32> for RoaringBitmap {
884    fn from_iter<I: IntoIterator<Item = &'a u32>>(iterator: I) -> RoaringBitmap {
885        let mut rb = RoaringBitmap::new();
886        rb.extend(iterator);
887        rb
888    }
889}
890
891impl Extend<u32> for RoaringBitmap {
892    /// Inserts multiple values and returns the count of new additions.
893    /// This is expected to be faster than calling [`RoaringBitmap::insert`] on each value.
894    ///
895    /// The provided integers values don't have to be in sorted order, but it may be preferable
896    /// to sort them from a performance point of view.
897    ///
898    /// # Examples
899    ///
900    /// ```rust
901    /// use roaring::RoaringBitmap;
902    ///
903    /// let mut rb = RoaringBitmap::new();
904    /// rb.extend([1, 2, 3, 4, 1500, 1508, 1507, 1509]);
905    /// assert!(rb.contains(2));
906    /// assert!(rb.contains(1508));
907    /// assert!(!rb.contains(5));
908    /// ```
909    #[inline]
910    fn extend<I: IntoIterator<Item = u32>>(&mut self, values: I) {
911        let mut values = values.into_iter();
912        let value = match values.next() {
913            Some(value) => value,
914            None => return,
915        };
916
917        let (mut currenthb, lowbit) = util::split(value);
918        let mut current_container_index = self.find_container_by_key(currenthb);
919        let mut current_cont = &mut self.containers[current_container_index];
920        current_cont.insert(lowbit);
921
922        for val in values {
923            let (newhb, lowbit) = util::split(val);
924            if currenthb == newhb {
925                // easy case, this could be quite frequent
926                current_cont.insert(lowbit);
927            } else {
928                currenthb = newhb;
929                current_container_index = self.find_container_by_key(currenthb);
930                current_cont = &mut self.containers[current_container_index];
931                current_cont.insert(lowbit);
932            }
933        }
934    }
935}
936
937impl<'a> Extend<&'a u32> for RoaringBitmap {
938    /// Inserts multiple values and returns the count of new additions.
939    /// This is expected to be faster than calling [`RoaringBitmap::insert`] on each value.
940    ///
941    /// The provided integers values don't have to be in sorted order, but it may be preferable
942    /// to sort them from a performance point of view.
943    ///
944    /// # Examples
945    ///
946    /// ```rust
947    /// use roaring::RoaringBitmap;
948    ///
949    /// let mut rb = RoaringBitmap::new();
950    /// rb.extend([1, 2, 3, 4, 1500, 1508, 1507, 1509]);
951    /// assert!(rb.contains(2));
952    /// assert!(rb.contains(1508));
953    /// assert!(!rb.contains(5));
954    /// ```
955    #[inline]
956    fn extend<I: IntoIterator<Item = &'a u32>>(&mut self, values: I) {
957        self.extend(values.into_iter().copied());
958    }
959}
960
961impl RoaringBitmap {
962    /// Create the set from a sorted iterator. Values must be sorted and deduplicated.
963    ///
964    /// The values of the iterator must be ordered and strictly greater than the greatest value
965    /// in the set. If a value in the iterator doesn't satisfy this requirement, it is not added
966    /// and the append operation is stopped.
967    ///
968    /// Returns `Ok` with the requested `RoaringBitmap`, `Err` with the number of elements
969    /// that were correctly appended before failure.
970    ///
971    /// # Example: Create a set from an ordered list of integers.
972    ///
973    /// ```rust
974    /// use roaring::RoaringBitmap;
975    ///
976    /// let mut rb = RoaringBitmap::from_sorted_iter(0..10).unwrap();
977    ///
978    /// assert!(rb.iter().eq(0..10));
979    /// ```
980    ///
981    /// # Example: Try to create a set from a non-ordered list of integers.
982    ///
983    /// ```rust
984    /// use roaring::RoaringBitmap;
985    ///
986    /// let integers = 0..10u32;
987    /// let error = RoaringBitmap::from_sorted_iter(integers.rev()).unwrap_err();
988    ///
989    /// assert_eq!(error.valid_until(), 1);
990    /// ```
991    pub fn from_sorted_iter<I: IntoIterator<Item = u32>>(
992        iterator: I,
993    ) -> Result<RoaringBitmap, NonSortedIntegers> {
994        let mut rb = RoaringBitmap::new();
995        rb.append(iterator).map(|_| rb)
996    }
997
998    /// Extend the set with a sorted iterator.
999    ///
1000    /// The values of the iterator must be ordered and strictly greater than the greatest value
1001    /// in the set. If a value in the iterator doesn't satisfy this requirement, it is not added
1002    /// and the append operation is stopped.
1003    ///
1004    /// Returns `Ok` with the number of elements appended to the set, `Err` with
1005    /// the number of elements we effectively appended before an error occurred.
1006    ///
1007    /// # Examples
1008    ///
1009    /// ```rust
1010    /// use roaring::RoaringBitmap;
1011    ///
1012    /// let mut rb = RoaringBitmap::new();
1013    /// assert_eq!(rb.append(0..10), Ok(10));
1014    ///
1015    /// assert!(rb.iter().eq(0..10));
1016    /// ```
1017    pub fn append<I: IntoIterator<Item = u32>>(
1018        &mut self,
1019        iterator: I,
1020    ) -> Result<u64, NonSortedIntegers> {
1021        // Name shadowed to prevent accidentally referencing the param
1022        let mut iterator = iterator.into_iter();
1023
1024        let mut prev = match (iterator.next(), self.max()) {
1025            (None, _) => return Ok(0),
1026            (Some(first), Some(max)) if first <= max => {
1027                return Err(NonSortedIntegers { valid_until: 0 })
1028            }
1029            (Some(first), _) => first,
1030        };
1031
1032        // It is now guaranteed that so long as the values of the iterator are
1033        // monotonically increasing they must also be the greatest in the set.
1034
1035        self.push_unchecked(prev);
1036
1037        let mut count = 1;
1038
1039        for value in iterator {
1040            if value <= prev {
1041                return Err(NonSortedIntegers { valid_until: count });
1042            } else {
1043                self.push_unchecked(value);
1044                prev = value;
1045                count += 1;
1046            }
1047        }
1048
1049        Ok(count)
1050    }
1051}
roaring/bitmap/iter.rs

roaring/bitmap/
iter.rs
