Loading...
Searching...
No Matches
irrMap.h
Go to the documentation of this file.
// 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
{
template <class KeyType, class ValueType>
class 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;
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
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
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
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
//------------------------------
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;
}
void set(const KeyType& k, const ValueType& v)
{
Node* p = find(k);
if (p)
p->setValue(v);
else
insert(k,v);
}
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;
}
bool remove(const KeyType& k)
{
Node* p = find(k);
return remove(p);
}
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;
}
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;
}
bool empty() const
{
_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
return Root == 0;
}
_IRR_DEPRECATED_ bool isEmpty() const
{
return empty();
}
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;
}
Node* getRoot() const
{
return Root;
}
u32 size() const
{
return Size;
}
void swap(map<KeyType, ValueType>& other)
{
core::swap(Root, other.Root);
core::swap(Size, other.Size);
}
//------------------------------
// Public Iterators
//------------------------------
Iterator getIterator() const
{
Iterator it(getRoot());
return it;
}
ConstIterator getConstIterator() const
{
Iterator it(getRoot());
return it;
}
ParentFirstIterator getParentFirstIterator() const
{
ParentFirstIterator it(getRoot());
return it;
}
ParentLastIterator getParentLastIterator() const
{
ParentLastIterator it(getRoot());
return it;
}
//------------------------------
// Public Operators
//------------------------------
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);
void setRoot(Node* newRoot)
{
Root = newRoot;
if (Root != 0)
{
Root->setParent(0);
Root->setBlack();
}
}
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;
}
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);
}
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__
irr::core::map::AccessClass
Definition irrMap.h:636
irr::core::map::AccessClass::operator=
void operator=(const ValueType &value)
Definition irrMap.h:643
irr::core::map::ConstIterator
Const Iterator.
Definition irrMap.h:288
irr::core::map::ConstIterator::operator->
const Node * operator->()
Definition irrMap.h:340
irr::core::map::ConstIterator::operator*
const Node & operator*()
Definition irrMap.h:345
irr::core::map::ConstIterator::getNode
const Node * getNode() const
Definition irrMap.h:318
irr::core::map::ConstIterator::ConstIterator
ConstIterator(const ConstIterator &src)
Definition irrMap.h:301
irr::core::map::ConstIterator::reset
void reset(bool atLowest=true)
Definition irrMap.h:304
irr::core::map::ConstIterator::ConstIterator
ConstIterator(const Node *root)
Definition irrMap.h:295
irr::core::map::ConstIterator::operator--
void operator--(int)
Definition irrMap.h:335
irr::core::map::ConstIterator::Iterator
friend class Iterator
Definition irrMap.h:289
irr::core::map::ConstIterator::operator++
void operator++(int)
Definition irrMap.h:330
irr::core::map::ConstIterator::atEnd
bool atEnd() const
Definition irrMap.h:312
irr::core::map::ConstIterator::ConstIterator
ConstIterator(const Iterator &src)
Definition irrMap.h:302
irr::core::map::ConstIterator::operator=
ConstIterator & operator=(const ConstIterator &src)
Definition irrMap.h:323
irr::core::map::ConstIterator::ConstIterator
ConstIterator()
Definition irrMap.h:292
irr::core::map::Iterator
Normal Iterator.
Definition irrMap.h:140
irr::core::map::Iterator::ConstIterator
friend class ConstIterator
Definition irrMap.h:141
irr::core::map::Iterator::Iterator
Iterator(Node *root)
Definition irrMap.h:147
irr::core::map::Iterator::operator--
void operator--(int)
Definition irrMap.h:186
irr::core::map::Iterator::Iterator
Iterator(const Iterator &src)
Definition irrMap.h:153
irr::core::map::Iterator::Iterator
Iterator()
Definition irrMap.h:144
irr::core::map::Iterator::operator=
Iterator & operator=(const Iterator &src)
Definition irrMap.h:174
irr::core::map::Iterator::operator*
Node & operator*()
Definition irrMap.h:196
irr::core::map::Iterator::operator++
void operator++(int)
Definition irrMap.h:181
irr::core::map::Iterator::atEnd
bool atEnd() const
Definition irrMap.h:163
irr::core::map::Iterator::reset
void reset(bool atLowest=true)
Definition irrMap.h:155
irr::core::map::Iterator::getNode
Node * getNode() const
Definition irrMap.h:169
irr::core::map::Iterator::operator->
Node * operator->()
Definition irrMap.h:191
irr::core::map::ParentFirstIterator
Parent First Iterator.
Definition irrMap.h:442
irr::core::map::ParentFirstIterator::ParentFirstIterator
ParentFirstIterator()
Definition irrMap.h:445
irr::core::map::ParentFirstIterator::ParentFirstIterator
ParentFirstIterator(Node *root)
Definition irrMap.h:447
irr::core::map::ParentFirstIterator::operator++
void operator++(int)
Definition irrMap.h:475
irr::core::map::ParentFirstIterator::operator->
Node * operator->()
Definition irrMap.h:480
irr::core::map::ParentFirstIterator::operator=
ParentFirstIterator & operator=(const ParentFirstIterator &src)
Definition irrMap.h:468
irr::core::map::ParentFirstIterator::getNode
Node * getNode()
Definition irrMap.h:463
irr::core::map::ParentFirstIterator::operator*
Node & operator*()
Definition irrMap.h:485
irr::core::map::ParentFirstIterator::atEnd
bool atEnd() const
Definition irrMap.h:457
irr::core::map::ParentFirstIterator::reset
void reset()
Definition irrMap.h:452
irr::core::map::ParentLastIterator
Parent Last Iterator.
Definition irrMap.h:542
irr::core::map::ParentLastIterator::getNode
Node * getNode()
Definition irrMap.h:563
irr::core::map::ParentLastIterator::operator=
ParentLastIterator & operator=(const ParentLastIterator &src)
Definition irrMap.h:568
irr::core::map::ParentLastIterator::atEnd
bool atEnd() const
Definition irrMap.h:557
irr::core::map::ParentLastIterator::ParentLastIterator
ParentLastIterator(Node *root)
Definition irrMap.h:547
irr::core::map::ParentLastIterator::operator++
void operator++(int)
Definition irrMap.h:575
irr::core::map::ParentLastIterator::ParentLastIterator
ParentLastIterator()
Definition irrMap.h:545
irr::core::map::ParentLastIterator::operator*
Node & operator*()
Definition irrMap.h:585
irr::core::map::ParentLastIterator::reset
void reset()
Definition irrMap.h:552
irr::core::map::ParentLastIterator::operator->
Node * operator->()
Definition irrMap.h:580
irr::core::map
map template for associative arrays using a red-black tree
Definition irrMap.h:19
irr::core::map::clear
void clear()
Clear the entire tree.
Definition irrMap.h:872
irr::core::map::empty
bool empty() const
Definition irrMap.h:889
irr::core::map::isEmpty
_IRR_DEPRECATED_ bool isEmpty() const
Definition irrMap.h:896
irr::core::map::getParentLastIterator
ParentLastIterator getParentLastIterator() const
Definition irrMap.h:982
irr::core::map::operator[]
AccessClass operator[](const KeyType &k)
operator [] for access to elements
Definition irrMap.h:994
irr::core::map::getParentFirstIterator
ParentFirstIterator getParentFirstIterator() const
Definition irrMap.h:971
irr::core::map::swap
void swap(map< KeyType, ValueType > &other)
Swap the content of this map container with the content of another map.
Definition irrMap.h:942
irr::core::map::getRoot
Node * getRoot() const
Definition irrMap.h:926
irr::core::map::remove
bool remove(const KeyType &k)
Removes a node from the tree and deletes it.
Definition irrMap.h:823
irr::core::map::remove
bool remove(Node *p)
Removes a node from the tree and deletes it.
Definition irrMap.h:831
irr::core::map::find
Node * find(const KeyType &keyToFind) const
Definition irrMap.h:904
irr::core::map::size
u32 size() const
Returns the number of nodes in the tree.
Definition irrMap.h:932
irr::core::map::Node
RBTree< KeyType, ValueType > Node
Definition irrMap.h:134
irr::core::map::~map
~map()
Definition irrMap.h:676
irr::core::map::getIterator
Iterator getIterator() const
Returns an iterator.
Definition irrMap.h:953
irr::core::map::getConstIterator
ConstIterator getConstIterator() const
Returns a Constiterator.
Definition irrMap.h:960
irr::core::map::set
void set(const KeyType &k, const ValueType &v)
Replaces the value if the key already exists, otherwise inserts a new element.
Definition irrMap.h:771
irr::core::map::delink
Node * delink(const KeyType &k)
Removes a node from the tree and returns it.
Definition irrMap.h:784
irr::core::map::map
map()
Definition irrMap.h:673
irr::core::map::insert
bool insert(const KeyType &keyNew, const ValueType &v)
Inserts a new node into the tree.
Definition irrMap.h:689
irrMath.h
irrTypes.h
_IRR_DEBUG_BREAK_IF
#define _IRR_DEBUG_BREAK_IF(_CONDITION_)
define a break macro for debugging.
Definition irrTypes.h:178
_IRR_DEPRECATED_
#define _IRR_DEPRECATED_
Defines a deprecated macro which generates a warning at compile time.
Definition irrTypes.h:195
_IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX
#define _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX
Defines a small statement to work around a microsoft compiler bug.
Definition irrTypes.h:207
irr::core
Basic classes such as vectors, planes, arrays, lists, and so on can be found in this namespace.
Definition aabbox3d.h:15
irr::core::swap
void swap(T1 &a, T2 &b)
swaps the content of the passed parameters
Definition irrMath.h:177
irr
Everything in the Irrlicht Engine can be found in this namespace.
Definition aabbox3d.h:13
irr::u32
unsigned int u32
32 bit unsigned variable.
Definition irrTypes.h:58
- Irrlicht Engine Documentation © 2003-2012 by Nikolaus Gebhardt. Generated on for Irrlicht 3D Engine by Doxygen 1.15.0