Return to GenericSort.m CVS log

Up to [NeXTSTEP 3.3 examples] / Examples / AppKit / SortingInAction

Annotation of Examples/AppKit/SortingInAction/GenericSort.m, revision 1.1

1.1     ! root        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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.