Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
use std::ptr::RawPtr;
type NodeRef<T> = Option<Box<Node<T>>>;
type NodeBackRef<T> = *mut Node<T>;
struct Node<T> {
left: NodeRef<T>,
right: NodeRef<T>,
parent: NodeBackRef<T>,
value: T,
}
struct Tree<T> {
root: NodeRef<T>
}
impl <T:Ord> Tree<T> {
fn new () -> Tree<T> {
Tree{root:None}
}
fn rotate_left(&mut self, mut node:Box<Node<T>>){
match node.right {
None => return,
Some(mut childBox) => {
match get_parent_mut(&mut*node) {
None => {
//we are the root
self.root = Some(childBox);
childBox.parent = RawPtr::null();
}
Some(parent) => {
//we are not the root
childBox.parent = parent as *mut _;
if is_left(node) {
parent.left = Some(childBox);
} else {
parent.right = Some(childBox);
}
}
}
node.right = childBox.left;
node.parent = (&mut*childBox as *mut _);
childBox.left = Some(node);
}
}
}
}
fn get_parent <'a, T> (node: &'a Node<T>) -> Option<&'a Node<T>> {
unsafe{node.parent.to_option()}
}
fn get_parent_mut <'a, T> (node: &'a mut Node<T>) -> Option<&'a mut Node<T>> {
unsafe{std::mem::transmute(node.parent.to_option())}
}
fn is_left <T> (child:&Node<T>) -> bool{
match get_parent(child) {
None => false,
Some(ref parent) => {
match parent.left {
None => false,
Some(leftChild) => {
(child as *const _) == (&*leftChild as *const _)
}
}
}
}
}
fn main(){
let mut tree:Tree<int> = Tree::new();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.