trie-rs 0.4.2

Memory efficient trie (prefix tree) and map library based on LOUDS
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

use super::naive_trie_b_f_iter::NaiveTrieBFIter;
use super::{NaiveTrie, NaiveTrieIntermOrLeaf, NaiveTrieRoot};
use std::vec::Drain;

impl<'trie, Label: Ord, Value> NaiveTrie<Label, Value> {
    pub fn make_root() -> Self {
        NaiveTrie::Root(NaiveTrieRoot { children: vec![] })
    }

    pub fn make_interm_or_leaf(label: Label, terminal: Option<Value>) -> Self {
        NaiveTrie::IntermOrLeaf(NaiveTrieIntermOrLeaf {
            children: vec![],
            label,
            value: terminal,
        })
    }

    pub fn push<Arr: Iterator<Item = Label>>(&'trie mut self, word: Arr, value: Value) {
        let mut trie = self;
        for chr in word {
            let res = trie
                .children()
                .binary_search_by(|child| child.label().cmp(&chr));
            match res {
                Ok(j) => {
                    trie = match trie {
                        NaiveTrie::Root(node) => &mut node.children[j],
                        NaiveTrie::IntermOrLeaf(node) => &mut node.children[j],
                        _ => panic!("Unexpected type"),
                    };
                }
                Err(j) => {
                    let child_trie = Self::make_interm_or_leaf(chr, None);
                    trie = match trie {
                        NaiveTrie::Root(node) => {
                            node.children.insert(j, child_trie);
                            &mut node.children[j]
                        }
                        NaiveTrie::IntermOrLeaf(node) => {
                            node.children.insert(j, child_trie);
                            &mut node.children[j]
                        }
                        _ => panic!("Unexpected type"),
                    };
                }
            };
        }
        match trie {
            NaiveTrie::IntermOrLeaf(node) => node.value = Some(value),
            _ => panic!("Unexpected type"),
        }
    }

    pub fn children(&self) -> &[Self] {
        match self {
            NaiveTrie::Root(node) => &node.children,
            NaiveTrie::IntermOrLeaf(node) => &node.children,
            _ => panic!("Unexpected type"),
        }
    }

    pub fn drain_children(&mut self) -> Drain<'_, Self> {
        match self {
            NaiveTrie::Root(node) => node.children.drain(0..),
            NaiveTrie::IntermOrLeaf(node) => node.children.drain(0..),
            _ => panic!("Unexpected type"),
        }
    }

    /// # Panics
    /// If self is not IntermOrLeaf.
    #[allow(dead_code)]
    pub fn value(&self) -> Option<&Value> {
        match self {
            NaiveTrie::IntermOrLeaf(node) => node.value.as_ref(),
            _ => panic!("Unexpected type"),
        }
    }

    /// # Panics
    /// If self is not IntermOrLeaf.
    pub fn label(&self) -> &Label {
        match self {
            NaiveTrie::IntermOrLeaf(node) => &node.label,
            _ => panic!("Unexpected type"),
        }
    }
}

impl<Label: Ord, Value> IntoIterator for NaiveTrie<Label, Value> {
    type Item = NaiveTrie<Label, Value>;
    type IntoIter = NaiveTrieBFIter<Label, Value>;
    fn into_iter(self) -> NaiveTrieBFIter<Label, Value> {
        NaiveTrieBFIter::new(self)
    }
}