1pub type Idx = usize;
8
9pub struct List<T> {
20 inner: Vec<Option<T>>,
21}
22
23impl<T> Default for List<T> {
24 fn default() -> Self {
25 Self { inner: Vec::default() }
26 }
27}
28
29impl<T: std::fmt::Debug> std::fmt::Debug for List<T> {
30 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
31 write!(f, "{:?}", self.inner)
32 }
33}
34
35impl<T> List<T> {
36 pub fn insert(&mut self, value: T) -> Idx {
39 let index = if let Some(index) = self.inner.iter_mut().position(|v| v.is_none()) {
40 self.inner[index] = Some(value);
41 index
42 } else {
43 self.inner.push(Some(value));
44 self.inner.len() - 1
45 };
46
47 Self::to_call_index(index)
48 }
49
50 pub fn get(&self, index: Idx) -> Option<&T> {
52 match Self::to_internal_index(index) {
53 Some(index) => self.inner.get(index).map(|v| v.as_ref()).unwrap_or(None),
54 None => None,
55 }
56 }
57
58 pub fn get_mut(&mut self, index: Idx) -> Option<&mut T> {
61 match Self::to_internal_index(index) {
62 Some(index) => self.inner.get_mut(index).map(|v| v.as_mut()).unwrap_or(None),
63 None => None,
64 }
65 }
66
67 pub fn remove(&mut self, index: Idx) -> Option<T> {
69 match Self::to_internal_index(index) {
70 Some(index) => self.inner.get_mut(index).map(|v| v.take()).unwrap_or(None),
71 None => None,
72 }
73 }
74
75 pub fn calls(&self) -> impl Iterator<Item = (Idx, &T)> + Clone {
77 self.inner
78 .iter()
79 .enumerate()
80 .flat_map(|(i, entry)| entry.as_ref().map(|v| (Self::to_call_index(i), v)))
81 }
82
83 fn to_internal_index(index: Idx) -> Option<usize> {
90 (index != 0).then(|| index - 1)
91 }
92
93 fn to_call_index(internal: usize) -> Idx {
97 internal + 1
98 }
99
100 pub fn len(&self) -> usize {
102 self.inner.iter().map(Option::as_ref).filter(Option::is_some).count()
103 }
104}
105
106#[cfg(test)]
107mod tests {
108 use super::*;
109
110 #[fuchsia::test]
111 fn call_list_insert() {
112 let mut list = List::default();
113 let i1 = list.insert(1);
114 assert_eq!(i1, 1, "The first value must be assigned the number 1");
115 let i2 = list.insert(2);
116 assert_eq!(i2, 2, "The second value is assigned the next available number");
117 }
118
119 #[fuchsia::test]
120 fn call_list_get() {
121 let mut list = List::default();
122 let i1 = list.insert(1);
123 let i2 = list.insert(2);
124 assert_eq!(list.get(0), None);
125 assert_eq!(list.get(i1), Some(&1));
126 assert_eq!(list.get(i2), Some(&2));
127 assert_eq!(list.get(3), None);
128 }
129
130 #[fuchsia::test]
131 fn call_list_get_mut() {
132 let mut list = List::default();
133 let i1 = list.insert(1);
134 let i2 = list.insert(2);
135 assert_eq!(list.get_mut(i1), Some(&mut 1));
136 assert_eq!(list.get_mut(i2), Some(&mut 2));
137 assert_eq!(list.get_mut(3), None);
138 }
139
140 #[fuchsia::test]
141 fn call_list_remove() {
142 let mut list = List::default();
143 let i1 = list.insert(1);
144 let i2 = list.insert(2);
145 let removed = list.remove(i1);
146 assert!(removed.is_some());
147 assert_eq!(list.get(i1), None, "The value at i1 is removed");
148 assert_eq!(list.get(i2), Some(&2), "The value at i2 is untouched");
149 let invalid_idx = 0;
150 assert!(list.remove(invalid_idx).is_none());
151 }
152
153 #[fuchsia::test]
154 fn call_list_remove_and_insert_behaves() {
155 let mut list = List::default();
156 let i1 = list.insert(1);
157 let i2 = list.insert(2);
158 let i3 = list.insert(3);
159 let i4 = list.insert(4);
160 assert!(list.remove(i2).is_some());
161 assert!(list.remove(i1).is_some());
162 assert!(list.remove(i3).is_some());
163 let i5 = list.insert(5);
164 assert_eq!(i5, i1, "i5 is the lowest possible index (i1) even though i1 was not the first or last index removed");
165 assert_eq!(list.get(i5), Some(&5), "The value at i5 is correct");
166 let i6 = list.insert(6);
167 let i7 = list.insert(7);
168 assert_eq!(i6, i2, "i6 takes the next available index (i2)");
169 assert_eq!(i7, i3, "i7 takes the next available index (i3)");
170 let i8_ = list.insert(8);
171 assert_ne!(i8_, i4, "i4 is reserved, so i8_ must take a new index");
172 assert_eq!(
173 i8_, 5,
174 "i8_ takes an index of 5 since it is the last of the 5 values to be inserted"
175 );
176 }
177
178 #[fuchsia::test]
179 fn call_list_iter_returns_all_valid_values() {
180 let mut list = List::default();
181 let i1 = list.insert(1);
182 let i2 = list.insert(2);
183 let i3 = list.insert(3);
184 let i4 = list.insert(4);
185 assert!(list.remove(i2).is_some());
186 let actual: Vec<_> = list.calls().collect();
187 let expected = vec![(i1, &1), (i3, &3), (i4, &4)];
188 assert_eq!(actual, expected);
189 }
190}