lazy_cogs/collections/
vec.rs

1use std::{mem, ops::{Index, IndexMut}};
2
3use crate::{lazy::LazyClone, lc::Lc};
4
5#[derive(Debug)]
6/// lazy-cogs implementation of a Vector. 
7/// It's a collection meant to be used when you need to work with the individual elements
8/// 
9/// Cloning a LazyVec is always O(1). Getting elements from it is also O(1)
10/// 
11/// Modifing existing elements may take O(n) if the vector is a clone that is still modified, 
12/// or if it has living clones.
13/// 
14/// Pushing elements follow the same logic
15pub struct LazyVec<T: Clone> { 
16    vec: Lc<Vec<Lc<T>>>,
17}
18
19impl<T: Clone> LazyVec<T> {
20    /// Creates a new empty LazyVec
21    pub fn new() -> Self {
22        Self{
23            vec: Lc::new(Vec::new())
24        }
25    }
26
27    /// Obtains a reference to a specific value in the lazy vector
28    /// 
29    /// If the index is out of range it returns `None`
30    /// 
31    /// This operation is **always** O(1)
32    pub fn get(&self, index: usize) -> Option<&T> {
33        let vec = self.vec.read();
34        
35        vec.get(index).map(Lc::read)
36    }
37
38    /// Obtains a mutable reference to a specific value in the lazy vector
39    /// 
40    /// If the index is out of range it returns `None`
41    /// 
42    /// This operation is protected, it means, that the other clones aren't affected
43    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
44        let vec = self.vec.read_mut();
45        
46        vec.get_mut(index).map(Lc::read_mut)
47    }
48
49    #[inline(always)]
50    /// Obtains a lazy clone to a specific value in the lazy vector
51    /// 
52    /// If the index is out of range it returns `None`
53    pub fn get_lazy(&self, index: usize) -> Option<Lc<T>> {
54        self.vec.get(index).cloned()
55    }
56
57    /// Updates an item in the current vector
58    /// 
59    /// The operation coast dependents on the state of the vector:
60    /// - If vector was never modified, this costs O(n)
61    /// - If it was modified but some one cloned it, it's also O(n)
62    /// - If it was modified and no one cloned it, it's O(1)
63    /// - If it isn't cloned from other vector and no one cloned it, it's O(1)
64    pub fn set(&mut self, index: usize, value: T) -> Result<(), ()>{
65        let mut vec = if self.is_mutable() {
66            // We can modify ourselves with no side effects
67            unsafe { 
68                mem::replace(
69                    &mut self.vec,
70                    Lc::new(Vec::new()))
71                .destroy() 
72            }
73
74        } else {
75            // We need to clone the vector so we don't mess with other clones
76            self.vec.take()
77        };
78
79        let res = match vec.get_mut(index) {
80            Some(elem) => {
81                elem.write(value);
82                Ok(())
83            },
84            None => Err(()),
85        };
86    
87        // Put the modified vector back in the structure
88        self.vec = Lc::new(vec);
89    
90        res
91    }
92
93    /// Pushes a new element at the end of the vector
94    pub fn push(&mut self, value: T) {
95        let mut vec = if self.is_mutable() {
96            unsafe {
97                mem::replace(
98                    &mut self.vec, 
99                    Lc::new(Vec::new()))
100                    .destroy()
101            }
102        } else {
103            self.vec.take()
104        };
105        
106        vec.push(Lc::new(value));
107        self.vec = Lc::new(vec);
108    }
109
110    /// Pops an element at the end of the vector
111    pub fn pop(&mut self) -> Option<T> {
112        let mut vec = if self.is_mutable() {
113            unsafe {
114                mem::replace(
115                    &mut self.vec, 
116                    Lc::new(Vec::new()))
117                    .destroy()
118            }
119        } else {
120            self.vec.take()
121        };
122        
123        let res = vec.pop();
124        self.vec = Lc::new(vec);
125        res.map(Lc::unwrap)
126    }
127
128    #[inline(always)]
129    /// Removes an element from the vector
130    pub fn remove(&mut self, index: usize) -> T {
131        self.remove_lazy(index).unwrap()
132    }
133
134    /// Removes an element from the vector and returns a lazy clone to it
135    pub fn remove_lazy(&mut self, index: usize) -> Lc<T> {
136        let mut vec = mem::replace(&mut self.vec, Lc::new(vec![])).unwrap();
137        let res = vec.remove(index);
138
139        self.vec = Lc::new(vec);
140
141        res
142    }
143
144    /// Inserts an element at a given position in a vector
145    pub fn insert(&mut self, index: usize, value: T) {
146        let mut vec = mem::replace(&mut self.vec, Lc::new(vec![])).unwrap();
147        vec.insert(index, value.into());
148
149        self.vec = Lc::new(vec);
150    }
151
152    /// Produces an iterator over the elements
153    pub fn iter(&self) -> impl Iterator<Item = &T> {
154        let vec = self.vec.read();
155        vec.iter().map(Lc::read)
156    }
157
158    /// Produces a mutable iterator
159    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
160        let vec = self.vec.read_mut();
161        vec.iter_mut().map(Lc::read_mut)
162    }
163}
164
165impl<T: Clone> LazyClone for LazyVec<T> {
166    #[inline(always)]
167    fn lazy(&self) -> Self {
168        Self { 
169            vec: self.vec.lazy()
170        }
171    }
172    
173    #[inline(always)]
174    fn eager(&self) -> Self {
175        Self { 
176            vec: self.vec.eager()
177        }
178    }
179
180    #[inline(always)]
181    fn is_mutable(&self) -> bool {
182        self.vec.is_mutable()
183    }
184}
185
186impl<T: Clone> From<Vec<Lc<T>>> for LazyVec<T> {
187    fn from(value: Vec<Lc<T>>) -> Self {
188        Self { 
189            vec: Lc::new(value) 
190        }
191    }
192}
193
194impl<T: Clone> From<Vec<T>> for LazyVec<T> {
195    fn from(value: Vec<T>) -> Self {
196        Self {
197            vec: Lc::new(value.into_iter()
198                .map(Lc::new)
199                .collect()
200            ),
201        }
202    }
203}
204
205impl<T: Clone> From<&[T]> for LazyVec<T> {
206    fn from(value: &[T]) -> Self {
207        value.to_vec().into()
208    }
209}
210
211impl<T: Clone> Into<Vec<Lc<T>>> for LazyVec<T> {
212    fn into(self) -> Vec<Lc<T>> {
213        self.vec.unwrap()
214            .into_iter()
215            .collect()
216    }
217}
218
219impl<T: Clone> Into<Vec<T>> for LazyVec<T> {
220    fn into(self) -> Vec<T> {
221        self.vec.unwrap()
222            .into_iter()
223            .map(|elem| elem.unwrap())
224            .collect()
225    }
226}
227
228impl<T: Clone> FromIterator<T> for LazyVec<T> {
229    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
230        Vec::from_iter(iter).into()
231    }
232}
233
234impl<T: Clone> IntoIterator for LazyVec<T> {
235    type Item = T;
236    type IntoIter = std::vec::IntoIter<T>;
237
238    fn into_iter(self) -> Self::IntoIter {
239        self.vec.take()
240            .into_iter()
241            .map(Lc::unwrap)
242            .collect::<Vec<T>>().into_iter()
243    }
244}
245
246impl<T: Clone> Index<usize> for LazyVec<T> {
247    type Output = T;
248
249    fn index(&self, index: usize) -> &Self::Output {
250        self.get(index).unwrap()
251    }
252}
253
254impl<T: Clone> IndexMut<usize> for LazyVec<T> {
255    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
256        self.get_mut(index).unwrap()
257    }
258}
259
260#[cfg(test)]
261mod tests {
262    use std::iter::zip;
263
264    use crate::lazy::LazyClone;
265
266    use super::LazyVec;
267
268    #[test]
269    fn create() {
270        let mut lv = LazyVec::<Box<str>>::from(&["Hello".into(), "World".into(), "Take".into(), "a look at this".into()] as &[Box<str>]);
271        let mut lv2 = lv.lazy();
272        let mut lv3 = lv2.lazy();
273
274        let _ = lv.set(0, "Bye".into());
275        let _ = lv2.set(2, "Give".into());
276        let _ = lv3.set(1, "Värld".into());
277
278        // Check if the boxes are the same, so we are safely reusing memory
279        assert_eq!(lv.get(1).unwrap().as_ref() as *const str, lv2.get(1).unwrap().as_ref() as *const str);
280        // Check if the boxes are not the same, so we cloned what was needed
281        assert_ne!(lv.get(1).unwrap().as_ref() as *const str, lv3.get(1).unwrap().as_ref() as *const str);
282    }
283
284    #[test]
285    #[allow(unused_mut)]
286    #[allow(unused_results)]
287    #[allow(unused_must_use)]
288    fn mutability_check() {
289        let mut lv = LazyVec::from(vec!["HI", "Goodbye", "Farwell", "Hello"]);
290        let mut lv2 = lv.lazy();
291        let mut lv3 = lv2.lazy();
292        let mut lv4 = lv2.lazy();
293        
294        lv2.set(3, "Halo");
295        lv.set(0, "Hej");
296
297        assert!(lv.is_mutable());
298        assert!(lv2.is_mutable());
299        assert!(!lv3.is_mutable());
300        assert!(!lv4.is_mutable());
301
302        for e in zip(zip(lv.iter(), lv2.iter()), zip(lv3.iter(), lv4.iter())) {
303            println!("{:?} : {:?} : {:?} : {:?}", e.0.0.as_ptr(), e.0.1.as_ptr(), e.1.0.as_ptr(), e.1.1.as_ptr())
304        }
305    }
306
307    #[test]
308    fn iterators() {
309        let lv = LazyVec::from([String::from("rust"), String::from("mojo"), String::from("zig"), String::from("carbon"),String::from("aura")].to_vec());
310
311        lv.iter()
312            .map(|elem| elem.to_uppercase())
313            .for_each(|elem| println!("{:?}", elem));
314
315        lv.into_iter()
316            .map(|elem| elem
317                .chars()
318                .rev()
319                .collect::<String>()
320            )
321            .for_each(|elem| println!("{:?}", elem));
322    }
323
324    #[test]
325    fn collecting() {
326        let v = vec!["Hi", "my", "name", "is", "something"];
327        let lv: LazyVec<_> = v.into_iter()
328            .collect();
329
330        dbg!(lv);
331    }
332}
lazy_cogs/collections/vec.rs

lazy_cogs/collections/
vec.rs
