AVL tree/C++

From Rosetta Code

Code[edit]

 
// The set template is the primary class of AVL Trees.
// The system is set up to add templates including tree and map.
 
#include<iostream>
 
class treeException
{
public:
 
treeException() {}
};
 
class EntryAlreadyExistsException : public treeException
{
public:
EntryAlreadyExistsException() {}
};
 
class EntryNotFoundException : public treeException
{
public:
EntryNotFoundException() {}
};
 
class InvalidSetOperationException : public treeException
{
public:
InvalidSetOperationException() {}
};
 
class IsHeaderException : public treeException
{
public:
IsHeaderException() {}
};
 
struct State
{
enum
{
Header,
Balanced,
LeftHigh,
RightHigh
};
};
 
struct Node // Base Node Class for all Trees
{
Node* Left;
Node* Right;
Node* Parent;
char Balance;
 
Node()
{
Balance = State::Header;
Left = this;
Right = this;
Parent = 0;
}
 
Node(Node* ParentSet)
{
Balance = State::Balanced;
Left = 0;
Right = 0;
Parent = ParentSet;
}
 
bool IsHeader() const {return !Balance;}
};
 
struct Direction
{
enum {FromLeft, FromRight};
};
 
inline void SwapNodeReference(Node*& first, Node*& second)
{Node* temporary = first; first = second; second = temporary;}
 
void SwapNodes(Node* A, Node* B)
{
if (B == A->Left)
{
if (B->Left) B->Left->Parent = A;
if (B->Right) B->Right->Parent = A;
 
if (A->Right) A->Right->Parent = B;
 
if (!A->Parent->IsHeader())
{
if (A->Parent->Left == A)
A->Parent->Left = B;
else
A->Parent->Right = B;
}
else A->Parent->Parent = B;
 
B->Parent = A->Parent;
A->Parent = B;
 
A->Left = B->Left;
B->Left = A;
 
SwapNodeReference(A->Right,B->Right);
}
else if (B == A->Right)
{
if (B->Right) B->Right->Parent = A;
if (B->Left) B->Left->Parent = A;
 
if (A->Left) A->Left->Parent = B;
 
if (!A->Parent->IsHeader())
{
if (A->Parent->Left == A)
A->Parent->Left = B;
else
A->Parent->Right = B;
}
else A->Parent->Parent = B;
 
B->Parent = A->Parent;
A->Parent = B;
 
A->Right = B->Right;
B->Right = A;
 
SwapNodeReference(A->Left,B->Left);
}
else if (A == B->Left)
{
if (A->Left) A->Left->Parent = B;
if (A->Right) A->Right->Parent = B;
 
if (B->Right) B->Right->Parent = A;
 
if (!B->Parent->IsHeader())
{
if (B->Parent->Left == B)
B->Parent->Left = A;
else
B->Parent->Right = A;
}
else B->Parent->Parent = A;
 
A->Parent = B->Parent;
B->Parent = A;
 
B->Left = A->Left;
A->Left = B;
 
SwapNodeReference(A->Right,B->Right);
}
else if (A == B->Right)
{
if (A->Right) A->Right->Parent = B;
if (A->Left) A->Left->Parent = B;
 
if (B->Left) B->Left->Parent = A;
 
if (!B->Parent->IsHeader())
{
if (B->Parent->Left == B)
B->Parent->Left = A;
else
B->Parent->Right = A;
}
else B->Parent->Parent = A;
 
A->Parent = B->Parent;
B->Parent = A;
 
B->Right = A->Right;
A->Right = B;
 
SwapNodeReference(A->Left,B->Left);
}
else
{
if (A->Parent == B->Parent)
SwapNodeReference(A->Parent->Left,A->Parent->Right);
else
{
if (!A->Parent->IsHeader())
{
if (A->Parent->Left == A)
A->Parent->Left = B;
else
A->Parent->Right = B;
}
else A->Parent->Parent = B;
 
if (!B->Parent->IsHeader())
{
if (B->Parent->Left == B)
B->Parent->Left = A;
else
B->Parent->Right = A;
}
else B->Parent->Parent = A;
}
 
if (B->Left) B->Left->Parent = A;
if (B->Right) B->Right->Parent = A;
 
if (A->Left) A->Left->Parent = B;
if (A->Right) A->Right->Parent = B;
 
SwapNodeReference(A->Left,B->Left);
SwapNodeReference(A->Right,B->Right);
SwapNodeReference(A->Parent,B->Parent);
}
 
unsigned long Balance = A->Balance;
A->Balance = B->Balance;
B->Balance=(char)Balance;
}
 
inline void RotateLeft(Node*& Root)
{
Node* Parent = Root->Parent;
Node* x = Root->Right;
 
Root->Parent = x;
x->Parent = Parent;
if (x->Left) x->Left->Parent = Root;
 
Root->Right = x->Left;
x->Left = Root;
Root = x;
}
 
inline void RotateRight(Node*& Root)
{
Node* Parent = Root->Parent;
Node* x = Root->Left;
 
Root->Parent = x;
x->Parent = Parent;
if (x->Right) x->Right->Parent = Root;
 
Root->Left = x->Right;
x->Right = Root;
Root = x;
}
 
inline void BalanceLeft(Node*& Root)
{
Node* Left = Root->Left; // Left Subtree of Root Node
 
switch (Left->Balance)
{
case State::LeftHigh:
Root->Balance = State::Balanced;
Left->Balance = State::Balanced;
RotateRight(Root);
break;
 
case State::RightHigh:
{
Node* subRight = Left->Right; // Right subtree of Left
switch (subRight->Balance)
{
case State::Balanced:
Root->Balance = State::Balanced;
Left->Balance = State::Balanced;
break;
 
case State::RightHigh:
Root->Balance = State::Balanced;
Left->Balance = State::LeftHigh;
break;
 
case State::LeftHigh:
Root->Balance = State::RightHigh;
Left->Balance = State::Balanced;
break;
}
subRight->Balance = State::Balanced;
RotateLeft(Left);
Root->Left = Left;
RotateRight(Root);
}
break;
 
case State::Balanced:
Root->Balance = State::LeftHigh;
Left->Balance = State::RightHigh;
RotateRight(Root);
break;
}
}
 
inline void BalanceRight(Node*& Root)
{
Node* Right = Root->Right; // Right Subtree of Root Node
 
switch (Right->Balance)
{
case State::RightHigh:
Root ->Balance = State::Balanced;
Right->Balance = State::Balanced;
RotateLeft(Root);
break;
 
case State::LeftHigh:
{
Node* subLeft = Right->Left; // Left Subtree of Right
switch (subLeft->Balance)
{
case State::Balanced:
Root ->Balance = State::Balanced;
Right->Balance = State::Balanced;
break;
 
case State::LeftHigh:
Root ->Balance = State::Balanced;
Right->Balance = State::RightHigh;
break;
 
case State::RightHigh:
Root ->Balance = State::LeftHigh;
Right->Balance = State::Balanced;
break;
}
subLeft->Balance = State::Balanced;
RotateRight(Right);
Root->Right = Right;
RotateLeft(Root);
}
break;
 
case State::Balanced:
Root ->Balance = State::RightHigh;
Right->Balance = State::LeftHigh;
RotateLeft(Root);
break;
}
}
 
inline void BalanceTree(Node* Root, unsigned long From)
{
bool Taller = true;
 
while (Taller)
{
Node* Parent = Root->Parent;
unsigned long NextFrom = (Parent->Left == Root) ? Direction::FromLeft : Direction::FromRight;
 
if (From == Direction::FromLeft)
{
switch (Root->Balance)
{
case State::LeftHigh:
if (Parent->IsHeader())
BalanceLeft(Parent->Parent);
else if (Parent->Left == Root)
BalanceLeft(Parent->Left);
else
BalanceLeft(Parent->Right);
Taller = false;
break;
 
case State::Balanced:
Root->Balance = State::LeftHigh;
Taller = true;
break;
 
case State::RightHigh:
Root->Balance = State::Balanced;
Taller = false;
break;
}
}
else
{
switch (Root->Balance)
{
case State::LeftHigh:
Root->Balance = State::Balanced;
Taller = false;
break;
 
case State::Balanced:
Root->Balance = State::RightHigh;
Taller = true;
break;
 
case State::RightHigh:
if (Parent->IsHeader())
BalanceRight(Parent->Parent);
else if (Parent->Left == Root)
BalanceRight(Parent->Left);
else
BalanceRight(Parent->Right);
Taller = false;
break;
}
}
 
if (Taller) // skip up a level
{
if (Parent->IsHeader())
Taller = false;
else
{
Root = Parent;
From = NextFrom;
}
}
}
}
 
 
inline void BalanceTreeRemove(Node* Root, unsigned long From)
{
if (Root->IsHeader()) return;
bool Shorter = true;
 
while (Shorter)
{
Node* Parent = Root->Parent;
unsigned long NextFrom = (Parent->Left == Root) ? Direction::FromLeft : Direction::FromRight;
 
if (From == Direction::FromLeft)
{
switch (Root->Balance)
{
case State::LeftHigh:
Root->Balance = State::Balanced;
Shorter = true;
break;
 
case State::Balanced:
Root->Balance = State::RightHigh;
Shorter = false;
break;
 
case State::RightHigh:
if (Root->Right->Balance == State::Balanced)
Shorter = false;
else
Shorter = true;
if (Parent->IsHeader())
BalanceRight(Parent->Parent);
else if (Parent->Left == Root)
BalanceRight(Parent->Left);
else
BalanceRight(Parent->Right);
break;
}
}
else
{
switch (Root->Balance)
{
case State::RightHigh:
Root->Balance = State::Balanced;
Shorter = true;
break;
 
case State::Balanced:
Root->Balance = State::LeftHigh;
Shorter = false;
break;
 
case State::LeftHigh:
if (Root->Left->Balance == State::Balanced)
Shorter = false;
else
Shorter = true;
if (Parent->IsHeader())
BalanceLeft(Parent->Parent);
else if (Parent->Left == Root)
BalanceLeft(Parent->Left);
else
BalanceLeft(Parent->Right);
break;
}
}
 
if (Shorter)
{
if (Parent->IsHeader())
Shorter = false;
else
{
From = NextFrom;
Root = Parent;
}
}
}
}
 
Node* PreviousItem(Node* node)
{
if (node->IsHeader()) {return node->Right;}
 
else if (node->Left != 0)
{
Node* y = node->Left;
while (y->Right != 0) y = y->Right;
node = y;
}
else
{
Node* y = node->Parent;
if (y->IsHeader()) return y;
while (node == y->Left) {node = y; y = y->Parent;}
node = y;
}
return node;
}
 
Node* NextItem(Node* node)
{
if (node->IsHeader()) return node->Left;
 
if (node->Right != 0)
{
node = node->Right;
while (node->Left != 0) node = node->Left;
}
else
{
Node* y = node->Parent;
if (y->IsHeader()) return y;
while (node == y->Right) {node = y; y = y->Parent;}
node = y;
}
return node;
}
 
inline Node* Minimum(Node* node)
{
while (node->Left) node=node->Left;
return node;
}
 
inline Node* Maximum(Node* node)
{
while (node->Right) node=node->Right;
return node;
}
 
void AdjustAdd(Node* Root)
{
Node* Header = Root->Parent;
while (!Header->IsHeader()) Header=Header->Parent;
 
if (Root->Parent->Left == Root)
{
BalanceTree(Root->Parent,Direction::FromLeft);
if (Header->Left == Root->Parent) Header->Left = Root;
}
else
{
BalanceTree(Root->Parent,Direction::FromRight);
if (Header->Right == Root->Parent) Header->Right = Root;
}
}
 
void AdjustRemove(Node* Parent, unsigned long Direction)
{
BalanceTreeRemove(Parent,Direction);
 
Node* Header = Parent;
while (!Header->IsHeader()) Header=Header->Parent;
 
if (Header->Parent == 0)
{
Header->Left = Header;
Header->Right = Header;
}
else
{
Header->Left = Minimum(Header->Parent);
Header->Right = Maximum(Header->Parent);
}
}
 
unsigned long Depth(const Node* root)
{
if (root)
{
unsigned long left = root->Left ? Depth(root->Left) : 0;
unsigned long right = root->Right ? Depth(root->Right) : 0;
return left < right ? right+1 : left+1;
}
else
return 0;
}
 
 
unsigned long Count(const Node* root)
{
if (root)
{
unsigned long left = root->Left ? Count(root->Left) : 0;
unsigned long right = root->Right ? Count(root->Right) : 0;
return left + right + 1;
}
else
return 0;
}
 
struct setOperation
{
enum
{
Union,
Intersection,
SymmetricDifference,
Difference,
};
};
 
template <class U, class V>
inline int compare(const U& u, const V& v)
{if (u < v) return -1; else if (v < u) return 1; else return 0;}
 
template<class T>
struct setNode : public Node
{
T Element;
 
setNode(const T& ElementSet,
Node* Parent) : Node(Parent), Element(ElementSet) {}
 
operator T&() {return Element;}
};
 
template <class T>
class setIterator
{
public:
 
Node* _node;
 
setIterator() : _node(0) {}
 
setIterator(Node* in) : _node(in) {}
 
setIterator(const setIterator<T>& i) : _node(i._node) {}
 
T& operator*() const
{
return ((setNode<T>*)_node)->Element;
}
 
T* operator->() const
{
return &((setNode<T>*)_node)->Element;
}
 
T* operator&() const
{
return &((setNode<T>*)_node)->Element;
}
 
setIterator<T>& operator++()
{_node = NextItem(_node); return *this;}
 
setIterator<T> operator++(int)
{setIterator<T> save = *this; ++*this ;return save;}
 
setIterator<T>& operator+=(unsigned long increment)
{for (unsigned long i=0; i<increment; i++) ++*this; return *this;}
 
setIterator<T> operator+(unsigned long increment) const
{
setIterator<T> result(*this);
for (unsigned long i=0; i<increment; i++) ++result;
return result;
}
 
setIterator<T>& operator--()
{_node = PreviousItem(_node); return *this;}
 
setIterator<T> operator--(int)
{setIterator<T> save = *this; --*this ;return save;}
 
setIterator<T>& operator-=(unsigned long decrement)
{for (unsigned long i=0; i<decrement; i++) --*this; return *this;}
 
setIterator<T> operator-(unsigned long decrement) const
{
setIterator<T> result(*this);
for (unsigned long i=0; i<decrement; i++) --result;
return result;
}
 
bool operator==(const setIterator<T>& y) const {return _node == y._node;}
 
bool operator!=(const setIterator<T>& y) const {return _node != y._node;}
 
const T& operator[](long i) const {return i>=0 ? *(*this + i) : *(*this - -i);}
 
long operator-(setIterator<T> iter) const
{
long result=0;
while (iter++ != *this) {result++;}
return result;
}
 
bool IsHeader() const {return _node->IsHeader();}
};
 
template <class T>
class constSetIterator
{
public:
 
const Node* _node;
 
constSetIterator() : _node(0) {}
 
constSetIterator(const Node* in) : _node(in) {}
 
constSetIterator(const constSetIterator<T>& i) : _node(i._node) {}
 
constSetIterator(const setIterator<T>& i) : _node(i._node) {}
 
const T& operator*() const
{
return ((setNode<T>*)_node)->Element;
}
 
const T* operator->() const
{
return &((setNode<T>*)_node)->Element;
}
 
const T* operator&() const
{
return &((setNode<T>*)_node)->Element;
}
 
constSetIterator<T>& operator++()
{_node = NextItem((Node*)_node); return *this;}
 
constSetIterator<T> operator++(int)
{constSetIterator<T> save = *this; ++*this ;return save;}
 
constSetIterator<T>& operator+=(unsigned long increment)
{for (unsigned long i=0; i<increment; i++) ++*this; return *this;}
 
constSetIterator<T> operator+(unsigned long increment) const
{
constSetIterator<T> result(*this);
for (unsigned long i=0; i<increment; i++) ++result;
return result;
}
 
constSetIterator<T>& operator--()
{_node = PreviousItem((Node*)_node); return *this;}
 
constSetIterator<T> operator--(int)
{setIterator save = *this; --*this ;return save;}
 
constSetIterator<T>& operator-=(unsigned long decrement)
{for (unsigned long i=0; i<decrement; i++) --*this; return *this;}
 
constSetIterator<T> operator-(unsigned long decrement) const
{
constSetIterator<T> result(*this);
for (unsigned long i=0; i<decrement; i++) --result;
return result;
}
 
bool operator==(const constSetIterator<T>& y) const {return _node == y._node;}
 
bool operator!=(const constSetIterator<T>& y) const {return _node != y._node;}
 
const T& operator[](long i) const {return i>=0 ? *(*this + i) : *(*this - -i);}
 
long operator-(constSetIterator<T> iter) const
{
long result=0;
while (iter++ != *this) {result++;}
return result;
}
 
bool IsHeader() const {return _node->IsHeader;}
};
 
template <class T>
class set
{
public:
 
typedef int (*keyCompare)(const T&,const T&);
 
protected:
 
Node Header;
keyCompare Compare;
 
public:
 
// *** iterators ***
 
typedef setIterator<T> iterator;
 
typedef constSetIterator<T> const_iterator;
 
// *** constructors, destructor, operators ***
 
set(keyCompare C=compare) : Compare(C) {}
 
set(const set<T>& copy) : Compare(copy.Compare)
{
Copy((setNode<T>*)copy.Header.Parent);
}
 
set(const set& A, const set& B, unsigned long operation)
{
Compare = A.Compare;
 
const_iterator first1 = A.begin();
const_iterator last1 = A.end();
const_iterator first2 = B.begin();
const_iterator last2 = B.end();
 
switch (operation)
{
case setOperation::Union:
{
while (first1 != last1 && first2 != last2)
{
int order = Compare(*first1,*first2);
 
if (order < 0)
{
insert(*first1);
++first1;
}
 
else if (order > 0)
{
insert(*first2);
++first2;
}
 
else
{
insert(*first1);
++first1; ++first2;
}
}
 
while (first1 != last1)
{
insert(*first1);
first1++;
}
 
while (first2 != last2)
{
insert(*first2);
first2++;
}
}
break;
 
case setOperation::Intersection:
{
while (first1 != last1 && first2 != last2)
{
int order = Compare(*first1,*first2);
 
if (order < 0)
++first1;
 
else if (order > 0)
++first2;
 
else
{
insert(*first1);
++first1; ++first2;
}
}
}
break;
 
case setOperation::SymmetricDifference:
{
while (first1 != last1 && first2 != last2)
{
int order = Compare(*first1,*first2);
 
if (order < 0)
{
insert(*first1);
++first1;
}
 
else if (order > 0)
{
insert(*first2);
++first2;
}
 
else
{++first1; ++first2;}
}
 
while (first1 != last1)
{
insert(*first1);
++first1;
}
 
while (first2 != last2)
{
insert(*first2);
++first2;
}
}
break;
 
case setOperation::Difference:
{
while (first1 != last1 && first2 != last2)
{
int order = Compare(*first1,*first2);
 
if (order < 0)
{
insert(*first1);
++first1;
}
 
else if (order > 0)
{
insert(*first1);
++first1; ++first2;
}
 
else
{++first1; ++first2;}
}
 
while (first1 != last1)
{
insert(*first1);
++first1;
}
}
break;
 
default:
throw InvalidSetOperationException();
}
}
 
template<class I>
set(I first,I last,keyCompare C=compare)
{
Compare = C;
while (first != last) insert(*first++);
}
 
~set()
{
Destroy((setNode<T>*)Header.Parent);
}
 
set<T>& operator=(const set<T>& copy)
{
erase();
Compare = copy.Compare;
Copy((setNode<T>*)copy.Header.Parent);
return *this;
}
 
unsigned long length() const {return Count(Header.Parent);}
 
operator keyCompare() const {return Compare;}
 
set<T>& operator<<(const T& Element) {insert(Element); return *this;}
 
set<T>& operator>>(const T& Element) {erase(Element); return *this;}
 
// *** methods ***
 
iterator begin() {return Header.Left;}
 
iterator end() {return &Header;}
 
const_iterator begin() const {return Header.Left;}
 
const_iterator end() const {return &Header;}
 
iterator insert(const T& Element)
{
Node* RootNode = Header.Parent;
 
if (RootNode == 0)
{
RootNode = new setNode<T>(Element,&Header);
Header.Left = RootNode;
Header.Right = RootNode;
Header.Parent = RootNode;
return RootNode;
}
 
else
{
for (; ; )
{
int Result = Compare(Element,((setNode<T>*)RootNode)->Element);
 
if (Result == 0)
throw EntryAlreadyExistsException();
 
else if (Result < 0)
{
if (RootNode->Left != 0)
RootNode = RootNode->Left;
else
{
Node* newNode = new setNode<T>(Element,RootNode);
RootNode->Left = newNode;
AdjustAdd(newNode);
return newNode;
}
}
 
else
{
if (RootNode->Right != 0)
RootNode = RootNode->Right;
else
{
Node* newNode = new setNode<T>(Element,RootNode);
RootNode->Right = newNode;
AdjustAdd(newNode);
return newNode;
}
}
}
}
}
 
void erase(const T& Element)
{
Node* RootNode = Header.Parent;
 
for (; ; )
{
if (RootNode == 0) throw EntryNotFoundException();
 
int Result = Compare(Element,((setNode<T>*)RootNode)->Element);
 
if (Result < 0)
RootNode = RootNode->Left;
 
else if (Result > 0)
RootNode = RootNode->Right;
 
else // Item is found
{
if (RootNode->Left != 0 && RootNode->Right != 0)
{
Node* Replace = RootNode->Left;
while (Replace->Right != 0) Replace = Replace->Right;
SwapNodes(RootNode, Replace);
}
 
Node* Parent = RootNode->Parent;
 
unsigned long From = (Parent->Left == RootNode) ? Direction::FromLeft : Direction::FromRight;
 
if (RootNode->Left == 0)
{
if (Parent == &Header)
Header.Parent = RootNode->Right;
else if (From == Direction::FromLeft)
Parent->Left = RootNode->Right;
else
Parent->Right = RootNode->Right;
 
if (RootNode->Right != 0) RootNode->Right->Parent = Parent;
}
else
{
if (Parent == &Header)
Header.Parent = RootNode->Left;
else if (From == Direction::FromLeft)
Parent->Left = RootNode->Left;
else
Parent->Right = RootNode->Left;
 
if (RootNode->Left != 0) RootNode->Left->Parent = Parent;
}
 
AdjustRemove(Parent, From);
delete (setNode<T>*)RootNode;
break;
}
}
}
 
void erase(iterator i)
{
Node* RootNode = i._node;
 
if (RootNode->IsHeader()) throw IsHeaderException();
 
if (RootNode->Left != 0 && RootNode->Right != 0)
{
Node* Replace = RootNode->Left;
while (Replace->Right != 0) Replace = Replace->Right;
SwapNodes(RootNode, Replace);
}
 
Node* Parent = RootNode->Parent;
 
unsigned long From = (Parent->Left == RootNode) ? Direction::FromLeft : Direction::FromRight;
 
if (RootNode->Left == 0)
{
if (Parent == &Header)
Header.Parent = RootNode->Right;
else if (From == Direction::FromLeft)
Parent->Left = RootNode->Right;
else
Parent->Right = RootNode->Right;
 
if (RootNode->Right != 0) RootNode->Right->Parent = Parent;
}
else
{
if (Parent == &Header)
Header.Parent = RootNode->Left;
else if (From == Direction::FromLeft)
Parent->Left = RootNode->Left;
else
Parent->Right = RootNode->Left;
 
if (RootNode->Left != 0) RootNode->Left->Parent = Parent;
}
 
AdjustRemove(Parent, From);
delete (setNode<T>*)RootNode;
}
 
bool operator[](const T& Element) const {return exists(Element);}
 
bool exists(const T& Element) const
{
if (!Header.Parent)
return false;
else
{
const Node* SearchNode = Header.Parent;
 
do
{
int Result = Compare(Element,((setNode<T>*)SearchNode)->Element);
 
if (Result < 0) SearchNode = SearchNode->Left;
 
else if (Result > 0) SearchNode = SearchNode->Right;
 
else break;
 
} while (SearchNode);
 
return SearchNode != 0;
}
}
 
iterator find(const T& Element) const
{
if (!Header.Parent)
throw EntryNotFoundException();
else
{
const Node* SearchNode = Header.Parent;
 
do
{
int Result = Compare(Element,((setNode<T>*)SearchNode)->Element);
 
if (Result < 0) SearchNode = SearchNode->Left;
 
else if (Result > 0) SearchNode = SearchNode->Right;
 
else break;
 
} while (SearchNode);
 
if (SearchNode == 0) throw EntryNotFoundException();
 
return (Node*)SearchNode;
}
}
 
void erase()
{
Destroy((setNode<T>*)Header.Parent);
Header.Left = &Header;
Header.Right = &Header;
Header.Parent = 0;
}
 
iterator after(const T& Element) const
{
const Node* y = &Header;
const Node* x = Header.Parent;
 
while (x != 0)
if (Compare(Element,((setNode<T>*)x)->Element)<0)
{y=x; x=x->Left;}
else
x=x->Right;
 
return (Node*)y;
}
 
iterator afterEquals(const T& Element) const
{
const Node* y = &Header;
const Node* x = Header.Parent;
 
while (x != 0)
{
int c = Compare(Element,((setNode<T>*)x)->Element);
if (c == 0)
{y=x; break;}
else if (c<0)
{y=x; x=x->Left;}
else
x=x->Right;
}
 
return (Node*)y;
}
 
iterator before(const T& Element) const
{
const Node* y = &Header;
const Node* x = Header.Parent;
 
while (x != 0)
if (Compare(Element,((setNode<T>*)x)->Element)<=0)
{x=x->Left;}
else
{y=x; x=x->Right;}
 
return (Node*)y;
}
 
iterator beforeEquals(const T& Element) const
{
const Node* y = &Header;
const Node* x = Header.Parent;
 
while (x != 0)
{
int c = Compare(Element,((setNode<T>*)x)->Element);
if (c == 0)
{y = x; break;}
else if (c<0)
x=x->Left;
else
{y=x; x=x->Right;}
}
 
return (Node*)y;
}
 
iterator last() {return Header.Right;}
 
const_iterator last() const {return Header.Right;}
 
unsigned long depth() const {return Depth(Header.Parent);}
 
protected:
 
void Copy(setNode<T>* Clone)
{
if (!Header.Parent) erase();
if (Clone)
{
Copy((setNode<T>*&)Header.Parent,Clone,&Header);
Header.Left = GetFirst();
Header.Right = GetLast();
}
}
 
void Copy(setNode<T>*& RootNode,
setNode<T>* n,
const Node* Parent)
{
RootNode = new setNode<T>(n->Element,(Node*)Parent);
RootNode->Balance = n->Balance;
 
if (n->Left)
Copy((setNode<T>*&)RootNode->Left,(setNode<T>*)n->Left,RootNode);
else RootNode->Left = 0;
 
if (n->Right)
Copy((setNode<T>*&)RootNode->Right,(setNode<T>*)n->Right,RootNode);
else RootNode->Right = 0;
}
 
Node* GetFirst()
{
if (!Header.Parent)
return &Header;
 
else
{
Node* SearchNode = Header.Parent;
while (SearchNode->Left) SearchNode = SearchNode->Left;
return SearchNode;
}
}
 
Node* GetLast()
{
if (!Header.Parent)
return &Header;
 
else
{
Node* SearchNode = Header.Parent;
while (SearchNode->Right) SearchNode = SearchNode->Right;
return SearchNode;
}
}
 
void Destroy(setNode<T>* RootNode)
{
if (RootNode)
{
if (RootNode->Left)
Destroy((setNode<T>*)RootNode->Left);
 
if (RootNode->Right)
Destroy((setNode<T>*)RootNode->Right);
 
delete RootNode;
}
}
};
 
template<class T>
inline set<T> operator|(const set<T>& a,const set<T>& b)
{set<T> r(a,b,setOperation::Union); return r;}
 
template<class T>
inline set<T> operator&(const set<T>& a,const set<T>& b)
{set<T> r(a,b,setOperation::Intersection); return r;}
 
template<class T>
inline set<T> operator^(const set<T>& a,const set<T>& b)
{set<T> r(a,b,setOperation::SymmetricDifference); return r;}
 
template<class T>
inline set<T> operator-(const set<T>& a,const set<T>& b)
{set<T> r(a,b,setOperation::Difference); return r;}
 
template<class T>
inline bool operator==(const set<T>& a,const set<T>& b)
{
set<T>::const_iterator first1 = a.begin();
set<T>::const_iterator last1 = a.end();
set<T>::const_iterator first2 = b.begin();
set<T>::const_iterator last2 = b.end();
 
bool equals=true;
 
set<T>::keyCompare c = a;
 
while (first1 != last1 && first2 != last2)
{
int order = c(*first1,*first2);
if (order < 0)
{equals=false; break;}
else if (order > 0)
{equals=false; break;}
else
{++first1; ++first2;}
}
 
if (equals)
{
if (first1 != last1) equals = false;
if (first2 != last2) equals = false;
}
 
return equals;
}
 
template<class T>
inline bool operator!=(const set<T>& a,const set<T>& b) {return !(a == b);}
 
template<class T>
inline bool operator<=(const set<T>& a,const set<T>& b)
{
set<T>::const_iterator first1 = a.begin();
set<T>::const_iterator last1 = a.end();
set<T>::const_iterator first2 = b.begin();
set<T>::const_iterator last2 = b.end();
 
set<T>::keyCompare c = a;
 
bool subset=true;
 
while (first1 != last1 && first2 != last2)
{
int order = c(*first1,*first2);
 
if (order < 0)
{subset=false; break;}
 
else if (order > 0)
++first2;
 
else
{++first1; ++first2;}
}
 
if (subset) if (first1 != last1) subset = false;
 
return subset;
}
 
template<class T>
inline int compare(const set<T>& a,const set<T>& b)
{
set<T>::const_iterator first1 = a.begin();
set<T>::const_iterator last1 = a.end();
set<T>::const_iterator first2 = b.begin();
set<T>::const_iterator last2 = b.end();
 
set<T>::keyCompare c = a;
 
while (first1 != last1 && first2 != last2)
{
int order = c(*first1,*first2);
if (order < 0)
return -1;
else if (order > 0)
return 1;
else
{++first1; ++first2;}
}
 
if (first1 != last1) return 1;
if (first2 != last2) return -1;
 
return 0;
}
 
template<class T>
std::ostream& operator<<(std::ostream& s,const set<T>& o)
{
s << "{";
set<T>::const_iterator e = o.end();
set<T>::const_iterator l = e-1;
for (set<T>::const_iterator i = o.begin(); i!=e; ++i)
{s << *i; if (i!=l) s << ",";}
s << "}";
return s;
}
 
void main()
{
try
{
set<double> s;
 
//*** Build the Set
 
for (int i=0; i<10; i++) s << i+.5;
 
//*** Print the set using iterators
 
std::cout << "{";
 
set<double>::iterator last = s.last();
 
for (set<double>::iterator x = s.begin(); x != s.end(); ++x)
{
std::cout << *x;
if (x != last) std::cout << ",";
}
 
std::cout << "}\n";
 
//*** Print the set using stream output operator
 
std::cout << s << "\n";
 
//*** Print the set using for each
 
std::cout << "{";
 
for each (double d in s)
{
std::cout << d;
if (d != *last) std::cout << ",";
}
 
std::cout << "}\n";
}
catch (treeException) {std::cout << "A Tree Exception Occurred.\n";}
}