/rust/registry/src/index.crates.io-1949cf8c6b5b557f/roaring-0.11.4/src/treemap/iter.rs

Source
use alloc::collections::{btree_map, BTreeMap};
use core::iter;
use core::ops::Add;

use super::util;
use crate::bitmap::IntoIter as IntoIter32;
use crate::bitmap::Iter as Iter32;
use crate::{NonSortedIntegers, RoaringBitmap, RoaringTreemap};

#[derive(Clone)]
struct To64Iter<'a> {
    hi: u32,
    inner: Iter32<'a>,
}

impl To64Iter<'_> {
    fn advance_to(&mut self, n: u32) {
        self.inner.advance_to(n)
    }

    fn advance_back_to(&mut self, n: u32) {
        self.inner.advance_back_to(n)
    }
}

impl Iterator for To64Iter<'_> {
    type Item = u64;
    fn next(&mut self) -> Option<u64> {
        self.inner.next().map(|n| util::join(self.hi, n))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }

    #[inline]
    fn fold<B, F>(self, init: B, mut f: F) -> B
    where
        Self: Sized,
        F: FnMut(B, Self::Item) -> B,
    {
        self.inner.fold(init, move |b, lo| f(b, ((self.hi as u64) << 32) + (lo as u64)))
    }
}

impl DoubleEndedIterator for To64Iter<'_> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.inner.next_back().map(|n| util::join(self.hi, n))
    }

    #[inline]
    fn rfold<B, F>(self, init: B, mut f: F) -> B
    where
        Self: Sized,
        F: FnMut(B, Self::Item) -> B,
    {
        self.inner.rfold(init, move |b, lo| f(b, ((self.hi as u64) << 32) + (lo as u64)))
    }
}

fn to64iter(t: (u32, &RoaringBitmap)) -> To64Iter<'_> {
    To64Iter { hi: t.0, inner: t.1.iter() }
}

#[derive(Clone)]
struct To64IntoIter {
    hi: u32,
    inner: IntoIter32,
}

impl Iterator for To64IntoIter {
    type Item = u64;
    fn next(&mut self) -> Option<u64> {
        self.inner.next().map(|n| util::join(self.hi, n))
    }

    #[inline]
    fn fold<B, F>(self, init: B, mut f: F) -> B
    where
        Self: Sized,
        F: FnMut(B, Self::Item) -> B,
    {
        self.inner.fold(init, move |b, lo| f(b, ((self.hi as u64) << 32) + (lo as u64)))
    }
}

impl DoubleEndedIterator for To64IntoIter {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.inner.next_back().map(|n| util::join(self.hi, n))
    }

    #[inline]
    fn rfold<B, F>(self, init: B, mut f: F) -> B
    where
        Self: Sized,
        F: FnMut(B, Self::Item) -> B,
    {
        self.inner.rfold(init, move |b, lo| f(b, ((self.hi as u64) << 32) + (lo as u64)))
    }
}

fn to64intoiter(t: (u32, RoaringBitmap)) -> To64IntoIter {
    To64IntoIter { hi: t.0, inner: t.1.into_iter() }
}

type InnerIntoIter = iter::FlatMap<
    btree_map::IntoIter<u32, RoaringBitmap>,
    To64IntoIter,
    fn((u32, RoaringBitmap)) -> To64IntoIter,
>;

/// An iterator for `RoaringTreemap`.
#[derive(Clone)]
pub struct Iter<'a> {
    outer: BitmapIter<'a>,
    front: Option<To64Iter<'a>>,
    back: Option<To64Iter<'a>>,
}

/// An iterator for `RoaringTreemap`.
pub struct IntoIter {
    inner: InnerIntoIter,
    size_hint: u64,
}

impl Iter<'_> {
    fn new(map: &'_ BTreeMap<u32, RoaringBitmap>) -> Iter<'_> {
        let outer = BitmapIter::new(map);
        Iter { outer, front: None, back: None }
    }

    /// Advance the iterator to the first position where the item has a value >= `n`
    ///
    /// # Examples
    ///
    /// ```rust
    /// use roaring::RoaringTreemap;
    /// use core::iter::FromIterator;
    ///
    /// let bitmap = (1..3).collect::<RoaringTreemap>();
    /// let mut iter = bitmap.iter();
    /// iter.advance_to(2);
    ///
    /// assert_eq!(iter.next(), Some(2));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn advance_to(&mut self, n: u64) {
        let (key, index) = util::split(n);

        self.outer.advance_to(key);

        if self.front.is_none() {
            let Some(next) = self.outer.next() else {
                // if the current front iterator is empty or not yet initialized,
                // but the outer bitmap iterator is empty, then consume the back
                // iterator from the front if it is not also exhausted
                if let Some(ref mut back) = self.back {
                    back.advance_to(index);
                }
                return;
            };
            self.front = Some(to64iter(next));
        }

        if let Some(ref mut front) = self.front {
            front.advance_to(index);
        }
    }

    /// Advance the back of the iterator to the first position where the item has a value <= `n`
    ///
    /// # Examples
    ///
    /// ```rust
    /// use roaring::RoaringTreemap;
    /// use core::iter::FromIterator;
    ///
    /// let bitmap = (1..3).collect::<RoaringTreemap>();
    /// let mut iter = bitmap.iter();
    /// iter.advance_back_to(1);
    ///
    /// assert_eq!(iter.next_back(), Some(1));
    /// assert_eq!(iter.next_back(), None);
    /// ```
    pub fn advance_back_to(&mut self, n: u64) {
        let (key, index) = util::split(n);

        self.outer.advance_back_to(key);

        if self.back.is_none() {
            let Some(next_back) = self.outer.next_back() else {
                // if the current back iterator is empty or not yet initialized,
                // but the outer bitmap iterator is empty, then consume the front
                // iterator from the back if it is not also exhausted
                if let Some(ref mut front) = self.front {
                    front.advance_back_to(index);
                }
                return;
            };
            self.back = Some(to64iter(next_back));
        }

        if let Some(ref mut back) = self.back {
            back.advance_back_to(index);
        }
    }
}

impl IntoIter {
    fn new(map: BTreeMap<u32, RoaringBitmap>) -> IntoIter {
        let size_hint = map.values().map(|r| r.len()).sum();
        let i = map.into_iter().flat_map(to64intoiter as _);
        IntoIter { inner: i, size_hint }
    }
}

impl Iterator for Iter<'_> {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        if let Some(ref mut front) = &mut self.front {
            if let Some(inner) = front.next() {
                return Some(inner);
            }
        }

        let Some(outer_next) = self.outer.next() else {
            // if the current front iterator is empty or not yet initialized,
            // but the outer bitmap iterator is empty, then consume the back
            // iterator from the front if it is not also exhausted
            if let Some(ref mut back) = &mut self.back {
                if let Some(next) = back.next() {
                    return Some(next);
                }
            }
            return None;
        };

        self.front = Some(to64iter(outer_next));
        self.next()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let front_size_hint = self.front.as_ref().map_or(0, |f| f.size_hint().0);
        let back_size_hint = self.back.as_ref().map_or(0, |b| b.size_hint().0);

        let size_hint = front_size_hint
            .saturating_add(back_size_hint)
            .saturating_add(self.outer.remaining() as usize);

        (size_hint, Some(size_hint))
    }
}

impl DoubleEndedIterator for Iter<'_> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if let Some(ref mut back) = &mut self.back {
            if let Some(inner) = back.next_back() {
                return Some(inner);
            }
        }

        let Some(outer_next_back) = self.outer.next_back() else {
            // if the current back iterator is empty or not yet initialized,
            // but the outer bitmap iterator is empty, then consume the front
            // iterator from the back if it is not also exhausted
            if let Some(ref mut front) = &mut self.front {
                if let Some(next_back) = front.next_back() {
                    return Some(next_back);
                }
            }
            return None;
        };

        self.back = Some(to64iter(outer_next_back));
        self.next_back()
    }
}

#[cfg(target_pointer_width = "64")]
impl ExactSizeIterator for Iter<'_> {
    fn len(&self) -> usize {
        self.size_hint().0
    }
}

impl Iterator for IntoIter {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        self.size_hint = self.size_hint.saturating_sub(1);
        self.inner.next()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        if self.size_hint < usize::MAX as u64 {
            (self.size_hint as usize, Some(self.size_hint as usize))
        } else {
            (usize::MAX, None)
        }
    }

    #[inline]
    fn fold<B, F>(self, init: B, f: F) -> B
    where
        Self: Sized,
        F: FnMut(B, Self::Item) -> B,
    {
        self.inner.fold(init, f)
    }
}

impl DoubleEndedIterator for IntoIter {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.size_hint = self.size_hint.saturating_sub(1);
        self.inner.next_back()
    }

    #[inline]
    fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
    where
        Fold: FnMut(Acc, Self::Item) -> Acc,
    {
        self.inner.rfold(init, fold)
    }
}

#[cfg(target_pointer_width = "64")]
impl ExactSizeIterator for IntoIter {
    fn len(&self) -> usize {
        self.size_hint as usize
    }
}

impl RoaringTreemap {
    /// Iterator over each value stored in the RoaringTreemap, guarantees values are ordered by
    /// value.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use roaring::RoaringTreemap;
    /// use core::iter::FromIterator;
    ///
    /// let bitmap = (1..3).collect::<RoaringTreemap>();
    /// let mut iter = bitmap.iter();
    ///
    /// assert_eq!(iter.next(), Some(1));
    /// assert_eq!(iter.next(), Some(2));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn iter(&'_ self) -> Iter<'_> {
        Iter::new(&self.map)
    }

    /// Iterator over pairs of partition number and the corresponding RoaringBitmap.
    /// The partition number is defined by the 32 most significant bits of the bit index.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use roaring::{RoaringBitmap, RoaringTreemap};
    /// use core::iter::FromIterator;
    ///
    /// let original = (0..6000).collect::<RoaringTreemap>();
    /// let mut bitmaps = original.bitmaps();
    ///
    /// assert_eq!(bitmaps.next(), Some((0, &(0..6000).collect::<RoaringBitmap>())));
    /// assert_eq!(bitmaps.next(), None);
    /// ```
    pub fn bitmaps(&'_ self) -> BitmapIter<'_> {
        BitmapIter::new(&self.map)
    }

    /// Construct a RoaringTreemap from an iterator of partition number and RoaringBitmap pairs.
    /// The partition number is defined by the 32 most significant bits of the bit index.
    /// Note that repeated partitions, if present, will replace previously set partitions.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use roaring::RoaringTreemap;
    /// use core::iter::FromIterator;
    ///
    /// let original = (0..6000).collect::<RoaringTreemap>();
    /// let clone = RoaringTreemap::from_bitmaps(original.bitmaps().map(|(p, b)| (p, b.clone())));
    ///
    /// assert_eq!(clone, original);
    /// ```
    pub fn from_bitmaps<I: IntoIterator<Item = (u32, RoaringBitmap)>>(iterator: I) -> Self {
        RoaringTreemap { map: iterator.into_iter().collect() }
    }
}

impl<'a> IntoIterator for &'a RoaringTreemap {
    type Item = u64;
    type IntoIter = Iter<'a>;

    fn into_iter(self) -> Iter<'a> {
        self.iter()
    }
}

impl IntoIterator for RoaringTreemap {
    type Item = u64;
    type IntoIter = IntoIter;

    fn into_iter(self) -> IntoIter {
        IntoIter::new(self.map)
    }
}

impl<const N: usize> From<[u64; N]> for RoaringTreemap {
    fn from(arr: [u64; N]) -> Self {
        RoaringTreemap::from_iter(arr)
    }
}

impl FromIterator<u64> for RoaringTreemap {
    fn from_iter<I: IntoIterator<Item = u64>>(iterator: I) -> RoaringTreemap {
        let mut rb = RoaringTreemap::new();
        rb.extend(iterator);
        rb
    }
}

impl<'a> FromIterator<&'a u64> for RoaringTreemap {
    fn from_iter<I: IntoIterator<Item = &'a u64>>(iterator: I) -> RoaringTreemap {
        let mut rb = RoaringTreemap::new();
        rb.extend(iterator);
        rb
    }
}

impl Extend<u64> for RoaringTreemap {
    fn extend<I: IntoIterator<Item = u64>>(&mut self, iterator: I) {
        for value in iterator {
            self.insert(value);
        }
    }
}

impl<'a> Extend<&'a u64> for RoaringTreemap {
    fn extend<I: IntoIterator<Item = &'a u64>>(&mut self, iterator: I) {
        for value in iterator {
            self.insert(*value);
        }
    }
}

impl RoaringTreemap {
    /// Create the set from a sorted iterator. Values must be sorted and deduplicated.
    ///
    /// The values of the iterator must be ordered and strictly greater than the greatest value
    /// in the set. If a value in the iterator doesn't satisfy this requirement, it is not added
    /// and the append operation is stopped.
    ///
    /// Returns `Ok` with the requested `RoaringTreemap`, `Err` with the number of elements
    /// we tried to append before an error occurred.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use roaring::RoaringTreemap;
    ///
    /// let mut rb = RoaringTreemap::from_sorted_iter(0..10).unwrap();
    ///
    /// assert!(rb.iter().eq(0..10));
    /// ```
    pub fn from_sorted_iter<I: IntoIterator<Item = u64>>(
        iterator: I,
    ) -> Result<RoaringTreemap, NonSortedIntegers> {
        let mut rt = RoaringTreemap::new();
        rt.append(iterator).map(|_| rt)
    }

    /// Extend the set with a sorted iterator.
    ///
    /// The values of the iterator must be ordered and strictly greater than the greatest value
    /// in the set. If a value in the iterator doesn't satisfy this requirement, it is not added
    /// and the append operation is stopped.
    ///
    /// Returns `Ok` with the number of elements appended to the set, `Err` with
    /// the number of elements we effectively appended before an error occurred.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use roaring::RoaringTreemap;
    ///
    /// let mut rb = RoaringTreemap::new();
    /// rb.append(0..10);
    ///
    /// assert!(rb.iter().eq(0..10));
    /// ```
    pub fn append<I: IntoIterator<Item = u64>>(
        &mut self,
        iterator: I,
    ) -> Result<u64, NonSortedIntegers> {
        let mut iterator = iterator.into_iter();
        let mut prev = match (iterator.next(), self.max()) {
            (None, _) => return Ok(0),
            (Some(first), Some(max)) if first <= max => {
                return Err(NonSortedIntegers { valid_until: 0 })
            }
            (Some(first), _) => first,
        };

        // It is now guaranteed that so long as the values of the iterator are
        // monotonically increasing they must also be the greatest in the set.

        self.push_unchecked(prev);

        let mut count = 1;
        for value in iterator {
            if value <= prev {
                return Err(NonSortedIntegers { valid_until: count });
            } else {
                self.push_unchecked(value);
                prev = value;
                count += 1;
            }
        }

        Ok(count)
    }
}

/// An iterator of `RoaringBitmap`s for `RoaringTreemap`.
#[derive(Clone)]
pub struct BitmapIter<'a> {
    treemap: &'a BTreeMap<u32, RoaringBitmap>,
    range: btree_map::Range<'a, u32, RoaringBitmap>,
    latest_front_idx: Option<u32>,
    latest_back_idx: Option<u32>,
}

impl<'a> BitmapIter<'a> {
    fn new(treemap: &'a BTreeMap<u32, RoaringBitmap>) -> Self {
        let range = treemap.range(..);
        Self { treemap, range, latest_back_idx: None, latest_front_idx: None }
    }

    fn advance_to(&mut self, new_front_idx: u32) {
        match self.latest_back_idx {
            Some(latest_back_idx) => match self.latest_front_idx {
                Some(last_idx) if last_idx >= new_front_idx => {}
                _ => {
                    // if asked to advance to beyond the back iterator,
                    // update the self.range iterator to be empty
                    if new_front_idx >= latest_back_idx {
                        self.range = self.treemap.range(0..1);
                        self.range.next_back();
                    } else {
                        // otherwise shrink the remaining range from the front
                        self.range = self.treemap.range(new_front_idx..latest_back_idx);
                    }

                    // self.range = self.treemap.range(new_front_idx..latest_back_idx);
                }
            },
            None => match self.latest_front_idx {
                Some(latest_idx) if latest_idx >= new_front_idx => {}
                _ => {
                    self.range = self.treemap.range(new_front_idx..);
                }
            },
        }
    }

    fn advance_back_to(&mut self, new_back_idx: u32) {
        match self.latest_front_idx {
            Some(latest_front_idx) => match self.latest_back_idx {
                // do nothing if asked to advance back to a higher index than the back is already at
                Some(latest_back_idx) if latest_back_idx <= new_back_idx => {}
                _ => {
                    // if asked to advance back to beyond the front iterator,
                    // update the self.range iterator to be empty
                    if new_back_idx <= latest_front_idx {
                        self.range = self.treemap.range(0..1);
                        self.range.next_back();
                    } else {
                        // otherwise shrink the remaining range from the back
                        self.range = self.treemap.range((latest_front_idx + 1)..new_back_idx);
                    }
                }
            },
            None => match self.latest_back_idx {
                Some(latest_back_idx) if latest_back_idx <= new_back_idx => {}
                _ => {
                    self.range = self.treemap.range(..=new_back_idx);
                }
            },
        }
    }

    fn remaining(&self) -> u64 {
        let range = self.range.clone();
        range.fold(0, |acc, (_, bitmap)| acc.add(bitmap.len()))
    }
}

impl<'a> Iterator for BitmapIter<'a> {
    type Item = (u32, &'a RoaringBitmap);

    fn next(&mut self) -> Option<Self::Item> {
        match self.range.next().map(|(&p, b)| (p, b)) {
            None => {
                self.latest_front_idx = None;
                None
            }
            Some((next_idx, next_map)) => {
                self.latest_front_idx = Some(next_idx);
                Some((next_idx, next_map))
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.range.size_hint()
    }
}

impl FromIterator<(u32, RoaringBitmap)> for RoaringTreemap {
    fn from_iter<I: IntoIterator<Item = (u32, RoaringBitmap)>>(iterator: I) -> RoaringTreemap {
        Self::from_bitmaps(iterator)
    }
}

impl DoubleEndedIterator for BitmapIter<'_> {
    fn next_back(&mut self) -> Option<Self::Item> {
        match self.range.next_back().map(|(&p, b)| (p, b)) {
            None => {
                self.latest_back_idx = None;
                None
            }
            Some((next_back_idx, next_back_map)) => {
                self.latest_back_idx = Some(next_back_idx);
                Some((next_back_idx, next_back_map))
            }
        }
    }
}

Coverage Report

Created: 2026-08-14 08:14

Line	Count	Source
1		use alloc::collections::{btree_map, BTreeMap};
2		use core::iter;
3		use core::ops::Add;
4
5		use super::util;
6		use crate::bitmap::IntoIter as IntoIter32;
7		use crate::bitmap::Iter as Iter32;
8		use crate::{NonSortedIntegers, RoaringBitmap, RoaringTreemap};
9
10		#[derive(Clone)]
11		struct To64Iter<'a> {
12		hi: u32,
13		inner: Iter32<'a>,
14		}
15
16		impl To64Iter<'_> {
17	0	fn advance_to(&mut self, n: u32) {
18	0	self.inner.advance_to(n)
19	0	}
20
21	0	fn advance_back_to(&mut self, n: u32) {
22	0	self.inner.advance_back_to(n)
23	0	}
24		}
25
26		impl Iterator for To64Iter<'_> {
27		type Item = u64;
28	0	fn next(&mut self) -> Option<u64> {
29	0	self.inner.next().map(\|n\| util::join(self.hi, n))
30	0	}
31
32	0	fn size_hint(&self) -> (usize, Option<usize>) {
33	0	self.inner.size_hint()
34	0	}
35
36		#[inline]
37	0	fn fold<B, F>(self, init: B, mut f: F) -> B
38	0	where
39	0	Self: Sized,
40	0	F: FnMut(B, Self::Item) -> B,
41		{
42	0	self.inner.fold(init, move \|b, lo\| f(b, ((self.hi as u64) << 32) + (lo as u64)))
43	0	}
44		}
45
46		impl DoubleEndedIterator for To64Iter<'_> {
47	0	fn next_back(&mut self) -> Option<Self::Item> {
48	0	self.inner.next_back().map(\|n\| util::join(self.hi, n))
49	0	}
50
51		#[inline]
52	0	fn rfold<B, F>(self, init: B, mut f: F) -> B
53	0	where
54	0	Self: Sized,
55	0	F: FnMut(B, Self::Item) -> B,
56		{
57	0	self.inner.rfold(init, move \|b, lo\| f(b, ((self.hi as u64) << 32) + (lo as u64)))
58	0	}
59		}
60
61	0	fn to64iter(t: (u32, &RoaringBitmap)) -> To64Iter<'_> {
62	0	To64Iter { hi: t.0, inner: t.1.iter() }
63	0	}
64
65		#[derive(Clone)]
66		struct To64IntoIter {
67		hi: u32,
68		inner: IntoIter32,
69		}
70
71		impl Iterator for To64IntoIter {
72		type Item = u64;
73	0	fn next(&mut self) -> Option<u64> {
74	0	self.inner.next().map(\|n\| util::join(self.hi, n))
75	0	}
76
77		#[inline]
78	0	fn fold<B, F>(self, init: B, mut f: F) -> B
79	0	where
80	0	Self: Sized,
81	0	F: FnMut(B, Self::Item) -> B,
82		{
83	0	self.inner.fold(init, move \|b, lo\| f(b, ((self.hi as u64) << 32) + (lo as u64)))
84	0	}
85		}
86
87		impl DoubleEndedIterator for To64IntoIter {
88	0	fn next_back(&mut self) -> Option<Self::Item> {
89	0	self.inner.next_back().map(\|n\| util::join(self.hi, n))
90	0	}
91
92		#[inline]
93	0	fn rfold<B, F>(self, init: B, mut f: F) -> B
94	0	where
95	0	Self: Sized,
96	0	F: FnMut(B, Self::Item) -> B,
97		{
98	0	self.inner.rfold(init, move \|b, lo\| f(b, ((self.hi as u64) << 32) + (lo as u64)))
99	0	}
100		}
101
102	0	fn to64intoiter(t: (u32, RoaringBitmap)) -> To64IntoIter {
103	0	To64IntoIter { hi: t.0, inner: t.1.into_iter() }
104	0	}
105
106		type InnerIntoIter = iter::FlatMap<
107		btree_map::IntoIter<u32, RoaringBitmap>,
108		To64IntoIter,
109		fn((u32, RoaringBitmap)) -> To64IntoIter,
110		>;
111
112		/// An iterator for `RoaringTreemap`.
113		#[derive(Clone)]
114		pub struct Iter<'a> {
115		outer: BitmapIter<'a>,
116		front: Option<To64Iter<'a>>,
117		back: Option<To64Iter<'a>>,
118		}
119
120		/// An iterator for `RoaringTreemap`.
121		pub struct IntoIter {
122		inner: InnerIntoIter,
123		size_hint: u64,
124		}
125
126		impl Iter<'_> {
127	0	fn new(map: &'_ BTreeMap<u32, RoaringBitmap>) -> Iter<'_> {
128	0	let outer = BitmapIter::new(map);
129	0	Iter { outer, front: None, back: None }
130	0	}
131
132		/// Advance the iterator to the first position where the item has a value >= `n`
133		///
134		/// # Examples
135		///
136		/// ```rust
137		/// use roaring::RoaringTreemap;
138		/// use core::iter::FromIterator;
139		///
140		/// let bitmap = (1..3).collect::<RoaringTreemap>();
141		/// let mut iter = bitmap.iter();
142		/// iter.advance_to(2);
143		///
144		/// assert_eq!(iter.next(), Some(2));
145		/// assert_eq!(iter.next(), None);
146		/// ```
147	0	pub fn advance_to(&mut self, n: u64) {
148	0	let (key, index) = util::split(n);
149
150	0	self.outer.advance_to(key);
151
152	0	if self.front.is_none() {
153	0	let Some(next) = self.outer.next() else {
154		// if the current front iterator is empty or not yet initialized,
155		// but the outer bitmap iterator is empty, then consume the back
156		// iterator from the front if it is not also exhausted
157	0	if let Some(ref mut back) = self.back {
158	0	back.advance_to(index);
159	0	}
160	0	return;
161		};
162	0	self.front = Some(to64iter(next));
163	0	}
164
165	0	if let Some(ref mut front) = self.front {
166	0	front.advance_to(index);
167	0	}
168	0	}
169
170		/// Advance the back of the iterator to the first position where the item has a value <= `n`
171		///
172		/// # Examples
173		///
174		/// ```rust
175		/// use roaring::RoaringTreemap;
176		/// use core::iter::FromIterator;
177		///
178		/// let bitmap = (1..3).collect::<RoaringTreemap>();
179		/// let mut iter = bitmap.iter();
180		/// iter.advance_back_to(1);
181		///
182		/// assert_eq!(iter.next_back(), Some(1));
183		/// assert_eq!(iter.next_back(), None);
184		/// ```
185	0	pub fn advance_back_to(&mut self, n: u64) {
186	0	let (key, index) = util::split(n);
187
188	0	self.outer.advance_back_to(key);
189
190	0	if self.back.is_none() {
191	0	let Some(next_back) = self.outer.next_back() else {
192		// if the current back iterator is empty or not yet initialized,
193		// but the outer bitmap iterator is empty, then consume the front
194		// iterator from the back if it is not also exhausted
195	0	if let Some(ref mut front) = self.front {
196	0	front.advance_back_to(index);
197	0	}
198	0	return;
199		};
200	0	self.back = Some(to64iter(next_back));
201	0	}
202
203	0	if let Some(ref mut back) = self.back {
204	0	back.advance_back_to(index);
205	0	}
206	0	}
207		}
208
209		impl IntoIter {
210	0	fn new(map: BTreeMap<u32, RoaringBitmap>) -> IntoIter {
211	0	let size_hint = map.values().map(\|r\| r.len()).sum();
212	0	let i = map.into_iter().flat_map(to64intoiter as _);
213	0	IntoIter { inner: i, size_hint }
214	0	}
215		}
216
217		impl Iterator for Iter<'_> {
218		type Item = u64;
219
220	0	fn next(&mut self) -> Option<u64> {
221	0	if let Some(ref mut front) = &mut self.front {
222	0	if let Some(inner) = front.next() {
223	0	return Some(inner);
224	0	}
225	0	}
226
227	0	let Some(outer_next) = self.outer.next() else {
228		// if the current front iterator is empty or not yet initialized,
229		// but the outer bitmap iterator is empty, then consume the back
230		// iterator from the front if it is not also exhausted
231	0	if let Some(ref mut back) = &mut self.back {
232	0	if let Some(next) = back.next() {
233	0	return Some(next);
234	0	}
235	0	}
236	0	return None;
237		};
238
239	0	self.front = Some(to64iter(outer_next));
240	0	self.next()
241	0	}
242
243	0	fn size_hint(&self) -> (usize, Option<usize>) {
244	0	let front_size_hint = self.front.as_ref().map_or(0, \|f\| f.size_hint().0);
245	0	let back_size_hint = self.back.as_ref().map_or(0, \|b\| b.size_hint().0);
246
247	0	let size_hint = front_size_hint
248	0	.saturating_add(back_size_hint)
249	0	.saturating_add(self.outer.remaining() as usize);
250
251	0	(size_hint, Some(size_hint))
252	0	}
253		}
254
255		impl DoubleEndedIterator for Iter<'_> {
256	0	fn next_back(&mut self) -> Option<Self::Item> {
257	0	if let Some(ref mut back) = &mut self.back {
258	0	if let Some(inner) = back.next_back() {
259	0	return Some(inner);
260	0	}
261	0	}
262
263	0	let Some(outer_next_back) = self.outer.next_back() else {
264		// if the current back iterator is empty or not yet initialized,
265		// but the outer bitmap iterator is empty, then consume the front
266		// iterator from the back if it is not also exhausted
267	0	if let Some(ref mut front) = &mut self.front {
268	0	if let Some(next_back) = front.next_back() {
269	0	return Some(next_back);
270	0	}
271	0	}
272	0	return None;
273		};
274
275	0	self.back = Some(to64iter(outer_next_back));
276	0	self.next_back()
277	0	}
278		}
279
280		#[cfg(target_pointer_width = "64")]
281		impl ExactSizeIterator for Iter<'_> {
282	0	fn len(&self) -> usize {
283	0	self.size_hint().0
284	0	}
285		}
286
287		impl Iterator for IntoIter {
288		type Item = u64;
289
290	0	fn next(&mut self) -> Option<u64> {
291	0	self.size_hint = self.size_hint.saturating_sub(1);
292	0	self.inner.next()
293	0	}
294
295	0	fn size_hint(&self) -> (usize, Option<usize>) {
296	0	if self.size_hint < usize::MAX as u64 {
297	0	(self.size_hint as usize, Some(self.size_hint as usize))
298		} else {
299	0	(usize::MAX, None)
300		}
301	0	}
302
303		#[inline]
304	0	fn fold<B, F>(self, init: B, f: F) -> B
305	0	where
306	0	Self: Sized,
307	0	F: FnMut(B, Self::Item) -> B,
308		{
309	0	self.inner.fold(init, f)
310	0	}
311		}
312
313		impl DoubleEndedIterator for IntoIter {
314	0	fn next_back(&mut self) -> Option<Self::Item> {
315	0	self.size_hint = self.size_hint.saturating_sub(1);
316	0	self.inner.next_back()
317	0	}
318
319		#[inline]
320	0	fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
321	0	where
322	0	Fold: FnMut(Acc, Self::Item) -> Acc,
323		{
324	0	self.inner.rfold(init, fold)
325	0	}
326		}
327
328		#[cfg(target_pointer_width = "64")]
329		impl ExactSizeIterator for IntoIter {
330	0	fn len(&self) -> usize {
331	0	self.size_hint as usize
332	0	}
333		}
334
335		impl RoaringTreemap {
336		/// Iterator over each value stored in the RoaringTreemap, guarantees values are ordered by
337		/// value.
338		///
339		/// # Examples
340		///
341		/// ```rust
342		/// use roaring::RoaringTreemap;
343		/// use core::iter::FromIterator;
344		///
345		/// let bitmap = (1..3).collect::<RoaringTreemap>();
346		/// let mut iter = bitmap.iter();
347		///
348		/// assert_eq!(iter.next(), Some(1));
349		/// assert_eq!(iter.next(), Some(2));
350		/// assert_eq!(iter.next(), None);
351		/// ```
352	0	pub fn iter(&'_ self) -> Iter<'_> {
353	0	Iter::new(&self.map)
354	0	}
355
356		/// Iterator over pairs of partition number and the corresponding RoaringBitmap.
357		/// The partition number is defined by the 32 most significant bits of the bit index.
358		///
359		/// # Examples
360		///
361		/// ```rust
362		/// use roaring::{RoaringBitmap, RoaringTreemap};
363		/// use core::iter::FromIterator;
364		///
365		/// let original = (0..6000).collect::<RoaringTreemap>();
366		/// let mut bitmaps = original.bitmaps();
367		///
368		/// assert_eq!(bitmaps.next(), Some((0, &(0..6000).collect::<RoaringBitmap>())));
369		/// assert_eq!(bitmaps.next(), None);
370		/// ```
371	0	pub fn bitmaps(&'_ self) -> BitmapIter<'_> {
372	0	BitmapIter::new(&self.map)
373	0	}
374
375		/// Construct a RoaringTreemap from an iterator of partition number and RoaringBitmap pairs.
376		/// The partition number is defined by the 32 most significant bits of the bit index.
377		/// Note that repeated partitions, if present, will replace previously set partitions.
378		///
379		/// # Examples
380		///
381		/// ```rust
382		/// use roaring::RoaringTreemap;
383		/// use core::iter::FromIterator;
384		///
385		/// let original = (0..6000).collect::<RoaringTreemap>();
386		/// let clone = RoaringTreemap::from_bitmaps(original.bitmaps().map(\|(p, b)\| (p, b.clone())));
387		///
388		/// assert_eq!(clone, original);
389		/// ```
390	0	pub fn from_bitmaps<I: IntoIterator<Item = (u32, RoaringBitmap)>>(iterator: I) -> Self {
391	0	RoaringTreemap { map: iterator.into_iter().collect() }
392	0	}
393		}
394
395		impl<'a> IntoIterator for &'a RoaringTreemap {
396		type Item = u64;
397		type IntoIter = Iter<'a>;
398
399	0	fn into_iter(self) -> Iter<'a> {
400	0	self.iter()
401	0	}
402		}
403
404		impl IntoIterator for RoaringTreemap {
405		type Item = u64;
406		type IntoIter = IntoIter;
407
408	0	fn into_iter(self) -> IntoIter {
409	0	IntoIter::new(self.map)
410	0	}
411		}
412
413		impl<const N: usize> From<[u64; N]> for RoaringTreemap {
414	0	fn from(arr: [u64; N]) -> Self {
415	0	RoaringTreemap::from_iter(arr)
416	0	} Unexecuted instantiation: <roaring::treemap::RoaringTreemap as core::convert::From<[u64; 9]>>::from Unexecuted instantiation: <roaring::treemap::RoaringTreemap as core::convert::From<[u64; _]>>::from
417		}
418
419		impl FromIterator<u64> for RoaringTreemap {
420	0	fn from_iter<I: IntoIterator<Item = u64>>(iterator: I) -> RoaringTreemap {
421	0	let mut rb = RoaringTreemap::new();
422	0	rb.extend(iterator);
423	0	rb
424	0	} Unexecuted instantiation: <roaring::treemap::RoaringTreemap as core::iter::traits::collect::FromIterator<u64>>::from_iter::<[u64; 9]> Unexecuted instantiation: <roaring::treemap::RoaringTreemap as core::iter::traits::collect::FromIterator<u64>>::from_iter::<_>
425		}
426
427		impl<'a> FromIterator<&'a u64> for RoaringTreemap {
428	0	fn from_iter<I: IntoIterator<Item = &'a u64>>(iterator: I) -> RoaringTreemap {
429	0	let mut rb = RoaringTreemap::new();
430	0	rb.extend(iterator);
431	0	rb
432	0	}
433		}
434
435		impl Extend<u64> for RoaringTreemap {
436	0	fn extend<I: IntoIterator<Item = u64>>(&mut self, iterator: I) {
437	0	for value in iterator {
438	0	self.insert(value);
439	0	}
440	0	} Unexecuted instantiation: <roaring::treemap::RoaringTreemap as core::iter::traits::collect::Extend<u64>>::extend::<[u64; 9]> Unexecuted instantiation: <roaring::treemap::RoaringTreemap as core::iter::traits::collect::Extend<u64>>::extend::<_>
441		}
442
443		impl<'a> Extend<&'a u64> for RoaringTreemap {
444	0	fn extend<I: IntoIterator<Item = &'a u64>>(&mut self, iterator: I) {
445	0	for value in iterator {
446	0	self.insert(*value);
447	0	}
448	0	}
449		}
450
451		impl RoaringTreemap {
452		/// Create the set from a sorted iterator. Values must be sorted and deduplicated.
453		///
454		/// The values of the iterator must be ordered and strictly greater than the greatest value
455		/// in the set. If a value in the iterator doesn't satisfy this requirement, it is not added
456		/// and the append operation is stopped.
457		///
458		/// Returns `Ok` with the requested `RoaringTreemap`, `Err` with the number of elements
459		/// we tried to append before an error occurred.
460		///
461		/// # Examples
462		///
463		/// ```rust
464		/// use roaring::RoaringTreemap;
465		///
466		/// let mut rb = RoaringTreemap::from_sorted_iter(0..10).unwrap();
467		///
468		/// assert!(rb.iter().eq(0..10));
469		/// ```
470	0	pub fn from_sorted_iter<I: IntoIterator<Item = u64>>(
471	0	iterator: I,
472	0	) -> Result<RoaringTreemap, NonSortedIntegers> {
473	0	let mut rt = RoaringTreemap::new();
474	0	rt.append(iterator).map(\|_\| rt)
475	0	}
476
477		/// Extend the set with a sorted iterator.
478		///
479		/// The values of the iterator must be ordered and strictly greater than the greatest value
480		/// in the set. If a value in the iterator doesn't satisfy this requirement, it is not added
481		/// and the append operation is stopped.
482		///
483		/// Returns `Ok` with the number of elements appended to the set, `Err` with
484		/// the number of elements we effectively appended before an error occurred.
485		///
486		/// # Examples
487		///
488		/// ```rust
489		/// use roaring::RoaringTreemap;
490		///
491		/// let mut rb = RoaringTreemap::new();
492		/// rb.append(0..10);
493		///
494		/// assert!(rb.iter().eq(0..10));
495		/// ```
496	0	pub fn append<I: IntoIterator<Item = u64>>(
497	0	&mut self,
498	0	iterator: I,
499	0	) -> Result<u64, NonSortedIntegers> {
500	0	let mut iterator = iterator.into_iter();
501	0	let mut prev = match (iterator.next(), self.max()) {
502	0	(None, _) => return Ok(0),
503	0	(Some(first), Some(max)) if first <= max => {
504	0	return Err(NonSortedIntegers { valid_until: 0 })
505		}
506	0	(Some(first), _) => first,
507		};
508
509		// It is now guaranteed that so long as the values of the iterator are
510		// monotonically increasing they must also be the greatest in the set.
511
512	0	self.push_unchecked(prev);
513
514	0	let mut count = 1;
515	0	for value in iterator {
516	0	if value <= prev {
517	0	return Err(NonSortedIntegers { valid_until: count });
518	0	} else {
519	0	self.push_unchecked(value);
520	0	prev = value;
521	0	count += 1;
522	0	}
523		}
524
525	0	Ok(count)
526	0	}
527		}
528
529		/// An iterator of `RoaringBitmap`s for `RoaringTreemap`.
530		#[derive(Clone)]
531		pub struct BitmapIter<'a> {
532		treemap: &'a BTreeMap<u32, RoaringBitmap>,
533		range: btree_map::Range<'a, u32, RoaringBitmap>,
534		latest_front_idx: Option<u32>,
535		latest_back_idx: Option<u32>,
536		}
537
538		impl<'a> BitmapIter<'a> {
539	0	fn new(treemap: &'a BTreeMap<u32, RoaringBitmap>) -> Self {
540	0	let range = treemap.range(..);
541	0	Self { treemap, range, latest_back_idx: None, latest_front_idx: None }
542	0	}
543
544	0	fn advance_to(&mut self, new_front_idx: u32) {
545	0	match self.latest_back_idx {
546	0	Some(latest_back_idx) => match self.latest_front_idx {
547	0	Some(last_idx) if last_idx >= new_front_idx => {}
548		_ => {
549		// if asked to advance to beyond the back iterator,
550		// update the self.range iterator to be empty
551	0	if new_front_idx >= latest_back_idx {
552	0	self.range = self.treemap.range(0..1);
553	0	self.range.next_back();
554	0	} else {
555	0	// otherwise shrink the remaining range from the front
556	0	self.range = self.treemap.range(new_front_idx..latest_back_idx);
557	0	}
558
559		// self.range = self.treemap.range(new_front_idx..latest_back_idx);
560		}
561		},
562	0	None => match self.latest_front_idx {
563	0	Some(latest_idx) if latest_idx >= new_front_idx => {}
564	0	_ => {
565	0	self.range = self.treemap.range(new_front_idx..);
566	0	}
567		},
568		}
569	0	}
570
571	0	fn advance_back_to(&mut self, new_back_idx: u32) {
572	0	match self.latest_front_idx {
573	0	Some(latest_front_idx) => match self.latest_back_idx {
574		// do nothing if asked to advance back to a higher index than the back is already at
575	0	Some(latest_back_idx) if latest_back_idx <= new_back_idx => {}
576		_ => {
577		// if asked to advance back to beyond the front iterator,
578		// update the self.range iterator to be empty
579	0	if new_back_idx <= latest_front_idx {
580	0	self.range = self.treemap.range(0..1);
581	0	self.range.next_back();
582	0	} else {
583	0	// otherwise shrink the remaining range from the back
584	0	self.range = self.treemap.range((latest_front_idx + 1)..new_back_idx);
585	0	}
586		}
587		},
588	0	None => match self.latest_back_idx {
589	0	Some(latest_back_idx) if latest_back_idx <= new_back_idx => {}
590	0	_ => {
591	0	self.range = self.treemap.range(..=new_back_idx);
592	0	}
593		},
594		}
595	0	}
596
597	0	fn remaining(&self) -> u64 {
598	0	let range = self.range.clone();
599	0	range.fold(0, \|acc, (_, bitmap)\| acc.add(bitmap.len()))
600	0	}
601		}
602
603		impl<'a> Iterator for BitmapIter<'a> {
604		type Item = (u32, &'a RoaringBitmap);
605
606	0	fn next(&mut self) -> Option<Self::Item> {
607	0	match self.range.next().map(\|(&p, b)\| (p, b)) {
608		None => {
609	0	self.latest_front_idx = None;
610	0	None
611		}
612	0	Some((next_idx, next_map)) => {
613	0	self.latest_front_idx = Some(next_idx);
614	0	Some((next_idx, next_map))
615		}
616		}
617	0	}
618
619	0	fn size_hint(&self) -> (usize, Option<usize>) {
620	0	self.range.size_hint()
621	0	}
622		}
623
624		impl FromIterator<(u32, RoaringBitmap)> for RoaringTreemap {
625	0	fn from_iter<I: IntoIterator<Item = (u32, RoaringBitmap)>>(iterator: I) -> RoaringTreemap {
626	0	Self::from_bitmaps(iterator)
627	0	}
628		}
629
630		impl DoubleEndedIterator for BitmapIter<'_> {
631	0	fn next_back(&mut self) -> Option<Self::Item> {
632	0	match self.range.next_back().map(\|(&p, b)\| (p, b)) {
633		None => {
634	0	self.latest_back_idx = None;
635	0	None
636		}
637	0	Some((next_back_idx, next_back_map)) => {
638	0	self.latest_back_idx = Some(next_back_idx);
639	0	Some((next_back_idx, next_back_map))
640		}
641		}
642	0	}
643		}