Return to GenericSort.m CVS log

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

Sample Programs from NeXSTEP 3.3

/* The GenericSort class is the focal class of this program.  It encapsulates 
 * all the functionality for a sort object:  keeping track of tick counts, 
 * knowing how to animate the sort, controlling the speed, managing the 
 * data.  GenericSort only lacks a specific sorting algorithm.  This makes 
 * way for a great inheritance--each of the specific sort classes needs to 
 * override -init (to assign their unique sort name) and to create a -sort 
 * method.  That's it.  In the sort method, the subclasses use the superclass 
 * methods -lessThan:: and -swap:with: and so on to compare and exchange 
 * values, and the superclass deals with all the implementation details of 
 * animating, speed control, pacing the sorts, etc.  Adding a new sort 
 * algorithm is then trivial, you only need to code the algorithm!
 * Because all the sorting occurs in a separate thread, Generic Sort will cons 
 * up a message to send to the main thread when it is time to do any drawing.
 *
 * Author: Julie Zelenski, NeXT Developer Support
 * You may freely copy, distribute and reuse the code in this example.  
 * NeXT disclaims any warranty of any kind, expressed or implied, as to 
 * its fitness for any particular use.
 */


#import "GenericSort.h"
#import "SortView.h"
#import "SortApp.h"
#import <mach/cthreads.h>

extern BOOL Abort;		// global variable to signal abort 
extern int TickCount;          	// global variable of current tick count 
extern mutex_t TickLock;	// mutual exclusion to protect TickCount 
extern condition_t TickUpdated;	// signaled when TickCount is increased 


@implementation GenericSort:Object


/* Static class variables */
static int SortsRunning;	// number of sorts fighting for processor
static mutex_t SortsLock;	// mutual exclusion to protect SortsRunning 


/* FACTORY METHODS */

+ initialize
/* +initialize is sent to the factory object for GenericSort before any 
 * other messages are sent.  This is a good place to allocate and initialize 
 * static class variables.
 */
{
    SortsRunning = 0;
    SortsLock = mutex_alloc();
    return self;
}


- init
/* The initialization method sets up a new sort.  The sort creates its own 
 * sortView, and initalizes its instance variables to their default values.  
 * It also builds the message struct it will send as a drawing message.
 */
{
    [super init];
    sortView = [[SortView allocFromZone:[self zone]] initSort:self]; 
    compareVal = 1;
    moveVal = 2;
    fcallVal = 8;
    animate = NO;
    speedDelay = 0;
    drawMsg.h.msg_simple = TRUE; 	// no ports or out-of-line data
    drawMsg.h.msg_size = sizeof(simpleMsg);
    drawMsg.h.msg_local_port = PORT_NULL;
    drawMsg.h.msg_type = MSG_TYPE_NORMAL;
    drawMsg.t.msg_type_name = MSG_TYPE_INTEGER_32;
    drawMsg.t.msg_type_size = 32;
    drawMsg.t.msg_type_number = MAXDATA;
    drawMsg.t.msg_type_inline = TRUE;	// no out-of-line data will be passed
    drawMsg.t.msg_type_longform = FALSE;
    drawMsg.t.msg_type_deallocate = FALSE;
    return self;
}



/* TARGET-ACTION METHODS */

- setTicks:(int)value for:(int)tag;
/* The SortController passes along this method to each sort when the user 
 * changes the ticks weighting of an operation.  This method assigns
 * the new tick value.
 */
{
#define COMPARE 3
#define MOVE 4
#define FCALL 5	

    switch (tag) {
        case COMPARE:	compareVal = value; 
			break;
        case MOVE: 	moveVal = value;
		 	break;
        case FCALL: 	fcallVal = value;
			break;
    }
    return self;
}


- setAnimate:(BOOL)value;
/* The SortController passes along this method to each sort when the user 
 * changes the animate compares switch.  This method can be sent while the
 * sort is sorting, and it immediately takes effect--the next comparison 
 * will highlight or not, depending on the new value.
 */
{
    animate = value;
    return self;
}


- setSpeed:(int)value;
/* The SortController passes along this method to each sort when the user 
 * moves the speed slider.  This method can be sent while the sort is sorting, 
 * and it immediately takes effect--the sorts will begin to slow down or 
 * speed up accordingly. 
 */
{
    speedDelay = value;
    return self;
}


- setSize:(int)size address:(int*)address
/* Called by the SortController when the user has started a sort.  This method
 * makes its own private copy of the data set generated by the SortController 
 * and grabs a hold of the port to send drawing messages to.  Then it sends 
 * a drawing message to the main thread to draw each of the bars.
 */
{
    int c;

    numElements = size;
    [sortView setUpForSize:numElements]; //calculate size and placement of bars
    data = (int *)calloc(numElements,sizeof(int));
    drawMsg.h.msg_remote_port = [NXApp drawPort]; //set port to send drawing to
    drawMsg.sortNum = sortNum;	// first parameter in drawMsg is my sort number
    for (c = 0; c < numElements; c++) {	// for each element in the data set
        data[c] = address[c];
        drawMsg.h.msg_id = MOVE_MSG;
        drawMsg.position[0] = c;
        drawMsg.value[0] = data[c];
        drawMsg.value[1] = 0;
        msg_send((msg_header_t *)&drawMsg,MSG_OPTION_NONE,0); 
    }
    return self;
}



/* PRIVATE METHODS */

- abort;
/* Called when the sort notices that the global variable Abort has been 
 * signaled. This calls sortDone to clean up after itself and exits the 
 * cthread.
 */
{
    [self sortDone];         	// signal done
    cthread_exit(0);		// kill thread
    return nil;
}


- sortDone;
/* Called when a sort has exited, either because it completed sorting or Abort 
 * was signaled.  It sends one last message to the drawPort to draw the 
 * finished sortView.  It also grabs the mutex for SortsRunning and decrements 
 * it by one.  It signals TickUpdated so any other thread waiting will wake up.
 */ 
{
    drawMsg.h.msg_id = FINISHED_MSG;    // send finished message to main thread
    msg_send((msg_header_t *)&drawMsg,MSG_OPTION_NONE,0); // draw finished
    mutex_lock(SortsLock);		// must protect shared global!!
    SortsRunning--;			// decrement number of sorts running
    mutex_unlock(SortsLock);
    condition_signal(TickUpdated);	// wake up any sleeping threads
    if (data) cfree(data);		// free the data set
    numElements = 0;
    return self;
}



static void myWait(int millisecs)
/* Because the unix function usleep() is not thread-safe, I wrote a little 
 * function to delay the sorts for a specified number of milliseconds. 
 * Basically it allocates a port for itself and then tries to receive a 
 * message on that port.  I don't send any messages to that port, so it is 
 * waiting futilely.  However, I indicate the msg_receive should time out in 
 * the number of milliseconds I wanted to wait.
 */
{
    msg_header_t nullMsg;
    port_t aPort;
    
    if (port_allocate(task_self(), &aPort) != KERN_SUCCESS) return;
    nullMsg.msg_local_port = aPort;
    nullMsg.msg_size = sizeof(nullMsg);
    
    msg_receive(&nullMsg,RCV_TIMEOUT,millisecs);// wait until timeout
    port_deallocate(task_self(),aPort);		// clean up
}


- adjust      
/* Adjust is called to make the sorts out in front wait for the other sorts 
 * to catch up before going on.  If this thread is in the lead (i.e. if its 
 * tick count is ahead of the global variable TickCount), it will increment 
 * TickCount, signal the condition TickUpdated (to wake up other sleeping 
 * threads) and then put itself to sleep waiting for another sort to catch up 
 * and signal the TickUpdated condition.  Of course, if this is the only sort 
 * running (if SortsRunning = 1) then I don't put myself into endless sleep 
 * waiting for a non-existent sort to catch up with me!  
 * The adjust method also is used to regulate the speed (corresponding to the 
 * speed slider).  Each thread will delay a number of milliseconds in this 
 * method based on how slow the animation should be.  (see myWait() function 
 * above)  At top speed, the sorts delay 0 milliseconds, but in slow motion 
 * they can delay up to half a second in this method.
 */
{   
    int ticks;
    
    if (speedDelay) myWait(speedDelay);	// wait speedDelay number of mseconds
    ticks = compareVal*compares + moveVal*moves + fcallVal*fcalls;
    mutex_lock(TickLock);
    if (ticks > TickCount) {		// if out in front
	TickCount = ticks;		// increment counter
	if (SortsRunning > 1) {	// if other sorts are running
	    condition_signal(TickUpdated); // signal counter has incremented
	    condition_wait(TickUpdated,TickLock); // wait til counter updated
        }
    }
    mutex_unlock(TickLock); 
    if (Abort) [self abort];
    return self;
}


- swap:(int)position1 with:(int)position2
/* To exchange values, the specific sort subclasses use the generic sort method 
 * swap:with.  This method exchanges the data elements, and sends a message 
 * to the main thread to do the drawing for that swap.  Before messaging, it 
 * calls the adjust method to make sure that sorts out in front wait for the 
 * other sorts to catch up before going on.  NOTE: Swap expects that the 
 * smaller value is in position1. 
 */
{    
    int temp;
    
    moves += 2;     // a swap involves two moves
    [self adjust];  
    drawMsg.h.msg_id = SWAP_MSG;	// send a swap message to main thread
    drawMsg.position[0] = position1;
    drawMsg.value[0] = data[position1];
    drawMsg.position[1] = position2;
    drawMsg.value[1] = data[position2];
    msg_send((msg_header_t *)&drawMsg,MSG_OPTION_NONE,0);
    temp = data[position1];
    data[position1] = data[position2];
    data[position2] = temp;
    return self;
}


- moveValue:(int)value to:(int)position
/* To change the value at a specific position, the specific sort subclasses 
 * use the generic sort method moveValue:to.  This method assigns the new value 
 * to the element, the data elements, and sends a message to the main thread to 
 * do the drawing for that move.  Before messaging, it calls the adjust method 
 * to make sure that sorts out in front wait for the other sorts to catch up 
 * before going on.  
 */
{      
    moves++;
    [self adjust]; 
    drawMsg.h.msg_id = MOVE_MSG;	// send a move message to main thread
    drawMsg.value[0] = value;
    drawMsg.position[0] = position;
    drawMsg.value[1] = data[position];
    msg_send((msg_header_t *)&drawMsg,MSG_OPTION_NONE,0);
    data[position] = value;  
    return self;
}


- (BOOL)lessThan:(int)position1 :(int)position2
/* To compares two values in the data set, the specific sort subclasses 
 * use the generic sort method lessThan::.  This method returns the value 
 * of the comparison, and if the sort is currently animating compares, it 
 * will send a message to the main thread highlight the two elements being 
 * compared.  Before messaging, it calls the adjust method to make sure that 
 * sorts out in front wait for the other sorts to catch up before going on.  
 */
{        
    compares++;     
    [self adjust];
    if (animate) {			// if animating compares
	drawMsg.h.msg_id = COMPARE_MSG;	// send compare message to main thread
	drawMsg.position[0] = position1;
	drawMsg.value[0] = data[position1];
	drawMsg.position[1] = position2;
	drawMsg.value[1] = data[position2];
	msg_send((msg_header_t *)&drawMsg,MSG_OPTION_NONE,0);    
    }
    return (data[position1] < data[position2]);
}


/* PUBLIC METHODS */

- sort;  
/* The method is the heart of the GenericSort class.  It is called to do the 
 * actual sorting.  The specific subclasses of GenericSort should override this 
 * method, making sure that the first line of their -sort method is call 
 * [super sort].  In the super version, this method is mostly a stub but it 
 * does perform a few important tasks, notably setting the counters to zero and 
 * adding this sort to the number of sorts currently running.
 */ 
{
    compares = moves = fcalls = 0;
    mutex_lock(SortsLock);	// must protect share global!!
    SortsRunning++;
    mutex_unlock(SortsLock);
    drawMsg.h.msg_id = SORTING_MSG;	 	// send message to main thread
    msg_send((msg_header_t *)&drawMsg,MSG_OPTION_NONE,0);  // status "Sorting"
    return self;
}



/* These methods simply retrieve instance variables of the sort object */

- view;
{   
    return sortView; 
}
- (const char*)getName;
{
    return sortName;
}
- (int)compares
{
    return compares;
}
- (int)moves
{
    return moves;
}
- (int)fcalls;
{
    return fcalls;
}
- (int)totalTicks
{
    return (compareVal*compares + moveVal*moves + fcallVal*fcalls);
}

@end

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