home *** CD-ROM | disk | FTP | other *** search
/ Microsoft Programmer's Library 1.3 / Microsoft-Programers-Library-v1.3.iso / sampcode / os2sdk / os2sdk12 / sort / sort.c next >
Encoding:
C/C++ Source or Header  |  1990-07-09  |  31.6 KB  |  860 lines
  1. /*************************************************************
  2.  
  3.  This program demonstrates the use of many threads by doing
  4.  LISTCNT simultaneous sorts.  Each sorting algorithm runs
  5.  from a separate thread, the routine which updates the display
  6.  is run from another thread, and the main thread is used to
  7.  handle the main window's messages.  The display thread is
  8.  started when the program begins and is not terminated (allows
  9.  default cleanup to terminate thread) as the display routine
  10.  is used throughout the program's life.
  11.  This code was written to allow easy modification.  To change
  12.  the number of simultaneous sorts, change the LISTCNT #define
  13.  and modify the global arrays which control the screen
  14.  drawing color, the sort each thread is to use, and the sort name.
  15.  Note:  This program was not intended to infer the relative
  16.         speeds of the various sorting algorithms.
  17.  
  18.  This program was written by Jeff Johnson, 8/89.
  19.  
  20.  Procedures in this file:
  21.    main()             Sets up the PM environment and calls
  22.                       the main dialog procedure ClientWndProc
  23.    ClientWndProc()    Handles the main window messages
  24.    CalcThread()       Generic stub that sets up, executes, and
  25.                       terminates each sort in an aux. thread
  26.    DispThread()       Updates the display during the sorts
  27.    BubbleSort()       Implements a bubble sort
  28.    InsertionSort()    Implements an insertion sort
  29.    BatcherSort()      Stub that calls recursive Batcher sort
  30.    BatcherSortR()     Implements a Batcher sort
  31.    QuickSort()        Stub that calls recursive Quick sort
  32.    QuickSortR()       Implements a Quick sort
  33.    EnableMenuItem()   Activates/deactivates a menu choice
  34.    EntryFldDlgProc()  Handles the set number of disks dialog box
  35.    RandomizeData()    Randomizes the data arrays for the sorts
  36.  
  37. **************************************************************/
  38.  
  39. #include "sort.h"
  40.  
  41. /********************* GLOBALS *******************************/
  42.  
  43. CHAR szClientClass[] = "Sort";
  44. USHORT Data[LISTCNT][NELEMS];     /* Array that contains the data to sort  */
  45.  
  46. /* Global data that defines each of the sort routines */
  47. ULONG  ulColors[LISTCNT] =   { CLR_RED,        /* Color of each of the     */
  48.                                CLR_BLUE,       /* LISTCNT data lists.      */
  49.                                CLR_DARKGREEN,
  50.                                CLR_YELLOW };
  51. VOID((*pExecSub[LISTCNT])())=  { BubbleSort,     /* List of sorts to be      */
  52.                                BatcherSort,    /* executed for each of the */
  53.                                QuickSort,      /* LISTCNT threads.         */
  54.                                InsertionSort };
  55. CHAR *szSubNames[LISTCNT] =  { "Bubble Sort",  /* Ascii names of sorts     */
  56.                                "Batcher Sort",
  57.                                "Quick Sort",
  58.                                "Insertion Sort" };
  59.  
  60. /*************************************************************/
  61.  
  62.  
  63. /*
  64.  * Function name: main()
  65.  *
  66.  * Parameters:  NONE
  67.  *
  68.  * Returns: Always returns 0
  69.  *
  70.  * Purpose: Sets up the PM environment, calls the main window proc,
  71.             handles the window's messages then cleans up and exits.
  72.  *
  73.  * Usage/Warnings:
  74.  *
  75.  * Calls: ClientWndProc() (thru PM)
  76.  */
  77.  
  78. int main()
  79. {
  80.    HAB          hab;
  81.    HMQ          hmq;
  82.    HWND         hwndFrame, hwndClient;
  83.    QMSG         qmsg;
  84.  
  85.    ULONG flFrameFlags = FCF_TITLEBAR      | FCF_SYSMENU | FCF_MINMAX    |
  86.                         FCF_SHELLPOSITION | FCF_MENU    | FCF_TASKLIST  |
  87.                         FCF_SIZEBORDER    | FCF_ICON;
  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 Dialog Proc params.
  122.  *              No user data is expected in the WM_CREATE.
  123.  *
  124.  * Returns: Returns with WM_QUIT message
  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()
  130.  *
  131.  * Calls: RandomizeData(), DispThread() (thru thread),
  132.           CalcThread() (thru thread)
  133.  */
  134.  
  135. MRESULT EXPENTRY ClientWndProc(HWND hwnd, USHORT msg, MPARAM mp1, MPARAM mp2)
  136. {
  137.    HPS    hps;                           /* Handle for painting            */
  138.    RECTL  rcl;                           /* Rectangle struct for painting  */
  139.    POINTL ptl;                           /* Point struct for painting      */
  140.    static CALCPARAM cp[LISTCNT];         /* Struct passed to sort threads  */
  141.    static TID    tidCalc[LISTCNT];       /* Sort threads IDs               */
  142.    static VOID   *pThreadStack[LISTCNT]; /* Pointer to sort threads stacks */
  143.    static CALCPARAM cpDisp;              /* Struct passed to disp thread   */
  144.    static TID    tidDisplay;             /* Secondary display thread ID    */
  145.    static VOID   *pDisplayStack;         /* Ptr to secondary display stack */
  146.    static USHORT usWindowYCoord=1;       /* Holds current client window ht */
  147.    static BYTE   cThreadCnt = 0;         /* Count of sort threads running  */
  148.    static USHORT cSetSize = NELEMS;      /* User sort set size             */
  149.    USHORT cnt,cnt2,usID;                 /* Utility counters               */
  150.    ULONG  ulBlip;                        /* Holds the marker pos for Paint */
  151.  
  152.    switch(msg)
  153.    {
  154.       case WM_CREATE:
  155.          RandomizeData(cSetSize);        /* Initially randomize data set   */
  156.  
  157.          /* Start display thread */
  158.          if((pDisplayStack = malloc(STACKSIZE)) == NULL)
  159.          {
  160.             WinAlarm(HWND_DESKTOP, WA_ERROR);      /* Can't allocate stack */
  161.             DosExit(EXIT_PROCESS,1);
  162.          }
  163.  
  164.          cpDisp.hwnd        = hwnd;
  165.          cpDisp.Array       = &usWindowYCoord;
  166.          cpDisp.pcThreadCnt = &cThreadCnt;
  167.          cpDisp.pcSetSize   = &cSetSize;
  168.  
  169.          if((tidDisplay = _beginthread(DispThread,pDisplayStack,
  170.                                          STACKSIZE, &cpDisp))  == -1)
  171.          {
  172.             free(pDisplayStack);          /* Couldn't start display thread */
  173.             WinAlarm(HWND_DESKTOP, WA_ERROR);
  174.             DosExit(EXIT_PROCESS,1);
  175.          }
  176.          /* Up the display priority an arbitrary amount to cause it to
  177.             update more rapidly and to give it a higher priority than
  178.             the sort threads.*/
  179.          DosSetPrty(PRTYS_THREAD,
  180.                     PRTYC_REGULAR,5,tidDisplay);
  181.          return 0L;
  182.  
  183.       case WM_SIZE:
  184.          WinInvalidateRect(hwnd,NULL,FALSE);     /* Force a redraw */
  185.          return WinDefWindowProc(hwnd, msg, mp1, mp2);
  186.  
  187.       case WM_PAINT:
  188.          hps = WinBeginPaint(hwnd,NULL,NULL);   /* Get paint handle      */
  189.          WinQueryWindowRect(hwnd,&rcl);
  190.          usWindowYCoord = (USHORT) rcl.yTop;
  191.  
  192.          if((XOFFSET < (USHORT) (rcl.xRight-rcl.xLeft)) && /* Draw if screen */
  193.             (YOFFSET < (USHORT) (rcl.yTop-rcl.yBottom)))   /* is big enough  */
  194.          {
  195.             DrawRect(rcl.xLeft,rcl.yBottom,         /* White out the screen  */
  196.                      rcl.xRight,rcl.yTop,CLR_WHITE);
  197.  
  198.             DrawLine(XOFFSET, YOFFSET,              /* Draw baseline         */
  199.                      rcl.xRight,YOFFSET,CLR_BLACK);
  200.  
  201.             DrawLine(XOFFSET, YOFFSET,              /* Draw vertical line    */
  202.                      XOFFSET,rcl.yTop,CLR_BLACK);
  203.  
  204.             for(cnt=0;cnt<LISTCNT;cnt++)            /* Draw data points      */
  205.             {
  206.                for(cnt2=0;cnt2<cSetSize;cnt2++)
  207.                {
  208.                   ulBlip = (rcl.yTop-YOFFSET-5) * Data[cnt][cnt2] / RAND_MAX
  209.                            + YOFFSET+1;
  210.  
  211.                   Draw2Pel(XOFFSET+1 + cnt2, ulBlip, ulColors[cnt]);
  212.                }
  213.             }
  214.             for(cnt=0;cnt<COLUMNCNT;cnt++)          /* Do bottom legend      */
  215.             {
  216.                for(cnt2=1;cnt2<=ROWCNT;cnt2++)
  217.                {
  218.                   usID = cnt*ROWCNT + cnt2-1;
  219.                   if(usID >= LISTCNT)
  220.                      break;
  221.  
  222.                   ptl.x = XOFFSET + cnt*COLUMNOFFSET;
  223.                   ptl.y = YOFFSET - cnt2*ROWOFFSET;
  224.  
  225.                   GpiSetColor(hps,ulColors[usID]);
  226.                   GpiCharStringAt(hps,&ptl,(LONG) strlen(szSubNames[usID]),
  227.                                   szSubNames[usID]);
  228.                }
  229.             }
  230.          }
  231.  
  232.          WinEndPaint(hps);
  233.          return 0L;
  234.  
  235.       case WM_COMMAND:
  236.          switch(COMMANDMSG(&msg)->cmd)
  237.          {
  238.             case IDM_START:
  239.  
  240.                /* Try to get stack space */
  241.                for(cnt=0;cnt<LISTCNT;cnt++)
  242.                {
  243.                   if((pThreadStack[cnt] = malloc(STACKSIZE)) == NULL)
  244.                   {
  245.                      WinAlarm(HWND_DESKTOP, WA_ERROR); /* Can't get memory */
  246.                      return 0L;
  247.                   }
  248.                   cp[cnt].hwnd          = hwnd;  /* Set the static struct  */
  249.                   cp[cnt].fContinueCalc = TRUE;
  250.                   cp[cnt].pFunc         = pExecSub[cnt];
  251.                   cp[cnt].usID          = cnt;
  252.                   cp[cnt].Array         = Data[cnt];
  253.                   cp[cnt].cArray        = cSetSize;
  254.  
  255.                   /* Try to start the thread */
  256.                   if((tidCalc[cnt] = _beginthread(CalcThread,pThreadStack[cnt],
  257.                                                   STACKSIZE, &cp[cnt]))  == -1)
  258.                   {
  259.                      free(pThreadStack[cnt]);    /* Thread wouldn't start  */
  260.                      WinAlarm(HWND_DESKTOP, WA_ERROR);
  261.                      return 0L;
  262.                   }
  263.                   if(cThreadCnt++ == 0)  /* When the first thread starts */
  264.                   {
  265.                      /* Disable Start, Set, and Randomize, enable Stop */
  266.                      EnableMenuItem(hwnd,IDM_START,FALSE);
  267.                      EnableMenuItem(hwnd,IDM_SET,FALSE);
  268.                      EnableMenuItem(hwnd,IDM_RANDOM,FALSE);
  269.                      EnableMenuItem(hwnd,IDM_STOP,TRUE);
  270.                   }
  271.                }
  272.                return 0L;
  273.  
  274.             case IDM_STOP:
  275.                for(cnt=0;cnt<LISTCNT;cnt++)
  276.                   cp[cnt].fContinueCalc = FALSE;  /* Notify thread to quit  */
  277.                return 0L;
  278.  
  279.             case IDM_RANDOM:
  280.                RandomizeData(cSetSize);                /* Randomize data */
  281.                WinInvalidateRect(hwnd,NULL,FALSE);     /* Force a redraw */
  282.                return 0L;
  283.  
  284.             case IDM_SET:
  285.                if(WinDlgBox(HWND_DESKTOP, hwnd, /* Pop up the query/set box */
  286.                             EntryFldDlgProc,(HMODULE) NULL,ID_SETCOUNT,
  287.                             (VOID FAR *) &cSetSize))
  288.                {
  289.                   WinInvalidateRect(hwnd,NULL,FALSE);     /* Force a redraw */
  290.                }
  291.                return 0L;
  292.  
  293.             default:
  294.                return WinDefWindowProc(hwnd, msg, mp1, mp2);
  295.          }
  296.  
  297.       case UM_CALC_DONE:
  298.          usID = (USHORT) SHORT1FROMMP(mp1); /* Get ID of quit thread     */
  299.  
  300.          if(--cThreadCnt == 0)              /* If all quit, enable menus */
  301.          {
  302.             EnableMenuItem(hwnd,IDM_START,TRUE);
  303.             EnableMenuItem(hwnd,IDM_SET,TRUE);
  304.             EnableMenuItem(hwnd,IDM_RANDOM,TRUE);
  305.             EnableMenuItem(hwnd,IDM_STOP,FALSE);
  306.          }
  307.  
  308.          free(pThreadStack[usID]);          /* Free thread's stack space */
  309.          return 0L;
  310.  
  311.       default:
  312.          return WinDefWindowProc(hwnd, msg, mp1, mp2);
  313.    }
  314. }
  315.  
  316.  
  317. /*
  318.  * Function name: CalcThread()
  319.  *
  320.  * Parameters:  pcp is a struct which contains the hwnd handle, the
  321.  *              continue flag which is initially set to TRUE, the ID
  322.  *              which is the
  323.  *
  324.  * Returns: VOID
  325.  *
  326.  * Purpose: This generic stub calls the passed "sort" function with a pointer
  327.  *          to the data and an item count, then when the sort terminates, it
  328.  *          cleans up by Posting a done message, then terminating the thread.
  329.  *
  330.  * Usage/Warnings: No DosExitCritSec() is called since _endthread()
  331.  *                 clears the critical section when the thread is
  332.  *                 terminated.
  333.  *
  334.  * Calls:  Whatever function is passed in pcp->pFunc.  (As initially
  335.  *         configured, it calls:  BubbleSort(), InsertionSort(),
  336.  *         BatcherSort(), and QuickSort()
  337.  */
  338.  
  339. VOID _cdecl FAR CalcThread(PCALCPARAM pcp)
  340. {
  341.    (*pcp->pFunc)(pcp);                      /* Execute recurs routine */
  342.  
  343.    DosEnterCritSec(); /* Set Crit so the UM_CALC_DONE isn't processed */
  344.                       /* until this thread has completely terminated  */
  345.    WinPostMsg(pcp->hwnd,UM_CALC_DONE,
  346.               MPFROMSHORT(pcp->usID),NULL);              /* Post done */
  347.  
  348.    _endthread();                /* Terminate thread and exit crit sec */
  349. }
  350.  
  351.  
  352. /*
  353.  * Function name: DispThread()
  354.  *
  355.  * Parameters:  pcp is a struct which contains the hwnd handle, the
  356.  *              count of active threads, the ->Array element points to
  357.  *              the current height of the window which can be dynamically
  358.  *              resized by the user, the pcSetSize points to the current
  359.  *              set size which can be changed by the user only when the
  360.  *              sort is stopped.
  361.  *              None of the other pcp members are used.
  362.  *
  363.  * Returns: VOID
  364.  *
  365.  * Purpose: This routine is run as a secondary thread to update the screen
  366.  *          when the sort threads are running.  It works by making passes
  367.  *          through the data lists and redrawing them.  A DosSleep(0) is
  368.  *          called at the end of each pass to help sychronize things a bit.
  369.  *
  370.  * Usage/Warnings: Note that this thread is started when the program is
  371.  *                 initialized, and is never terminated.  Note that
  372.  *                 fDoUpdate is used in such a way that the screen is
  373.  *                 ALWAYS updated once after all threads have terminated.
  374.  *                 This avoids the possibility of the display not being
  375.  *                 fully accurate when the sorts terminate.
  376.  *
  377.  * Calls:
  378.  */
  379.  
  380. VOID _cdecl FAR DispThread(PCALCPARAM pcp)
  381. {
  382.    HAB hab;              /* Anchor block, used just for WinInitialize() */
  383.    USHORT cnt,cnt2;      /* Utility counters                            */
  384.    HPS hps;              /* Presentation space handle                   */
  385.    POINTL ptl;           /* Used for various drawing macros             */
  386.    ULONG  ulBlip;        /* Holds the Y offset for a given data point   */
  387.    BYTE   fDoUpdate = 0; /* Used to ensure screen is fully updated      */
  388.                          /* after all sort threads terminate            */
  389.    USHORT *pusYCoord = pcp->Array; /* Points to location that always    */
  390.                                    /* contains current client wind hgt  */
  391.  
  392.    hab = WinInitialize(0);    /* Called to increase Ring 2 stack size   */
  393.    hps = WinGetPS(pcp->hwnd);
  394.  
  395.    while(TRUE)
  396.    {
  397.       if(*pcp->pcThreadCnt != 0)          /* Set update flag if at least 1 */
  398.          fDoUpdate = (BYTE) (*pcp->pcThreadCnt+1); /* sort thread is still running  */
  399.  
  400.       while(!fDoUpdate && !(*pcp->pcThreadCnt));  /* Only update when a    */
  401.                                                   /* sort is running       */
  402.       for(cnt=0;cnt<*pcp->pcSetSize;cnt++)        /* Update data set       */
  403.       {
  404.          DrawLine(XOFFSET+1 + cnt,YOFFSET+1,      /* Erase vertical column */
  405.                   XOFFSET+1 + cnt,*pusYCoord, CLR_WHITE);
  406.  
  407.          for(cnt2=0;cnt2<LISTCNT;cnt2++)          /* Draw each point       */
  408.          {
  409.             ulBlip = (ULONG) (*pusYCoord-YOFFSET-5)*Data[cnt2][cnt] / RAND_MAX
  410.                       + YOFFSET+1;
  411.             Draw2Pel(XOFFSET+1 + cnt, ulBlip, ulColors[cnt2]);
  412.          }
  413.       }
  414.       fDoUpdate--;  /* Decrement update flag */
  415.    }
  416.  
  417.    /* Note that these 3 lines NEVER get executed, but should the program be
  418.       modified to end the thread, this is the appropriate termination code. */
  419.    WinReleasePS(hps);
  420.    WinTerminate(hab);
  421.    _endthread();
  422. }
  423.  
  424.  
  425. /*
  426.  * Function name: BubbleSort()
  427.  *
  428.  * Parameters:  pcp is a struct which contains the hwnd handle, a
  429.  *              pointer to the data array, and a count of the items in
  430.  *              the data array.
  431.  *              None of the other pcp members are used.
  432.  *
  433.  * Returns: VOID
  434.  *
  435.  * Purpose:  Implements a bubble sort which is an O(n^2) algorithm.  It
  436.  *           works by repeatedly going through the data and comparing
  437.  *           consecutive elements and swapping them if they aren't in
  438.  *           the correct order.  This guarantees that each pass will
  439.  *           place at least one additional item in its appropriate
  440.  *           place.
  441.  *
  442.  * Usage/Warnings:
  443.  *
  444.  * Calls:
  445.  */
  446.  
  447. VOID BubbleSort(PCALCPARAM pcp)
  448. {
  449.    BOOL fModified = FALSE; /* Set whenever a swap is done, if an entire */
  450.                            /* pass doesn't set the flag, the we're done */
  451.    SHORT cnt,cnt2;         /* Counters used for the 2-level loops       */
  452.    USHORT usTemp;          /* Used to hold a data item during a swap    */
  453.  
  454.    for(cnt=pcp->cArray-1;cnt>=0;cnt--) /* Set for the max no. of passes */
  455.    {
  456.       for(cnt2=0;cnt2<cnt;cnt2++) /* Only sort thru current cnt pass    */
  457.       {
  458.          if(!pcp->fContinueCalc)  /* User wishes to terminate the sort  */
  459.             return;
  460.  
  461.          if(pcp->Array[cnt2]>pcp->Array[cnt2+1]) /* Items need to swap  */
  462.          {
  463.             fModified = TRUE;
  464.  
  465.             usTemp = pcp->Array[cnt2];
  466.             pcp->Array[cnt2] = pcp->Array[cnt2+1];
  467.             pcp->Array[cnt2+1]= usTemp;
  468.          }
  469.       }
  470.       if(!fModified)          /* Nothing changed during the entire pass */
  471.          break;
  472.       fModified = FALSE;                       /* Reset the modify flag */
  473.    }
  474. }
  475.  
  476.  
  477. /*
  478.  * Function name: InsertionSort()
  479.  *
  480.  * Parameters:  pcp is a struct which contains the hwnd handle, a
  481.  *              pointer to the data array, and a count of the items in
  482.  *              the data array.
  483.  *              None of the other pcp members are used.
  484.  *
  485.  * Returns: VOID
  486.  *
  487.  * Purpose:  Implements an insertion sort which is an O(n^2) algorithm.
  488.  *           This sort works much faster and does not require that much
  489.  *           additional code to implement.  It works by setting a sorted
  490.  *           list to be just the first element, the working each
  491.  *           successive item into the already sorted list.
  492.  *
  493.  * Usage/Warnings:
  494.  *
  495.  * Calls:
  496.  */
  497.  
  498. VOID InsertionSort(PCALCPARAM pcp)
  499. {
  500.    SHORT cnt,cnt2;         /* Counters used for the 2-level loops       */
  501.    USHORT usTemp;          /* Used to hold a data item during a swap    */
  502.  
  503.    for(cnt=1;cnt<(SHORT)pcp->cArray;cnt++)         /* Insert each item in turn */
  504.    {
  505.       if(!pcp->fContinueCalc)      /* User wishes to terminate the sort */
  506.          return;
  507.       usTemp=pcp->Array[cnt];                   /* Hold value to insert */
  508.       cnt2=cnt-1;
  509.       while(pcp->Array[cnt2]>usTemp)    /* Move items down to make room */
  510.       {
  511.          pcp->Array[cnt2+1]=pcp->Array[cnt2];
  512.          cnt2--;
  513.          if(cnt2<0)
  514.             break;
  515.       }
  516.       pcp->Array[cnt2+1] = usTemp;                   /* Insert the item */
  517.    }
  518. }
  519.  
  520.  
  521. /*
  522.  * Function name: BatcherSort()
  523.  *
  524.  * Parameters:  pcp is a struct which contains the continue flag,
  525.  *              a pointer to the data array, and a count of the items in
  526.  *              the data array.
  527.  *              None of the other pcp members are used.
  528.  *
  529.  * Returns: VOID
  530.  *
  531.  * Purpose:  This routine is a stub that calls the recursive Batcher sort
  532.  *           with the proper initial arguments.
  533.  *
  534.  * Usage/Warnings:  It passes the pcp, the size of the array to be sorted,
  535.  *                  the offset to start sorting at(0), the number number
  536.  *                  of elements each item is from neighboring elements (1),
  537.  *                  and Half flag to sort the halves (1=YES).
  538.  *
  539.  * Calls:  BatcherSortR()
  540.  */
  541.  
  542. VOID BatcherSort(PCALCPARAM pcp)
  543. {
  544.    BatcherSortR(pcp,pcp->cArray,0,1,1);
  545. }
  546.  
  547.  
  548. /*
  549.  * Function name: BatcherSortR()
  550.  *
  551.  * Parameters:  pcp is a struct which contains the continue flag,
  552.  *              a pointer to the data array.
  553.  *              None of the other pcp members are used.
  554.  *              usArrSize is the number of elements in the current sort set.
  555.  *              usStart is the offset to the 1st element in the set.
  556.  *              usSkip is the spacing between consecutive elements.
  557.  *              fHalves sorts the 2 halves when set, otherwise skips the
  558.  *                      1st 2 of the 4 sub-sorts.
  559.  *
  560.  * Returns: VOID
  561.  *
  562.  * Purpose:  Implements Batcher sort which is O(n lg n).  The advantage
  563.  *           of the batcher sort is that the comparisons made do NOT
  564.  *           depend upon the outcome of previous comparisons.  This makes
  565.  *           it a good algorithm for parallelism.  The algorithm works as
  566.  *           follows:  Sort the first half, sort the second half, sort the
  567.  *           odd elements, sort the even elements, then compare swap
  568.  *           elements 2/3, 4/5, ...
  569.  *
  570.  * Usage/Warnings:  There are several adaptations to the algorithm to
  571.  *                  allow it to work with arbitrary sized data sets
  572.  *                  (the original required a power of 2 sized data
  573.  *                  set):  if the set size is less than 2, the routine
  574.  *                  returns, the first "half" is always the largest
  575.  *                  possible power of two, and the top value for the
  576.  *                  final compare/swap is adjusted to round up in
  577.  *                  case of an odd data set.
  578.  *                  Another optimization is that involving the fHalves
  579.  *                  flag.  This stems from the observation that when
  580.  *                  the odd/even sort recurses, the first and second
  581.  *                  halves are already sorted, thus the first 2
  582.  *                  recursive calls are unnecessary in this case.
  583.  *
  584.  * Calls:  BatcherSortR() (recursively)
  585.  */
  586.  
  587. VOID BatcherSortR(PCALCPARAM pcp, USHORT usArrSize, USHORT usStart,
  588.                   USHORT usSkip, BOOL fHalves)
  589. {
  590.    USHORT cnt,usUpper,usTemp; /* Utility variables */
  591.  
  592.    if(!pcp->fContinueCalc) /* User wishes to terminate the sort */
  593.       return;
  594.  
  595.    if(usArrSize<2) /* No sorting needed if <2 items in the set */
  596.       return;
  597.  
  598.    if(usArrSize==2) /* Do simple compare/swap if there are 2 elements */
  599.    {
  600.       if(pcp->Array[usStart]>pcp->Array[usStart+usSkip])
  601.       {
  602.          usTemp = pcp->Array[usStart];
  603.          pcp->Array[usStart] = pcp->Array[usStart+usSkip];
  604.          pcp->Array[usStart+usSkip]= usTemp;
  605.       }
  606.       return;
  607.    }
  608.  
  609.    usTemp=1;                  /* usTemp ends up holding the smallest power */
  610.    while(usTemp < usArrSize)  /* of 2 that is at least as big as usArrSize */
  611.       usTemp *= 2;
  612.  
  613.    if(fHalves)  /* If the sort was NOT called by the odd/even recurses */
  614.    {
  615.       BatcherSortR(pcp,usTemp/2,usStart,usSkip,1);    /* Sort 1st half */
  616.       BatcherSortR(pcp,usArrSize-usTemp/2,            /* Sort 2nd half */
  617.                    usStart+usTemp/2*usSkip,usSkip,1);
  618.    }
  619.    BatcherSortR(pcp,usArrSize-usArrSize/2,usStart,usSkip*2,0); /* Sort evens */
  620.    BatcherSortR(pcp,usArrSize/2,usStart+usSkip,usSkip*2,0);    /* Sort odds  */
  621.  
  622.    if(!pcp->fContinueCalc) /* User wishes to terminate the sort */
  623.       return;
  624.  
  625.    usUpper=usStart+usSkip+(usArrSize-usArrSize/2-1)*2*usSkip;
  626.    for(cnt=usStart+usSkip;cnt<usUpper;cnt+=usSkip*2) /* Do final compares */
  627.    {
  628.       if(pcp->Array[cnt]>pcp->Array[cnt+usSkip])
  629.       {
  630.          usTemp = pcp->Array[cnt];
  631.          pcp->Array[cnt] = pcp->Array[cnt+usSkip];
  632.          pcp->Array[cnt+usSkip]= usTemp;
  633.       }
  634.       if(!pcp->fContinueCalc) /* User wishes to terminate the sort */
  635.          return;
  636.    }
  637. }
  638.  
  639.  
  640. /*
  641.  * Function name: QuickSort()
  642.  *
  643.  * Parameters:  pcp is a struct which contains the continue flag,
  644.  *              a pointer to the data array, and a count of the items in
  645.  *              the data array.
  646.  *              None of the other pcp members are used.
  647.  *
  648.  * Returns: VOID
  649.  *
  650.  * Purpose:  This routine is a stub that calls the recursive Quick sort
  651.  *           with the proper initial arguments.
  652.  *
  653.  * Usage/Warnings:  It passes the pcp (Which contains the array ptr),
  654.  *                  the offset to start sorting at(0), and the offset to
  655.  *                  finish sorting at (Array size-1).
  656.  *
  657.  * Calls:  QuickSortR()
  658.  */
  659.  
  660. VOID QuickSort(PCALCPARAM pcp)
  661. {
  662.    QuickSortR(pcp,0,pcp->cArray-1);
  663. }
  664.  
  665.  
  666. /*
  667.  * Function name: QuickSortR()
  668.  *
  669.  * Parameters:  pcp is a struct which contains the continue flag,
  670.  *              a pointer to the data array.
  671.  *              None of the other pcp members are used.
  672.  *              sLeft is the offset of the leftmost sort element (smallest).
  673.  *              sRight is the offset of rightmost sort element (largest).
  674.  *
  675.  * Returns: VOID
  676.  *
  677.  * Purpose:  Implements Quick sort which is O(n lg n).  Quick sort is a
  678.  *           good all-purpose sorting algorithm and is widely used.  This
  679.  *           implementation works by placing the first element in the list
  680.  *           into its correct place, by moving all elements smaller to its
  681.  *           left, and all numbers larger to its right.  The Quick sort
  682.  *           recurses on the 2 halves on either side of the properly placed
  683.  *           element.
  684.  *
  685.  * Usage/Warnings:
  686.  *
  687.  * Calls:  QuickSortR() (recursively)
  688.  */
  689.  
  690. VOID QuickSortR(PCALCPARAM pcp, SHORT sLeft, SHORT sRight)
  691. {
  692.    SHORT sTempLeft  = sLeft;    /* Holds lower bound on split position      */
  693.    SHORT sTempRight = sRight;   /* Holds upper bound on split position      */
  694.    SHORT sSplit;                /* Used to hold offset of positioned elem   */
  695.    USHORT usTemp;               /* Holds temp element during positioning    */
  696.  
  697.    if(sLeft>=sRight)            /* If there is <=1 element, return          */
  698.       return;
  699.  
  700.    if(!pcp->fContinueCalc)      /* User wishes to terminate the sort        */
  701.       return;
  702.  
  703.    /* Split list, sSplit will contain the split element */
  704.    usTemp = pcp->Array[sTempLeft];
  705.  
  706.    while(TRUE)       /* Loop thru 2 cases until the split position is found */
  707.    {
  708.       while(pcp->Array[sTempRight] > usTemp && /* Skip elems on right side  */
  709.                         sTempRight > sLeft)    /* that are > the split elem */
  710.          sTempRight--;
  711.  
  712.       if(sTempRight<=sTempLeft)  /* Left and Right have met, split is found */
  713.       {
  714.          pcp->Array[sTempLeft]=usTemp;  /* Place split elem at proper place */
  715.          sSplit = sTempLeft;
  716.          break;
  717.       }
  718.       pcp->Array[sTempLeft++] =
  719.                     pcp->Array[sTempRight];    /* Move small element to LHS */
  720.  
  721.       while(pcp->Array[sTempLeft] < usTemp &&  /* Skip elems on left side   */
  722.                         sTempLeft < sRight)    /* that are < the split elem */
  723.          sTempLeft++;
  724.  
  725.       if(sTempRight<=sTempLeft)  /* Left and Right have met, split is found */
  726.       {
  727.          pcp->Array[sTempRight]=usTemp; /* Place split elem at proper place */
  728.          sSplit = sTempRight;
  729.          break;
  730.       }
  731.       pcp->Array[sTempRight--] =
  732.                     pcp->Array[sTempLeft];     /* Move large element to RHS */
  733.    }
  734.  
  735.    QuickSortR(pcp,sLeft,sSplit-1);     /* Sort the 1st half of the list     */
  736.  
  737.    if(!pcp->fContinueCalc)             /* User wishes to terminate the sort */
  738.       return;
  739.  
  740.    QuickSortR(pcp,sSplit+1,sRight);    /* Sort the 2nd half of the list     */
  741. }
  742.  
  743.  
  744. /*
  745.  * Function name: EnableMenuItem()
  746.  *
  747.  * Parameters:  hwnd is a handle of the current window.
  748.  *              sMenuItem is the ID of the item to Enable/Disable.
  749.  *              fEnable will enable item if TRUE, otherwise disables it.
  750.  *
  751.  * Returns: VOID
  752.  *
  753.  * Purpose: This routine handles enabling/disabling of menu items.  This
  754.  *          is done by getting Parent and Menu hwnd handles then sending
  755.  *          the appropriate message.
  756.  *
  757.  * Usage/Warnings:
  758.  *
  759.  * Calls:
  760.  */
  761.  
  762. VOID EnableMenuItem(HWND hwnd, SHORT sMenuItem, BOOL fEnable)
  763. {
  764.    HWND hwndParent = WinQueryWindow(hwnd, QW_PARENT, FALSE);
  765.    HWND hwndMenu   = WinWindowFromID(hwndParent, FID_MENU);
  766.  
  767.    WinSendMsg(hwndMenu, MM_SETITEMATTR,
  768.               MPFROM2SHORT(sMenuItem, TRUE),
  769.               MPFROM2SHORT(MIA_DISABLED, fEnable ? 0 : MIA_DISABLED));
  770. }
  771.  
  772.  
  773. /*
  774.  * Function name: EntryFldDlgProc()
  775.  *
  776.  * Parameters:  hwnd, msg, mp1, mp2.  Standard PM Dialog Proc params.
  777.  *              A pointer to the current set size is passed in WM_INITDLG.
  778.  *
  779.  * Returns: Terminates with a TRUE iff a new valid data set size is entered.
  780.  *
  781.  * Purpose: Handles all the messages associated with the set entry field
  782.  *          and calls the appropriate handling procedures.  The purpose
  783.  *          of this dialog box is to get a new data set size for the
  784.  *          sort routines.
  785.  *
  786.  *
  787.  * Usage/Warnings: If the value entered is valid, the proc will set the
  788.  *                 variable passed in through the WM_INITDLG to the value.
  789.  *
  790.  * Calls:
  791.  */
  792.  
  793. MRESULT EXPENTRY EntryFldDlgProc(HWND hwnd, USHORT msg, MPARAM mp1, MPARAM mp2)
  794. {
  795.    SHORT sNewSize;                                     /* Holds new set set */
  796.    static USHORT FAR *pcSetSize;    /* Set to point to user-passed set size */
  797.    switch(msg)
  798.    {
  799.       case WM_INITDLG:
  800.          pcSetSize=PVOIDFROMMP(mp2);
  801.          WinSendDlgItemMsg(hwnd, ID_ENTRYFLD,EM_SETTEXTLIMIT,  /* Limit len */
  802.                                  MPFROM2SHORT(3,0),NULL);
  803.          WinSetDlgItemShort(hwnd, ID_ENTRYFLD,(SHORT) *pcSetSize,TRUE);
  804.          return 0L;                           /* Allow normal focus setting */
  805.  
  806.       case WM_COMMAND:
  807.          switch(COMMANDMSG(&msg)->cmd)
  808.          {
  809.             case DID_OK:
  810.                WinQueryDlgItemShort(hwnd, ID_ENTRYFLD,
  811.                                     &sNewSize, TRUE); /* Get the short      */
  812.                if(sNewSize>0 && sNewSize<=NELEMS)  /* Set new data set size */
  813.                {
  814.                   *pcSetSize = (USHORT) sNewSize;
  815.                   WinDismissDlg(hwnd,TRUE);
  816.                }
  817.                else                                   /* Invalid value      */
  818.                   WinDismissDlg(hwnd,FALSE);
  819.                return 0L;
  820.  
  821.             case DID_CANCEL:
  822.                WinDismissDlg(hwnd,FALSE);
  823.                return 0L;
  824.  
  825.             default:
  826.                return WinDefDlgProc(hwnd, msg, mp1, mp2);
  827.          }
  828.  
  829.       default:
  830.          return WinDefDlgProc(hwnd, msg, mp1, mp2);
  831.    }
  832. }
  833.  
  834. /*
  835.  * Function name: RandomizeData()
  836.  *
  837.  * Parameters:  cSetSize is the current size of the data set
  838.  *
  839.  * Returns: VOID
  840.  *
  841.  * Purpose: This routine randomizes the data arrays.
  842.  *
  843.  * Usage/Warnings: This routine assumes that LISTCNT and NELEMS define
  844.  *                 the dimensions of the global Data array which is
  845.  *                 randomized.
  846.  *
  847.  * Calls:
  848.  */
  849.  
  850. VOID RandomizeData(USHORT cSetSize)
  851. {
  852.    USHORT cnt,cnt2;
  853.    for(cnt=0;cnt<LISTCNT;cnt++)
  854.       for(cnt2=0;cnt2<cSetSize;cnt2++)
  855.          Data[cnt][cnt2] = rand();
  856. }
  857.  
  858.  
  859. 
  860.