rill_protocol/
pathfinder.rs

1use crate::io::provider::{EntryId, Path};
2use derive_more::{Deref, DerefMut};
3use std::collections::HashMap;
4
5/// Universal storage with `EntryId` hierarchy.
6#[derive(Debug, Deref, DerefMut)]
7pub struct Pathfinder<T> {
8    root: Record<T>,
9}
10
11impl<T> Pathfinder<T> {
12    pub fn new() -> Self {
13        Self {
14            root: Record::default(),
15        }
16    }
17}
18
19impl<T> Default for Pathfinder<T> {
20    fn default() -> Self {
21        Self::new()
22    }
23}
24
25#[derive(Debug)]
26pub struct Record<T> {
27    subs: HashMap<EntryId, Record<T>>,
28    link: Option<T>,
29}
30
31impl<T> Default for Record<T> {
32    fn default() -> Self {
33        Self {
34            subs: HashMap::new(),
35            link: None,
36        }
37    }
38}
39
40pub struct Discovered<'a, T> {
41    pub remained_path: Path,
42    pub record: &'a Record<T>,
43}
44
45impl<T> Record<T> {
46    /// Creates nodes for the provided `Path`.
47    ///
48    /// It returns empty record if value is not exists and you
49    /// have to use `set_link` method to assign a value to it.
50    pub fn dig(&mut self, path: Path) -> &mut Self {
51        let mut record = self;
52        let entries: Vec<_> = path.into();
53        for element in entries {
54            record = record.subs.entry(element).or_default();
55        }
56        record
57    }
58
59    /// Tries to find a `Record` for the `Path`, but it it's not
60    /// exists than it returned the last record in a chain and the
61    /// remained (unprocessed) `Path`.
62    pub fn discover(&self, path: &Path) -> Discovered<'_, T> {
63        let mut record = self;
64        let mut iter = path.as_ref().iter();
65        let mut remained = Vec::new();
66        for element in &mut iter {
67            if let Some(next_record) = record.subs.get(element) {
68                record = next_record;
69            } else {
70                remained.push(element.clone());
71                break;
72            }
73        }
74        remained.extend(iter.cloned());
75        Discovered {
76            remained_path: Path::from(remained),
77            record,
78        }
79    }
80
81    pub fn remove(&mut self, path: &Path) -> Option<Self> {
82        let mut record = self;
83        let mut iter = path.as_ref().iter();
84        while let Some(element) = iter.next() {
85            if iter.len() == 0 {
86                return record.subs.remove(element);
87            } else if let Some(next_record) = record.subs.get_mut(element) {
88                record = next_record;
89            } else {
90                break;
91            }
92        }
93        None
94    }
95
96    /// Returns the `Record` for the `Path` or `None` if the `Record` not
97    /// exists for the path.
98    pub fn find(&self, path: &Path) -> Option<&Self> {
99        let mut record = self;
100        for element in path.as_ref() {
101            if let Some(next_record) = record.subs.get(element) {
102                record = next_record;
103            } else {
104                return None;
105            }
106        }
107        Some(record)
108    }
109
110    pub fn find_mut(&mut self, path: &Path) -> Option<&mut Self> {
111        let mut record = self;
112        for element in path.as_ref() {
113            if let Some(next_record) = record.subs.get_mut(element) {
114                record = next_record;
115            } else {
116                return None;
117            }
118        }
119        Some(record)
120    }
121
122    pub fn list(&self) -> impl Iterator<Item = (EntryId, Option<&T>)> {
123        self.subs.iter().map(|(id, record)| {
124            let id = id.to_owned();
125            (id, record.link.as_ref())
126        })
127    }
128
129    pub fn set_link(&mut self, link: T) -> Option<T> {
130        let mut cell = Some(link);
131        std::mem::swap(&mut self.link, &mut cell);
132        cell
133    }
134
135    pub fn take_link(&mut self) -> Option<T> {
136        self.link.take()
137    }
138
139    pub fn get_link(&self) -> Option<&T> {
140        self.link.as_ref()
141    }
142
143    pub fn get_link_mut(&mut self) -> Option<&mut T> {
144        self.link.as_mut()
145    }
146
147    pub fn has_link(&self) -> bool {
148        self.link.is_some()
149    }
150}
rill_protocol/pathfinder.rs

rill_protocol/
pathfinder.rs
