在一个死亡的论坛上发一个从未活过的代码，致我已经风飘云散的过去 - Chinaunix

#ifndef _RBTree_H_
#define _RBTree_H_
#include <e32base.h>
#define EFailed ((TAny *)(-1))
typedef void (*TFree)(void*);
typedef TInt (*TComp)(void*, void*);
struct TUserOP{
TFree iFree;
TComp iCompare;
};
class TTreeNode;
class TTreeIterator;
class CRBTree : public CBase{
public:
// TUser must not be NULL and iCompare should be
// provided too. while, iFree can be NULL if not needed
static IMPORT_C CRBTree* NewL(TUserOP* op);
IMPORT_C ~CRBTree();
// add a node to tree
// aUser, data proviced by user which will be added to tree
// aRep, if the data has exists, would it replace the old one
// or failed
// return value: EFailed, error occured
// the old one being replaced by the aUser, if aRep is false or
// there is data which is equal to aUser, return NULL
IMPORT_C TAny* AddL(TAny* aUser, TBool aRep);
// remove node
IMPORT_C TAny* Unlink(TAny* aUser);
IMPORT_C void Remove(TAny* aUser);
// clear all nodes in the tree
// the tree will be empty, while ok to add nodes again
IMPORT_C void Reset();
// number of nodes of the tree
IMPORT_C TInt Length();
// the min node in the tree
// the compare is provided by TUserOP
IMPORT_C TAny* Min();
// the max node in the tree
// the compare is provided by TUserOP
IMPORT_C TAny* Max();
// find the node in the tree, which is euqal to aUser
// compared with TUserOP::iCompare
IMPORT_C TAny* Find(TAny* aUser);
// generate a handle for later FindNext
// return -1, when can't find the aUser
// the handle will be used for forward search only
IMPORT_C TInt FindFirst(TAny* aUser);
// generate a handle for later RFindNext
// return -1, when can't find the aUser
// the handle will be used for backward search only
IMPORT_C TInt RFindFirst(TAny* aUser);
// return data referenced by handle, and reposition the
// handle to nexr data
// return value: the data referenced by handle
// EFailed if error occured
// NULL when there is no more data
IMPORT_C TAny* FindNext(TInt aHandle);
// same with FindNext, but is a safer method, meaning, the
// method will validate the handle provided by user, while
// FindNext will not. The method is slower.
IMPORT_C TAny* FindNextSafe(TInt aHandle);
// return data referenced by handle, and reposition the
// handle to previous data
// return value: the data referenced by handle
// EFailed if error occured
// NULL when there is no more data
IMPORT_C TAny* RFindNext(TInt aHandle);
// same with RFindNext, but is a safer method, meaning, the
// method will validate the handle provided by user, while
// RFindNext will not. The method is slower.
IMPORT_C TAny* RFindNextSafe(TInt aHandle);
// Close the handle when finish using it.
// must be called after using it to release resouce used internal
IMPORT_C void CloseFindHandle(TInt handle);
// A safe version of CloseFindHandle
IMPORT_C void CloseFindHandleSafe(TInt handle);
#ifdef _DEBUG
IMPORT_C TInt BlackHeight();
private:
TInt CRBTree::BlackHeight(TTreeNode* aNode);
#endif
public:
enum TColor{EBlack, ERed};
enum TDirect{EForward, EBackward};
private:
CRBTree(TUserOP* op);
CRBTree::CRBTree(const CRBTree&);
CRBTree& operator = (const CRBTree&);
void ConstructL();
void AdjustBeforeInsert(TTreeNode* aNode);
void AdjustBeforeRemove(TTreeNode* aNode);
void InsertL(TAny* aUser, TTreeNode* aFather, TInt aFlag);
void InsertRotate(TTreeNode* aFather, TTreeNode* aNode);
TAny* RemoveNode(TTreeNode* aNode);
TTreeNode* Find(TAny* aUser, TInt& aFlag);
TInt FindFirst(TAny* aUser, TDirect aDirect);
TTreeNode* FindNext(TTreeNode* aNode);
TTreeNode* RFindNext(TTreeNode* aNode);
void AdjustFindHandles(TTreeNode* aNode);
TInt ValidateHandle(TInt aHandle);
TTreeNode** PointerOf(TTreeNode* aNode);
void RotateLeft(TTreeNode* aFather, TTreeNode* aNode, TTreeNode** aPPNode);
void RotateRight(TTreeNode* aFather, TTreeNode* aNode, TTreeNode** aPPNode);
private:
TUserOP* iOps;
TTreeNode* iRoot;
TTreeIterator* iIterator;
TInt iNrNodes;
};
#endif
#include "rbtree.h"
#include <e32std.h>
#define BLACK(x) (x == NULL || x->iColor == EBlack)
class TTreeNode{
public:
TTreeNode(CRBTree::TColor aColor){
iLChild = iRChild = iFather = NULL;
iColor = aColor;
}
public:
TTreeNode* iFather;
TTreeNode* iLChild;
TTreeNode* iRChild;
CRBTree::TColor iColor;
TAny* iUser;
};
class TTreeIterator{
public:
TTreeIterator(TTreeNode* aNode, CRBTree::TDirect aDirection){
ASSERT(aNode);
iNext = iPrev = NULL;
iNode = aNode;
iDirection = aDirection;
}
TTreeNode* iNode;
CRBTree::TDirect iDirection;
TTreeIterator* iNext;
TTreeIterator* iPrev;
};
//========================================================
CRBTree::CRBTree(TUserOP* aOp){
iOps = aOp;
}
EXPORT_C CRBTree::~CRBTree(){
Reset();
}
EXPORT_C CRBTree* CRBTree::NewL(TUserOP* aOp){
CRBTree* self = new (ELeave) CRBTree(aOp);
CleanupStack::PushL(self);
self->ConstructL();
CleanupStack::Pop();
return self;
}
void CRBTree::ConstructL(){
if(iOps == NULL || iOps->iCompare == NULL)
User::Leave(KErrArgument);
}
EXPORT_C TInt CRBTree::Length(){
return iNrNodes;
}
EXPORT_C TAny* CRBTree::Min(){
TTreeNode* cur = iRoot;
if(cur != NULL){
while(cur->iLChild){
cur = cur->iLChild;
}
}
return cur->iUser;
}
EXPORT_C TAny* CRBTree::Max(){
TTreeNode* cur = iRoot;
if(cur != NULL){
while(cur->iRChild){
cur = cur->iRChild;
}
}
return cur->iUser;
}
EXPORT_C void CRBTree::Reset(){
TTreeNode* cur = iRoot;
LABEL:
if(cur){
if(cur->iLChild){
cur = cur->iLChild;
goto LABEL;
}
if(cur->iRChild){
cur = cur->iRChild;
goto LABEL;
}
if(iOps->iFree){
iOps->iFree(cur->iUser);
}
TTreeNode* father = cur->iFather;
delete cur;
if(cur != iRoot){
if(father->iLChild == cur)
father->iLChild = NULL;
else
father->iRChild = NULL;
cur = father;
goto LABEL;
}
}
TTreeIterator* it = iIterator;
while(it){
TTreeIterator* next = it->iNext;
delete it;
it = next;
}
iRoot = NULL;
iIterator = NULL;
iNrNodes = 0;
}
EXPORT_C TAny* CRBTree::AddL(TAny* aUser, TBool aRep){
if(aUser == NULL)
User::Leave(KErrArgument);
if(iRoot == NULL){
TTreeNode* node = new (ELeave) TTreeNode(EBlack);
++iNrNodes;
iRoot = node;
iRoot->iUser = aUser;
return NULL;
}
TInt flag = 1;
TTreeNode* node = Find(aUser, flag);
ASSERT(node);
TAny* oldkey = node->iUser;
if(flag == 0){
if(aRep){
node->iUser = oldkey;
return oldkey;
}
User::Leave(KErrAlreadyExists);
}
InsertL(aUser, node, flag);
++iNrNodes;
return NULL;
}
void CRBTree::InsertL(TAny* aUser, TTreeNode* aFather, TInt aFlag){
TTreeNode* newNode = new (ELeave) TTreeNode(ERed);
newNode->iUser = aUser;
if(aFlag > 0){
aFather->iLChild = newNode;
newNode->iFather = aFather;
}else{
aFather->iRChild = newNode;
newNode->iFather = aFather;
}
if(aFather->iColor == ERed){
InsertRotate(aFather, newNode);
}
}
TTreeNode* CRBTree::Find(TAny* aUser, TInt& aFlag){
ASSERT(aUser);
TInt adjust = aFlag;
TTreeNode* cur = iRoot;
while(cur){
aFlag = iOps->iCompare(cur->iUser, aUser);
if(aFlag == 0)
return cur;
if(adjust && cur->iLChild && cur->iRChild &&
cur->iColor == EBlack && cur->iLChild->iColor == ERed &&
cur->iRChild->iColor == ERed){
AdjustBeforeInsert(cur);
}
if(aFlag > 0 && cur->iLChild){
cur = cur->iLChild;
}else if(aFlag < 0 && cur->iRChild){
cur = cur->iRChild;
}else{
return cur;
}
}
return NULL;
}
void CRBTree::AdjustBeforeInsert(TTreeNode* aNode){
aNode->iLChild->iColor = EBlack;
aNode->iRChild->iColor = EBlack;
if(aNode->iFather){
aNode->iColor = ERed;
if(aNode->iFather->iColor == ERed)
InsertRotate(aNode->iFather, aNode);
}
}
void CRBTree::InsertRotate(TTreeNode* aFather, TTreeNode* aNode){
ASSERT(aNode->iColor == ERed);
ASSERT(aFather->iColor == ERed);
ASSERT(aFather->iFather);
TTreeNode* grandpa = aFather->iFather;
TBool left1 = (aFather->iLChild == aNode);
TBool left2 = (grandpa->iLChild == aFather);
TBool same = (left1 == left2);
if(same){
aNode = aFather;
aFather = aNode->iFather;
}
LABEL:
TTreeNode** pp_node = PointerOf(aFather);
if(left1){
RotateRight(aFather, aNode, pp_node);
}else{
RotateLeft(aFather, aNode, pp_node);
}
if(!same){
left1 = !left1;
aFather = aNode->iFather;
same = true;
goto LABEL;
}
aNode->iColor = EBlack;
if(left1){
aNode->iRChild->iColor = ERed;
}else{
aNode->iLChild->iColor = ERed;
}
}
void CRBTree::RotateLeft(TTreeNode* aFather, TTreeNode* aNode, TTreeNode** aPPNode){
*aPPNode = aNode;
aNode->iFather = aFather->iFather;
aFather->iRChild = aNode->iLChild;
if(aNode->iLChild){
aNode->iLChild->iFather = aFather;
}
aNode->iLChild = aFather;
aFather->iFather = aNode;
}
void CRBTree::RotateRight(TTreeNode* aFather, TTreeNode* aNode, TTreeNode** aPPNode){
*aPPNode = aNode;
aNode->iFather = aFather->iFather;
aFather->iLChild = aNode->iRChild;
if(aNode->iRChild){
aNode->iRChild->iFather = aFather;
}
aNode->iRChild = aFather;
aFather->iFather = aNode;
}
EXPORT_C TAny* CRBTree::Unlink(TAny* aUser){
if(aUser == NULL){
return NULL;
}
TAny* user = NULL;
TInt flag = 0;
TTreeNode* node = Find(aUser, flag);
if(node != NULL && flag == 0){
AdjustFindHandles(node);
user = RemoveNode(node);
--iNrNodes;
}
return user;
}
EXPORT_C void CRBTree::Remove(TAny* aUser){
TAny* user = Unlink(aUser);
if(user && iOps->iFree){
iOps->iFree(user);
}
}
TAny* CRBTree::RemoveNode(TTreeNode* aNode){
ASSERT(aNode);
if(aNode->iLChild && aNode->iRChild){
TTreeNode* next = FindNext(aNode);
TAny* saved_key = next->iUser;
next->iUser = aNode->iUser;
aNode->iUser = saved_key;
aNode = next;
}
TTreeNode** pp_node = PointerOf(aNode);
if(aNode->iRChild != NULL){
aNode->iRChild->iFather = aNode->iFather;
aNode->iRChild->iColor = EBlack;
*pp_node = aNode->iRChild;
}else if(aNode->iLChild != NULL){
aNode->iLChild->iFather = aNode->iFather;
aNode->iLChild->iColor = EBlack;
*pp_node = aNode->iLChild;
}else{
if(aNode->iColor == EBlack){
AdjustBeforeRemove(aNode);
}
*pp_node = NULL;
}
TAny* user = aNode->iUser;
delete aNode;
return user;
}
void CRBTree::AdjustBeforeRemove(TTreeNode* aNode){
LABEL:
TTreeNode* father = aNode->iFather;
if(father == NULL){
return;
}
TTreeNode* brother;
TBool left = father->iLChild == aNode;
if(left){
brother = father->iRChild;
}else{
brother = father->iLChild;
}
ASSERT(brother);
if(brother->iColor == ERed){
TTreeNode** pp_node = PointerOf(father);
if(left){
RotateLeft(father, brother, pp_node);
brother = father->iRChild;
}else{
RotateRight(father, brother, pp_node);
brother = father->iLChild;
}
father->iColor = ERed;
father->iFather->iColor = EBlack;
}
if(BLACK(brother->iLChild) && BLACK(brother->iRChild)){
if(father->iColor == ERed){
father->iColor = EBlack;
brother->iColor = ERed;
return;
}
brother->iColor = ERed;
aNode = father;
goto LABEL;
}
if(left){
if(BLACK(brother->iRChild)){
ASSERT(brother->iLChild->iColor == ERed);
RotateRight(brother, brother->iLChild, &(father->iRChild));
brother = brother->iFather;
brother->iColor = EBlack;
brother->iRChild->iColor = ERed;
}
}else if(BLACK(brother->iLChild)){
ASSERT(brother->iRChild->iColor == ERed);
RotateLeft(brother, brother->iRChild, &(father->iLChild));
brother = brother->iFather;
brother->iColor = EBlack;
brother->iLChild->iColor = ERed;
}
TTreeNode** pp_node = PointerOf(father);
if(left){
RotateLeft(father, brother, pp_node);
brother->iRChild->iColor = EBlack;
}else{
RotateRight(father, brother, pp_node);
brother->iLChild->iColor = EBlack;
}
brother->iColor = father->iColor;
father->iColor = EBlack;
}
TTreeNode** CRBTree::PointerOf(TTreeNode* aNode){
ASSERT(aNode);
TTreeNode** pp_node;
if(aNode->iFather){
if(aNode->iFather->iLChild == aNode)
pp_node = &aNode->iFather->iLChild;
else
pp_node = &aNode->iFather->iRChild;
}else{
pp_node = &iRoot;
}
return pp_node;
}
TTreeNode* CRBTree::FindNext(TTreeNode* aNode){
ASSERT(aNode);
TTreeNode* cur = aNode->iRChild;
if(cur){
while(cur->iLChild){
cur = cur->iLChild;
}
return cur;
}
cur = aNode->iFather;
while(cur){
if(cur->iLChild == aNode){
return cur;
}
aNode = cur;
cur = cur->iFather;
}
return NULL;
}
TTreeNode* CRBTree::RFindNext(TTreeNode* aNode){
ASSERT(aNode);
TTreeNode* cur = aNode->iLChild;
if(cur){
while(cur->iRChild){
cur = cur->iRChild;
}
return cur;
}
cur = aNode->iFather;
while(cur){
if(cur->iRChild == aNode){
return cur;
}
aNode = cur;
cur = cur->iFather;
}
return NULL;
}
void CRBTree::AdjustFindHandles(TTreeNode* aNode){
TTreeIterator* it = iIterator;
while(it){
if(it->iNode == aNode){
if(it->iDirection == EForward){
it->iNode = FindNext(aNode);
}else{
it->iNode = RFindNext(aNode);
}
}
it = it->iNext;
}
}
TInt CRBTree::ValidateHandle(TInt aHandle){
TTreeIterator* it = iIterator;
TTreeIterator* in = (TTreeIterator *) aHandle;
while(it){
if(it == in){
break;
}
it = it->iNext;
}
if(it == NULL){
return -1;
}
return 0;
}
EXPORT_C TAny* CRBTree::Find(TAny* aUser){
if(aUser == NULL){
return NULL;
}
TInt flag = 0;
TTreeNode* node = Find(aUser, flag);
if(node == NULL || flag != 0){
return NULL;
}
return node->iUser;
}
TInt CRBTree::FindFirst(TAny* aUser, TDirect aDirect){
if(aUser == NULL){
return -1;
}
TInt flag = 0;
TTreeNode* node = Find(aUser, flag);
if(node == NULL){
return -1;
}
if(flag == 0){
TTreeIterator* it;
TRAPD(err, it = new (ELeave) TTreeIterator(node, aDirect));
if(KErrNone != err){
return -1;
}
if(iIterator != NULL){
it->iNext = iIterator;
iIterator->iPrev = it;
}
iIterator = it;
return (TInt) (iIterator);
}
return -1;
}
EXPORT_C TInt CRBTree::FindFirst(TAny* aUser){
return FindFirst(aUser, EForward);
}
EXPORT_C TInt CRBTree::RFindFirst(TAny* aUser){
return FindFirst(aUser, EBackward);
}
EXPORT_C TAny* CRBTree::FindNext(TInt handle){
TTreeIterator* it = (TTreeIterator *) handle;
if(it->iDirection != EForward){
return EFailed;
}
TTreeNode* node = it->iNode;
if(node == NULL){
return NULL;
}
TTreeNode* next = FindNext(node);
it->iNode = next;
return node->iUser;
}
EXPORT_C TAny* CRBTree::FindNextSafe(TInt handle){
if(-1 == ValidateHandle(handle)){
return EFailed;
}
return FindNext(handle);
}
EXPORT_C TAny* CRBTree::RFindNext(TInt handle){
TTreeIterator* it = (TTreeIterator *) handle;
if(it->iDirection != EBackward){
return EFailed;
}
TTreeNode* node = it->iNode;
if(node == NULL){
return NULL;
}
TTreeNode* next = RFindNext(node);
it->iNode = next;
return node->iUser;
}
EXPORT_C TAny* CRBTree::RFindNextSafe(TInt handle){
if(-1 == ValidateHandle(handle)){
return EFailed;
}
return RFindNext(handle);
}
EXPORT_C void CRBTree::CloseFindHandle(TInt handle){
if(iIterator == NULL){
return;
}
TTreeIterator* in = (TTreeIterator *) handle;
if(iIterator == in){
iIterator = in->iNext;
if(iIterator)
iIterator->iPrev = NULL;
}else{
in->iPrev->iNext = in->iNext;
if(in->iNext)
in->iNext->iPrev = in->iPrev;
}
delete in;
}
EXPORT_C void CRBTree::CloseFindHandleSafe(TInt handle){
if(-1 != ValidateHandle(handle)){
CloseFindHandle(handle);
}
}
#ifdef _DEBUG
EXPORT_C TInt CRBTree::BlackHeight(){
ASSERT(BLACK(iRoot));
return BlackHeight(iRoot);
}
TInt CRBTree::BlackHeight(TTreeNode* aNode){
TInt n = 0;
if(BLACK(aNode)){
n = 1;
}else{
ASSERT(BLACK(aNode->iLChild));
ASSERT(BLACK(aNode->iRChild));
}
TInt n1 = 0;
TInt n2 = 0;
if(aNode){
n1 = BlackHeight(aNode->iLChild);
n2 = BlackHeight(aNode->iRChild);
}
ASSERT(n1 == n2);
return (n + n1);
}
#endif

复制代码