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 retain(
200 &mut self,
201 target: &[u32],
202 parent_is_retained: bool,
203 mut path: Vec<u32>,
204 retainer: &mut impl FnMut(&[u32], &V) -> bool,
205 traverser: &mut impl FnMut(&[u32], &V),
206 ) -> bool {
207 let mut retain = parent_is_retained;
208 if path.starts_with(target)
209 && let Some(value) = self.value.as_ref()
210 {
211 if parent_is_retained {
212 retain = retainer(&path, value);
213 }
214
215 if !retain {
216 traverser(&path, value);
217 }
218 }
219
220 let mut i = 0;
221 self.items.retain_mut(|item| {
222 let mut retain = retain;
223 path.push(i as u32);
224 if target.starts_with(&path) || path.starts_with(target) {
225 retain = item.retain(target, retain, path.clone(), retainer, traverser);
226 }
227 path.pop();
228 i += 1;
229 retain
230 });
231 retain
232 }
233
234 pub fn traverse_1_level(
235 &self,
236 target: &[u32],
237 mut path: Vec<u32>,
238 traverser: &mut impl FnMut(&[u32], &V),
239 ) {
240 if path == target {
241 for (i, item) in self.items.iter().enumerate() {
242 if let Some(value) = item.value.as_ref() {
243 path.push(i as u32);
244 traverser(&path, value);
245 path.pop();
246 }
247 }
248 } else {
249 for (i, item) in self.items.iter().enumerate() {
250 path.push(i as u32);
251 item.traverse_1_level(target, path.clone(), traverser);
252 path.pop();
253 }
254 }
255 }
256
257 pub fn value(self) -> Option<V> {
258 self.value
259 }
260}
261
262pub struct PathGraph<V> {
263 entry: Option<PathGraphEntry<V>>,
264}
265
266impl<V> Default for PathGraph<V> {
267 fn default() -> Self {
268 Self::new()
269 }
270}
271
272impl<V: fmt::Debug> fmt::Debug for PathGraph<V> {
273 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
274 f.debug_struct("PathGraph")
275 .field("entry", &self.entry)
276 .finish()
277 }
278}
279
280impl<V> PathGraph<V> {
281 pub fn new() -> Self {
282 Self { entry: None }
283 }
284
285 pub fn insert(&mut self, path: &[u32], value: V) {
286 if let Some(entry) = &mut self.entry {
287 entry.insert(path, value);
288 } else {
289 let mut entry = PathGraphEntry {
290 value: None,
291 items: Vec::new(),
292 };
293 entry.insert(path, value);
294 self.entry = Some(entry);
295 }
296 }
297
298 pub fn insert_entry(&mut self, path: &[u32], entry: PathGraphEntry<V>) {
299 if let Some(root_entry) = &mut self.entry {
300 root_entry.insert_entry(path, entry);
301 } else {
302 let mut root_entry = PathGraphEntry {
303 value: None,
304 items: Vec::new(),
305 };
306 root_entry.insert_entry(path, entry);
307 self.entry = Some(root_entry);
308 }
309 }
310
311 pub fn remove(&mut self, path: &[u32]) -> Option<PathGraphEntry<V>> {
312 if let Some(entry) = &mut self.entry {
313 entry.remove(path)
314 } else {
315 None
316 }
317 }
318
319 pub fn find_path(&self, finder: impl Fn(Option<&V>) -> bool) -> Option<Vec<u32>> {
320 if let Some(entry) = &self.entry {
321 entry.find_path(vec![], &finder)
322 } else {
323 None
324 }
325 }
326
327 pub fn find(&self, finder: impl Fn(Option<&V>) -> bool) -> Option<&V> {
328 if let Some(entry) = &self.entry {
329 entry.find(vec![], &finder)
330 } else {
331 None
332 }
333 }
334
335 pub fn reduce<A>(
336 &self,
337 acc: &mut A,
338 reducer: impl Fn(Option<&V>, &[u32], &mut A) -> bool,
339 ) -> bool {
340 if let Some(entry) = &self.entry {
341 entry.reduce(acc, vec![], &reducer)
342 } else {
343 false
344 }
345 }
346
347 pub fn find_child_path(
348 &self,
349 target: &[u32],
350 finder: impl Fn(Option<&V>) -> bool,
351 ) -> Option<Vec<u32>> {
352 if let Some(entry) = &self.entry {
353 entry.find_child_path(vec![], target, &finder)
354 } else {
355 None
356 }
357 }
358
359 pub fn len(&self, path: &[u32]) -> Option<usize> {
360 if let Some(entry) = &self.entry {
361 entry.len(path)
362 } else {
363 None
364 }
365 }
366
367 pub fn get(&self, path: &[u32]) -> Option<&V> {
368 if let Some(entry) = &self.entry {
369 entry.get(path)
370 } else {
371 None
372 }
373 }
374
375 pub fn size(&self) -> usize {
376 let mut size = 0;
377 if let Some(entry) = &self.entry {
378 entry.size(&mut size);
379 }
380 size
381 }
382
383 pub fn traverse(&self, target: &[u32], mut traverser: impl FnMut(&[u32], &V)) {
384 if let Some(entry) = &self.entry {
385 entry.traverse(target, vec![], &mut traverser);
386 }
387 }
388
389 pub fn retain(
390 &mut self,
391 target: &[u32],
392 mut retainer: impl FnMut(&[u32], &V) -> bool,
393 mut traverser: impl FnMut(&[u32], &V),
394 ) {
395 if let Some(entry) = &mut self.entry
396 && !entry.retain(target, true, vec![], &mut retainer, &mut traverser)
397 {
398 let _ = self.entry.take();
399 }
400 }
401
402 pub fn traverse_1_level(&self, target: &[u32], mut traverser: impl FnMut(&[u32], &V)) {
403 if let Some(entry) = &self.entry {
404 entry.traverse_1_level(target, vec![], &mut traverser);
405 }
406 }
407}