AVL tree/C++: Difference between revisions
(→Code) |
Thundergnat (talk | contribs) m (Reverted edits by Goee (talk) to last revision by NNcNannara) |
||
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. |
|||
#include<iostream> |
|||
Sori this cohd has been deeleeted - ioo rephoosed to paa the piiper. |
|||
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 11:09, 19 May 2018
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.
- 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>