/rust/registry/src/index.crates.io-1949cf8c6b5b557f/roaring-0.11.2/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};

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() }
}

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`.
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`.
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: 2025-11-28 06:44

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