AVL tree/C++: Difference between revisions
< AVL tree
Content added Content deleted
(→Code) |
(→Code) |
||
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.