Angelscript/angelscript/source/as_map.h

787 lines
16 KiB
C++

/*
AngelCode Scripting Library
Copyright (c) 2003-2013 Andreas Jonsson
This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any
damages arising from the use of this software.
Permission is granted to anyone to use this software for any
purpose, including commercial applications, and to alter it and
redistribute it freely, subject to the following restrictions:
1. The origin of this software must not be misrepresented; you
must not claim that you wrote the original software. If you use
this software in a product, an acknowledgment in the product
documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and
must not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source
distribution.
The original version of this library can be located at:
http://www.angelcode.com/angelscript/
Andreas Jonsson
andreas@angelcode.com
*/
//
// as_map.h
//
// This class is used for mapping a value to another
//
#ifndef AS_MAP_H
#define AS_MAP_H
template <class KEY, class VAL> struct asSMapNode;
template <class KEY, class VAL> class asCMap
{
public:
asCMap();
~asCMap();
int Insert(const KEY &key, const VAL &value);
int Insert(asSMapNode<KEY,VAL> *node);
int GetCount() const;
const KEY &GetKey(const asSMapNode<KEY,VAL> *cursor) const;
const VAL &GetValue(const asSMapNode<KEY,VAL> *cursor) const;
VAL &GetValue(asSMapNode<KEY,VAL> *cursor);
void Erase(asSMapNode<KEY,VAL> *cursor);
asSMapNode<KEY,VAL> *Remove(asSMapNode<KEY,VAL> *cursor);
void EraseAll();
void SwapWith(asCMap<KEY,VAL> &other);
// Returns true as long as cursor is valid
bool MoveTo(asSMapNode<KEY,VAL> **out, const KEY &key) const;
bool MoveFirst(asSMapNode<KEY,VAL> **out) const;
bool MoveLast(asSMapNode<KEY,VAL> **out) const;
bool MoveNext(asSMapNode<KEY,VAL> **out, asSMapNode<KEY,VAL> *cursor) const;
bool MovePrev(asSMapNode<KEY,VAL> **out, asSMapNode<KEY,VAL> *cursor) const;
// For debugging only
int CheckIntegrity(asSMapNode<KEY,VAL> *node) const;
protected:
// Don't allow value assignment
asCMap &operator=(const asCMap &) { return *this; }
void BalanceInsert(asSMapNode<KEY,VAL> *node);
void BalanceErase(asSMapNode<KEY,VAL> *child, asSMapNode<KEY,VAL> *parent);
int EraseAll(asSMapNode<KEY,VAL> *node);
int RotateLeft(asSMapNode<KEY,VAL> *node);
int RotateRight(asSMapNode<KEY,VAL> *node);
asSMapNode<KEY,VAL> *root;
asSMapNode<KEY,VAL> dummy;
int count;
};
//---------------------------------------------------------------------------
// Implementation
// Properties of a Red-Black Tree
//
// 1. The root is always black
// 2. All single paths from the root to leafs
// contain the same amount of black nodes
// 3. No red node can have a red node as parent
#define ISRED(x) ((x != 0) && (x)->isRed)
#define ISBLACK(x) (!ISRED(x))
template <class KEY, class VAL> struct asSMapNode
{
asSMapNode() {parent = 0; left = 0; right = 0; isRed = true;}
void Init(KEY k, VAL v) {key = k; value = v; parent = 0; left = 0; right = 0; isRed = true;}
asSMapNode *parent;
asSMapNode *left;
asSMapNode *right;
bool isRed;
KEY key;
VAL value;
};
template <class KEY, class VAL>
asCMap<KEY, VAL>::asCMap()
{
root = 0;
count = 0;
}
template <class KEY, class VAL>
asCMap<KEY, VAL>::~asCMap()
{
EraseAll();
}
template <class KEY, class VAL>
void asCMap<KEY,VAL>::SwapWith(asCMap<KEY,VAL> &other)
{
asSMapNode<KEY,VAL> *tmpRoot = root;
int tmpCount = count;
root = other.root;
count = other.count;
other.root = tmpRoot;
other.count = tmpCount;
}
template <class KEY, class VAL>
void asCMap<KEY, VAL>::EraseAll()
{
EraseAll(root);
root = 0;
}
template <class KEY, class VAL>
int asCMap<KEY, VAL>::EraseAll(asSMapNode<KEY, VAL> *p)
{
if( p == 0 ) return -1;
EraseAll( p->left );
EraseAll( p->right );
typedef asSMapNode<KEY,VAL> node_t;
asDELETE(p,node_t);
count--;
return 0;
}
template <class KEY, class VAL>
int asCMap<KEY, VAL>::GetCount() const
{
return count;
}
template <class KEY, class VAL>
int asCMap<KEY, VAL>::Insert(const KEY &key, const VAL &value)
{
typedef asSMapNode<KEY,VAL> node_t;
asSMapNode<KEY,VAL> *nnode = asNEW(node_t);
if( nnode == 0 )
{
// Out of memory
return -1;
}
nnode->key = key;
nnode->value = value;
return Insert(nnode);
}
template <class KEY, class VAL>
int asCMap<KEY, VAL>::Insert(asSMapNode<KEY,VAL> *nnode)
{
// Insert the node
if( root == 0 )
root = nnode;
else
{
asSMapNode<KEY,VAL> *p = root;
for(;;)
{
if( nnode->key < p->key )
{
if( p->left == 0 )
{
nnode->parent = p;
p->left = nnode;
break;
}
else
p = p->left;
}
else
{
if( p->right == 0 )
{
nnode->parent = p;
p->right = nnode;
break;
}
else
p = p->right;
}
}
}
BalanceInsert(nnode);
count++;
return 0;
}
template <class KEY, class VAL>
void asCMap<KEY, VAL>::BalanceInsert(asSMapNode<KEY, VAL> *node)
{
// The node, that is red, can't have a red parent
while( node != root && node->parent->isRed )
{
// Check color of uncle
if( node->parent == node->parent->parent->left )
{
asSMapNode<KEY,VAL> *uncle = node->parent->parent->right;
if( ISRED(uncle) )
{
// B
// R R
// N
// Change color on parent, uncle, and grand parent
node->parent->isRed = false;
uncle->isRed = false;
node->parent->parent->isRed = true;
// Continue balancing from grand parent
node = node->parent->parent;
}
else
{
// B
// R B
// N
if( node == node->parent->right )
{
// Make the node a left child
node = node->parent;
RotateLeft(node);
}
// Change color on parent and grand parent
// Then rotate grand parent to the right
node->parent->isRed = false;
node->parent->parent->isRed = true;
RotateRight(node->parent->parent);
}
}
else
{
asSMapNode<KEY,VAL> *uncle = node->parent->parent->left;
if( ISRED(uncle) )
{
// B
// R R
// N
// Change color on parent, uncle, and grand parent
// Continue balancing from grand parent
node->parent->isRed = false;
uncle->isRed = false;
node = node->parent->parent;
node->isRed = true;
}
else
{
// B
// B R
// N
if( node == node->parent->left )
{
// Make the node a right child
node = node->parent;
RotateRight(node);
}
// Change color on parent and grand parent
// Then rotate grand parent to the right
node->parent->isRed = false;
node->parent->parent->isRed = true;
RotateLeft(node->parent->parent);
}
}
}
root->isRed = false;
}
// For debugging purposes only
template <class KEY, class VAL>
int asCMap<KEY, VAL>::CheckIntegrity(asSMapNode<KEY, VAL> *node) const
{
if( node == 0 )
{
if( root == 0 )
return 0;
else if( ISRED(root) )
return -1;
else
node = root;
}
int left = 0, right = 0;
if( node->left )
left = CheckIntegrity(node->left);
if( node->right )
right = CheckIntegrity(node->right);
if( left != right || left == -1 )
return -1;
if( ISBLACK(node) )
return left+1;
return left;
}
// Returns true if successful
template <class KEY, class VAL>
bool asCMap<KEY, VAL>::MoveTo(asSMapNode<KEY,VAL> **out, const KEY &key) const
{
asSMapNode<KEY,VAL> *p = root;
while( p )
{
if( key < p->key )
p = p->left;
else if( key == p->key )
{
if( out ) *out = p;
return true;
}
else
p = p->right;
}
if( out ) *out = 0;
return false;
}
template <class KEY, class VAL>
void asCMap<KEY, VAL>::Erase(asSMapNode<KEY,VAL> *cursor)
{
asSMapNode<KEY,VAL> *node = Remove(cursor);
asASSERT( node == cursor );
typedef asSMapNode<KEY,VAL> node_t;
asDELETE(node,node_t);
}
template <class KEY, class VAL>
asSMapNode<KEY,VAL> *asCMap<KEY, VAL>::Remove(asSMapNode<KEY,VAL> *cursor)
{
if( cursor == 0 ) return 0;
asSMapNode<KEY,VAL> *node = cursor;
//---------------------------------------------------
// Choose the node that will replace the erased one
asSMapNode<KEY,VAL> *remove;
if( node->left == 0 || node->right == 0 )
remove = node;
else
{
remove = node->right;
while( remove->left ) remove = remove->left;
}
//--------------------------------------------------
// Remove the node
asSMapNode<KEY,VAL> *child;
if( remove->left )
child = remove->left;
else
child = remove->right;
if( child ) child->parent = remove->parent;
if( remove->parent )
{
if( remove == remove->parent->left )
remove->parent->left = child;
else
remove->parent->right = child;
}
else
root = child;
// If we remove a black node we must make sure the tree is balanced
if( ISBLACK(remove) )
BalanceErase(child, remove->parent);
//----------------------------------------
// Replace the erased node with the removed one
if( remove != node )
{
if( node->parent )
{
if( node->parent->left == node )
node->parent->left = remove;
else
node->parent->right = remove;
}
else
root = remove;
remove->isRed = node->isRed;
remove->parent = node->parent;
remove->left = node->left;
if( remove->left ) remove->left->parent = remove;
remove->right = node->right;
if( remove->right ) remove->right->parent = remove;
}
count--;
return node;
}
// Call method only if removed node was black
// child is the child of the removed node
template <class KEY, class VAL>
void asCMap<KEY, VAL>::BalanceErase(asSMapNode<KEY, VAL> *child, asSMapNode<KEY, VAL> *parent)
{
// If child is red
// Color child black
// Terminate
// These tests assume brother is to the right.
// 1. Brother is red
// Color parent red and brother black
// Rotate parent left
// Transforms to 2b
// 2a. Parent and brother is black, brother's children are black
// Color brother red
// Continue test with parent as child
// 2b. Parent is red, brother is black, brother's children are black
// Color parent black and brother red
// Terminate
// 3. Brother is black, and brother's left is red and brother's right is black
// Color brother red and brother's left black
// Rotate brother to right
// Transforms to 4.
// 4. Brother is black, brother's right is red
// Color brother's right black
// Color brother to color of parent
// Color parent black
// Rotate parent left
// Terminate
while( child != root && ISBLACK(child) )
{
if( child == parent->left )
{
asSMapNode<KEY,VAL> *brother = parent->right;
// Case 1
if( ISRED(brother) )
{
brother->isRed = false;
parent->isRed = true;
RotateLeft(parent);
brother = parent->right;
}
// Case 2
if( brother == 0 ) break;
if( ISBLACK(brother->left) && ISBLACK(brother->right) )
{
// Case 2b
if( ISRED(parent) )
{
parent->isRed = false;
brother->isRed = true;
break;
}
brother->isRed = true;
child = parent;
parent = child->parent;
}
else
{
// Case 3
if( ISBLACK(brother->right) )
{
brother->left->isRed = false;
brother->isRed = true;
RotateRight(brother);
brother = parent->right;
}
// Case 4
brother->isRed = parent->isRed;
parent->isRed = false;
brother->right->isRed = false;
RotateLeft(parent);
break;
}
}
else
{
asSMapNode<KEY,VAL> *brother = parent->left;
// Case 1
if( ISRED(brother) )
{
brother->isRed = false;
parent->isRed = true;
RotateRight(parent);
brother = parent->left;
}
// Case 2
if( brother == 0 ) break;
if( ISBLACK(brother->left) && ISBLACK(brother->right) )
{
// Case 2b
if( ISRED(parent) )
{
parent->isRed = false;
brother->isRed = true;
break;
}
brother->isRed = true;
child = parent;
parent = child->parent;
}
else
{
// Case 3
if( ISBLACK(brother->left) )
{
brother->right->isRed = false;
brother->isRed = true;
RotateLeft(brother);
brother = parent->left;
}
// Case 4
brother->isRed = parent->isRed;
parent->isRed = false;
brother->left->isRed = false;
RotateRight(parent);
break;
}
}
}
if( child )
child->isRed = false;
}
template <class KEY, class VAL>
int asCMap<KEY, VAL>::RotateRight(asSMapNode<KEY, VAL> *node)
{
// P L //
// / \ / \ //
// L R => Ll P //
// / \ / \ //
// Ll Lr Lr R //
if( node->left == 0 ) return -1;
asSMapNode<KEY,VAL> *left = node->left;
// Update parent
if( node->parent )
{
asSMapNode<KEY,VAL> *parent = node->parent;
if( parent->left == node )
parent->left = left;
else
parent->right = left;
left->parent = parent;
}
else
{
root = left;
left->parent = 0;
}
// Move left's right child to node's left child
node->left = left->right;
if( node->left ) node->left->parent = node;
// Put node as left's right child
left->right = node;
node->parent = left;
return 0;
}
template <class KEY, class VAL>
int asCMap<KEY, VAL>::RotateLeft(asSMapNode<KEY, VAL> *node)
{
// P R //
// / \ / \ //
// L R => P Rr //
// / \ / \ //
// Rl Rr L Rl //
if( node->right == 0 ) return -1;
asSMapNode<KEY,VAL> *right = node->right;
// Update parent
if( node->parent )
{
asSMapNode<KEY,VAL> *parent = node->parent;
if( parent->right == node )
parent->right = right;
else
parent->left = right;
right->parent = parent;
}
else
{
root = right;
right->parent = 0;
}
// Move right's left child to node's right child
node->right = right->left;
if( node->right ) node->right->parent = node;
// Put node as right's left child
right->left = node;
node->parent = right;
return 0;
}
template <class KEY, class VAL>
const VAL &asCMap<KEY, VAL>::GetValue(const asSMapNode<KEY,VAL> *cursor) const
{
if( cursor == 0 )
return dummy.value;
return cursor->value;
}
template <class KEY, class VAL>
VAL &asCMap<KEY, VAL>::GetValue(asSMapNode<KEY,VAL> *cursor)
{
if( cursor == 0 )
return dummy.value;
return cursor->value;
}
template <class KEY, class VAL>
const KEY &asCMap<KEY, VAL>::GetKey(const asSMapNode<KEY,VAL> *cursor) const
{
if( cursor == 0 )
return dummy.key;
return cursor->key;
}
template <class KEY, class VAL>
bool asCMap<KEY, VAL>::MoveFirst(asSMapNode<KEY,VAL> **out) const
{
*out = root;
if( root == 0 ) return false;
while( (*out)->left )
*out = (*out)->left;
return true;
}
template <class KEY, class VAL>
bool asCMap<KEY, VAL>::MoveLast(asSMapNode<KEY,VAL> **out) const
{
*out = root;
if( root == 0 ) return false;
while( (*out)->right )
*out = (*out)->right;
return true;
}
template <class KEY, class VAL>
bool asCMap<KEY, VAL>::MoveNext(asSMapNode<KEY,VAL> **out, asSMapNode<KEY,VAL> *cursor) const
{
if( cursor == 0 )
{
*out = 0;
return false;
}
if( cursor->right == 0 )
{
// Move upwards until we find a parent node to the right
while( cursor->parent && cursor->parent->right == cursor )
cursor = cursor->parent;
cursor = cursor->parent;
*out = cursor;
if( cursor == 0 )
return false;
return true;
}
cursor = cursor->right;
while( cursor->left )
cursor = cursor->left;
*out = cursor;
return true;
}
template <class KEY, class VAL>
bool asCMap<KEY, VAL>::MovePrev(asSMapNode<KEY,VAL> **out, asSMapNode<KEY,VAL> *cursor) const
{
if( cursor == 0 )
{
*out = 0;
return false;
}
if( cursor->left == 0 )
{
// Move upwards until we find a parent node to the left
while( cursor->parent && cursor->parent->left == cursor )
cursor = cursor->parent;
cursor = cursor->parent;
*out = cursor;
if( cursor == 0 )
return false;
return true;
}
cursor = cursor->left;
while( cursor->right )
cursor = cursor->right;
*out = cursor;
return true;
}
#endif