![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to GenericSort.m CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [NeXTSTEP 3.3 examples] / Examples / AppKit / SortingInAction|
Return to GenericSort.m CVS log | Up to [NeXTSTEP 3.3 examples] / Examples / AppKit / SortingInAction |
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.