louds 0.1.1

LOUDS implementation for Rust
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

use std::collections::VecDeque;
use trie::Trie;

/// Naive trie implementation supporting dynamic insertion.
#[derive(Debug)]
pub struct TrieVec<T> {
    children: Vec<(T, Box<TrieVec<T>>)>,
    terminal: bool,
}

impl<'a, T> TrieVec<T> {
    pub fn new() -> TrieVec<T> {
        TrieVec {
            children: Vec::new(),
            terminal: false,
        }
    }
    pub fn bf_iter(&'a self) -> BFIter<'a, T> {
        BFIter::new(&self)
    }
    pub fn children(&self) -> &Vec<(T, Box<Self>)> {
        &self.children
    }
    pub fn terminal(&self) -> bool {
        self.terminal
    }
    pub fn children_len(&self) -> usize {
        self.children.len()
    }
}

impl<T: Eq + PartialOrd + Ord + Clone> TrieVec<T> {
    pub fn insert<K: AsRef<[T]>>(&mut self, key: K) {
        let mut t = self;
        for c in key.as_ref() {
            let mut next_pos = t.children.len();
            let mut found = false;
            for (i, (c2, _)) in t.children.iter().enumerate() {
                if c <= c2 {
                    next_pos = i;
                    found = c == c2;
                    break;
                }
            }
            if !found {
                t.children
                    .insert(next_pos, (c.clone(), Box::new(TrieVec::new())));
            }
            t = &mut { t }.children[next_pos].1;
        }
        t.terminal = true;
    }
}

impl<T: Eq + PartialOrd + Ord> Trie<T> for TrieVec<T> {
    fn has<K: AsRef<[T]>>(&self, key: K) -> bool {
        let mut t = self;
        for c in key.as_ref() {
            match t.children.binary_search_by(|(c2, _)| c2.cmp(c)) {
                Ok(pos) => {
                    t = &t.children[pos].1;
                }
                Err(_) => {
                    return false;
                }
            }
        }
        t.terminal
    }
}

pub struct BFIter<'a, T: 'a> {
    queue: VecDeque<&'a TrieVec<T>>,
}

impl<'a, T> BFIter<'a, T> {
    fn new(t: &'a TrieVec<T>) -> Self {
        let mut queue = VecDeque::new();
        queue.push_back(t);
        BFIter { queue: queue }
    }
}

impl<'a, T> Iterator for BFIter<'a, T> {
    type Item = &'a TrieVec<T>;

    fn next(&mut self) -> Option<Self::Item> {
        self.queue.pop_front().map(|node| {
            for (_, t) in &node.children {
                self.queue.push_back(t);
            }
            node
        })
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_trie_vec() {
        let mut t = TrieVec::new();
        let keys = &["to", "tea", "ten", "i", "in", "inn", "we"];
        let keys_not = &["te", "inno", "web", "hoge", ""];
        for key in keys {
            t.insert(key);
        }

        for key in keys {
            assert!(t.has(key), "t should have key '{}'", key);
        }
        for key in keys_not {
            assert!(!t.has(key), "t should not have key '{}'", key);
        }
    }
}