AVL tree/Managed C++

Code

 
// AVL in Managed C++

using namespace System;
using namespace System::Collections;
using namespace System::Collections::Generic;
using namespace System::Threading;
using namespace System::Runtime::Serialization;

namespace Calculus
{

public enum class State
{
 Header,
 LeftHigh,
 Balanced,
 RightHigh
};

public enum class Direction { FromLeft, FromRight };

public ref struct Node
{
 Node^ Left;
 Node^ Right;
 Node^ Parent;
 State Balance;

 Node()
 {
  Left = this;
  Right = this;
  Parent = nullptr;
  Balance = State::Header;
 }

 Node(Node^ p)
 {
  Left = nullptr;
  Right = nullptr;
  Parent = p;
  Balance = State::Balanced;
 }

 property Boolean IsHeader
 { Boolean get() { return Balance == State::Header; } }
};

generic <typename T>
public delegate void TypeFound(Object^ O, T type);

generic <typename T>
public delegate void TypeAdded(Object^ O, T type);

generic <typename T>
public delegate void TypeRemoved(Object^ O, T type);

generic <typename T>
public delegate void TypeUpdated(Object^ O, T before, T after);

generic<typename T>
public interface struct IHasher
{
 int GetHashCode(T t);
};

generic<typename T>
[Serializable]
public ref class Hasher abstract : IHasher<T>
{
 public:

  static property Hasher<T>^ Default { Hasher<T>^ get(); }

  virtual int GetHashCode(T t) = 0;
};

generic<typename T>
[Serializable]
public ref class DefaultHasher : Hasher<T>
{
 public:

 virtual int GetHashCode(T t) override
 {
  return t->GetHashCode();
 }
};

generic<typename T>
Hasher<T>^ Hasher<T>::Default::get() { return gcnew DefaultHasher<T>(); }


generic<typename T>
 public interface struct ICloneable
 {
  T Clone();
 };

generic<typename T>
public interface class ICloner  {  T Clone(T t); };

generic<typename T>
[Serializable]
 public ref struct Cloner abstract : ICloner<T>
{
 static property Cloner<T>^ Default { Cloner<T>^ get(); }

 static property Cloner<T>^ Invisible { Cloner<T>^ get(); }

 virtual T Clone(T t) = 0;
};

generic<typename T>
[Serializable]
public ref struct DefaultCloner1 : Cloner<T>
{
 virtual T Clone(T t) override
 {
  ICloneable<T>^ copier = (ICloneable<T>^)t;
  return copier->Clone();
 }
};

generic<typename T>
[Serializable]
public ref struct DefaultCloner2 : Cloner<T>
{
 virtual T Clone(T t) override
 {
  ICloneable<T>^ copier = (ICloneable<T>^)t;
  return (T)copier->Clone();
 }
};

generic<typename T>
[Serializable]
public ref struct DefaultNoCloner : Cloner<T>
{
 virtual T Clone(T t) override
 {
  return t;
 }
};

generic<typename T>
Cloner<T>^ Cloner<T>::Default::get()
{
   Type^ TypeT = T::typeid;
   Type^ TypeIC1 = ICloneable<T>::typeid;
   Type^ TypeIC2 = ICloneable::typeid;
   if (TypeIC1->IsAssignableFrom(TypeT))
     return gcnew DefaultCloner1<T>();
   else if (TypeIC2->IsAssignableFrom(TypeT))
     return gcnew DefaultCloner2<T>();
   else
     return gcnew DefaultNoCloner<T>();
}

 generic<typename T>
 Cloner<T>^ Cloner<T>::Invisible::get() { return gcnew DefaultNoCloner<T>(); } 

    public ref struct OutOfKeyOrderException : public Exception
    {
        static String^ message = gcnew String("A tree was found to be out of key order.");

        OutOfKeyOrderException() : Exception(message)
        {
            HelpLink = gcnew String("Benedict@NNcNannara.net");
            Source = gcnew String("Calculus Subsystem");
        }
    };

    public ref struct TreeInvalidParentException : public Exception
    {
        static String^ message = gcnew String("The validation routines detected that the parent structure of a tree is invalid.");

        TreeInvalidParentException() : Exception(message)
        {
            HelpLink = gcnew String("Benedict@NNcNannara.net");
            Source = gcnew String("Calculus Subsystem");
        }
    };

    public ref struct TreeOutOfBalanceException : public Exception
    {
        static String^ message = gcnew String("The validation routines detected that the tree is out of balance.");

        TreeOutOfBalanceException() : Exception(message)
        {
            HelpLink = gcnew String("Benedict@NNcNannara.net");
            Source = gcnew String("Calculus Subsystem");
        }
    };

    public ref struct InvalidEmptyTreeException : public Exception
    {
        static String^ message = gcnew String("The validation routines detected that an empty tree is invalid.");

        InvalidEmptyTreeException() : Exception(message)
        {
            HelpLink = gcnew String("Benedict@NNcNannara.net");
            Source = gcnew String("Calculus Subsystem");
        }
    };


    public ref struct InvalidEndItemException : public Exception
    {
        static String^ message = gcnew String("The validation routines detected that the end item of a tree is invalid.");

        InvalidEndItemException() : Exception(message)
        {
            HelpLink = gcnew String("Benedict@NNcNannara.net");
            Source = gcnew String("Calculus Subsystem");
        }
    };

     public ref struct EntryAlreadyExistsException : public Exception
    {
        static String^ message = gcnew String("An entry already exists in the collection.");

        EntryAlreadyExistsException() : Exception(message)
        {
            HelpLink = gcnew String("Benedict@NNcNannara.net");
            Source = gcnew String("Calculus Subsystem");
        }
    };

    public ref struct DifferentKeysException : public Exception
    {
        static String^ message = gcnew String("The specified items have different keys.");

        DifferentKeysException() : Exception(message)
        {
            HelpLink = gcnew String("Benedict@NNcNannara.net");
            Source = gcnew String("Calculus Subsystem");
        }
    };

    public ref struct AddSubTreeFailedException : public Exception
    {
        static String^ message = gcnew String("Subtree creation failed.");

        AddSubTreeFailedException() : Exception(message)
        {
            HelpLink = gcnew String("Benedict@NNcNannara.net");
            Source = gcnew String("Calculus Subsystem");
        }
    };

    public ref struct IsEndItemException : public Exception
    {
        static String^ message = gcnew String("The requested action cannot be performed on an end item.");

        IsEndItemException() : Exception(message)
        {
            HelpLink = gcnew String("Benedict@NNcNannara.net");
            Source = gcnew String("Calculus Subsystem");
        }
    };

    public ref struct EntryNotFoundException : public Exception
    {
        static String^ message = gcnew String("The requested entry could not be located in the specified collection.");

        EntryNotFoundException() : Exception(message)
        {
            HelpLink = gcnew String("Benedict@NNcNannara.net");
            Source = gcnew String("Calculus Subsystem");
        }
    };

    public ref struct InvalidSetOperationException : public Exception
    {
        static String^ message = gcnew String("An invalid set operation was specified.");

        InvalidSetOperationException() : Exception(message)
        {
            HelpLink = gcnew String("Benedict@NNcNannara.net");
            Source = gcnew String("Calculus Subsystem");
        }
    };

Node^ PreviousItem(Node^ node)
{
 if (node->IsHeader) {return node->Right;}

 else if (node->Left != nullptr)
  {
   Node^ y = node->Left;
   while (y->Right != nullptr) 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 != nullptr)
  {
   node = node->Right;
   while (node->Left != nullptr) 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;
}

void SwapNodeReference(Node^% first, Node^% second)
{Node^ temporary = first; first = second; second = temporary;}

void LeftNodeSwap(Node^ Root, Node^ Replace)
{
 if (Replace->Left) Replace->Left->Parent = Root;
 if (Replace->Right) Replace->Right->Parent = Root;

 if (Root->Right) Root->Right->Parent = Replace;

 if (Replace == Root->Left)
  {
   Replace->Parent = Root->Parent;
   Root->Parent = Replace;

   Root->Left = Replace->Left;
   Replace->Left = Root;
  }
 else
  {
   Root->Left->Parent = Replace;

   if (Replace->Parent->Left == Replace)
    Replace->Parent->Left = Root;
   else
    Replace->Parent->Right = Root;

   SwapNodeReference(Root->Left,Replace->Left);
   SwapNodeReference(Root->Parent,Replace->Parent);
  }

 SwapNodeReference(Root->Right,Replace->Right);

 State Balance = Root->Balance;
 Root->Balance = Replace->Balance;
 Replace->Balance=Balance;
}

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);
  }

 State Balance = A->Balance;
 A->Balance = B->Balance;
 B->Balance=Balance;
}

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

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

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

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

void BalanceTree(Node^ Root, Direction From)
{
  bool Taller = true;

  while (Taller)
   {
    Node^ Parent = Root->Parent;
    Direction 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;
       }
     }
   }
 }

void BalanceTreeRemove(Node^ Root, Direction From)
{
  if (Root->IsHeader) return;
  bool Shorter = true;

  while (Shorter)
   {
    Node^ Parent = Root->Parent;
    Direction 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^ Minimum(Node^ node)
{
 while (node->Left) node=node->Left;
 return node;
}

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, Direction Direction)
{
 BalanceTreeRemove(Parent,Direction);
 
 Node^ Header = Parent;
 while (!Header->IsHeader) Header=Header->Parent;

 if (Header->Parent == nullptr)
 {
  Header->Left = Header;
  Header->Right = Header;
 }
 else
 {
  Header->Left = Minimum(Header->Parent);
  Header->Right = Maximum(Header->Parent);
 }
}

unsigned long long Depth(Node^ Root)
{
 if (Root)
  {
   unsigned long long Left  = Root->Left  ? Depth(Root->Left)  : 0;
   unsigned long long Right = Root->Right ? Depth(Root->Right) : 0;
   return Left < Right ? Right+1 : Left+1;
  }
 else
  return 0;
}

unsigned long long Count(Node^ Root)
{
 if (Root)
  {
   unsigned long long left  = Root->Left  ? Count(Root->Left)  : 0;
   unsigned long long right = Root->Right ? Count(Root->Right) : 0;
   return left + right + 1;
  }
 else
  return 0;
}

 public enum class SetOperation
 {
            Union,
            Intersection,
            SymmetricDifference,
            Difference,
            Equality,
            Inequality,
            Subset,
            Superset
 };

generic<typename T>
public ref class SetNode : Node
{
 public:

  T Data;

  SetNode(T dataType, Node^ Parent) : Node(Parent) {Data = dataType; }
};

generic<typename T>
public value struct SetEntry : System::Collections::Generic::IEnumerator<T>
{
 public:

  SetEntry(Node^ n) { _Node = n; }

  property T Value
  {
   T get()
    {
     if (_Node->Balance == State::Header) throw gcnew IsEndItemException();
     return ((SetNode<T>^)_Node)->Data;
    }
   void set(T Value)
    {
     if (_Node->Balance == State::Header) throw gcnew IsEndItemException();
     ((SetNode<T>^)_Node)->Data = Value;
    }
  }

 property Boolean IsHeader { Boolean get() { return _Node->IsHeader; } }

 virtual Boolean MoveNext()
 {
  _Node = NextItem(_Node);
  return _Node->IsHeader ? false : true;
 }

 Boolean MovePrevious()
 {
  _Node = PreviousItem(_Node);
  return _Node->IsHeader ? false : true;
 }

 static SetEntry<T> operator ++(SetEntry<T> entry)
 {
  entry._Node = NextItem(entry._Node);
  return entry;
 }

 static SetEntry<T> operator --(SetEntry<T> entry)
 {
  entry._Node = PreviousItem(entry._Node);
  return entry;
 }

 static SetEntry<T> operator +(SetEntry<T> C, unsigned long long Increment)
 {
  SetEntry<T> Result =  SetEntry<T>(C._Node);
  for (unsigned long long i = 0; i < Increment; i++) ++Result;
  return Result;
 }

 static SetEntry<T> operator +(unsigned long long Increment, SetEntry<T> C)
 {
  SetEntry<T> Result = SetEntry<T>(C._Node);
  for (unsigned long long i = 0; i < Increment; i++) ++Result;
  return Result;
 }

 static SetEntry<T> operator -(SetEntry<T> C, unsigned long long Decrement)
 {
  SetEntry<T> Result = SetEntry<T>(C._Node);
  for (unsigned long long i = 0; i < Decrement; i++) --Result;
  return Result;
 }

 virtual void Reset()
 { while (!_Node->IsHeader) _Node = NextItem(_Node); }

 virtual property Object^ InterfaceCurrentA
  {
   Object^ get()  = System::Collections::IEnumerator::Current::get
      {
          if (_Node->Balance == State::Header) throw gcnew IsEndItemException();
          return ((SetNode<T>^)_Node)->Data;
      }
  }

 virtual property T InterfaceCurrentB
  {
   T get()  = System::Collections::Generic::IEnumerator<T>::Current::get
      {
          if (_Node->Balance == State::Header) throw gcnew IsEndItemException();
          return ((SetNode<T>^)_Node)->Data;
      }
  }

 static Boolean operator ==(SetEntry<T> x, SetEntry<T> y) { return x._Node == y._Node; }
 static Boolean operator !=(SetEntry<T> x, SetEntry<T> y) { return x._Node != y._Node; }

 static long long operator -(SetEntry<T> This, SetEntry<T> iter)
 {
  long long Result = 0;
  while (This._Node != iter._Node) { iter.MoveNext(); Result++; }
  return Result;
 }

 virtual String^ ToString() override
 {
  if (_Node->Balance == State::Header) throw gcnew IsEndItemException();
  return Value->ToString();
 }

 Node^ _Node;
};


generic<typename T>
[Serializable]
public ref class Set : public System::Collections::Generic::ICollection<T>,
                       public System::ICloneable,
                       public ISerializable,
                       public IComparable<Set<T>^>,
                       public IEquatable<Set<T>^>
{
 public:
  event TypeAdded<T>^ Added;
  event TypeRemoved<T>^ Removed;
  event TypeUpdated<T>^ Updated;

 protected:
  Node^ Header;
  System::Collections::Generic::IComparer<T>^ TComparer;
  ICloner<T>^ TCloner;
  IHasher<T>^ THasher;
  unsigned long long Nodes;

  property Node^ Root
  {
   Node^ get() { return Header->Parent; }
   void set(Node^ Value) { Header->Parent = Value; }
  }

        //*** Constructors ***

 public:

  Set()
   {
    Nodes=0;
    Header = gcnew Node();
    TComparer = System::Collections::Generic::Comparer<T>::Default;
    TCloner = Calculus::Cloner<T>::Default;
    THasher = Calculus::Hasher<T>::Default;
   }

  Set(System::Collections::Generic::IComparer<T>^ TCompare)
  {
   Nodes=0;
   Header = gcnew Node();
   TComparer = TCompare;
   TCloner = Calculus::Cloner<T>::Default;
   THasher = Calculus::Hasher<T>::Default;
  }

  Set(Set<T>^ SetToCopy)
  {
   Nodes=0;
   Header = gcnew Node();
   TComparer = SetToCopy->TComparer;
   TCloner = SetToCopy->TCloner;
   THasher = SetToCopy->THasher;
   Copy((SetNode<T>^)SetToCopy->Root);
  }

  Set(System::Collections::Generic::IEnumerable<T>^ Collection)
  {
   Nodes=0;
   Header = gcnew Node();
   TComparer = System::Collections::Generic::Comparer<T>::Default;
   TCloner = Calculus::Cloner<T>::Default;
   THasher = Calculus::Hasher<T>::Default;

   for each (T t in Collection) Add(TCloner->Clone(t));
  }

  Set(... array<T>^ Collection)
  {
   Nodes=0;
   Header = gcnew Node();
   TComparer = System::Collections::Generic::Comparer<T>::Default;
   TCloner = Calculus::Cloner<T>::Default;
   THasher = Calculus::Hasher<T>::Default;

   for each (T t in Collection) Add(TCloner->Clone(t));
  }

  Set(System::Collections::Generic::IEnumerable<T>^ Collection,
      System::Collections::Generic::IComparer<T>^ TCompare)
  {
   Nodes=0;
   Header = gcnew Node();
   TComparer = TCompare;
   TCloner = Calculus::Cloner<T>::Default;
   THasher = Calculus::Hasher<T>::Default;
 
   for each (T t in Collection) Add(TCloner->Clone(t));
  }

  Set(Set<T>^ A,
      Set<T>^ B,
      SetOperation operation)
  {
   Nodes=0;
   Header = gcnew Node();
   TComparer = A->TComparer;
   TCloner = A->TCloner;
   THasher = A->THasher;
   CombineSets(A, B, this, operation);
  }

  Set(SerializationInfo^ si, StreamingContext sc)
  {
   Nodes=0;
   System::Collections::Generic::IComparer<T>^ TCompare = (System::Collections::Generic::IComparer<T>^)si->GetValue("TComparer", System::Collections::Generic::IComparer<T>::typeid);
   Calculus::ICloner<T>^ TClone = (Calculus::ICloner<T>^)si->GetValue("TCloner", ICloner<T>::typeid);
   Calculus::IHasher<T>^ THasher = (Calculus::IHasher<T>^)si->GetValue("THasher", IHasher<T>::typeid);

   Header = gcnew Node();
   TComparer = TCompare;
   TCloner = TClone;

   Type^ type = T::typeid;

   unsigned long long LoadCount = si->GetUInt64("Count");

   for (unsigned long long i = 0; i < LoadCount; i++)
   {
    Object^ obj = si->GetValue(i.ToString(), type);
    Add((T)obj, false);
   }
  }

        //*** Operators ***

  static Set<T>^ operator |(Set<T>^ A, Set<T>^ B)
  {
   Set<T>^ U = gcnew Set<T>(A->TComparer);
   U->TCloner = A->TCloner;
   U->THasher = A->THasher;
   CombineSets(A, B, U, SetOperation::Union);
   return U;
  }

  static Set<T>^ operator &(Set<T>^ A, Set<T>^ B)
  {
   Set<T>^ I = gcnew Set<T>(A->TComparer);
   I->TCloner = A->TCloner;
   I->THasher = A->THasher;
   CombineSets(A, B, I, SetOperation::Intersection);
   return I;
  }

  static Set<T>^ operator ^(Set<T>^ A, Set<T>^ B)
  {
   Set<T>^ S = gcnew Set<T>(A->TComparer);
   S->TCloner = A->TCloner;
   S->THasher = A->THasher;
   CombineSets(A, B, S, SetOperation::SymmetricDifference);
   return S;
  }

  static Set<T>^ operator -(Set<T>^ A, Set<T>^ B)
  {
   Set<T>^ S = gcnew Set<T>(A->TComparer);
   S->TCloner = A->TCloner;
   S->THasher = A->THasher;
   CombineSets(A, B, S, SetOperation::Difference);
   return S;
  }

  static Boolean operator ==(Set<T>^ A, Set<T>^ B)
  {
   return CheckSets(A, B, SetOperation::Equality);
  }

  static Boolean operator !=(Set<T>^ A, Set<T>^ B)
  {
   return CheckSets(A, B, SetOperation::Inequality);
  }

  static Boolean operator <(Set<T>^ A, Set<T>^ B)
  {
   return CheckSets(A, B, SetOperation::Subset);
  }

  static Boolean operator >(Set<T>^ A, Set<T>^ B)
  {
   return CheckSets(A, B, SetOperation::Superset);
  }

  property Boolean default [T]
  {
   Boolean get(T key)
   {
    if (Root == nullptr)
     return false;
    else
     {
      Node^ search = Root;

      do
       {
        int Result = TComparer->Compare(key, static_cast<SetNode<T>^>(search)->Data);

        if (Result < 0) search = search->Left;

        else if (Result > 0) search = search->Right;

        else break;

       } while (search != nullptr);

       return search != nullptr;
      }
    }
  }

 static Set<T>^ operator +(Set<T>^ set, T t)
 {
  set->Add(t, false);
  return set;
 }

 static Set<T>^ operator -(Set<T>^ set, T t)
 {
  set->Remove(t);
  return set;
 }

 //*** Properties ***

 property SetEntry<T> Begin
 { SetEntry<T> get() { return SetEntry<T>(Header->Left); } }

 property ICloner<T>^ TypeCloner
 {
  ICloner<T>^ get() { return TCloner; }
  void set(ICloner<T>^ Value) { TCloner = Value; }
 }
 property System::Collections::Generic::IComparer<T>^ Comparer
 {System::Collections::Generic::IComparer<T>^ get() { return TComparer; } }

 virtual property int Count { int get() { return (int)Length; } }

 property SetEntry<T> End
 { SetEntry<T> get() { return SetEntry<T>(Header); } }

 property T First
 { T get() { return ((SetNode<T>^)LeftMost)->Data; } }

 property int Hash { int get() { return GetHashCode(); } }

 property IHasher<T>^ Hasher
 {
  IHasher<T>^ get() { return THasher; }
  void set(IHasher<T>^ Value) { THasher = Value; }
 }

 virtual property Boolean IsReadOnly { Boolean get() { return false; } }

 virtual property Boolean IsSynchronized { Boolean get() { return true; } }

 property T Last
 { T get() { return ((SetNode<T>^)RightMost)->Data; } }

 property Node^ LeftMost
 {
  Node^ get() { return Header->Left; }
  void set(Node^ Value) { Header->Left = Value; }
 }

 property unsigned long long Length {  unsigned long long get() { return Count;} }

 property Node^ RightMost
 {
  Node^ get() { return Header->Right; }
  void set(Node^ Value) { Header->Right = Value; }
 }
 
 property Object^ SyncRoot { Object^ get() { return this; } }

        //*** Public Methods ***

 SetEntry<T> After(T Value, Boolean equals)
 {
  return SetEntry<T>(equals ? AfterEquals(Value) : After(Value));
 }

 virtual void Add(T t)
 {
  Add(t, false);
 }

 void Add(SetEntry<T> cse)
 {
  Add(TCloner->Clone(cse.Value), false);
 }

 unsigned long long Add(System::Collections::Generic::IEnumerable<T>^ copy)
 {
  unsigned long long count = 0;

  for each(T t in copy)
  {
   Add(TCloner->Clone(t), false);
   count++;
  }

  return count;
 }

 SetEntry<T> Before(T value, bool equals)
 {
  return SetEntry<T>(equals ? BeforeEquals(value) : Before(value));
 }

 virtual void Clear() { Remove(); }

 void CallRemoved(T data) { Removed(this, data); }

 virtual Object^ Clone()
 {
  Set<T>^ setOut = gcnew Set<T>(TComparer);
  setOut->TCloner = TCloner;
  setOut->THasher = THasher;
  setOut->Copy((SetNode<T>^)Root);
  return setOut;
 }

 virtual int CompareTo(Set<T>^ B)
 {
  return CompareSets(this, B);
 }

 virtual bool Contains(T t)
 {
  Node^ found = Search(t);
  return found != nullptr ? true : false;
 }

 virtual Boolean Contains(Set<T>^ ss)
 {
  for each (T t in ss)
   if (Search(t) == nullptr) return false;

  return true;
 }

 virtual void CopyTo(array<T>^ arr, int i)
 {
  SetEntry<T> begin = SetEntry<T>((SetNode<T>^)Header->Left);
  SetEntry<T> end = SetEntry<T>(Header);

  while (begin != end)
  {
   arr->SetValue(TCloner->Clone(((SetNode<T>^)begin._Node)->Data), i);
   i++; begin.MoveNext();
  }
 }

  virtual void CopyTo(System::Array^ arr, int i)
  {
   SetEntry<T> begin = SetEntry<T>((SetNode<T>^)Header->Left);
   SetEntry<T> end = SetEntry<T>(Header);

   while (begin != end)
   {
     arr->SetValue(TCloner->Clone(((SetNode<T>^)begin._Node)->Data), i);
     i++; begin.MoveNext();
   }
  }

  virtual Boolean Equals(Set<T>^ compare)
  {
   SetEntry<T> first1 = Begin;
   SetEntry<T> last1 = End;
   SetEntry<T> first2 = compare->Begin;
   SetEntry<T> last2 = compare->End;

   Boolean equals = true;

   while (first1 != last1 && first2 != last2)
    {
     if (TComparer->Compare(first1.Value, first2.Value) == 0)
      { first1.MoveNext(); first2.MoveNext(); }
     else
      { equals = false; break; }
    }

   if (equals)
    {
     if (first1 != last1) equals = false;
     if (first2 != last2) equals = false;
    }

   return equals;
  }

  T Find(T value)
  {
   Node^ _Node = Search(value);
   if (_Node == nullptr)
     throw gcnew EntryNotFoundException();
   return ((SetNode<T>^)_Node)->Data;
  }

 virtual System::Collections::IEnumerator^ InterfaceGetEnumeratorSimple() sealed = System::Collections::IEnumerable::GetEnumerator
 { return gcnew SetEntry<T>(Header); }

 virtual System::Collections::Generic::IEnumerator<T>^ InterfaceGetEnumerator() sealed = System::Collections::Generic::IEnumerable<T>::GetEnumerator
 { return gcnew SetEntry<T>(Header); }

  virtual Int32 GetHashCode() override
  {
   Int32 HashCode = 0;
   for each (T t in this) HashCode += THasher->GetHashCode(t);
   return HashCode;
  }

  virtual void GetObjectData(SerializationInfo^ si, StreamingContext sc)
  {
   si->SetType(Calculus::Set<T>::typeid);

   Type^ type = T::typeid;

   unsigned long long index = 0;
   for each (T e in *this)
   {
     si->AddValue(index.ToString(), e, type);
     index++;
   }

   si->AddValue("Count", index);
   si->AddValue("TComparer", TComparer, TComparer->GetType());
   si->AddValue("TCloner", TCloner, TCloner->GetType());
   si->AddValue("THasher", THasher, THasher->GetType());
  }

  SetEntry<T> Insert(T t) { return SetEntry<T>(Add(t, false)); }

  SetEntry<T> Locate(T value)
  {
   Node^ _Node = Search(value);
   if (_Node == nullptr)
     throw gcnew EntryNotFoundException();
   return SetEntry<T>(_Node);
  }

  void Notify()
  {
   Notify((SetNode<T>^)Root);
  }

  unsigned long long Remove()
  {
   for each (T t in this) Removed(this, t);
   unsigned long long count = Nodes;
   Root = nullptr;
   LeftMost = Header;
   RightMost = Header;
   Nodes = 0;
   return count;
  }

  virtual bool Remove(T data)
  {
   Node^ root = Root;

   for (; ; )
   {
    if (root == nullptr) throw gcnew EntryNotFoundException();

    int compare = TComparer->Compare(data, ((SetNode<T>^)root)->Data);

    if (compare < 0)
     root = root->Left;

    else if (compare > 0)
     root = root->Right;

    else // Item is found
    {
     if (root->Left != nullptr && root->Right != nullptr)
     {
      Node^ replace = root->Left;
      while (replace->Right != nullptr) replace = replace->Right;
      SwapNodes(root, replace);
     }

     Node^ Parent = root->Parent;

     Direction From = (Parent->Left == root) ? Direction::FromLeft : Direction::FromRight;

     if (LeftMost == root)
      {
       Node^ n = NextItem(root);

       if (n->IsHeader)
        { LeftMost = Header; RightMost = Header; }
       else
         LeftMost = n;
      }
      else if (RightMost == root)
       {
        Node^ p = PreviousItem(root);

        if (p->IsHeader)
         { LeftMost = Header; RightMost = Header; }
        else
          RightMost = p;
       }

     if (root->Left == nullptr)
     {
      if (Parent == Header)
        Header->Parent = root->Right;
      else if (Parent->Left == root)
        Parent->Left = root->Right;
      else
        Parent->Right = root->Right;

      if (root->Right != nullptr) root->Right->Parent = Parent;
     }
     else
      {
       if (Parent == Header)
        Header->Parent = root->Left;
       else if (Parent->Left == root)
        Parent->Left = root->Left;
       else
        Parent->Right = root->Left;

       if (root->Left != nullptr) root->Left->Parent = Parent;
      }

      AdjustRemove(Parent, From);
      Nodes--;
      Removed(this, ((SetNode<T>^)root)->Data);
      break;
     }
   }
   return true;
  }

  void Remove(SetEntry<T> i) { Remove(i._Node); }

  Node^ Search(T data)
  {
   if (Root == nullptr)
     return nullptr;
   else
    {
     Node^ search = Root;

     do
      {
       int Result = TComparer->Compare(data, ((SetNode<T>^)search)->Data);

       if (Result < 0) search = search->Left;

       else if (Result > 0) search = search->Right;

       else break;

      } while (search != nullptr);

      return search;
    }
  }

  virtual String^ ToString() override
  {
   String^ StringOut = gcnew String("{");

   SetEntry<T> start = Begin;
   SetEntry<T> end = End;
   SetEntry<T> last = End - 1;

   while (start != end)
   {
    String^ NewStringOut = start.Value->ToString();
    if (start != last) NewStringOut = NewStringOut + gcnew String(",");
    StringOut = StringOut + NewStringOut;
    ++start;
   }

   StringOut = StringOut + gcnew String("}");
   return StringOut;
  }

 void Update(T value)
 {
  if (Root == nullptr)
   throw gcnew EntryNotFoundException();
  else
   {
    Node^ search = Root;

    do
    {
     int Result = TComparer->Compare(value, ((SetNode<T>^)search)->Data);

     if (Result < 0) search = search->Left;

     else if (Result > 0) search = search->Right;

     else break;

    } while (search != nullptr);

    if (search == nullptr) throw gcnew EntryNotFoundException();

    T saved = ((SetNode<T>^)search)->Data;
    ((SetNode<T>^)search)->Data = value;
    Updated(this, saved, value);
  }
 }

 void Update(SetEntry<T>^ entry, T after) {  Update((SetNode<T>^)entry->_Node, after); }

 void Validate()
 {
  if (Nodes == 0 || Root == nullptr)
  {
   if (Nodes != 0) { throw gcnew InvalidEmptyTreeException(); }
   if (Root != nullptr) { throw gcnew InvalidEmptyTreeException(); }
   if (LeftMost != Header) { throw gcnew InvalidEndItemException(); }
   if (RightMost != Header) { throw gcnew InvalidEndItemException(); }
  }

  Validate((SetNode<T>^)Root);

  if (Root != nullptr)
  {
   Node^ x = Root;
   while (x->Left != nullptr) x = x->Left;

   if (LeftMost != x) throw gcnew InvalidEndItemException();

   Node^ y = Root;
   while (y->Right != nullptr) y = y->Right;

   if (RightMost != y) throw gcnew InvalidEndItemException();
  }
 }

        //*** Private Methods ***

 protected:

 Node^ After(T data)
 {
  Node^ y = Header;
  Node^ x = Root;

  while (x != nullptr)
   if (TComparer->Compare(data, ((SetNode<T>^)x)->Data) < 0)
    { y = x; x = x->Left; }
   else
     x = x->Right;

  return y;
 }

 Node^ AfterEquals(T data)
 {
  Node^ y = Header;
  Node^ x = Root;

  while (x != nullptr)
  {
   int c = TComparer->Compare(data, ((SetNode<T>^)x)->Data);
   if (c == 0)
    { y = x; break; }
   else if (c < 0)
    { y = x; x = x->Left; }
   else
    x = x->Right;
  }

  return y;
 }

 SetNode<T>^ Add(T data, bool exist)
 {
  Node^ root = Root;

  if (root == nullptr)
   {
    Root = gcnew SetNode<T>(data, Header);
    Nodes++;
    LeftMost = Root;
    RightMost = Root;
    Added(this, ((SetNode<T>^)Root)->Data);
    return (SetNode<T>^)Root;
   }
  else
   {
    for (; ; )
     {
      int compare = TComparer->Compare(data, static_cast<SetNode<T>^>(root)->Data);

      if (compare == 0) // Item Exists
       {
        if (exist)
         {
          T saved = ((SetNode<T>^)root)->Data;
          ((SetNode<T>^)root)->Data = data;
          Updated(this, saved, data);
          return (SetNode<T>^)root;
         }
        else
         throw gcnew EntryAlreadyExistsException();
       }

      else if (compare < 0)
       {
        if (root->Left != nullptr)
         root = root->Left;
        else
         {
          SetNode<T>^ NewNode = gcnew SetNode<T>(data, root);
          Nodes++;
          root->Left = NewNode;
          AdjustAdd(NewNode);
          Added(this, NewNode->Data);
          return NewNode;
         }
      }

    else
     {
      if (root->Right != nullptr)
       root = root->Right;
      else
       {
        SetNode<T>^ NewNode = gcnew SetNode<T>(data, root);
        Nodes++;
        root->Right = NewNode;
        AdjustAdd(NewNode);
        Added(this, NewNode->Data);
        return NewNode;
       }
     }
    }
   }
 }

 unsigned long long Add(Node^ begin, Node^ end)
 {
  bool success = true;
  unsigned long long count = 0;

  SetEntry<T> i(begin);

  while (success && i._Node != end)
  {
   if (!i._Node->IsHeader)
    {
     try
      {
       Add(TCloner->Clone(i.Value), false);
       count++;
       i.MoveNext();
      }
     catch (Exception^) { success = false; }
    }
   else i.MoveNext();
  }
  if (!success)
   {
    if (count != 0)
     {
      i.MovePrevious();
      SetEntry<T> start(begin); start.MovePrevious();

      while (i != start)
       {
        SetEntry<T> j(i._Node); j.MovePrevious();
        if (!i._Node->IsHeader) Remove(i.Value);
        i = j;
       }
     }
    throw gcnew AddSubTreeFailedException();
   }
  return Count;
 }

 Node^ Before(T data)
 {
  Node^ y = Header;
  Node^ x = Root;

  while (x != nullptr)
   if (TComparer->Compare(data, ((SetNode<T>^)x)->Data) <= 0)
    x = x->Left;
   else
    { y = x; x = x->Right; }

  return y;
 }

 Node^ BeforeEquals(T data)
 {
  Node^ y = Header;
  Node^ x = Root;

  while (x != nullptr)
  {
   int c = TComparer->Compare(data, ((SetNode<T>^)x)->Data);
   if (c == 0)
    { y = x; break; }
   else if (c < 0)
    x = x->Left;
   else
    { y = x; x = x->Right; }
  }

  return y;
 }

 void Bounds()
 {
  LeftMost = GetFirst();
  RightMost = GetLast();
 }

 void Copy(SetNode<T>^ CopyRoot)
 {
  if (Root != nullptr) Remove();
  if (CopyRoot != nullptr)
   {
     Copy(Header->Parent, CopyRoot, Header);
     LeftMost = GetFirst();
     RightMost = GetLast();
    }
 }

 void Copy(Node^% root, SetNode<T>^ CopyRoot, Node^ Parent)
 {
  root = gcnew SetNode<T>(TCloner->Clone(CopyRoot->Data), Parent);
  Nodes++;

  root->Balance = CopyRoot->Balance;

  if (CopyRoot->Left != nullptr)
   Copy(root->Left, (SetNode<T>^)CopyRoot->Left, (SetNode<T>^)root);

  if (CopyRoot->Right != nullptr)
   Copy(root->Right, (SetNode<T>^)CopyRoot->Right, (SetNode<T>^)root);

  Added(this, ((SetNode<T>^)root)->Data);
 }

 Node^ GetFirst()
 {
  if (Root == nullptr)
   return Header;

  else
   {
    Node^ search = Root;
    while (search->Left != nullptr) search = search->Left;
    return search;
   }
 }

 Node^ GetLast()
 {
  if (Root == nullptr)
   return Header;

  else
   {
    Node^ search = Root;
    while (search->Right != nullptr) search = search->Right;
    return search;
   }
 }

 void Import(SetNode<T>^ n)
 {
  if (n != nullptr) ImportTree(n);
 }

 void ImportTree(SetNode<T>^ n)
 {
  if (n->Left != nullptr) ImportTree((SetNode<T>^)n->Left);
  Add(n->Data, false);
  if (n->Right != nullptr) ImportTree((SetNode<T>^)n->Right);
 }

 void Notify(SetNode<T>^ root)
 {
  if (root != nullptr)
  {
   if (root->Left != nullptr)
    Notify((SetNode<T>^)root->Left);

   Added(this, root->Data);

   if (root->Right != nullptr)
    Notify((SetNode<T>^)root->Right);
  }
 }

 void Remove(Node^ root)
 {
  if (root->Left != nullptr && root->Right != nullptr)
  {
   Node^ replace = root->Left;
   while (replace->Right != nullptr) replace = replace->Right;
   SwapNodes(root, replace);
  }

  Node^ Parent = root->Parent;

  Direction From = (Parent->Left == root) ? Direction::FromLeft : Direction::FromRight;

  if (LeftMost == root)
  {
   Node^ n = NextItem(root);

   if (n->IsHeader)
    { LeftMost = Header; RightMost = Header; }
   else
    LeftMost = n;
  }
  else if (RightMost == root)
  {
    Node^ p = PreviousItem(root);

    if (p->IsHeader)
     { LeftMost = Header; RightMost = Header; }
    else
     RightMost = p;
  }

  if (root->Left == nullptr)
  {
   if (Parent == Header)
    Header->Parent = root->Right;
   else if (Parent->Left == root)
    Parent->Left = root->Right;
   else
    Parent->Right = root->Right;

   if (root->Right != nullptr) root->Right->Parent = Parent;
  }
  else
  {
   if (Parent == Header)
    Header->Parent = root->Left;
   else if (Parent->Left == root)
    Parent->Left = root->Left;
   else
    Parent->Right = root->Left;

   if (root->Left != nullptr) root->Left->Parent = Parent;
  }

  AdjustRemove(Parent, From);
  Nodes--;
  Removed(this, ((SetNode<T>^)root)->Data);
 }

 unsigned long long Remove(Node^ i, Node^ j)
 {
  if (i == LeftMost && j == Header)
   return Remove();
  else
   {
    unsigned long long count = 0;
    while (i != j)
    {
     SetEntry<T> iter(i); iter.MoveNext();
     if (i != Header) { Remove(i); count++; }
     i = iter._Node;
    }

    return count;
   }
 }

 void Update(SetNode<T>^ Node, T value)
 {
  if (TComparer->Compare(Node->Data, value) != 0) throw gcnew DifferentKeysException();
  T saved = Node->Data;
  Node->Data = value;
  Updated(this, saved, value);
 }

 void Validate(SetNode<T>^ root)
 {
  if (root == nullptr) return;

  if (root->Left != nullptr)
   {
    SetNode<T>^ Left = (SetNode<T>^)root->Left;

    if (TComparer->Compare(Left->Data, root->Data) >= 0)
     throw gcnew OutOfKeyOrderException();

    if (Left->Parent != root)
     throw gcnew TreeInvalidParentException();

    Validate((SetNode<T>^)root->Left);
   }

  if (root->Right != nullptr)
   {
    SetNode<T>^ Right = (SetNode<T>^)root->Right;

    if (TComparer->Compare(Right->Data, root->Data) <= 0)
     throw gcnew OutOfKeyOrderException();

    if (Right->Parent != root)
     throw gcnew TreeInvalidParentException();

    Validate((SetNode<T>^)root->Right);
   }

  unsigned long long DepthLeft = root->Left != nullptr ? Depth(root->Left) : 0;
  unsigned long long DepthRight = root->Right != nullptr ? Depth(root->Right) : 0;

  if (DepthLeft > DepthRight && DepthLeft - DepthRight > 2)
   throw gcnew TreeOutOfBalanceException();

  if (DepthLeft < DepthRight && DepthRight - DepthLeft > 2)
   throw gcnew TreeOutOfBalanceException();
 }

        //*** Static Methods

 static void CombineSets(Set<T>^ A,
                         Set<T>^ B,
                         Set<T>^ R,
                         SetOperation operation)
{
 System::Collections::Generic::IComparer<T>^ TComparer = R->TComparer;
 Calculus::ICloner<T>^ TCloner = R->TCloner;

 SetEntry<T> first1 = A->Begin;
 SetEntry<T> last1 = A->End;
 SetEntry<T> first2 = B->Begin;
 SetEntry<T> last2 = B->End;

            switch (operation)
            {
                case SetOperation::Union:
                    while (first1 != last1 && first2 != last2)
                    {
                        int order = TComparer->Compare(first1.Value, first2.Value);

                        if (order < 0)
                        {
                            R->Add(TCloner->Clone(first1.Value));
                            first1.MoveNext();
                        }

                        else if (order > 0)
                        {
                            R->Add(TCloner->Clone(first2.Value));
                            first2.MoveNext();
                        }

                        else
                        {
                            R->Add(TCloner->Clone(first1.Value));
                            first1.MoveNext();
                            first2.MoveNext();
                        }
                    }
                    while (first1 != last1)
                    {
                        R->Add(TCloner->Clone(first1.Value));
                        first1.MoveNext();
                    }
                    while (first2 != last2)
                    {
                        R->Add(TCloner->Clone(first2.Value));
                        first2.MoveNext();
                    }
                    return;

                case SetOperation::Intersection:
                    while (first1 != last1 && first2 != last2)
                    {
                        int order = TComparer->Compare(first1.Value, first2.Value);

                        if (order < 0)
                            first1.MoveNext();

                        else if (order > 0)
                            first2.MoveNext();

                        else
                        {
                            R->Add(TCloner->Clone(first1.Value));
                            first1.MoveNext();
                            first2.MoveNext();
                        }
                    }
                    return;

                case SetOperation::SymmetricDifference:
                    while (first1 != last1 && first2 != last2)
                    {
                        int order = TComparer->Compare(first1.Value, first2.Value);

                        if (order < 0)
                        {
                            R->Add(TCloner->Clone(first1.Value));
                            first1.MoveNext();
                        }

                        else if (order > 0)
                        {
                            R->Add(TCloner->Clone(first2.Value));
                            first2.MoveNext();
                        }

                        else
                        { first1.MoveNext(); first2.MoveNext(); }
                    }

                    while (first1 != last1)
                    {
                        R->Add(TCloner->Clone(first1.Value));
                        first1.MoveNext();
                    }

                    while (first2 != last2)
                    {
                        R->Add(TCloner->Clone(first2.Value));
                        first2.MoveNext();
                    }
                    return;

                case SetOperation::Difference:
                    while (first1 != last1 && first2 != last2)
                    {
                        int order = TComparer->Compare(first1.Value, first2.Value);

                        if (order < 0)
                        {
                            R->Add(TCloner->Clone(first1.Value));
                            first1.MoveNext();
                        }

                        else if (order > 0)
                        {
                            R->Add(TCloner->Clone(first1.Value));
                            first1.MoveNext();
                            first2.MoveNext();
                        }

                        else
                        { first1.MoveNext(); first2.MoveNext(); }
                    }

                    while (first1 != last1)
                    {
                        R->Add(TCloner->Clone(first1.Value));
                        first1.MoveNext();
                    }
                    return;
            }

            throw gcnew InvalidSetOperationException();
        }

        static Boolean CheckSets(Set<T>^ A,
                                 Set<T>^ B,
                                 SetOperation operation)
        {
            System::Collections::Generic::IComparer<T>^ TComparer = A->TComparer;

            SetEntry<T> first1 = A->Begin;
            SetEntry<T> last1 = A->End;
            SetEntry<T> first2 = B->Begin;
            SetEntry<T> last2 = B->End;

            switch (operation)
            {
                case SetOperation::Equality:
                case SetOperation::Inequality:
                    {
                        bool equals = true;

                        while (first1 != last1 && first2 != last2)
                        {
                            if (TComparer->Compare(first1.Value, first2.Value) == 0)
                            { first1.MoveNext(); first2.MoveNext(); }
                            else
                            { equals = false; break; }
                        }

                        if (equals)
                        {
                            if (first1 != last1) equals = false;
                            if (first2 != last2) equals = false;
                        }

                        if (operation == SetOperation::Equality)
                            return equals;
                        else
                            return !equals;
                    }

                case SetOperation::Subset:
                case SetOperation::Superset:
                    {
                        bool subset = true;

                        while (first1 != last1 && first2 != last2)
                        {
                            int order = TComparer->Compare(first1.Value, first2.Value);

                            if (order < 0)
                            { subset = false; break; }

                            else if (order > 0)
                                first2.MoveNext();

                            else
                            { first1.MoveNext(); first2.MoveNext(); }
                        }

                        if (subset)
                            if (first1 != last1) subset = false;

                        if (operation == SetOperation::Subset)
                            return subset;
                        else
                            return !subset;
                    }
            }

            throw gcnew InvalidSetOperationException();
        }

        static int CompareSets(Set<T>^ A,
                               Set<T>^ B)
        {
            System::Collections::Generic::IComparer<T>^ TComparer = A->TComparer;

            SetEntry<T> first1 = A->Begin;
            SetEntry<T> last1 = A->End;
            SetEntry<T> first2 = B->Begin;
            SetEntry<T> last2 = B->End;

            int Result = 0;

            while (first1 != last1 && first2 != last2)
            {
                Result = TComparer->Compare(first1.Value, first2.Value);
                if (Result == 0)
                { first1.MoveNext(); first2.MoveNext(); }
                else
                    return Result;
            }

            if (first1 != last1) return 1;
            if (first2 != last2) return -1;

            return 0;
        }
    };

}

using namespace Calculus;

int main(array<System::String ^> ^args)
{
    Set<int>^ S = gcnew Set<int>(1, 3, 5 , 6, 7, 9);
    Set<int>^ T = gcnew Set<int>(2, 4, 6 , 7, 8, 9);
    Set<int>^ U = S | T;
    Console::WriteLine(S + " | " + T + " == " + U);
    return 0;
}