ferrijs_std/utils/
reuse_list.rs

1use std::fmt::Debug;
2
3#[derive(Default, Clone)]
4pub struct ReuseList<T> {
5    items: Vec<Option<T>>,
6    slots: Vec<usize>,
7    last_slot_idx: usize,
8    len: usize,
9    slot_size: usize,
10}
11
12impl<T: Debug> Debug for ReuseList<T> {
13    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
14        f.debug_struct("ReuseList")
15            .field("items", &self.items)
16            .field("slots", &self.slots)
17            .finish()
18    }
19}
20
21impl<T> ReuseList<T> {
22    pub fn new() -> Self {
23        Self::with_capacity(0)
24    }
25
26    //is empty
27    pub fn is_empty(&self) -> bool {
28        self.len == 0
29    }
30
31    //create a with capacity
32    pub fn with_capacity(capacity: usize) -> Self {
33        Self {
34            items: Vec::with_capacity(capacity),
35            slots: Vec::with_capacity(capacity >> 2),
36            last_slot_idx: 0,
37            len: 0,
38            slot_size: 0,
39        }
40    }
41
42    pub fn append(&mut self, item: T) -> usize {
43        if self.slot_size > 0 {
44            //reuse empty slot if valid
45            let slot = self.slots[self.last_slot_idx - 1];
46            if slot > 0 {
47                self.items[slot - 1] = Some(item);
48                self.slots[self.last_slot_idx - 1] = 0;
49                if self.last_slot_idx > 1 {
50                    self.last_slot_idx -= 1;
51                }
52
53                self.len += 1;
54                return slot - 1;
55            }
56        }
57        //no valid empty slots, append to end
58        self.items.push(Some(item));
59        self.len += 1;
60        self.items.len() - 1
61    }
62
63    pub fn remove(&mut self, index: usize) -> Option<T> {
64        if index >= self.items.len() {
65            return None;
66        }
67
68        let item = self.items[index].take();
69        if item.is_some() {
70            if self.slot_size > 0 && self.slots[self.last_slot_idx - 1] == 0 {
71                self.slots[self.last_slot_idx - 1] = index + 1;
72            } else {
73                self.slots.push(index + 1);
74                self.last_slot_idx += 1;
75                self.slot_size += 1;
76            }
77            self.len -= 1;
78        }
79        item
80    }
81
82    pub fn get(&self, index: usize) -> Option<&T> {
83        if index >= self.items.len() {
84            None
85        } else {
86            self.items[index].as_ref()
87        }
88    }
89
90    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
91        if index >= self.items.len() {
92            None
93        } else {
94            self.items[index].as_mut()
95        }
96    }
97
98    pub fn capacity(&self) -> usize {
99        self.items.capacity()
100    }
101
102    pub fn len(&self) -> usize {
103        self.len
104    }
105
106    pub fn iter(&self) -> impl Iterator<Item = &T> {
107        self.items.iter().filter_map(|x| x.as_ref())
108    }
109
110    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
111        self.items.iter_mut().filter_map(|x| x.as_mut())
112    }
113
114    //implement clear
115    pub fn clear(&mut self) {
116        self.items.clear();
117        self.slots.clear();
118        self.last_slot_idx = 0;
119        self.len = 0;
120        self.slot_size = 0;
121    }
122
123    pub fn optimize(&mut self) {
124        let mut new_items = Vec::with_capacity(self.len);
125
126        for item in self.items.iter_mut() {
127            let a = item.take();
128            if a.is_some() {
129                new_items.push(a);
130            }
131        }
132        self.items = new_items;
133        self.slots.clear();
134        self.last_slot_idx = 0;
135        self.slot_size = 0;
136    }
137}
138
139#[cfg(test)]
140mod tests {
141    use super::*;
142
143    #[test]
144    fn test_new() {
145        let list: ReuseList<i32> = ReuseList::new();
146        assert_eq!(list.len(), 0);
147        assert_eq!(list.capacity(), 0);
148        assert_eq!(list.items.len(), 0);
149        assert_eq!(list.slots.len(), 0);
150    }
151
152    #[test]
153    fn test_with_capacity() {
154        let list: ReuseList<i32> = ReuseList::with_capacity(10);
155        assert_eq!(list.len(), 0);
156        assert_eq!(list.capacity(), 10);
157        assert_eq!(list.items.len(), 0);
158        assert_eq!(list.slots.len(), 0);
159    }
160
161    #[test]
162    fn test_append() {
163        let mut list = ReuseList::new();
164        assert_eq!(list.append(1), 0);
165        assert_eq!(list.append(2), 1);
166        assert_eq!(list.append(3), 2);
167        assert_eq!(list.len(), 3);
168
169        let items: Vec<i32> = list.iter().cloned().collect();
170        assert_eq!(items, vec![1, 2, 3]);
171        assert_eq!(list.items, vec![Some(1), Some(2), Some(3)]);
172        assert_eq!(list.slots, vec![]);
173    }
174
175    #[test]
176    fn test_remove() {
177        let mut list = ReuseList::new();
178        list.append(1);
179        list.append(2);
180        list.append(3);
181
182        assert_eq!(list.remove(1), Some(2));
183        assert_eq!(list.len(), 2);
184
185        let items: Vec<i32> = list.iter().cloned().collect();
186        assert_eq!(items, vec![1, 3]);
187        assert_eq!(list.items, vec![Some(1), None, Some(3)]);
188        assert_eq!(list.slots, vec![2]);
189
190        assert_eq!(list.remove(5), None);
191    }
192
193    #[test]
194    fn test_reuse_slots() {
195        let mut list = ReuseList::new();
196        list.append(1);
197        list.append(2);
198        list.append(3);
199
200        list.remove(1); // Remove 2
201        assert_eq!(list.append(4), 1); // Should reuse index 1
202
203        let items: Vec<i32> = list.iter().cloned().collect();
204        assert_eq!(items, vec![1, 4, 3]);
205        assert_eq!(list.items, vec![Some(1), Some(4), Some(3)]);
206        assert_eq!(list.slots, vec![0]);
207    }
208
209    #[test]
210    fn test_get() {
211        let mut list = ReuseList::new();
212        list.append(1);
213        list.append(2);
214
215        assert_eq!(list.get(0), Some(&1));
216        assert_eq!(list.get(1), Some(&2));
217        assert_eq!(list.get(2), None);
218        assert_eq!(list.items, vec![Some(1), Some(2)]);
219        assert_eq!(list.slots, vec![]);
220    }
221
222    #[test]
223    fn test_get_mut() {
224        let mut list = ReuseList::new();
225        list.append(1);
226        list.append(2);
227
228        if let Some(value) = list.get_mut(0) {
229            *value = 10;
230        }
231
232        assert_eq!(list.get(0), Some(&10));
233        assert_eq!(list.items, vec![Some(10), Some(2)]);
234        assert_eq!(list.slots, vec![]);
235    }
236
237    #[test]
238    fn test_iter() {
239        let mut list = ReuseList::new();
240        list.append(1);
241        list.append(2);
242        list.append(3);
243        list.remove(1);
244
245        let items: Vec<i32> = list.iter().cloned().collect();
246        assert_eq!(items, vec![1, 3]);
247        assert_eq!(list.items, vec![Some(1), None, Some(3)]);
248        assert_eq!(list.slots, vec![2]);
249    }
250
251    #[test]
252    fn test_iter_mut() {
253        let mut list = ReuseList::new();
254        list.append(1);
255        list.append(2);
256        list.append(3);
257
258        for item in list.iter_mut() {
259            *item *= 2;
260        }
261
262        let items: Vec<i32> = list.iter().cloned().collect();
263        assert_eq!(items, vec![2, 4, 6]);
264        assert_eq!(list.items, vec![Some(2), Some(4), Some(6)]);
265        assert_eq!(list.slots, vec![]);
266    }
267
268    #[test]
269    fn test_multiple_removes() {
270        let mut list = ReuseList::new();
271        for i in 0..5 {
272            list.append(i);
273        }
274
275        list.remove(1);
276        list.remove(3);
277
278        let items: Vec<i32> = list.iter().cloned().collect();
279        assert_eq!(items, vec![0, 2, 4]);
280        assert_eq!(list.items, vec![Some(0), None, Some(2), None, Some(4)]);
281        assert_eq!(list.slots, vec![2, 4]);
282
283        // Test reuse of both slots
284        list.append(10);
285        list.append(11);
286
287        let items: Vec<i32> = list.iter().cloned().collect();
288        assert_eq!(items, vec![0, 11, 2, 10, 4]);
289        assert_eq!(
290            list.items,
291            vec![Some(0), Some(11), Some(2), Some(10), Some(4)]
292        );
293        assert_eq!(list.slots, vec![0, 0]);
294
295        list.remove(0);
296
297        let items: Vec<i32> = list.iter().cloned().collect();
298        assert_eq!(items, vec![11, 2, 10, 4]);
299        assert_eq!(list.items, vec![None, Some(11), Some(2), Some(10), Some(4)]);
300        assert_eq!(list.slots, vec![1, 0]);
301
302        list.append(20);
303
304        let items: Vec<i32> = list.iter().cloned().collect();
305        assert_eq!(items, vec![20, 11, 2, 10, 4]);
306        assert_eq!(
307            list.items,
308            vec![Some(20), Some(11), Some(2), Some(10), Some(4)]
309        );
310        assert_eq!(list.slots, vec![0, 0]);
311
312        //remove all items
313        list.clear();
314    }
315
316    #[test]
317    fn test_optimize() {
318        let mut list = ReuseList::new();
319        list.append(1);
320        list.append(2);
321        list.append(3);
322        list.remove(1);
323
324        assert_eq!(list.items, vec![Some(1), None, Some(3)]);
325        assert_eq!(list.slots, vec![2]);
326
327        list.optimize();
328
329        assert_eq!(list.items, vec![Some(1), Some(3)]);
330        assert_eq!(list.slots, vec![]);
331        assert_eq!(list.last_slot_idx, 0);
332        assert_eq!(list.slot_size, 0);
333
334        let items: Vec<i32> = list.iter().cloned().collect();
335        assert_eq!(items, vec![1, 3]);
336    }
337}
ferrijs_std/utils/reuse_list.rs

ferrijs_std/utils/
reuse_list.rs
