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 if self.items.get(path[0] as usize).is_none() {
23 self.items.resize_with(path[0] as usize + 1, || Self {
24 value: None,
25 items: Vec::new(),
26 });
27 } else if path.len() == 1 {
28 self.items.insert(
29 path[0] as usize,
30 Self {
31 value: None,
32 items: Vec::new(),
33 },
34 );
35 }
36 self.items[path[0] as usize].insert(&path[1..], value)
37 }
38 }
39
40 pub fn insert_entry(&mut self, path: &[u32], entry: PathGraphEntry<V>) {
41 if path.is_empty() {
42 *self = entry;
43 } else {
44 if self.items.get(path[0] as usize).is_none() {
45 self.items.resize_with(path[0] as usize + 1, || Self {
46 value: None,
47 items: Vec::new(),
48 });
49 } else if path.len() == 1 {
50 self.items.insert(
51 path[0] as usize,
52 Self {
53 value: None,
54 items: Vec::new(),
55 },
56 );
57 }
58 self.items[path[0] as usize].insert_entry(&path[1..], entry)
59 }
60 }
61
62 pub fn remove(&mut self, path: &[u32]) -> Option<PathGraphEntry<V>> {
63 if path.is_empty() {
64 unreachable!()
65 } else if path.len() == 1 {
66 if path[0] as usize >= self.items.len() {
67 self.items.pop()
68 } else {
69 Some(self.items.remove(path[0] as usize))
70 }
71 } else if let Some(item) = self.items.get_mut(path[0] as usize) {
72 item.remove(&path[1..])
73 } else {
74 None
75 }
76 }
77
78 pub fn find_path(
79 &self,
80 path: Vec<u32>,
81 finder: &impl Fn(Option<&V>) -> bool,
82 ) -> Option<Vec<u32>> {
83 if finder(self.value.as_ref()) {
84 return Some(path);
85 }
86 for (i, item) in self.items.iter().enumerate() {
87 let mut path = path.clone();
88 path.push(i as u32);
89 if let Some(path) = item.find_path(path, finder) {
90 return Some(path);
91 }
92 }
93 None
94 }
95
96 pub fn find(&self, path: Vec<u32>, finder: &impl Fn(Option<&V>) -> bool) -> Option<&V> {
97 if finder(self.value.as_ref()) {
98 return self.value.as_ref();
99 }
100 for (i, item) in self.items.iter().enumerate() {
101 let mut path = path.clone();
102 path.push(i as u32);
103 if let Some(res) = item.find(path, finder) {
104 return Some(res);
105 }
106 }
107 None
108 }
109
110 pub fn reduce<A>(
111 &self,
112 acc: &mut A,
113 path: Vec<u32>,
114 reducer: &impl Fn(Option<&V>, &[u32], &mut A) -> bool,
115 ) -> bool {
116 if reducer(self.value.as_ref(), &path, acc) {
117 return true;
118 }
119 for (i, item) in self.items.iter().enumerate() {
120 let mut path = path.clone();
121 path.push(i as u32);
122 if item.reduce(acc, path, reducer) {
123 return true;
124 }
125 }
126 false
127 }
128
129 pub fn find_child_path(
130 &self,
131 path: Vec<u32>,
132 target: &[u32],
133 finder: &impl Fn(Option<&V>) -> bool,
134 ) -> Option<Vec<u32>> {
135 if !path.is_empty() && &path[0..path.len() - 1] == target && finder(self.value.as_ref()) {
136 return Some(path);
137 }
138 for (i, item) in self.items.iter().enumerate() {
139 let mut path = path.clone();
140 path.push(i as u32);
141 if let Some(path) = item.find_child_path(path, target, finder) {
142 return Some(path);
143 }
144 }
145 None
146 }
147
148 pub fn get(&self, path: &[u32]) -> Option<&V> {
149 if path.is_empty() {
150 self.value.as_ref()
151 } else if let Some(item) = self.items.get(path[0] as usize) {
152 item.get(&path[1..])
153 } else {
154 None
155 }
156 }
157
158 pub fn len(&self, path: &[u32]) -> Option<usize> {
159 if path.is_empty() {
160 Some(self.items.len())
161 } else if let Some(item) = self.items.get(path[0] as usize) {
162 item.len(&path[1..])
163 } else {
164 None
165 }
166 }
167
168 pub fn size(&self, size: &mut usize) {
169 if self.value.is_some() {
170 *size += 1;
171 }
172
173 for item in &self.items {
174 item.size(size);
175 }
176 }
177
178 pub fn traverse(
179 &self,
180 target: &[u32],
181 mut path: Vec<u32>,
182 traverser: &mut impl FnMut(&[u32], &V),
183 ) {
184 if path.starts_with(target)
185 && let Some(value) = self.value.as_ref()
186 {
187 traverser(&path, value);
188 }
189
190 for (i, item) in self.items.iter().enumerate() {
191 path.push(i as u32);
192 if target.starts_with(&path) || path.starts_with(target) {
193 item.traverse(target, path.clone(), traverser);
194 }
195 path.pop();
196 }
197 }
198
199 pub fn traverse_1_level(
200 &self,
201 target: &[u32],
202 mut path: Vec<u32>,
203 traverser: &mut impl FnMut(&[u32], &V),
204 ) {
205 if path == target {
206 for (i, item) in self.items.iter().enumerate() {
207 if let Some(value) = item.value.as_ref() {
208 path.push(i as u32);
209 traverser(&path, value);
210 path.pop();
211 }
212 }
213 } else {
214 for (i, item) in self.items.iter().enumerate() {
215 path.push(i as u32);
216 item.traverse_1_level(target, path.clone(), traverser);
217 path.pop();
218 }
219 }
220 }
221}
222
223pub struct PathGraph<V> {
224 entry: Option<PathGraphEntry<V>>,
225}
226
227impl<V> Default for PathGraph<V> {
228 fn default() -> Self {
229 Self::new()
230 }
231}
232
233impl<V: fmt::Debug> fmt::Debug for PathGraph<V> {
234 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
235 f.debug_struct("PathGraph")
236 .field("entry", &self.entry)
237 .finish()
238 }
239}
240
241impl<V> PathGraph<V> {
242 pub fn new() -> Self {
243 Self { entry: None }
244 }
245
246 pub fn insert(&mut self, path: &[u32], value: V) {
247 if let Some(entry) = &mut self.entry {
248 entry.insert(path, value);
249 } else {
250 let mut entry = PathGraphEntry {
251 value: None,
252 items: Vec::new(),
253 };
254 entry.insert(path, value);
255 self.entry = Some(entry);
256 }
257 }
258
259 pub fn insert_entry(&mut self, path: &[u32], entry: PathGraphEntry<V>) {
260 if let Some(root_entry) = &mut self.entry {
261 root_entry.insert_entry(path, entry);
262 } else {
263 let mut root_entry = PathGraphEntry {
264 value: None,
265 items: Vec::new(),
266 };
267 root_entry.insert_entry(path, entry);
268 self.entry = Some(root_entry);
269 }
270 }
271
272 pub fn remove(&mut self, path: &[u32]) -> Option<PathGraphEntry<V>> {
273 if let Some(entry) = &mut self.entry {
274 entry.remove(path)
275 } else {
276 None
277 }
278 }
279
280 pub fn find_path(&self, finder: impl Fn(Option<&V>) -> bool) -> Option<Vec<u32>> {
281 if let Some(entry) = &self.entry {
282 entry.find_path(vec![], &finder)
283 } else {
284 None
285 }
286 }
287
288 pub fn find(&self, finder: impl Fn(Option<&V>) -> bool) -> Option<&V> {
289 if let Some(entry) = &self.entry {
290 entry.find(vec![], &finder)
291 } else {
292 None
293 }
294 }
295
296 pub fn reduce<A>(
297 &self,
298 acc: &mut A,
299 reducer: impl Fn(Option<&V>, &[u32], &mut A) -> bool,
300 ) -> bool {
301 if let Some(entry) = &self.entry {
302 entry.reduce(acc, vec![], &reducer)
303 } else {
304 false
305 }
306 }
307
308 pub fn find_child_path(
309 &self,
310 target: &[u32],
311 finder: impl Fn(Option<&V>) -> bool,
312 ) -> Option<Vec<u32>> {
313 if let Some(entry) = &self.entry {
314 entry.find_child_path(vec![], target, &finder)
315 } else {
316 None
317 }
318 }
319
320 pub fn len(&self, path: &[u32]) -> Option<usize> {
321 if let Some(entry) = &self.entry {
322 entry.len(path)
323 } else {
324 None
325 }
326 }
327
328 pub fn get(&self, path: &[u32]) -> Option<&V> {
329 if let Some(entry) = &self.entry {
330 entry.get(path)
331 } else {
332 None
333 }
334 }
335
336 pub fn size(&self) -> usize {
337 let mut size = 0;
338 if let Some(entry) = &self.entry {
339 entry.size(&mut size);
340 }
341 size
342 }
343
344 pub fn traverse(&self, target: &[u32], mut traverser: impl FnMut(&[u32], &V)) {
345 if let Some(entry) = &self.entry {
346 entry.traverse(target, vec![], &mut traverser);
347 }
348 }
349
350 pub fn traverse_1_level(&self, target: &[u32], mut traverser: impl FnMut(&[u32], &V)) {
351 if let Some(entry) = &self.entry {
352 entry.traverse_1_level(target, vec![], &mut traverser);
353 }
354 }
355}