irr::core::map replacemant of the one from STL

[katoun]

Hello.
Here is the code foe a core::map that I have made for my game engine:D
It is started from irrlicht code and it tis independant of other classes so it can work with Irrlicht to expecialy that I use the typedefine from it:D
Here it is:

Code: Select all

// Copyright 2006-2007 by Kat'Oun

#ifndef _MAP_H_
#define _MAP_H_

#include <core/Types.h>

namespace game
{
namespace core
{

template <class KeyType, class ValueType> 
class map
{

	template <class KeyType, class ValueType> 
	class RBTree
	{
	public:
	
		RBTree(const KeyType& k, const ValueType& v)
		:mKey(k),mValue(v),mLeftChild(0),mRightChild(0),mParent(0),mIsRed(true)
		{}

	
		virtual ~RBTree(){}

	
		void SetLeftChild(RBTree* p)  { mLeftChild=p; if (p) p->SetParent(this);}
		void SetRightChild(RBTree* p) { mRightChild=p;if (p) p->SetParent(this);}
		void SetParent(RBTree* p)	   { mParent=p; }

		void SetValue(const ValueType& v)  { mValue = v; }
	

		void SetRed()        { mIsRed = true; }
		void SetBlack()      { mIsRed = false; }

		RBTree* GetLeftChild() const  { return mLeftChild; }
		RBTree* GetRightChild() const { return mRightChild; }
		RBTree* GetParent() const     { return mParent; }

		ValueType GetValue() const         { return mValue; }
		KeyType GetKey() const             { return mKey; }

	
		bool IsRoot() const           { return mParent==0; }
		bool IsLeftChild() const      { return mParent!=0 && mParent->GetLeftChild()==this; }
		bool IsRightChild() const     { return mParent!=0 && mParent->GetRightChild()==this; }
		bool IsLeaf() const           { return mLeftChild==0 && mRightChild==0; }
		unsigned int GetLevel() const { if (IsRoot()) return 1; else return GetParent()->GetLevel() + 1; }


		bool IsRed() const   { return mIsRed; };
		bool IsBlack() const { return !mIsRed; };

	private:
	
		RBTree();
	
		RBTree*	mLeftChild;
		RBTree*	mRightChild;

		RBTree*	mParent;

		KeyType			mKey;
		ValueType		mValue;


		bool mIsRed;

	};

public:
	
	typedef RBTree<KeyType,ValueType> Node;
	
	
	class Iterator
	{
	public:
		
		Iterator():mRoot(0),mCur(0){}

		// Constructor(Node*)
		Iterator(Node* root):mRoot(root)
		{ 
			Reset();
		}

		// Copy constructor
		Iterator(const Iterator& src):mRoot(src.mRoot),mCur(src.mCur){}

		
		void Reset(bool atLowest=true) 
		{ 
			if (atLowest) 
				mCur = Min(mRoot); 
			else 
				mCur = Max(mRoot);
		}
		
		bool atEnd() const
		{ 
			return mCur==0; 
		}

		Node* GetNode() 
		{ 
			return mCur;	
		}
		
		Iterator& operator=(const Iterator& src) 
		{ 
			mRoot = src.mRoot; 
			mCur = src.mCur; 
			return (*this);
		}
	
		void operator++(int)
		{ 
			Inc(); 
		}
		
		void operator--(int)
		{
			Dec();
		}

	
		Node* operator -> () 
		{ 
			return GetNode();	
		}
		
		Node& operator*   () 
		{ 
			if (atEnd())
			{
				throw "Iterator at end";			
			}
			return *mCur; 
		}

	private:
		
		Node* Min(Node* n)
		{
			while(n && n->GetLeftChild())
				n = n->GetLeftChild();
			return n;
		}
	
		Node* Max(Node* n)
		{
			while(n && n->GetRightChild())
				n = n->GetRightChild();
			return n;
		}
	
		void Inc()
		{
			// Already at end?
			if (mCur==0)
				return;

			if (mCur->GetRightChild())
			{
				// If current node has a right child, the next higher node is the 
				// node with lowest key beneath the right child.
				mCur =  Min(mCur->GetRightChild());
			}
			else if (mCur->IsLeftChild())
			{
				// No right child? Well if current node is a left child then
				// the next higher node is the parent
				mCur = mCur->GetParent();
			}
			else
			{
				// Current node neither is left child nor has a right child.
				// Ie it is either right child or root
				// The next higher node is the parent of the first non-right
				// child (ie either a left child or the root) up in the
				// hierarchy. Root's parent is 0.
				while(mCur->IsRightChild())
					mCur = mCur->GetParent();
				mCur =  mCur->GetParent();
			}
		}
		
		void Dec()
		{
			// Already at end?
			if (mCur==0)
				return;

			if (mCur->GetLeftChild())
			{
				// If current node has a left child, the next lower node is the 
				// node with highest key beneath the left child.
				mCur =  Max(mCur->GetLeftChild());
			}
			else if (mCur->IsRightChild())
			{
				// No left child? Well if current node is a right child then
				// the next lower node is the parent
				mCur =  mCur->GetParent();
			}
			else
			{
				// Current node neither is right child nor has a left child.
				// Ie it is either left child or root
				// The next higher node is the parent of the first non-left
				// child (ie either a right child or the root) up in the
				// hierarchy. Root's parent is 0.

				while(mCur->IsLeftChild())
					mCur = mCur->GetParent();
				mCur =  mCur->GetParent();
			}
		}
		
		Node* mRoot;
		Node* mCur;
	}; // Iterator

	//--------------------------------------------------------
	// class map::ParentFirstIterator. 
	// Traverses the tree from top to bottom. Typical usage is 
	// when storing the tree structure, because when reading it 
	// later (and inserting elements) the tree structure will
	// be the same.
	//--------------------------------------------------------
	class ParentFirstIterator
	{
	public:

	
		ParentFirstIterator():mRoot(0),mCur(0)
		{
		}

		
		explicit ParentFirstIterator(Node* root):mRoot(root),mCur(0)
		{ 
			Reset(); 
		}

		void Reset() 
		{ 
			mCur = mRoot; 
		}

		
		bool atEnd() const 
		{ 
			return mCur==0; 
		}

		Node* GetNode() 
		{ 
			return mCur;	
		}

		
		ParentFirstIterator& operator=(const ParentFirstIterator& src) 
		{ 
			mRoot = src.mRoot; mCur = src.mCur; return (*this);
		}

		
		void operator++(int) 
		{ 
			Inc(); 
		}

		
		Node* operator -> () 
		{ 
			return GetNode();	
		}

		Node& operator*   () 
		{ 
			if (atEnd())
				throw "ParentFirstIterator at end";			
			return *GetNode(); 
		}

	private:
		
		void Inc()
		{
			// Already at end?
			if (mCur==0)
				return;

			// First we try down to the left
			if (mCur->GetLeftChild())
			{
				mCur =  mCur->GetLeftChild();
			}
			else if (mCur->GetRightChild())
			{
				// No left child? The we go down to the right.
				mCur = mCur->GetRightChild();
			}
			else
			{
				// No children? Move up in the hierarcy until
				// we either reach 0 (and are finished) or
				// find a right uncle.
				while (mCur!=0)
				{
					// But if parent is left child and has a right "uncle" the parent
					// has already been processed but the uncle hasn't. Move to 
					// the uncle.
					if (mCur->IsLeftChild() && mCur->GetParent()->GetRightChild())
					{
						mCur = mCur->GetParent()->GetRightChild();
						return;
					}
					mCur = mCur->GetParent();
				}
			}
		}
		
		Node* mRoot;
		Node* mCur;

	}; // ParentFirstIterator

	//--------------------------------------------------------
	// class map::ParentLastIterator. 
	// Traverse the tree from bottom to top.
	// Typical usage is when deleting all elements in the tree
	// because you must delete the children before you delete
	// their parent.
	//--------------------------------------------------------
	class ParentLastIterator
	{
	public:
		
		ParentLastIterator():mRoot(0),mCur(0){}

		
		explicit ParentLastIterator(Node* root):mRoot(root),mCur(0)
		{ 
			Reset();
		}
		
		void Reset() 
		{ 
			mCur = Min(mRoot); 
		}

	
		bool atEnd() const 
		{ 
			return mCur==0; 
		}
		
		Node* GetNode() 
		{ 
			return mCur;	
		}

		ParentLastIterator& operator=(const ParentLastIterator& src) 
		{ 
			mRoot = src.mRoot; 
			mCur = src.mCur; 
			return (*this);
		}
		
		void operator++(int) 
		{ 
			Inc(); 
		}

		Node* operator -> () 
		{ 
			return GetNode();	
		}
		
		Node& operator*   () 
		{ 
			if (atEnd())
				throw "ParentLastIterator at end";			
			return *GetNode(); 
		}
	private:
		
		Node* Min(Node* n)
		{
			while(n!=0 && (n->GetLeftChild()!=0 || n->GetRightChild()!=0))
			{
				if (n->GetLeftChild())
					n = n->GetLeftChild();
				else
					n = n->GetRightChild();
			}
			return n;
		}
		
		void Inc()
		{
			// Already at end?
			if (mCur==0)
				return;

			// Note: Starting point is the node as far down to the left as possible.

			// If current node has an uncle to the right, go to the
			// node as far down to the left from the uncle as possible
			// else just go up a level to the parent.
			if (mCur->IsLeftChild() && mCur->GetParent()->GetRightChild())
			{
				mCur = Min(mCur->GetParent()->GetRightChild());
			}
			else
				mCur = mCur->GetParent();
		}

	
		Node* mRoot;
		Node* mCur;
	}; // ParentLastIterator

	// AccessClass is a temparoary class used with the [] operator.
	// It makes it possible to have different behavior in situations like:
	// myTree["Foo"] = 32; 
	//   If "Foo" already exist, just update its value else insert a new 
	//   element.
	// int i = myTree["Foo"]
	// If "Foo" exists return its value, else throw an exception.
	 
	class AccessClass
	{
		// Let map be the only one who can instantiate this class.
		friend class map<KeyType, ValueType>;
	
	public:

		// Assignment operator. Handles the myTree["Foo"] = 32; situation
		void operator=(const ValueType& value)
		{
			// Just use the Set method, it handles already exist/not exist situation
			mTree.Set(mKey,value);
		}

		// ValueType operator
		operator ValueType()
		{
			Node* node = mTree.Find(mKey);

			// Not found
			if (node==0)
			{
				throw "Item not found";
			}

			return node->GetValue();
		}


	private:
		
		AccessClass(map& tree, const KeyType& key):mTree(tree),mKey(key){}
		
		AccessClass();

		
		map& mTree;
		const KeyType& mKey;
	}; // AccessClass

		
	// Constructor.
	map():mRoot(0),mSize(0){}

	// Destructor
	~map()
	{ 
		DeleteAll(); 
	}

	//------------------------------
	// Public Commands
	//------------------------------

	bool Insert(const KeyType& keyNew, const ValueType& v)
	{
		// First insert node the "usual" way (no fancy balance logic yet)
		Node* newNode = new Node(keyNew,v);
		if (!Insert(newNode))
		{
			delete newNode;
			return false;
		}

		// Then attend a balancing party
		while  (!newNode->IsRoot() && (newNode->GetParent()->IsRed()))
		{
			if ( newNode->GetParent()->IsLeftChild()) 
			{
				// If newNode is a left child, get its right 'uncle'
				Node* newNodesUncle = newNode->GetParent()->GetParent()->GetRightChild();
				if ( newNodesUncle!=0 && newNodesUncle->IsRed())
				{
					// case 1 - change the colours
					newNode->GetParent()->SetBlack();
					newNodesUncle->SetBlack();
					newNode->GetParent()->GetParent()->SetRed();
					// Move newNode up the tree
					newNode = newNode->GetParent()->GetParent();
				}
				else 
				{
					// newNodesUncle is a black node
					if ( newNode->IsRightChild()) 
					{
					// and newNode is to the right
					// case 2 - move newNode up and rotate
					newNode = newNode->GetParent();
					RotateLeft(newNode);
					}
					// case 3
					newNode->GetParent()->SetBlack();
					newNode->GetParent()->GetParent()->SetRed();
					RotateRight(newNode->GetParent()->GetParent());
				}
			}
			else 
			{
				// If newNode is a right child, get its left 'uncle'
				Node* newNodesUncle = newNode->GetParent()->GetParent()->GetLeftChild();
				if ( newNodesUncle!=0 && newNodesUncle->IsRed())
				{
					// case 1 - change the colours
					newNode->GetParent()->SetBlack();
					newNodesUncle->SetBlack();
					newNode->GetParent()->GetParent()->SetRed();
					// Move newNode up the tree
					newNode = newNode->GetParent()->GetParent();
				}
				else 
				{
					// newNodesUncle is a black node
					if ( newNode->IsLeftChild()) 
					{
						// and newNode is to the left
						// case 2 - move newNode up and rotate
						newNode = newNode->GetParent();
						RotateRight(newNode);
					}
					// case 3
					newNode->GetParent()->SetBlack();
					newNode->GetParent()->GetParent()->SetRed();
					RotateLeft(newNode->GetParent()->GetParent());
				}

			}
		}
		// Color the root black
		mRoot->SetBlack();
		return true;
	}

	// Set. If the key already exist just replace the value
	// else insert a new element.
	void Set(const KeyType& k, const ValueType& v)
	{
		Node* p = Find(k);
		if (p)
		{
			p->SetValue(v);
		}
		else
			Insert(k,v);
	}

	//Remove a node from the tree.
	//Return the removed node. 
	Node* Remove(const KeyType& k)
	{
		Node* p = Find(k);
		if (p == 0) return false;

		// Rotate p down to the left until it has no right child, will get there
		// sooner or later.
		while(p->GetRightChild())
		{
			// "Pull up my right child and let it knock me down to the left"
			RotateLeft(p);
		}
		// p now has no right child but might have a left child
		Node* left = p->GetLeftChild(); 

		// Let p's parent point to p's child instead of point to p
		if (p->IsLeftChild())
		{
			p->GetParent()->SetLeftChild(left);
		}
		else if (p->IsRightChild())
		{
			p->GetParent()->SetRightChild(left);
		}
		else
		{
			// p has no parent => p is the root. 
			// Let the left child be the new root.
			SetRoot(left);
		}

		// p is now gone from the tree in the sense that 
		// no one is pointing at it, so return it.
		
		mSize--;
		return p;
	}

	// Remove a node.Return true if the node could
	// be found (and was removed) in the tree.
	bool Delete(const KeyType& k)
	{
		Node* p = Find(k);
		if (p == 0) return false;

		// Rotate p down to the left until it has no right child, will get there
		// sooner or later.
		while(p->GetRightChild())
		{
			// "Pull up my right child and let it knock me down to the left"
			RotateLeft(p);
		}
		// p now has no right child but might have a left child
		Node* left = p->GetLeftChild(); 

		// Let p's parent point to p's child instead of point to p
		if (p->IsLeftChild())
		{
			p->GetParent()->SetLeftChild(left);
		}
		else if (p->IsRightChild())
		{
			p->GetParent()->SetRightChild(left);
		}
		else
		{
			// p has no parent => p is the root. 
			// Let the left child be the new root.
			SetRoot(left);
		}

		// p is now gone from the tree in the sense that 
		// no one is pointing at it. Let's get rid of it.
		delete p;
			
		mSize--;
		return true;
	}

	// Wipe out the entire tree.
	void DeleteAll()
	{
		ParentLastIterator i(GetParentLastIterator());

		while(!i.atEnd())
		{
			Node* p = i.GetNode();
			i++; // Increment it before it is deleted
			     // else iterator will get quite confused.
			delete p;
		}
		mRoot = 0;
		mSize= 0;
	}

	// Is the tree empty?
	bool IsEmpty() const 
	{ 
		return mRoot == 0; 
	}

	// Search for the node.
	// Returns 0 if node couldn't be found.
	Node* Find(const KeyType& keyToFind) const
	{
		Node* pNode = mRoot;

		while(pNode!=0)
		{
			KeyType key(pNode->GetKey());

			if (keyToFind == key)
			{
				// Found it! Return it! Wheee!
				return pNode;
			}			
			else if (keyToFind < key)
			{
				pNode = pNode->GetLeftChild();
			}
			else //keyToFind > key
			{
				pNode = pNode->GetRightChild();
			}
		}

		return 0;
	}
	
	// Get the root element. 0 if tree is empty.
	Node* GetRoot() const 
	{ 
		return mRoot; 
	}

	// Number of nodes in the tree.
	u32 Size() const 
	{ 
		return mSize; 
	}

	//------------------------------
	// Public Iterators
	//------------------------------
	Iterator GetIterator()			 
	{ 
		Iterator it(GetRoot());
		return it; 
	}
	ParentFirstIterator GetParentFirstIterator() 
	{
		ParentFirstIterator it(GetRoot());
		return it; 
	}
	ParentLastIterator GetParentLastIterator()
	{   
		ParentLastIterator it(GetRoot());
		return it;	
	}
	
	//------------------------------
	// Public Operators
	//------------------------------

	// operator [] for accesss to elements
	AccessClass operator[](const KeyType& k) 
	{
		return AccessClass(*this, k);
	}
private:

	//------------------------------
	// Disabled methods
	//------------------------------
	// Copy constructor and assignment operator deliberately 
	// defined but not implemented. The tree should never be 
	// copied, pass along references to it instead (or use auto_ptr to it).
	explicit map(const map& src); 
	map& operator = (const map& src);

	void SetRoot(Node* newRoot)
	{
		mRoot = newRoot;
		if (mRoot!=0)
			mRoot->SetParent(0);
	}

	// Insert a node into the tree without using any fancy balancing logic.
	// Returns false if that key already exist in the tree.
	bool Insert(Node* newNode)
	{
		bool result=true; // Assume success

		if (mRoot==0)
		{
			SetRoot(newNode);
			mSize = 1;
		}
		else
		{
			Node* pNode = mRoot;
			KeyType keyNew = newNode->GetKey();
			while (pNode)
			{
				KeyType key(pNode->GetKey());

				if (keyNew == key)
				{
					result = false;
					pNode = 0;
				} 
				else if (keyNew < key)
				{
					if (pNode->GetLeftChild()==0)
					{
						pNode->SetLeftChild(newNode);
						pNode = 0;
					}
					else
					{
						pNode = pNode->GetLeftChild();
					}
				} 
				else 
				{
					// keyNew > key
					if (pNode->GetRightChild()==0)
					{
						pNode->SetRightChild(newNode);
						pNode = 0;
					}
					else
					{
						pNode = pNode->GetRightChild();
					}
				}
			}

			if (result)
			{
				mSize++;
			}
		}
		
		return result;
	}

	// Rotate left.
	// Pull up node's right child and let it knock node down to the left
	void RotateLeft(Node* p)
	{		
		Node* right = p->GetRightChild();

		p->SetRightChild(right->GetLeftChild());
		
		if (p->IsLeftChild())
			p->GetParent()->SetLeftChild(right);
		else if (p->IsRightChild())
			p->GetParent()->SetRightChild(right);
		else
		{
			SetRoot(right);
		}
		right->SetLeftChild(p);
	}

	// Rotate right.
	// Pull up node's left child and let it knock node down to the right
	void RotateRight(Node* p)
	{		

		Node* left = p->GetLeftChild();

		p->SetLeftChild(left->GetRightChild());
		
		if (p->IsLeftChild())
			p->GetParent()->SetLeftChild(left);
		else if (p->IsRightChild())
			p->GetParent()->SetRightChild(left);
		else
		{
			SetRoot(left);
		}
		left->SetRightChild(p);
	}

	//------------------------------
	// Private Members
	//------------------------------
	Node* mRoot; // The top node. 0 if empty.	
	u32 mSize; // Number of nodes in the tree

};

} // end namespace core
} // end namespace game

#endif // _MAP_H_

and to use one of these something like this:

Code: Select all

bool Exit=false;
u64 Key=0;

	core::map<u64, f32>  M;

	for(u64 i=0;i<rand()%1000;i++)
		M.Insert(i,(f32)(rand()%40000));

	

	while(!Exit)
	{
		char c;
		cin>>c;

		if(c=='.')
			Exit=true;
		else if(c=='s')
		{
			cin>>Key;
			core::map<u64, f32>::Node* n=M.Find(Key);
			if(n==NULL)
				cout<<"Not found"<<endl;
			else
				cout<<"Found : "<<n->GetValue()<<endl;


		}
		else if(c=='p')
		{
			core::map<u64,f32>::Iterator it=M.GetIterator();
			while(!it.atEnd())
			{
				core::map<u64,f32>::Node* n=it.GetNode();
				cout<<n->GetValue()<<endl;
				it++;
			}

		}
		else if(c=='r')
		{
			M.DeleteAll();
			for(u64 i=0;i<900000;i++)
				M.Insert(i,(f32)(rand()%4000000000)+rand());

		}		
		
	}

Good luck with it.

[Eternl Knight]

Now THIS needs to make it into Irrlicht. There are MANY different uses in Irrlicht that would benefit from using maps. Even in the current engine, there are areas where sorted arrays are used where a map would work better.

--EK

[drac_gd]

Nice.. what is the licence for the copywrite?

[katoun]

Free source code
It is made out of free source code, started form a Red Black Tree implementation and then I made it a core::map.

[TheRLG]

What kind of speed difference, if any, is there between your implementation and STL implementation?

[Eternl Knight]

That would depend on the implementation of STL really. Although, having a look at my version of STL, they are using a red-black tree concept for their implementation as well.

--EK

[bitplane]

I just emailed katoun and asked if its okay to add this to the core. I've tidied it up a bit, mostly just renamed some functions so they fit with irrlicht's capitalization policy.
hopefully Irrlicht will have a core::map class soon

[hybrid]

But be careful with the code's origins. I guess some parts are closely related to gcc's map implementation which might raise GPL violations
EDIT: I did not mean that this code is actually from gcc's STL implementation, but even still we have to be careful if this code has some predecessor. And this is far more likely if there are several examples available on the net.

[Eternl Knight]

Well, red/black tree implementations are a dime a dozen. That and there really is only a limited number of ways it can be done - so unless you have strong evidence it came from GCC, I would think it safe.

Seriously - I can code a red/black implementation from scratch and it would probably look quite similar. And I've never looked at GCC source code (compilers are not really interesting code for me).

--EK

[Saturn]

I guess some parts are closely related to gcc's map.

Why do you believe this? It doesn't even look remotely similar. The interface is totally different, the inheritance relationships, the iterators, coding style and so on...

[Eternl Knight]

No offense, hybrid, but I think you're being a little too paranoid. Red/black tree implementations have been described ad nauseum by computer science professors since the dawn of assembly code.

There are so many overlapping implementations that unless there were exact code matches - it would be next to impossible for someone to prove copyright infringement based on the small amount of code the tree implementation takes.

You accept other patches without problems - what is so special about this that makes you hesitate?

--EK

[hybrid]

I just said that bitplane should take care of the code origins. I guess that defining a general container class is much more likely to be closely related to other implementations than, e.g., a mesh loader using the Irrlicht vertex and mesh buffer base classes. Moreover, there had been another proposal of this stuff some time ago which also did not make it into the core (for whatever reasons, I was not in the team at that time).
But I won't reject the code, nor do I have any proof for a copyright violation. And yes, I try to check those things for other larger classes, too

[katoun]

bitplane

just emailed katoun and asked if its okay to add this to the core. I've tidied it up a bit, mostly just renamed some functions so they fit with irrlicht's capitalization policy.
hopefully Irrlicht will have a core::map class soon Smile

YES it is ok . Do it!
I havent aswered your email because I have a lot of work and I forgot to check my email.

[CuteAlien]

Free source code :D
It is made out of free source code, started form a Red Black Tree implementation and then I made it a core::map. :D

Unfortunatly that's not enough information. Free Source code does not necessarly mean it's compatible with the zlib-license. Can you give us the information from where you got the base for your source code?

[katoun]

Code: Select all

/*=====================================================================
	BinTree.h - Binary tree template class

	Author: Per Nilsson

	Freeware and no copyright on my behalf. However, if you use the 
	code in some manner	I'd appreciate a notification about it
	perfnurt@hotmail.com

	The Red-Black insertion algorithm is to some extent based upon
	the example in 
	http://www.oopweb.com/Algorithms/Documents/PLDS210/Volume/red_black.html

Happy now?
Here is all of the file I have inspired my core::map class

Code: Select all

/*=====================================================================
	BinTree.h - Binary tree template class

	Author: Per Nilsson

	Freeware and no copyright on my behalf. However, if you use the 
	code in some manner	I'd appreciate a notification about it
	perfnurt@hotmail.com

	The Red-Black insertion algorithm is to some extent based upon
	the example in 
	http://www.oopweb.com/Algorithms/Documents/PLDS210/Volume/red_black.html

	Classes:

		// The node class.
		template <class KeyType, class ValueType> class BinTreeNode

		// The tree class
		template <class KeyType, class ValueType> class BinTree
		{
		public:
			// Regular low->high (++) and high->low (--) iterator
		    class Iterator

			// Top to bottom iterator
			class ParentFirstIterator

			// Bottom to top iterator
			class ParentLastIterator

			// Top to bottom, level by level iterator
			class ByLevelIterator
		}

	Requirements:
		The KeyType class must support:
			1. < and == operations.
			2. Copy construction.

		The ValueType must support:
			1. Copy construction.
			2. Assignment operation (=) if BinTreeNode::SetValue is used

    Dependencies:
		No external dependencies

    #define NO_REDBLACK to deactivate the red-black functionality. 
	Tree will still work, but nothing is done in regards of balancing.

=====================================================================*/
#ifndef _BINTREE_H_
#define _BINTREE_H_

//------------------------------------------------------------
// class BinTreeNode is the element type of the BinTree tree. 
//------------------------------------------------------------
template <class KeyType, class ValueType> 
class BinTreeNode
{
public:
	//------------------------------
	// Public Construction
	//------------------------------

	// Constructor(Key, Value)
	BinTreeNode(const KeyType& k, const ValueType& v)
		:mKey(k),mValue(v),mLeftChild(0),mRightChild(0),mParent(0)
#ifndef NO_REDBLACK
		,mIsRed(true)
#endif
	{}

	// Destructor
	virtual ~BinTreeNode(){}

	//------------------------------
	// Public Commands
	//------------------------------
	// Set methods.
	// Set*Child also updates the the child's parent attribute.
	void SetLeftChild(BinTreeNode* p)  { mLeftChild=p; if (p) p->SetParent(this);}
	void SetRightChild(BinTreeNode* p) { mRightChild=p;if (p) p->SetParent(this);}
	void SetParent(BinTreeNode* p)	   { mParent=p; }

	void SetValue(const ValueType& v)  { mValue = v; }
	// Note: Deliberately no SetKey, that could easily screw up the tree.
	// If a key shall be changed, delete node from tree and insert a new one instead.

#ifndef NO_REDBLACK
	void SetRed()        { mIsRed = true; }
	void SetBlack()      { mIsRed = false; }
#endif
	//------------------------------
	// Public Queries
	//------------------------------

	// Get methods
	BinTreeNode* GetLeftChild() const  { return mLeftChild; }
	BinTreeNode* GetRightChild() const { return mRightChild; }
	BinTreeNode* GetParent() const     { return mParent; }

	ValueType GetValue() const         { return mValue; }
	KeyType GetKey() const             { return mKey; }

	// Some more or less useful queries
	bool IsRoot() const           { return mParent==0; }
	bool IsLeftChild() const      { return mParent!=0 && mParent->GetLeftChild()==this; }
	bool IsRightChild() const     { return mParent!=0 && mParent->GetRightChild()==this; }
	bool IsLeaf() const           { return mLeftChild==0 && mRightChild==0; }
	unsigned int GetLevel() const { if (IsRoot()) return 1; else return GetParent()->GetLevel() + 1; }

#ifndef NO_REDBLACK
	bool IsRed() const   { return mIsRed; };
	bool IsBlack() const { return !mIsRed; };
#endif

private:
	//------------------------------
	// Disabled Methods
	//------------------------------

	// Default constructor - deliberately not implemented
	BinTreeNode();

	//------------------------------
	// Private Members
	//------------------------------
	BinTreeNode*	mLeftChild;
	BinTreeNode*	mRightChild;

	BinTreeNode*	mParent;

	KeyType			mKey;
	ValueType		mValue;

#ifndef NO_REDBLACK
	bool mIsRed;
#endif

};

//------------------------------------------------------------
// class BinTree. Holder of the tree structure. 
//------------------------------------------------------------
template <class KeyType, class ValueType> 
class BinTree
{
public:
	//------------------------------
	// Public Definitions
	//------------------------------
	typedef BinTreeNode<KeyType,ValueType> Node;

	//------------------------------
	// Public Classes
	//------------------------------

	//--------------------------------------------------------
	// class BinTree::Iterator.
	// Regular low->high (++) and high->low (--) iterator
	//--------------------------------------------------------
	class Iterator
	{
	public:
		//------------------------------
		// Public Construction
		//------------------------------
		// Default Constructor
		Iterator():mRoot(0),mCur(0){}

		// Constructor(Node*)
		Iterator(Node* root):mRoot(root){ Reset();}

		// Copy constructor
		Iterator(const Iterator& src):mRoot(src.mRoot),mCur(src.mCur){}


		//------------------------------
		// Public Commands
		//------------------------------
		// Reset the iterator
		// atLowest : true  - Reset at lowest key value (and then ++ your way through)
		//            false - Reset at highest key value (and then -- your way through)
		void Reset(bool atLowest=true) 
		{ 
			if (atLowest) 
				mCur = Min(mRoot); 
			else 
				mCur = Max(mRoot);
		}

		//------------------------------
		// Public Queries
		//------------------------------

		// Has the iterator reached the end?
		bool atEnd() const { return mCur==0; }
		Node* GetNode() { return mCur;	}

		//------------------------------
		// Public Operators
		//------------------------------

		// Assignment operator
		Iterator& operator=(const Iterator& src) 
		{ 
			mRoot = src.mRoot; 
			mCur = src.mCur; 
			return (*this);
		}

		// Increment operator
		void operator++(int) { Inc(); }

		// Decrement operator
		void operator--(int)
		{
			Dec();
		}

		// Access operators
		Node* operator -> () { return GetNode();	}
		Node& operator*   () 
		{ 
			if (atEnd())
			{
				throw "Iterator at end";			
			}
			return *mCur; 
		}

	private:
		//------------------------------
		// Private Helper Methods
		//------------------------------

		// Min: Returns node with lowest key from n and down.
		//      Ie the node all down to the left
		Node* Min(Node* n)
		{
			while(n && n->GetLeftChild())
				n = n->GetLeftChild();
			return n;
		}
		// Min: Returns node with highest key from n and down.
		//      Ie the node all down to the right
		Node* Max(Node* n)
		{
			while(n && n->GetRightChild())
				n = n->GetRightChild();
			return n;
		}

		//------------------------------
		// Private Commands
		//------------------------------
		// ++
		void Inc()
		{
			// Already at end?
			if (mCur==0)
				return;

			if (mCur->GetRightChild())
			{
				// If current node has a right child, the next higher node is the 
				// node with lowest key beneath the right child.
				mCur =  Min(mCur->GetRightChild());
			}
			else if (mCur->IsLeftChild())
			{
				// No right child? Well if current node is a left child then
				// the next higher node is the parent
				mCur = mCur->GetParent();
			}
			else
			{
				// Current node neither is left child nor has a right child.
				// Ie it is either right child or root
				// The next higher node is the parent of the first non-right
				// child (ie either a left child or the root) up in the
				// hierarchy. Root's parent is 0.
				while(mCur->IsRightChild())
					mCur = mCur->GetParent();
				mCur =  mCur->GetParent();
			}
		}

		// --
		void Dec()
		{
			// Already at end?
			if (mCur==0)
				return;

			if (mCur->GetLeftChild())
			{
				// If current node has a left child, the next lower node is the 
				// node with highest key beneath the left child.
				mCur =  Max(mCur->GetLeftChild());
			}
			else if (mCur->IsRightChild())
			{
				// No left child? Well if current node is a right child then
				// the next lower node is the parent
				mCur =  mCur->GetParent();
			}
			else
			{
				// Current node neither is right child nor has a left child.
				// Ie it is either left child or root
				// The next higher node is the parent of the first non-left
				// child (ie either a right child or the root) up in the
				// hierarchy. Root's parent is 0.

				while(mCur->IsLeftChild())
					mCur = mCur->GetParent();
				mCur =  mCur->GetParent();
			}
		}

		//------------------------------
		// Private Members
		//------------------------------
		Node* mRoot;
		Node* mCur;
	}; // Iterator

	//--------------------------------------------------------
	// class BinTree::ParentFirstIterator. 
	// Traverses the tree from top to bottom. Typical usage is 
	// when storing the tree structure, because when reading it 
	// later (and inserting elements) the tree structure will
	// be the same.
	//--------------------------------------------------------
	class ParentFirstIterator
	{
	public:

		//------------------------------
		// Public Construction
		//------------------------------
		// Default constructor
		ParentFirstIterator():mRoot(0),mCur(0){}

		// Constructor(Node*)
		explicit ParentFirstIterator(Node* root):mRoot(root),mCur(0){ Reset(); }

		//------------------------------
		// Public Commands
		//------------------------------
		void Reset() { mCur = mRoot; };

		//------------------------------
		// Public Queries
		//------------------------------

		// Has the iterator reached the end?
		bool atEnd() const { return mCur==0; }
		Node* GetNode() { return mCur;	}

		//------------------------------
		// Public Operators
		//------------------------------

		// Assignment operator
		ParentFirstIterator& operator=(const ParentFirstIterator& src) 
		{ 
			mRoot = src.mRoot; mCur = src.mCur; return (*this);
		}

		// Increment operator
		void operator++(int) { Inc(); }

		// Access operators
		Node* operator -> () { return GetNode();	}
		Node& operator*   () 
		{ 
			if (atEnd())
				throw "ParentFirstIterator at end";			
			return *GetNode(); 
		}
	private:

		//------------------------------
		// Private Commands
		//------------------------------

		void Inc()
		{
			// Already at end?
			if (mCur==0)
				return;

			// First we try down to the left
			if (mCur->GetLeftChild())
			{
				mCur =  mCur->GetLeftChild();
			}
			else if (mCur->GetRightChild())
			{
				// No left child? The we go down to the right.
				mCur = mCur->GetRightChild();
			}
			else
			{
				// No children? Move up in the hierarcy until
				// we either reach 0 (and are finished) or
				// find a right uncle.
				while (mCur!=0)
				{
					// But if parent is left child and has a right "uncle" the parent
					// has already been processed but the uncle hasn't. Move to 
					// the uncle.
					if (mCur->IsLeftChild() && mCur->GetParent()->GetRightChild())
					{
						mCur = mCur->GetParent()->GetRightChild();
						return;
					}
					mCur = mCur->GetParent();
				}
			}
		}

		//------------------------------
		// Private Members
		//------------------------------
		Node* mRoot;
		Node* mCur;

	}; // ParentFirstIterator

	//--------------------------------------------------------
	// class BinTree::ParentLastIterator. 
	// Traverse the tree from bottom to top.
	// Typical usage is when deleting all elements in the tree
	// because you must delete the children before you delete
	// their parent.
	//--------------------------------------------------------
	class ParentLastIterator
	{
	public:

		//------------------------------
		// Public Construction
		//------------------------------
		// Default constructor
		ParentLastIterator():mRoot(0),mCur(0){}

		// Constructor(Node*)
		explicit ParentLastIterator(Node* root):mRoot(root),mCur(0){ Reset();}

		//------------------------------
		// Public Commands
		//------------------------------
		void Reset() { mCur = Min(mRoot); }

		//------------------------------
		// Public Queries
		//------------------------------

		// Has the iterator reached the end?
		bool atEnd() const { return mCur==0; }
		Node* GetNode() { return mCur;	}

		//------------------------------
		// Public Operators
		//------------------------------

		// Assignment operator
		ParentLastIterator& operator=(const ParentLastIterator& src) { mRoot = src.mRoot; mCur = src.mCur; return (*this);}

		// Increment operator
		void operator++(int) { Inc(); }

		// Access operators
		Node* operator -> () { return GetNode();	}
		Node& operator*   () 
		{ 
			if (atEnd())
				throw "ParentLastIterator at end";			
			return *GetNode(); 
		}
	private:
		//------------------------------
		// Private Helper Methods
		//------------------------------

		// Min: Returns the node as far down to the left as possible.
		Node* Min(Node* n)
		{
			while(n!=0 && (n->GetLeftChild()!=0 || n->GetRightChild()!=0))
			{
				if (n->GetLeftChild())
					n = n->GetLeftChild();
				else
					n = n->GetRightChild();
			}
			return n;
		}

		//------------------------------
		// Private Commands
		//------------------------------
		void Inc()
		{
			// Already at end?
			if (mCur==0)
				return;

			// Note: Starting point is the node as far down to the left as possible.

			// If current node has an uncle to the right, go to the
			// node as far down to the left from the uncle as possible
			// else just go up a level to the parent.
			if (mCur->IsLeftChild() && mCur->GetParent()->GetRightChild())
			{
				mCur = Min(mCur->GetParent()->GetRightChild());
			}
			else
				mCur = mCur->GetParent();
		}

		//------------------------------
		// Private Members
		//------------------------------
		Node* mRoot;
		Node* mCur;
	}; // ParentLastIterator

	// ByLevelIterator. Traverse tree top to bottom, level by level left to right.
	// Typical usage : I don't know. Perhaps if the tree should be displayed               
	// in some fancy way.
	// It is the most memory consuming of all iterators as it will allocate an 
	// array of (Size()+1)/2 Node*s.
	// Impl. desc:
	//   mArray[0] is the current node we're looking at, initially set to mRoot.
	//   When ++:ing the children of mArray[0] (if any) are put last in the 
	//   array and the array is shifted down 1 step
	class ByLevelIterator
	{
	public:
		//------------------------------
		// Public Construction
		//------------------------------

		// Default constructor
		ByLevelIterator():mRoot(0),mArray(0),mSize(0){}

		// Constructor(treeRoot, elementsInTree)
		ByLevelIterator(Node* root, unsigned int size):mRoot(root),mSize(size),mArray(0){ Reset();}

		// Copy constructor
		ByLevelIterator(const ByLevelIterator& src):mRoot(src.mRoot),mSize(src.mSize),mEndPos(src.mEndPos)
		{
			if (src.mArray!=0)
			{
				mArray = new Node*[(mSize+1)/2];
				memcpy(mArray,src.mArray,sizeof(Node*)*(mSize+1)/2);
			}
			else
				mArray = 0;
		}

		// Destructor
		~ByLevelIterator() 
		{ 
			if (mArray!=0)
			{
				delete [] mArray;
				mArray = 0;
			}
		}

		//------------------------------
		// Public Commands
		//------------------------------
		void Reset() 
		{ 
			if (mSize>0)
			{
				// Only allocate the first time Reset is called
				if (mArray==0)
				{
					// mArray must be able to hold the maximum "width" of the tree which
					// at most can be (NumberOfNodesInTree + 1 ) / 2
					mArray = new Node*[(mSize+1)/2];
				}
				// Initialize the array with 1 element, the mRoot.
				mArray[0] = mRoot;
				mEndPos = 1;
			}
			else 
				mEndPos=0;
		} // Reset

		//------------------------------
		// Public Queries
		//------------------------------

		// Has the iterator reached the end?
		bool atEnd() const { return mEndPos == 0; }
		Node* GetNode() { return mArray[0];	}

		//------------------------------
		// Public Operators
		//------------------------------

		// Assignment Operator
		ByLevelIterator& operator=(const ByLevelIterator& src) 
		{ 
			mRoot = src.mRoot; 
			mSize = src.mSize;
			if (src.mArray!=0)
			{
				mArray = new Node*[(mSize+1)/2];
				memcpy(mArray,src.mArray,sizeof(Node*)*(mSize+1)/2);
			}
			else
				mArray = 0;

			return (*this);
		}

		// Increment operator
		void operator++(int) { Inc(); }

		// Access operators
		Node* operator -> () { return GetNode(); }
		Node& operator*   () 
		{ 
			if (atEnd())
				throw "ParentLastIterator at end";			
			return *GetNode(); 
		}
	private:

		//------------------------------
		// Private Commands
		//------------------------------

		void Inc()
		{
			if (mEndPos == 0)
				return;

			// Current node is mArray[0]
			Node* pNode = mArray[0];

			// Move the array down one notch, ie we have a new current node 
			// (the one than just was mArray[1])
			for (unsigned int i=0;i<mEndPos;i++)
			{
				mArray[i] = mArray[i+1];
			}
			mEndPos--;

			Node* pChild=pNode->GetLeftChild();
			if (pChild) // Append the left child of the former current node
			{ 
				mArray[mEndPos] = pChild;
				mEndPos++;
			}

			pChild = pNode->GetRightChild();
			if (pChild) // Append the right child of the former current node
			{ 
				mArray[mEndPos] = pChild;
				mEndPos++;
			}

		}

		//------------------------------
		// Private Members
		//------------------------------
		Node** mArray;
		Node* mRoot;
		unsigned int mSize;
		unsigned int mEndPos;
	}; // ByLevelIterator

	// AccessClass is a temparoary class used with the [] operator.
	// It makes it possible to have different behavior in situations like:
	// myTree["Foo"] = 32; 
	//   If "Foo" already exist, just update its value else insert a new 
	//   element.
	// int i = myTree["Foo"]
	// If "Foo" exists return its value, else throw an exception.
	// 
	class AccessClass
	{
		// Let BinTree be the only one who can instantiate this class.
		friend class BinTree<KeyType, ValueType>;
	public:

		// Assignment operator. Handles the myTree["Foo"] = 32; situation
		operator=(const ValueType& value)
		{
			// Just use the Set method, it handles already exist/not exist situation
			mTree.Set(mKey,value);
		}

		// ValueType operator
		operator ValueType()
		{
			Node* node = mTree.Find(mKey);

			// Not found
			if (node==0)
			{
				throw "Item not found";
			}

			return node->GetValue();
		}


	private:
		//------------------------------
		// Private Construction
		//------------------------------
		AccessClass(BinTree& tree, const KeyType& key):mTree(tree),mKey(key){}
		//------------------------------
		// Disabled Methods
		//------------------------------
		// Default constructor
		AccessClass();

		//------------------------------
		// Private Members
		//------------------------------
		BinTree& mTree;
		const KeyType& mKey;
	}; // AccessClass

	// ==== Enough of that, lets get back to the BinTree class itself ====

	//------------------------------
	// Public Construction
	//------------------------------
	// Constructor.
	BinTree():mRoot(0),mSize(0){}

	// Destructor
	~BinTree(){ DeleteAll(); }

	//------------------------------
	// Public Commands
	//------------------------------

	bool Insert(const KeyType& keyNew, const ValueType& v)
#ifndef NO_REDBLACK
	// RED / BLACK insertion
	{
		// First insert node the "usual" way (no fancy balance logic yet)
		Node* newNode = new Node(keyNew,v);
		if (!Insert(newNode))
		{
			delete newNode;
			return false;
		}

		// Then attend a balancing party
		while  (!newNode->IsRoot() && (newNode->GetParent()->IsRed()))
		{
			if ( newNode->GetParent()->IsLeftChild()) 
			{
				// If newNode is a left child, get its right 'uncle'
				Node* newNodesUncle = newNode->GetParent()->GetParent()->GetRightChild();
				if ( newNodesUncle!=0 && newNodesUncle->IsRed())
				{
					// case 1 - change the colours
					newNode->GetParent()->SetBlack();
					newNodesUncle->SetBlack();
					newNode->GetParent()->GetParent()->SetRed();
					// Move newNode up the tree
					newNode = newNode->GetParent()->GetParent();
				}
				else 
				{
					// newNodesUncle is a black node
					if ( newNode->IsRightChild()) 
					{
					// and newNode is to the right
					// case 2 - move newNode up and rotate
					newNode = newNode->GetParent();
					RotateLeft(newNode);
					}
					// case 3
					newNode->GetParent()->SetBlack();
					newNode->GetParent()->GetParent()->SetRed();
					RotateRight(newNode->GetParent()->GetParent());
				}
			}
			else 
			{
				// If newNode is a right child, get its left 'uncle'
				Node* newNodesUncle = newNode->GetParent()->GetParent()->GetLeftChild();
				if ( newNodesUncle!=0 && newNodesUncle->IsRed())
				{
					// case 1 - change the colours
					newNode->GetParent()->SetBlack();
					newNodesUncle->SetBlack();
					newNode->GetParent()->GetParent()->SetRed();
					// Move newNode up the tree
					newNode = newNode->GetParent()->GetParent();
				}
				else 
				{
					// newNodesUncle is a black node
					if ( newNode->IsLeftChild()) 
					{
						// and newNode is to the left
						// case 2 - move newNode up and rotate
						newNode = newNode->GetParent();
						RotateRight(newNode);
					}
					// case 3
					newNode->GetParent()->SetBlack();
					newNode->GetParent()->GetParent()->SetRed();
					RotateLeft(newNode->GetParent()->GetParent());
				}

			}
		}
		// Color the root black
		mRoot->SetBlack();
		return true;
	}
#else
	// No balance logic insertion
	{
		Node* newNode = new Node(keyNew,v);
		if (!Insert(newNode))
		{
			delete newNode;
			return false;
		}
		return true;
	}
#endif // NO_REDBLACK

	// Set. If the key already exist just replace the value
	// else insert a new element.
	void Set(const KeyType& k, const ValueType& v)
	{
		Node* p = Find(k);
		if (p)
		{
			p->SetValue(v);
		}
		else
			Insert(k,v);
	}

	// Remove a node.Return true if the node could
	// be found (and was removed) in the tree.
	bool Delete(const KeyType& k)
	{
		Node* p = Find(k);
		if (p == 0) return false;

		// Rotate p down to the left until it has no right child, will get there
		// sooner or later.
		while(p->GetRightChild())
		{
			// "Pull up my right child and let it knock me down to the left"
			RotateLeft(p);
		}
		// p now has no right child but might have a left child
		Node* left = p->GetLeftChild(); 

		// Let p's parent point to p's child instead of point to p
		if (p->IsLeftChild())
		{
			p->GetParent()->SetLeftChild(left);
		}
		else if (p->IsRightChild())
		{
			p->GetParent()->SetRightChild(left);
		}
		else
		{
			// p has no parent => p is the root. 
			// Let the left child be the new root.
			SetRoot(left);
		}

		// p is now gone from the tree in the sense that 
		// no one is pointing at it. Let's get rid of it.
		delete p;
			
		mSize--;
		return true;
	}

	// Wipe out the entire tree.
	void DeleteAll()
	{
		ParentLastIterator i(GetParentLastIterator());

		while(!i.atEnd())
		{
			Node* p = i.GetNode();
			i++; // Increment it before it is deleted
			     // else iterator will get quite confused.
			delete p;
		}
		mRoot = 0;
		mSize= 0;
	}

	//------------------------------
	// Public Queries
	//------------------------------

	// Is the tree empty?
	bool IsEmpty() const { return mRoot == 0; }

	// Search for the node.
	// Returns 0 if node couldn't be found.
	Node* Find(const KeyType& keyToFind) const
	{
		Node* pNode = mRoot;

		while(pNode!=0)
		{
			KeyType key(pNode->GetKey());

			if (keyToFind == key)
			{
				// Found it! Return it! Wheee!
				return pNode;
			}			
			else if (keyToFind < key)
			{
				pNode = pNode->GetLeftChild();
			}
			else //keyToFind > key
			{
				pNode = pNode->GetRightChild();
			}
		}

		return 0;
	}
	
	// Get the root element. 0 if tree is empty.
	Node* GetRoot() const { return mRoot; }

	// Number of nodes in the tree.
	unsigned int Size() const { return mSize; }

	//------------------------------
	// Public Iterators
	//------------------------------
	Iterator GetIterator()			 
	{ 
		Iterator it(GetRoot());
		return it; 
	}
	ParentFirstIterator GetParentFirstIterator() 
	{
		ParentFirstIterator it(GetRoot());
		return it; 
	}
	ParentLastIterator GetParentLastIterator()
	{   
		ParentLastIterator it(GetRoot());
		return it;	
	}
	ByLevelIterator GetByLevelIterator()	 
	{ 
		ByLevelIterator it(GetRoot(),Size());
		return it;	
	}
	
	//------------------------------
	// Public Operators
	//------------------------------

	// operator [] for accesss to elements
	AccessClass operator[](const KeyType& k) 
	{
		return AccessClass(*this, k);
	}
private:

	//------------------------------
	// Disabled methods
	//------------------------------
	// Copy constructor and assignment operator deliberately 
	// defined but not implemented. The tree should never be 
	// copied, pass along references to it instead (or use auto_ptr to it).
	explicit BinTree(const BinTree& src); 
	BinTree& operator = (const BinTree& src);


	//------------------------------
	// Private Commands
	//------------------------------
	void SetRoot(Node* newRoot)
	{
		mRoot = newRoot;
		if (mRoot!=0)
			mRoot->SetParent(0);
	}

	// Insert a node into the tree without using any fancy balancing logic.
	// Returns false if that key already exist in the tree.
	bool Insert(Node* newNode)
	{
		bool result=true; // Assume success

		if (mRoot==0)
		{
			SetRoot(newNode);
			mSize = 1;
		}
		else
		{
			Node* pNode = mRoot;
			KeyType keyNew = newNode->GetKey();
			while (pNode)
			{
				KeyType key(pNode->GetKey());

				if (keyNew == key)
				{
					result = false;
					pNode = 0;
				} 
				else if (keyNew < key)
				{
					if (pNode->GetLeftChild()==0)
					{
						pNode->SetLeftChild(newNode);
						pNode = 0;
					}
					else
					{
						pNode = pNode->GetLeftChild();
					}
				} 
				else 
				{
					// keyNew > key
					if (pNode->GetRightChild()==0)
					{
						pNode->SetRightChild(newNode);
						pNode = 0;
					}
					else
					{
						pNode = pNode->GetRightChild();
					}
				}
			}

			if (result)
			{
				mSize++;
			}
		}
		
		return result;
	}

	// Rotate left.
	// Pull up node's right child and let it knock node down to the left
	void RotateLeft(Node* p)
	{		
		Node* right = p->GetRightChild();

		p->SetRightChild(right->GetLeftChild());
		
		if (p->IsLeftChild())
			p->GetParent()->SetLeftChild(right);
		else if (p->IsRightChild())
			p->GetParent()->SetRightChild(right);
		else
		{
			SetRoot(right);
		}
		right->SetLeftChild(p);
	}

	// Rotate right.
	// Pull up node's left child and let it knock node down to the right
	void RotateRight(Node* p)
	{		

		Node* left = p->GetLeftChild();

		p->SetLeftChild(left->GetRightChild());
		
		if (p->IsLeftChild())
			p->GetParent()->SetLeftChild(left);
		else if (p->IsRightChild())
			p->GetParent()->SetRightChild(left);
		else
		{
			SetRoot(left);
		}
		left->SetRightChild(p);
	}

	//------------------------------
	// Private Members
	//------------------------------
	Node* mRoot; // The top node. 0 if empty.	
	unsigned int mSize; // Number of nodes in the tree
};
#endif // _BINTREE_H_

It's only one file.
I hope this is usefull.I hope it clears all the doubts.
Have fun with it now:D