Skip to content

Instantly share code, notes, and snippets.

@jbaiter
Last active February 6, 2016 22:24
Show Gist options
  • Save jbaiter/6e8176ddd478b50929b5 to your computer and use it in GitHub Desktop.
Save jbaiter/6e8176ddd478b50929b5 to your computer and use it in GitHub Desktop.
type Link<T> = Option<Box<Node<T>>>;
#[derive(Debug)]
pub struct BST<T: Ord> {
root: Link<T>
}
pub struct IntoIter<T: Ord>(Link<T>);
impl<T: Ord + Copy> BST<T> {
pub fn new() -> Self {
BST { root: None }
}
pub fn insert(&mut self, val: T) -> bool {
self.root.insert(val)
}
pub fn search(&self, val: T) -> bool {
self.root.search(val)
}
}
impl<T: Ord + Copy> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
let link = self.0.take();
match link {
None => None,
Some(node) => {
let res = node.value;
self.0 = node.right;
Some(res)
}
}
}
}
impl<T: Ord + Copy> IntoIterator for BST<T> {
type Item = T;
type IntoIter = IntoIter<T>;
fn into_iter(self) -> Self::IntoIter {
IntoIter(self.root)
}
}
trait InsertSearch<T: Ord> {
fn insert(&mut self, entry: T) -> bool;
fn search(&self, entry: T) -> bool;
}
impl<T: Ord> InsertSearch<T> for Link<T> {
fn insert(&mut self, val: T) -> bool {
match *self {
None => {
*self = Some(
Box::new(Node::new(val)));
true
}
Some(ref mut node) => {
if node.value == val {
false
} else if val < node.value {
node.left.insert(val)
} else {
node.right.insert(val)
}
}
}
}
fn search(&self, val: T) -> bool {
match *self {
None => false,
Some(ref node) => {
if val == node.value {
true
} else if val < node.value {
node.left.search(val)
} else {
node.right.search(val)
}
}
}
}
}
#[derive(Debug,Clone)]
struct Node<T: Ord> {
value: T,
left: Link<T>,
right: Link<T>
}
impl<T: Ord> Node<T> {
fn new(val: T) -> Self {
Node {
value: val,
left: None,
right: None,
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment