basic_tree 0.2.5

basic tree for rust, for now including only trie
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
125
126

use std::cell::RefCell;
use std::cmp::Eq;
use std::cmp::PartialEq;
use std::collections::HashMap;
use std::hash::Hash;
use std::rc::Rc;

#[derive(Debug, Clone)]
pub enum Leaf<T> {
    End(T),
    Nil,
}

impl<T: PartialEq> PartialEq for Leaf<T> {
    fn eq(&self, other: &Self) -> bool {
        match self {
            Leaf::End(d) => match other {
                Leaf::End(od) => d == od,
                Leaf::Nil => false,
            },
            Leaf::Nil => match other {
                Leaf::End(_) => false,
                Leaf::Nil => true,
            },
        }
    }
}

/// Adds one to the number given.
///
/// # Examples
///
/// Trie is the basic trait to implement for a trie tree
/// ```
/// let node = Node::new();
/// let seq = vec!["你".to_string(), "我".to_string(), "他".to_string()];
/// let seq1 = vec!["你".to_string(), "我".to_string()];
/// Node::insert_seq(node.clone(), &seq, Leaf::End("intention".to_string()));
/// let leaf = Node::get_leaf(node.clone(), &seq1);
/// assert_ne!(leaf, Leaf::End("intention".to_string()));
/// ```

#[derive(Debug)]
pub struct Node<T: Eq + Hash + Clone> {
    pub node: HashMap<T, Rc<RefCell<Node<T>>>>,
    pub leaf: Leaf<T>,
}

pub trait Trie<T: Eq + Hash + Clone> {
    /// add node chars and leaf chars to Node.
    fn insert_seq(node: Rc<RefCell<Node<T>>>, words: &[T], leaf: Leaf<T>) {
        let (index, mut m_node) = Node::find_last_node(node.clone(), &words);
        for word in &words[index..] {
            m_node = Node::add_node(m_node.clone(), word.to_owned());
        }
        Node::add_leaf(m_node, leaf);
    }
    /// get the corresponding leaf from the char seq.
    fn get_leaf(node: Rc<RefCell<Node<T>>>, words: &[T]) -> Leaf<T> {
        let length = words.len();
        let (index, node) = Node::find_last_node(node.clone(), words);
        if index + 1 == length {
            let m_node = node.borrow();
            m_node.leaf.to_owned()
        } else {
            Leaf::Nil
        }
    }
    /// get the node correspongding to char.
    fn find_node(node: Rc<RefCell<Node<T>>>, word: &T) -> (bool, Rc<RefCell<Node<T>>>) {
        let m_node = node.borrow();
        match m_node.node.get(word) {
            Some(mm_node) => (true, mm_node.clone()),
            None => (false, node.clone()),
        }
    }
    /// get the last node correspongding to chars.
    fn find_last_node(node: Rc<RefCell<Node<T>>>, words: &[T]) -> (usize, Rc<RefCell<Node<T>>>) {
        let mut m_node = node.clone();
        let mut out_index = 0;
        for (index, word) in words.iter().enumerate() {
            let (label, mm_node) = Node::find_node(m_node.clone(), word);
            if label {
                out_index = index + 1;
                m_node = mm_node;
            }
        }
        (out_index, m_node.clone())
    }

    /// add leaf to the node
    fn add_leaf(node: Rc<RefCell<Node<T>>>, leaf: Leaf<T>) -> bool {
        let mut m_node = node.borrow_mut();
        m_node.leaf = leaf;
        true
    }

    /// add node to the node
    fn add_node(node: Rc<RefCell<Node<T>>>, node_data: T) -> Rc<RefCell<Node<T>>> {
        let mut m_node = node.borrow_mut();
        let new_node = Node::new();
        m_node.node.insert(node_data, new_node.clone());
        new_node.clone()
    }
}

impl<T: Eq + Hash + Clone> Trie<T> for Node<T> {}

impl<T: Eq + Hash + Clone> Node<T> {
    pub fn new() -> Rc<RefCell<Node<T>>> {
        Rc::new(RefCell::new(Node {
            node: HashMap::new(),
            leaf: Leaf::Nil,
        }))
    }
}

#[test]
fn name() {
    let node = Node::new();
    let seq = vec!["你".to_string(), "我".to_string(), "他".to_string()];
    let seq1 = vec!["你".to_string(), "我".to_string()];
    Node::insert_seq(node.clone(), &seq, Leaf::End("intention".to_string()));
    let leaf = Node::get_leaf(node.clone(), &seq1);
    assert_ne!(leaf, Leaf::End("intention".to_string()));
}