tree.rs

/// # Example
///
/// ```rust
/// fn main() {
/// 	let mut tree = Tree::<char,String>::new();
/// 	tree.insert_recursively(&vec!('H', 'C'), "HandleHelloConnectMessage".into_string());
/// 	tree.insert_recursively(&vec!('H', 'G'), "HandleHelloGameMessage".into_string());
/// 
/// 	println!("{}", tree.find_recursively(&vec!('H', 'G')).unwrap());
/// 	println!("{}", tree.find_recursively(&vec!('H', 'C')).unwrap());
/// }
/// ```

use std::collections::{HashMap, Map};
use std::hash::{Hash};


pub struct Tree<K, V> {
	root: Box<TreeNode<K, V>>
}

impl<K: Eq + Hash + Clone, V> Tree<K, V> {
	pub fn new() -> Tree<K, V> {
		Tree {
			root: box TreeNode::<K, V>::new(0)
		}
	}

	pub fn find_recursively<'a>(&'a self, keys: &Vec<K>)  -> Option<&'a V> {
		self.root.find_recursively(keys)
	}
	pub fn insert_recursively(&mut self, keys: &Vec<K>, v: V) {
		self.root.insert_recursively(keys, v);
	}
}

struct TreeNode<K, V> {
	value: Option<V>,
	children: HashMap<K, Box<TreeNode<K, V>>>,
	index: i16
}

impl<K: Eq + Hash + Clone, V> TreeNode<K, V> {
	fn new (index: i16) -> TreeNode<K, V> {
		TreeNode {
			value: None,
			children: HashMap::new(),
			index: index
		}
	}

	fn find_recursively<'a>(&'a self, keys: &Vec<K>)  -> Option<&'a V> {
		if self.value.is_some() {
			return Some(self.value.get_ref());
		}

		let k = keys.get(self.index as uint);
		match self.children.find(k) {
			Some(node) =>  node.find_recursively(keys),
			_ => None
		}
	}

	fn insert_recursively(&mut self, keys: &Vec<K>, v: V) {

		if self.index - keys.len() as i16 >= 0 {
			self.value = Some(v);
		} else {
			let k = keys.get(self.index as uint);

			if !self.children.contains_key(k) {
				self.children.insert(k.clone(), box TreeNode::<K, V>::new(self.index + 1));
			}

			match self.children.find_mut(k) {
				Some(child)	=> child.insert_recursively(keys, v),
				_			=> { }
			}
		}
	}
}
/* TODO : Implement traits

impl<K: Eq + Hash, V> Collection for TreeNode<K, V> {
	fn len(&self) -> uint { 
		self.children.len()
	}

	fn is_empty(&self) -> bool { 
		self.len() == 0 
	}
}

impl<K: Eq + Hash, V> Map<K, V> for TreeNode<K, V> {
	fn contains_key(&self, k: &K) -> bool {
		self.find(k).is_some()
	}

	fn find<'a>(&'a self, k: &K)  -> Option<&'a V> {
		match self.children.find(k)  {
			Some(node) => 
				match node.value {
					Some(ref v) => Some(v),
					_ => None
				},
			_ => None
		}
	}
}

*/