//============================================================================//
//											Stack Intersection
//============================================================================//
/*

	There are two available stacks, user can handle both stacks by menu object
   switching. First Fill those 2 stacks, then Ask to find intersection.
   Intersection is done by comparisons & intersetcted elements are shifted
   to a new stack for further application if required.

   Note : No sentinal value techinque is used to remain stacks original elements
   unchanged.

   Fraz Jamshed : warbird43@gmail.com

//============================================================================//
*/

#include <iostream.h>
#include <conio.h>
#include <process.h>

class Node;
class Node
{
	public:
   	int data;
      Node *Next;
};

class Stack;
class Stack
{
	private:
   	Node *Top;
      int Count;

   public:
   	Stack :: Stack();
      Stack :: ~Stack();
      bool Stack :: Push( int & );
      bool Stack :: Pop ( int & );
      bool Stack :: Display ( void );
      void Stack :: topStack( int & );
      void Stack :: Intersection ( Stack & , Stack & );
      int Stack :: getTop();

};


//============================================================================//
//											Constructor
//============================================================================//

Stack :: Stack ()
{
   Count = 0;
   Top = NULL ;
}


//============================================================================//
//											Destructor
//============================================================================//

Stack :: ~Stack ()
{
   while( Top!=NULL )
   {
		Node * temp;
   	temp = Top ;
   	Top = Top->Next;
   	delete temp;
   }
}


//============================================================================//
//											Push Stack
//============================================================================//

bool Stack :: Push ( int & value )
{
	Node * temp = new Node ;

   if(!temp)
   return false;

   temp->data = value;
   temp->Next = NULL;

   if( Top == NULL )
   Top = temp ;

   else
   {
   	temp->Next = Top ;
      Top = temp;
   }

   Count++;

   return true;
}

//============================================================================//
//											Pop Stack
//============================================================================//

bool Stack :: Pop ( int & value )
{
	if( Top == NULL )
   return false;

   else
   {
   	value = Top->data ;
      Node * temp = Top ;
   	Top = Top->Next ;
      delete temp;
   }

   Count--;

   return true;

}

//============================================================================//
//											Display Stack
//============================================================================//

bool Stack :: Display ( void )
{
   if ( !Top )
   	return false;

   else
   {
   	Node * temp = Top;

   	for( ; Top != NULL ; Top = Top->Next )
   	{
   		cout<<Top->data<<endl;
   	}

   	Top = temp ;
   }


   return true;
}

//============================================================================//
//											Top Stack
//============================================================================//

void Stack :: topStack ( int & value )
{
	value = Top->data ;
}

//============================================================================//
//											Menu Launcher
//============================================================================//

void mainMenu( Stack & Object )
{


   int iPin , x ;

	while(1)
	{clrscr();


		cout<<"[1]\t Push\n";
		cout<<"[2]\t Pop\n";
		cout<<"[3]\t Top\n";
		cout<<"[4]\t Display\n";
		cout<<"[0]\t Exit\n";

		cin>>iPin;

		switch ( iPin )
		{

		case 1:

			{
				cout<<"Enter Value :";
				cin>>x;
				bool flag = Object.Push(x);
				if( flag == false )
				cout<<"\a\n================\nMemory Not allocated\n================\n";
				break;
			}

		case 2:

			{

            clrscr();
            int x;
				bool flag = Object.Pop(x);
				if ( flag == false )
				cout<<"\a\n================\nEmpty\n================\n"<<endl;
            else
            cout<<"\n================\nPopped = "<<x<<"\n================\n"<<endl;
            getch();
				break;
			}


		case 3:

			{
            clrscr();
				Object.topStack(x);
            cout<<"Top = "<<x<<endl;
            getch();
				break;
			}


		case 4:

			{
            clrscr();
				bool flag = Object.Display();
            if( flag == false )
            cout<<"Stack Empty";
            getch();
				break;
			}


		case 0:
			return;


		default:
			cout<<"\a";


		}
	}
getch();
}


//============================================================================//
//										   Object Switch
//============================================================================//


void ObjectSwitch( Stack & O, Stack & O2 , Stack & newObj )
{

   char choice = '1';
   while(choice!=27)
   {
      clrscr();

   	cout<<"[1]	Select Stack1"<<endl;
      cout<<"[2]	Select Stack2"<<endl;
      cout<<"[3]	Evaluate Intersection"<<endl;
      cout<<"[Esc]	..Exit"<<endl;

      choice=getch();

      switch( choice )
      {
      	case '1':
         {
         	mainMenu( O );
            break;
         }

         case '2':
         {
         	mainMenu( O2 );
            break;
         }
         case '3':
         {
         	O.Intersection( O2 , newObj );
            break;
         }
         case 27:
         {
         	exit(1);
         }
         default:
         	cout<<"\a";
      }

   }



}

//============================================================================//
//											Get Top
//============================================================================//

int Stack :: getTop()
{
	return this->Top->data;
}

//============================================================================//
//											Stack Intersection
//============================================================================//


void Stack :: Intersection ( Stack &O2 , Stack &newObj )
{


   clrscr();
   cout<<"\nComparisons for Intersection...\n\n";

   {

   if ( !O2.Top && !this->Top )
   {
   	cout<<"\a";
   	return;
   }

   else
   {

      Node * temp = this->Top;

      for(  ; this->Top != NULL ; this->Top = this->Top->Next )
      {
         Node * temp2 = O2.Top;
      	for( ; O2.Top != NULL ; O2.Top = O2.Top->Next )
   		{
   			cout<<this->Top->data<<" :: "<<O2.Top->data<<endl;

            if( this->Top->data == O2.Top->data )
            {
                 newObj.Push(this->Top->data);
            }
   		}

         cout<<endl;
   	   O2.Top = temp2 ;
      }

      this->Top = temp ;

   }
   }

   cout<<"\nNew Stack :: Intersected data from both Stacks...\n\n";

   {

   if ( !newObj.Top )
	{
   	cout<<"Stacks Mutually Exclusive!";
   }

   else
   {
   	Node * temp = newObj.Top;

   	for( ; newObj.Top != NULL ; newObj.Top = newObj.Top->Next )
   	{
   		cout<<newObj.Top->data<<endl;
   	}

   	newObj.Top = temp ;
   }

   }


   getch();
}



//============================================================================//
//											 * * *
//============================================================================//


main()
{
	Stack Object1 ;
   Stack Object2 ;
   Stack Object3 ;
   ObjectSwitch(Object1,Object2,Object3);
}