== Code ==

// Finite Ordered Sets - 4State - Balanced

using System;
using System.Collections.Generic;

public enum Direction { FromLeft, FromRight };

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

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

public class Node
{
    public Node Left;
    public Node Right;
    public Node Parent;
    public State Balance;

    public Node()
    {
        Left = this;
        Right = this;
        Parent = null;
        Balance = State.Header;
    }

    public Node(Node p)
    {
        Left = null;
        Right = null;
        Parent = p;
        Balance = State.Balanced;
    }

    public bool IsHeader
    { get { return Balance == State.Header; } }
}

public class SetNode<T> : Node
{
    public T Data;

    public SetNode() { }

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

    public override int GetHashCode()
    {
        return Data.GetHashCode();
    }
}

class Utility // Nongeneric Tree Balancing
{
    static void RotateLeft(ref Node Root)
    {
        Node Parent = Root.Parent;
        Node x = Root.Right;

        Root.Parent = x;
        x.Parent = Parent;
        if (x.Left != null) x.Left.Parent = Root;

        Root.Right = x.Left;
        x.Left = Root;
        Root = x;
    }

    static void RotateRight(ref Node Root)
    {
        Node Parent = Root.Parent;
        Node x = Root.Left;

        Root.Parent = x;
        x.Parent = Parent;
        if (x.Right != null) x.Right.Parent = Root;

        Root.Left = x.Right;
        x.Right = Root;
        Root = x;
    }

    static void BalanceLeft(ref Node Root)
    {
        Node Left = Root.Left;

        switch (Left.Balance)
        {
            case State.LeftHigh:
                Root.Balance = State.Balanced;
                Left.Balance = State.Balanced;
                RotateRight(ref Root);
                break;

            case State.RightHigh:
                {
                    Node subRight = Left.Right;
                    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(ref Left);
                    Root.Left = Left;
                    RotateRight(ref Root);
                }
                break;

            case State.Balanced:
                Root.Balance = State.LeftHigh;
                Left.Balance = State.RightHigh;
                RotateRight(ref Root);
                break;
        }
    }

    static void BalanceRight(ref Node Root)
    {
        Node Right = Root.Right;

        switch (Right.Balance)
        {
            case State.RightHigh:
                Root.Balance = State.Balanced;
                Right.Balance = State.Balanced;
                RotateLeft(ref 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(ref Right);
                    Root.Right = Right;
                    RotateLeft(ref Root);
                }
                break;

            case State.Balanced:
                Root.Balance = State.RightHigh;
                Right.Balance = State.LeftHigh;
                RotateLeft(ref Root);
                break;
        }
    }

    public static void BalanceSet(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(ref Parent.Parent);
                        else if (Parent.Left == Root)
                            BalanceLeft(ref Parent.Left);
                        else
                            BalanceLeft(ref 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(ref Parent.Parent);
                        else if (Parent.Left == Root)
                            BalanceRight(ref Parent.Left);
                        else
                            BalanceRight(ref Parent.Right);
                        Taller = false;
                        break;
                }
            }

            if (Taller) // skip up a level
            {
                if (Parent.IsHeader)
                    Taller = false;
                else
                {
                    Root = Parent;
                    From = NextFrom;
                }
            }
        }
    }

    public static void BalanceSetRemove(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(ref Parent.Parent);
                        else if (Parent.Left == Root)
                            BalanceRight(ref Parent.Left);
                        else
                            BalanceRight(ref 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(ref Parent.Parent);
                        else if (Parent.Left == Root)
                            BalanceLeft(ref Parent.Left);
                        else
                            BalanceLeft(ref Parent.Right);
                        break;
                }
            }

            if (Shorter)
            {
                if (Parent.IsHeader)
                    Shorter = false;
                else
                {
                    From = NextFrom;
                    Root = Parent;
                }
            }
        }
    }

    public static Node PreviousItem(Node Node)
    {
        if (Node.IsHeader) { return Node.Right; }

        if (Node.Left != null)
        {
            Node = Node.Left;
            while (Node.Right != null) Node = Node.Right;
        }
        else
        {
            Node y = Node.Parent;
            if (y.IsHeader) return y;
            while (Node == y.Left) { Node = y; y = y.Parent; }
            Node = y;
        }
        return Node;
    }

    public static Node NextItem(Node Node)
    {
        if (Node.IsHeader) return Node.Left;

        if (Node.Right != null)
        {
            Node = Node.Right;
            while (Node.Left != null) 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;
    }

    public static ulong Depth(Node Root)
    {
        if (Root != null)
        {
            ulong Left = Root.Left != null ? Depth(Root.Left) : 0;
            ulong Right = Root.Right != null ? Depth(Root.Right) : 0;
            return Left < Right ? Right + 1 : Left + 1;
        }
        else
            return 0;
    }

    static void SwapNodeReference(ref Node First,
                                  ref Node Second)
    { Node Temporary = First; First = Second; Second = Temporary; }

    public static void SwapNodes(Node A, Node B)
    {
        if (B == A.Left)
        {
            if (B.Left != null) B.Left.Parent = A;
            if (B.Right != null) B.Right.Parent = A;

            if (A.Right != null) 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(ref A.Right, ref B.Right);
        }
        else if (B == A.Right)
        {
            if (B.Right != null) B.Right.Parent = A;
            if (B.Left != null) B.Left.Parent = A;

            if (A.Left != null) 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(ref A.Left, ref B.Left);
        }
        else if (A == B.Left)
        {
            if (A.Left != null) A.Left.Parent = B;
            if (A.Right != null) A.Right.Parent = B;

            if (B.Right != null) 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(ref A.Right, ref B.Right);
        }
        else if (A == B.Right)
        {
            if (A.Right != null) A.Right.Parent = B;
            if (A.Left != null) A.Left.Parent = B;

            if (B.Left != null) 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(ref A.Left, ref B.Left);
        }
        else
        {
            if (A.Parent == B.Parent)
                SwapNodeReference(ref A.Parent.Left, ref 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 != null) B.Left.Parent = A;
            if (B.Right != null) B.Right.Parent = A;

            if (A.Left != null) A.Left.Parent = B;
            if (A.Right != null) A.Right.Parent = B;

            SwapNodeReference(ref A.Left, ref B.Left);
            SwapNodeReference(ref A.Right, ref B.Right);
            SwapNodeReference(ref A.Parent, ref B.Parent);
        }

        State Balance = A.Balance;
        A.Balance = B.Balance;
        B.Balance = Balance;
    }
}

public struct SetEntry<T> : IEnumerator<T>
{
    public SetEntry(Node N) { _Node = N; }

    public T Value
    {
        get
        {
            return ((SetNode<T>)_Node).Data;
        }
    }

    public bool IsEnd { get { return _Node.IsHeader; } }

    public bool MoveNext()
    {
        _Node = Utility.NextItem(_Node);
        return _Node.IsHeader ? false : true;
    }

    public bool MovePrevious()
    {
        _Node = Utility.PreviousItem(_Node);
        return _Node.IsHeader ? false : true;
    }

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

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

    public void Reset()
    {
        while (!MoveNext()) ;
    }

    object System.Collections.IEnumerator.Current
    { get { return ((SetNode<T>)_Node).Data; } }

    T IEnumerator<T>.Current
    { get { return ((SetNode<T>)_Node).Data; } }

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

    public override bool Equals(object o) { return _Node == ((SetEntry<T>)o)._Node; }

    public override int GetHashCode() { return _Node.GetHashCode(); }

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

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

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

    public override string ToString()
    {
        return Value.ToString();
    }

    public void Dispose() { }

    public Node _Node;
}

class Set<T> : IEnumerable<T>
{
    IComparer<T> Comparer;
    Node Header;
    ulong Nodes;

    //*** Constructors ***

    public Set()
    {
        Comparer = Comparer<T>.Default;
        Header = new Node();
        Nodes = 0;
    }

    public Set(IComparer<T> c)
    {
        Comparer = c;
        Header = new Node();
        Nodes = 0;
    }

    //*** Properties ***

    SetNode<T> Root
    {
        get { return (SetNode<T>)Header.Parent; }
        set { Header.Parent = value; }
    }

    Node LeftMost
    {
        get { return Header.Left; }
        set { Header.Left = value; }
    }

    Node RightMost
    {
        get { return Header.Right; }
        set { Header.Right = value; }
    }

    public SetEntry<T> Begin
    { get { return new SetEntry<T>(Header.Left); } }

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

    public ulong Length { get { return Nodes; } }

    public ulong Depth { get { return Utility.Depth(Root); } }

    //*** Operators ***

    public bool this[T key] { get { return Search(key); } }

    public static Set<T> operator +(Set<T> set, T t)
    {
        set.Add(t); return set;
    }

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

    public static Set<T> operator |(Set<T> A, Set<T> B)
    {
        Set<T> U = new Set<T>(A.Comparer);
        CombineSets(A, B, U, SetOperation.Union);
        return U;
    }

    public static Set<T> operator &(Set<T> A, Set<T> B)
    {
        Set<T> I = new Set<T>(A.Comparer);
        CombineSets(A, B, I, SetOperation.Intersection);
        return I;
    }

    public static Set<T> operator ^(Set<T> A, Set<T> B)
    {
        Set<T> S = new Set<T>(A.Comparer);
        CombineSets(A, B, S, SetOperation.SymmetricDifference);
        return S;
    }

    public static Set<T> operator -(Set<T> A, Set<T> B)
    {
        Set<T> S = new Set<T>(A.Comparer);
        CombineSets(A, B, S, SetOperation.Difference);
        return S;
    }

    public static bool operator ==(Set<T> A, Set<T> B)
    {
        return CheckSets(A, B, SetOperation.Equality);
    }

    public static bool operator !=(Set<T> A, Set<T> B)
    {
        return CheckSets(A, B, SetOperation.Inequality);
    }

    public override bool Equals(object o)
    {
        return CheckSets(this, (Set<T>)o, SetOperation.Equality);
    }


    //*** Methods ***

    public void Add(T key)
    {
        if (Root == null)
        {
            Root = new SetNode<T>(key, Header);
            LeftMost = RightMost = Root;
        }
        else
        {
            SetNode<T> Search = Root;
            for (; ; )
            {
                int Compare = Comparer.Compare(key, Search.Data);

                if (Compare == 0) // Item Exists
                    throw new EntryAlreadyExistsException();

                else if (Compare < 0)
                {
                    if (Search.Left != null)
                        Search = (SetNode<T>)Search.Left;
                    else
                    {
                        Search.Left = new SetNode<T>(key, Search);
                        if (LeftMost == Search) LeftMost = (SetNode<T>)Search.Left;
                        Utility.BalanceSet(Search, Direction.FromLeft);
                        Nodes++;
                        break;
                    }
                }

                else
                {
                    if (Search.Right != null)
                        Search = (SetNode<T>)Search.Right;
                    else
                    {
                        Search.Right = new SetNode<T>(key, Search);
                        if (RightMost == Search) RightMost = (SetNode<T>)Search.Right;
                        Utility.BalanceSet(Search, Direction.FromRight);
                        Nodes++;
                        break;
                    }
                }
            }
        }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    { return new SetEntry<T>(Header); }

    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    { return new SetEntry<T>(Header); }

    public override int GetHashCode()
    {
        return GetHashCode((SetNode<T>)Header.Parent);
    }

    int GetHashCode(SetNode<T> Root)
    {
        if (Root != null)
        {
            int HashCode = Root.GetHashCode();

            if (Root.Left != null)
                HashCode += GetHashCode((SetNode<T>)Root.Left);

            if (Root.Right != null)
                HashCode += GetHashCode((SetNode<T>)Root.Right);

            return HashCode;
        }

        return 0;
    }


    public void Remove(T key)
    {
        SetNode<T> root = Root;

        for (; ; )
        {
            if (root == null)
                throw new EntryNotFoundException();

            int Compare = Comparer.Compare(key, root.Data);

            if (Compare < 0)
                root = (SetNode<T>)root.Left;

            else if (Compare > 0)
                root = (SetNode<T>)root.Right;

            else // Item is found
            {
                if (root.Left != null && root.Right != null)
                {
                    SetNode<T> replace = (SetNode<T>)root.Left;
                    while (replace.Right != null) replace = (SetNode<T>)replace.Right;
                    Utility.SwapNodes(root, replace);
                }

                SetNode<T> Parent = (SetNode<T>)root.Parent;

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

                if (LeftMost == root)
                {
                    SetEntry<T> e = new SetEntry<T>(root); e.MoveNext();

                    if (e._Node.IsHeader)
                    { LeftMost = Header; RightMost = Header; }
                    else
                        LeftMost = e._Node;
                }
                else if (RightMost == root)
                {
                    SetEntry<T> e = new SetEntry<T>(root); e.MovePrevious();

                    if (e._Node.IsHeader)
                    { LeftMost = Header; RightMost = Header; }
                    else
                        RightMost = e._Node;
                }

                if (root.Left == null)
                {
                    if (Parent == Header)
                        Header.Parent = root.Right;
                    else if (Parent.Left == root)
                        Parent.Left = root.Right;
                    else
                        Parent.Right = root.Right;

                    if (root.Right != null) 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 != null) root.Left.Parent = Parent;
                }

                Utility.BalanceSetRemove(Parent, From);
                Nodes--;
                break;
            }
        }
    }

    public bool Search(T key)
    {
        if (Root == null)
            return false;
        else
        {
            SetNode<T> Search = Root;

            do
            {
                int Result = Comparer.Compare(key, Search.Data);

                if (Result < 0) Search = (SetNode<T>)Search.Left;

                else if (Result > 0) Search = (SetNode<T>)Search.Right;

                else break;

            } while (Search != null);

            if (Search == null)
                return false;
            else
                return true;
        }
    }

    public override string ToString()
    {
        string StringOut = "{";

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

        while (start != end)
        {
            string new_StringOut = start.Value.ToString();
            if (start != last) new_StringOut = new_StringOut + ",";
            StringOut = StringOut + new_StringOut;
            ++start;
        }

        StringOut = StringOut + "}";
        return StringOut;
    }

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

        Validate(Root);

        if (Root != null)
        {
            SetNode<T> x = Root;
            while (x.Left != null) x = (SetNode<T>)x.Left;

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

            SetNode<T> y = Root;
            while (y.Right != null) y = (SetNode<T>)y.Right;

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

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

        if (root.Left != null)
        {
            SetNode<T> Left = (SetNode<T>)root.Left;

            if (Comparer.Compare(Left.Data, root.Data) >= 0)
                throw new OutOfKeyOrderException();

            if (Left.Parent != root)
                throw new TreeInvalidParentException();

            Validate((SetNode<T>)root.Left);
        }

        if (root.Right != null)
        {
            SetNode<T> Right = (SetNode<T>)root.Right;

            if (Comparer.Compare(Right.Data, root.Data) <= 0)
                throw new OutOfKeyOrderException();

            if (Right.Parent != root)
                throw new TreeInvalidParentException();

            Validate((SetNode<T>)root.Right);
        }

        ulong depth_Left = root.Left != null ? Utility.Depth(root.Left) : 0;
        ulong depth_Right = root.Right != null ? Utility.Depth(root.Right) : 0;

        if (depth_Left > depth_Right && depth_Left - depth_Right > 2)
            throw new TreeOutOfBalanceException();

        if (depth_Left < depth_Right && depth_Right - depth_Left > 2)
            throw new TreeOutOfBalanceException();
    }

    public static void CombineSets(Set<T> A,
                                   Set<T> B,
                                   Set<T> R,
                                   SetOperation operation)
    {
        IComparer<T> TComparer = R.Comparer;
        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(First1.Value);
                        First1.MoveNext();
                    }

                    else if (Order > 0)
                    {
                        R.Add(First2.Value);
                        First2.MoveNext();
                    }

                    else
                    {
                        R.Add(First1.Value);
                        First1.MoveNext();
                        First2.MoveNext();
                    }
                }
                while (First1 != Last1)
                {
                    R.Add(First1.Value);
                    First1.MoveNext();
                }
                while (First2 != Last2)
                {
                    R.Add(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(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(First1.Value);
                        First1.MoveNext();
                    }

                    else if (Order > 0)
                    {
                        R.Add(First2.Value);
                        First2.MoveNext();
                    }

                    else
                    { First1.MoveNext(); First2.MoveNext(); }
                }

                while (First1 != Last1)
                {
                    R.Add(First1.Value);
                    First1.MoveNext();
                }

                while (First2 != Last2)
                {
                    R.Add(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(First1.Value);
                        First1.MoveNext();
                    }

                    else if (Order > 0)
                    {
                        R.Add(First1.Value);
                        First1.MoveNext();
                        First2.MoveNext();
                    }

                    else
                    { First1.MoveNext(); First2.MoveNext(); }
                }

                while (First1 != Last1)
                {
                    R.Add(First1.Value);
                    First1.MoveNext();
                }
                return;
        }

        throw new InvalidSetOperationException();
    }

    public static bool CheckSets(Set<T> A,
                                 Set<T> B,
                                 SetOperation operation)
    {
        IComparer<T> TComparer = A.Comparer;
        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 new InvalidSetOperationException();
    }
}

public class EntryNotFoundException : Exception
{
    static String message = "The requested entry could not be located in the specified collection.";

    public EntryNotFoundException() : base(message) { }
}

public class EntryAlreadyExistsException : Exception
{
    static String message = "The requested entry already resides in the collection.";

    public EntryAlreadyExistsException() : base(message) { }
}

public class InvalidEndItemException : Exception
{
    static String message = "The validation routines detected that the end item of a tree is invalid.";

    public InvalidEndItemException() : base(message) { }
}

public class InvalidEmptyTreeException : Exception
{
    static String message = "The validation routines detected that an empty tree is invalid.";

    public InvalidEmptyTreeException() : base(message) { }
}

public class OutOfKeyOrderException : Exception
{
    static String message = "A trees was found to be out of key order.";

    public OutOfKeyOrderException() : base(message) { }
}

public class TreeInvalidParentException : Exception
{
    static String message = "The validation routines detected that the Parent structure of a tree is invalid.";

    public TreeInvalidParentException() : base(message) { }
}

public class TreeOutOfBalanceException : Exception
{
    static String message = "The validation routines detected that the tree is out of State.";

    public TreeOutOfBalanceException() : base(message) { }
}

public class InvalidSetOperationException : Exception
{
    static String message = "An invalid set operation was requested.";

    public InvalidSetOperationException() : base(message) { }
}

class Program
{
    static void Main()
    {
        Set<string> s = new Set<string>() {"S0","S1","S2","S3","S4",
                                           "S5","S6","S7","S8","S9"};

        Console.WriteLine("Depth = {0}", s.Depth);

        s.Validate();

        for (int i = 0; i < 10; i += 2)
            s.Remove("S" + i.ToString());

        Console.WriteLine("Depth = {0}", s.Depth);

        s.Validate();

        Console.WriteLine("{0}", s);

        Set<int> A = new Set<int>() { 1, 3, 5, 7 };
        Set<int> B = new Set<int>() { 2, 4, 6, 8 };

        Set<int> U = A | B;

        Console.WriteLine("{0} | {1} == {2}", A, B, U);
    }
}