default_vec2/
default_vec.rs

1use alloc::boxed::Box;
2use core::fmt::{Debug, Formatter};
3use core::marker::PhantomData;
4use core::ops::{Index, IndexMut};
5use core::{mem, slice};
6#[cfg(feature = "serde-1")]
7use serde::{Deserialize, Serialize};
8
9/// A mapping from indexes to values where all indexes initially map to [`Default::default`]
10///
11/// It is stored in 2 `usize`s worth of memory since it doesn't need to store the length.
12///
13/// It resizes its heap allocation whenever an element that wouldn't otherwise fit in memory is added
14/// and doesn't ever shrink its memory so it could end of wasting memory if an element is added with
15/// a large index and then removed
16#[cfg_attr(feature = "serde-1", derive(Serialize, Deserialize))]
17pub struct DefaultVec<T, I = usize>(Box<[T]>, PhantomData<I>);
18
19impl<T, I> Default for DefaultVec<T, I> {
20    fn default() -> Self {
21        DefaultVec(Box::default(), PhantomData)
22    }
23}
24
25impl<T: Clone + Default, I: Into<usize>> Clone for DefaultVec<T, I> {
26    fn clone(&self) -> Self {
27        DefaultVec(self.0.clone(), PhantomData)
28    }
29
30    fn clone_from(&mut self, source: &Self) {
31        if source.capacity() > self.capacity() {
32            self.reserve(source.capacity())
33        }
34        self.0[..source.0.len()].clone_from_slice(&source.0);
35        for x in &mut self.0[source.0.len()..] {
36            *x = T::default()
37        }
38    }
39}
40
41#[test]
42fn test_clone_long() {
43    let mut x: DefaultVec<u32> = DefaultVec::default();
44    *x.get_mut(0) = 3;
45    let mut y: DefaultVec<u32> = DefaultVec::default();
46    *y.get_mut(5) = 7;
47    x.clone_from(&y);
48    assert_eq!(x.capacity(), y.capacity());
49    assert_eq!(x.get(0), 0);
50    assert_eq!(x.get(5), 7);
51    assert_eq!(x, y);
52}
53
54#[test]
55fn test_clone_short() {
56    let mut x: DefaultVec<u32> = DefaultVec::default();
57    *x.get_mut(0) = 3;
58    let mut y: DefaultVec<u32> = DefaultVec::default();
59    *y.get_mut(5) = 7;
60    y.clone_from(&x);
61    assert_eq!(y.get(0), 3);
62    assert_eq!(y.get(5), 0);
63    assert_eq!(x, y);
64}
65
66impl<T: PartialEq + Default, I> PartialEq for DefaultVec<T, I> {
67    fn eq(&self, other: &Self) -> bool {
68        let (long, short) = if self.0.len() < other.0.len() {
69            (&*other.0, &*self.0)
70        } else {
71            (&*self.0, &*other.0)
72        };
73        short == &long[..short.len()] && long[short.len()..].iter().all(|x| *x == T::default())
74    }
75}
76
77impl<T: Eq + Default, I> Eq for DefaultVec<T, I> {}
78
79#[test]
80fn test_eq() {
81    let mut x: DefaultVec<u32> = DefaultVec::default();
82    *x.get_mut(42) = 3;
83    *x.get_mut(42) = u32::default();
84    assert_eq!(x, DefaultVec::default())
85}
86
87impl<T: Debug + Default, I: Into<usize>> Debug for DefaultVec<T, I> {
88    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
89        self.0.fmt(f)
90    }
91}
92
93pub trait ConstDefault: Default + 'static {
94    /// Constant version of default value
95    const DEFAULT: &'static Self;
96}
97
98impl<T: Default, I: Into<usize>> DefaultVec<T, I> {
99    #[cold]
100    #[inline(never)]
101    fn reserve_idx(&mut self, i: usize) {
102        let mut v = mem::take(&mut self.0).into_vec();
103        v.reserve(i + 1 - v.len());
104        v.resize_with(v.capacity(), T::default);
105        self.0 = v.into_boxed_slice();
106        assert!(i < self.0.len())
107    }
108
109    pub(super) fn reserve(&mut self, i: usize) {
110        let mut v = mem::take(&mut self.0).into_vec();
111        v.reserve_exact(i - v.len());
112        v.resize_with(v.capacity(), T::default);
113        self.0 = v.into_boxed_slice();
114    }
115
116    /// Returns mutable access to the element at `i`
117    pub fn get_mut(&mut self, i: I) -> &mut T {
118        let i: usize = i.into();
119        if i < self.0.len() {
120            &mut self.0[i]
121        } else {
122            self.reserve_idx(i);
123            &mut self.0[i]
124        }
125    }
126
127    /// Returns shared access to the element at `i`
128    pub fn get(&self, i: I) -> T
129    where
130        T: Copy,
131    {
132        let i: usize = i.into();
133        self.0.get(i).copied().unwrap_or_default()
134    }
135
136    /// Resets all elements to there default value
137    pub fn clear(&mut self) {
138        self.0.fill_with(Default::default)
139    }
140
141    pub fn capacity(&self) -> usize {
142        self.0.len()
143    }
144
145    /// Returns an iterator over the elements of this list
146    /// the iterator will have `capacity` elements
147    pub fn iter(&self) -> slice::Iter<'_, T> {
148        self.0.iter()
149    }
150
151    /// Returns a mutable iterator over the elements of this list
152    /// the iterator will have `capacity` elements
153    pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> {
154        self.0.iter_mut()
155    }
156}
157impl<T: ConstDefault, I: Into<usize>> Index<I> for DefaultVec<T, I> {
158    type Output = T;
159
160    fn index(&self, index: I) -> &Self::Output {
161        self.0.get(index.into()).unwrap_or(T::DEFAULT)
162    }
163}
164
165impl<T: ConstDefault, I: Into<usize>> IndexMut<I> for DefaultVec<T, I> {
166    fn index_mut(&mut self, index: I) -> &mut Self::Output {
167        self.get_mut(index)
168    }
169}
default_vec2/default_vec.rs

default_vec2/
default_vec.rs
