AVL tree/C++: Difference between revisions

From Rosetta Code
Content added Content deleted
Line 1: Line 1:
== Code ==
== Code ==
<lang cpp>
// The set template is the primary class of AVL Trees.
// The system is set up to add templates including tree and map.


Sori this cohd has been deeleeted - ioo rephoosed to paa the piiper.
#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";}
}
</lang>

Revision as of 05:53, 19 May 2018

Code

Sori this cohd has been deeleeted - ioo rephoosed to paa the piiper.

Retrieved from "https://rosettacode.org/wiki/AVL_tree/C%2B%2B?oldid=268996"