luminol_data/
option_vec.rs

1// Copyright (C) 2024 Melody Madeline Lyons
2//
3// This file is part of Luminol.
4//
5// Luminol is free software: you can redistribute it and/or modify
6// it under the terms of the GNU General Public License as published by
7// the Free Software Foundation, either version 3 of the License, or
8// (at your option) any later version.
9//
10// Luminol is distributed in the hope that it will be useful,
11// but WITHOUT ANY WARRANTY; without even the implied warranty of
12// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13// GNU General Public License for more details.
14//
15// You should have received a copy of the GNU General Public License
16// along with Luminol.  If not, see <http://www.gnu.org/licenses/>.
17
18use std::{
19    iter::FusedIterator,
20    ops::{Index, IndexMut},
21};
22
23use alox_48::SerializeHash;
24use serde::ser::SerializeMap;
25
26#[derive(Debug, Clone, PartialEq, Eq)]
27/// A vector that can contain unused indices.
28pub struct OptionVec<T> {
29    vec: Vec<Option<T>>,
30    num_values: usize,
31}
32
33#[derive(Debug)]
34pub struct Iter<'a, T> {
35    size: usize,
36    vec_iter: std::iter::Enumerate<std::slice::Iter<'a, Option<T>>>,
37}
38
39#[derive(Debug)]
40pub struct IterMut<'a, T> {
41    size: usize,
42    vec_iter: std::iter::Enumerate<std::slice::IterMut<'a, Option<T>>>,
43}
44
45pub struct Visitor<T>(std::marker::PhantomData<T>);
46
47impl<T> OptionVec<T> {
48    /// Create a new OptionVec with no elements.
49    pub fn new() -> Self {
50        Self {
51            vec: Vec::new(),
52            num_values: 0,
53        }
54    }
55
56    pub fn len(&self) -> usize {
57        self.vec.len()
58    }
59
60    pub fn size(&self) -> usize {
61        self.num_values
62    }
63
64    pub fn is_empty(&self) -> bool {
65        self.vec.is_empty()
66    }
67
68    pub fn contains(&self, index: usize) -> bool {
69        self.get(index).is_some()
70    }
71
72    pub fn get(&self, index: usize) -> Option<&T> {
73        self.vec.get(index).and_then(|x| x.as_ref())
74    }
75
76    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
77        self.vec.get_mut(index).and_then(|x| x.as_mut())
78    }
79
80    pub fn capacity(&self) -> usize {
81        self.vec.capacity()
82    }
83
84    pub fn reserve(&mut self, additional: usize) {
85        self.vec.reserve(additional);
86    }
87
88    pub fn clear(&mut self) {
89        self.vec.clear();
90    }
91
92    pub fn iter(&self) -> Iter<'_, T> {
93        self.into_iter()
94    }
95
96    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
97        self.into_iter()
98    }
99
100    /// Write the element at the given index.
101    /// If there is already an element at the given index, it will be overwritten.
102    /// If there isn't, a new element will be added at that index.
103    pub fn insert(&mut self, index: usize, element: T) {
104        if index >= self.len() {
105            let additional = index - self.len() + 1;
106            self.reserve(additional);
107            self.vec
108                .extend(std::iter::repeat_with(|| None).take(additional));
109        }
110        if self.vec[index].is_none() {
111            self.num_values += 1;
112        }
113        self.vec[index] = Some(element);
114    }
115
116    /// Remove the element at the given index and return it.
117    /// If the OptionVec is not big enough to contain this index, this will throw an error.
118    /// If there isn't an element at that index, this will throw an error.
119    pub fn try_remove(&mut self, index: usize) -> Result<T, String> {
120        if index >= self.len() {
121            Err(String::from("index out of bounds"))
122        } else if self.vec[index].is_none() {
123            Err(String::from("index not found"))
124        } else {
125            self.num_values -= 1;
126            Ok(self.vec[index].take().unwrap())
127        }
128    }
129
130    pub fn option_remove(&mut self, index: usize) -> Option<T> {
131        if index >= self.len() {
132            None
133        } else {
134            self.num_values -= 1;
135            self.vec[index].take()
136        }
137    }
138
139    /// Remove the element at the given index and return it.
140    /// If the OptionVec is not big enough to contain this index, this will panic.
141    /// If there isn't an element at that index, this will panic.
142    pub fn remove(&mut self, index: usize) -> T {
143        self.try_remove(index).unwrap()
144    }
145}
146
147impl<T> Default for OptionVec<T> {
148    fn default() -> Self {
149        OptionVec::new()
150    }
151}
152
153impl<T> FromIterator<(usize, T)> for OptionVec<T> {
154    fn from_iter<I: IntoIterator<Item = (usize, T)>>(iterable: I) -> Self {
155        let mut vec = Vec::new();
156        let mut num_values = 0;
157        for (i, v) in iterable.into_iter() {
158            if i >= vec.len() {
159                let additional = i - vec.len() + 1;
160                vec.reserve(additional);
161                vec.extend(std::iter::repeat_with(|| None).take(additional));
162            }
163            if vec[i].is_none() {
164                num_values += 1;
165            }
166            vec[i] = Some(v);
167        }
168        Self { vec, num_values }
169    }
170}
171
172impl<T> Extend<(usize, T)> for OptionVec<T> {
173    fn extend<I: IntoIterator<Item = (usize, T)>>(&mut self, iterable: I) {
174        for (i, v) in iterable.into_iter() {
175            if i >= self.vec.len() {
176                let additional = i - self.vec.len() + 1;
177                self.vec.reserve(additional);
178                self.vec
179                    .extend(std::iter::repeat_with(|| None).take(additional));
180            }
181            if self.vec[i].is_none() {
182                self.num_values += 1;
183            }
184            self.vec[i] = Some(v);
185        }
186    }
187}
188
189impl<T> Index<usize> for OptionVec<T> {
190    type Output = T;
191    fn index(&self, index: usize) -> &Self::Output {
192        self.get(index).expect("index not found")
193    }
194}
195
196impl<T> IndexMut<usize> for OptionVec<T> {
197    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
198        self.get_mut(index).expect("index not found")
199    }
200}
201
202impl<'a, T> IntoIterator for &'a OptionVec<T> {
203    type Item = (usize, &'a T);
204    type IntoIter = Iter<'a, T>;
205    fn into_iter(self) -> Self::IntoIter {
206        Self::IntoIter {
207            size: self.size(),
208            vec_iter: self.vec.iter().enumerate(),
209        }
210    }
211}
212
213impl<'a, T> IntoIterator for &'a mut OptionVec<T> {
214    type Item = (usize, &'a mut T);
215    type IntoIter = IterMut<'a, T>;
216    fn into_iter(self) -> Self::IntoIter {
217        Self::IntoIter {
218            size: self.size(),
219            vec_iter: self.vec.iter_mut().enumerate(),
220        }
221    }
222}
223
224impl<'a, T> Iterator for Iter<'a, T> {
225    type Item = (usize, &'a T);
226    fn next(&mut self) -> Option<Self::Item> {
227        for (index, element) in &mut self.vec_iter {
228            if let Some(element) = element {
229                self.size -= 1;
230                return Some((index, element));
231            }
232        }
233        None
234    }
235}
236
237impl<T> DoubleEndedIterator for Iter<'_, T> {
238    fn next_back(&mut self) -> Option<Self::Item> {
239        while let Some((index, element)) = self.vec_iter.next_back() {
240            if let Some(element) = element {
241                self.size -= 1;
242                return Some((index, element));
243            }
244        }
245        None
246    }
247}
248
249impl<T> ExactSizeIterator for Iter<'_, T> {
250    fn len(&self) -> usize {
251        self.size
252    }
253}
254
255impl<T> FusedIterator for Iter<'_, T> {}
256
257impl<'a, T> Iterator for IterMut<'a, T> {
258    type Item = (usize, &'a mut T);
259    fn next(&mut self) -> Option<Self::Item> {
260        for (index, element) in &mut self.vec_iter {
261            if let Some(element) = element {
262                self.size -= 1;
263                return Some((index, element));
264            }
265        }
266        None
267    }
268}
269
270impl<T> DoubleEndedIterator for IterMut<'_, T> {
271    fn next_back(&mut self) -> Option<Self::Item> {
272        while let Some((index, element)) = self.vec_iter.next_back() {
273            if let Some(element) = element {
274                self.size -= 1;
275                return Some((index, element));
276            }
277        }
278        None
279    }
280}
281
282impl<T> ExactSizeIterator for IterMut<'_, T> {
283    fn len(&self) -> usize {
284        self.size
285    }
286}
287
288impl<T> FusedIterator for IterMut<'_, T> {}
289
290impl<T> Clone for Iter<'_, T> {
291    fn clone(&self) -> Self {
292        Self {
293            size: self.size,
294            vec_iter: self.vec_iter.clone(),
295        }
296    }
297}
298
299impl<'de, T> serde::de::Visitor<'de> for Visitor<T>
300where
301    T: serde::Deserialize<'de>,
302{
303    type Value = OptionVec<T>;
304
305    fn expecting(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
306        formatter.write_str("a key-value mapping")
307    }
308
309    fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
310    where
311        A: serde::de::MapAccess<'de>,
312    {
313        std::iter::from_fn(|| map.next_entry().transpose()).collect()
314    }
315}
316
317impl<'de, T> serde::Deserialize<'de> for OptionVec<T>
318where
319    T: serde::Deserialize<'de>,
320{
321    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
322    where
323        D: serde::Deserializer<'de>,
324    {
325        deserializer.deserialize_map(Visitor(std::marker::PhantomData))
326    }
327}
328
329impl<T> serde::Serialize for OptionVec<T>
330where
331    T: serde::Serialize,
332{
333    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
334    where
335        S: serde::Serializer,
336    {
337        let mut ser = serializer.serialize_map(Some(self.size()))?;
338        for (index, element) in self {
339            ser.serialize_key(&index)?;
340            ser.serialize_value(element)?;
341        }
342        ser.end()
343    }
344}
345
346impl<'de, T> alox_48::Visitor<'de> for Visitor<T>
347where
348    T: alox_48::Deserialize<'de>,
349{
350    type Value = OptionVec<T>;
351
352    fn expecting(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
353        formatter.write_str("a key-value mapping")
354    }
355
356    fn visit_hash<A>(self, mut map: A) -> Result<Self::Value, alox_48::DeError>
357    where
358        A: alox_48::HashAccess<'de>,
359    {
360        std::iter::from_fn(|| map.next_entry().transpose()).collect()
361    }
362}
363
364impl<'de, T> alox_48::Deserialize<'de> for OptionVec<T>
365where
366    T: alox_48::Deserialize<'de>,
367{
368    fn deserialize<D>(deserializer: D) -> Result<Self, alox_48::DeError>
369    where
370        D: alox_48::DeserializerTrait<'de>,
371    {
372        deserializer.deserialize(Visitor(std::marker::PhantomData))
373    }
374}
375
376impl<T> alox_48::Serialize for OptionVec<T>
377where
378    T: alox_48::Serialize,
379{
380    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, alox_48::SerError>
381    where
382        S: alox_48::SerializerTrait,
383    {
384        let mut ser = serializer.serialize_hash(self.size())?;
385        for (index, element) in self {
386            ser.serialize_key(&index)?;
387            ser.serialize_value(element)?;
388        }
389        ser.end()
390    }
391}
luminol_data/option_vec.rs

luminol_data/
option_vec.rs
