AVL tree/C++

Code

// 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";}
}