extern crate unicode_segmentation;

use std::collections::HashMap;

use unicode_segmentation::{UnicodeSegmentation, Graphemes};

#[derive(Debug)]
pub struct Trie<T> {
    root: Option<Node<T>>
}

#[derive(Debug)]
struct Node<T> {
    data: Option<T>,
    children: HashMap<String, Node<T>>
}

impl<T> Trie<T> {
    pub fn new() -> Self {
        Trie {
            root: None
        }
    }

    pub fn get(&self, key: &str) -> Option<&T> {
        match self.root {
            None => None,
            Some(ref root) => {
                let mut key_parts = UnicodeSegmentation::graphemes(key, true);
                root.get(key_parts)
            }
        }
    }

    pub fn add(&mut self, key: &str, value: T) -> Option<T> {
        if self.root.is_none() {
            self.root = Some(Node::new());
        }

        let mut key_parts = UnicodeSegmentation::graphemes(key, true);

        match self.root {
            None => unreachable!(),
            Some(ref mut root) => root.add(key_parts, value)
        }
    }
}

impl<T> Node<T> {

    fn new() -> Self {
        Node {
            data: None,
            children: HashMap::new()
        }
    }

    fn get_child_or_new(&mut self, char: &str) -> &mut Self {
        if ! self.children.contains_key(char) {
            self.children.insert(char.into(), Node::new());
        }
        self.children.get_mut(char).expect("Just Checked for this above")
    }

    fn add(&mut self, mut key_iter: Graphemes, data: T) -> Option<T> {
        match key_iter.next() {
            // this is a new data node
            None => {
                let old_data = self.data.take();
                self.data = Some(data);
                old_data
            }
            Some(char) => {
                let mut child = self.get_child_or_new(char);
                child.add(key_iter, data)
            }
        }
    }

    fn get(&self, mut key_iter: Graphemes) -> Option<&T> {
        match key_iter.next() {
            None => self.data.as_ref(),
            Some(char) => {
                match self.children.get(char) {
                    None => None,
                    Some(ch) => {
                        ch.get(key_iter)
                    }
                }
            }
        }
    }

}