214 lines
4.1 KiB
C++
214 lines
4.1 KiB
C++
//+---------------------------------------------------------------------------
|
|
//
|
|
// Microsoft Windows
|
|
// Copyright (C) Microsoft Corporation, 1994 - 1995.
|
|
//
|
|
// File: avl.hxx
|
|
//
|
|
// Contents:
|
|
//
|
|
// Classes:
|
|
//
|
|
// Functions:
|
|
//
|
|
// History: 6/25/1995 RaviR Created
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
|
|
#ifndef _AVL_HXX_
|
|
#define _AVL_HXX_
|
|
|
|
|
|
//----------------------------------------------------------------------------
|
|
//
|
|
// Class: CAVLNodeAtom
|
|
//
|
|
// History: 6/29/1995 RaviR Created
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
class CAVLNodeAtom;
|
|
typedef CAVLNodeAtom * PAVLNODEATOM;
|
|
|
|
class CAVLNodeAtom
|
|
{
|
|
public:
|
|
CAVLNodeAtom() {;}
|
|
|
|
virtual ~CAVLNodeAtom() {;}
|
|
|
|
virtual int Compare(CAVLNodeAtom *pCAVLNodeAtom) = 0;
|
|
|
|
#if (DBG == 1)
|
|
virtual void Dump(void) {;}
|
|
#endif
|
|
|
|
};
|
|
|
|
|
|
//----------------------------------------------------------------------------
|
|
//
|
|
// Class: CTreeNode
|
|
//
|
|
// History: 8/29/1995 RaviR Created
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
class CTreeNode
|
|
{
|
|
public:
|
|
|
|
CTreeNode(PAVLNODEATOM pa)
|
|
: _l(NULL), _r(NULL), _p(NULL), _pa(pa), _b(0), _flag(0) {;}
|
|
|
|
~CTreeNode()
|
|
{
|
|
delete _pa;
|
|
delete _l;
|
|
delete _r;
|
|
}
|
|
|
|
PAVLNODEATOM Atom(void) { return _pa; }
|
|
char Balance(void) { return _b; }
|
|
CTreeNode * Left(void) { return _l; }
|
|
CTreeNode * Right(void) { return _r; }
|
|
CTreeNode * Parent(void) { return _p; }
|
|
|
|
|
|
void SetAtom(PAVLNODEATOM pa) { _pa = pa; }
|
|
void SetBalance(char b) { _b = b; }
|
|
void SetLeft(CTreeNode *l) { _l = l; if (l) l->_p = this; }
|
|
void SetRight(CTreeNode *r) { _r = r; if (r) r->_p = this; }
|
|
void SetParent(CTreeNode *p) { _p = p; }
|
|
|
|
PAVLNODEATOM GetMin(void); // Methods reqd for Delete
|
|
PAVLNODEATOM GetMax(void); // Methods reqd for Delete
|
|
|
|
|
|
#if (DBG == 1)
|
|
void Dump(void);
|
|
#endif
|
|
|
|
CTreeNode * _l; // left child
|
|
CTreeNode * _r; // right child
|
|
CTreeNode * _p; // parent
|
|
|
|
PAVLNODEATOM _pa; // ptr to atom
|
|
|
|
char _b; // balance
|
|
BYTE _flag; // flag used by CAVLTree::GetFirst & CAVLTree::GetNext
|
|
|
|
BOOL IsTraversed(void) { return _flag; }
|
|
void SetTraversed(void) { _flag = TRUE; }
|
|
|
|
void ResetTraversedFlag(void)
|
|
{
|
|
_flag = FALSE;
|
|
|
|
if (_l != NULL)
|
|
{
|
|
_l->ResetTraversedFlag();
|
|
}
|
|
if (_r != NULL)
|
|
{
|
|
_r->ResetTraversedFlag();
|
|
}
|
|
}
|
|
|
|
}; // class CTreeNode
|
|
|
|
|
|
inline
|
|
PAVLNODEATOM
|
|
CTreeNode::GetMin(void)
|
|
{
|
|
CTreeNode * ptn = this;
|
|
|
|
while (ptn->Left() != NULL)
|
|
{
|
|
ptn = ptn->Left();
|
|
}
|
|
|
|
return ptn->Atom();
|
|
}
|
|
|
|
inline
|
|
PAVLNODEATOM
|
|
CTreeNode::GetMax(void)
|
|
{
|
|
CTreeNode * ptn = this;
|
|
|
|
while (ptn->Right() != NULL)
|
|
{
|
|
ptn = ptn->Right();
|
|
}
|
|
|
|
return ptn->Atom();
|
|
}
|
|
|
|
|
|
//----------------------------------------------------------------------------
|
|
//
|
|
// Class: CAVLTree
|
|
//
|
|
// History: 8/29/1995 RaviR Created
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
|
|
class CAVLTree
|
|
{
|
|
public:
|
|
CAVLTree(void)
|
|
: _pFirstNode(NULL),
|
|
_pCurrentNode(NULL) {;}
|
|
|
|
virtual ~CAVLTree()
|
|
{
|
|
delete _pFirstNode;
|
|
}
|
|
|
|
HRESULT Insert(PAVLNODEATOM pa);
|
|
|
|
PAVLNODEATOM GetAtom(PAVLNODEATOM pa);
|
|
|
|
PAVLNODEATOM GetFirst(void);
|
|
|
|
PAVLNODEATOM GetNext(void);
|
|
|
|
void Clear(void)
|
|
{
|
|
if (_pFirstNode != NULL)
|
|
{
|
|
delete _pFirstNode;
|
|
_pFirstNode = NULL;
|
|
}
|
|
}
|
|
|
|
void Delete(PAVLNODEATOM pa);
|
|
|
|
#if (DBG == 1)
|
|
void Dump(void);
|
|
#endif
|
|
|
|
private:
|
|
|
|
BOOL _Insert(CTreeNode ** ppNode, PAVLNODEATOM pa);
|
|
|
|
BOOL _Delete(CTreeNode ** ppNode, PAVLNODEATOM pa);
|
|
|
|
CTreeNode * _pFirstNode; // First node in the tree.
|
|
|
|
CTreeNode * _pCurrentNode; // used by getfirst getnext
|
|
|
|
HRESULT _hrInsert; // used by Insert & _Insert
|
|
|
|
}; // class CAVLTree
|
|
|
|
|
|
|
|
|
|
#endif // _AVL_HXX_
|
|
|