1 /*
2 //--------------------------------------------------------------------
3 // Copyright (C) 1993,1994:
4 // J.C. Meza
5 // Sandia National Laboratories
6 // meza@california.sandia.gov
7 //--------------------------------------------------------------------
8 */
9
10 #include "pds.h"
11
sort(int ndim,int * total,int * array,int * scheme,int * error)12 int sort(int ndim, int *total, int *array, int *scheme, int *error)
13 {
14 /*******************************************************************
15 *
16 * THIS IS A FORTRAN IMPLEMENTATION OF THE NON-RECURSIVE VERSION FOR
17 * SORTING AN ARRAY OF NUMBERS. THE ALGORITHM IS THAT WHICH APPEARS
18 * AS PROGRAM 2.11 IN WIRTH'S BOOK "ALGORITHMS + DATA STRUCTURES =
19 * PASCAL PROGRAMS", PRENTICE-HALL, 1976. THE MODIFICATION TO
20 * MINIMIZE THE STACK SIZE DESCRIBED IN (2.16) OF THIS REFERENCE IS
21 * ALSO USED.
22 *
23 * -----ON INPUT-----
24 *
25 * ARRAY -- INDEX ARRAY OF POINTERS FOR THE N-TUPLES IN
26 * `SCHEME'
27 *
28 * SCHEME -- THE INTEGER N-TUPLES FOR THE SEARCH STRATEGY NOTE
29 * THAT WE ARE ACTUALLY SORTING THE N-TUPLES IN
30 * `SCHEME', BUT WE USE `ARRAY' TO STORE THIS
31 * ORDERING
32 *
33 * N -- THE DIMENSION OF THE PROBLEM TO BE SOLVED
34 *
35 * TOTAL -- THE NUMBER OF "RAW" POINTS GENERATED FOR `SCHEME'
36 * NOTE THAT THE NUMBER OF ITEMS TO BE SORTED IS
37 * THUS N + 1 + TOTAL
38 *
39 * -----ON OUTPUT----
40 *
41 * ARRAY -- THE INDEX DENOTING A SORTING FOR THE N-TUPLES IN
42 * `SCHEME'. NOTE THAT THE ORIGINAL ARRAY OF
43 * NUMBERS IS WRITTEN OVER AND LOST
44 *
45 * ERROR -- FLAG TO INDICATE THAT THE ARRAY TO BE SORTED IS
46 * TOO LONG FOR THE INTERNAL STACK (SEE COMMENTS
47 * BELOW)
48 *
49 * WRITTEN BY R.M.LEWIS JULY,1986
50 *
51 * LAST MODIFICATION BY VIRGINIA TORCZON FEBRUARY 27, 1992
52 *
53 * WIRTH'S REMEDY TO KEEP THE LENGTH OF THE STACK STACK (`M') LESS
54 * THAN THE LENGTH OF THE LIST TO BE SORTED (`N') LIES IN STACKING
55 * THE SORT REQUEST FOR THE LONGER PARTITION AND CONTINUING DIRECTLY
56 * WITH THE FURTHER PARTITIONING OF THE SMALLER SECTIONS. IF THIS
57 * IS ENFORCED THEN THE LENGTH OF THE STACK CAN BE LIMITED TO M =
58 * LOG N.
59 * 2
60 *
61 * IN THIS IMPLEMENTATION, WE HAVE ALLOCATED THE STACK LOCALLY TO BE
62 * OF LENGTH M, WHICH ALLOWS US TO SORT ARRAYS OF LENGTH UP TO 2**M.
63 * TO MAKE SURE THAT WE DO NOT EXCEED THIS UPPER BOUND, THE
64 * FOLLOWING TEST IS MADE BEFORE BEGINNING THE SEARCH.
65 *
66 *******************************************************************/
67
68 /* System generated locals */
69
70 int array_offset, scheme_dim1, scheme_offset;
71
72 /* Local variables */
73
74 static int temp, i, j, l, r, s, x, stack[64] /* was [32][2] */;
75 extern int order(int, int *, int *);
76 static int power, remain, length;
77
78 /* Parameter adjustments */
79
80 array_offset = -(ndim);
81 array -= array_offset;
82 scheme_dim1 = ndim + 2;
83 scheme_offset = scheme_dim1 * (-(ndim)) - 1;
84 scheme -= scheme_offset;
85
86 /* Function Body */
87
88 power = 0;
89 remain = 0;
90 length = *total + ndim + 1;
91 L50:
92
93 if (length > 1) {
94 ++power;
95 remain += length % 2;
96 length /= 2;
97 goto L50;
98 }
99
100 if (remain > 0) {
101 ++power;
102 }
103
104 if (power <= 32) {
105
106 /* INITIALIZE THE STACK : WE BEGIN THE PARTITIONING AT THE LEFT
107 * AND RIGHT ENDS OF THE ARRAY */
108
109 s = 1;
110 stack[s - 1] = -(ndim);
111 stack[s + 31] = *total;
112
113 /* BEGIN THE LOOP TO SIMULATE RECURSION */
114
115 L100:
116
117 /* TAKE THE TOP REQUEST OFF THE STACK */
118
119 l = stack[s - 1];
120 r = stack[s + 31];
121 --s;
122
123 /* SPLIT { ARRAY(L) , .... , ARRAY(R) } */
124
125 L200:
126 i = l;
127 j = r;
128 x = array[(l + r) / 2];
129
130 L300:
131
132 /* THE FOLLOWING IS EQUIVALENT TO: DO WHILE
133 * (SCHEME(*,I) < SCHEME(*,X))
134 * I = I + 1
135 * END DO */
136
137 L330:
138 if (order(ndim, &scheme[array[i] * scheme_dim1 + 1], &scheme[x *
139 scheme_dim1 + 1]) < 0) {
140 ++i;
141 goto L330;
142 }
143
144 /* THE FOLLOWING IS EQUIVALENT TO: DO WHILE
145 * (SCHEME(*,J) > SCHEME(*,X))
146 * J = J + 1
147 * END DO */
148
149 L350:
150 if (order(ndim, &scheme[array[j] * scheme_dim1 + 1], &scheme[x *
151 scheme_dim1 + 1]) > 0) {
152 --j;
153 goto L350;
154 }
155
156 /* PERFORM A SWAP, AND THEN MOVE ON IN THE SCAN */
157
158 if (i <= j) {
159 temp = array[i];
160 array[i] = array[j];
161 array[j] = temp;
162
163 ++i;
164 --j;
165 }
166
167 if (i <= j) {
168 goto L300;
169 }
170
171 /* PLACE ON THE STACK THE REQUEST TO SORT THE LONGER PARTITION AND
172 * BEGIN FURTHER PARTIONING OF THE SMALLER PARTITIONS */
173
174 if (j - l < r - i) {
175
176 if (i < r) {
177 ++s;
178 stack[s - 1] = i;
179 stack[s + 31] = r;
180 }
181
182 r = j;
183 } else {
184
185 if (l < j) {
186 ++s;
187 stack[s - 1] = l;
188 stack[s + 31] = j;
189 }
190
191 l = i;
192 }
193
194 /* THE FOLLOWING TWO IF-THEN BLOCKS MARK THE ENDS OF TWO
195 * REPEAT-UNTIL BLOCKS. CAN YOU SEE WHAT THEY ARE ??? */
196
197 if (l < r) {
198 goto L200;
199 }
200
201 if (s > 0) {
202 goto L100;
203 } else {
204 return 0;
205 }
206 }
207
208 *error = 1;
209
210 return 0;
211 }
212
quick(int ndim,int * array,int * error)213 int quick(int ndim, int *array, int *error)
214 {
215 /*******************************************************************
216 *
217 * THIS IS A FORTRAN IMPLEMENTATION OF THE NON-RECURSIVE VERSION FOR
218 * SORTING AN ARRAY OF NUMBERS. THE ALGORITHM IS THAT WHICH APPEARS
219 * AS PROGRAM 2.11 IN WIRTH'S BOOK "ALGORITHMS + DATA STRUCTURES =
220 * PASCAL PROGRAMS", PRENTICE-HALL, 1976. THE MODIFICATION TO
221 * MINIMIZE THE STACK SIZE DESCRIBED IN (2.16) OF THIS REFERENCE IS
222 * ALSO USED.
223 *
224 * -----ON INPUT-----
225 *
226 * ARRAY -- THE ARRAY OF NUMBERS TO BE SORTED : THIS ROUTINE
227 * ASSUMES THAT THESE NUMBERS ARE INTEGER.
228 *
229 * N -- THE NUMBER OF ITEMS TO BE SORTED
230 *
231 * -----ON OUTPUT----
232 *
233 * ARRAY -- THE NUMBERS SORTED IN ASCENDING ORDER : NOTE THAT
234 * THE ORIGINAL ARRAY OF NUMBERS IS WRITTEN OVER AND
235 * LOST
236 *
237 * ERROR -- FLAG TO INDICATE THAT THE ARRAY TO BE SORTED IS
238 * TOO LONG FOR THE INTERNAL STACK (SEE COMMENTS
239 * BELOW)
240 *
241 * WRITTEN BY R.M.LEWIS JULY,1986
242 *
243 * LAST MODIFICATION BY VIRGINIA TORCZON FEBRUARY 27, 1992
244 *
245 * WIRTH'S REMEDY TO KEEP THE LENGTH OF THE STACK STACK (`M') LESS
246 * THAN THE LENGTH OF THE LIST TO BE SORTED (`N') LIES IN STACKING
247 * THE SORT REQUEST FOR THE LONGER PARTITION AND CONTINUING DIRECTLY
248 * WITH THE FURTHER PARTITIONING OF THE SMALLER SECTIONS. IF THIS
249 * IS ENFORCED THEN THE LENGTH OF THE STACK CAN BE LIMITED TO M =
250 * LOG N.
251 * 2
252 *
253 * IN THIS IMPLEMENTATION, WE HAVE ALLOCATED THE STACK LOCALLY TO BE
254 * OF LENGTH M, WHICH ALLOWS US TO SORT ARRAYS OF LENGTH UP TO 2**M.
255 * TO MAKE SURE THAT WE DO NOT EXCEED THIS UPPER BOUND, THE
256 * FOLLOWING TEST IS MADE BEFORE BEGINNING THE SEARCH.
257 *
258 *******************************************************************/
259
260 static int temp, i, j, l, r, s, x, stack[64] /* was [32][2] */,
261 power, remain, length;
262
263 /* Parameter adjustments */
264
265 --array;
266
267 /* Function Body */
268
269 power = 0;
270 remain = 0;
271 length = ndim;
272
273 L50:
274 if (length > 1) {
275 ++power;
276 remain += length % 2;
277 length /= 2;
278 goto L50;
279 }
280
281 if (remain > 0) {
282 ++power;
283 }
284
285 if (power <= 32) {
286
287 /* INITIALIZE THE STACK : WE BEGIN THE PARTITIONING AT THE LEFT
288 * AND RIGHT ENDS OF THE ARRAY */
289
290 s = 1;
291 stack[s - 1] = 1;
292 stack[s + 31] = ndim;
293
294
295 /* BEGIN THE LOOP TO SIMULATE RECURSION */
296
297 L100:
298
299 /* TAKE THE TOP REQUEST OFF THE STACK */
300
301 l = stack[s - 1];
302 r = stack[s + 31];
303 --s;
304
305 /* SPLIT { ARRAY(L) , .... , ARRAY(R) } */
306
307 L200:
308 i = l;
309 j = r;
310 x = array[(l + r) / 2];
311
312 L300:
313
314
315 /* THE FOLLOWING IS EQUIVALENT TO : DO WHILE( ARRAY(I) < X )
316 * I = I + 1
317 * END DO */
318
319 L330:
320 if (array[i] < x) {
321 ++i;
322 goto L330;
323 }
324
325 /* THE FOLLOWING IS EQUIVALENT TO : DO WHILE( ARRAY(J) > X )
326 * J = J + 1
327 * END DO */
328
329 L350:
330 if (array[j] > x) {
331 --j;
332 goto L350;
333 }
334
335 /* PERFORM A SWAP, AND THEN MOVE ON IN THE SCAN */
336
337 if (i <= j) {
338 temp = array[i];
339 array[i] = array[j];
340 array[j] = temp;
341
342 ++i;
343 --j;
344 }
345
346 if (i <= j) {
347 goto L300;
348 }
349
350
351 /* PLACE ON THE STACK THE REQUEST TO SORT THE LONGER PARTITION AND
352 * BEGIN FURTHER PARTIONING OF THE SMALLER PARTITIONS */
353
354 if (j - l < r - i) {
355
356 if (i < r) {
357 ++s;
358 stack[s - 1] = i;
359 stack[s + 31] = r;
360 }
361
362 r = j;
363 } else {
364
365 if (l < j) {
366 ++s;
367 stack[s - 1] = l;
368 stack[s + 31] = j;
369 }
370
371 l = i;
372 }
373
374 /* THE FOLLOWING TWO IF-THEN BLOCKS MARK THE ENDS OF TWO
375 * REPEAT-UNTIL BLOCKS. CAN YOU SEE WHAT THEY ARE ??? */
376
377 if (l < r) {
378 goto L200;
379 }
380
381 if (s > 0) {
382 goto L100;
383 } else {
384 return 0;
385 }
386 }
387
388 *error = 1;
389
390 return 0;
391 }
392
393