home *** CD-ROM | disk | FTP | other *** search
/ Microsoft Programmer's Library 1.3 / Microsoft-Programers-Library-v1.3.iso / sampcode / os2sdk / os2sdk12 / hanoi / hanoi.c next >
Encoding:
C/C++ Source or Header  |  1990-07-06  |  18.7 KB  |  540 lines
  1. /*************************************************************
  2.  
  3.  This program implements a tower of hanoi program.  This
  4.  sample app was written to demonstrate the use of a multi-
  5.  threaded program.  The main thread handles the PM interface,
  6.  the second thread is started to do the recursive execution
  7.  of the hanoi algorithm.
  8.  
  9.  This program was written by Jeff Johnson, 7/89.
  10.  
  11.  Procedures in this file:
  12.    main()             Sets up the PM environment and heap and
  13.                       calls the main window procedure ClientWndProc
  14.    ClientWndProc()    Handles the main window messages
  15.    CalcThread()       Sets up and terminates the secondary thread
  16.    DrawDisk()         Draws or erases a disk on one of the poles
  17.    MoveDisk()         Moves a disk from one pole to another
  18.    Hanoi()            Recursive alogrithm for tower of hanoi prog
  19.    EnableMenuItem()   Activates/deactivates a menu choice
  20.    EntryFldDlgProc()  Handles the set number of disks dialog box
  21.    SetupTowers()      Sets up the global tower data
  22.  
  23. **************************************************************/
  24.  
  25. #include "hanoi.h"
  26.  
  27.  
  28. /********************* GLOBALS *******************************/
  29.  
  30. CHAR szClientClass[] = "Hanoi";
  31.  
  32. /* Note that this use of global data precludes multiple windows
  33.    of hanoi running at the same time.  Thus, from an object-
  34.    oriented perspective, this is less than desireable and the
  35.    data should be passed into the window, rather than used
  36.    explicitly. */
  37.  
  38. BYTE abTowers[3][MAXDISKCNT];     /* Used to hold disk numbers on each post */
  39. BYTE abTowersNdx[3];              /* Current number of disks on each post   */
  40. BYTE cTowerSize = DEFAULTSIZE;   /* Holds the total number of disks        */
  41. USHORT ausPolePos[3]= { POSTOFFSET, /* Holds offset drawing information     */
  42.                        POSTOFFSET + POSTSPACE,
  43.                        POSTOFFSET + 2*POSTSPACE };
  44. ULONG  ulIterations;
  45.  
  46. /*************************************************************/
  47.  
  48.  
  49. /*
  50.  * Function name: main()
  51.  *
  52.  * Parameters:  argc, argv.  If the user places a number (1 thru MAXDISKCNT)
  53.  *              on the command line, that number will become the default
  54.  *              number of disks on the stack. Otherwise there will be
  55.  *              DEFUALTSIZE disks initially.
  56.  *
  57.  * Returns: Always returns 0
  58.  *
  59.  * Purpose: Parses the command line, sets up the PM environment, prepares
  60.  *          the Tower arrays, calls the main window proc, handles the
  61.  *          window's messages then cleans up and exits.
  62.  *
  63.  * Usage/Warnings:
  64.  *
  65.  * Calls: ClientWndProc() (thru PM)
  66.  */
  67.  
  68. int main(int argc, char *argv[])
  69. {
  70.    HAB          hab;
  71.    HMQ          hmq;
  72.    HWND         hwndFrame, hwndClient;
  73.    QMSG         qmsg;
  74.  
  75.    ULONG flFrameFlags = FCF_TITLEBAR      | FCF_SYSMENU | FCF_MINBUTTON |
  76.                         FCF_SHELLPOSITION | FCF_MENU    | FCF_TASKLIST  |
  77.                         FCF_ICON          | FCF_BORDER  | FCF_ACCELTABLE;
  78.  
  79.    SHORT sHold;
  80.  
  81.    if(argc > 1)  /* If command line arg, use as the initial number of disks */
  82.    {
  83.       sHold = atoi(argv[1]);
  84.       if(sHold>0 && sHold<=MAXDISKCNT)
  85.          cTowerSize = (BYTE) sHold;
  86.    }
  87.    SetupTowers();
  88.  
  89.    /* These PM calls should be error checked */
  90.    hab = WinInitialize(0);
  91.    hmq = WinCreateMsgQueue(hab, 0);
  92.  
  93.    if(!WinRegisterClass(hab, szClientClass,ClientWndProc,0L,0))
  94.    {
  95.       WinAlarm(HWND_DESKTOP, WA_ERROR);        /* Register failed */
  96.       DosExit(EXIT_PROCESS,1);
  97.    }
  98.  
  99.    hwndFrame = WinCreateStdWindow(HWND_DESKTOP, WS_VISIBLE,
  100.                                   &flFrameFlags, szClientClass, NULL,
  101.                                   0L, (HMODULE) NULL, ID_MAINMENU, &hwndClient);
  102.    if(!hwndFrame)
  103.    {
  104.       WinAlarm(HWND_DESKTOP, WA_ERROR); /* Window create failed */
  105.       DosExit(EXIT_PROCESS,1);
  106.    }
  107.  
  108.    while(WinGetMsg(hab,&qmsg,NULL,0,0))        /* Message loop */
  109.       WinDispatchMsg(hab,&qmsg);
  110.  
  111.    WinDestroyWindow(hwndFrame);                /* Clean up     */
  112.    WinDestroyMsgQueue(hmq);
  113.    WinTerminate(hab);
  114.    return 0;
  115. }
  116.  
  117.  
  118. /*
  119.  * Function name: ClientWndProc()
  120.  *
  121.  * Parameters:  hwnd, msg, mp1, mp2.  Standard PM Window Proc params.
  122.  *              No user data is expected in the WM_CREATE.
  123.  *
  124.  * Returns:
  125.  *
  126.  * Purpose: Handles all the messages associated with the main window
  127.  *          and calls the appropriate handling procedures.
  128.  *
  129.  * Usage/Warnings: Called only by main().  Note that when WM_PAINT executes,
  130.  *                 the secondary thread may change data during the update
  131.  *                 which may cause a problem.  However, this is NOT a write
  132.  *                 conflict, as only 1 thread does the writing.
  133.  *
  134.  * Calls:  DrawDisk(), CalcThread() (thru Thread), EntryFldDlgProc() (thru PM)
  135.  */
  136.  
  137. MRESULT EXPENTRY ClientWndProc(HWND hwnd, USHORT msg, MPARAM mp1, MPARAM mp2)
  138. {
  139.    HPS    hps;                         /* Handle for painting           */
  140.    RECTL  rcl;                         /* Rectangle struct for painting */
  141.    POINTL ptl;                         /* Point struct for painting     */
  142.    BYTE   cPole,bCnt,bHeight,cnt;      /* Utility variables             */
  143.    CHAR   szMsg[MSGBUFSIZE];           /* sprintf buffer                */
  144.    static CALCPARAM cp;                /* Struct used to notify thread  */
  145.    static TID    tidCalc;              /* Secondary thread ID           */
  146.    static VOID   *pThreadStack;        /* Pointer to secondary stack    */
  147.  
  148.    switch(msg)
  149.    {
  150.       case WM_PAINT:
  151.          hps = WinBeginPaint(hwnd,NULL,NULL);   /* Get paint handle     */
  152.          WinQueryWindowRect(hwnd,&rcl);
  153.  
  154.          DrawRect(rcl.xLeft,rcl.yBottom,        /* White out the screen */
  155.                   rcl.xRight,rcl.yTop,CLR_WHITE);
  156.  
  157.          /* Draw the base */
  158.          DrawRect(BASEXOFFSET,           BASEYOFFSET,
  159.                   BASEXOFFSET+BASELEN-1, BASEYOFFSET+BASETHICK-1,
  160.                   CLR_DARKGREEN);
  161.  
  162.          /* Draw the 3 posts */
  163.          bHeight = (BYTE) (cTowerSize*DISKSPACE + POSTEXTRAHT);
  164.          for(cnt=0;cnt<3;cnt++)
  165.          {
  166.             DrawRect(ausPolePos[cnt]-POSTHALF,          BASEYOFFSET,
  167.                      ausPolePos[cnt]-POSTHALF+POSTWIDTH,bHeight,
  168.                      CLR_DARKGREEN);
  169.          }
  170.  
  171.          /* Place the appropriate disks on each pole */
  172.          for(cPole=0;cPole<3;cPole++)
  173.          {
  174.             for(bCnt=0;bCnt<abTowersNdx[cPole];bCnt++)
  175.             {
  176.                DrawDisk(hps,cPole,bCnt,fDRAW);
  177.             }
  178.          }
  179.  
  180.          WinEndPaint(hps);
  181.          return 0L;
  182.  
  183.       case WM_COMMAND:
  184.          switch(COMMANDMSG(&msg)->cmd)
  185.          {
  186.             case IDM_START:
  187.                /* Try to get stack space */
  188.                if((pThreadStack = malloc(STACKSIZE)) == NULL)
  189.                {
  190.                   WinAlarm(HWND_DESKTOP, WA_ERROR);  /* Couldn't get memory */
  191.                   return 0L;
  192.                }
  193.                cp.hwnd = hwnd;           /* Set the static struct  */
  194.                cp.fContinueCalc = TRUE;
  195.                ulIterations = 0;         /* Zero iteration counter */
  196.  
  197.                /* Try to start the thread */
  198.                if((tidCalc = _beginthread(CalcThread,pThreadStack,
  199.                                           STACKSIZE, &cp))     == -1)
  200.                {
  201.                   free(pThreadStack);    /* Thread wouldn't start  */
  202.                   WinAlarm(HWND_DESKTOP, WA_ERROR);
  203.                   return 0L;
  204.                }
  205.                /* Disallow menu items that could change data while the second
  206.                   thread is running */
  207.                EnableMenuItem(hwnd,IDM_START,FALSE); /* Disable Start & set */
  208.                EnableMenuItem(hwnd,IDM_SET,FALSE);
  209.                EnableMenuItem(hwnd,IDM_STOP,TRUE);   /* Enable Stop item    */
  210.                return 0L;
  211.  
  212.             case IDM_STOP:
  213.                cp.fContinueCalc = FALSE;  /* Notify thread to quit          */
  214.                return 0L;
  215.  
  216.             case IDM_SET:
  217.                if(WinDlgBox(HWND_DESKTOP, hwnd, /* Pop up the query/set box */
  218.                          EntryFldDlgProc,(HMODULE) NULL,ID_SETCOUNT,NULL))
  219.                {
  220.                   SetupTowers();                          /* Reset towers   */
  221.                   WinInvalidateRect(hwnd,NULL,FALSE);     /* Force a redraw */
  222.                }
  223.                return 0L;
  224.  
  225.              default:
  226.                 return WinDefWindowProc(hwnd, msg, mp1, mp2);
  227.          }
  228.  
  229.       case UM_CALC_DONE:
  230.          EnableMenuItem(hwnd,IDM_START,TRUE);  /* Reenable Start & set      */
  231.          EnableMenuItem(hwnd,IDM_SET,TRUE);
  232.          EnableMenuItem(hwnd,IDM_STOP,FALSE);  /* Disable stop              */
  233.          free(pThreadStack);                   /* Free thread's stack space */
  234.  
  235.          sprintf(szMsg,"%lu disks were moved.",ulIterations);  /* Print msg */
  236.          WinMessageBox(HWND_DESKTOP, hwnd, szMsg, "Done!", 0, MB_OK);
  237.  
  238.          SetupTowers();                        /* Reset towers              */
  239.          WinInvalidateRect(hwnd,NULL,FALSE);   /* Force a screen redraw     */
  240.          return 0L;
  241.  
  242.        default:
  243.           return WinDefWindowProc(hwnd, msg, mp1, mp2);
  244.    }
  245. }
  246.  
  247.  
  248. /*
  249.  * Function name: CalcThread()
  250.  *
  251.  * Parameters:  pcp is a struct which contains the hwnd handle and the
  252.  *              continue flag which is initially set to TRUE.
  253.  *
  254.  * Returns: VOID
  255.  *
  256.  * Purpose: Calls the recursive Hanoi with initial setting of 0,2,1 meaning
  257.  *          from pole 0, to pole 2, using pole 1 as a temporary.  Hanoi
  258.  *          returns when finished, or the user says stop.  This proc then
  259.  *          sets a critical section so the posted message won't be handled
  260.  *          until the thread is terminated.
  261.  *
  262.  * Usage/Warnings: No DosExitCritSec() is called since _endthread() supposedly
  263.  *                 clears the critical section when the thread is
  264.  *                 terminated.
  265.  *
  266.  * Calls:  Hanoi()
  267.  */
  268.  
  269. VOID _cdecl FAR CalcThread(PCALCPARAM pcp)
  270. {
  271.    HAB hab;
  272.  
  273.    hab = WinInitialize(0);    /* Called to increase Ring 2 stack size */
  274.    Hanoi(pcp,cTowerSize,0,2,1);      /* Execute the recursive routine */
  275.    WinTerminate(hab);
  276.  
  277.    DosEnterCritSec(); /* Set Crit so the UM_CALC_DONE isn't processed */
  278.                       /* until this thread has completely terminated  */
  279.    WinPostMsg(pcp->hwnd,UM_CALC_DONE,NULL,NULL);         /* Post done */
  280.  
  281.    _endthread();                                  /* Terminate thread */
  282. }
  283.  
  284.  
  285. /*
  286.  * Function name: DrawDisk()
  287.  *
  288.  * Parameters:  hps is a handle to the main PS space.
  289.  *              cPole is the pole (0-2) to draw the disk on.
  290.  *              bLevel is the number of spaces from the bottom to draw disk.
  291.  *              fDraw if =0, erase disk, if =1 draw disk.
  292.  *
  293.  * Returns: VOID
  294.  *
  295.  * Purpose: This routine takes a PS handle, the hanoi spindle and disk level
  296.  *          and draws an appropriately sized disk.
  297.  *
  298.  * Usage/Warnings: Does not grab exclusive access to the screen before
  299.  *                 drawing which may cause a problem.
  300.  *
  301.  * Calls:
  302.  */
  303.  
  304. VOID DrawDisk(HPS hps,BYTE cPole, BYTE bLevel,BYTE fDraw)
  305. {
  306.    USHORT usXstart,usYstart,usWidth;
  307.    POINTL ptl;
  308.  
  309.    usYstart = BOTDISKYPOS + DISKSPACE*bLevel;  /* Calculate Bottom of disk   */
  310.  
  311.    usWidth  = (MAXDISKWIDTH-MINDISKWIDTH)*abTowers[cPole][bLevel]/cTowerSize
  312.               + MINDISKWIDTH;                  /* Calculate the disk's width */
  313.  
  314.    usXstart = ausPolePos[cPole] - usWidth/2;   /* Center disk on pole        */
  315.  
  316.    if(fDraw == fDRAW)  /* If we are to draw the disk */
  317.    {
  318.       DrawRect(usXstart,usYstart,usXstart+usWidth,
  319.                usYstart+DISKTHICK-1,CLR_RED);
  320.    }
  321.    else         /* We are to erase the disk, then redraw the pole */
  322.    {
  323.       DrawRect(usXstart,usYstart,usXstart+usWidth,
  324.                usYstart+DISKTHICK-1,CLR_WHITE);
  325.       DrawRect(ausPolePos[cPole]-POSTHALF,usYstart,
  326.                ausPolePos[cPole]-POSTHALF+POSTWIDTH,usYstart+DISKTHICK-1,
  327.                CLR_DARKGREEN);
  328.    }
  329. }
  330.  
  331.  
  332. /*
  333.  * Function name: MoveDisk()
  334.  *
  335.  * Parameters:  hps is a handle to the main PS space.
  336.  *              bFrom is the spindle to take the top disk from.
  337.  *              bTo is the spindle to place the disk on.
  338.  *
  339.  * Returns: VOID
  340.  *
  341.  * Purpose: This routine moves the top disk from the bFrom spindle to the top
  342.  *          of the bTo spindle.
  343.  *
  344.  * Usage/Warnings: Does error checking for trying to move a disk from a
  345.  *                 spindle that does not have any disks on it.
  346.  *
  347.  * Calls:  MoveDisk()
  348.  */
  349.  
  350. VOID MoveDisk(HPS hps,BYTE bFrom,BYTE bTo)
  351. {
  352.    CHAR bTOSndx;  /* Top of stack index  */
  353.    BYTE bDiskNum; /* Disk number to move */
  354.  
  355.    bTOSndx = (CHAR) (abTowersNdx[bFrom]-1);
  356.    if(bTOSndx < 0)
  357.       return;
  358.  
  359.    DrawDisk(hps,bFrom,bTOSndx,fERASE);   /* Remove disk off from stack     */
  360.  
  361.    bDiskNum = abTowers[bFrom][bTOSndx];  /* Get move disk number           */
  362.    abTowersNdx[bFrom]--;                 /* Decrease count on from spindle */
  363.  
  364.    bTOSndx = abTowersNdx[bTo]++;         /* Offset to place the disk at    */
  365.    abTowers[bTo][bTOSndx] = bDiskNum;    /* Place on stack in memory       */
  366.  
  367.    DrawDisk(hps,bTo,bTOSndx,fDRAW);      /* Draw disk on the to stack      */
  368. }
  369.  
  370.  
  371. /*
  372.  * Function name: Hanoi()
  373.  *
  374.  * Parameters:  pcp is a struct which contains the hwnd handle and the
  375.  *                  continue flag which is initially set to TRUE.
  376.  *              bHeight is the number of disks in the from stack to move.
  377.  *              bFrom is the from spindle number, 0-2.
  378.  *              bTo is the to spindle number.
  379.  *              bTemp is the temporary spindle number.
  380.  *
  381.  * Returns: VOID
  382.  *
  383.  * Purpose: This routine implements a recursive hanoi program that works as
  384.  *          follows:  By recursion, move all the disks, except for the
  385.  *          bottom disk to the temporary stack.  Then move the bottom
  386.  *          disk to the target spindle.  Now recursively move the stack
  387.  *          on the temporary spindle to the target spindle.  The limiting
  388.  *          case is when Hanoi() is called with a bHeight of 0 in which
  389.  *          case the depth recursion is terminated.
  390.  *
  391.  * Usage/Warnings: This routine checks the ->fContinueCalc flag, which is set
  392.  *                 by the main thread when the user selects stop, to see if
  393.  *                 the user wishes to abort the algorithm.  If so, it backs
  394.  *                 out and exits.
  395.  *
  396.  * Calls:  MoveDisk()
  397.  */
  398.  
  399. VOID Hanoi(PCALCPARAM pcp, BYTE bHeight, BYTE bFrom, BYTE bTo, BYTE bTemp)
  400. {
  401.    HPS hps;
  402.  
  403.    if(bHeight<=0 || !pcp->fContinueCalc)  /* Exit up if no more disks or */
  404.       return;                             /* the user said Stop          */
  405.  
  406.    Hanoi(pcp,(BYTE)(bHeight-1),bFrom,bTemp,bTo);  /* Move all but bottom disk    */
  407.  
  408.    if(!pcp->fContinueCalc)                /* If user said to stop        */
  409.       return;
  410.  
  411.    /* Display bFrom -> bTo */
  412.    hps = WinGetPS(pcp->hwnd);
  413.    MoveDisk(hps,bFrom,bTo);               /* Move the bottom disk        */
  414.    WinReleasePS(hps);
  415.    ulIterations++;
  416.  
  417.    Hanoi(pcp,(BYTE)(bHeight-1),bTemp,bTo,bFrom);  /* Move disks over             */
  418. }
  419.  
  420.  
  421. /*
  422.  * Function name: EnableMenuItem()
  423.  *
  424.  * Parameters:  hwnd is a handle of the current window.
  425.  *              sMenuItem is the ID of the item to Enable/Disable.
  426.  *              fEnable will enable item if TRUE, otherwise disables it.
  427.  *
  428.  * Returns: VOID
  429.  *
  430.  * Purpose: This routine handles enabling/disabling of menu items.  This
  431.  *          is done by getting Parent and Menu hwnd handles then sending
  432.  *          the appropriate message.
  433.  *
  434.  * Usage/Warnings:
  435.  *
  436.  * Calls:
  437.  */
  438.  
  439. VOID EnableMenuItem(HWND hwnd, SHORT sMenuItem, BOOL fEnable)
  440. {
  441.    HWND hwndParent = WinQueryWindow(hwnd, QW_PARENT, FALSE);
  442.    HWND hwndMenu   = WinWindowFromID(hwndParent, FID_MENU);
  443.  
  444.    WinSendMsg(hwndMenu, MM_SETITEMATTR,
  445.               MPFROM2SHORT(sMenuItem, TRUE),
  446.               MPFROM2SHORT(MIA_DISABLED, fEnable ? 0 : MIA_DISABLED));
  447. }
  448.  
  449.  
  450. /*
  451.  * Function name: EntryFldDlgProc()
  452.  *
  453.  * Parameters:  hwnd, msg, mp1, mp2.  Standard PM Dialog Proc params.
  454.  *              No user data is expected in the WM_CREATE.
  455.  *
  456.  * Returns: Terminates with a TRUE iff a new valid Tower Size has been entered.
  457.  *
  458.  * Purpose: Handles all the messages associated with the set entry field
  459.  *          and calls the appropriate handling procedures.  The purpose
  460.  *          of this dialog box is to get a new number of disks for the
  461.  *          hanoi routine.
  462.  *
  463.  *
  464.  * Usage/Warnings: If the value entered is valid, global cTowerSize is
  465.  *                 changed to the new value, and TRUE is returned.
  466.  *
  467.  * Calls:
  468.  */
  469.  
  470. MRESULT EXPENTRY EntryFldDlgProc(HWND hwnd, USHORT msg, MPARAM mp1, MPARAM mp2)
  471. {
  472.    SHORT sNewSize;            /* Holds new number of disks        */
  473.  
  474.    switch(msg)
  475.    {
  476.       case WM_INITDLG:
  477.          WinSendDlgItemMsg(hwnd, ID_ENTRYFLD,EM_SETTEXTLIMIT,  /* Limit len */
  478.                                  MPFROM2SHORT(2,0),NULL);
  479.          WinSetDlgItemShort(hwnd, ID_ENTRYFLD,(SHORT) cTowerSize,TRUE);
  480.          return 0L;                           /* Allow normal focus setting */
  481.  
  482.       case WM_COMMAND:
  483.          switch(COMMANDMSG(&msg)->cmd)
  484.          {
  485.             case DID_OK:
  486.                WinQueryDlgItemShort(hwnd, ID_ENTRYFLD,
  487.                                     &sNewSize, TRUE); /* Get the short      */
  488.                if(sNewSize>0 && sNewSize<=MAXDISKCNT) /* Set new Tower size */
  489.                {
  490.                   cTowerSize = (BYTE) sNewSize;
  491.                   WinDismissDlg(hwnd,TRUE);
  492.                }
  493.                else                                   /* Invalid value      */
  494.                   WinDismissDlg(hwnd,FALSE);
  495.                return 0L;
  496.  
  497.             case DID_CANCEL:
  498.                WinDismissDlg(hwnd,FALSE);
  499.                return 0L;
  500.  
  501.             default:
  502.                return WinDefDlgProc(hwnd, msg, mp1, mp2);
  503.          }
  504.  
  505.       default:
  506.          return WinDefDlgProc(hwnd, msg, mp1, mp2);
  507.    }
  508. }
  509.  
  510. /*
  511.  * Function name: SetupTowers()
  512.  *
  513.  * Parameters:  None
  514.  *
  515.  * Returns: VOID
  516.  *
  517.  * Purpose: This routine initializes the global arrays that represent the
  518.  *          hanoi stacks.  This involves placing all the disks on the
  519.  *          first peg, emptying the other 2 pegs and setting the associated
  520.  *          counts.
  521.  *
  522.  * Usage/Warnings: Calling uses the global variable cTowerSize to determine
  523.  *                 how many disks there are.
  524.  *
  525.  * Calls:
  526.  */
  527.  
  528. VOID SetupTowers()
  529. {
  530.    USHORT cnt;
  531.  
  532.    for(cnt=0;cnt<cTowerSize;cnt++)       /* Setup the intial post with disks */
  533.       abTowers[0][cnt] = (BYTE)(cTowerSize-cnt-1);
  534.  
  535.    abTowersNdx[0] = cTowerSize;          /* Set disk count for initial post  */
  536.    abTowersNdx[1] = abTowersNdx[2] = 0;  /* Zero other post counts           */
  537. }
  538.  
  539. 
  540.