From 393b5cd1dc438872af89d334ef6e5fcc59f27d47 Mon Sep 17 00:00:00 2001 From: David Walter Seikel Date: Sun, 13 Jan 2013 17:24:39 +1000 Subject: Added Irrlicht 1.8, but without all the Windows binaries. --- libraries/irrlicht-1.8/include/irrMap.h | 1127 +++++++++++++++++++++++++++++++ 1 file changed, 1127 insertions(+) create mode 100644 libraries/irrlicht-1.8/include/irrMap.h (limited to 'libraries/irrlicht-1.8/include/irrMap.h') diff --git a/libraries/irrlicht-1.8/include/irrMap.h b/libraries/irrlicht-1.8/include/irrMap.h new file mode 100644 index 0000000..9e9ae73 --- /dev/null +++ b/libraries/irrlicht-1.8/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 map +{ + //! red/black tree for map + template + 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 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; + + 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& 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__ + -- cgit v1.1