prefix-trie 0.9.0

Prefix trie (tree) datastructure (both a set and a map) that provides exact and longest-prefix matches.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

//! Debug formatting for PrefixMap.
//!
//! The output hides the internal TreeBitMap structure and shows the logical prefix trie,
//! matching the style of PrefixMap's debug output.

use std::fmt::{Debug, Formatter, Result};

use crate::{Prefix, PrefixMap};

impl<P: Prefix + Debug, T: Debug> Debug for PrefixMap<P, T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        let entries: Vec<(P, &T)> = self.iter().collect();
        DebugSubtree { entries: &entries }.fmt(f)
    }
}

struct DebugSubtree<'a, P, T> {
    entries: &'a [(P, &'a T)],
}

struct DebugExtendedNode<'a, P, T> {
    value: &'a T,
    children: DebugSubtree<'a, P, T>,
}

impl<P: Prefix + Debug, T: Debug> Debug for DebugExtendedNode<'_, P, T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        let mut d = f.debug_struct("");
        d.field("value", self.value);
        if !self.children.entries.is_empty() {
            d.field("children", &self.children);
        }
        d.finish()
    }
}

impl<P: Prefix + Debug, T: Debug> Debug for DebugSubtree<'_, P, T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        let mut dm = f.debug_map();
        let mut entries = self.entries;

        while let Some(((prefix, value), rest)) = entries.split_first() {
            let child_count = rest.iter().take_while(|(p, _)| prefix.contains(p)).count();
            let (children, remaining) = rest.split_at(child_count);
            entries = remaining;

            dm.entry(
                prefix,
                &DebugExtendedNode {
                    value: *value,
                    children: DebugSubtree { entries: children },
                },
            );
        }

        dm.finish()
    }
}