pathgraph/
lib.rs

1use core::fmt;
2
3pub struct PathGraphEntry<V> {
4    value: Option<V>,
5    items: Vec<PathGraphEntry<V>>,
6}
7
8impl<V: fmt::Debug> fmt::Debug for PathGraphEntry<V> {
9    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
10        f.debug_struct("PathGraphEntry")
11            .field("value", &self.value)
12            .field("items", &self.items)
13            .finish()
14    }
15}
16
17impl<V> PathGraphEntry<V> {
18    pub fn insert(&mut self, path: &[u32], value: V) {
19        if path.is_empty() {
20            self.value = Some(value);
21        } else {
22            match self.items.get(path[0] as usize) {
23                None => {
24                    self.items.resize_with(path[0] as usize + 1, || Self {
25                        value: None,
26                        items: Vec::new(),
27                    });
28                }
29                // Only shift on collision with a real sibling; empty
30                // placeholders from prior moves are filled in place.
31                Some(existing) if path.len() == 1 && existing.value.is_some() => {
32                    self.items.insert(
33                        path[0] as usize,
34                        Self {
35                            value: None,
36                            items: Vec::new(),
37                        },
38                    );
39                }
40                _ => {}
41            }
42            self.items[path[0] as usize].insert(&path[1..], value)
43        }
44    }
45
46    pub fn insert_entry(&mut self, path: &[u32], entry: PathGraphEntry<V>) {
47        if path.is_empty() {
48            *self = entry;
49        } else {
50            match self.items.get(path[0] as usize) {
51                None => {
52                    self.items.resize_with(path[0] as usize + 1, || Self {
53                        value: None,
54                        items: Vec::new(),
55                    });
56                }
57                Some(existing) if path.len() == 1 && existing.value.is_some() => {
58                    self.items.insert(
59                        path[0] as usize,
60                        Self {
61                            value: None,
62                            items: Vec::new(),
63                        },
64                    );
65                }
66                _ => {}
67            }
68            self.items[path[0] as usize].insert_entry(&path[1..], entry)
69        }
70    }
71
72    pub fn remove(&mut self, path: &[u32]) -> Option<PathGraphEntry<V>> {
73        if path.is_empty() {
74            unreachable!()
75        } else if path.len() == 1 {
76            if path[0] as usize >= self.items.len() {
77                self.items.pop()
78            } else {
79                Some(self.items.remove(path[0] as usize))
80            }
81        } else if let Some(item) = self.items.get_mut(path[0] as usize) {
82            item.remove(&path[1..])
83        } else {
84            None
85        }
86    }
87
88    pub fn find_path(
89        &self,
90        path: Vec<u32>,
91        finder: &impl Fn(Option<&V>) -> bool,
92    ) -> Option<Vec<u32>> {
93        if finder(self.value.as_ref()) {
94            return Some(path);
95        }
96        for (i, item) in self.items.iter().enumerate() {
97            let mut path = path.clone();
98            path.push(i as u32);
99            if let Some(path) = item.find_path(path, finder) {
100                return Some(path);
101            }
102        }
103        None
104    }
105
106    pub fn find(&self, path: Vec<u32>, finder: &impl Fn(Option<&V>) -> bool) -> Option<&V> {
107        if finder(self.value.as_ref()) {
108            return self.value.as_ref();
109        }
110        for (i, item) in self.items.iter().enumerate() {
111            let mut path = path.clone();
112            path.push(i as u32);
113            if let Some(res) = item.find(path, finder) {
114                return Some(res);
115            }
116        }
117        None
118    }
119
120    pub fn reduce<A>(
121        &self,
122        acc: &mut A,
123        path: Vec<u32>,
124        reducer: &impl Fn(Option<&V>, &[u32], &mut A) -> bool,
125    ) -> bool {
126        if reducer(self.value.as_ref(), &path, acc) {
127            return true;
128        }
129        for (i, item) in self.items.iter().enumerate() {
130            let mut path = path.clone();
131            path.push(i as u32);
132            if item.reduce(acc, path, reducer) {
133                return true;
134            }
135        }
136        false
137    }
138
139    pub fn find_child_path(
140        &self,
141        path: Vec<u32>,
142        target: &[u32],
143        finder: &impl Fn(Option<&V>) -> bool,
144    ) -> Option<Vec<u32>> {
145        if !path.is_empty() && &path[0..path.len() - 1] == target && finder(self.value.as_ref()) {
146            return Some(path);
147        }
148        for (i, item) in self.items.iter().enumerate() {
149            let mut path = path.clone();
150            path.push(i as u32);
151            if let Some(path) = item.find_child_path(path, target, finder) {
152                return Some(path);
153            }
154        }
155        None
156    }
157
158    pub fn get(&self, path: &[u32]) -> Option<&V> {
159        if path.is_empty() {
160            self.value.as_ref()
161        } else if let Some(item) = self.items.get(path[0] as usize) {
162            item.get(&path[1..])
163        } else {
164            None
165        }
166    }
167
168    pub fn len(&self, path: &[u32]) -> Option<usize> {
169        if path.is_empty() {
170            Some(self.items.len())
171        } else if let Some(item) = self.items.get(path[0] as usize) {
172            item.len(&path[1..])
173        } else {
174            None
175        }
176    }
177
178    pub fn size(&self, size: &mut usize) {
179        if self.value.is_some() {
180            *size += 1;
181        }
182
183        for item in &self.items {
184            item.size(size);
185        }
186    }
187
188    pub fn traverse(
189        &self,
190        target: &[u32],
191        mut path: Vec<u32>,
192        traverser: &mut impl FnMut(&[u32], &V),
193    ) {
194        if path.starts_with(target)
195            && let Some(value) = self.value.as_ref()
196        {
197            traverser(&path, value);
198        }
199
200        for (i, item) in self.items.iter().enumerate() {
201            path.push(i as u32);
202            if target.starts_with(&path) || path.starts_with(target) {
203                item.traverse(target, path.clone(), traverser);
204            }
205            path.pop();
206        }
207    }
208
209    pub fn retain(
210        &mut self,
211        target: &[u32],
212        parent_is_retained: bool,
213        mut path: Vec<u32>,
214        retainer: &mut impl FnMut(&[u32], &V) -> bool,
215        traverser: &mut impl FnMut(&[u32], &V),
216    ) -> bool {
217        let mut retain = parent_is_retained;
218        if path.starts_with(target)
219            && let Some(value) = self.value.as_ref()
220        {
221            if parent_is_retained {
222                retain = retainer(&path, value);
223            }
224
225            if !retain {
226                traverser(&path, value);
227            }
228        }
229
230        let mut i = 0;
231        self.items.retain_mut(|item| {
232            let mut retain = retain;
233            path.push(i as u32);
234            if target.starts_with(&path) || path.starts_with(target) {
235                retain = item.retain(target, retain, path.clone(), retainer, traverser);
236            }
237            path.pop();
238            i += 1;
239            retain
240        });
241        retain
242    }
243
244    pub fn traverse_1_level(
245        &self,
246        target: &[u32],
247        mut path: Vec<u32>,
248        traverser: &mut impl FnMut(&[u32], &V),
249    ) {
250        if path == target {
251            for (i, item) in self.items.iter().enumerate() {
252                if let Some(value) = item.value.as_ref() {
253                    path.push(i as u32);
254                    traverser(&path, value);
255                    path.pop();
256                }
257            }
258        } else {
259            for (i, item) in self.items.iter().enumerate() {
260                path.push(i as u32);
261                item.traverse_1_level(target, path.clone(), traverser);
262                path.pop();
263            }
264        }
265    }
266
267    pub fn value(self) -> Option<V> {
268        self.value
269    }
270}
271
272pub struct PathGraph<V> {
273    entry: Option<PathGraphEntry<V>>,
274}
275
276impl<V> Default for PathGraph<V> {
277    fn default() -> Self {
278        Self::new()
279    }
280}
281
282impl<V: fmt::Debug> fmt::Debug for PathGraph<V> {
283    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
284        f.debug_struct("PathGraph")
285            .field("entry", &self.entry)
286            .finish()
287    }
288}
289
290impl<V> PathGraph<V> {
291    pub fn new() -> Self {
292        Self { entry: None }
293    }
294
295    pub fn insert(&mut self, path: &[u32], value: V) {
296        if let Some(entry) = &mut self.entry {
297            entry.insert(path, value);
298        } else {
299            let mut entry = PathGraphEntry {
300                value: None,
301                items: Vec::new(),
302            };
303            entry.insert(path, value);
304            self.entry = Some(entry);
305        }
306    }
307
308    pub fn insert_entry(&mut self, path: &[u32], entry: PathGraphEntry<V>) {
309        if let Some(root_entry) = &mut self.entry {
310            root_entry.insert_entry(path, entry);
311        } else {
312            let mut root_entry = PathGraphEntry {
313                value: None,
314                items: Vec::new(),
315            };
316            root_entry.insert_entry(path, entry);
317            self.entry = Some(root_entry);
318        }
319    }
320
321    pub fn remove(&mut self, path: &[u32]) -> Option<PathGraphEntry<V>> {
322        if let Some(entry) = &mut self.entry {
323            entry.remove(path)
324        } else {
325            None
326        }
327    }
328
329    pub fn find_path(&self, finder: impl Fn(Option<&V>) -> bool) -> Option<Vec<u32>> {
330        if let Some(entry) = &self.entry {
331            entry.find_path(vec![], &finder)
332        } else {
333            None
334        }
335    }
336
337    pub fn find(&self, finder: impl Fn(Option<&V>) -> bool) -> Option<&V> {
338        if let Some(entry) = &self.entry {
339            entry.find(vec![], &finder)
340        } else {
341            None
342        }
343    }
344
345    pub fn reduce<A>(
346        &self,
347        acc: &mut A,
348        reducer: impl Fn(Option<&V>, &[u32], &mut A) -> bool,
349    ) -> bool {
350        if let Some(entry) = &self.entry {
351            entry.reduce(acc, vec![], &reducer)
352        } else {
353            false
354        }
355    }
356
357    pub fn find_child_path(
358        &self,
359        target: &[u32],
360        finder: impl Fn(Option<&V>) -> bool,
361    ) -> Option<Vec<u32>> {
362        if let Some(entry) = &self.entry {
363            entry.find_child_path(vec![], target, &finder)
364        } else {
365            None
366        }
367    }
368
369    pub fn len(&self, path: &[u32]) -> Option<usize> {
370        if let Some(entry) = &self.entry {
371            entry.len(path)
372        } else {
373            None
374        }
375    }
376
377    pub fn get(&self, path: &[u32]) -> Option<&V> {
378        if let Some(entry) = &self.entry {
379            entry.get(path)
380        } else {
381            None
382        }
383    }
384
385    pub fn size(&self) -> usize {
386        let mut size = 0;
387        if let Some(entry) = &self.entry {
388            entry.size(&mut size);
389        }
390        size
391    }
392
393    pub fn traverse(&self, target: &[u32], mut traverser: impl FnMut(&[u32], &V)) {
394        if let Some(entry) = &self.entry {
395            entry.traverse(target, vec![], &mut traverser);
396        }
397    }
398
399    pub fn retain(
400        &mut self,
401        target: &[u32],
402        mut retainer: impl FnMut(&[u32], &V) -> bool,
403        mut traverser: impl FnMut(&[u32], &V),
404    ) {
405        if let Some(entry) = &mut self.entry
406            && !entry.retain(target, true, vec![], &mut retainer, &mut traverser)
407        {
408            let _ = self.entry.take();
409        }
410    }
411
412    pub fn traverse_1_level(&self, target: &[u32], mut traverser: impl FnMut(&[u32], &V)) {
413        if let Some(entry) = &self.entry {
414            entry.traverse_1_level(target, vec![], &mut traverser);
415        }
416    }
417}
418
419#[cfg(test)]
420mod tests {
421    use super::*;
422
423    /// An `insert` targeting a placeholder left by a prior `remove` +
424    /// `insert_entry` pair must fill it in place instead of shifting siblings.
425    #[test]
426    fn insert_fills_placeholder_left_by_move_sequence() {
427        let mut graph = PathGraph::<u32>::new();
428        graph.insert(&[], 0);
429        graph.insert(&[0], 10);
430        graph.insert(&[0, 0], 100);
431        graph.insert(&[0, 1], 200);
432
433        let a = graph.remove(&[0, 1]).unwrap();
434        graph.insert_entry(&[0, 0], a);
435        let b = graph.remove(&[0, 1]).unwrap();
436        graph.insert_entry(&[0, 2], b);
437
438        assert_eq!(graph.get(&[0, 0]), Some(&200));
439        assert_eq!(graph.get(&[0, 1]), None);
440        assert_eq!(graph.get(&[0, 2]), Some(&100));
441
442        graph.insert(&[0, 1], 999);
443
444        assert_eq!(graph.get(&[0, 0]), Some(&200));
445        assert_eq!(graph.get(&[0, 1]), Some(&999));
446        assert_eq!(graph.get(&[0, 2]), Some(&100));
447        assert_eq!(graph.get(&[0, 3]), None);
448        assert_eq!(graph.len(&[0]), Some(3));
449    }
450
451    /// `insert` still shifts when the target slot holds a real sibling.
452    #[test]
453    fn insert_still_shifts_occupied_siblings() {
454        let mut graph = PathGraph::<u32>::new();
455        graph.insert(&[], 0);
456        graph.insert(&[0], 10);
457        graph.insert(&[0, 0], 100);
458        graph.insert(&[0, 1], 200);
459
460        graph.insert(&[0, 1], 150);
461
462        assert_eq!(graph.get(&[0, 0]), Some(&100));
463        assert_eq!(graph.get(&[0, 1]), Some(&150));
464        assert_eq!(graph.get(&[0, 2]), Some(&200));
465        assert_eq!(graph.len(&[0]), Some(3));
466    }
467}
pathgraph/lib.rs

pathgraph/
lib.rs
