include <iostream.h>
#include <math.h>
#define ARRAYSIZE 100
/*************************************************************************************************
PROGRAMMED BY : REHAN AHMED KHAN
PAKISTAN- KARACHI
BS student in FAST University
(foundation for advancement of science and technology)
this program is free ware and anyone can use it.
/************************************************************************************************/
/*************************************************************************************************
*								THE ALGORITHM USED IS AS FOLLOWS								 *
*																								 *
*	Because the tree is complete it can be stored in an array of 2^n-1.							 *
*	The root of the tree is in position 2^(n-1)-1												 *
*	For any level j, the first node at that level is in position 2^(n-1-j)-1					 *
*	and each successive node at that level is 2^(n-j) elements beyond the previous element		 *
*	at that level																				 *
*	So the sequential traversal of the array produces the solution of Towers of Hanoi Problem	 *
*																								 *
*************************************************************************************************/
class TowersHanoi


    {
    	private:
    		struct										//node structure


        		{
        			char chToPeg;
        			char chFromPeg;
        			int iDiskNo;
        		}node[ARRAYSIZE];							//Array of Nodes

        		char except(char chFromPeg, char chToPeg);	//returns peg other than provided as parameter
        	public:
        		TowersHanoi();								//constructor
        		//generates the tree
        		void generateTree(char chFromPeg,char chToPeg, int iDiskNo);
    };
    //////////////////////////////////////////////////////////////////////////////////////////////////
    TowersHanoi::TowersHanoi()


        {
        	int iDiskNo;
        	cout << "\nENTER THE NUMBER OF DISKS >> ";
        	cin >> iDiskNo;

        	generateTree('A','B',iDiskNo);
        	int cMoves=(int)pow(2,iDiskNo)-1;

        	cout << "THE MOVES ARE AS FOLLOWS\n";
        	for(int i=0;i<cMoves;i++)
        		cout << i+1 << ": " <<"Move Disk " << node[i].iDiskNo << " From " << node[i].chFromPeg
        			 << " To " << node[i].chToPeg << endl;
    }
    //////////////////////////////////////////////////////////////////////////////////////////////////
    void TowersHanoi::generateTree(char chFromPeg, char chToPeg, int iDiskNo)


        {
        	int j, iLevel=1, iDistance, iDistance2;
        	int iNodeIndex;

        	node[(int)pow(2,iDiskNo-1)-1].chToPeg=chToPeg;
        	node[(int)pow(2,iDiskNo-1)-1].chFromPeg=chFromPeg;
        	node[(int)pow(2,iDiskNo-1)-1].iDiskNo=iDiskNo;
        	for(int i=1;i<=iDiskNo-1;i++)


            	{
            		iDistance=0;
            		iDistance2=(int)pow(2,iDiskNo-i);
            		for(j=0;j<(int)pow(2,i);j++)


                		{
                			if(j%2==0)


                    			{
                    				iNodeIndex=iDistance+(int)pow(2,iDiskNo-1-i)-1;
                    				node[iNodeIndex].chToPeg=
                    					except(node[iNodeIndex+iDistance2/2].chFromPeg,
                    						node[iNodeIndex+iDistance2/2].chToPeg);

                    				node[iNodeIndex].chFromPeg=
                    					node[iNodeIndex+iDistance2/2].chFromPeg;
                    				node[iNodeIndex].iDiskNo=iDiskNo-iLevel;
                    			}
                    			else


                        			{
                        				iNodeIndex=iDistance+(int)pow(2,iDiskNo-1-i)-1;
                        				node[iNodeIndex].chFromPeg=
                        					except(node[iNodeIndex-iDistance2/2].chFromPeg,
                        						node[iNodeIndex-iDistance2/2].chToPeg);

                        				node[iNodeIndex].chToPeg=
                        					node[iNodeIndex-iDistance2/2].chToPeg;
                        				node[iNodeIndex].iDiskNo=iDiskNo-iLevel;
                        			}
                        			iDistance+=(int)pow(2,iDiskNo-i);
                        		}
                        		iLevel++;
                        	}
                    }
                    //////////////////////////////////////////////////////////////////////////////////////////////////
                    char TowersHanoi::except(char chFromPeg, char chToPeg)


                        {
                        	if(chFromPeg=='A' && chToPeg=='B' || chFromPeg=='B' && chToPeg=='A')
                        		return 'C';
                        	if(chFromPeg=='A' && chToPeg=='C' || chFromPeg=='C' && chToPeg=='A')
                        		return 'B';
                        	if(chFromPeg=='B' && chToPeg=='C' || chFromPeg=='C' && chToPeg=='B')
                        		return 'A';
                    }
                    //////////////////////////////////////////////////////////////////////////////////////////////////
                    /*ostream& operator << (ostream& s,nodeHanoi node)


                        {
                        	return s <<"Move Disk " << node.iDiskNo << " From " << node.chFromPeg
                        		 << " To " << node.chToPeg << endl;
                    }*/
                    //////////////////////////////////////////////////////////////////////////////////////////////////
                    void main(void)


                        {
                        	cout << "A represents FROM PEG,\nB represents TO PEG,\nC represents AUXILLARY PEG\n";
                        	TowersHanoi towersHanoi;
                    }