/rust/registry/src/index.crates.io-1949cf8c6b5b557f/roaring-0.11.4/src/bitmap/container.rs

Source
use core::fmt;
use core::ops::{
    BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, RangeInclusive, Sub, SubAssign,
};

use super::store::{self, ArrayStore, Interval, IntervalStore, Store, BITMAP_BYTES};
use super::util;

pub const ARRAY_LIMIT: u64 = 4096;
#[cfg(test)]
pub const RUN_MAX_SIZE: u64 = 2048;

#[cfg(not(feature = "std"))]
use alloc::vec::Vec;

#[derive(PartialEq, Eq, Clone)]
pub(crate) struct Container {
    pub key: u16,
    pub store: Store,
}

#[derive(Clone)]
pub(crate) struct Iter<'a> {
    pub key: u16,
    inner: store::Iter<'a>,
}

impl Container {
    pub fn new(key: u16) -> Container {
        Container { key, store: Store::new() }
    }

    pub fn new_with_range(key: u16, range: RangeInclusive<u16>) -> Container {
        if range.len() <= 2 {
            let mut array = ArrayStore::new();
            array.insert_range(range);
            Self { key, store: Store::Array(array) }
        } else {
            Self {
                key,
                store: Store::Run(IntervalStore::new_with_range(
                    // This is ok, since range must be non empty
                    Interval::new_unchecked(*range.start(), *range.end()),
                )),
            }
        }
    }

    pub fn full(key: u16) -> Container {
        Container { key, store: Store::full() }
    }

    pub fn from_lsb0_bytes(key: u16, bytes: &[u8], byte_offset: usize) -> Option<Self> {
        Some(Container { key, store: Store::from_lsb0_bytes(bytes, byte_offset)? })
    }
}

impl Container {
    pub fn len(&self) -> u64 {
        self.store.len()
    }

    pub fn is_empty(&self) -> bool {
        self.store.is_empty()
    }

    #[inline]
    pub fn insert(&mut self, index: u16) -> bool {
        if self.store.insert(index) {
            self.ensure_correct_store();
            true
        } else {
            false
        }
    }

    pub fn insert_range(&mut self, range: RangeInclusive<u16>) -> u64 {
        if range.is_empty() {
            return 0;
        }
        match &self.store {
            Store::Bitmap(bitmap) => {
                let added_amount = range.len() as u64
                    - bitmap.intersection_len_interval(&Interval::new_unchecked(
                        *range.start(),
                        *range.end(),
                    ));
                let union_cardinality = bitmap.len() + added_amount;
                if union_cardinality == 1 << 16 {
                    self.store = Store::Run(IntervalStore::full());
                    added_amount
                } else {
                    self.store.insert_range(range)
                }
            }
            Store::Array(array) => {
                let added_amount = range.len() as u64
                    - array.intersection_len_interval(&Interval::new_unchecked(
                        *range.start(),
                        *range.end(),
                    ));
                let union_cardinality = array.len() + added_amount;
                if union_cardinality == 1 << 16 {
                    self.store = Store::Run(IntervalStore::full());
                    added_amount
                } else if union_cardinality <= ARRAY_LIMIT {
                    self.store.insert_range(range)
                } else {
                    self.store = self.store.to_bitmap();
                    self.store.insert_range(range)
                }
            }
            Store::Run(_) => self.store.insert_range(range),
        }
    }

    /// Pushes `index` at the end of the container only if `index` is the new max.
    ///
    /// Returns whether the `index` was effectively pushed.
    pub fn push(&mut self, index: u16) -> bool {
        if self.store.push(index) {
            self.ensure_correct_store();
            true
        } else {
            false
        }
    }

    ///
    /// Pushes `index` at the end of the container.
    /// It is up to the caller to have validated index > self.max()
    ///
    /// # Panics
    ///
    /// If debug_assertions enabled and index is > self.max()
    pub(crate) fn push_unchecked(&mut self, index: u16) {
        self.store.push_unchecked(index);
        self.ensure_correct_store();
    }

    pub fn remove(&mut self, index: u16) -> bool {
        if self.store.remove(index) {
            self.ensure_correct_store();
            true
        } else {
            false
        }
    }

    pub fn remove_range(&mut self, range: RangeInclusive<u16>) -> u64 {
        let result = self.store.remove_range(range);
        self.ensure_correct_store();
        result
    }

    pub fn remove_smallest(&mut self, n: u64) {
        match &self.store {
            Store::Bitmap(bits) => {
                if bits.len() - n <= ARRAY_LIMIT {
                    let mut replace_array = Vec::with_capacity((bits.len() - n) as usize);
                    replace_array.extend(bits.iter().skip(n as usize));
                    self.store = Store::Array(store::ArrayStore::from_vec_unchecked(replace_array));
                } else {
                    self.store.remove_smallest(n)
                }
            }
            Store::Array(_) => self.store.remove_smallest(n),
            Store::Run(_) => self.store.remove_smallest(n),
        };
    }

    pub fn remove_biggest(&mut self, n: u64) {
        match &self.store {
            Store::Bitmap(bits) => {
                if bits.len() - n <= ARRAY_LIMIT {
                    let mut replace_array = Vec::with_capacity((bits.len() - n) as usize);
                    replace_array.extend(bits.iter().take((bits.len() - n) as usize));
                    self.store = Store::Array(store::ArrayStore::from_vec_unchecked(replace_array));
                } else {
                    self.store.remove_biggest(n)
                }
            }
            Store::Array(_) => self.store.remove_biggest(n),
            Store::Run(_) => self.store.remove_biggest(n),
        };
    }

    pub fn contains(&self, index: u16) -> bool {
        self.store.contains(index)
    }

    pub fn contains_range(&self, range: RangeInclusive<u16>) -> bool {
        self.store.contains_range(range)
    }

    pub fn is_full(&self) -> bool {
        self.store.is_full()
    }

    pub fn is_disjoint(&self, other: &Self) -> bool {
        self.store.is_disjoint(&other.store)
    }

    pub fn is_subset(&self, other: &Self) -> bool {
        self.len() <= other.len() && self.store.is_subset(&other.store)
    }

    pub fn intersection_len(&self, other: &Self) -> u64 {
        self.store.intersection_len(&other.store)
    }

    pub fn min(&self) -> Option<u16> {
        self.store.min()
    }

    #[inline]
    pub fn max(&self) -> Option<u16> {
        self.store.max()
    }

    pub fn rank(&self, index: u16) -> u64 {
        self.store.rank(index)
    }

    pub(crate) fn ensure_correct_store(&mut self) -> bool {
        let new_store = match &self.store {
            Store::Bitmap(ref bits) if bits.len() <= ARRAY_LIMIT => {
                Store::Array(bits.to_array_store()).into()
            }
            Store::Array(ref vec) if vec.len() > ARRAY_LIMIT => {
                Store::Bitmap(vec.to_bitmap_store()).into()
            }
            _ => None,
        };
        if let Some(new_store) = new_store {
            self.store = new_store;
            true
        } else {
            false
        }
    }

    pub fn optimize(&mut self) -> bool {
        match &mut self.store {
            Store::Bitmap(_) => {
                let num_runs = self.store.count_runs();
                let size_as_run = IntervalStore::serialized_byte_size(num_runs);
                if BITMAP_BYTES <= size_as_run {
                    return false;
                }
                self.store = self.store.to_run();
                true
            }
            Store::Array(array) => {
                let size_as_array = array.byte_size();
                let num_runs = self.store.count_runs();
                let size_as_run = IntervalStore::serialized_byte_size(num_runs);
                if size_as_array <= size_as_run {
                    return false;
                }
                self.store = self.store.to_run();
                true
            }
            Store::Run(runs) => {
                let size_as_run = runs.byte_size();
                let card = runs.len();
                let size_as_array = ArrayStore::serialized_byte_size(card);
                let min_size_non_run = size_as_array.min(BITMAP_BYTES);
                if size_as_run <= min_size_non_run {
                    return false;
                }
                if card <= ARRAY_LIMIT {
                    self.store = Store::Array(runs.to_array());
                    return true;
                }
                self.store = Store::Bitmap(runs.to_bitmap());
                true
            }
        }
    }

    pub fn remove_run_compression(&mut self) -> bool {
        match &mut self.store {
            Store::Bitmap(_) | Store::Array(_) => false,
            Store::Run(runs) => {
                let card = runs.len();
                if card <= ARRAY_LIMIT {
                    self.store = Store::Array(runs.to_array());
                } else {
                    self.store = Store::Bitmap(runs.to_bitmap());
                }
                true
            }
        }
    }
}

impl BitOr<&Container> for &Container {
    type Output = Container;

    fn bitor(self, rhs: &Container) -> Container {
        let store = BitOr::bitor(&self.store, &rhs.store);
        let mut container = Container { key: self.key, store };
        container.ensure_correct_store();
        container
    }
}

impl BitOrAssign<Container> for Container {
    fn bitor_assign(&mut self, rhs: Container) {
        BitOrAssign::bitor_assign(&mut self.store, rhs.store);
        self.ensure_correct_store();
    }
}

impl BitOrAssign<&Container> for Container {
    fn bitor_assign(&mut self, rhs: &Container) {
        BitOrAssign::bitor_assign(&mut self.store, &rhs.store);
        self.ensure_correct_store();
    }
}

impl BitAnd<&Container> for &Container {
    type Output = Container;

    fn bitand(self, rhs: &Container) -> Container {
        let store = BitAnd::bitand(&self.store, &rhs.store);
        let mut container = Container { key: self.key, store };
        container.ensure_correct_store();
        container
    }
}

impl BitAndAssign<Container> for Container {
    fn bitand_assign(&mut self, rhs: Container) {
        BitAndAssign::bitand_assign(&mut self.store, rhs.store);
        self.ensure_correct_store();
    }
}

impl BitAndAssign<&Container> for Container {
    fn bitand_assign(&mut self, rhs: &Container) {
        BitAndAssign::bitand_assign(&mut self.store, &rhs.store);
        self.ensure_correct_store();
    }
}

impl Sub<&Container> for &Container {
    type Output = Container;

    fn sub(self, rhs: &Container) -> Container {
        let store = Sub::sub(&self.store, &rhs.store);
        let mut container = Container { key: self.key, store };
        container.ensure_correct_store();
        container
    }
}

impl SubAssign<&Container> for Container {
    fn sub_assign(&mut self, rhs: &Container) {
        SubAssign::sub_assign(&mut self.store, &rhs.store);
        self.ensure_correct_store();
    }
}

impl BitXor<&Container> for &Container {
    type Output = Container;

    fn bitxor(self, rhs: &Container) -> Container {
        let store = BitXor::bitxor(&self.store, &rhs.store);
        let mut container = Container { key: self.key, store };
        container.ensure_correct_store();
        container
    }
}

impl BitXorAssign<Container> for Container {
    fn bitxor_assign(&mut self, rhs: Container) {
        BitXorAssign::bitxor_assign(&mut self.store, rhs.store);
        self.ensure_correct_store();
    }
}

impl BitXorAssign<&Container> for Container {
    fn bitxor_assign(&mut self, rhs: &Container) {
        BitXorAssign::bitxor_assign(&mut self.store, &rhs.store);
        self.ensure_correct_store();
    }
}

impl<'a> IntoIterator for &'a Container {
    type Item = u32;
    type IntoIter = Iter<'a>;

    fn into_iter(self) -> Iter<'a> {
        let store: &Store = &self.store;
        Iter { key: self.key, inner: store.into_iter() }
    }
}

impl IntoIterator for Container {
    type Item = u32;
    type IntoIter = Iter<'static>;

    fn into_iter(self) -> Iter<'static> {
        Iter { key: self.key, inner: self.store.into_iter() }
    }
}

impl Iterator for Iter<'_> {
    type Item = u32;
    fn next(&mut self) -> Option<u32> {
        self.inner.next().map(|i| util::join(self.key, i))
    }

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

    fn count(self) -> usize
    where
        Self: Sized,
    {
        self.inner.count()
    }

    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        self.inner.nth(n).map(|i| util::join(self.key, i))
    }
}

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

impl ExactSizeIterator for Iter<'_> {}

impl Iter<'_> {
    pub(crate) fn peek(&self) -> Option<u32> {
        self.inner.peek().map(|i| util::join(self.key, i))
    }

    pub(crate) fn peek_back(&self) -> Option<u32> {
        self.inner.peek_back().map(|i| util::join(self.key, i))
    }

    pub(crate) fn advance_to(&mut self, index: u16) {
        self.inner.advance_to(index);
    }

    pub(crate) fn advance_back_to(&mut self, index: u16) {
        self.inner.advance_back_to(index);
    }

    /// Returns the range of consecutive set bits from the current position to the end of the current run
    ///
    /// After this call, the iterator will be positioned at the first item after the returned range.
    /// Returns `None` if the iterator is exhausted.
    pub(crate) fn next_range(&mut self) -> Option<RangeInclusive<u32>> {
        self.inner
            .next_range()
            .map(|r| util::join(self.key, *r.start())..=util::join(self.key, *r.end()))
    }

    /// Returns the range of consecutive set bits from the start of the current run to the current back position
    ///
    /// After this call, the back of the iterator will be positioned at the last item before the returned range.
    /// Returns `None` if the iterator is exhausted.
    pub(crate) fn next_range_back(&mut self) -> Option<RangeInclusive<u32>> {
        self.inner
            .next_range_back()
            .map(|r| util::join(self.key, *r.start())..=util::join(self.key, *r.end()))
    }
}

impl fmt::Debug for Container {
    fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
        format!("Container<{:?} @ {:?}>", self.len(), self.key).fmt(formatter)
    }
}

Coverage Report

Created: 2026-08-14 08:14

Line	Count	Source
1		use core::fmt;
2		use core::ops::{
3		BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, RangeInclusive, Sub, SubAssign,
4		};
5
6		use super::store::{self, ArrayStore, Interval, IntervalStore, Store, BITMAP_BYTES};
7		use super::util;
8
9		pub const ARRAY_LIMIT: u64 = 4096;
10		#[cfg(test)]
11		pub const RUN_MAX_SIZE: u64 = 2048;
12
13		#[cfg(not(feature = "std"))]
14		use alloc::vec::Vec;
15
16		#[derive(PartialEq, Eq, Clone)]
17		pub(crate) struct Container {
18		pub key: u16,
19		pub store: Store,
20		}
21
22		#[derive(Clone)]
23		pub(crate) struct Iter<'a> {
24		pub key: u16,
25		inner: store::Iter<'a>,
26		}
27
28		impl Container {
29	0	pub fn new(key: u16) -> Container {
30	0	Container { key, store: Store::new() }
31	0	}
32
33	0	pub fn new_with_range(key: u16, range: RangeInclusive<u16>) -> Container {
34	0	if range.len() <= 2 {
35	0	let mut array = ArrayStore::new();
36	0	array.insert_range(range);
37	0	Self { key, store: Store::Array(array) }
38		} else {
39	0	Self {
40	0	key,
41	0	store: Store::Run(IntervalStore::new_with_range(
42	0	// This is ok, since range must be non empty
43	0	Interval::new_unchecked(range.start(), range.end()),
44	0	)),
45	0	}
46		}
47	0	}
48
49	0	pub fn full(key: u16) -> Container {
50	0	Container { key, store: Store::full() }
51	0	}
52
53	0	pub fn from_lsb0_bytes(key: u16, bytes: &[u8], byte_offset: usize) -> Option<Self> {
54	0	Some(Container { key, store: Store::from_lsb0_bytes(bytes, byte_offset)? })
55	0	}
56		}
57
58		impl Container {
59	0	pub fn len(&self) -> u64 {
60	0	self.store.len()
61	0	}
62
63	0	pub fn is_empty(&self) -> bool {
64	0	self.store.is_empty()
65	0	}
66
67		#[inline]
68	0	pub fn insert(&mut self, index: u16) -> bool {
69	0	if self.store.insert(index) {
70	0	self.ensure_correct_store();
71	0	true
72		} else {
73	0	false
74		}
75	0	}
76
77	0	pub fn insert_range(&mut self, range: RangeInclusive<u16>) -> u64 {
78	0	if range.is_empty() {
79	0	return 0;
80	0	}
81	0	match &self.store {
82	0	Store::Bitmap(bitmap) => {
83	0	let added_amount = range.len() as u64
84	0	- bitmap.intersection_len_interval(&Interval::new_unchecked(
85	0	*range.start(),
86	0	*range.end(),
87	0	));
88	0	let union_cardinality = bitmap.len() + added_amount;
89	0	if union_cardinality == 1 << 16 {
90	0	self.store = Store::Run(IntervalStore::full());
91	0	added_amount
92		} else {
93	0	self.store.insert_range(range)
94		}
95		}
96	0	Store::Array(array) => {
97	0	let added_amount = range.len() as u64
98	0	- array.intersection_len_interval(&Interval::new_unchecked(
99	0	*range.start(),
100	0	*range.end(),
101	0	));
102	0	let union_cardinality = array.len() + added_amount;
103	0	if union_cardinality == 1 << 16 {
104	0	self.store = Store::Run(IntervalStore::full());
105	0	added_amount
106	0	} else if union_cardinality <= ARRAY_LIMIT {
107	0	self.store.insert_range(range)
108		} else {
109	0	self.store = self.store.to_bitmap();
110	0	self.store.insert_range(range)
111		}
112		}
113	0	Store::Run(_) => self.store.insert_range(range),
114		}
115	0	}
116
117		/// Pushes `index` at the end of the container only if `index` is the new max.
118		///
119		/// Returns whether the `index` was effectively pushed.
120	0	pub fn push(&mut self, index: u16) -> bool {
121	0	if self.store.push(index) {
122	0	self.ensure_correct_store();
123	0	true
124		} else {
125	0	false
126		}
127	0	}
128
129		///
130		/// Pushes `index` at the end of the container.
131		/// It is up to the caller to have validated index > self.max()
132		///
133		/// # Panics
134		///
135		/// If debug_assertions enabled and index is > self.max()
136	0	pub(crate) fn push_unchecked(&mut self, index: u16) {
137	0	self.store.push_unchecked(index);
138	0	self.ensure_correct_store();
139	0	}
140
141	0	pub fn remove(&mut self, index: u16) -> bool {
142	0	if self.store.remove(index) {
143	0	self.ensure_correct_store();
144	0	true
145		} else {
146	0	false
147		}
148	0	}
149
150	0	pub fn remove_range(&mut self, range: RangeInclusive<u16>) -> u64 {
151	0	let result = self.store.remove_range(range);
152	0	self.ensure_correct_store();
153	0	result
154	0	}
155
156	0	pub fn remove_smallest(&mut self, n: u64) {
157	0	match &self.store {
158	0	Store::Bitmap(bits) => {
159	0	if bits.len() - n <= ARRAY_LIMIT {
160	0	let mut replace_array = Vec::with_capacity((bits.len() - n) as usize);
161	0	replace_array.extend(bits.iter().skip(n as usize));
162	0	self.store = Store::Array(store::ArrayStore::from_vec_unchecked(replace_array));
163	0	} else {
164	0	self.store.remove_smallest(n)
165		}
166		}
167	0	Store::Array(_) => self.store.remove_smallest(n),
168	0	Store::Run(_) => self.store.remove_smallest(n),
169		};
170	0	}
171
172	0	pub fn remove_biggest(&mut self, n: u64) {
173	0	match &self.store {
174	0	Store::Bitmap(bits) => {
175	0	if bits.len() - n <= ARRAY_LIMIT {
176	0	let mut replace_array = Vec::with_capacity((bits.len() - n) as usize);
177	0	replace_array.extend(bits.iter().take((bits.len() - n) as usize));
178	0	self.store = Store::Array(store::ArrayStore::from_vec_unchecked(replace_array));
179	0	} else {
180	0	self.store.remove_biggest(n)
181		}
182		}
183	0	Store::Array(_) => self.store.remove_biggest(n),
184	0	Store::Run(_) => self.store.remove_biggest(n),
185		};
186	0	}
187
188	0	pub fn contains(&self, index: u16) -> bool {
189	0	self.store.contains(index)
190	0	}
191
192	0	pub fn contains_range(&self, range: RangeInclusive<u16>) -> bool {
193	0	self.store.contains_range(range)
194	0	}
195
196	0	pub fn is_full(&self) -> bool {
197	0	self.store.is_full()
198	0	}
199
200	0	pub fn is_disjoint(&self, other: &Self) -> bool {
201	0	self.store.is_disjoint(&other.store)
202	0	}
203
204	0	pub fn is_subset(&self, other: &Self) -> bool {
205	0	self.len() <= other.len() && self.store.is_subset(&other.store)
206	0	}
207
208	0	pub fn intersection_len(&self, other: &Self) -> u64 {
209	0	self.store.intersection_len(&other.store)
210	0	}
211
212	0	pub fn min(&self) -> Option<u16> {
213	0	self.store.min()
214	0	}
215
216		#[inline]
217	0	pub fn max(&self) -> Option<u16> {
218	0	self.store.max()
219	0	}
220
221	0	pub fn rank(&self, index: u16) -> u64 {
222	0	self.store.rank(index)
223	0	}
224
225	0	pub(crate) fn ensure_correct_store(&mut self) -> bool {
226	0	let new_store = match &self.store {
227	0	Store::Bitmap(ref bits) if bits.len() <= ARRAY_LIMIT => {
228	0	Store::Array(bits.to_array_store()).into()
229		}
230	0	Store::Array(ref vec) if vec.len() > ARRAY_LIMIT => {
231	0	Store::Bitmap(vec.to_bitmap_store()).into()
232		}
233	0	_ => None,
234		};
235	0	if let Some(new_store) = new_store {
236	0	self.store = new_store;
237	0	true
238		} else {
239	0	false
240		}
241	0	}
242
243	0	pub fn optimize(&mut self) -> bool {
244	0	match &mut self.store {
245		Store::Bitmap(_) => {
246	0	let num_runs = self.store.count_runs();
247	0	let size_as_run = IntervalStore::serialized_byte_size(num_runs);
248	0	if BITMAP_BYTES <= size_as_run {
249	0	return false;
250	0	}
251	0	self.store = self.store.to_run();
252	0	true
253		}
254	0	Store::Array(array) => {
255	0	let size_as_array = array.byte_size();
256	0	let num_runs = self.store.count_runs();
257	0	let size_as_run = IntervalStore::serialized_byte_size(num_runs);
258	0	if size_as_array <= size_as_run {
259	0	return false;
260	0	}
261	0	self.store = self.store.to_run();
262	0	true
263		}
264	0	Store::Run(runs) => {
265	0	let size_as_run = runs.byte_size();
266	0	let card = runs.len();
267	0	let size_as_array = ArrayStore::serialized_byte_size(card);
268	0	let min_size_non_run = size_as_array.min(BITMAP_BYTES);
269	0	if size_as_run <= min_size_non_run {
270	0	return false;
271	0	}
272	0	if card <= ARRAY_LIMIT {
273	0	self.store = Store::Array(runs.to_array());
274	0	return true;
275	0	}
276	0	self.store = Store::Bitmap(runs.to_bitmap());
277	0	true
278		}
279		}
280	0	}
281
282	0	pub fn remove_run_compression(&mut self) -> bool {
283	0	match &mut self.store {
284	0	Store::Bitmap(_) \| Store::Array(_) => false,
285	0	Store::Run(runs) => {
286	0	let card = runs.len();
287	0	if card <= ARRAY_LIMIT {
288	0	self.store = Store::Array(runs.to_array());
289	0	} else {
290	0	self.store = Store::Bitmap(runs.to_bitmap());
291	0	}
292	0	true
293		}
294		}
295	0	}
296		}
297
298		impl BitOr<&Container> for &Container {
299		type Output = Container;
300
301	0	fn bitor(self, rhs: &Container) -> Container {
302	0	let store = BitOr::bitor(&self.store, &rhs.store);
303	0	let mut container = Container { key: self.key, store };
304	0	container.ensure_correct_store();
305	0	container
306	0	}
307		}
308
309		impl BitOrAssign<Container> for Container {
310	0	fn bitor_assign(&mut self, rhs: Container) {
311	0	BitOrAssign::bitor_assign(&mut self.store, rhs.store);
312	0	self.ensure_correct_store();
313	0	}
314		}
315
316		impl BitOrAssign<&Container> for Container {
317	0	fn bitor_assign(&mut self, rhs: &Container) {
318	0	BitOrAssign::bitor_assign(&mut self.store, &rhs.store);
319	0	self.ensure_correct_store();
320	0	}
321		}
322
323		impl BitAnd<&Container> for &Container {
324		type Output = Container;
325
326	0	fn bitand(self, rhs: &Container) -> Container {
327	0	let store = BitAnd::bitand(&self.store, &rhs.store);
328	0	let mut container = Container { key: self.key, store };
329	0	container.ensure_correct_store();
330	0	container
331	0	}
332		}
333
334		impl BitAndAssign<Container> for Container {
335	0	fn bitand_assign(&mut self, rhs: Container) {
336	0	BitAndAssign::bitand_assign(&mut self.store, rhs.store);
337	0	self.ensure_correct_store();
338	0	}
339		}
340
341		impl BitAndAssign<&Container> for Container {
342	0	fn bitand_assign(&mut self, rhs: &Container) {
343	0	BitAndAssign::bitand_assign(&mut self.store, &rhs.store);
344	0	self.ensure_correct_store();
345	0	}
346		}
347
348		impl Sub<&Container> for &Container {
349		type Output = Container;
350
351	0	fn sub(self, rhs: &Container) -> Container {
352	0	let store = Sub::sub(&self.store, &rhs.store);
353	0	let mut container = Container { key: self.key, store };
354	0	container.ensure_correct_store();
355	0	container
356	0	}
357		}
358
359		impl SubAssign<&Container> for Container {
360	0	fn sub_assign(&mut self, rhs: &Container) {
361	0	SubAssign::sub_assign(&mut self.store, &rhs.store);
362	0	self.ensure_correct_store();
363	0	}
364		}
365
366		impl BitXor<&Container> for &Container {
367		type Output = Container;
368
369	0	fn bitxor(self, rhs: &Container) -> Container {
370	0	let store = BitXor::bitxor(&self.store, &rhs.store);
371	0	let mut container = Container { key: self.key, store };
372	0	container.ensure_correct_store();
373	0	container
374	0	}
375		}
376
377		impl BitXorAssign<Container> for Container {
378	0	fn bitxor_assign(&mut self, rhs: Container) {
379	0	BitXorAssign::bitxor_assign(&mut self.store, rhs.store);
380	0	self.ensure_correct_store();
381	0	}
382		}
383
384		impl BitXorAssign<&Container> for Container {
385	0	fn bitxor_assign(&mut self, rhs: &Container) {
386	0	BitXorAssign::bitxor_assign(&mut self.store, &rhs.store);
387	0	self.ensure_correct_store();
388	0	}
389		}
390
391		impl<'a> IntoIterator for &'a Container {
392		type Item = u32;
393		type IntoIter = Iter<'a>;
394
395	0	fn into_iter(self) -> Iter<'a> {
396	0	let store: &Store = &self.store;
397	0	Iter { key: self.key, inner: store.into_iter() }
398	0	}
399		}
400
401		impl IntoIterator for Container {
402		type Item = u32;
403		type IntoIter = Iter<'static>;
404
405	0	fn into_iter(self) -> Iter<'static> {
406	0	Iter { key: self.key, inner: self.store.into_iter() }
407	0	}
408		}
409
410		impl Iterator for Iter<'_> {
411		type Item = u32;
412	0	fn next(&mut self) -> Option<u32> {
413	0	self.inner.next().map(\|i\| util::join(self.key, i))
414	0	}
415
416	0	fn size_hint(&self) -> (usize, Option<usize>) {
417	0	self.inner.size_hint()
418	0	}
419
420	0	fn count(self) -> usize
421	0	where
422	0	Self: Sized,
423		{
424	0	self.inner.count()
425	0	}
426
427	0	fn nth(&mut self, n: usize) -> Option<Self::Item> {
428	0	self.inner.nth(n).map(\|i\| util::join(self.key, i))
429	0	}
430		}
431
432		impl DoubleEndedIterator for Iter<'_> {
433	0	fn next_back(&mut self) -> Option<Self::Item> {
434	0	self.inner.next_back().map(\|i\| util::join(self.key, i))
435	0	}
436		}
437
438		impl ExactSizeIterator for Iter<'_> {}
439
440		impl Iter<'_> {
441	0	pub(crate) fn peek(&self) -> Option<u32> {
442	0	self.inner.peek().map(\|i\| util::join(self.key, i))
443	0	}
444
445	0	pub(crate) fn peek_back(&self) -> Option<u32> {
446	0	self.inner.peek_back().map(\|i\| util::join(self.key, i))
447	0	}
448
449	0	pub(crate) fn advance_to(&mut self, index: u16) {
450	0	self.inner.advance_to(index);
451	0	}
452
453	0	pub(crate) fn advance_back_to(&mut self, index: u16) {
454	0	self.inner.advance_back_to(index);
455	0	}
456
457		/// Returns the range of consecutive set bits from the current position to the end of the current run
458		///
459		/// After this call, the iterator will be positioned at the first item after the returned range.
460		/// Returns `None` if the iterator is exhausted.
461	0	pub(crate) fn next_range(&mut self) -> Option<RangeInclusive<u32>> {
462	0	self.inner
463	0	.next_range()
464	0	.map(\|r\| util::join(self.key, r.start())..=util::join(self.key, r.end()))
465	0	}
466
467		/// Returns the range of consecutive set bits from the start of the current run to the current back position
468		///
469		/// After this call, the back of the iterator will be positioned at the last item before the returned range.
470		/// Returns `None` if the iterator is exhausted.
471	0	pub(crate) fn next_range_back(&mut self) -> Option<RangeInclusive<u32>> {
472	0	self.inner
473	0	.next_range_back()
474	0	.map(\|r\| util::join(self.key, r.start())..=util::join(self.key, r.end()))
475	0	}
476		}
477
478		impl fmt::Debug for Container {
479	0	fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
480	0	format!("Container<{:?} @ {:?}>", self.len(), self.key).fmt(formatter)
481	0	}
482		}