Inital commitHEADmaster

1 files changed, 1127 insertions, 0 deletions

diff --git a/include/irrMap.h b/include/irrMap.h
new file mode 100644
index 0000000..9e9ae73
--- /dev/null
+++ b/include/irrMap.h
@@ -0,0 +1,1127 @@
+// Copyright (C) 2006-2012 by Kat'Oun

+// This file is part of the "Irrlicht Engine".

+// For conditions of distribution and use, see copyright notice in irrlicht.h

+

+#ifndef __IRR_MAP_H_INCLUDED__

+#define __IRR_MAP_H_INCLUDED__

+

+#include "irrTypes.h"

+#include "irrMath.h"

+

+namespace irr

+{

+namespace core

+{

+

+//! map template for associative arrays using a red-black tree

+template <class KeyType, class ValueType>

+class map

+{

+	//! red/black tree for map

+	template <class KeyTypeRB, class ValueTypeRB>

+	class RBTree

+	{

+	public:

+

+		RBTree(const KeyTypeRB& k, const ValueTypeRB& v)

+			: LeftChild(0), RightChild(0), Parent(0), Key(k),

+				Value(v), IsRed(true) {}

+

+		void setLeftChild(RBTree* p)

+		{

+			LeftChild=p;

+			if (p)

+				p->setParent(this);

+		}

+

+		void setRightChild(RBTree* p)

+		{

+			RightChild=p;

+			if (p)

+				p->setParent(this);

+		}

+

+		void setParent(RBTree* p)		{ Parent=p; }

+

+		void setValue(const ValueTypeRB& v)	{ Value = v; }

+

+		void setRed()			{ IsRed = true; }

+		void setBlack()			{ IsRed = false; }

+

+		RBTree* getLeftChild() const	{ return LeftChild; }

+		RBTree* getRightChild() const	{ return RightChild; }

+		RBTree* getParent() const		{ return Parent; }

+

+		const ValueTypeRB& getValue() const

+		{

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			return Value;

+		}

+

+		ValueTypeRB& getValue()

+		{

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			return Value;

+		}

+

+		const KeyTypeRB& getKey() const

+		{

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			return Key;

+		}

+

+		bool isRoot() const

+		{

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			return Parent==0;

+		}

+

+		bool isLeftChild() const

+		{

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			return (Parent != 0) && (Parent->getLeftChild()==this);

+		}

+

+		bool isRightChild() const

+		{

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			return (Parent!=0) && (Parent->getRightChild()==this);

+		}

+

+		bool isLeaf() const

+		{

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			return (LeftChild==0) && (RightChild==0);

+		}

+

+		unsigned int getLevel() const

+		{

+			if (isRoot())

+				return 1;

+			else

+				return getParent()->getLevel() + 1;

+		}

+

+

+		bool isRed() const

+		{

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			return IsRed;

+		}

+

+		bool isBlack() const

+		{

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			return !IsRed;

+		}

+

+	private:

+		RBTree();

+

+		RBTree*		LeftChild;

+		RBTree*		RightChild;

+

+		RBTree*		Parent;

+

+		KeyTypeRB	Key;

+		ValueTypeRB	Value;

+

+		bool IsRed;

+	}; // RBTree

+

+	public:

+

+	typedef RBTree<KeyType,ValueType> Node;

+	// We need the forwad declaration for the friend declaration

+	class ConstIterator;

+

+	//! Normal Iterator

+	class Iterator

+	{

+		friend class ConstIterator;

+	public:

+

+		Iterator() : Root(0), Cur(0) {}

+

+		// Constructor(Node*)

+		Iterator(Node* root) : Root(root)

+		{

+			reset();

+		}

+

+		// Copy constructor

+		Iterator(const Iterator& src) : Root(src.Root), Cur(src.Cur) {}

+

+		void reset(bool atLowest=true)

+		{

+			if (atLowest)

+				Cur = getMin(Root);

+			else

+				Cur = getMax(Root);

+		}

+

+		bool atEnd() const

+		{

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			return Cur==0;

+		}

+

+		Node* getNode() const

+		{

+			return Cur;

+		}

+

+		Iterator& operator=(const Iterator& src)

+		{

+			Root = src.Root;

+			Cur = src.Cur;

+			return (*this);

+		}

+

+		void operator++(int)

+		{

+			inc();

+		}

+

+		void operator--(int)

+		{

+			dec();

+		}

+

+		Node* operator->()

+		{

+			return getNode();

+		}

+

+		Node& operator*()

+		{

+			_IRR_DEBUG_BREAK_IF(atEnd()) // access violation

+

+			return *Cur;

+		}

+

+	private:

+

+		Node* getMin(Node* n) const

+		{

+			while(n && n->getLeftChild())

+				n = n->getLeftChild();

+			return n;

+		}

+

+		Node* getMax(Node* n) const

+		{

+			while(n && n->getRightChild())

+				n = n->getRightChild();

+			return n;

+		}

+

+		void inc()

+		{

+			// Already at end?

+			if (Cur==0)

+				return;

+

+			if (Cur->getRightChild())

+			{

+				// If current node has a right child, the next higher node is the

+				// node with lowest key beneath the right child.

+				Cur = getMin(Cur->getRightChild());

+			}

+			else if (Cur->isLeftChild())

+			{

+				// No right child? Well if current node is a left child then

+				// the next higher node is the parent

+				Cur = Cur->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(Cur->isRightChild())

+					Cur = Cur->getParent();

+				Cur = Cur->getParent();

+			}

+		}

+

+		void dec()

+		{

+			// Already at end?

+			if (Cur==0)

+				return;

+

+			if (Cur->getLeftChild())

+			{

+				// If current node has a left child, the next lower node is the

+				// node with highest key beneath the left child.

+				Cur = getMax(Cur->getLeftChild());

+			}

+			else if (Cur->isRightChild())

+			{

+				// No left child? Well if current node is a right child then

+				// the next lower node is the parent

+				Cur = Cur->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(Cur->isLeftChild())

+					Cur = Cur->getParent();

+				Cur = Cur->getParent();

+			}

+		}

+

+		Node* Root;

+		Node* Cur;

+	}; // Iterator

+

+	//! Const Iterator

+	class ConstIterator

+	{

+		friend class Iterator;

+	public:

+

+		ConstIterator() : Root(0), Cur(0) {}

+

+		// Constructor(Node*)

+		ConstIterator(const Node* root) : Root(root)

+		{

+			reset();

+		}

+

+		// Copy constructor

+		ConstIterator(const ConstIterator& src) : Root(src.Root), Cur(src.Cur) {}

+		ConstIterator(const Iterator& src) : Root(src.Root), Cur(src.Cur) {}

+

+		void reset(bool atLowest=true)

+		{

+			if (atLowest)

+				Cur = getMin(Root);

+			else

+				Cur = getMax(Root);

+		}

+

+		bool atEnd() const

+		{

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			return Cur==0;

+		}

+

+		const Node* getNode() const

+		{

+			return Cur;

+		}

+

+		ConstIterator& operator=(const ConstIterator& src)

+		{

+			Root = src.Root;

+			Cur = src.Cur;

+			return (*this);

+		}

+

+		void operator++(int)

+		{

+			inc();

+		}

+

+		void operator--(int)

+		{

+			dec();

+		}

+

+		const Node* operator->()

+		{

+			return getNode();

+		}

+

+		const Node& operator*()

+		{

+			_IRR_DEBUG_BREAK_IF(atEnd()) // access violation

+

+			return *Cur;

+		}

+

+	private:

+

+		const Node* getMin(const Node* n) const

+		{

+			while(n && n->getLeftChild())

+				n = n->getLeftChild();

+			return n;

+		}

+

+		const Node* getMax(const Node* n) const

+		{

+			while(n && n->getRightChild())

+				n = n->getRightChild();

+			return n;

+		}

+

+		void inc()

+		{

+			// Already at end?

+			if (Cur==0)

+				return;

+

+			if (Cur->getRightChild())

+			{

+				// If current node has a right child, the next higher node is the

+				// node with lowest key beneath the right child.

+				Cur = getMin(Cur->getRightChild());

+			}

+			else if (Cur->isLeftChild())

+			{

+				// No right child? Well if current node is a left child then

+				// the next higher node is the parent

+				Cur = Cur->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(Cur->isRightChild())

+					Cur = Cur->getParent();

+				Cur = Cur->getParent();

+			}

+		}

+

+		void dec()

+		{

+			// Already at end?

+			if (Cur==0)

+				return;

+

+			if (Cur->getLeftChild())

+			{

+				// If current node has a left child, the next lower node is the

+				// node with highest key beneath the left child.

+				Cur = getMax(Cur->getLeftChild());

+			}

+			else if (Cur->isRightChild())

+			{

+				// No left child? Well if current node is a right child then

+				// the next lower node is the parent

+				Cur = Cur->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(Cur->isLeftChild())

+					Cur = Cur->getParent();

+				Cur = Cur->getParent();

+			}

+		}

+

+		const Node* Root;

+		const Node* Cur;

+	}; // ConstIterator

+

+

+	//! Parent First Iterator.

+	/** 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() : Root(0), Cur(0)	{}

+

+	explicit ParentFirstIterator(Node* root) : Root(root), Cur(0)

+	{

+		reset();

+	}

+

+	void reset()

+	{

+		Cur = Root;

+	}

+

+	bool atEnd() const

+	{

+		_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+		return Cur==0;

+	}

+

+	Node* getNode()

+	{

+		return Cur;

+	}

+

+	ParentFirstIterator& operator=(const ParentFirstIterator& src)

+	{

+		Root = src.Root;

+		Cur = src.Cur;

+		return (*this);

+	}

+

+	void operator++(int)

+	{

+		inc();

+	}

+

+	Node* operator -> ()

+	{

+		return getNode();

+	}

+

+	Node& operator* ()

+	{

+		_IRR_DEBUG_BREAK_IF(atEnd()) // access violation

+

+		return *getNode();

+	}

+

+	private:

+

+	void inc()

+	{

+		// Already at end?

+		if (Cur==0)

+			return;

+

+		// First we try down to the left

+		if (Cur->getLeftChild())

+		{

+			Cur = Cur->getLeftChild();

+		}

+		else if (Cur->getRightChild())

+		{

+			// No left child? The we go down to the right.

+			Cur = Cur->getRightChild();

+		}

+		else

+		{

+			// No children? Move up in the hierarcy until

+			// we either reach 0 (and are finished) or

+			// find a right uncle.

+			while (Cur!=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 (Cur->isLeftChild() && Cur->getParent()->getRightChild())

+				{

+					Cur = Cur->getParent()->getRightChild();

+					return;

+				}

+				Cur = Cur->getParent();

+			}

+		}

+	}

+

+	Node* Root;

+	Node* Cur;

+

+	}; // ParentFirstIterator

+

+

+	//! Parent Last Iterator

+	/** 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() : Root(0), Cur(0) {}

+

+		explicit ParentLastIterator(Node* root) : Root(root), Cur(0)

+		{

+			reset();

+		}

+

+		void reset()

+		{

+			Cur = getMin(Root);

+		}

+

+		bool atEnd() const

+		{

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			return Cur==0;

+		}

+

+		Node* getNode()

+		{

+			return Cur;

+		}

+

+		ParentLastIterator& operator=(const ParentLastIterator& src)

+		{

+			Root = src.Root;

+			Cur = src.Cur;

+			return (*this);

+		}

+

+		void operator++(int)

+		{

+			inc();

+		}

+

+		Node* operator -> ()

+		{

+			return getNode();

+		}

+

+		Node& operator* ()

+		{

+			_IRR_DEBUG_BREAK_IF(atEnd()) // access violation

+

+			return *getNode();

+		}

+	private:

+

+		Node* getMin(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 (Cur==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 (Cur->isLeftChild() && Cur->getParent()->getRightChild())

+			{

+				Cur = getMin(Cur->getParent()->getRightChild());

+			}

+			else

+				Cur = Cur->getParent();

+		}

+

+		Node* Root;

+		Node* Cur;

+	}; // ParentLastIterator

+

+

+	// AccessClass is a temporary class used with the [] operator.

+	// It makes it possible to have different behavior in situations like:

+	// myTree["Foo"] = 32;

+	// If "Foo" already exists update its value else insert a new element.

+	// int i = myTree["Foo"]

+	// If "Foo" exists return its value.

+	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

+			Tree.set(Key,value);

+		}

+

+		// ValueType operator

+		operator ValueType()

+		{

+			Node* node = Tree.find(Key);

+

+			// Not found

+			_IRR_DEBUG_BREAK_IF(node==0) // access violation

+

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			return node->getValue();

+		}

+

+	private:

+

+		AccessClass(map& tree, const KeyType& key) : Tree(tree), Key(key) {}

+

+		AccessClass();

+

+		map& Tree;

+		const KeyType& Key;

+	}; // AccessClass

+

+

+	// Constructor.

+	map() : Root(0), Size(0) {}

+

+	// Destructor

+	~map()

+	{

+		clear();

+	}

+

+	//------------------------------

+	// Public Commands

+	//------------------------------

+

+	//! Inserts a new node into the tree

+	/** \param keyNew: the index for this value

+	\param v: the value to insert

+	\return True if successful, false if it fails (already exists) */

+	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;

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			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 colors

+					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 colors

+					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

+		Root->setBlack();

+		return true;

+	}

+

+	//! Replaces the value if the key already exists, otherwise inserts a new element.

+	/** \param k The index for this value

+	\param v The new value of */

+	void set(const KeyType& k, const ValueType& v)

+	{

+		Node* p = find(k);

+		if (p)

+			p->setValue(v);

+		else

+			insert(k,v);

+	}

+

+	//! Removes a node from the tree and returns it.

+	/** The returned node must be deleted by the user

+	\param k the key to remove

+	\return A pointer to the node, or 0 if not found */

+	Node* delink(const KeyType& k)

+	{

+		Node* p = find(k);

+		if (p == 0)

+			return 0;

+

+		// 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.

+

+		--Size;

+		return p;

+	}

+

+	//! Removes a node from the tree and deletes it.

+	/** \return True if the node was found and deleted */

+	bool remove(const KeyType& k)

+	{

+		Node* p = find(k);

+		return remove(p);

+	}

+

+	//! Removes a node from the tree and deletes it.

+	/** \return True if the node was found and deleted */

+	bool remove(Node* p)

+	{

+		if (p == 0)

+		{

+			_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+			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;

+

+		--Size;

+		return true;

+	}

+

+	//! Clear the entire tree

+	void clear()

+	{

+		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;

+		}

+		Root = 0;

+		Size= 0;

+	}

+

+	//! Is the tree empty?

+	//! \return Returns true if empty, false if not

+	bool empty() const

+	{

+		_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+		return Root == 0;

+	}

+

+	//! \deprecated Use empty() instead. This method may be removed by Irrlicht 1.9

+	_IRR_DEPRECATED_ bool isEmpty() const

+	{

+		return empty();

+	}

+

+	//! Search for a node with the specified key.

+	//! \param keyToFind: The key to find

+	//! \return Returns 0 if node couldn't be found.

+	Node* find(const KeyType& keyToFind) const

+	{

+		Node* pNode = Root;

+

+		while(pNode!=0)

+		{

+			const KeyType& key=pNode->getKey();

+

+			if (keyToFind == key)

+				return pNode;

+			else if (keyToFind < key)

+				pNode = pNode->getLeftChild();

+			else //keyToFind > key

+				pNode = pNode->getRightChild();

+		}

+

+		return 0;

+	}

+

+	//! Gets the root element.

+	//! \return Returns a pointer to the root node, or

+	//! 0 if the tree is empty.

+	Node* getRoot() const

+	{

+		return Root;

+	}

+

+	//! Returns the number of nodes in the tree.

+	u32 size() const

+	{

+		return Size;

+	}

+

+	//! Swap the content of this map container with the content of another map

+	/** Afterwards this object will contain the content of the other object and the other

+	object will contain the content of this object. Iterators will afterwards be valid for

+	the swapped object.

+	\param other Swap content with this object	*/

+	void swap(map<KeyType, ValueType>& other)

+	{

+		core::swap(Root, other.Root);

+		core::swap(Size, other.Size);

+	}

+

+	//------------------------------

+	// Public Iterators

+	//------------------------------

+

+	//! Returns an iterator

+	Iterator getIterator() const

+	{

+		Iterator it(getRoot());

+		return it;

+	}

+

+	//! Returns a Constiterator

+	ConstIterator getConstIterator() const

+	{

+		Iterator it(getRoot());

+		return it;

+	}

+

+	//! Returns a 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.

+	ParentFirstIterator getParentFirstIterator() const

+	{

+		ParentFirstIterator it(getRoot());

+		return it;

+	}

+

+	//! Returns a ParentLastIterator to 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.

+	ParentLastIterator getParentLastIterator() const

+	{

+		ParentLastIterator it(getRoot());

+		return it;

+	}

+

+	//------------------------------

+	// Public Operators

+	//------------------------------

+

+	//! operator [] for access to elements

+	/** for example myMap["key"] */

+	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.

+	explicit map(const map& src);

+	map& operator = (const map& src);

+

+	//! Set node as new root.

+	/** The node will be set to black, otherwise core dumps may arise

+	(patch provided by rogerborg).

+	\param newRoot Node which will be the new root

+	*/

+	void setRoot(Node* newRoot)

+	{

+		Root = newRoot;

+		if (Root != 0)

+		{

+			Root->setParent(0);

+			Root->setBlack();

+		}

+	}

+

+	//! Insert a node into the tree without using any fancy balancing logic.

+	/** \return false if that key already exist in the tree. */

+	bool insert(Node* newNode)

+	{

+		bool result=true; // Assume success

+

+		if (Root==0)

+		{

+			setRoot(newNode);

+			Size = 1;

+		}

+		else

+		{

+			Node* pNode = Root;

+			const KeyType& keyNew = newNode->getKey();

+			while (pNode)

+			{

+				const 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)

+				++Size;

+		}

+

+		_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;

+		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* Root; // The top node. 0 if empty.

+	u32 Size; // Number of nodes in the tree

+};

+

+} // end namespace core

+} // end namespace irr

+

+#endif // __IRR_MAP_H_INCLUDED__

+