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

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,
            },
        }
    }
}
#[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> {
    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);
    }

    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
        }
    }

    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()),
        }
    }

    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())
    }

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

    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()));
}