rate_common/memory/
stackmapping.rs

1//! `StackMapping` combines a `BoundedVector` and an `Array`, providing fast look-up and iteration.
2
3use crate::memory::{Array, BoundedVector, HeapSpace, Offset};
4use rate_macros::HeapSpace;
5use std::{fmt::Debug, iter::IntoIterator, ops::Index, slice};
6
7/// A combination of a [`BoundedVector`](../boundedvector/struct.BoundedVector.html)
8/// and an [`Array`](../array/struct.Array.html).
9///
10/// This provides `Vec`-like semantics with elements of type `Key`.
11/// Additionally, each key is associated with one value of type `T` (key is
12/// mapped to value).
13/// The value can be looked up in constant time using the index operator (`[]`).
14#[derive(Debug, HeapSpace, Default)]
15pub struct StackMapping<Key: Offset + Copy + Debug, T: Copy + Debug> {
16    /// The default value to use for unmapped keys.
17    default_value: T,
18    /// The `Array` that stores the key-value pairs.
19    array: Array<Key, T>,
20    /// The stack that stores the keys.
21    vector: BoundedVector<Key>,
22}
23
24impl<Key: Offset + Copy + Debug, T: Copy + Debug> StackMapping<Key, T> {
25    /// Construct a new `StackMapping`.
26    ///
27    /// # Parameters
28    /// - `array_value:` see [default_value](#structfield.default_value)
29    /// - `array_size:` the size of the array, must be large enough to hold
30    ///   the highest expected value of type `Key`
31    /// - `stack_size:` the maximum size of the stack, e.g. the maximum
32    ///   number of keys that can be added to this stackmapping
33    pub fn with_array_value_size_stack_size(
34        array_value: T,
35        array_size: usize,
36        stack_size: usize,
37    ) -> StackMapping<Key, T> {
38        StackMapping {
39            default_value: array_value,
40            array: Array::new(array_value, array_size),
41            vector: BoundedVector::with_capacity(stack_size),
42        }
43    }
44    /// See [`Vec::len()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.len).
45    pub fn len(&self) -> usize {
46        self.vector.len()
47    }
48    /// See [`Vec::is_empty()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.is_empty).
49    pub fn is_empty(&self) -> bool {
50        self.vector.is_empty()
51    }
52    /// This removs the top `Key` and also resets the mapping of this key
53    /// to the [default_value](#structfield.default_value).
54    pub fn pop(&mut self) -> Option<Key> {
55        self.vector.pop().map(|key| {
56            self.array[key] = self.default_value;
57            key
58        })
59    }
60    /// Returns the last key in the vector.
61    /// # Panics
62    /// Panics if the vector is empty.
63    pub fn peek(&self) -> Key {
64        self.vector[self.vector.len() - 1]
65    }
66    /// This clears the vector and resets all mappings.
67    pub fn clear(&mut self) {
68        while !self.is_empty() {
69            self.pop();
70        }
71    }
72    /// Returns the key in the vector at the given index.
73    pub fn stack_at(&self, offset: usize) -> Key {
74        self.vector[offset]
75    }
76    /// Returns the mutable key in the vector at the given index.
77    pub fn stack_at_mut(&mut self, offset: usize) -> &mut Key {
78        &mut self.vector[offset]
79    }
80    /// Pushes to the vector and maps `key` to `value`.
81    pub fn push(&mut self, key: Key, value: T) {
82        self.array[key] = value;
83        self.vector.push(key);
84    }
85    /// Pushes to the vector.
86    pub fn push_but_do_not_set(&mut self, key: Key) {
87        self.vector.push(key);
88    }
89    /// Maps `key` to `value`.
90    pub fn set_but_do_not_push(&mut self, key: Key, value: T) {
91        self.array[key] = value;
92    }
93    /// Returns an iterator over the keys in the vector.
94    pub fn iter(&self) -> slice::Iter<Key> {
95        self.into_iter()
96    }
97}
98
99impl<Key: Offset + Copy + Debug, T: Copy + Debug> Index<Key> for StackMapping<Key, T> {
100    type Output = T;
101    fn index(&self, key: Key) -> &T {
102        &self.array[key]
103    }
104}
105
106impl<'a, Key: Offset + Copy + Debug, T: Copy + Debug> IntoIterator for &'a StackMapping<Key, T> {
107    type Item = &'a Key;
108    type IntoIter = slice::Iter<'a, Key>;
109    fn into_iter(self) -> Self::IntoIter {
110        self.vector.into_iter()
111    }
112}
113
114impl<Key: Ord + Offset + Copy + Debug, T: Copy + Debug> StackMapping<Key, T> {
115    /// See [`Vec::sort_unstable()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_unstable).
116    pub fn sort_unstable(&mut self) {
117        self.vector.sort_unstable()
118    }
119}
120
121impl<Key: Offset + Copy + Debug, T: Copy + Debug> StackMapping<Key, T> {
122    /// See [`Vec::sort_unstable_by_key()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_unstable_by_key).
123    pub fn sort_unstable_by_key<F, K>(&mut self, f: F)
124    where
125        F: FnMut(&Key) -> K,
126        K: Ord,
127    {
128        self.vector.sort_unstable_by_key(f)
129    }
130}
rate_common/memory/stackmapping.rs

rate_common/memory/
stackmapping.rs
