tree.rs

use generic_array::{GenericArray, ArrayLength};
pub use generic_array::typenum;

use std::ptr;
use std::mem;

pub struct Node<T, N: ArrayLength<NodeRef<T,N>>> {
	value: T,
	index: usize,
	parent: NodeRef<T,N> ,
	children: GenericArray<NodeRef<T, N>, N>
}

impl<T, N: ArrayLength<NodeRef<T,N>>> Node<T,N> {
	fn new(value: T) -> Self {
		Node {
			value: value,
			index: 0,
			parent: NodeRef::default(),
			children: GenericArray::new()
		}
	}
}

pub struct NodeRef<T, N: ArrayLength<NodeRef<T,N>>> {
	ptr: *mut Node<T,N>
}

impl<T, N: ArrayLength<NodeRef<T,N>>> Copy for NodeRef<T,N> {}

#[allow(expl_impl_clone_on_copy)]
impl<T, N: ArrayLength<NodeRef<T,N>>> Clone for NodeRef<T, N> { fn clone(&self) -> NodeRef<T, N> { *self } }

impl<T, N: ArrayLength<NodeRef<T,N>>> Default for NodeRef<T,N> {
	#[inline(always)]
	fn default() -> Self {
		NodeRef {
			ptr: ptr::null_mut()
		}
	}
}

impl<T, N: ArrayLength<NodeRef<T,N>>> NodeRef<T,N> {
	fn is_null(&self) -> bool {
		self.ptr.is_null()
	}
}
pub struct Tree<T, N: ArrayLength<NodeRef<T,N>>> {
	node: NodeRef<T,N>
}

impl<T, N: ArrayLength<NodeRef<T,N>>> Drop for Tree<T,N> {
	fn drop(&mut self) {
		// Traverse to root node
		while self.parent().is_some() {}
		
		let mut stk = Vec::new();
		stk.push(self.get_ref());
		while !stk.is_empty() {
			
			//let children = unsafe {(*stk.pop().unwrap().ptr).children.iter()};
			let top = stk.pop().unwrap();
			let children = unsafe {(*top.ptr).children.iter()};

			for child in children {
				if !child.is_null() {
					stk.push(*child);
				}
			}

			unsafe {
				Box::from_raw(top.ptr);
			}
		}
	}
}

impl<T, N: ArrayLength<NodeRef<T,N>>> Tree<T,N> {
	/// Construct a new Tree with a default value of T type.
	pub fn new(value: T) -> Self {
		Tree {
			node: NodeRef {
				ptr: Box::into_raw(Box::new(Node::new(value)))
			}
		}
	}

	pub fn parent(&mut self) -> Option<usize> {
		let parent = unsafe {(*self.node.ptr).parent};
		if parent.is_null() {
			None
		}else {
			let index = unsafe { (*self.node.ptr).index };
		    self.node = parent;
		    Some(index)
		}
	}

	pub fn child(&mut self, index: usize) -> bool {
		if index >= N::to_usize() {
			return false;
		}
		let child = unsafe {*(*self.node.ptr).children.get_unchecked(index)};
		if child.is_null() {
			false
		} else {
			self.node = child;
			true
		}
	}

	pub fn take(&mut self, index: usize) -> Option<Tree<T,N>> {
		let child = unsafe { (*self.node.ptr).children[index]};
		if child.is_null() {
			None
		} else {
			unsafe {
				(*child.ptr).parent = NodeRef::default();
				(*self.node.ptr).children[index] = NodeRef::default();
			}
			Some(Tree {node:child})
		}
	}

	pub fn attach(&mut self,mut tree: Tree<T,N>, index: usize) -> Option<Tree<T, N>> {
		if index >= N::to_usize() {
			return None;
		}
		let child = unsafe {*(*self.node.ptr).children.get_unchecked(index)};
		let removed = if child.is_null() {
			None
		} else {
			unsafe { 
				(*child.ptr).parent = NodeRef::default();
			}
			Some(Tree{node: child})
		};

		while tree.parent().is_some() {}

		unsafe {
			(*tree.node.ptr).parent = self.node;
			(*tree.node.ptr).index = index;
			(*self.node.ptr).children[index] = tree.node;
		};
		mem::forget(tree);
		removed
	}

	fn get_ref(&self) -> NodeRef<T,N> {
		self.node
	}

	pub fn value(&self) -> &T {
		unsafe {&(*self.node.ptr).value}
	}

	pub fn value_mut(&self) -> &mut T {
		unsafe {&mut (*self.node.ptr).value}
	}
}