irr::core::map< KeyType, ValueType > Class Template Reference

map template for associative arrays using a red-black tree More...

#include <irrMap.h>

Classes
class	AccessClass
class	ConstIterator
	Const Iterator. More...
class	Iterator
	Normal Iterator. More...
class	ParentFirstIterator
	Parent First Iterator. More...
class	ParentLastIterator
	Parent Last Iterator. More...

Public Types
typedef RBTree< KeyType, ValueType >	Node
typedef KeyType	key_type
typedef ValueType	value_type
typedef u32	size_type

Public Member Functions
	map ()
	~map ()
bool	insert (const KeyType &keyNew, const ValueType &v)
	Inserts a new node into the tree. More...
void	set (const KeyType &k, const ValueType &v)
	Replaces the value if the key already exists, otherwise inserts a new element. More...
Node *	delink (const KeyType &k)
	Removes a node from the tree and returns it. More...
bool	remove (const KeyType &k)
	Removes a node from the tree and deletes it. More...
bool	remove (Node *p)
	Removes a node from the tree and deletes it. More...
void	clear ()
	Clear the entire tree. More...
bool	empty () const
_IRR_DEPRECATED_ bool	isEmpty () const
Node *	find (const KeyType &keyToFind) const
Node *	getRoot () const
u32	size () const
	Returns the number of nodes in the tree. More...
void	swap (map< KeyType, ValueType > &other)
	Swap the content of this map container with the content of another map. More...
Iterator	getIterator () const
	Returns an iterator. More...
ConstIterator	getConstIterator () const
	Returns a Constiterator. More...
ParentFirstIterator	getParentFirstIterator () const
ParentLastIterator	getParentLastIterator () const
AccessClass	operator[] (const KeyType &k)
	operator [] for access to elements More...

Detailed Description

template<class KeyType, class ValueType>
class irr::core::map< KeyType, ValueType >

map template for associative arrays using a red-black tree

Definition at line 18 of file irrMap.h.

Member Typedef Documentation

key_type

template<class KeyType, class ValueType>

typedef KeyType irr::core::map< KeyType, ValueType >::key_type

Definition at line 668 of file irrMap.h.

Node

template<class KeyType, class ValueType>

typedef RBTree<KeyType,ValueType> irr::core::map< KeyType, ValueType >::Node

Definition at line 125 of file irrMap.h.

size_type

template<class KeyType, class ValueType>

typedef u32 irr::core::map< KeyType, ValueType >::size_type

Definition at line 670 of file irrMap.h.

value_type

template<class KeyType, class ValueType>

typedef ValueType irr::core::map< KeyType, ValueType >::value_type

Definition at line 669 of file irrMap.h.

Constructor & Destructor Documentation

map()

template<class KeyType, class ValueType>

irr::core::map< KeyType, ValueType >::map ( )

inline

Definition at line 659 of file irrMap.h.

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

~map()

template<class KeyType, class ValueType>

irr::core::map< KeyType, ValueType >::~map ( )

inline

Definition at line 662 of file irrMap.h.

        {
                clear();
        }

Member Function Documentation

clear()

template<class KeyType, class ValueType>

void irr::core::map< KeyType, ValueType >::clear ( void  )

inline

Clear the entire tree.

Definition at line 861 of file irrMap.h.

        {
                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;
        }

delink()

template<class KeyType, class ValueType>

Node* irr::core::map< KeyType, ValueType >::delink ( const KeyType &  k )

inline

Removes a node from the tree and returns it.

The returned node must be deleted by the user

Parameters

k	the key to remove

Returns

A pointer to the node, or 0 if not found

Definition at line 774 of file irrMap.h.

        {
                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;
        }

empty()

template<class KeyType, class ValueType>

bool irr::core::map< KeyType, ValueType >::empty ( ) const

inline

Is the tree empty?

Returns

Returns true if empty, false if not

Definition at line 878 of file irrMap.h.

        {
                return Root == 0;
        }

find()

template<class KeyType, class ValueType>

Node* irr::core::map< KeyType, ValueType >::find ( const KeyType &  keyToFind ) const

inline

Search for a node with the specified key.

Parameters

keyToFind

The key to find

Returns

Returns 0 if node couldn't be found.

Definition at line 892 of file irrMap.h.

        {
                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;
        }

getConstIterator()

template<class KeyType, class ValueType>

ConstIterator irr::core::map< KeyType, ValueType >::getConstIterator ( ) const

inline

Returns a Constiterator.

Definition at line 948 of file irrMap.h.

        {
                Iterator it(getRoot());
                return it;
        }

getIterator()

template<class KeyType, class ValueType>

Iterator irr::core::map< KeyType, ValueType >::getIterator ( ) const

inline

Returns an iterator.

Definition at line 941 of file irrMap.h.

        {
                Iterator it(getRoot());
                return it;
        }

getParentFirstIterator()

template<class KeyType, class ValueType>

ParentFirstIterator irr::core::map< KeyType, ValueType >::getParentFirstIterator ( ) const

inline

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.

Definition at line 959 of file irrMap.h.

        {
                ParentFirstIterator it(getRoot());
                return it;
        }

getParentLastIterator()

template<class KeyType, class ValueType>

ParentLastIterator irr::core::map< KeyType, ValueType >::getParentLastIterator ( ) const

inline

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.

Definition at line 970 of file irrMap.h.

        {
                ParentLastIterator it(getRoot());
                return it;
        }

getRoot()

template<class KeyType, class ValueType>

Node* irr::core::map< KeyType, ValueType >::getRoot ( ) const

inline

Gets the root element.

Returns

Returns a pointer to the root node, or 0 if the tree is empty.

Definition at line 914 of file irrMap.h.

        {
                return Root;
        }

insert()

template<class KeyType, class ValueType>

bool irr::core::map< KeyType, ValueType >::insert ( const KeyType &  keyNew, const ValueType &  v  )

inline

Inserts a new node into the tree.

Parameters

keyNew	the index for this value
v	the value to insert

Returns

True if successful, false if it fails (already exists)

Definition at line 680 of file irrMap.h.

        {
                // 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 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;
        }

isEmpty()

template<class KeyType, class ValueType>

_IRR_DEPRECATED_ bool irr::core::map< KeyType, ValueType >::isEmpty ( ) const

inline

Deprecated:

Use empty() instead. This method may be removed by Irrlicht 1.9

Definition at line 884 of file irrMap.h.

        {
                return empty();
        }

operator[]()

template<class KeyType, class ValueType>

AccessClass irr::core::map< KeyType, ValueType >::operator[] ( const KeyType &  k )

inline

operator [] for access to elements

for example myMap["key"]

Definition at line 982 of file irrMap.h.

        {
                return AccessClass(*this, k);
        }

remove() [1/2]

template<class KeyType, class ValueType>

bool irr::core::map< KeyType, ValueType >::remove ( const KeyType &  k )

inline

Removes a node from the tree and deletes it.

Returns

True if the node was found and deleted

Definition at line 813 of file irrMap.h.

        {
                Node* p = find(k);
                return remove(p);
        }

remove() [2/2]

template<class KeyType, class ValueType>

bool irr::core::map< KeyType, ValueType >::remove ( Node *  p )

inline

Removes a node from the tree and deletes it.

Returns

True if the node was found and deleted

Definition at line 821 of file irrMap.h.

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

                --Size;
                return true;
        }

set()

template<class KeyType, class ValueType>

void irr::core::map< KeyType, ValueType >::set ( const KeyType &  k, const ValueType &  v  )

inline

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

Parameters

k	The index for this value
v	The new value of

Definition at line 761 of file irrMap.h.

        {
                Node* p = find(k);
                if (p)
                        p->setValue(v);
                else
                        insert(k,v);
        }

size()

template<class KeyType, class ValueType>

u32 irr::core::map< KeyType, ValueType >::size ( ) const

inline

Returns the number of nodes in the tree.

Definition at line 920 of file irrMap.h.

        {
                return Size;
        }

swap()

template<class KeyType, class ValueType>

void irr::core::map< KeyType, ValueType >::swap ( map< KeyType, ValueType > &  other )

inline

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.

Parameters

other

Swap content with this object

Definition at line 930 of file irrMap.h.

        {
                core::swap(Root, other.Root);
                core::swap(Size, other.Size);
        }

---

The documentation for this class was generated from the following file:

• include/irrlicht/irrMap.h