trie_tree/trie/
basic.rs

1use std::cell::RefCell;
2use std::cmp::Eq;
3use std::cmp::PartialEq;
4use std::collections::HashMap;
5use std::hash::Hash;
6use std::rc::Rc;
7
8#[derive(Debug, Clone)]
9pub enum Leaf<T> {
10    End(T),
11    Nil,
12}
13
14impl<T: PartialEq> PartialEq for Leaf<T> {
15    fn eq(&self, other: &Self) -> bool {
16        match self {
17            Leaf::End(d) => match other {
18                Leaf::End(od) => d == od,
19                Leaf::Nil => false,
20            },
21            Leaf::Nil => match other {
22                Leaf::End(_) => false,
23                Leaf::Nil => true,
24            },
25        }
26    }
27}
28
29/// Adds one to the number given.
30///
31/// # Examples
32///
33/// Trie is the basic trait to implement for a trie tree
34/// ```
35/// let node = Node::new();
36/// let seq = vec!["你".to_string(), "我".to_string(), "他".to_string()];
37/// let seq1 = vec!["你".to_string(), "我".to_string()];
38/// Node::insert_seq(node.clone(), &seq, Leaf::End("intention".to_string()));
39/// let leaf = Node::get_leaf(node.clone(), &seq1);
40/// assert_ne!(leaf, Leaf::End("intention".to_string()));
41/// ```
42
43#[derive(Debug)]
44pub struct Node<T: Eq + Hash + Clone> {
45    pub node: HashMap<T, Rc<RefCell<Node<T>>>>,
46    pub leaf: Leaf<T>,
47}
48
49pub trait Trie<T: Eq + Hash + Clone> {
50    /// add node chars and leaf chars to Node.
51    fn insert_seq(node: Rc<RefCell<Node<T>>>, words: &[T], leaf: Leaf<T>) {
52        let (index, mut m_node) = Node::find_last_node(node.clone(), &words);
53        for word in &words[index..] {
54            m_node = Node::add_node(m_node.clone(), word.to_owned());
55        }
56        Node::add_leaf(m_node, leaf);
57    }
58    /// get the corresponding leaf from the char seq.
59    fn get_leaf(node: Rc<RefCell<Node<T>>>, words: &[T]) -> Leaf<T> {
60        let length = words.len();
61        let (index, node) = Node::find_last_node(node.clone(), words);
62        if index + 1 == length {
63            let m_node = node.borrow();
64            m_node.leaf.to_owned()
65        } else {
66            Leaf::Nil
67        }
68    }
69    /// get the node correspongding to char.
70    fn find_node(node: Rc<RefCell<Node<T>>>, word: &T) -> (bool, Rc<RefCell<Node<T>>>) {
71        let m_node = node.borrow();
72        match m_node.node.get(word) {
73            Some(mm_node) => (true, mm_node.clone()),
74            None => (false, node.clone()),
75        }
76    }
77    /// get the last node correspongding to chars.
78    fn find_last_node(node: Rc<RefCell<Node<T>>>, words: &[T]) -> (usize, Rc<RefCell<Node<T>>>) {
79        let mut m_node = node.clone();
80        let mut out_index = 0;
81        for (index, word) in words.iter().enumerate() {
82            let (label, mm_node) = Node::find_node(m_node.clone(), word);
83            if label {
84                out_index = index + 1;
85                m_node = mm_node;
86            }
87        }
88        (out_index, m_node.clone())
89    }
90
91    /// add leaf to the node
92    fn add_leaf(node: Rc<RefCell<Node<T>>>, leaf: Leaf<T>) -> bool {
93        let mut m_node = node.borrow_mut();
94        m_node.leaf = leaf;
95        true
96    }
97
98    /// add node to the node
99    fn add_node(node: Rc<RefCell<Node<T>>>, node_data: T) -> Rc<RefCell<Node<T>>> {
100        let mut m_node = node.borrow_mut();
101        let new_node = Node::new();
102        m_node.node.insert(node_data, new_node.clone());
103        new_node.clone()
104    }
105}
106
107impl<T: Eq + Hash + Clone> Trie<T> for Node<T> {}
108
109impl<T: Eq + Hash + Clone> Node<T> {
110    pub fn new() -> Rc<RefCell<Node<T>>> {
111        Rc::new(RefCell::new(Node {
112            node: HashMap::new(),
113            leaf: Leaf::Nil,
114        }))
115    }
116}
117
118#[test]
119fn name() {
120    let node = Node::new();
121    let seq = vec!["你".to_string(), "我".to_string(), "他".to_string()];
122    let seq1 = vec!["你".to_string(), "我".to_string()];
123    Node::insert_seq(node.clone(), &seq, Leaf::End("intention".to_string()));
124    let leaf = Node::get_leaf(node.clone(), &seq1);
125    assert_ne!(leaf, Leaf::End("intention".to_string()));
126}
trie_tree/trie/basic.rs

trie_tree/trie/
basic.rs
