This is GenericSort.m in view mode; [Download] [Up]
/* 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 <threadkit/threadkit.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;
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));
[ NXApp threadLock ] ;
for (c = 0; c < numElements; c++) { // for each element in the data set
data[c] = address[c];
[sortView moveValue:data[c] to:c oldValue:0];
}
[ NXApp threadUnlock ] ;
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
[ TKThread exit ] ; // 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.
*/
{
[ NXApp threadLock ] ;
[sortView displayFinished];
[ NXApp notifyDone: sortNum ] ;
[ NXApp threadUnlock ] ;
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];
[ NXApp threadLock ] ;
[sortView swap:position1 value:data[position1]
with:position2 value:data[position2]];
[ NXApp threadUnlock ] ;
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];
[ NXApp threadLock ] ;
[sortView moveValue:value to:position
oldValue:data[position]];
[ NXApp threadUnlock ] ;
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
[ NXApp threadLock ] ;
[sortView compare:position1 value:data[position1]
with:position2 value:data[position2]];
[ NXApp threadUnlock ] ;
}
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);
[ NXApp threadLock ] ;
[ NXApp notifySorting ] ;
[ NXApp threadUnlock ] ;
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);
}
@endThese are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.