utils/array.rs
1//! Array helpers.
2
3use std::fmt;
4use std::hash::Hash;
5use std::ops::{Deref, DerefMut};
6
7/// A fixed-size array-backed vector.
8///
9/// `ArrayVec` has a fixed-sized `N` long array and a length field to track how many elements are
10/// populated. It is useful for storing a small but variable number of elements without heap
11/// allocation.
12///
13/// The implementation is intentionally simple, and requires [`Copy`] and [`Default`] bounds on some
14/// methods instead of using [`std::mem::MaybeUninit`].
15#[derive(Clone, PartialEq, Eq, Hash)]
16pub struct ArrayVec<T, const N: usize> {
17 len: usize,
18 data: [T; N],
19}
20
21impl<T, const N: usize> ArrayVec<T, N> {
22 /// Creates a new empty `ArrayVec`.
23 ///
24 /// # Examples
25 /// ```
26 /// # use utils::array::ArrayVec;
27 /// let vec: ArrayVec<i32, 5> = ArrayVec::new();
28 /// assert_eq!(vec.len(), 0);
29 /// ```
30 #[inline]
31 #[must_use]
32 pub fn new() -> Self
33 where
34 T: Copy + Default,
35 {
36 Self {
37 len: 0,
38 data: [T::default(); N],
39 }
40 }
41
42 /// Creates a new `ArrayVec`, copying initial data from the provided slice.
43 ///
44 /// # Examples
45 /// ```
46 /// # use utils::array::ArrayVec;
47 /// let mut vec: ArrayVec<i32, 5> = ArrayVec::<i32, 5>::from_slice(&[1, 2, 3]).unwrap();
48 /// assert_eq!(vec.len(), 3);
49 /// assert_eq!(vec.pop(), Some(3));
50 /// assert_eq!(vec.pop(), Some(2));
51 /// assert_eq!(vec.pop(), Some(1));
52 /// assert_eq!(vec.pop(), None);
53 ///
54 /// assert_eq!(ArrayVec::<i32, 5>::from_slice(&[1, 2, 3, 4, 5, 6]), None);
55 /// ```
56 #[inline]
57 #[must_use]
58 pub fn from_slice(slice: &[T]) -> Option<Self>
59 where
60 T: Copy + Default,
61 {
62 if slice.len() > N {
63 None
64 } else {
65 let mut data = [T::default(); N];
66 data[..slice.len()].copy_from_slice(slice);
67 Some(Self {
68 len: slice.len(),
69 data,
70 })
71 }
72 }
73
74 /// Adds an element to the end of the vector.
75 ///
76 /// Returns [`Err`] containing the provided value if the vector is already full.
77 ///
78 /// # Examples
79 /// ```
80 /// # use utils::array::ArrayVec;
81 /// let mut vec: ArrayVec<i32, 2> = ArrayVec::new();
82 /// assert_eq!(vec.push(1), Ok(()));
83 /// assert_eq!(vec.push(2), Ok(()));
84 /// assert_eq!(vec.push(3), Err(3)); // Vector is full
85 /// ```
86 #[inline]
87 pub fn push(&mut self, value: T) -> Result<(), T> {
88 let len = self.len;
89 if len < N {
90 self.data[len] = value;
91 // LLVM can't always tell that an element write doesn't overwrite the length, so
92 // write the length last using the value read above to avoid reading it again
93 self.len = len + 1;
94 Ok(())
95 } else {
96 Err(value)
97 }
98 }
99
100 /// Removes the last element from the vector and returns it, or [`None`] if it is empty.
101 ///
102 /// # Examples
103 /// ```
104 /// # use utils::array::ArrayVec;
105 /// let mut vec: ArrayVec<i32, 3> = ArrayVec::new();
106 /// vec.push(1).unwrap();
107 /// assert_eq!(vec.pop(), Some(1));
108 /// assert_eq!(vec.pop(), None);
109 /// ```
110 #[inline]
111 pub fn pop(&mut self) -> Option<T>
112 where
113 T: Default,
114 {
115 // Write the length last (see push)
116 let len = self.len.checked_sub(1)?;
117 let value = std::mem::take(&mut self.data[len]);
118 self.len = len;
119 Some(value)
120 }
121
122 /// Returns a slice of all the populated elements in the vector.
123 ///
124 /// # Examples
125 ///
126 /// ```
127 /// # use utils::array::ArrayVec;
128 /// let mut vec: ArrayVec<i32, 3> = ArrayVec::new();
129 /// vec.push(1).unwrap();
130 /// vec.push(2).unwrap();
131 /// assert_eq!(vec.as_slice(), &[1, 2]);
132 /// ```
133 #[inline]
134 pub fn as_slice(&self) -> &[T] {
135 #[cfg(feature = "unsafe")]
136 unsafe {
137 std::hint::assert_unchecked(self.len <= N);
138 }
139
140 &self.data[..self.len]
141 }
142
143 /// Returns a mutable slice of all the populated elements in the vector.
144 ///
145 /// # Examples
146 ///
147 /// ```
148 /// # use utils::array::ArrayVec;
149 /// let mut vec: ArrayVec<i32, 3> = ArrayVec::new();
150 /// vec.push(1).unwrap();
151 /// vec.push(2).unwrap();
152 /// let mut slice = vec.as_mut_slice();
153 /// slice[1] = 10;
154 /// assert_eq!(slice, &[1, 10]);
155 /// ```
156 #[inline]
157 pub fn as_mut_slice(&mut self) -> &mut [T] {
158 #[cfg(feature = "unsafe")]
159 unsafe {
160 std::hint::assert_unchecked(self.len <= N);
161 }
162
163 &mut self.data[..self.len]
164 }
165
166 /// Returns a reference to the backing array.
167 ///
168 /// Any items after the current length will be set to the default value.
169 ///
170 /// # Examples
171 /// ```
172 /// # use utils::array::ArrayVec;
173 /// let mut vec: ArrayVec<i32, 8> = ArrayVec::new();
174 /// vec.push(10).unwrap();
175 /// vec.push(6).unwrap();
176 /// vec.pop().unwrap();
177 /// assert_eq!(vec.into_array(), [10, 0, 0, 0, 0, 0, 0, 0]);
178 /// ```
179 #[inline]
180 pub fn as_array(&self) -> &[T; N] {
181 &self.data
182 }
183
184 /// Returns the capacity of the vector, which is always `N`.
185 ///
186 /// # Examples
187 /// ```
188 /// # use utils::array::ArrayVec;
189 /// let vec: ArrayVec<i32, 5> = ArrayVec::new();
190 /// assert_eq!(vec.capacity(), 5);
191 /// ```
192 #[inline]
193 pub fn capacity(&self) -> usize {
194 N
195 }
196
197 /// Returns whether the vector is full.
198 ///
199 /// # Examples
200 ///
201 /// ```
202 /// # use utils::array::ArrayVec;
203 /// let mut vec: ArrayVec<i32, 2> = ArrayVec::new();
204 /// assert!(!vec.is_full());
205 /// vec.push(1).unwrap();
206 /// assert!(!vec.is_full());
207 /// vec.push(2).unwrap();
208 /// assert!(vec.is_full());
209 /// ```
210 #[inline]
211 pub fn is_full(&self) -> bool {
212 self.len == N
213 }
214
215 /// Returns the backing array.
216 ///
217 /// Any items after the current length will be set to the default value.
218 ///
219 /// # Examples
220 /// ```
221 /// # use utils::array::ArrayVec;
222 /// let mut vec: ArrayVec<i32, 5> = ArrayVec::new();
223 /// vec.push(1).unwrap();
224 /// vec.push(2).unwrap();
225 /// vec.push(3).unwrap();
226 /// vec.pop().unwrap();
227 /// assert_eq!(vec.into_array(), [1, 2, 0, 0, 0]);
228 /// ```
229 #[inline]
230 pub fn into_array(self) -> [T; N] {
231 self.data
232 }
233}
234
235impl<T, const N: usize> Deref for ArrayVec<T, N> {
236 type Target = [T];
237
238 #[inline]
239 fn deref(&self) -> &Self::Target {
240 self.as_slice()
241 }
242}
243
244impl<T, const N: usize> DerefMut for ArrayVec<T, N> {
245 #[inline]
246 fn deref_mut(&mut self) -> &mut Self::Target {
247 self.as_mut_slice()
248 }
249}
250
251impl<'a, T, const N: usize> IntoIterator for &'a ArrayVec<T, N> {
252 type Item = &'a T;
253 type IntoIter = std::slice::Iter<'a, T>;
254
255 #[inline]
256 fn into_iter(self) -> Self::IntoIter {
257 self.iter()
258 }
259}
260
261impl<'a, T, const N: usize> IntoIterator for &'a mut ArrayVec<T, N> {
262 type Item = &'a mut T;
263 type IntoIter = std::slice::IterMut<'a, T>;
264
265 #[inline]
266 fn into_iter(self) -> Self::IntoIter {
267 self.iter_mut()
268 }
269}
270
271impl<T: fmt::Debug, const N: usize> fmt::Debug for ArrayVec<T, N> {
272 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
273 f.debug_struct("ArrayVec")
274 .field("len", &self.len)
275 .field("cap", &N)
276 .field("data", &self.as_slice())
277 .finish()
278 }
279}
280
281impl<T: Default + Copy, const N: usize> Default for ArrayVec<T, N> {
282 fn default() -> Self {
283 Self::new()
284 }
285}
286
287impl<T, const N: usize> From<[T; N]> for ArrayVec<T, N> {
288 fn from(data: [T; N]) -> Self {
289 ArrayVec { len: N, data }
290 }
291}