gistfile1.txt

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, node:&mut Node<T>) {
		match node.right {
			None => return,
			Some(mut childBox) => {
				node.right = childBox.left;
				node.parent = (&mut*childBox as *mut _);
				match get_parent_mut(&mut*node) {
					None => {
						//we are the root
						childBox.left = self.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) {
							childBox.left = parent.left;
							parent.left = Some(childBox);
						} else {
							childBox.left = parent.right;
							parent.right = Some(childBox);
						}
					}
				}
			}
		}
	}
}

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();
}