cl_structures/
index_map.rs

1//! Trivially-copyable, easily comparable typed [indices](MapIndex),
2//! and an [IndexMap] to contain them.
3//!
4//! # Examples
5//!
6//! ```rust
7//! # use cl_structures::index_map::*;
8//! // first, create a new MapIndex type (this ensures type safety)
9//! make_index! {
10//!     Number
11//! }
12//!
13//! // then, create a map with that type
14//! let mut numbers: IndexMap<Number, i32> = IndexMap::new();
15//! let first = numbers.insert(1);
16//! let second = numbers.insert(2);
17//! let third = numbers.insert(3);
18//!
19//! // You can access elements immutably with `get`
20//! assert_eq!(Some(&3), numbers.get(third));
21//! assert_eq!(Some(&2), numbers.get(second));
22//! // or by indexing
23//! assert_eq!(1, numbers[first]);
24//!
25//! // Or mutably
26//! *numbers.get_mut(first).unwrap() = 100000;
27//!
28//! assert_eq!(Some(&100000), numbers.get(first));
29//! ```
30
31/// Creates newtype indices over [`usize`] for use as [IndexMap] keys.
32///
33/// Generated key types implement [Clone], [Copy],
34/// [Debug](core::fmt::Debug), [PartialEq], [Eq], [PartialOrd], [Ord], [Hash](core::hash::Hash),
35/// and [MapIndex].
36#[macro_export]
37macro_rules! make_index {($($(#[$meta:meta])* $name:ident),*$(,)?) => {$(
38    $(#[$meta])*
39    #[repr(transparent)]
40    #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
41    pub struct $name(usize);
42
43    impl $crate::index_map::MapIndex for $name {
44        #[doc = concat!("Constructs a [`", stringify!($name), "`] from a [`usize`] without checking bounds.\n")]
45        /// The provided value should be within the bounds of its associated container
46        #[inline]
47        fn from_usize(value: usize) -> Self {
48            Self(value)
49        }
50        #[inline]
51        fn get(&self) -> usize {
52            self.0
53        }
54    }
55
56    impl From< $name > for usize {
57        fn from(value: $name) -> Self {
58            value.0
59        }
60    }
61)*}}
62
63use self::iter::MapIndexIter;
64use std::{
65    ops::{Index, IndexMut},
66    slice::GetDisjointMutError,
67};
68
69pub use make_index;
70
71/// An index into a [IndexMap]. For full type-safety,
72/// there should be a unique [MapIndex] for each [IndexMap].
73pub trait MapIndex: std::fmt::Debug {
74    /// Constructs an [`MapIndex`] from a [`usize`] without checking bounds.
75    ///
76    /// The provided value should be within the bounds of its associated container.
77    fn from_usize(value: usize) -> Self;
78    /// Gets the index of the [`MapIndex`] by value
79    fn get(&self) -> usize;
80}
81
82/// It's an array. Lmao.
83#[derive(Clone, Debug, PartialEq, Eq)]
84pub struct IndexMap<K: MapIndex, V> {
85    map: Vec<V>,
86    id_type: std::marker::PhantomData<K>,
87}
88
89impl<V, K: MapIndex> IndexMap<K, V> {
90    /// Constructs an empty IndexMap.
91    pub fn new() -> Self {
92        Self::default()
93    }
94
95    /// Gets a reference to the value in slot `index`.
96    pub fn get(&self, index: K) -> Option<&V> {
97        self.map.get(index.get())
98    }
99
100    /// Gets a mutable reference to the value in slot `index`.
101    pub fn get_mut(&mut self, index: K) -> Option<&mut V> {
102        self.map.get_mut(index.get())
103    }
104
105    /// Returns mutable references to many indices at once.
106    ///
107    /// Returns an error if any index is out of bounds, or if the same index was passed twice.
108    pub fn get_disjoint_mut<const N: usize>(
109        &mut self,
110        indices: [K; N],
111    ) -> Result<[&mut V; N], GetDisjointMutError> {
112        self.map.get_disjoint_mut(indices.map(|id| id.get()))
113    }
114
115    /// Returns an iterator over the IndexMap.
116    pub fn values(&self) -> impl Iterator<Item = &V> {
117        self.map.iter()
118    }
119
120    /// Returns an iterator that allows modifying each value.
121    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
122        self.map.iter_mut()
123    }
124
125    /// Returns an iterator over all keys in the IndexMap.
126    pub fn keys(&self) -> iter::MapIndexIter<K> {
127        // Safety: IndexMap currently has map.len() entries, and data cannot be removed
128        MapIndexIter::new(0..self.map.len())
129    }
130
131    /// Constructs an [ID](MapIndex) from a [usize], if it's within bounds
132    #[doc(hidden)]
133    pub fn try_key_from(&self, value: usize) -> Option<K> {
134        (value < self.map.len()).then(|| K::from_usize(value))
135    }
136
137    /// Inserts a new item into the IndexMap, returning the key associated with it.
138    pub fn insert(&mut self, value: V) -> K {
139        let id = self.map.len();
140        self.map.push(value);
141
142        // Safety: value was pushed to `self.map[id]`
143        K::from_usize(id)
144    }
145
146    /// Replaces a value in the IndexMap, returning the old value.
147    pub fn replace(&mut self, key: K, value: V) -> V {
148        std::mem::replace(&mut self[key], value)
149    }
150}
151
152impl<K: MapIndex, V> Default for IndexMap<K, V> {
153    fn default() -> Self {
154        Self { map: vec![], id_type: std::marker::PhantomData }
155    }
156}
157
158impl<K: MapIndex, V> Index<K> for IndexMap<K, V> {
159    type Output = V;
160
161    fn index(&self, index: K) -> &Self::Output {
162        match self.map.get(index.get()) {
163            None => panic!("Index {:?} out of bounds in IndexMap!", index),
164            Some(value) => value,
165        }
166    }
167}
168
169impl<K: MapIndex, V> IndexMut<K> for IndexMap<K, V> {
170    fn index_mut(&mut self, index: K) -> &mut Self::Output {
171        match self.map.get_mut(index.get()) {
172            None => panic!("Index {:?} out of bounds in IndexMap!", index),
173            Some(value) => value,
174        }
175    }
176}
177
178mod iter {
179    //! Iterators for [IndexMap](super::IndexMap)
180    use super::MapIndex;
181    use std::{marker::PhantomData, ops::Range};
182
183    /// Iterates over the keys of an [IndexMap](super::IndexMap), independently of the map.
184    ///
185    /// This is guaranteed to never overrun the length of the map, but is *NOT* guaranteed
186    /// to iterate over all elements of the map if the map is extended during iteration.
187    #[derive(Clone, Debug, PartialEq, Eq, Hash)]
188    pub struct MapIndexIter<K: MapIndex> {
189        range: Range<usize>,
190        _id: PhantomData<K>,
191    }
192
193    impl<K: MapIndex> MapIndexIter<K> {
194        /// Creates a new [MapIndexIter] producing the given [MapIndex]
195        pub(super) fn new(range: Range<usize>) -> Self {
196            Self { range, _id: PhantomData }
197        }
198    }
199
200    impl<ID: MapIndex> Iterator for MapIndexIter<ID> {
201        type Item = ID;
202
203        fn next(&mut self) -> Option<Self::Item> {
204            Some(ID::from_usize(self.range.next()?))
205        }
206        fn size_hint(&self) -> (usize, Option<usize>) {
207            self.range.size_hint()
208        }
209    }
210
211    impl<ID: MapIndex> DoubleEndedIterator for MapIndexIter<ID> {
212        fn next_back(&mut self) -> Option<Self::Item> {
213            // Safety: see above
214            Some(ID::from_usize(self.range.next_back()?))
215        }
216    }
217
218    impl<ID: MapIndex> ExactSizeIterator for MapIndexIter<ID> {}
219}
cl_structures/index_map.rs

cl_structures/
index_map.rs
