#include <iostream.h>
// a disk with a value , which is an element of the stack ,tower in this case
class Disk    
{
public:
int value;
Disk* next;
};//class Disk

class Tower //a stack data structure representing a tower 
{
public:
int size;
Disk* current;
Tower()
{
  size=0;
  current=NULL;
}//default constructor


int peep();
bool push(int);
bool pop();
bool isEmpty();
int getTowerSize();
void printTowerSize();
void printTowerDisks();
void printTowerMenu();

};

int Tower::peep()
{
	return this->current->value;
}

bool Tower::push(int ele)
{
Disk*	temp;

temp=new Disk;

	if(current==NULL)
	{
		temp->next=NULL;

	}
	else
	{
		temp->next=current;
	}
	temp->value=ele;
	this->current=temp;
	
	size++;
    return false;
}

bool Tower::pop()
{
	if(isEmpty())
	{
	cout<<"\nTower is Empty\n";      
	return false;
	}
	else
	{
	current=current->next;
	size=size--;
	}
	return true;
}

bool Tower::isEmpty()
{
	if(getTowerSize()==0)
	return true;
	
	return false;
}

int Tower::getTowerSize()
{
return size;
}//returns size of the Tower

void Tower::printTowerSize()
{
cout<<"\nThe Size of the Tower:"<<size<<"\n";
}//print the Tower size

void Tower::printTowerDisks()
{
	if(this->isEmpty())
	{
	cout<<"-----\n";
	cout<<" "<<endl;
	cout<<"-----\n";
	return;
	}
Disk *curr2;	
curr2=this->current ;
     
		cout<<"-----\n";
		cout<<"Tower\n";
		cout<<"-----\n";
		int i=0;
		while(curr2 !=NULL)
		{
			if(i>4)
			break;

			i++;
			cout<<" |"<<curr2->value<<"|\n";
			curr2=curr2->next;
		}
}// print the Tower

void createSourceTower(Tower *source,int numberOfDisks)
{
	for(int i=numberOfDisks;i>0;i--)
	{
      source->push(i);               
	}

}


void moveDisk(Tower *source,Tower *dest) // movinng a disk from source to destionation
 {
dest->push(source->current->value );
source->pop();
 }


void hanoi( int N, Tower *source, Tower *dest,Tower  *aux ) // move N disks from source to destination
{
    if (N > 0 )
	{
	hanoi(N - 1, source, aux, dest);      //move n-1 disks from source to auxxilary (sub problem)
	moveDisk(source,dest);                //move nTH disk from source to destination 
	hanoi(N - 1, aux, dest, source);      //move n-1 disks from auxillary to destination (sub problem)
	}

}


void main()
{
Tower *source,*destination,*auxillary; 
//Towers required for the 3 towers source destination and auxillary
source=new Tower;
destination=new Tower;
auxillary=new Tower;

//take number of disks from user
int numberOfDisks;
cout<<"Enter number of Disks in the source Tower";
cin>>numberOfDisks;

//inserting the disks into the source tower 
createSourceTower(source,numberOfDisks);

cout<<"==============================================="<<endl;
cout<<"Initial Scenario of the Towers "<<endl;
cout<<"Source"<<endl;
source->printTowerDisks ();
cout<<"Auxillary"<<endl;
auxillary->printTowerDisks ();
cout<<"Destination"<<endl;
destination->printTowerDisks ();
hanoi( numberOfDisks,source,  destination, auxillary );
cout<<"==============================================="<<endl;
cout<<"Final Scenario of the Towers "<<endl;
cout<<"Source"<<endl;
source->printTowerDisks();
cout<<"Auxillary"<<endl;
auxillary->printTowerDisks ();
cout<<"Destination"<<endl;
destination->printTowerDisks ();
cout<<"==============================================="<<endl;

}