/*******************************************************************************

Description: A Red Black Tree container

Authors: Clay Smith as porter and maintainer. Original code and author can be found <a href="http://eternallyconfuzzled.com/tuts/redblack.html">here.</a> 

Liscense: Public domain. 


Examples:
----------------------------------------
import arc.templates.redblacktree; 

int main() {

	auto RedBlackTree!(int) tree = new RedBlackTree!(int); 

	for (int i = 0; i < 10; i++)
		tree.add(i); 

	//tree.destroy(); 
	//tree.destroy(); 

	auto RedBlackTree!(int) t2 = new RedBlackTree!(int)(tree); 

	foreach(RedBlackTree!(int).Node n; t2)
		writefln(n.data); 

//	tree.print(); 

	RedBlackTree!(int).Node n = tree.search(8); 
	if (n !is null)
		writefln("found value ", n.data); 
	if (n is null)
		writefln("null"); 

	if (99 in tree)
	{
		writefln("99 is in tree"); 
	}

	writefln("hi");

	if (tree.isValid)
		writefln("Tree is valid"); 

   return 0;
}

----------------------------------------

*******************************************************************************/

module arc.templates.redblacktree;

import std.stdio; 

/// Templated Red Black Tree container class 
class RedBlackTree(T)
{
  public:
	/// create blank tree
	this()
	{
		root = null;
		size = 0; 
	}

	/// create a tree based off of another tree 
	this(inout RedBlackTree tree)
	{
		duplicate(tree); 
	}

	/// destroy all contents in tree 
	~this()
	{
		// remove all elements from tree and set root null and size to 0 
		destroy(); 
	}

	/// print contents of the tree with writefln 
	void print ()
	{
	  print_r( root );
	}

	/// add data to the tree 
	bool add( T data )
	{
		root = add_r(root, data);
		root.red = 0;
		size++; 
		return true;
	}

	/// remove data from tree 
	bool remove ( T data )
	{
	  int done = 0;

	  root = remove_r ( root, data, done );
	  
	  if ( root !is null )
		root.red = 0;

	  size--; 
	  return true;
	}

	/// search for a key in the tree and return it if found
	Node search(T data, Node node = null) 
	{
		if(node is null)
			node = root;
			
		int nResult;
		
		while(node !is null && (nResult = (data == node.data ? 0 : (data >= node.data ? -1 : 1))) != 0)
			node = node.link[nResult < 0];
			
		return node is null ? null : node;
	}  

	/// remove all data from the tree  
	void destroy()
	{
		destroy_r(root); 

		size = 0;
		root = null;
	}
	
	/// returns whether the binary tree is valid or not
	int isValid() { return assertNode(root); } 

	/// return tree nodes size
	int getSize()    {  return size;  }

	/// true if empty
	bool isEmpty()    {  return size == 0; }

	/// merge data from tree into this one
	void merge(inout RedBlackTree tree)
	{
		createCopy(tree.root);
	}

	/// make this tree a duplicate of another  
	void duplicate(inout RedBlackTree tree)
	{
		destroy();
		createCopy(tree.root); 
		size = tree.size; 
	}

	// foreach iterator forwards 
	int opApply(int delegate(inout Node) dg)
	{
		return applyForward(root, dg); 
	}

	// simply return whether value is in tree 'if (4 in tree)'
	bool opIn_r(T data)
	{
		if (search(data) is null)
			return false;
			
		return true;
	}

  private: 
	// copy from leafSrc into leafDst in order
	void createCopy(Node leafSrc)
	{
		if (leafSrc !is null)
		{
			createCopy(leafSrc.link[LEFT]);

			add(leafSrc.data); 
	   
			createCopy(leafSrc.link[RIGHT]);
		}
	}
  
	// iterate tree forwards 
	int applyForward(Node node, int delegate(inout Node) dg)
	{
      int result = 0;
	  
      while(node !is null) 
      {
        result = applyForward(node.link[LEFT], dg);
        if (result) return result;

        result = dg(node);
        if (result) return result;
        
        node = node.link[RIGHT];
      }

      return result;		
	}

	// recursive remove node 
	Node remove_r (Node node, T data, inout int done )
	{
	  if ( node is null )
		done = 1;
	  else {
		int dir;

		if ( node.data == data ) 
		{
		  if ( node.link[LEFT] is null
			|| node.link[RIGHT] is null )
		  {
			Node save = node.link[node.link[LEFT] is null];

			/* Case 0 */
			if ( isRed ( node ) )
			  done = 1;
			else if ( isRed ( save ) ) {
			  save.red = 0;
			  done = 1;
			}

			delete node;

			return save;
		  }
		  else {
			Node heir = node.link[LEFT];

			while ( heir.link[RIGHT] !is null )
			  heir = heir.link[RIGHT];

			node.data = heir.data;
			data = heir.data;
		  }
		}

		dir = node.data < data;
		node.link[dir] = remove_r ( node.link[dir], data, done );

		if ( !done )
		  node = remove_balance ( node, dir, done );
	  }

	  return node;
	}

	// remove and balances the nodes 
	Node remove_balance (Node node, int dir, inout int done )
	{
	  Node p = node;
	  Node s = node.link[!dir];

	  /* Case reduction, remove red sibling */
	  if ( isRed ( s ) ) {
		node = singleRotation ( node, dir );
		s = p.link[!dir];
	  }

	  if ( s !is null ) {
		if ( !isRed ( s.link[LEFT] )
		  && !isRed ( s.link[RIGHT] ) )
		{
		  if ( isRed ( p ) )
			done = 1;
		  p.red = 0;
		  s.red = 1;
		}
		else {
		  int save = node.red;

		  if ( isRed ( s.link[!dir] ) )
			node = singleRotation ( p, dir );
		  else
			node = doubleRotation ( p, dir );

		  node.red = save;
		  node.link[LEFT].red = 0;
		  node.link[RIGHT].red = 0;
		  done = 1;
		}
	  }

	  return node;
	}

	// add recursive
	Node add_r (Node node, T data )
	{
	  if ( node is null )
		node = new Node( data );
	  else if ( data != node.data ) {
		int dir = node.data < data;

		node.link[dir] =
		  add_r ( node.link[dir], data );

		if ( isRed ( node.link[dir] ) ) {
		  if ( isRed ( node.link[!dir] ) ) {
			/* Case 1 */
			node.red = 1;
			node.link[LEFT].red = 0;
			node.link[RIGHT].red = 0;
		  }
		  else {
			/* Cases 2 & 3 */
			if ( isRed ( node.link[dir].link[dir] ) )
			  node = singleRotation ( node, !dir );
			else if ( isRed ( node.link[dir].link[!dir] ) )
			  node = doubleRotation ( node, !dir );
		  }
		}
	  }

	  return node;
	}
  
	// recursive print routine
	void print_r ( Node node )
	{
	  if ( node !is null ) {
		print_r ( node.link[LEFT] );
		writefln (node.data);
		print_r ( node.link[RIGHT] );
	  }
	}

	// recursive destruction of all tree elements 
	void destroy_r(Node node)
	{
		if (node !is null)
		{
			destroy_r(node.link[LEFT]);
			destroy_r(node.link[RIGHT]);
			delete node; node = null;  
		}
	}

	// assert node 
	int assertNode ( Node node )
	{
	  int lh, rh;

	  if ( node is null )
		return 1;
	  else {
		Node ln = node.link[LEFT];
		Node rn = node.link[RIGHT];

		/* Consecutive red links */
		if ( isRed ( node ) ) {
		  if ( isRed ( ln ) || isRed ( rn ) ) {
			writefln ( "Red violation" );
			return 0;
		  }
		}

		lh = assertNode ( ln );
		rh = assertNode ( rn );

		/* Invalid binary search tree */
		if ( ( ln !is null && ln.data >= node.data )
		  || ( rn !is null && rn.data <= node.data ) )
		{
		  writefln ( "Binary tree violation" );
		  return 0;
		}

		/* Black height mismatch */
		if ( lh != 0 && rh != 0 && lh != rh ) {
		  writefln ( "Black violation" );
		  return 0;
		}

		/* Only count black links */
		if ( lh != 0 && rh != 0 )
		  return isRed ( node ) ? lh : lh + 1;
		else
		  return 0;
	  }
	}

	// single rotation 
	Node singleRotation (Node node, int dir )
	{
	  Node save = node.link[!dir];

	  node.link[!dir] = save.link[dir];
	  save.link[dir] = node;

	  node.red = 1;
	  save.red = 0;

	  return save;
	}

	// double rotation 
	Node doubleRotation (Node node, int dir )
	{
	  node.link[!dir] =	singleRotation ( node.link[!dir], !dir );
	  return singleRotation ( node, dir );
	}
  
	// node is red? or not
	int isRed ( Node node )
	{
	  return node !is null && node.red == 1;
	}

	enum { LEFT=0, RIGHT=1 }

	// a tree node 
	class Node 
	{
		this(T data)
		{
			this.data = data; 
			red = 1; // 1 is red, 0 is black 
			link[LEFT] = null; 
			link[RIGHT] = null; 
		}
		
		int red;
		T data;
		Node link[2];
	}

	// root node of our tree 
	Node root;
	// number of items in the tree 
	int size; 
}