home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer) / NeXT_Developer-3.3.iso / NextDeveloper / Examples / AppKit / SortingInAction / GenericSort.m < prev    next >
Encoding:
Text File  |  1992-05-27  |  12.2 KB  |  367 lines
  1.  
  2. /* The GenericSort class is the focal class of this program.  It encapsulates 
  3.  * all the functionality for a sort object:  keeping track of tick counts, 
  4.  * knowing how to animate the sort, controlling the speed, managing the 
  5.  * data.  GenericSort only lacks a specific sorting algorithm.  This makes 
  6.  * way for a great inheritance--each of the specific sort classes needs to 
  7.  * override -init (to assign their unique sort name) and to create a -sort 
  8.  * method.  That's it.  In the sort method, the subclasses use the superclass 
  9.  * methods -lessThan:: and -swap:with: and so on to compare and exchange 
  10.  * values, and the superclass deals with all the implementation details of 
  11.  * animating, speed control, pacing the sorts, etc.  Adding a new sort 
  12.  * algorithm is then trivial, you only need to code the algorithm!
  13.  * Because all the sorting occurs in a separate thread, Generic Sort will cons 
  14.  * up a message to send to the main thread when it is time to do any drawing.
  15.  *
  16.  * Author: Julie Zelenski, NeXT Developer Support
  17.  * You may freely copy, distribute and reuse the code in this example.  
  18.  * NeXT disclaims any warranty of any kind, expressed or implied, as to 
  19.  * its fitness for any particular use.
  20.  */
  21.  
  22.  
  23. #import "GenericSort.h"
  24. #import "SortView.h"
  25. #import "SortApp.h"
  26. #import <mach/cthreads.h>
  27.  
  28. extern BOOL Abort;        // global variable to signal abort 
  29. extern int TickCount;              // global variable of current tick count 
  30. extern mutex_t TickLock;    // mutual exclusion to protect TickCount 
  31. extern condition_t TickUpdated;    // signaled when TickCount is increased 
  32.  
  33.  
  34. @implementation GenericSort:Object
  35.  
  36.  
  37. /* Static class variables */
  38. static int SortsRunning;    // number of sorts fighting for processor
  39. static mutex_t SortsLock;    // mutual exclusion to protect SortsRunning 
  40.  
  41.  
  42. /* FACTORY METHODS */
  43.  
  44. + initialize
  45. /* +initialize is sent to the factory object for GenericSort before any 
  46.  * other messages are sent.  This is a good place to allocate and initialize 
  47.  * static class variables.
  48.  */
  49. {
  50.     SortsRunning = 0;
  51.     SortsLock = mutex_alloc();
  52.     return self;
  53. }
  54.  
  55.  
  56. - init
  57. /* The initialization method sets up a new sort.  The sort creates its own 
  58.  * sortView, and initalizes its instance variables to their default values.  
  59.  * It also builds the message struct it will send as a drawing message.
  60.  */
  61. {
  62.     [super init];
  63.     sortView = [[SortView allocFromZone:[self zone]] initSort:self]; 
  64.     compareVal = 1;
  65.     moveVal = 2;
  66.     fcallVal = 8;
  67.     animate = NO;
  68.     speedDelay = 0;
  69.     drawMsg.h.msg_simple = TRUE;     // no ports or out-of-line data
  70.     drawMsg.h.msg_size = sizeof(simpleMsg);
  71.     drawMsg.h.msg_local_port = PORT_NULL;
  72.     drawMsg.h.msg_type = MSG_TYPE_NORMAL;
  73.     drawMsg.t.msg_type_name = MSG_TYPE_INTEGER_32;
  74.     drawMsg.t.msg_type_size = 32;
  75.     drawMsg.t.msg_type_number = MAXDATA;
  76.     drawMsg.t.msg_type_inline = TRUE;    // no out-of-line data will be passed
  77.     drawMsg.t.msg_type_longform = FALSE;
  78.     drawMsg.t.msg_type_deallocate = FALSE;
  79.     return self;
  80. }
  81.  
  82.  
  83.  
  84. /* TARGET-ACTION METHODS */
  85.  
  86. - setTicks:(int)value for:(int)tag;
  87. /* The SortController passes along this method to each sort when the user 
  88.  * changes the ticks weighting of an operation.  This method assigns
  89.  * the new tick value.
  90.  */
  91. {
  92. #define COMPARE 3
  93. #define MOVE 4
  94. #define FCALL 5    
  95.  
  96.     switch (tag) {
  97.         case COMPARE:    compareVal = value; 
  98.             break;
  99.         case MOVE:     moveVal = value;
  100.              break;
  101.         case FCALL:     fcallVal = value;
  102.             break;
  103.     }
  104.     return self;
  105. }
  106.  
  107.  
  108. - setAnimate:(BOOL)value;
  109. /* The SortController passes along this method to each sort when the user 
  110.  * changes the animate compares switch.  This method can be sent while the
  111.  * sort is sorting, and it immediately takes effect--the next comparison 
  112.  * will highlight or not, depending on the new value.
  113.  */
  114. {
  115.     animate = value;
  116.     return self;
  117. }
  118.  
  119.  
  120. - setSpeed:(int)value;
  121. /* The SortController passes along this method to each sort when the user 
  122.  * moves the speed slider.  This method can be sent while the sort is sorting, 
  123.  * and it immediately takes effect--the sorts will begin to slow down or 
  124.  * speed up accordingly. 
  125.  */
  126. {
  127.     speedDelay = value;
  128.     return self;
  129. }
  130.  
  131.  
  132. - setSize:(int)size address:(int*)address
  133. /* Called by the SortController when the user has started a sort.  This method
  134.  * makes its own private copy of the data set generated by the SortController 
  135.  * and grabs a hold of the port to send drawing messages to.  Then it sends 
  136.  * a drawing message to the main thread to draw each of the bars.
  137.  */
  138. {
  139.     int c;
  140.  
  141.     numElements = size;
  142.     [sortView setUpForSize:numElements]; //calculate size and placement of bars
  143.     data = (int *)calloc(numElements,sizeof(int));
  144.     drawMsg.h.msg_remote_port = [NXApp drawPort]; //set port to send drawing to
  145.     drawMsg.sortNum = sortNum;    // first parameter in drawMsg is my sort number
  146.     for (c = 0; c < numElements; c++) {    // for each element in the data set
  147.         data[c] = address[c];
  148.         drawMsg.h.msg_id = MOVE_MSG;
  149.         drawMsg.position[0] = c;
  150.         drawMsg.value[0] = data[c];
  151.         drawMsg.value[1] = 0;
  152.         msg_send((msg_header_t *)&drawMsg,MSG_OPTION_NONE,0); 
  153.     }
  154.     return self;
  155. }
  156.  
  157.  
  158.  
  159. /* PRIVATE METHODS */
  160.  
  161. - abort;
  162. /* Called when the sort notices that the global variable Abort has been 
  163.  * signaled. This calls sortDone to clean up after itself and exits the 
  164.  * cthread.
  165.  */
  166. {
  167.     [self sortDone];             // signal done
  168.     cthread_exit(0);        // kill thread
  169.     return nil;
  170. }
  171.  
  172.  
  173. - sortDone;
  174. /* Called when a sort has exited, either because it completed sorting or Abort 
  175.  * was signaled.  It sends one last message to the drawPort to draw the 
  176.  * finished sortView.  It also grabs the mutex for SortsRunning and decrements 
  177.  * it by one.  It signals TickUpdated so any other thread waiting will wake up.
  178.  */ 
  179. {
  180.     drawMsg.h.msg_id = FINISHED_MSG;    // send finished message to main thread
  181.     msg_send((msg_header_t *)&drawMsg,MSG_OPTION_NONE,0); // draw finished
  182.     mutex_lock(SortsLock);        // must protect shared global!!
  183.     SortsRunning--;            // decrement number of sorts running
  184.     mutex_unlock(SortsLock);
  185.     condition_signal(TickUpdated);    // wake up any sleeping threads
  186.     if (data) cfree(data);        // free the data set
  187.     numElements = 0;
  188.     return self;
  189. }
  190.  
  191.  
  192.  
  193. static void myWait(int millisecs)
  194. /* Because the unix function usleep() is not thread-safe, I wrote a little 
  195.  * function to delay the sorts for a specified number of milliseconds. 
  196.  * Basically it allocates a port for itself and then tries to receive a 
  197.  * message on that port.  I don't send any messages to that port, so it is 
  198.  * waiting futilely.  However, I indicate the msg_receive should time out in 
  199.  * the number of milliseconds I wanted to wait.
  200.  */
  201. {
  202.     msg_header_t nullMsg;
  203.     port_t aPort;
  204.     
  205.     if (port_allocate(task_self(), &aPort) != KERN_SUCCESS) return;
  206.     nullMsg.msg_local_port = aPort;
  207.     nullMsg.msg_size = sizeof(nullMsg);
  208.     
  209.     msg_receive(&nullMsg,RCV_TIMEOUT,millisecs);// wait until timeout
  210.     port_deallocate(task_self(),aPort);        // clean up
  211. }
  212.  
  213.  
  214. - adjust      
  215. /* Adjust is called to make the sorts out in front wait for the other sorts 
  216.  * to catch up before going on.  If this thread is in the lead (i.e. if its 
  217.  * tick count is ahead of the global variable TickCount), it will increment 
  218.  * TickCount, signal the condition TickUpdated (to wake up other sleeping 
  219.  * threads) and then put itself to sleep waiting for another sort to catch up 
  220.  * and signal the TickUpdated condition.  Of course, if this is the only sort 
  221.  * running (if SortsRunning = 1) then I don't put myself into endless sleep 
  222.  * waiting for a non-existent sort to catch up with me!  
  223.  * The adjust method also is used to regulate the speed (corresponding to the 
  224.  * speed slider).  Each thread will delay a number of milliseconds in this 
  225.  * method based on how slow the animation should be.  (see myWait() function 
  226.  * above)  At top speed, the sorts delay 0 milliseconds, but in slow motion 
  227.  * they can delay up to half a second in this method.
  228.  */
  229. {   
  230.     int ticks;
  231.     
  232.     if (speedDelay) myWait(speedDelay);    // wait speedDelay number of mseconds
  233.     ticks = compareVal*compares + moveVal*moves + fcallVal*fcalls;
  234.     mutex_lock(TickLock);
  235.     if (ticks > TickCount) {        // if out in front
  236.     TickCount = ticks;        // increment counter
  237.     if (SortsRunning > 1) {    // if other sorts are running
  238.         condition_signal(TickUpdated); // signal counter has incremented
  239.         condition_wait(TickUpdated,TickLock); // wait til counter updated
  240.         }
  241.     }
  242.     mutex_unlock(TickLock); 
  243.     if (Abort) [self abort];
  244.     return self;
  245. }
  246.  
  247.  
  248. - swap:(int)position1 with:(int)position2
  249. /* To exchange values, the specific sort subclasses use the generic sort method 
  250.  * swap:with.  This method exchanges the data elements, and sends a message 
  251.  * to the main thread to do the drawing for that swap.  Before messaging, it 
  252.  * calls the adjust method to make sure that sorts out in front wait for the 
  253.  * other sorts to catch up before going on.  NOTE: Swap expects that the 
  254.  * smaller value is in position1. 
  255.  */
  256. {    
  257.     int temp;
  258.     
  259.     moves += 2;     // a swap involves two moves
  260.     [self adjust];  
  261.     drawMsg.h.msg_id = SWAP_MSG;    // send a swap message to main thread
  262.     drawMsg.position[0] = position1;
  263.     drawMsg.value[0] = data[position1];
  264.     drawMsg.position[1] = position2;
  265.     drawMsg.value[1] = data[position2];
  266.     msg_send((msg_header_t *)&drawMsg,MSG_OPTION_NONE,0);
  267.     temp = data[position1];
  268.     data[position1] = data[position2];
  269.     data[position2] = temp;
  270.     return self;
  271. }
  272.  
  273.  
  274. - moveValue:(int)value to:(int)position
  275. /* To change the value at a specific position, the specific sort subclasses 
  276.  * use the generic sort method moveValue:to.  This method assigns the new value 
  277.  * to the element, the data elements, and sends a message to the main thread to 
  278.  * do the drawing for that move.  Before messaging, it calls the adjust method 
  279.  * to make sure that sorts out in front wait for the other sorts to catch up 
  280.  * before going on.  
  281.  */
  282. {      
  283.     moves++;
  284.     [self adjust]; 
  285.     drawMsg.h.msg_id = MOVE_MSG;    // send a move message to main thread
  286.     drawMsg.value[0] = value;
  287.     drawMsg.position[0] = position;
  288.     drawMsg.value[1] = data[position];
  289.     msg_send((msg_header_t *)&drawMsg,MSG_OPTION_NONE,0);
  290.     data[position] = value;  
  291.     return self;
  292. }
  293.  
  294.  
  295. - (BOOL)lessThan:(int)position1 :(int)position2
  296. /* To compares two values in the data set, the specific sort subclasses 
  297.  * use the generic sort method lessThan::.  This method returns the value 
  298.  * of the comparison, and if the sort is currently animating compares, it 
  299.  * will send a message to the main thread highlight the two elements being 
  300.  * compared.  Before messaging, it calls the adjust method to make sure that 
  301.  * sorts out in front wait for the other sorts to catch up before going on.  
  302.  */
  303. {        
  304.     compares++;     
  305.     [self adjust];
  306.     if (animate) {            // if animating compares
  307.     drawMsg.h.msg_id = COMPARE_MSG;    // send compare message to main thread
  308.     drawMsg.position[0] = position1;
  309.     drawMsg.value[0] = data[position1];
  310.     drawMsg.position[1] = position2;
  311.     drawMsg.value[1] = data[position2];
  312.     msg_send((msg_header_t *)&drawMsg,MSG_OPTION_NONE,0);    
  313.     }
  314.     return (data[position1] < data[position2]);
  315. }
  316.  
  317.  
  318. /* PUBLIC METHODS */
  319.  
  320. - sort;  
  321. /* The method is the heart of the GenericSort class.  It is called to do the 
  322.  * actual sorting.  The specific subclasses of GenericSort should override this 
  323.  * method, making sure that the first line of their -sort method is call 
  324.  * [super sort].  In the super version, this method is mostly a stub but it 
  325.  * does perform a few important tasks, notably setting the counters to zero and 
  326.  * adding this sort to the number of sorts currently running.
  327.  */ 
  328. {
  329.     compares = moves = fcalls = 0;
  330.     mutex_lock(SortsLock);    // must protect share global!!
  331.     SortsRunning++;
  332.     mutex_unlock(SortsLock);
  333.     drawMsg.h.msg_id = SORTING_MSG;         // send message to main thread
  334.     msg_send((msg_header_t *)&drawMsg,MSG_OPTION_NONE,0);  // status "Sorting"
  335.     return self;
  336. }
  337.  
  338.  
  339.  
  340. /* These methods simply retrieve instance variables of the sort object */
  341.  
  342. - view;
  343. {   
  344.     return sortView; 
  345. }
  346. - (const char*)getName;
  347. {
  348.     return sortName;
  349. }
  350. - (int)compares
  351. {
  352.     return compares;
  353. }
  354. - (int)moves
  355. {
  356.     return moves;
  357. }
  358. - (int)fcalls;
  359. {
  360.     return fcalls;
  361. }
  362. - (int)totalTicks
  363. {
  364.     return (compareVal*compares + moveVal*moves + fcallVal*fcalls);
  365. }
  366.  
  367. @end