// --------------------------------------------------------------------------
// www.UnitedBusinessTechnologies.com
// Copyright (c) 1998 - 2002 All Rights Reserved.
//
// Source in this file is released to the public under the following license:
// --------------------------------------------------------------------------
// This toolkit may be used free of charge for any purpose including corporate
// and academic use. For profit, and Non-Profit uses are permitted.
//
// This source code and any work derived from this source code must retain
// this copyright at the top of each source file.
//
// UBT welcomes any suggestions, improvements or new platform ports.
// email to: XMLFoundation@UnitedBusinessTechnologies.com
// --------------------------------------------------------------------------
#include "GBTree.h"
#include <string.h> // for:strlen(), strcpy(), strcmp()
GBTree::GBTree() :
m_root(0),
m_numNodes(0),
m_Last(0),
m_First(0)
{
}
void GBTree::clear()
{
GBTreeStruct *curr = m_First;
while(curr)
{
delete [] curr->m_szKey;
GBTreeStruct *d = curr;
curr = curr->m_Next;
delete d;
}
m_First = 0;
m_root = 0;
m_numNodes = 0;
}
void GBTree::rightRotate(GBTreeStruct * &rootPtr)
{
GBTreeStruct *ptr2, *ptr3;
ptr2 = rootPtr->m_rightPtr;
if (ptr2->m_balance == rightTilt)
{
// rotate once
rootPtr->m_rightPtr = ptr2->m_leftPtr;
ptr2->m_leftPtr = rootPtr;
rootPtr->m_balance = noTilt;
rootPtr = ptr2;
}
else
{
// rotate twice
ptr3 = ptr2->m_leftPtr;
ptr2->m_leftPtr = ptr3->m_rightPtr;
ptr3->m_rightPtr = ptr2;
rootPtr->m_rightPtr = ptr3->m_leftPtr;
ptr3->m_leftPtr = rootPtr;
ptr2->m_balance = (ptr3->m_balance == leftTilt) ? rightTilt : noTilt;
rootPtr->m_balance = (ptr3->m_balance == rightTilt) ? leftTilt : noTilt;
rootPtr = ptr3;
}
rootPtr->m_balance = noTilt;
}
void GBTree::leftRotate(GBTreeStruct * &rootPtr)
{
GBTreeStruct *ptr2, *ptr3;
ptr2 = rootPtr->m_leftPtr;
if (ptr2->m_balance == leftTilt)
{
// rotate once
rootPtr->m_leftPtr = ptr2->m_rightPtr;
ptr2->m_rightPtr = rootPtr;
rootPtr->m_balance = noTilt;
rootPtr = ptr2;
}
else
{
// rotate twice
ptr3 = ptr2->m_rightPtr;
ptr2->m_rightPtr = ptr3->m_leftPtr;
ptr3->m_leftPtr = ptr2;
rootPtr->m_leftPtr = ptr3->m_rightPtr;
ptr3->m_rightPtr = rootPtr;
ptr2->m_balance = (ptr3->m_balance == rightTilt) ? leftTilt : noTilt;
rootPtr->m_balance = (ptr3->m_balance == leftTilt) ? rightTilt : noTilt;
rootPtr = ptr3;
}
rootPtr->m_balance = noTilt;
}
void GBTree::insertNode(GBTreeStruct * &rootPtr, const char *szKey, void *value)
{
if (!rootPtr)
{
rootPtr = new GBTreeStruct;
if (!rootPtr)
{
// throw GenericException();
}
// copy data
rootPtr->m_dataNode = value;
rootPtr->m_leftPtr = 0;
rootPtr->m_rightPtr = 0;
rootPtr->m_balance = noTilt;
rootPtr->m_szKey = new char[strlen(szKey) + 1];
strcpy(rootPtr->m_szKey, szKey);
if (!m_First)
m_First = rootPtr;
rootPtr->m_Prev = m_Last;
rootPtr->m_Next = 0;
if (m_Last)
m_Last->m_Next = rootPtr;
m_Last = rootPtr;
m_numNodes++;
m_insertedOK = 1;
}
else if (strcmp(szKey, rootPtr->m_szKey) < 0)
{
insertNode(rootPtr->m_leftPtr, szKey, value);
if (m_insertedOK)
{
switch (rootPtr->m_balance)
{
case leftTilt :
leftRotate(rootPtr);
m_insertedOK = 0;
break;
case noTilt :
rootPtr->m_balance = leftTilt;
break;
case rightTilt :
rootPtr->m_balance = noTilt;
m_insertedOK = 0;
break;
}
}
}
else
{
insertNode(rootPtr->m_rightPtr, szKey, value);
if (m_insertedOK)
{
switch (rootPtr->m_balance)
{
case leftTilt :
rootPtr->m_balance = noTilt;
m_insertedOK = 0;
break;
case noTilt :
rootPtr->m_balance = rightTilt;
break;
case rightTilt :
rightRotate(rootPtr);
m_insertedOK = 0;
break;
}
}
}
}
void *GBTree::searchTree(const char *szKey, unsigned occur /* = 1 */)
{
unsigned count = 0;
GBTreeStruct *p = 0;
occur = (occur == 0) ? 1 : occur;
if (occur > m_numNodes)
{
return 0;
}
p = m_root;
while (p && count < occur)
{
int nDir = strcmp(szKey, p->m_szKey);
if (nDir > 0)
{
p = p->m_rightPtr;
}
else if (nDir < 0)
{
p = p->m_leftPtr;
}
else
{
// found a match
count++;
if (count < occur)
{
p = p->m_leftPtr;
}
}
}
if (p)
return p->m_dataNode;
return 0;
}
void GBTree::rightBalance(GBTreeStruct * &rootPtr, bool &delOK)
{
GBTreeStruct *ptr2, *ptr3;
balanceState balance, balnc3;
switch (rootPtr->m_balance)
{
case leftTilt :
rootPtr->m_balance = noTilt;
break;
case noTilt :
rootPtr->m_balance = rightTilt;
delOK = 0;
break;
case rightTilt :
ptr2 = rootPtr->m_rightPtr;
balance = ptr2->m_balance;
if (balance != leftTilt)
{
rootPtr->m_rightPtr = ptr2->m_leftPtr;
ptr2->m_leftPtr = rootPtr;
if (balance == noTilt)
{
rootPtr->m_balance = rightTilt;
ptr2->m_balance = leftTilt;
delOK = 0;
}
else
{
rootPtr->m_balance = noTilt;
ptr2->m_balance = noTilt;
}
rootPtr = ptr2;
}
else
{
ptr3 = ptr2->m_leftPtr;
balnc3 = ptr3->m_balance;
ptr2->m_leftPtr = ptr3->m_rightPtr;
ptr3->m_rightPtr = ptr2;
rootPtr->m_rightPtr = ptr3->m_leftPtr;
ptr3->m_leftPtr = rootPtr;
ptr2->m_balance = (balnc3 == leftTilt) ? rightTilt : noTilt;
rootPtr->m_balance = (balnc3 == rightTilt) ? leftTilt : noTilt;
rootPtr = ptr3;
ptr3->m_balance = noTilt;
}
break;
}
}
void GBTree::leftBalance(GBTreeStruct * &rootPtr, bool &delOK)
{
GBTreeStruct *ptr2, *ptr3;
balanceState balance, balnc3;
switch (rootPtr->m_balance)
{
case rightTilt :
rootPtr->m_balance = noTilt;
break;
case noTilt :
rootPtr->m_balance = leftTilt;
delOK = 0;
break;
case leftTilt :
ptr2 = rootPtr->m_leftPtr;
balance = ptr2->m_balance;
if (balance != rightTilt)
{
rootPtr->m_leftPtr = ptr2->m_rightPtr;
ptr2->m_rightPtr = rootPtr;
if (balance == noTilt)
{
rootPtr->m_balance = leftTilt;
ptr2->m_balance = rightTilt;
delOK = 0;
}
else
{
rootPtr->m_balance = noTilt;
ptr2->m_balance = noTilt;
}
rootPtr = ptr2;
}
else
{
ptr3 = ptr2->m_rightPtr;
balnc3 = ptr3->m_balance;
ptr2->m_rightPtr = ptr3->m_leftPtr;
ptr3->m_leftPtr = ptr2;
rootPtr->m_leftPtr = ptr3->m_rightPtr;
ptr3->m_rightPtr = rootPtr;
ptr2->m_balance = (balnc3 == rightTilt) ? leftTilt : noTilt;
rootPtr->m_balance = (balnc3 == leftTilt) ? rightTilt : noTilt;
rootPtr = ptr3;
ptr3->m_balance = noTilt;
}
break;
}
}
void GBTree::deleteBothChildren(GBTreeStruct * &rootPtr,
GBTreeStruct * &ptr,
bool &delOK)
{
if (!ptr->m_rightPtr)
{
rootPtr->m_dataNode = ptr->m_dataNode;
delete rootPtr->m_szKey;
rootPtr->m_szKey = ptr->m_szKey;
ptr->m_szKey = 0;
m_nodeMarker = ptr;
if (ptr == m_First)
m_First = ptr;
if (ptr == m_Last)
m_Last = ptr->m_Prev;
if (ptr->m_Prev)
ptr->m_Prev->m_Next = ptr->m_Next;
if (ptr->m_Next)
ptr->m_Next->m_Prev = ptr->m_Prev;
ptr = ptr->m_leftPtr;
delOK = 1;
}
else
{
deleteBothChildren(rootPtr, ptr->m_rightPtr, delOK);
if (delOK)
{
leftBalance(ptr, delOK);
}
///
}
}
void GBTree::removeNode(GBTreeStruct * &rootPtr,
unsigned &occur,
bool &delOK,
const char *szKey)
{
GBTreeStruct *p;
if (!rootPtr)
{
delOK = 0;
}
else
{
int nMatched = strcmp(szKey, rootPtr->m_szKey);
if (nMatched == 0)
{
occur--;
}
if (occur > 0 && nMatched <= 0)
{
removeNode(rootPtr->m_leftPtr, occur, delOK, szKey);
if (delOK)
{
rightBalance(rootPtr, delOK);
}
}
else if (nMatched > 0)
{
removeNode(rootPtr->m_rightPtr, occur, delOK, szKey);
if (delOK)
{
leftBalance(rootPtr, delOK);
}
}
else
{
p = rootPtr;
if (!rootPtr->m_rightPtr)
{
rootPtr = rootPtr->m_leftPtr;
delOK = 1;
if (p == m_First)
m_First = p->m_Next;
if (p == m_Last)
m_Last = p->m_Prev;
if (p->m_Prev)
p->m_Prev->m_Next = p->m_Next;
if (p->m_Next)
p->m_Next->m_Prev = p->m_Prev;
delete p->m_szKey;
p->m_szKey = 0;
delete p;
p = 0;
}
else if (!rootPtr->m_leftPtr)
{
rootPtr = rootPtr->m_rightPtr;
delOK = 1;
if (p == m_First)
m_First = p->m_Next;
if (p == m_Last)
m_Last = p->m_Prev;
if (p->m_Prev)
p->m_Prev->m_Next = p->m_Next;
if (p->m_Next)
p->m_Next->m_Prev = p->m_Prev;
delete p->m_szKey;
p->m_szKey = 0;
delete p;
p = 0;
}
else
{
deleteBothChildren(rootPtr, rootPtr->m_leftPtr, delOK);
if (delOK)
{
rightBalance(rootPtr, delOK);
}
delete m_nodeMarker;
}
m_numNodes--;
}
}
}
bool GBTree::remove(const char *szKey, unsigned occur /* = 1 */)
{
unsigned oldCount = m_numNodes;
bool delOK = 0;
occur = (occur == 0) ? 1 : occur;
if (occur > m_numNodes)
return 0;
removeNode(m_root, occur, delOK, szKey);
return (oldCount > m_numNodes) ? 1 : 0;
}
bool GBTree::delSubTree(GBTreeStruct * &rootPtr)
{
bool delThisNode = 0;
if (!rootPtr->m_leftPtr && !rootPtr->m_rightPtr)
{
delThisNode = 1;
}
else
{
if (rootPtr->m_leftPtr)
{
if (delSubTree(rootPtr->m_leftPtr))
{
delete rootPtr->m_leftPtr->m_szKey;
delete rootPtr->m_leftPtr;
rootPtr->m_leftPtr = 0;
}
}
if (rootPtr->m_rightPtr)
{
if (delSubTree(rootPtr->m_rightPtr))
{
delete rootPtr->m_rightPtr->m_szKey;
delete rootPtr->m_rightPtr;
rootPtr->m_rightPtr = 0;
}
}
delThisNode = (!rootPtr->m_leftPtr && !rootPtr->m_rightPtr) ? 1 : 0;
}
return delThisNode;
}
void GBTree::insert(const char *szKey, void *value)
{
m_insertedOK = 0;
insertNode(m_root, szKey, value);
}
void GBTreeIterator::Reset(GBTree *p, int nDirection)
{
m_pTree = p;
m_Direction = nDirection;
m_pInsertionOrderCurrent = 0;
m_pLookAhead =0;
m_strTreeStack.RemoveAll();
m_strFrameLocStack.RemoveAll();
m_strTreeStack.AddLast(m_pTree->m_root);
m_strFrameLocStack.AddLast((void *)0);
}
// supply a tree, or reset() this iterator before using it.
GBTreeIterator::GBTreeIterator(GBTree *p, int nDirection)
{
m_pTree = p;
m_Direction = nDirection;
m_pInsertionOrderCurrent = 0;
m_pLookAhead =0;
if (m_pTree)
{
m_strTreeStack.AddLast(m_pTree->m_root);
m_strFrameLocStack.AddLast((void *)0);
}
}
int GBTreeIterator::operator () (void)
{
if (m_pLookAhead)
return 1;
else
m_pLookAhead = (*this)++;
return (m_pLookAhead == 0) ? 0 : 1;
}
// stacked recursion
void * GBTreeIterator::operator ++ (int)
{
if (m_pLookAhead)
{
void *pRet = m_pLookAhead;
m_pLookAhead = 0;
return pRet;
}
if (m_Direction == 2 )
{
if (!m_pInsertionOrderCurrent)
m_pInsertionOrderCurrent = m_pTree->m_First;
else
m_pInsertionOrderCurrent = m_pInsertionOrderCurrent->m_Next;
return (m_pInsertionOrderCurrent) ? m_pInsertionOrderCurrent->m_dataNode : 0;
}
// load the current GBTreeStruct for this stack frame
GBTree::GBTreeStruct *btRoot = (GBTree::GBTreeStruct *)m_strTreeStack.Last();
if (!btRoot)
return 0;
// load the integer that tells us where to start or resume this stack frame
union CAST_THIS_TYPE_SAFE_COMPILERS
{
void * mbrVoid;
unsigned int mbrInt;
}Member;
Member.mbrVoid = m_strFrameLocStack.Last();
switch (Member.mbrInt)
{
case 1: goto LOCATION1;
case 2: goto LOCATION2;
case 3: goto LOCATION3;
case 4: goto LOCATION4;
}
LOCATION1:
// Move either Left or Right down the tree depending on [Pos.m_Direction]
if (m_Direction != 0)
{
if( btRoot->m_leftPtr )
{
m_strFrameLocStack.RemoveLast(); // update the frame position location
m_strFrameLocStack.AddLast((void *)2);
m_strTreeStack.AddLast(btRoot->m_leftPtr); // prepare the next frame
m_strFrameLocStack.AddLast((void *)1);
return (*this)++; // load the next frame
}
}
else
{
if( btRoot->m_rightPtr )
{
m_strFrameLocStack.RemoveLast(); // update the frame position location
m_strFrameLocStack.AddLast((void *)2);
m_strTreeStack.AddLast(btRoot->m_rightPtr);// prepare the next frame
m_strFrameLocStack.AddLast((void *)1);
return (*this)++; // load the next frame
}
}
LOCATION2:
if (m_Direction == 1 || m_Direction == 0)
{
m_strFrameLocStack.RemoveLast(); // update the frame position location
m_strFrameLocStack.AddLast((void *)3);
return btRoot->m_dataNode; // unwind all frames, return the result
}
LOCATION3:
// Move either Left or Right down the tree depending on [Pos.m_Direction]
if (m_Direction != 0)
{
if( btRoot->m_rightPtr )
{
m_strFrameLocStack.RemoveLast(); // same as above, but opposite direction
m_strFrameLocStack.AddLast((void *)4);
m_strTreeStack.AddLast(btRoot->m_rightPtr);
m_strFrameLocStack.AddLast((void *)1);
return (*this)++;
}
}
else
{
if( btRoot->m_leftPtr )
{
m_strFrameLocStack.RemoveLast();
m_strFrameLocStack.AddLast((void *)4);
m_strTreeStack.AddLast(btRoot->m_leftPtr);
m_strFrameLocStack.AddLast((void *)1);
return (*this)++;
}
}
LOCATION4:
// pop this frame, and resume the previous frame in it's last state
m_strTreeStack.RemoveLast();
m_strFrameLocStack.RemoveLast();
return (*this)++;
}
Submit an article or tip