957 lines
22 KiB
C++
957 lines
22 KiB
C++
/*************************************************************************/
|
|
/* File : XBinaryTree.h */
|
|
/* Author : Aymeric Bard */
|
|
/* */
|
|
/* Virtools SDK */
|
|
/* Copyright (c) Virtools 2000, All Rights Reserved. */
|
|
/*************************************************************************/
|
|
#ifndef BINARYTREE_H
|
|
|
|
#define BINARYTREE_H
|
|
|
|
|
|
#include "XUtil.h"
|
|
|
|
|
|
|
|
template <class T>
|
|
class Compare
|
|
{
|
|
public:
|
|
bool operator() (const T& iT1,const T& iT2) const {return (iT1 < iT2);}
|
|
};
|
|
|
|
/************************************************
|
|
Summary: Not Yet Documented
|
|
|
|
|
|
************************************************/
|
|
template <class T, class TCmpFunc = Compare<T>, bool TMulti = true>
|
|
class XBTree
|
|
{
|
|
public:
|
|
typedef T Type;
|
|
typedef T* Pointer;
|
|
typedef T& Reference;
|
|
typedef const T& ConstReference;
|
|
|
|
protected:
|
|
enum Color {RED, BLACK};
|
|
|
|
struct Node
|
|
{
|
|
Node* parent;
|
|
Node* left;
|
|
Node* right;
|
|
Color color;
|
|
T value;
|
|
};
|
|
|
|
public:
|
|
class Iterator;
|
|
|
|
// Const iterator
|
|
class ConstIterator
|
|
{
|
|
public:
|
|
ConstIterator(){}
|
|
ConstIterator ( Node* iP):m_Node(iP) {}
|
|
ConstIterator(const Iterator& iCopy)
|
|
: m_Node(iCopy.m_Node) {}
|
|
ConstReference operator*() const
|
|
{return m_Node->value; }
|
|
Type* operator->() const
|
|
{return &m_Node->value; }
|
|
ConstIterator& operator++()
|
|
{XInc();
|
|
return (*this); }
|
|
ConstIterator operator++(int)
|
|
{ConstIterator _Tmp = *this;
|
|
++*this;
|
|
return (_Tmp); }
|
|
ConstIterator& operator--()
|
|
{XDec();
|
|
return (*this); }
|
|
ConstIterator operator--(int)
|
|
{ConstIterator _Tmp = *this;
|
|
--*this;
|
|
return (_Tmp); }
|
|
bool operator==(const ConstIterator& iX) const
|
|
{return (m_Node == iX.m_Node); }
|
|
bool operator!=(const ConstIterator& iX) const
|
|
{return (!(*this == iX)); }
|
|
protected:
|
|
void XDec()
|
|
{
|
|
if (m_Node->color == RED && XParent(m_Node->parent) == m_Node) {
|
|
m_Node = m_Node->right;
|
|
} else {
|
|
if (m_Node->left != m_Nil) {
|
|
m_Node = XMax(m_Node->left);
|
|
} else {
|
|
Node* n;
|
|
while (m_Node == XLeft(n = m_Node->parent))
|
|
m_Node = n;
|
|
m_Node = n;
|
|
}
|
|
}
|
|
}
|
|
void XInc()
|
|
{
|
|
if (m_Node->right != m_Nil) {
|
|
m_Node = XMin(m_Node->right);
|
|
} else {
|
|
Node* n;
|
|
while (m_Node == XRight(n = m_Node->parent))
|
|
m_Node = n;
|
|
|
|
if (m_Node->right != n) {
|
|
m_Node = n;
|
|
}
|
|
}
|
|
}
|
|
|
|
Node* m_Node;
|
|
};
|
|
friend class ConstIterator;
|
|
|
|
// Non-Const Iterator
|
|
class Iterator : public ConstIterator
|
|
{
|
|
public:
|
|
Iterator() {}
|
|
Iterator(Node* iNode) : ConstIterator(iNode) {}
|
|
Reference operator*() const {return this->m_Node->value;}
|
|
Iterator& operator++() {
|
|
this->XInc();
|
|
return (*this);
|
|
}
|
|
Iterator operator++(int) {
|
|
Iterator _Tmp = *this;
|
|
++*this;
|
|
return (_Tmp);
|
|
}
|
|
Iterator& operator--() {
|
|
this->XDec();
|
|
return (*this);
|
|
}
|
|
Iterator operator--(int) {
|
|
Iterator _Tmp = *this;
|
|
--*this;
|
|
return (_Tmp);
|
|
}
|
|
bool operator==(const Iterator& iA) const
|
|
{return (this->m_Node == iA.m_Node); }
|
|
bool operator!=(const Iterator& iA) const
|
|
{return (!(*this == iA)); }
|
|
|
|
};
|
|
friend class Iterator;
|
|
|
|
///
|
|
// Methods
|
|
|
|
explicit XBTree(const TCmpFunc& iCmp = TCmpFunc()):m_KeyCompare(iCmp)
|
|
{
|
|
XInit();
|
|
}
|
|
XBTree(const XBTree& iModel):m_KeyCompare(iModel.m_KeyCompare)
|
|
{
|
|
XInit();
|
|
XCopy(iModel);
|
|
}
|
|
~XBTree()
|
|
{
|
|
Erase(Begin(), End());
|
|
XFreeNode(m_Head);
|
|
|
|
// Nil Node management
|
|
// TODO : thread safe ? -> lock resource
|
|
if (--m_NilRefCount == 0) {
|
|
XFreeNode(m_Nil);
|
|
m_Nil = 0;
|
|
}
|
|
}
|
|
|
|
const XBTree& operator = (const XBTree& iModel)
|
|
{
|
|
if (this != &iModel) {
|
|
Erase(Begin(), End());
|
|
m_KeyCompare = iModel.m_KeyCompare;
|
|
XCopy(iModel);
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
/************************************************
|
|
Summary: Returns an iterator on the first element.
|
|
************************************************/
|
|
Iterator Begin() {return Iterator(this->XLMost());}
|
|
/************************************************
|
|
Summary: Returns an iterator after the last element.
|
|
************************************************/
|
|
Iterator End() {return Iterator(m_Head); }
|
|
|
|
/************************************************
|
|
Summary: Returns a const iterator on the first element.
|
|
************************************************/
|
|
ConstIterator Begin() const {return Iterator(this->XLmost());}
|
|
/************************************************
|
|
Summary: Returns a const iterator after the last element.
|
|
************************************************/
|
|
ConstIterator End() const {return ConstIterator(m_Head); }
|
|
|
|
/************************************************
|
|
Summary: Returns an iterator on the first
|
|
element for a reverse iteration.
|
|
************************************************/
|
|
Iterator RBegin() {return (Size())?Iterator(--End()):Iterator(m_Nil);}
|
|
/************************************************
|
|
Summary: Returns a const iterator after the last
|
|
element for a reverse iteration.
|
|
************************************************/
|
|
Iterator REnd() {return (Size()>1)?Iterator(--Begin()):Iterator(--(--(Begin()))); }
|
|
|
|
/************************************************
|
|
Summary: Returns a const iterator on the first
|
|
element for a reverse iteration.
|
|
************************************************/
|
|
ConstIterator RBegin() const {return ConstIterator(End());}
|
|
/************************************************
|
|
Summary: Returns a const iterator after the last
|
|
element for a reverse iteration.
|
|
************************************************/
|
|
ConstIterator REnd() const {return ConstIterator(Begin()); }
|
|
|
|
/************************************************
|
|
Summary: Returns the elements number.
|
|
************************************************/
|
|
unsigned int Size() const {return m_Size; }
|
|
|
|
|
|
Iterator Insert(Iterator iT, ConstReference iValue)
|
|
{
|
|
if (Size() == 0)
|
|
;
|
|
else if (iT == Begin()) {
|
|
if (m_KeyCompare(iValue, iT.m_Node->value))
|
|
return (XInsert(m_Head, iT.m_Node, iValue));
|
|
} else if (iT == End()) {
|
|
if (m_KeyCompare(XValue(XRMost()), iValue))
|
|
return XInsert(m_Nil, XRMost(), iValue);
|
|
} else {
|
|
Iterator i = iT;
|
|
if (m_KeyCompare((--i).m_Node->value, iValue) && m_KeyCompare(iValue, iT.m_Node->value)) {
|
|
if (i.m_Node->right == m_Nil)
|
|
return XInsert(m_Nil, i.m_Node, iValue);
|
|
else
|
|
return XInsert(m_Head, iT.m_Node, iValue);
|
|
}
|
|
}
|
|
return Insert(iValue);
|
|
}
|
|
|
|
Iterator Insert(ConstReference iValue)
|
|
{
|
|
Node* n = XRoot();
|
|
Node* nodeBefore = m_Head;
|
|
bool ans = true;
|
|
while (n != m_Nil) {
|
|
nodeBefore = n;
|
|
ans = m_KeyCompare(iValue,n->value);
|
|
n = ans ? n->left : n->right;
|
|
}
|
|
|
|
if (TMulti) return XInsert(n,nodeBefore, iValue);
|
|
Iterator it = Iterator(nodeBefore);
|
|
if (!ans)
|
|
;
|
|
else if (it == Begin())
|
|
return XInsert(n, nodeBefore, iValue);
|
|
else
|
|
--it;
|
|
if (m_KeyCompare(*it, iValue))
|
|
return XInsert(n, nodeBefore, iValue);
|
|
|
|
// already in the tree... maybe do a pair ????
|
|
return it;
|
|
}
|
|
|
|
Iterator PushBack(ConstReference iValue) {return Insert(iValue);}
|
|
|
|
Iterator Erase(Iterator iT)
|
|
{
|
|
Node* x;
|
|
Node* y = (iT++).m_Node;
|
|
Node* z = y;
|
|
if (XLeft(y) == m_Nil) x = XRight(y);
|
|
else if (XRight(y) == m_Nil) x = XLeft(y);
|
|
else y = XMin(XRight(y)), x = XRight(y);
|
|
|
|
{
|
|
// _Lockit _Lk;
|
|
if (y != z) {
|
|
XParent(XLeft(z)) = y;
|
|
XLeft(y) = XLeft(z);
|
|
if (y == XRight(z)) XParent(x) = y;
|
|
else {
|
|
XParent(x) = XParent(y);
|
|
XLeft(XParent(y)) = x;
|
|
XRight(y) = XRight(z);
|
|
XParent(XRight(z)) = y;
|
|
}
|
|
if (XRoot() == z) {
|
|
XRoot() = y;
|
|
} else {
|
|
if (XLeft(XParent(z)) == z) XLeft(XParent(z)) = y;
|
|
else XRight(XParent(z)) = y;
|
|
}
|
|
XParent(y) = XParent(z);
|
|
XSwap(XColor(y), XColor(z));
|
|
y = z;
|
|
} else {
|
|
XParent(x) = XParent(y);
|
|
if (XRoot() == z) {
|
|
XRoot() = x;
|
|
} else {
|
|
if (XLeft(XParent(z)) == z) {
|
|
XLeft(XParent(z)) = x;
|
|
} else {
|
|
XRight(XParent(z)) = x;
|
|
}
|
|
}
|
|
if (XLMost() != z) ;
|
|
else {
|
|
if (XRight(z) == m_Nil) {
|
|
XLMost() = XParent(z);
|
|
} else {
|
|
XLMost() = XMin(x);
|
|
}
|
|
}
|
|
|
|
if (XRMost() != z) ;
|
|
else {
|
|
if (XLeft(z) == m_Nil) {
|
|
XRMost() = XParent(z);
|
|
} else {
|
|
XRMost() = XMax(x);
|
|
}
|
|
}
|
|
}
|
|
if (XColor(y) == BLACK) {
|
|
while (x != XRoot() && XColor(x) == BLACK) {
|
|
if (x == XLeft(XParent(x))) {
|
|
Node* _W = XRight(XParent(x));
|
|
if (XColor(_W) == RED) {
|
|
XColor(_W) = BLACK;
|
|
XColor(XParent(x)) = RED;
|
|
XLRotate(XParent(x));
|
|
_W = XRight(XParent(x));
|
|
}
|
|
if (XColor(XLeft(_W)) == BLACK && XColor(XRight(_W)) == BLACK) {
|
|
XColor(_W) = RED;
|
|
x = XParent(x);
|
|
} else {
|
|
if (XColor(XRight(_W)) == BLACK) {
|
|
XColor(XLeft(_W)) = BLACK;
|
|
XColor(_W) = RED;
|
|
XRRotate(_W);_W = XRight(XParent(x));
|
|
}
|
|
XColor(_W) = XColor(XParent(x));
|
|
XColor(XParent(x)) = BLACK;
|
|
XColor(XRight(_W)) = BLACK;
|
|
XLRotate(XParent(x));
|
|
break;
|
|
}
|
|
} else {
|
|
Node* _W = XLeft(XParent(x));
|
|
if (XColor(_W) == RED) {
|
|
XColor(_W) = BLACK;
|
|
XColor(XParent(x)) = RED;
|
|
XRRotate(XParent(x));
|
|
_W = XLeft(XParent(x));
|
|
}
|
|
if (XColor(XRight(_W)) == BLACK && XColor(XLeft(_W)) == BLACK) {
|
|
XColor(_W) = RED;
|
|
x = XParent(x);
|
|
} else {
|
|
if (XColor(XLeft(_W)) == BLACK) {
|
|
XColor(XRight(_W)) = BLACK;
|
|
XColor(_W) = RED;
|
|
XLRotate(_W);
|
|
_W = XLeft(XParent(x));
|
|
}
|
|
XColor(_W) = XColor(XParent(x));
|
|
XColor(XParent(x)) = BLACK;
|
|
XColor(XLeft(_W)) = BLACK;
|
|
XRRotate(XParent(x));
|
|
break;
|
|
}
|
|
}
|
|
XColor(x) = BLACK;
|
|
}
|
|
}
|
|
}
|
|
XDestval(&XValue(y));
|
|
XFreeNode(y);
|
|
--m_Size;
|
|
return (iT);
|
|
}
|
|
Iterator Erase(Iterator iFirst, Iterator iLast)
|
|
{
|
|
if (Size() == 0 || iFirst != Begin() || iLast != End()) {
|
|
while (iFirst != iLast) {
|
|
Erase(iFirst++);
|
|
}
|
|
return iFirst;
|
|
} else {
|
|
XErase(XRoot());
|
|
XRoot() = m_Nil;
|
|
m_Size = 0;
|
|
XLMost() = m_Head;
|
|
XRMost() = m_Head;
|
|
return Begin();
|
|
}
|
|
}
|
|
void Clear() {
|
|
Erase(Begin(), End());
|
|
}
|
|
Iterator Find(ConstReference iValue) {
|
|
Iterator i(XLBound(iValue));
|
|
return ((i == End() || m_KeyCompare(iValue, i.m_Node->value))? End() : i);
|
|
}
|
|
ConstIterator Find(ConstReference iValue) const {
|
|
ConstIterator i(XLBound(iValue));
|
|
return ((i == End() || m_KeyCompare(iValue, i.m_Node->value))? End() : i);
|
|
}
|
|
|
|
void Swap(XBTree& iTree)
|
|
{
|
|
Swap(m_KeyCompare, iTree.m_KeyCompare);
|
|
if (this->m_Allocator == iTree.m_Allocator) {
|
|
Swap(m_Head, iTree.m_Head);
|
|
Swap(m_Size, iTree.m_Size);
|
|
} else {
|
|
XBTree _Ts = *this;
|
|
*this = iTree;
|
|
iTree = _Ts;
|
|
}
|
|
}
|
|
|
|
protected:
|
|
|
|
static Node*& XLeft(Node* iNode) {return ((Node*&)(*iNode).left); }
|
|
static Node*& XParent(Node* iNode) {return ((Node*&)(*iNode).parent); }
|
|
static Node*& XRight(Node* iNode) {return iNode->right; }
|
|
static Color& XColor(Node* iNode) {return iNode->color; }
|
|
static Reference XValue(Node* iNode){return ((Reference)(*iNode).value); }
|
|
|
|
static Node* XMax(Node* iN) {while (iN->right != m_Nil) iN = iN->right; return iN; }
|
|
static Node* XMin(Node* iN) {while (iN->left != m_Nil) iN = iN->left; return iN; }
|
|
|
|
Node*& XRoot() const {return m_Head->parent;}
|
|
Node*& XRMost() const {return m_Head->right;}
|
|
Node*& XLMost() const {return m_Head->left;}
|
|
|
|
void XLRotate(Node* iN) {
|
|
Node* y = iN->right;
|
|
iN->right = y->left;
|
|
if (y->left != m_Nil) XParent(y->left) = iN;
|
|
y->parent = iN->parent;
|
|
if (iN == XRoot()) {
|
|
XRoot() = y;
|
|
} else {
|
|
if (iN == XLeft(iN->parent)) {
|
|
XLeft(iN->parent) = y;
|
|
} else {
|
|
XRight(iN->parent) = y;
|
|
}
|
|
}
|
|
y->left = iN;
|
|
iN->parent = y;
|
|
}
|
|
|
|
void XRRotate(Node* iN) {
|
|
Node* y = iN->left;
|
|
iN->left = y->right;
|
|
if (y->right != m_Nil) XParent(y->right) = iN;
|
|
y->parent = iN->parent;
|
|
if (iN == XRoot()) XRoot() = y;
|
|
else if (iN == XRight(iN->parent))
|
|
XRight(iN->parent) = y;
|
|
else
|
|
XLeft(iN->parent) = y;
|
|
y->right = iN;
|
|
iN->parent = y;
|
|
}
|
|
|
|
Node* XLBound(ConstReference iValue) const
|
|
{
|
|
Node* x = XRoot();
|
|
Node* y = m_Head;
|
|
while (x != m_Nil) {
|
|
if (m_KeyCompare(x->value, iValue)) {
|
|
x = x->right;
|
|
} else {
|
|
y = x;
|
|
x = x->left;
|
|
}
|
|
}
|
|
return (y);
|
|
}
|
|
|
|
Node* XUBound(ConstReference iValue) const
|
|
{
|
|
Node* x = XRoot();
|
|
Node* y = m_Head;
|
|
while (x != m_Nil) {
|
|
if (m_KeyCompare(iValue, x->value)) {
|
|
y = x, x = x->left;
|
|
} else {
|
|
x = x->right;
|
|
}
|
|
}
|
|
return (y);
|
|
}
|
|
|
|
void XInit()
|
|
{
|
|
Node* tmp = XBuynode(0, BLACK);
|
|
{
|
|
// _Lockit _Lk; :: TODO Thread locking
|
|
if (m_Nil == 0) {
|
|
m_Nil = tmp;
|
|
tmp = 0;
|
|
m_Nil->left = 0;
|
|
m_Nil->right = 0;
|
|
}
|
|
++m_NilRefCount;
|
|
}
|
|
if (tmp != 0) {
|
|
XFreeNode(tmp);
|
|
}
|
|
m_Head = XBuynode(m_Nil, RED);
|
|
m_Size = 0;
|
|
XLMost() = m_Head;
|
|
XRMost() = m_Head;
|
|
}
|
|
|
|
void XErase(Node* iNode)
|
|
{
|
|
for (Node* n = iNode; n != m_Nil; iNode = n) {
|
|
XErase(n->right);
|
|
n = n->left;
|
|
XDestval(&XValue(iNode));
|
|
XFreeNode(iNode);
|
|
}
|
|
}
|
|
|
|
Iterator XInsert(Node* iNode, Node* iBefore, ConstReference iValue)
|
|
{
|
|
Node* z = XBuynode(iBefore, RED);
|
|
z->left = m_Nil;
|
|
z->right= m_Nil;
|
|
XConsval(&z->value, iValue);
|
|
++m_Size;
|
|
if (iBefore == m_Head || iNode != m_Nil || m_KeyCompare(iValue, iBefore->value)) {
|
|
iBefore->left = z;
|
|
if (iBefore == m_Head) {
|
|
XRoot() = z;
|
|
XRMost() = z;
|
|
} else {
|
|
if (iBefore == XLMost()) XLMost() = z;
|
|
}
|
|
} else {
|
|
iBefore->right = z;
|
|
if (iBefore == XRMost()) XRMost() = z;
|
|
}
|
|
for (iNode = z; iNode != XRoot() && XColor(iNode->parent) == RED; ) {
|
|
if (iNode->parent == XLeft(XParent(iNode->parent))) {
|
|
iBefore = XRight(XParent(iNode->parent));
|
|
if (iBefore->color == RED) {
|
|
XColor(iNode->parent) = BLACK;
|
|
iBefore->color = BLACK;
|
|
XColor(XParent(iNode->parent)) = RED;
|
|
iNode = XParent(iNode->parent);
|
|
} else {
|
|
if (iNode == XRight(iNode->parent)) {
|
|
iNode = iNode->parent;
|
|
XLRotate(iNode);
|
|
}
|
|
XColor(iNode->parent) = BLACK;
|
|
XColor(XParent(iNode->parent)) = RED;
|
|
XRRotate(XParent(iNode->parent));
|
|
}
|
|
} else {
|
|
iBefore = XLeft(XParent(iNode->parent));
|
|
if (iBefore->color == RED) {
|
|
XColor(iNode->parent) = BLACK;
|
|
iBefore->color = BLACK;
|
|
XColor(XParent(iNode->parent)) = RED;
|
|
iNode = XParent(iNode->parent);
|
|
} else {
|
|
if (iNode == XLeft(iNode->parent)) {
|
|
iNode = iNode->parent;
|
|
XRRotate(iNode);
|
|
}
|
|
XColor(iNode->parent) = BLACK;
|
|
XColor(XParent(iNode->parent)) = RED;
|
|
XLRotate(XParent(iNode->parent));
|
|
}
|
|
}
|
|
}
|
|
XColor(XRoot()) = BLACK;
|
|
return Iterator(z);
|
|
}
|
|
|
|
//
|
|
// (De)Allocation methods
|
|
|
|
Node* XBuynode(Node* iParent, Color iColor) {
|
|
Node* n = new Node;
|
|
n->parent = iParent;
|
|
n->color = iColor;
|
|
return n;
|
|
}
|
|
// Construction by placement new
|
|
void XConsval(Pointer iP, ConstReference iValue) {new ((void*)iP) T(iValue); }
|
|
void XDestval(Pointer iP) {(iP)->~T(); }
|
|
void XFreeNode(Node* iN) {delete iN;}
|
|
|
|
|
|
// Null reference
|
|
static Node* m_Nil;
|
|
static int m_NilRefCount;
|
|
|
|
TCmpFunc m_KeyCompare;
|
|
Node* m_Head;
|
|
unsigned int m_Size;
|
|
|
|
|
|
};
|
|
|
|
template <class T, class TCmpFunc, bool TMulti>
|
|
typename XBTree<T,TCmpFunc,TMulti>::Node* XBTree<T,TCmpFunc,TMulti>::m_Nil = 0;
|
|
|
|
template <class T, class TCmpFunc, bool TMulti>
|
|
int XBTree<T,TCmpFunc,TMulti>::m_NilRefCount = 0;
|
|
|
|
/************************************************
|
|
Summary: Not Yet Documented
|
|
|
|
|
|
************************************************/
|
|
template <class T>
|
|
class XBinaryTreeNode
|
|
{
|
|
public:
|
|
// Ctors
|
|
XBinaryTreeNode() : m_Left(NULL),m_Right(NULL){}
|
|
XBinaryTreeNode( const T & E ) : m_Data( E ), m_Left( NULL ),m_Right( NULL ) { }
|
|
XBinaryTreeNode( const T & E,XBinaryTreeNode* L, XBinaryTreeNode* R ):m_Data(E),m_Left(L),m_Right(R) { }
|
|
// Dtor
|
|
~XBinaryTreeNode() {}
|
|
|
|
///
|
|
// Members
|
|
|
|
// Data
|
|
T m_Data;
|
|
// Children
|
|
XBinaryTreeNode* m_Left;
|
|
XBinaryTreeNode* m_Right;
|
|
};
|
|
|
|
template <class T>
|
|
class XBinaryTree;
|
|
|
|
|
|
/************************************************
|
|
Summary: Not Yet Documented
|
|
|
|
|
|
************************************************/
|
|
template <class T>
|
|
class XBinaryTreeIt
|
|
{
|
|
typedef XBinaryTreeNode<T> tNode;
|
|
typedef XBinaryTree<T>* tTree;
|
|
typedef XBinaryTreeIt<T> tIterator;
|
|
public:
|
|
// Ctors
|
|
XBinaryTreeIt(const tNode* n, const tTree tree) : m_Tree(tree),m_Node(n){}
|
|
XBinaryTreeIt(tNode* n=NULL):m_Node(n) {}
|
|
// Dtor
|
|
~XBinaryTreeIt() {}
|
|
|
|
// Operators
|
|
int operator==(const tIterator& it) const { return m_Node == it.m_Node; }
|
|
int operator!=(const tIterator& it) const { return m_Node != it.m_Node; }
|
|
|
|
const T& operator*() { return (*m_Node).m_Data; }
|
|
// T* operator*() { return &(m_Node->m_Data); }
|
|
|
|
tIterator& operator++() { // Prefixe
|
|
// TODO
|
|
return *this;
|
|
}
|
|
tIterator operator++(int) {
|
|
tIterator tmp = *this;
|
|
++*this;
|
|
return tmp;
|
|
}
|
|
|
|
///
|
|
// Members
|
|
|
|
// The Binary Tree
|
|
tTree m_Tree;
|
|
// Current Node
|
|
tNode* m_Node;
|
|
|
|
};
|
|
|
|
/************************************************
|
|
Summary: Not Yet Documented
|
|
|
|
|
|
************************************************/
|
|
template <class T>
|
|
class XBinaryTree
|
|
{
|
|
typedef XBinaryTreeIt<T> tIterator;
|
|
typedef XBinaryTreeNode<T> tNode;
|
|
friend class XBinaryTreeIt<T>;
|
|
public:
|
|
XBinaryTree()
|
|
{
|
|
m_Root = m_NullNode = new tNode;
|
|
}
|
|
|
|
~XBinaryTree()
|
|
{
|
|
XRemove(m_Root);
|
|
delete m_NullNode;
|
|
}
|
|
|
|
void Clear()
|
|
{
|
|
XRemove(m_Root);
|
|
m_Root = m_NullNode;
|
|
}
|
|
|
|
int GetMemoryOccupation() const
|
|
{
|
|
// Childs + this + NullNode
|
|
return XMemory(m_Root) + sizeof(XBinaryTree<T>) + sizeof(tNode);
|
|
}
|
|
|
|
tIterator Begin() const
|
|
{
|
|
return End();
|
|
|
|
}
|
|
|
|
tIterator End() const
|
|
{
|
|
return tIterator(m_NullNode);
|
|
}
|
|
|
|
// Infixed iteration
|
|
void Iterate(void(*f)(const T&,void *),void* arg = NULL) const {
|
|
XInfixe(m_Root,f,arg);
|
|
}
|
|
|
|
// Postfixed iteration
|
|
void BackIterate(void(*f)(const T&,void *),void* arg = NULL) const {
|
|
XPostfixe(m_Root,f,arg);
|
|
}
|
|
|
|
// Prefixed iteration
|
|
void Prefixe(void(*f)(const T&,void *),void* arg = NULL) const {
|
|
XPrefixe(m_Root,f,arg);
|
|
}
|
|
|
|
static
|
|
int XCompare(const void *elem1, const void *elem2 )
|
|
{
|
|
return (*(T*)elem2 - *(T*)elem1);
|
|
}
|
|
|
|
// Get The Smallest element
|
|
T GetSmallest() const
|
|
{
|
|
if (m_Root == m_NullNode) return (T)0;
|
|
return XGetSmallest(m_Root);
|
|
}
|
|
|
|
// Insert an element in the tree (return 0 if it was already there)
|
|
int Insert(const T& o,VxSortFunc compare = XCompare)
|
|
{
|
|
m_NullNode->m_Data = o;
|
|
tNode** parent = &m_Root;
|
|
tNode* t = m_Root;
|
|
while(compare(&t->m_Data,&o) != 0) {
|
|
if(compare(&o,&t->m_Data)>0) {
|
|
parent = &t->m_Left;
|
|
t = t->m_Left;
|
|
} else {
|
|
parent = &t->m_Right;
|
|
t = t->m_Right;
|
|
}
|
|
}
|
|
// The value wasn't found, we insert it
|
|
if(t == m_NullNode) {
|
|
*parent = new tNode(o,m_NullNode,m_NullNode);;
|
|
return 1;
|
|
}
|
|
// already in the tree
|
|
return 0;
|
|
}
|
|
|
|
// Insert an element in the tree (return 0 if it was already there)
|
|
int Remove(const T& o,VxSortFunc compare = XCompare)
|
|
{
|
|
m_NullNode->m_Data = o;
|
|
tNode** parent = &m_Root;
|
|
tNode* t = m_Root;
|
|
while(compare(&t->m_Data,&o) != 0) {
|
|
if (compare(&o,&t->m_Data)>0) {
|
|
parent = &t->m_Left;
|
|
t = t->m_Left;
|
|
} else {
|
|
parent = &t->m_Right;
|
|
t = t->m_Right;
|
|
}
|
|
}
|
|
// The value was found, we remove it
|
|
if(t != m_NullNode) {
|
|
// No left child ?
|
|
if(t->m_Left == m_NullNode) {
|
|
// if it's a leaf ?
|
|
if (t->m_Right == m_NullNode) {
|
|
delete t;
|
|
*parent = m_NullNode;
|
|
} else { // we reup the right tree in place
|
|
*parent = t->m_Right;
|
|
delete t;
|
|
}
|
|
} else { // There's a left child
|
|
// No right Child
|
|
if (t->m_Right == m_NullNode) { // we reup the left tree in place
|
|
*parent = t->m_Left;
|
|
delete t;
|
|
} else { // we have to put the max of the left tree in place
|
|
tNode* left = t->m_Left;
|
|
parent = &t;
|
|
while(left->m_Right != m_NullNode) {
|
|
parent = &left;
|
|
left = left->m_Right;
|
|
}
|
|
*parent = left->m_Left;
|
|
t->m_Data = left->m_Data;
|
|
delete left;
|
|
}
|
|
}
|
|
return 1;
|
|
}
|
|
// already in the tree
|
|
return 0;
|
|
}
|
|
|
|
// Search an element in the tree
|
|
int Find(const T& o,VxSortFunc compare = XCompare) const
|
|
{
|
|
m_NullNode->m_Data = o;
|
|
tNode* t = m_Root;
|
|
while(compare(&t->m_Data,&o) != 0) {
|
|
if (compare(&o,&t->m_Data)>0) {
|
|
t = t->m_Left;
|
|
} else {
|
|
t = t->m_Right;
|
|
}
|
|
}
|
|
|
|
return t != m_NullNode;
|
|
}
|
|
|
|
// Search an element in the tree
|
|
T* FindPtr(const T& o,VxSortFunc compare = XCompare) const
|
|
{
|
|
m_NullNode->m_Data = o;
|
|
tNode* t = m_Root;
|
|
while(compare(&t->m_Data,&o) != 0) {
|
|
if (compare(&o,&t->m_Data)>0) {
|
|
t = t->m_Left;
|
|
} else {
|
|
t = t->m_Right;
|
|
}
|
|
}
|
|
|
|
return (t != m_NullNode) ? &t->m_Data : NULL;
|
|
}
|
|
|
|
private:
|
|
// Methods
|
|
void XRemove(tNode* t)
|
|
{
|
|
if( t != m_NullNode) {
|
|
XRemove( t->m_Left );
|
|
XRemove( t->m_Right );
|
|
delete t;
|
|
}
|
|
}
|
|
|
|
int XMemory(tNode* t)
|
|
{
|
|
|
|
if( t != m_NullNode) {
|
|
return XMemory( t->m_Left ) + XMemory( t->m_Right ) + sizeof(tNode);
|
|
} else return 0;
|
|
|
|
}
|
|
|
|
// Get The Smallest element
|
|
T XGetSmallest(tNode* t) const
|
|
{
|
|
if ((t->m_Left == m_NullNode) && (t->m_Right == m_NullNode)) return t->m_Data;
|
|
if (t->m_Left != m_NullNode) return XGetSmallest(t->m_Left);
|
|
if (t->m_Right!= m_NullNode) return XGetSmallest(t->m_Right);
|
|
return t->m_Data;
|
|
}
|
|
|
|
void XInfixe(tNode* t,void(*f)(const T&,void *),void* arg) const {
|
|
if( t != m_NullNode) {
|
|
XInfixe(t->m_Left,f,arg);
|
|
f(t->m_Data,arg);
|
|
XInfixe(t->m_Right,f,arg);
|
|
}
|
|
}
|
|
|
|
void XPrefixe(tNode* t,void(*f)(const T&,void *),void* arg) const {
|
|
if( t != m_NullNode) {
|
|
f(t->m_Data,arg);
|
|
XPrefixe(t->m_Left,f,arg);
|
|
XPrefixe(t->m_Right,f,arg);
|
|
}
|
|
}
|
|
|
|
void XPostfixe(tNode* t,void(*f)(const T&,void *),void* arg) const {
|
|
if( t != m_NullNode) {
|
|
XPostfixe(t->m_Right,f,arg);
|
|
f(t->m_Data,arg);
|
|
XPostfixe(t->m_Left,f,arg);
|
|
}
|
|
}
|
|
|
|
// Members
|
|
// Root
|
|
tNode* m_Root;
|
|
// Null Node
|
|
tNode* m_NullNode;
|
|
};
|
|
|
|
|
|
|
|
#endif // BINARYTREE_H
|