const_lru/iters/
iter_key_order.rs

1use num_traits::{PrimInt, Unsigned};
2
3use crate::ConstLru;
4
5/// Iterates through the keys and values of the `ConstLru` in the keys' sorted order
6///
7/// Does not change the LRU order of the elements.
8pub struct IterKeyOrder<'a, K, V, const CAP: usize, I: PrimInt + Unsigned> {
9    /// from_smallest_bsi == from_largest_bsi means ended
10    from_smallest_bsi: I,
11    from_largest_bsi: I,
12    const_lru: &'a ConstLru<K, V, CAP, I>,
13}
14
15impl<'a, K, V, const CAP: usize, I: PrimInt + Unsigned> IterKeyOrder<'a, K, V, CAP, I> {
16    pub fn new(const_lru: &'a ConstLru<K, V, CAP, I>) -> Self {
17        Self {
18            from_smallest_bsi: I::zero(),
19            from_largest_bsi: const_lru.len(),
20            const_lru,
21        }
22    }
23
24    /// Assumes bs_i is in bounds
25    /// returns const_lru.bs_index[bs_i]
26    fn get_index(&self, bs_i: I) -> I {
27        self.const_lru.bs_index[bs_i.to_usize().unwrap()]
28    }
29
30    /// Assumes bs_i is in bounds
31    fn get_entry(&mut self, bs_i: I) -> (&'a K, &'a V) {
32        let i = self.get_index(bs_i).to_usize().unwrap();
33        let key = unsafe { self.const_lru.keys[i].assume_init_ref() };
34        let val = unsafe { self.const_lru.values[i].assume_init_ref() };
35        (key, val)
36    }
37
38    fn has_ended(&self) -> bool {
39        self.from_smallest_bsi == self.from_largest_bsi
40    }
41}
42
43impl<'a, K, V, const CAP: usize, I: PrimInt + Unsigned> Iterator
44    for IterKeyOrder<'a, K, V, CAP, I>
45{
46    type Item = (&'a K, &'a V);
47
48    fn next(&mut self) -> Option<Self::Item> {
49        if self.has_ended() {
50            return None;
51        }
52        // consume then increment
53        let res = self.get_entry(self.from_smallest_bsi);
54        self.from_smallest_bsi = self.from_smallest_bsi + I::one();
55        Some(res)
56    }
57
58    fn size_hint(&self) -> (usize, Option<usize>) {
59        let l = (self.from_largest_bsi - self.from_smallest_bsi)
60            .to_usize()
61            .unwrap();
62        (l, Some(l))
63    }
64}
65
66// TODO: look into https://doc.rust-lang.org/std/iter/trait.TrustedLen.html when it lands in stable
67impl<'a, K, V, const CAP: usize, I: PrimInt + Unsigned> ExactSizeIterator
68    for IterKeyOrder<'a, K, V, CAP, I>
69{
70}
71
72impl<'a, K, V, const CAP: usize, I: PrimInt + Unsigned> DoubleEndedIterator
73    for IterKeyOrder<'a, K, V, CAP, I>
74{
75    fn next_back(&mut self) -> Option<Self::Item> {
76        if self.has_ended() {
77            return None;
78        }
79        // decrement then consume
80        self.from_largest_bsi = self.from_largest_bsi - I::one();
81        let res = self.get_entry(self.from_largest_bsi);
82        Some(res)
83    }
84}
85
86/// Iterator that also returns the index of the current element
87///
88/// Used for internal implementation, currently only used to impl clone()
89pub struct IterIndexed<'a, K, V, const CAP: usize, I: PrimInt + Unsigned>(
90    IterKeyOrder<'a, K, V, CAP, I>,
91);
92
93impl<'a, K, V, const CAP: usize, I: PrimInt + Unsigned> IterIndexed<'a, K, V, CAP, I> {
94    pub fn new(const_lru: &'a ConstLru<K, V, CAP, I>) -> Self {
95        Self(IterKeyOrder::new(const_lru))
96    }
97}
98
99impl<'a, K, V, const CAP: usize, I: PrimInt + Unsigned> Iterator for IterIndexed<'a, K, V, CAP, I> {
100    type Item = (I, &'a K, &'a V);
101
102    fn next(&mut self) -> Option<Self::Item> {
103        if self.0.has_ended() {
104            return None;
105        }
106        // consume then increment
107        // next() modifies from_smallest_bsi, so read index out first
108        let i = self.0.get_index(self.0.from_smallest_bsi);
109        let (k, v) = self.0.next().unwrap();
110        Some((i, k, v))
111    }
112
113    // TODO: look into https://doc.rust-lang.org/std/iter/trait.TrustedLen.html when it lands in stable
114    fn size_hint(&self) -> (usize, Option<usize>) {
115        self.0.size_hint()
116    }
117}
118
119// TODO: look into https://doc.rust-lang.org/std/iter/trait.TrustedLen.html when it lands in stable
120impl<'a, K, V, const CAP: usize, I: PrimInt + Unsigned> ExactSizeIterator
121    for IterIndexed<'a, K, V, CAP, I>
122{
123}
124
125impl<'a, K, V, const CAP: usize, I: PrimInt + Unsigned> DoubleEndedIterator
126    for IterIndexed<'a, K, V, CAP, I>
127{
128    fn next_back(&mut self) -> Option<Self::Item> {
129        // decrement then consume
130        self.0
131            .next_back()
132            .map(|(k, v)| (self.0.get_index(self.0.from_largest_bsi), k, v))
133    }
134}
const_lru/iters/iter_key_order.rs

const_lru/iters/
iter_key_order.rs
