pie_core/
index.rs

1//! Definition of the Index type
2
3use std::{convert::TryFrom, fmt, hash::{Hash, Hasher}, marker::PhantomData};
4
5/// A type-safe, compact handle to an element in an `ElemPool`.
6///
7/// An `Index<T>` is essentially a wrapper around a `u32`, providing a cheap,
8/// `Copy`-able way to reference list elements without relying on raw pointers
9/// or garbage collection.
10///
11/// # Rationale
12///
13/// Using a custom `Index` type instead of a raw `usize` or `u32` provides
14/// several benefits:
15/// - **Type Safety:** `Index<Foo>` is a different type from `Index<Bar>`. This
16///   prevents accidentally using an index from a pool of `Foo`s to access a
17///   pool of `Bar`s. The `PhantomData<T>` marker enforces this at compile time
18///   with zero runtime cost.
19/// - **"None" State:** The maximum value of `u32` is reserved for `Index::NONE`,
20///   creating a clear, efficient "null" or "invalid" state, similar to
21///   `Option<T>` but without the added size overhead.
22/// - **API Clarity:** Using `Index<T>` in function signatures makes it clear
23///   that the function expects a handle to a list element, not just an arbitrary
24///   number.
25#[derive(Eq)]
26pub struct Index<T> {
27    ndx: u32,
28    _marker: PhantomData<T>,
29}
30
31// Manually implement Clone and Copy to avoid trait bounds on `T`.
32// This is sound because `PhantomData<T>` has a size of zero.
33impl<T> Clone for Index<T> {
34    #[inline]
35    fn clone(&self) -> Self {
36        *self
37    }
38}
39impl<T> Copy for Index<T> {}
40
41impl<T> fmt::Debug for Index<T> {
42    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
43        match self.ndx {
44            u32::MAX => write!(f, "Index(-)"),
45            _ => write!(f, "{:?}", self.ndx),
46        }
47    }
48}
49
50impl<T> Default for Index<T> {
51    /// The default `Index` is `Index::NONE`.
52    fn default() -> Self {
53        Self::NONE
54    }
55}
56
57impl<T> PartialEq for Index<T> {
58    #[inline]
59    fn eq(&self, other: &Self) -> bool {
60        self.ndx == other.ndx
61    }
62}
63
64impl<T> Hash for Index<T> {
65    #[inline]
66    fn hash<H: Hasher>(&self, state: &mut H) {
67        self.ndx.hash(state);
68    }
69}
70
71impl<T> Index<T> {
72    /// An invalid index, conceptually similar to `Option::None`.
73    ///
74    /// This constant value (`u32::MAX`) is reserved to represent a null or
75    /// sentinel link. All valid indices into the `ElemPool` will be less
76    /// than this value.
77    pub const NONE: Self = Index {
78        ndx: u32::MAX,
79        _marker: PhantomData,
80    };
81
82    /// Returns `true` if the index is valid (i.e., not `Index::NONE`).
83    ///
84    /// # Example
85    /// ```
86    /// # use pie_core::Index;
87    /// let valid_index = Index::<i32>::from(10_u32);
88    /// assert!(valid_index.is_some());
89    ///
90    /// let invalid_index = Index::<i32>::NONE;
91    /// assert!(!invalid_index.is_some());
92    /// ```
93    #[inline]
94    pub fn is_some(&self) -> bool {
95        self.ndx != u32::MAX
96    }
97
98    /// Returns `true` if the index is invalid (i.e., it is `Index::NONE`).
99    ///
100    /// # Example
101    /// ```
102    /// # use pie_core::Index;
103    /// let invalid_index = Index::<i32>::NONE;
104    /// assert!(invalid_index.is_none());
105    ///
106    /// let valid_index = Index::<i32>::from(10_u32);
107    /// assert!(!valid_index.is_none());
108    /// ```
109    #[inline]
110    pub fn is_none(&self) -> bool {
111        self.ndx == u32::MAX
112    }
113
114    /// Converts the `Index` to an `Option<usize>`.
115    ///
116    /// This is used internally to safely access the `ElemPool`'s underlying `Vec`.
117    /// Returns `Some(usize)` for a valid index, and `None` for `Index::NONE`.
118    #[inline]
119    pub(crate) fn get(&self) -> Option<usize> {
120        if self.is_some() {
121            Some(self.ndx as usize)
122        } else {
123            None
124        }
125    }
126}
127
128impl<T> From<u32> for Index<T> {
129    /// Creates an `Index` from a raw `u32`.
130    #[inline]
131    fn from(ndx: u32) -> Index<T> {
132        Self {
133            ndx,
134            _marker: PhantomData,
135        }
136    }
137}
138
139impl<T> From<usize> for Index<T> {
140    /// Creates an `Index` from a `usize`.
141    ///
142    /// This conversion is fallible. Values greater than or equal to
143    /// `u32::MAX` will be converted into an invalid index (`Index::NONE`).
144    /// This prevents out-of-bounds errors when converting from `usize` on
145    /// 64-bit platforms.
146    ///
147    /// # Example
148    /// ```
149    /// # use pie_core::Index;
150    /// let index1 = Index::<char>::from(123_usize);
151    /// assert!(index1.is_some());
152    ///
153    /// let index2 = Index::<char>::from(u32::MAX as usize);
154    /// assert!(index2.is_none());
155    /// ```
156    #[inline]
157    fn from(index: usize) -> Index<T> {
158        Index::from(u32::try_from(index).unwrap_or(u32::MAX))
159    }
160}
161
162impl<T> fmt::Display for Index<T> {
163    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
164        match self.get() {
165            Some(n) => write!(f, "{}", n),
166            None => write!(f, "-"),
167        }
168    }
169}
170
171#[cfg(test)]
172mod tests {
173    use super::*;
174    use std::collections::HashSet;
175
176    // A dummy type to use for the generic Index<T>
177    #[derive(PartialEq, Eq)]
178    struct MyData;
179
180    #[test]
181    fn test_creation_and_constants() {
182        let index_from_u32 = Index::<MyData>::from(42_u32);
183        assert_eq!(index_from_u32.ndx, 42);
184
185        let index_from_usize = Index::<MyData>::from(123_usize);
186        assert_eq!(index_from_usize.ndx, 123);
187
188        // Check the NONE constant
189        assert_eq!(Index::<MyData>::NONE.ndx, u32::MAX);
190    }
191
192    #[test]
193    fn test_default() {
194        // Default should be equivalent to NONE
195        let default_index = Index::<MyData>::default();
196        assert_eq!(default_index, Index::NONE);
197        assert!(default_index.is_none());
198    }
199
200    #[test]
201    fn test_state_checks() {
202        let valid_index = Index::<MyData>::from(10_u32);
203        let none_index = Index::<MyData>::NONE;
204
205        // is_some()
206        assert!(valid_index.is_some());
207        assert!(!none_index.is_some());
208
209        // is_none()
210        assert!(!valid_index.is_none());
211        assert!(none_index.is_none());
212    }
213
214    #[test]
215    fn test_get() {
216        let valid_index = Index::<MyData>::from(99_u32);
217        let none_index = Index::<MyData>::NONE;
218
219        assert_eq!(valid_index.get(), Some(99_usize));
220        assert_eq!(none_index.get(), None);
221    }
222
223    #[test]
224    fn test_from_usize_overflow() {
225        // A usize that fits into u32
226        let normal_usize = u32::MAX - 1;
227        let index1 = Index::<MyData>::from(normal_usize as usize);
228        assert_eq!(index1.ndx, u32::MAX - 1);
229        assert!(index1.is_some());
230
231        // A usize that is exactly u32::MAX should become NONE
232        let overflow_usize_1 = u32::MAX;
233        let index2 = Index::<MyData>::from(overflow_usize_1 as usize);
234        assert_eq!(index2, Index::NONE);
235        assert!(index2.is_none());
236
237        // A larger usize should also become NONE
238        let overflow_usize_2 = u64::MAX as usize;
239        let index3 = Index::<MyData>::from(overflow_usize_2);
240        assert_eq!(index3, Index::NONE);
241        assert!(index3.is_none());
242    }
243
244    #[test]
245    fn test_equality() {
246        let index1a = Index::<MyData>::from(1_u32);
247        let index1b = Index::<MyData>::from(1_u32);
248        let index2 = Index::<MyData>::from(2_u32);
249        let none1 = Index::<MyData>::NONE;
250        let none2 = Index::<MyData>::NONE;
251
252        assert_eq!(index1a, index1b);
253        assert_eq!(none1, none2);
254        assert_ne!(index1a, index2);
255        assert_ne!(index1a, none1);
256    }
257
258    #[test]
259    fn test_clone_and_copy() {
260        let original = Index::<MyData>::from(50_u32);
261
262        // Test Copy
263        let copied = original;
264        assert_eq!(original, copied);
265
266        // Test Clone
267        let cloned = original.clone();
268        assert_eq!(original, cloned);
269
270        // Ensure they are distinct in memory but equal in value
271        assert_eq!(original.ndx, copied.ndx);
272        assert_eq!(original.ndx, cloned.ndx);
273    }
274
275    #[test]
276    fn test_hash() {
277        let mut set = HashSet::new();
278        let index1 = Index::<MyData>::from(1_u32);
279        let index1_dup = Index::<MyData>::from(1_u32);
280        let index2 = Index::<MyData>::from(2_u32);
281        let none_index = Index::<MyData>::NONE;
282
283        assert!(set.insert(index1));
284        assert!(set.insert(index2));
285        assert!(set.insert(none_index));
286
287        // Inserting a duplicate should return false
288        assert!(!set.insert(index1_dup));
289
290        // Check size and membership
291        assert_eq!(set.len(), 3);
292        assert!(set.contains(&index1));
293        assert!(set.contains(&index2));
294        assert!(set.contains(&none_index));
295        assert!(!set.contains(&Index::from(99_u32)));
296    }
297
298    #[test]
299    fn test_formatting() {
300        let valid_index = Index::<MyData>::from(123_u32);
301        let none_index = Index::<MyData>::NONE;
302
303        // Test Debug format
304        let debug_valid = format!("{:?}", valid_index);
305        let debug_none = format!("{:?}", none_index);
306        assert_eq!(debug_valid, "123");
307        assert_eq!(debug_none, "Index(-)");
308
309        // Test Display format
310        let display_valid = format!("{}", valid_index);
311        let display_none = format!("{}", none_index);
312        assert_eq!(display_valid, "123");
313        assert_eq!(display_none, "-");
314    }
315}
pie_core/index.rs

pie_core/
index.rs
