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.get(0), 0);
49    assert_eq!(x.get(5), 7);
50    assert_eq!(x, y);
51}
52
53#[test]
54fn test_clone_short() {
55    let mut x: DefaultVec<u32> = DefaultVec::default();
56    *x.get_mut(0) = 3;
57    let mut y: DefaultVec<u32> = DefaultVec::default();
58    *y.get_mut(5) = 7;
59    y.clone_from(&x);
60    assert_eq!(y.get(0), 3);
61    assert_eq!(y.get(5), 0);
62    assert_eq!(x, y);
63}
64
65impl<T: PartialEq + Default, I> PartialEq for DefaultVec<T, I> {
66    fn eq(&self, other: &Self) -> bool {
67        let (long, short) = if self.0.len() < other.0.len() {
68            (&*other.0, &*self.0)
69        } else {
70            (&*self.0, &*other.0)
71        };
72        short == &long[..short.len()] && long[short.len()..].iter().all(|x| *x == T::default())
73    }
74}
75
76impl<T: Eq + Default, I> Eq for DefaultVec<T, I> {}
77
78#[test]
79fn test_eq() {
80    let mut x: DefaultVec<u32> = DefaultVec::default();
81    *x.get_mut(42) = 3;
82    *x.get_mut(42) = u32::default();
83    assert_eq!(x, DefaultVec::default())
84}
85
86impl<T: Debug + Default, I: Into<usize>> Debug for DefaultVec<T, I> {
87    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
88        self.0.fmt(f)
89    }
90}
91
92pub trait ConstDefault: Default + 'static {
93    /// Constant version of default value
94    const DEFAULT: &'static Self;
95}
96
97impl<T: Default, I: Into<usize>> DefaultVec<T, I> {
98    #[cold]
99    #[inline(never)]
100    pub(super) fn reserve(&mut self, i: usize) {
101        let mut v = mem::take(&mut self.0).into_vec();
102        v.reserve(i + 1 - v.len());
103        v.resize_with(v.capacity(), T::default);
104        self.0 = v.into_boxed_slice();
105        assert!(i < self.0.len())
106    }
107
108    /// Returns mutable access to the element at `i`
109    pub fn get_mut(&mut self, i: I) -> &mut T {
110        let i: usize = i.into();
111        if i < self.0.len() {
112            &mut self.0[i]
113        } else {
114            self.reserve(i);
115            &mut self.0[i]
116        }
117    }
118
119    /// Returns shared access to the element at `i`
120    pub fn get(&self, i: I) -> T
121    where
122        T: Copy,
123    {
124        let i: usize = i.into();
125        self.0.get(i).copied().unwrap_or_default()
126    }
127
128    /// Resets all elements to there default value
129    pub fn clear(&mut self) {
130        self.0.fill_with(Default::default)
131    }
132
133    pub fn capacity(&self) -> usize {
134        self.0.len()
135    }
136
137    /// Returns an iterator over the elements of this list
138    /// the iterator will have `capacity` elements
139    pub fn iter(&self) -> slice::Iter<T> {
140        self.0.iter()
141    }
142
143    /// Returns a mutable iterator over the elements of this list
144    /// the iterator will have `capacity` elements
145    pub fn iter_mut(&mut self) -> slice::IterMut<T> {
146        self.0.iter_mut()
147    }
148}
149impl<T: ConstDefault, I: Into<usize>> Index<I> for DefaultVec<T, I> {
150    type Output = T;
151
152    fn index(&self, index: I) -> &Self::Output {
153        self.0.get(index.into()).unwrap_or(T::DEFAULT)
154    }
155}
156
157impl<T: ConstDefault, I: Into<usize>> IndexMut<I> for DefaultVec<T, I> {
158    fn index_mut(&mut self, index: I) -> &mut Self::Output {
159        self.get_mut(index)
160    }
161}
default_vec2/default_vec.rs

default_vec2/
default_vec.rs
