iddqd/id_ord_map/
iter.rs

1use super::{IdOrdItem, RefMut, tables::IdOrdMapTables};
2use crate::support::{
3    alloc::Global,
4    btree_table,
5    item_set::{ConsumingItemSet, ItemSet, ItemSlotsPtr},
6};
7use core::iter::FusedIterator;
8
9/// An iterator over the elements of an [`IdOrdMap`] by shared reference.
10///
11/// Created by [`IdOrdMap::iter`], and ordered by keys.
12///
13/// [`IdOrdMap`]: crate::IdOrdMap
14/// [`IdOrdMap::iter`]: crate::IdOrdMap::iter
15#[derive(Clone, Debug)]
16pub struct Iter<'a, T: IdOrdItem> {
17    items: &'a ItemSet<T, Global>,
18    iter: btree_table::Iter<'a>,
19}
20
21impl<'a, T: IdOrdItem> Iter<'a, T> {
22    pub(super) fn new(
23        items: &'a ItemSet<T, Global>,
24        tables: &'a IdOrdMapTables,
25    ) -> Self {
26        Self { items, iter: tables.key_to_item.iter() }
27    }
28}
29
30impl<'a, T: IdOrdItem> Iterator for Iter<'a, T> {
31    type Item = &'a T;
32
33    #[inline]
34    fn next(&mut self) -> Option<Self::Item> {
35        let index = self.iter.next()?;
36        Some(&self.items[index])
37    }
38
39    #[inline]
40    fn size_hint(&self) -> (usize, Option<usize>) {
41        self.iter.size_hint()
42    }
43}
44
45impl<T: IdOrdItem> ExactSizeIterator for Iter<'_, T> {
46    #[inline]
47    fn len(&self) -> usize {
48        self.iter.len()
49    }
50}
51
52// btree_set::Iter is a FusedIterator, so Iter is as well.
53impl<T: IdOrdItem> FusedIterator for Iter<'_, T> {}
54
55/// An iterator over the elements of a [`IdOrdMap`] by mutable reference.
56///
57/// This iterator returns [`RefMut`] instances.
58///
59/// Created by [`IdOrdMap::iter_mut`], and ordered by keys.
60///
61/// [`IdOrdMap`]: crate::IdOrdMap
62/// [`IdOrdMap::iter_mut`]: crate::IdOrdMap::iter_mut
63#[derive(Debug)]
64pub struct IterMut<'a, T: IdOrdItem> {
65    items: ItemSlotsPtr<'a, T>,
66    tables: &'a IdOrdMapTables,
67    iter: btree_table::Iter<'a>,
68}
69
70impl<'a, T: IdOrdItem> IterMut<'a, T> {
71    pub(super) fn new(
72        items: &'a mut ItemSet<T, Global>,
73        tables: &'a IdOrdMapTables,
74    ) -> Self {
75        Self {
76            items: ItemSlotsPtr::new(items.slots_mut()),
77            tables,
78            iter: tables.key_to_item.iter(),
79        }
80    }
81}
82
83impl<'a, T: IdOrdItem> Iterator for IterMut<'a, T> {
84    type Item = RefMut<'a, T>;
85
86    #[inline]
87    fn next(&mut self) -> Option<Self::Item> {
88        let index = self.iter.next()?;
89
90        // SAFETY: `get_mut` requires that we pass each `index` at most once
91        // for the lifetime of `self.items`. We do, because:
92        //
93        // * `self.iter` visits each entry of the B-tree once, and
94        // * no two entries hold the same index (the no-duplicate invariant in
95        //   the `btree_table` module docs).
96        //
97        // The user's `Ord` is not called at any point, since iteration is
98        // structural.
99        let item: &'a mut T = unsafe { self.items.get_mut(index) };
100
101        let hash = self.tables.make_hash(item);
102
103        Some(RefMut::new(self.tables.state().clone(), hash, item))
104    }
105
106    #[inline]
107    fn size_hint(&self) -> (usize, Option<usize>) {
108        self.iter.size_hint()
109    }
110}
111
112impl<'a, T: IdOrdItem> ExactSizeIterator for IterMut<'a, T> {
113    #[inline]
114    fn len(&self) -> usize {
115        self.iter.len()
116    }
117}
118
119impl<'a, T: IdOrdItem> FusedIterator for IterMut<'a, T> {}
120
121/// An iterator over the elements of a [`IdOrdMap`] by ownership.
122///
123/// Created by [`IdOrdMap::into_iter`], and ordered by keys.
124///
125/// [`IdOrdMap`]: crate::IdOrdMap
126/// [`IdOrdMap::into_iter`]: crate::IdOrdMap::into_iter
127#[derive(Debug)]
128pub struct IntoIter<T: IdOrdItem> {
129    items: ConsumingItemSet<T, Global>,
130    iter: btree_table::IntoIter,
131}
132
133impl<T: IdOrdItem> IntoIter<T> {
134    pub(super) fn new(
135        items: ItemSet<T, Global>,
136        tables: IdOrdMapTables,
137    ) -> Self {
138        Self {
139            items: items.into_consuming(),
140            iter: tables.key_to_item.into_iter(),
141        }
142    }
143}
144
145impl<T: IdOrdItem> Iterator for IntoIter<T> {
146    type Item = T;
147
148    #[inline]
149    fn next(&mut self) -> Option<Self::Item> {
150        let index = self.iter.next()?;
151        // We own `self.items` and the B-tree's indexes are never revisited, so
152        // we can take directly from the consuming view.
153        let next = self
154            .items
155            .take(index)
156            .unwrap_or_else(|| panic!("index {index} not found in items"));
157        Some(next)
158    }
159
160    #[inline]
161    fn size_hint(&self) -> (usize, Option<usize>) {
162        self.iter.size_hint()
163    }
164}
165
166impl<T: IdOrdItem> ExactSizeIterator for IntoIter<T> {
167    #[inline]
168    fn len(&self) -> usize {
169        self.iter.len()
170    }
171}
172
173// btree_map::IntoIter is a FusedIterator, so IntoIter is as well.
174impl<T: IdOrdItem> FusedIterator for IntoIter<T> {}
iddqd/id_ord_map/iter.rs

iddqd/id_ord_map/
iter.rs
