We've finally progressed far enough in our journey through Rust that we can produce something truly useful. Our binary tree could still be improved in any number of ways, but it does what it was designed to do: it allows us to easily store and retrieve any number of key/value pairs.
So, here we have a complete, useful data structure. First we have the actual structure that stores the tree node data:
struct TreeNode<K, V> where K: PartialOrd + PartialEq {
key: K,
value: V,
lesser: Option<Box<TreeNode<K, V>>>,
greater: Option<Box<TreeNode<K, V>>>,
}Next, we have the implementation block to define the functionality of the TreeNode type, starting with the set function, which associates a key with a value:
impl<K, V> TreeNode<K, V> where K: PartialOrd + PartialEq {
fn set(&mut self, key: K, value: V) {
if key == self.key {
self.value = value;
}
else if key < self.key {
match self.lesser {
None => {
self.lesser = Some(Box::new(TreeNode {key, value,
lesser: None, greater: None }));
},
Some(ref mut lesser) => {
lesser.set(key, value);
}
}
}
else {
match self.greater {
None => {
self.greater = Some(Box::new(TreeNode {key, value,
lesser: None, greater: None }));
}
Some(ref mut greater) => {
greater.set(key, value);
}
}
}
}
The get_ref and get_mut functions are structured very similarly to the set function, because all three of them use the same mechanism to search the tree for a node with the correct key:
fn get_ref(&self, key: K) -> Result<&V, String> {
if key == self.key {
return Ok(&self.value);
}
else if key < self.key {
match self.lesser {
None => {
return Err("No such key".to_string());
}
Some(ref lesser) => {
return lesser.get_ref(key);
}
}
}
else {
match self.greater {
None => {
return Err("No such key".to_string());
}
Some(ref greater) => {
return greater.get_ref(key);
}
}
}
}
fn get_mut(&mut self, key: K) -> Result<&mut V, String> {
if key == self.key {
return Ok(&mut self.value);
}
else if key < self.key {
match self.lesser {
None => {
return Err("No such key".to_string());
}
Some(ref mut lesser) => {
return lesser.get_mut(key);
}
}
}
else {
match self.greater {
None => {
return Err("No such key".to_string());
}
Some(ref mut greater) => {
return greater.get_mut(key);
}
}
}
}
}Next comes the definition of our Tree data type, which provides the public interface to our data structure, and allows us to have an empty tree:
pub struct Tree<K, V> where K: PartialOrd + PartialEq {
root: Option<Box<TreeNode<K, V>>>,
}And now the implementation block for Tree, with the public functions that provide us with a way to interact with TreeNodes:
impl<K, V> Tree<K, V> where K: PartialOrd + PartialEq {
pub fn new() -> Tree<K, V> {
Tree { root: None }
}
pub fn set(&mut self, key: K, value: V) {
match self.root {
None => {
self.root = Some(Box::new(TreeNode { key, value,
lesser: None, greater: None }));
}
Some(ref mut root) => {
root.set(key, value);
}
}
}
pub fn get_ref(&self, key: K) -> Result<&V, String> {
match self.root {
None => {
return Err("No such key".to_string());
}
Some(ref root) => {
return root.get_ref(key);
}
}
}
pub fn get_mut(&mut self, key: K) -> Result<&mut V, String> {
match self.root {
None => {
return Err("No such key".to_string());
}
Some(ref mut root) => {
return root.get_mut(key);
}
}
}
}
Finally, we have a main function to actually use our tree, so we can see it in action:
fn main() {
let mut tree: Tree<&'static str, f32> = Tree::new();
tree.set("first key", 12.65);
tree.set("second key", 99.999);
tree.set("third key", -128.5);
tree.set("fourth key", 67.21);
println!("tree.get_ref("third key") is {}", match
tree.get_ref("third key") {
Err(_) => {println!("Invalid!"); &0.0},
Ok(x) => x,
});
}