Tree rotation without Rc

gistfile1.rs

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>) {
		let b_left = is_left(node);
		if node.right.is_some() {
			let mut childBox = node.right.take_unwrap();

			node.right = childBox.left.take();
			node.parent = &mut *childBox as *mut _;

			match get_parent_mut(&mut*node) {
				None => {
					//we are the root
					childBox.left = self.root.take();
					childBox.parent = RawPtr::null();
					self.root = Some(childBox);
				}
				Some(ref mut parent) => {
					//we are not the root
					childBox.parent = &mut **parent as *mut _;
					if b_left {
						childBox.left = parent.left.take();
						parent.left = Some(childBox);
					} else {
						childBox.left = parent.right.take();
						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(ref leftChild) => {
					(child as *const _) == (&**leftChild as *const _)
				}
			}
		}
	}
}

fn main(){
	let mut tree:Tree<int> = Tree::new();
}