# include <iostream.h>
 # include   <stdlib.h>
 # include   <string.h>
 # include    <conio.h>

 /**************************************************************************///--------------------------  Class Definition  --------------------------///**************************************************************************///--------------------------------  Set  ---------------------------------//class Set
 {
    private:
       int data;
       int size;

       staticint flag;
       staticintvalue;
       staticint cur;

       Set *LeftNode;
       Set *RightNode;

    public:
       Set *RootNode;
       Set *Location;
       Set *Parent;

       Set( );
       Set* InsertElement(Set*, constint);
       void DeleteElementWith0Or1Child( );
       void DeleteElementWith2Child( );
       void getElementAtPos(Set*, constint);
       int getElementAt(Set*, constint);
       void Print(Set*);
       void Print( );
       void PrintAscending(Set*);
       void PrintDescending(Set*);

       int Size( );
       void Empty( );
       int IsEmpty( );
       void Read(constchar*);
       void AddElement(constint);
       void DeleteElement(constint);
       void PrintAscending( );
       void PrintDescending( );
       int IsAnElement(constint);
       Set Union(const Set set);
       Set Intersection(const Set set);
       int IsASubSet(const Set subset);
       intoperator==(const Set set);
       Set operator-(const Set set);
 };

 int Set::flag = 1;
 int Set::value = 0;
 int Set::cur = 0;

 /*************************************************************************///------------------------  Function Definitions  -----------------------///*************************************************************************///-------------------------------  Set( )  ------------------------------//

 Set::Set( )
 {
    RootNode = NULL;
    LeftNode = NULL;
    RightNode = NULL;

    data = 0;
    size = 0;
 }

 //--------------------------  InsertElement( )  ------------------------//

 Set* Set::InsertElement(Set *Node, constint data)
 {
    if (Node == NULL)
    {
       Set *Temp;

       Temp = new Set;

       Temp->data = data;
       Node = Temp;
       Node->LeftNode = NULL;
       Node->RightNode = NULL;

       size ++;
    }

    else
    {
       Parent = Node;

       if (data > Node->data)
       {
      if (Node->RightNode == NULL)
         Node->RightNode = InsertElement(Node->RightNode, data);

      else
         InsertElement(Node->RightNode, data);
       }

       else
       {
      if (Node->LeftNode == NULL)
         Node->LeftNode = InsertElement(Node->LeftNode, data);

      else
         InsertElement(Node->LeftNode,data);
       }
    }

    return Node;
 }

 //------------------------------  Size( )  -------------------------------//int Set::Size( )
 {
    return size;
 }

 //-----------------------------  IsEmpty( )  -----------------------------//int Set::IsEmpty( )
 {
    if (RootNode == NULL)
       return 1;

    return 0;
 }

 //-------------------------------  Empty( )  -----------------------------//void Set::Empty( )
 {
    for (int i = size; i >= 1; i--)
    {
       int num = getElementAt(RootNode, i);

       flag = 0;

       DeleteElement(num);

       flag = 1;
    }

    RootNode = NULL;
    size = 0;
 }

 //---------------------------  getElementAtPos( )  -----------------------//void Set::getElementAtPos(Set *Node, constint req)
 {
    cur ++;

    if (cur == req)
       value = Node->data;

    if (Node->LeftNode != NULL)
       getElementAtPos(Node->LeftNode, req);

    if (Node->RightNode != NULL)
       getElementAtPos(Node->RightNode, req);
 }

 int Set::getElementAt(Set* Node, constint req)
 {
    value = 0;
    cur = 0;

    getElementAtPos(Node, req);

    returnvalue;
 }

 //----------------------------------  Print( )  --------------------------//void Set::Print(Set *Node)
 {
    if (Node == NULL)
    {  }

    else
    {
       cout << " " << Node->data;

       if (Node->LeftNode != NULL)
      Print(Node->LeftNode);

       if (Node->RightNode != NULL)
      Print(Node->RightNode);
    }
 }

 void Set::Print( )
 {
    Print(RootNode);
 }

 //---------------------------  PrintAscending( )  ------------------------//void Set::PrintAscending(Set *Node)
 {
    if (Node==NULL)
    {  }

    else
    {
       if (Node->LeftNode != NULL)
      PrintAscending(Node->LeftNode);

       cout << " " << Node->data;

       if (Node->RightNode != NULL)
      PrintAscending(Node->RightNode);
    }
 }

 void Set::PrintAscending( )
 {
    PrintAscending(RootNode);
 }

 //---------------------------  PrintDescending( )  -----------------------//void Set::PrintDescending(Set *Node)
 {
    if (Node == NULL)
    {  }

    else
    {
       if (Node->RightNode != NULL)
      PrintDescending(Node->RightNode);

       cout << " " << Node->data;

       if (Node->LeftNode != NULL)
      PrintDescending(Node->LeftNode);
    }
 }

 void Set::PrintDescending( )
 {
    PrintDescending(RootNode);
 }

 //---------------------------  IsAnElement( )  ---------------------------//int Set::IsAnElement(constint key)
 {
    int depth = 1;
    int left_right = 0;

    Set *Pointer = NULL;
    Set *Save = NULL;

    Location = NULL;
    Parent = NULL;

    if (RootNode == NULL)
    {
       Location = NULL;
       Parent = NULL;
    }

    elseif (key == RootNode->data)
    {
       Location = RootNode;
       Parent = NULL;

       depth = 1;
    }

    else
    {
       if (key < RootNode->data)
       {
      Pointer = RootNode->LeftNode;

      left_right = 1;
       }

       else
       {
      Pointer = RootNode->RightNode;

      left_right = 2;
       }

       Save = RootNode;

       while (Pointer != NULL)
       {
      depth += 1;

      if (key == Pointer->data)
      {
         Location = Pointer;
         Parent = Save;

         break;
      }

      elseif(key < Pointer->data)
      {
         Save = Pointer;
         Pointer = Pointer->LeftNode;
      }

      elseif(key > Pointer->data)
      {
         Save = Pointer;
         Pointer = Pointer->RightNode;
      }
       }
    }

    if (flag == 1)
    {
       if (Location == NULL)
       {
      Parent = NULL;

      cout << "\n\n*** " << key << " is not found in the Set. " << endl;
       }

       elseif (Location != NULL)
       {
      if (left_right == 0)
         cout << "\n\n*** " << key << " is the Root Node." << endl;

      elseif (left_right == 1)
         cout << "\n\n*** " << key << " lies at the Left side of the Root Node ";

      elseif (left_right == 2)
         cout << "\n\n*** " << key << " lies at the Right side of the Root Node ";

      if (left_right)
         cout << "and at the depth level " << depth << endl;
       }
    }

    if (Location != NULL)
       return 1;

    return 0;
 }

 //--------------------  DeleteElementWith0Or1Child( )  -------------------//void Set::DeleteElementWith0Or1Child( )
 {
    Set *Child;

    if (Location->LeftNode == NULL && Location->RightNode == NULL)
       Child = NULL;

    elseif (Location->LeftNode != NULL)
       Child = Location->LeftNode;

    else
       Child = Location->RightNode;

    if (Parent != NULL)
    {
       if (Location == Parent->LeftNode)
      Parent->LeftNode = Child;

       else
      Parent->RightNode = Child;
    }

    else
       RootNode = Child;
 }

 //----------------------  DeleteElementWith2Child( )  --------------------//void Set::DeleteElementWith2Child( )
 {
    Set *Pointer = Location->RightNode;
    Set *Save = Location;

    Set *Sucessor;
    Set *Parent_sucessor;

    while (Pointer->LeftNode != NULL)
    {
       Save = Pointer;
       Pointer = Pointer->LeftNode;
    }

    Sucessor = Pointer;
    Parent_sucessor = Save;

    Set *temp_loc = Location;
    Set *temp_par = Parent;

    Location = Sucessor;
    Parent = Parent_sucessor;

    DeleteElementWith0Or1Child( );

    Location = temp_loc;
    Parent = temp_par;

    if (Parent != NULL)
    {
       if (Location == Parent->LeftNode)
      Parent->LeftNode = Sucessor;

       else
      Parent->RightNode = Sucessor;
    }

    else
       RootNode = Sucessor;

    Sucessor->LeftNode = Location->LeftNode;
    Sucessor->RightNode = Location->RightNode;
 }

 //--------------------------  DeleteElement( )  --------------------------//void Set::DeleteElement(constint key)
 {
    IsAnElement(key);

    if (RootNode == NULL)
    {
       if (flag == 1)
      cout << "\n\n*** Error : Set is empty. \n" << endl;
    }

    elseif (Location == NULL)
    {
       if (flag == 1)
      cout << "\n\n*** " << key << "  does not exists in the Set \n" << endl;
    }

    else
    {
       if (Location->RightNode != NULL && Location->LeftNode != NULL)
      DeleteElementWith2Child( );

       else
      DeleteElementWith0Or1Child( );

       size --;

       if (flag == 1)
      cout << "*** " << key << " is deleted from the Set." << endl;
    }
 }

 //----------------------------  AddElement( )  ---------------------------//void Set::AddElement(constint num)
 {
    if (RootNode == NULL)
       RootNode = InsertElement(RootNode, num);

    else
    {
       flag = 0;

       IsAnElement(num);

       flag = 1;

       if (Location==NULL)
      InsertElement(RootNode, num);
    }
 }

 //--------------------------------  Read( )  -----------------------------//void Set::Read(constchar* Numbers)
 {
    char Temp[255] = {NULL};

    strcpy(Temp, Numbers);

    char* Ptr = strtok(Temp,",");

    int num = 0;

    flag = 0;

    while (Ptr != NULL)
    {
       num = atoi(Ptr);

       AddElement(num);

       Ptr = strtok(NULL, ",");
    }

    flag = 1;
 }

 //----------------------------------  Union( )  --------------------------//

 Set Set::Union(const Set set)
 {
    Set C;

    flag = 0;

    for (int i = 1; i <= size; i ++)
       C.AddElement(getElementAt(RootNode, i));

    for (int j = 1; j <= set.Size( ); j ++)
       C.AddElement(getElementAt(set.RootNode, j));

   flag = 1;

    return C;
 }

 //---------------------------  Intersection( )  --------------------------//

 Set Set::Intersection(const Set set)
 {
    Set C;

    for (int i = 1; i <= size; i ++)
    {
       int num = getElementAt(RootNode, i);

       flag = 0;

       if (set.IsAnElement(num) == 1)
      C.AddElement(num);

       flag = 1;
    }

    return C;
 }

 //----------------------------  Operator==( )  ---------------------------//int Set::operator==(const Set set)
 {
    if (size != set.Size( ))
       return 0;

    int eFlag = 1;

    for (int i = 1; i <= size; i ++)
    {
       int num = getElementAt(RootNode, i);

       flag = 0;

       if (set.IsAnElement(num) == 0)
       {
      eFlag = 0;

      break;
       }

       flag = 1;
    }

    return eFlag;
 }

 //-----------------------------  Operator-( )  ---------------------------//

 Set Set::operator-(const Set set)
 {
    Set C;

    for (int i = 1; i <= size; i ++)
       C.AddElement(getElementAt(RootNode, i));

    for (int j = 1; j <= set.Size( ); j ++)
    {
       int num = getElementAt(set.RootNode, j);

       flag = 0;

       C.DeleteElement(num);

       flag = 1;
    }

    return C;
 }

 //-----------------------------  IsASubSet( )  ---------------------------//int Set::IsASubSet(const Set subset)
 {
    if (size == 0)
       return 0;

    if (subset.Size( ) == 0)
       return 1;

    int eFlag = 1;

    for (int i = 1; i <= size; i ++)
    {
       int num = getElementAt(subset.RootNode, i);

       flag = 0;

       if (IsAnElement(num) == 0)
       {
      eFlag = 0;
      break;
       }

       flag = 1;
    }

    return eFlag;
 }

 /*************************************************************************///-------------------------------  main( )  -----------------------------///*************************************************************************/int main( )
 {
    clrscr( );

    Set A;

    cout << "Read() & AddElement() Demonstration" << endl;
    cout << "***********************************" << endl;

    cout << "\nRead(\"5,3,1,2,0\")" << endl;
    A.Read("5,3,1,2,0");

    cout << "AddElement(4)" << endl;
    cout << "AddElement(9)" << endl;
    cout << "AddElement(4)" << endl;
    A.AddElement(4);
    A.AddElement(9);
    A.AddElement(4);

    cout << "\nSet A =";
    A.Print( );

    getch( );

    cout << "\n\n\nPrintAscending() Demonstration" << endl;
    cout << "******************************" << endl;

    cout << "\nAscending Order :";
    A.PrintAscending( );

    getch( );

    cout << "\n\n\nPrintDescending() Demonstration" << endl;
    cout << "*******************************" << endl;

    cout << "\nDescending Order :";
    A.PrintDescending( );

    getch( );

    cout << "\n\n\nDeleteElement() Demonstration" << endl;
    cout << "*****************************" << endl;

    cout << "DeleteElement(5)" << endl;
    A.DeleteElement(5);

    cout << "\nSet =";
    A.Print( );

    getch( );

    cout << "\n\n\nIsAnElement() Demonstration" << endl;
    cout << "***************************" << endl;

    A.IsAnElement(2);

    getch( );

    cout << "\n\n\nSize() Demonstration" << endl;
    cout << "********************" << endl;

    cout << "\nSet Size = " << A.Size( ) << endl;

    getch( );

    cout << "\n\n\nIsEmpty() Demonstration" << endl;
    cout << "******************************" << endl;

    if (A.IsEmpty( ) == 1)
       cout << "\nThe Set is Empty" << endl;

    else
       cout << "\nThe Set Is Not Empty" << endl;

    getch( );

    cout << "\n\n\nUnion() Demonstration" << endl;
    cout << "*********************" << endl;

    Set B, C;

    B.Read("1,7,0,4,6,8,5");

    cout << "\nSet A =";
    A.Print( );

    cout << "\nSet B =";
    B.Print( );

    C = A.Union(B);

    cout << "\n\nC = A u B =";
    C.Print( );

    getch( );

    cout << "\n\n\nIntersection() Demonstration" << endl;
    cout << "****************************" << endl;

    C = A.Intersection(B);

    cout << "\n\nC = A n B =";
    C.Print( );

    getch( );

    cout << "\n\n\nEmpty() Demonstration" << endl;
    cout << "*********************" << endl;

    C.Empty( );

    if (C.IsEmpty( ) == 1)
       cout << "\n\nThe Set C is Empty" << endl;

    else
       cout << "\n\nThe Set C Is Not Empty" << endl;

    getch( );

    cout << "\n\n\nOperator == Demonstration" << endl;
    cout << "*************************" << endl;

    if (A == B)
      cout << "\nSet A = Set B" << endl;

    else
      cout << "\nSet A != Set B" << endl;

    getch( );

    cout << "\n\n\nOperator - Demonstration" << endl;
    cout << "************************" << endl;

    C = (A - B);

    cout << "\nC = A - B = ";
    C.Print( );

    getch( );

    cout << "\n\n\nIsASubSet() Demonstration" << endl;
    cout << "*************************" << endl;

    B.Empty( );

    B.Read("4,1,2");

    cout << "\n\nSet A =";
    A.Print( );

    cout << "\nSet B =";
    B.Print( );

    if (A.IsASubSet(B) == 1)
       cout << "\n\nSet B is a Subset of Set A" << endl;

    else
       cout << "\n\nSet B is not Subset of Set A" << endl;

    getch( );
    return 0;
 }