byte_trie 0.3.0

A compressed trie based on bytes with some weird child node bucket sizes.
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

use crate::child::Child;
use crate::keys::BytesKey;
use crate::nodes::AdaptiveNode;
use crate::tries::{BitTrie, ByteTrie, NibbleTrie};
use serde::ser::SerializeMap;
use serde::{Serialize, Serializer};

impl<T> Serialize for ByteTrie<T>
where
    T: Serialize,
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        serializer.serialize_newtype_struct("ByteTrie", &self.root)
    }
}

impl<T> Serialize for NibbleTrie<T>
where
    T: Serialize,
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        serializer.serialize_newtype_struct("NibbleTrie", &self.root)
    }
}

impl<T> Serialize for BitTrie<T>
where
    T: Serialize,
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        serializer.serialize_newtype_struct("BitTrie", &self.root)
    }
}

impl<K, T> Serialize for AdaptiveNode<K, T>
where
    K: BytesKey,
    T: Serialize,
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        let mut map = serializer.serialize_map(None)?;

        flatten_node(&self)
            .iter()
            .try_for_each(|n| node_or_children(n, &mut map))?;

        map.end()
    }
}

fn node_or_children<K, T, M>(node: &AdaptiveNode<K, T>, map: &mut M) -> Result<(), M::Error>
where
    K: BytesKey,
    T: Serialize,
    M: SerializeMap,
{
    let is_empty = match &node.child {
        Some(child) => child.is_empty(),
        None => true,
    };

    if is_empty {
        map.serialize_entry(&node.key.to_string(), &node.value)
    } else {
        map.serialize_entry(&node.key.to_string(), &node.child)
    }
}

fn flatten_node<K, T>(node: &AdaptiveNode<K, T>) -> Vec<&AdaptiveNode<K, T>>
where
    K: BytesKey,
    T: Serialize,
{
    if !node.key.get().is_empty() {
        return vec![node];
    }

    match &node.child {
        Some(child) => child.child().iter().fold(Vec::new(), |mut acc, child| {
            if let Some(child) = child {
                acc.append(&mut flatten_node(child));
            }

            acc
        }),
        None => Vec::new(),
    }
}

impl<K, T> Serialize for Child<K, T>
where
    K: BytesKey,
    T: Serialize,
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        let mut map = serializer.serialize_map(None)?;

        self.child()
            .iter()
            .filter_map(|c| c.as_ref().map(flatten_node))
            .try_for_each(|nodes| {
                nodes
                    .iter()
                    .try_for_each(|node| node_or_children(node, &mut map))
            })?;

        map.end()
    }
}