Thanks ;-)katoun wrote: I hope this is usefull.I hope it clears all the doubts.
Have fun with it now:D
irr::core::map replacemant of the one from STL
Hello.
I have done some access Updates to the code
I have done some access Updates to the code
Last edited by katoun on Tue Jan 30, 2007 11:11 pm, edited 1 time in total.
Kat'Oun
Here is the code:
And some examples:
It is taken directly from my WIP game engine but as I sayed is quite portable 
Code: Select all
// Copyright 2006-2007 by Kat'Oun
#ifndef _MAP_H_
#define _MAP_H_
#include <Config.h>
#include <core/Types.h>
namespace game
{
namespace core
{
template <class KeyType, class ValueType>
class GAME_TEMPLATE_EXPORT map
{
template <class KeyType, class ValueType>
class /*GAME_DLL_PRIVATE*/ 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; }
ValueType* GetValuePtr() { 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;
typedef ValueType Value;
typedef KeyType Key;
class /*GAME_DLL_EXPORT*/ 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* GetNodePtr()
{
return mCur;
}
Node& GetNode()
{
if (atEnd())
{
throw "Iterator at end";
}
return *mCur;
}
Iterator& operator=(const Iterator& src)
{
mRoot = src.mRoot;
mCur = src.mCur;
return (*this);
}
void operator++(int)
{
Inc();
}
void operator--(int)
{
Dec();
}
ValueType operator -> ()
{
if (atEnd())
{
throw "Iterator at end";
}
return mCur->GetValue();
}
ValueType operator * ()
{
if (atEnd())
{
throw "Iterator at end";
}
return mCur->GetValue();
}
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 /*GAME_DLL_EXPORT*/ 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* GetNodePtr()
{
return mCur;
}
Node& GetNode()
{
if (atEnd())
throw "ParentFirstIterator at end";
return *mCur;
}
ParentFirstIterator& operator=(const ParentFirstIterator& src)
{
mRoot = src.mRoot; mCur = src.mCur; return (*this);
}
void operator++(int)
{
Inc();
}
ValueType operator -> ()
{
if (atEnd())
{
throw "ParentFirstIterator at end";
}
return mCur->GetValue();
}
ValueType operator * ()
{
if (atEnd())
{
throw "ParentFirstIterator at end";
}
return mCur->GetValue();
}
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 /*GAME_DLL_EXPORT*/ 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* GetNodePtr()
{
return mCur;
}
Node& GetNode()
{
if (atEnd())
throw "ParentLastIterator at end";
return *mCur;
}
ParentLastIterator& operator=(const ParentLastIterator& src)
{
mRoot = src.mRoot;
mCur = src.mCur;
return (*this);
}
void operator++(int)
{
Inc();
}
ValueType operator -> ()
{
if (atEnd())
throw "ParentLastIterator at end";
return mCur->GetValue();
}
ValueType operator * ()
{
if (atEnd())
throw "ParentLastIterator at end";
return mCur->GetValue();
}
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 /*GAME_DLL_EXPORT*/ 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.FindNode(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 (!InsertNode(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 = FindNode(k);
if (p)
{
p->SetValue(v);
}
else
Insert(k,v);
}
// Search for the node.
// Returns 0 if node couldn't be found
// else return the found ValueType
Value* Find(const KeyType& keyToFind) const
{
Node* pNode = FindNode(keyToFind);
if(pNode!=0)
return pNode->GetValuePtr();
return 0;
}
//Remove a node from the tree.
//Return the removed ValueType.
Value* Remove(const KeyType& k)
{
Node* pNode = RemoveNode(k);
if(pNode!=0)
return pNode->GetValuePtr();
return 0;
}
// Remove a node.Return true if the node could
// be found (and was removed) in the tree.
bool Delete(const KeyType& k)
{
return DeleteNode(k);
}
// Wipe out the entire tree.
void DeleteAll()
{
ParentLastIterator i(GetParentLastIterator());
while(!i.atEnd())
{
Node* p = i.GetNodePtr();
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;
}
// 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 InsertNode(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;
}
// Search for the node.
// Returns 0 if node couldn't be found.
Node* FindNode(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;
}
//Remove a node from the tree.
//Return the removed node.
Node* RemoveNode(const KeyType& k)
{
Node* p = FindNode(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.
mSize--;
return p;
}
// Remove a node.Return true if the node could
// be found (and was removed) in the tree.
bool DeleteNode(const KeyType& k)
{
Node* p = FindNode(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;
}
// 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_
Code: Select all
using namespace game;
using namespace std;
int main(int argc, char **argv)
{
bool Exit=false;
s32 Key=0;
core::map<u64, float> M;
for(int 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, float>::Value* n=M.Find(Key);
if(n==NULL)
cout<<"Not found"<<endl;
else
cout<<"Found : "<<(*n)<<endl;
}
else if(c=='p')
{
core::map<u64,float>::Iterator it=M.GetIterator();
while(!it.atEnd())
{
core::map<u64,float>::Node* n=it.GetNodePtr();
cout<<(*it)<<endl;
it++;
}
}
else if(c=='r')
{
M.DeleteAll();
for(int i=0;i<10000;i++)
M.Insert(i,(f32)(rand()%4000000000)+rand());
}
}
/*core::string S("Hello");
cout<<S.c_str()<<endl;
while(!Exit)
{
char c;
cin>>c;
if(c=='.')
Exit=true;
else if(c=='a')
{
char s[256];
cin>>s;
S.append(s);
}
else if(c=='c')
{
S="";
}
cout<<S.c_str()<<endl;
}
/*core::string Key;
core::map<core::string, float> Ms;
for(int i=0;i<rand()%100;++i)
{
char c[256];
int j=0;
for(j=0;j<rand()%10-1;j++)
c[j]=(char)('a' + rand()%('z'-'a'-1));
c[j+1]='\0';
core::string st=c;
Ms.Insert(st,(f32)(rand()%40000));
}
while(!Exit)
{
char c;
cin>>c;
if(c=='.')
Exit=true;
else if(c=='s')
{
char s[256];
cin>>s;
Key=s;
core::map<core::string, float>::Value* n=Ms.Find(Key);
if(n==NULL)
cout<<"Not found"<<endl;
else
cout<<"Found : "<<(*n)<<endl;
}
else if(c=='p')
{
core::map<core::string,float>::Iterator it=Ms.GetIterator();
while(!it.atEnd())
{
core::map<core::string,float>::Node* n=it.GetNodePtr();
if(n==NULL)
cout<<"Element NULL"<<endl;
else
cout<<n->GetKey()<<" "<<n->GetValue()<<endl;
it++;
}
}
else if(c=='r')
{
Ms.DeleteAll();
for(int i=0;i<20;i++)
{
char c[256];
int j=0;
for(j=0;j<rand()%10-1;j++)
c[j]=(char)('a' + rand()%('z'-'a'-1));
c[j+1]='\0';
core::string st=c;
Ms.Insert(st,(f32)(rand()%4000000000)+rand());
}
}
else if(c=='d')
{
Ms.DeleteAll();
}
}*/
Kat'Oun