I like the idea of Irrlicht having it's oun std classes they seem to bee fast.
Well there is one thing Irrlicht misses a std::map and I finaly found some docs and some sourses and made a RB tree with wich std::maps are made.
TODO:
1. the tree does not have a remove function implemented(I don't know how yet)
2. make a class core::map wich hase a RB treee inside to be able to add, remove and search items.
Good luck and here is the code :
RedBlackTree.h
Code: Select all
#ifndef _RED_BLACK_TREE_H_
#define _RED_BLACK_TREE_H_
#include <iostream>
using namespace std;
// Red-black tree class
//
// CONSTRUCTION: with negative infinity object also
// used to signal failed finds
//
// ******************PUBLIC OPERATIONS*********************
// void insert(key, item) --> Insert x
// void remove(key) --> Remove x (unimplemented)
// Item find(key) --> Return item that matches x
// Item findMin( ) --> Return smallest item
// Item findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order
// Node and forward declaration because g++ does
// not understand nested classes.
template <class Key,class Item>
class RedBlackTree;
template <class Key,class Item>
class RedBlackNode
{
Key key;
Item item;
RedBlackNode *left;
RedBlackNode *right;
int color;
// c = 1 should be c = RedBlackTree<Comparable>::BLACK
// But Visual 5.0 does not comprehend it.
RedBlackNode(const Key &theKey=Key(),const Item &theItem=Item(),
RedBlackNode *lt=NULL,RedBlackNode *rt=NULL,
int c=1)
: key(theKey),item(theItem),left(lt),right(rt),color(c){}
friend class RedBlackTree<Key,Item>;
};
template <class Key,class Item>
class RedBlackTree
{
public:
explicit RedBlackTree(Item &negInf);
RedBlackTree(RedBlackTree &rhs);
~RedBlackTree();
Item & findMin();
Item & findMax();
Item & find(Key &key);
bool isEmpty();
void printTree();
void makeEmpty();
void insert(Key &key,Item &item);
void remove(Key &key);
enum {RED, BLACK};
RedBlackTree &operator=(RedBlackTree &rhs);
private:
RedBlackNode<Key,Item> *header; // The tree header (contains negInf)
Item ITEM_NOT_FOUND;
RedBlackNode<Key,Item> *nullNode;
// Used in insert routine and its helpers (logically static)
RedBlackNode<Key,Item> *current;
RedBlackNode<Key,Item> *parent;
RedBlackNode<Key,Item> *grand;
RedBlackNode<Key,Item> *great;
// Usual recursive stuff
void reclaimMemory(RedBlackNode<Key,Item> *t);
void printTree( RedBlackNode<Key,Item> *t);
RedBlackNode<Key,Item> *find(RedBlackNode<Key,Item> *t,Key &key);
RedBlackNode<Key,Item> *clone( RedBlackNode<Key,Item> *t);
// Red-black tree manipulations
void handleReorient(Key &key);
RedBlackNode<Key,Item> *rotate(Key & ey,
RedBlackNode<Key,Item> *parent);
void rotateWithLeftChild(RedBlackNode<Key,Item> * &k2);
void rotateWithRightChild(RedBlackNode<Key,Item> * &k1);
};
///////////////////////////
///////////////////////////
/**
* Construct the tree.
* negInf is a value less than or equal to all others.
* It is also used as ITEM_NOT_FOUND.
*/
template <class Key,class Item>
RedBlackTree<Key,Item>::RedBlackTree(Item &negInf)
:ITEM_NOT_FOUND(negInf)
{
nullNode = new RedBlackNode<Key,Item>;
nullNode->left = nullNode->right = nullNode;
header = new RedBlackNode<Key,Item>(Key(),negInf);
header->left = header->right = nullNode;
}
/**
* Copy constructor.
*/
template <class Key,class Item>
RedBlackTree<Key,Item>::RedBlackTree(RedBlackTree<Key,Item> &rhs)
: ITEM_NOT_FOUND(rhs.ITEM_NOT_FOUND)
{
nullNode = new RedBlackNode<Key,Item>;
nullNode->left = nullNode->right = nullNode;
header = new RedBlackNode<Key,Item>(Key(),ITEM_NOT_FOUND );
header->left = header->right = nullNode;
*this = rhs;
}
/**
* Destroy the tree.
*/
template <class Key,class Item>
RedBlackTree<Key,Item>::~RedBlackTree()
{
makeEmpty( );
delete nullNode;
delete header;
}
/**
* Insert item wiht key into the tree. Does nothing if key already present.
*/
template <class Key,class Item>
void RedBlackTree<Key,Item>::insert(Key &key,Item &item)
{
current = parent = grand = header;
nullNode->key=key;
nullNode->item=item;
while(current->key != key)
{
great = grand; grand = parent; parent = current;
current = key<current->key ? current->left : current->right;
// Check if two red children; fix if so
if( current->left->color == RED && current->right->color == RED )
handleReorient(key);
}
// Insertion fails if already present
if( current != nullNode )
return;
current = new RedBlackNode<Key,Item>(key,item,nullNode,nullNode);
// Attach to parent
if(key < parent->key)
parent->left = current;
else
parent->right = current;
handleReorient(key);
}
/**
* Remove item x from the tree.
* Not implemented in this version.
*/
template <class Key,class Item>
void RedBlackTree<Key,Item>::remove(Key &key)
{
cout << "Sorry, remove unimplemented; " <<key<<
" still present" << endl;
}
/**
* Find the smallest item the tree.
* Return the smallest item or ITEM_NOT_FOUND if empty.
*/
template <class Key,class Item>
Item & RedBlackTree<Key,Item>::findMin()
{
if(isEmpty())
return ITEM_NOT_FOUND;
RedBlackNode<Key,Item> *itr = header->right;
while(itr->left != nullNode)
itr = itr->left;
return itr->item;
}
/**
* Find the largest item in the tree.
* Return the largest item or ITEM_NOT_FOUND if empty.
*/
template <class Key,class Item>
Item & RedBlackTree<Key,Item>::findMax()
{
if(isEmpty())
return ITEM_NOT_FOUND;
RedBlackNode<Key,Item> *itr = header->right;
while(itr->right != nullNode)
itr = itr->right;
return itr->item;
}
/**
* Find item x in the tree.
* Return the matching item or ITEM_NOT_FOUND if not found.
*/
template <class Key,class Item>
Item & RedBlackTree<Key,Item>::find(Key &key)
{
RedBlackNode<Key,Item> *curr = find(header,key);
if(curr!= nullNode)
return curr->item;
else
return ITEM_NOT_FOUND;
}
/**
* Make the tree logically empty.
*/
template <class Key,class Item>
void RedBlackTree<Key,Item>::makeEmpty()
{
reclaimMemory(header->right);
header->right = nullNode;
}
/**
* Test if the tree is logically empty.
* Return true if empty, false otherwise.
*/
template <class Key,class Item>
bool RedBlackTree<Key,Item>::isEmpty()
{
return header->right == nullNode;
}
/**
* Print the tree contents in sorted order.
*/
template <class Key,class Item>
void RedBlackTree<Key,Item>::printTree()
{
if(header->right == nullNode)
cout<<"Empty tree"<<endl;
else
printTree(header->right);
}
/**
* Deep copy.
*/
template <class Key,class Item>
RedBlackTree<Key,Item> &
RedBlackTree<Key,Item>::operator=(RedBlackTree<Key,Item> &rhs)
{
if( this != &rhs )
{
makeEmpty( );
header->right = clone(rhs.header->right);
}
return *this;
}
/**
* Internal method to print a subtree t in sorted order.
*/
template <class Key,class Item>
void RedBlackTree<Key,Item>::printTree(RedBlackNode<Key,Item> *t)
{
if( t != t->left )
{
printTree(t->left);
cout<<"Key:"<<t->key<<" Item:"<<t->item<<endl;
printTree(t->right);
}
}
template <class Key,class Item>
RedBlackNode<Key,Item> *RedBlackTree<Key,Item>::find(RedBlackNode<Key,Item> *t,Key &key)
{
if(t!=NULL)
{
if(key < t->key)
return find(t->left,key);
else
if(key > t->key)
return find(t->right,key);
else
return t;
}
}
/**
* Internal method to clone subtree.
*/
template <class Key,class Item>
RedBlackNode<Key,Item> *
RedBlackTree<Key,Item>::clone(RedBlackNode<Key,Item> * t)
{
if(t == t->left) // Cannot test against nullNode!!!
return nullNode;
else
return new RedBlackNode<Key,Item>(t->key,t->item,clone(t->left),
clone(t->right),t->color);
}
/**
* Internal routine that is called during an insertion
* if a node has two red children. Performs flip
* and rotatons.
* item is the item being inserted.
*/
template <class Key,class Item>
void RedBlackTree<Key,Item>::handleReorient(Key &key)
{
// Do the color flip
current->color = RED;
current->left->color = BLACK;
current->right->color = BLACK;
if(parent->color == RED) // Have to rotate
{
grand->color = RED;
if(key < grand->key != key < parent->key)
parent = rotate(key,grand); // Start dbl rotate
current = rotate(key,great);
current->color = BLACK;
}
header->right->color = BLACK; // Make root black
}
/**
* Internal routine that performs a single or double rotation.
* Because the result is attached to the parent, there are four cases.
* Called by handleReorient.
* item is the item in handleReorient.
* parent is the parent of the root of the rotated subtree.
* Return the root of the rotated subtree.
*/
template <class Key,class Item>
RedBlackNode<Key,Item> *
RedBlackTree<Key,Item>::rotate(Key & key,
RedBlackNode<Key,Item> *theParent)
{
if(key < theParent->key )
{
key < theParent->left->key ?
rotateWithLeftChild(theParent->left) : // LL
rotateWithRightChild(theParent->left); // LR
return theParent->left;
}
else
{
key < theParent->right->key ?
rotateWithLeftChild(theParent->right) : // RL
rotateWithRightChild(theParent->right); // RR
return theParent->right;
}
}
/**
* Rotate binary tree node with left child.
*/
template <class Key,class Item>
void RedBlackTree<Key,Item>::
rotateWithLeftChild(RedBlackNode<Key,Item> * &k2)
{
RedBlackNode<Key,Item> *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2 = k1;
}
/**
* Rotate binary tree node with right child.
*/
template <class Key,class Item>
void RedBlackTree<Key,Item>::
rotateWithRightChild(RedBlackNode<Key,Item> * &k1)
{
RedBlackNode<Key,Item> *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1 = k2;
}
/**
* Internal method to reclaim internal nodes
* in subtree t.
*/
template <class Key,class Item>
void RedBlackTree<Key,Item>::reclaimMemory(RedBlackNode<Key,Item> *t)
{
if( t != t->left )
{
reclaimMemory( t->left );
reclaimMemory( t->right );
delete t;
}
}
////////////////////////////
////////////////////////////
#endif
Code: Select all
#include "RedBlackTree.h"
#include <iostream>
using namespace std;
// Test program
int main( )
{
float ITEM_NOT_FOUND =-9999.99f ;
RedBlackTree<int,float> t(ITEM_NOT_FOUND);
int NUMS = 40000;
int GAP = 37;
int i;
float f;
cout<<"Checking... (no more output means success)"<<endl;
for(i=rand()%GAP,f=i+0.1f;i<rand()%NUMS;i=i+rand()%GAP,f=i+0.1f)
t.insert(i,f);
t.printTree();
cout<<t.findMin()<<" "<<t.findMax()<<endl;
return 0;
}
