4851
|
1 /* |
|
2 Copyright (C) 2003 David Bateman |
|
3 |
|
4 This file is part of Octave. |
|
5 |
|
6 Octave is free software; you can redistribute it and/or modify it |
|
7 under the terms of the GNU General Public License as published by the |
|
8 Free Software Foundation; either version 2, or (at your option) any |
|
9 later version. |
|
10 |
|
11 Octave is distributed in the hope that it will be useful, but WITHOUT |
|
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
14 for more details. |
|
15 |
|
16 You should have received a copy of the GNU General Public License |
|
17 along with Octave; see the file COPYING. If not, write to the Free |
5307
|
18 Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
|
19 02110-1301, USA. |
4851
|
20 |
|
21 Code stolen in large part from Python's, listobject.c, which itself had |
|
22 no license header. However, thanks to Tim Peters for the parts of the |
|
23 code I ripped-off. |
|
24 |
|
25 As required in the Python license the short description of the changes |
|
26 made are |
|
27 |
|
28 * convert the sorting code in listobject.cc into a generic class, |
|
29 replacing PyObject* with the type of the class T. |
|
30 |
|
31 The Python license is |
|
32 |
|
33 PSF LICENSE AGREEMENT FOR PYTHON 2.3 |
|
34 -------------------------------------- |
|
35 |
|
36 1. This LICENSE AGREEMENT is between the Python Software Foundation |
|
37 ("PSF"), and the Individual or Organization ("Licensee") accessing and |
|
38 otherwise using Python 2.3 software in source or binary form and its |
|
39 associated documentation. |
|
40 |
|
41 2. Subject to the terms and conditions of this License Agreement, PSF |
|
42 hereby grants Licensee a nonexclusive, royalty-free, world-wide |
|
43 license to reproduce, analyze, test, perform and/or display publicly, |
|
44 prepare derivative works, distribute, and otherwise use Python 2.3 |
|
45 alone or in any derivative version, provided, however, that PSF's |
|
46 License Agreement and PSF's notice of copyright, i.e., "Copyright (c) |
|
47 2001, 2002, 2003 Python Software Foundation; All Rights Reserved" are |
|
48 retained in Python 2.3 alone or in any derivative version prepared by |
|
49 Licensee. |
|
50 |
|
51 3. In the event Licensee prepares a derivative work that is based on |
|
52 or incorporates Python 2.3 or any part thereof, and wants to make |
|
53 the derivative work available to others as provided herein, then |
|
54 Licensee hereby agrees to include in any such work a brief summary of |
|
55 the changes made to Python 2.3. |
|
56 |
|
57 4. PSF is making Python 2.3 available to Licensee on an "AS IS" |
|
58 basis. PSF MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR |
|
59 IMPLIED. BY WAY OF EXAMPLE, BUT NOT LIMITATION, PSF MAKES NO AND |
|
60 DISCLAIMS ANY REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR FITNESS |
|
61 FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF PYTHON 2.3 WILL NOT |
|
62 INFRINGE ANY THIRD PARTY RIGHTS. |
|
63 |
|
64 5. PSF SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PYTHON |
|
65 2.3 FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR LOSS AS |
|
66 A RESULT OF MODIFYING, DISTRIBUTING, OR OTHERWISE USING PYTHON 2.3, |
|
67 OR ANY DERIVATIVE THEREOF, EVEN IF ADVISED OF THE POSSIBILITY THEREOF. |
|
68 |
|
69 6. This License Agreement will automatically terminate upon a material |
|
70 breach of its terms and conditions. |
|
71 |
|
72 7. Nothing in this License Agreement shall be deemed to create any |
|
73 relationship of agency, partnership, or joint venture between PSF and |
|
74 Licensee. This License Agreement does not grant permission to use PSF |
|
75 trademarks or trade name in a trademark sense to endorse or promote |
|
76 products or services of Licensee, or any third party. |
|
77 |
|
78 8. By copying, installing or otherwise using Python 2.3, Licensee |
|
79 agrees to be bound by the terms and conditions of this License |
|
80 Agreement. |
|
81 */ |
|
82 |
|
83 #ifdef HAVE_CONFIG_H |
|
84 #include <config.h> |
|
85 #endif |
|
86 |
5883
|
87 #include <cassert> |
6482
|
88 #include <cstdlib> |
5883
|
89 |
4851
|
90 #include "lo-mappers.h" |
|
91 #include "quit.h" |
|
92 #include "oct-sort.h" |
|
93 |
|
94 #define IFLT(a,b) if (compare == NULL ? ((a) < (b)) : compare ((a), (b))) |
|
95 |
|
96 template <class T> |
|
97 octave_sort<T>::octave_sort (void) : compare (NULL) |
|
98 { |
4998
|
99 merge_init (); |
4851
|
100 merge_getmem (1024); |
|
101 } |
|
102 |
|
103 template <class T> |
|
104 octave_sort<T>::octave_sort (bool (*comp) (T, T)) : compare (comp) |
|
105 { |
4998
|
106 merge_init (); |
4851
|
107 merge_getmem (1024); |
|
108 } |
|
109 |
|
110 /* Reverse a slice of a list in place, from lo up to (exclusive) hi. */ |
|
111 template <class T> |
|
112 void |
|
113 octave_sort<T>::reverse_slice(T *lo, T *hi) |
|
114 { |
|
115 --hi; |
|
116 while (lo < hi) |
|
117 { |
|
118 T t = *lo; |
|
119 *lo = *hi; |
|
120 *hi = t; |
|
121 ++lo; |
|
122 --hi; |
|
123 } |
|
124 } |
|
125 |
|
126 template <class T> |
|
127 void |
|
128 octave_sort<T>::binarysort (T *lo, T *hi, T *start) |
|
129 { |
|
130 register T *l, *p, *r; |
|
131 register T pivot; |
|
132 |
|
133 if (lo == start) |
|
134 ++start; |
|
135 |
|
136 for (; start < hi; ++start) |
|
137 { |
|
138 /* set l to where *start belongs */ |
|
139 l = lo; |
|
140 r = start; |
|
141 pivot = *r; |
|
142 /* Invariants: |
|
143 * pivot >= all in [lo, l). |
|
144 * pivot < all in [r, start). |
|
145 * The second is vacuously true at the start. |
|
146 */ |
|
147 do |
|
148 { |
|
149 p = l + ((r - l) >> 1); |
|
150 IFLT (pivot, *p) |
|
151 r = p; |
|
152 else |
|
153 l = p+1; |
|
154 } |
|
155 while (l < r); |
|
156 /* The invariants still hold, so pivot >= all in [lo, l) and |
|
157 pivot < all in [l, start), so pivot belongs at l. Note |
|
158 that if there are elements equal to pivot, l points to the |
|
159 first slot after them -- that's why this sort is stable. |
|
160 Slide over to make room. |
|
161 Caution: using memmove is much slower under MSVC 5; |
|
162 we're not usually moving many slots. */ |
|
163 for (p = start; p > l; --p) |
|
164 *p = *(p-1); |
|
165 *l = pivot; |
|
166 } |
|
167 |
|
168 return; |
|
169 } |
|
170 |
|
171 /* |
|
172 Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi |
|
173 is required on entry. "A run" is the longest ascending sequence, with |
|
174 |
|
175 lo[0] <= lo[1] <= lo[2] <= ... |
|
176 |
|
177 or the longest descending sequence, with |
|
178 |
|
179 lo[0] > lo[1] > lo[2] > ... |
|
180 |
|
181 Boolean *descending is set to 0 in the former case, or to 1 in the latter. |
|
182 For its intended use in a stable mergesort, the strictness of the defn of |
|
183 "descending" is needed so that the caller can safely reverse a descending |
|
184 sequence without violating stability (strict > ensures there are no equal |
|
185 elements to get out of order). |
|
186 |
|
187 Returns -1 in case of error. |
|
188 */ |
|
189 template <class T> |
|
190 int |
|
191 octave_sort<T>::count_run(T *lo, T *hi, int *descending) |
|
192 { |
|
193 int n; |
|
194 |
|
195 *descending = 0; |
|
196 ++lo; |
|
197 if (lo == hi) |
|
198 return 1; |
|
199 |
|
200 n = 2; |
|
201 |
|
202 IFLT (*lo, *(lo-1)) |
|
203 { |
|
204 *descending = 1; |
|
205 for (lo = lo+1; lo < hi; ++lo, ++n) |
|
206 { |
|
207 IFLT (*lo, *(lo-1)) |
|
208 ; |
|
209 else |
|
210 break; |
|
211 } |
|
212 } |
|
213 else |
|
214 { |
|
215 for (lo = lo+1; lo < hi; ++lo, ++n) |
|
216 { |
|
217 IFLT (*lo, *(lo-1)) |
|
218 break; |
|
219 } |
|
220 } |
|
221 |
|
222 return n; |
|
223 } |
|
224 |
|
225 /* |
|
226 Locate the proper position of key in a sorted vector; if the vector contains |
|
227 an element equal to key, return the position immediately to the left of |
|
228 the leftmost equal element. [gallop_right() does the same except returns |
|
229 the position to the right of the rightmost equal element (if any).] |
|
230 |
|
231 "a" is a sorted vector with n elements, starting at a[0]. n must be > 0. |
|
232 |
|
233 "hint" is an index at which to begin the search, 0 <= hint < n. The closer |
|
234 hint is to the final result, the faster this runs. |
|
235 |
|
236 The return value is the int k in 0..n such that |
|
237 |
|
238 a[k-1] < key <= a[k] |
|
239 |
|
240 pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW, |
|
241 key belongs at index k; or, IOW, the first k elements of a should precede |
|
242 key, and the last n-k should follow key. |
|
243 |
|
244 Returns -1 on error. See listsort.txt for info on the method. |
|
245 */ |
|
246 template <class T> |
|
247 int |
|
248 octave_sort<T>::gallop_left(T key, T *a, int n, int hint) |
|
249 { |
|
250 int ofs; |
|
251 int lastofs; |
|
252 int k; |
|
253 |
|
254 a += hint; |
|
255 lastofs = 0; |
|
256 ofs = 1; |
|
257 IFLT (*a, key) |
|
258 { |
|
259 /* a[hint] < key -- gallop right, until |
|
260 * a[hint + lastofs] < key <= a[hint + ofs] |
|
261 */ |
|
262 const int maxofs = n - hint; /* &a[n-1] is highest */ |
|
263 while (ofs < maxofs) |
|
264 { |
|
265 IFLT (a[ofs], key) |
|
266 { |
|
267 lastofs = ofs; |
|
268 ofs = (ofs << 1) + 1; |
|
269 if (ofs <= 0) /* int overflow */ |
|
270 ofs = maxofs; |
|
271 } |
|
272 else /* key <= a[hint + ofs] */ |
|
273 break; |
|
274 } |
|
275 if (ofs > maxofs) |
|
276 ofs = maxofs; |
|
277 /* Translate back to offsets relative to &a[0]. */ |
|
278 lastofs += hint; |
|
279 ofs += hint; |
|
280 } |
|
281 else |
|
282 { |
|
283 /* key <= a[hint] -- gallop left, until |
|
284 * a[hint - ofs] < key <= a[hint - lastofs] |
|
285 */ |
|
286 const int maxofs = hint + 1; /* &a[0] is lowest */ |
|
287 while (ofs < maxofs) |
|
288 { |
|
289 IFLT (*(a-ofs), key) |
|
290 break; |
|
291 /* key <= a[hint - ofs] */ |
|
292 lastofs = ofs; |
|
293 ofs = (ofs << 1) + 1; |
|
294 if (ofs <= 0) /* int overflow */ |
|
295 ofs = maxofs; |
|
296 } |
|
297 if (ofs > maxofs) |
|
298 ofs = maxofs; |
|
299 /* Translate back to positive offsets relative to &a[0]. */ |
|
300 k = lastofs; |
|
301 lastofs = hint - ofs; |
|
302 ofs = hint - k; |
|
303 } |
|
304 a -= hint; |
|
305 |
|
306 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the |
|
307 * right of lastofs but no farther right than ofs. Do a binary |
|
308 * search, with invariant a[lastofs-1] < key <= a[ofs]. |
|
309 */ |
|
310 ++lastofs; |
|
311 while (lastofs < ofs) |
|
312 { |
|
313 int m = lastofs + ((ofs - lastofs) >> 1); |
|
314 |
|
315 IFLT (a[m], key) |
|
316 lastofs = m+1; /* a[m] < key */ |
|
317 else |
|
318 ofs = m; /* key <= a[m] */ |
|
319 } |
|
320 return ofs; |
|
321 } |
|
322 |
|
323 /* |
|
324 Exactly like gallop_left(), except that if key already exists in a[0:n], |
|
325 finds the position immediately to the right of the rightmost equal value. |
|
326 |
|
327 The return value is the int k in 0..n such that |
|
328 |
|
329 a[k-1] <= key < a[k] |
|
330 |
|
331 or -1 if error. |
|
332 |
|
333 The code duplication is massive, but this is enough different given that |
|
334 we're sticking to "<" comparisons that it's much harder to follow if |
|
335 written as one routine with yet another "left or right?" flag. |
|
336 */ |
|
337 template <class T> |
|
338 int |
|
339 octave_sort<T>::gallop_right(T key, T *a, int n, int hint) |
|
340 { |
|
341 int ofs; |
|
342 int lastofs; |
|
343 int k; |
|
344 |
|
345 a += hint; |
|
346 lastofs = 0; |
|
347 ofs = 1; |
|
348 IFLT (key, *a) |
|
349 { |
|
350 /* key < a[hint] -- gallop left, until |
|
351 * a[hint - ofs] <= key < a[hint - lastofs] |
|
352 */ |
|
353 const int maxofs = hint + 1; /* &a[0] is lowest */ |
|
354 while (ofs < maxofs) |
|
355 { |
|
356 IFLT (key, *(a-ofs)) |
|
357 { |
|
358 lastofs = ofs; |
|
359 ofs = (ofs << 1) + 1; |
|
360 if (ofs <= 0) /* int overflow */ |
|
361 ofs = maxofs; |
|
362 } |
|
363 else /* a[hint - ofs] <= key */ |
|
364 break; |
|
365 } |
|
366 if (ofs > maxofs) |
|
367 ofs = maxofs; |
|
368 /* Translate back to positive offsets relative to &a[0]. */ |
|
369 k = lastofs; |
|
370 lastofs = hint - ofs; |
|
371 ofs = hint - k; |
|
372 } |
|
373 else |
|
374 { |
|
375 /* a[hint] <= key -- gallop right, until |
|
376 * a[hint + lastofs] <= key < a[hint + ofs] |
|
377 */ |
|
378 const int maxofs = n - hint; /* &a[n-1] is highest */ |
|
379 while (ofs < maxofs) |
|
380 { |
|
381 IFLT (key, a[ofs]) |
|
382 break; |
|
383 /* a[hint + ofs] <= key */ |
|
384 lastofs = ofs; |
|
385 ofs = (ofs << 1) + 1; |
|
386 if (ofs <= 0) /* int overflow */ |
|
387 ofs = maxofs; |
|
388 } |
|
389 if (ofs > maxofs) |
|
390 ofs = maxofs; |
|
391 /* Translate back to offsets relative to &a[0]. */ |
|
392 lastofs += hint; |
|
393 ofs += hint; |
|
394 } |
|
395 a -= hint; |
|
396 |
|
397 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the |
|
398 * right of lastofs but no farther right than ofs. Do a binary |
|
399 * search, with invariant a[lastofs-1] <= key < a[ofs]. |
|
400 */ |
|
401 ++lastofs; |
|
402 while (lastofs < ofs) |
|
403 { |
|
404 int m = lastofs + ((ofs - lastofs) >> 1); |
|
405 |
|
406 IFLT (key, a[m]) |
|
407 ofs = m; /* key < a[m] */ |
|
408 else |
|
409 lastofs = m+1; /* a[m] <= key */ |
|
410 } |
|
411 return ofs; |
|
412 } |
|
413 |
|
414 /* Conceptually a MergeState's constructor. */ |
|
415 template <class T> |
|
416 void |
|
417 octave_sort<T>::merge_init(void) |
|
418 { |
|
419 ms.a = NULL; |
|
420 ms.alloced = 0; |
|
421 ms.n = 0; |
|
422 ms.min_gallop = MIN_GALLOP; |
|
423 } |
|
424 |
|
425 /* Free all the temp memory owned by the MergeState. This must be called |
|
426 * when you're done with a MergeState, and may be called before then if |
|
427 * you want to free the temp memory early. |
|
428 */ |
|
429 template <class T> |
|
430 void |
|
431 octave_sort<T>::merge_freemem(void) |
|
432 { |
|
433 if (ms.a) |
|
434 free (ms.a); |
|
435 ms.alloced = 0; |
|
436 ms.a = NULL; |
|
437 } |
|
438 |
|
439 static inline int |
|
440 roundupsize(int n) |
|
441 { |
|
442 unsigned int nbits = 3; |
5760
|
443 unsigned int n2 = static_cast<unsigned int> (n) >> 8; |
4851
|
444 |
|
445 /* Round up: |
|
446 * If n < 256, to a multiple of 8. |
|
447 * If n < 2048, to a multiple of 64. |
|
448 * If n < 16384, to a multiple of 512. |
|
449 * If n < 131072, to a multiple of 4096. |
|
450 * If n < 1048576, to a multiple of 32768. |
|
451 * If n < 8388608, to a multiple of 262144. |
|
452 * If n < 67108864, to a multiple of 2097152. |
|
453 * If n < 536870912, to a multiple of 16777216. |
|
454 * ... |
|
455 * If n < 2**(5+3*i), to a multiple of 2**(3*i). |
|
456 * |
|
457 * This over-allocates proportional to the list size, making room |
|
458 * for additional growth. The over-allocation is mild, but is |
|
459 * enough to give linear-time amortized behavior over a long |
|
460 * sequence of appends() in the presence of a poorly-performing |
|
461 * system realloc() (which is a reality, e.g., across all flavors |
|
462 * of Windows, with Win9x behavior being particularly bad -- and |
|
463 * we've still got address space fragmentation problems on Win9x |
|
464 * even with this scheme, although it requires much longer lists to |
|
465 * provoke them than it used to). |
|
466 */ |
|
467 while (n2) { |
|
468 n2 >>= 3; |
|
469 nbits += 3; |
|
470 } |
|
471 return ((n >> nbits) + 1) << nbits; |
|
472 } |
|
473 |
|
474 /* Ensure enough temp memory for 'need' array slots is available. |
|
475 * Returns 0 on success and -1 if the memory can't be gotten. |
|
476 */ |
|
477 template <class T> |
|
478 int |
|
479 octave_sort<T>::merge_getmem(int need) |
|
480 { |
|
481 if (need <= ms.alloced) |
|
482 return 0; |
|
483 |
|
484 need = roundupsize(need); |
|
485 /* Don't realloc! That can cost cycles to copy the old data, but |
|
486 * we don't care what's in the block. |
|
487 */ |
|
488 merge_freemem( ); |
5760
|
489 ms.a = static_cast <T *> (malloc (need * sizeof (T))); |
4851
|
490 if (ms.a) { |
|
491 ms.alloced = need; |
|
492 return 0; |
|
493 } |
|
494 merge_freemem( ); /* reset to sane state */ |
|
495 return -1; |
|
496 } |
|
497 |
|
498 #define MERGE_GETMEM(NEED) ((NEED) <= ms.alloced ? 0 : \ |
|
499 merge_getmem(NEED)) |
|
500 |
|
501 /* Merge the na elements starting at pa with the nb elements starting at pb |
|
502 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. |
|
503 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the |
|
504 * merge, and should have na <= nb. See listsort.txt for more info. |
|
505 * Return 0 if successful, -1 if error. |
|
506 */ |
|
507 template <class T> |
|
508 int |
|
509 octave_sort<T>::merge_lo(T *pa, int na, T *pb, int nb) |
|
510 { |
|
511 int k; |
|
512 T *dest; |
|
513 int result = -1; /* guilty until proved innocent */ |
|
514 int min_gallop = ms.min_gallop; |
|
515 |
|
516 if (MERGE_GETMEM(na) < 0) |
|
517 return -1; |
|
518 memcpy(ms.a, pa, na * sizeof(T)); |
|
519 dest = pa; |
|
520 pa = ms.a; |
|
521 |
|
522 *dest++ = *pb++; |
|
523 --nb; |
|
524 if (nb == 0) |
|
525 goto Succeed; |
|
526 if (na == 1) |
|
527 goto CopyB; |
|
528 |
|
529 for (;;) { |
|
530 int acount = 0; /* # of times A won in a row */ |
|
531 int bcount = 0; /* # of times B won in a row */ |
|
532 |
|
533 /* Do the straightforward thing until (if ever) one run |
|
534 * appears to win consistently. |
|
535 */ |
|
536 for (;;) { |
|
537 |
|
538 IFLT (*pb, *pa) |
|
539 { |
|
540 *dest++ = *pb++; |
|
541 ++bcount; |
|
542 acount = 0; |
|
543 --nb; |
|
544 if (nb == 0) |
|
545 goto Succeed; |
|
546 if (bcount >= min_gallop) |
|
547 break; |
|
548 } |
|
549 else |
|
550 { |
|
551 *dest++ = *pa++; |
|
552 ++acount; |
|
553 bcount = 0; |
|
554 --na; |
|
555 if (na == 1) |
|
556 goto CopyB; |
|
557 if (acount >= min_gallop) |
|
558 break; |
|
559 } |
|
560 } |
|
561 |
|
562 /* One run is winning so consistently that galloping may |
|
563 * be a huge win. So try that, and continue galloping until |
|
564 * (if ever) neither run appears to be winning consistently |
|
565 * anymore. |
|
566 */ |
|
567 ++min_gallop; |
|
568 do |
|
569 { |
|
570 min_gallop -= min_gallop > 1; |
|
571 ms.min_gallop = min_gallop; |
|
572 k = gallop_right(*pb, pa, na, 0); |
|
573 acount = k; |
|
574 if (k) |
|
575 { |
|
576 if (k < 0) |
|
577 goto Fail; |
|
578 memcpy(dest, pa, k * sizeof(T)); |
|
579 dest += k; |
|
580 pa += k; |
|
581 na -= k; |
|
582 if (na == 1) |
|
583 goto CopyB; |
|
584 /* na==0 is impossible now if the comparison |
|
585 * function is consistent, but we can't assume |
|
586 * that it is. |
|
587 */ |
|
588 if (na == 0) |
|
589 goto Succeed; |
|
590 } |
|
591 *dest++ = *pb++; |
|
592 --nb; |
|
593 if (nb == 0) |
|
594 goto Succeed; |
|
595 |
|
596 k = gallop_left(*pa, pb, nb, 0); |
|
597 bcount = k; |
|
598 if (k) { |
|
599 if (k < 0) |
|
600 goto Fail; |
|
601 memmove(dest, pb, k * sizeof(T)); |
|
602 dest += k; |
|
603 pb += k; |
|
604 nb -= k; |
|
605 if (nb == 0) |
|
606 goto Succeed; |
|
607 } |
|
608 *dest++ = *pa++; |
|
609 --na; |
|
610 if (na == 1) |
|
611 goto CopyB; |
|
612 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); |
|
613 ++min_gallop; /* penalize it for leaving galloping mode */ |
|
614 ms.min_gallop = min_gallop; |
|
615 } |
|
616 Succeed: |
|
617 result = 0; |
|
618 Fail: |
|
619 if (na) |
|
620 memcpy(dest, pa, na * sizeof(T)); |
|
621 return result; |
|
622 CopyB: |
|
623 /* The last element of pa belongs at the end of the merge. */ |
|
624 memmove(dest, pb, nb * sizeof(T)); |
|
625 dest[nb] = *pa; |
|
626 return 0; |
|
627 } |
|
628 |
|
629 /* Merge the na elements starting at pa with the nb elements starting at pb |
|
630 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. |
|
631 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the |
|
632 * merge, and should have na >= nb. See listsort.txt for more info. |
|
633 * Return 0 if successful, -1 if error. |
|
634 */ |
|
635 template <class T> |
|
636 int |
|
637 octave_sort<T>::merge_hi(T *pa, int na, T *pb, int nb) |
|
638 { |
|
639 int k; |
|
640 T *dest; |
|
641 int result = -1; /* guilty until proved innocent */ |
|
642 T *basea; |
|
643 T *baseb; |
|
644 int min_gallop = ms.min_gallop; |
|
645 |
|
646 if (MERGE_GETMEM(nb) < 0) |
|
647 return -1; |
|
648 dest = pb + nb - 1; |
|
649 memcpy(ms.a, pb, nb * sizeof(T)); |
|
650 basea = pa; |
|
651 baseb = ms.a; |
|
652 pb = ms.a + nb - 1; |
|
653 pa += na - 1; |
|
654 |
|
655 *dest-- = *pa--; |
|
656 --na; |
|
657 if (na == 0) |
|
658 goto Succeed; |
|
659 if (nb == 1) |
|
660 goto CopyA; |
|
661 |
|
662 for (;;) |
|
663 { |
|
664 int acount = 0; /* # of times A won in a row */ |
|
665 int bcount = 0; /* # of times B won in a row */ |
|
666 |
|
667 /* Do the straightforward thing until (if ever) one run |
|
668 * appears to win consistently. |
|
669 */ |
|
670 for (;;) |
|
671 { |
|
672 IFLT (*pb, *pa) |
|
673 { |
|
674 *dest-- = *pa--; |
|
675 ++acount; |
|
676 bcount = 0; |
|
677 --na; |
|
678 if (na == 0) |
|
679 goto Succeed; |
|
680 if (acount >= min_gallop) |
|
681 break; |
|
682 } |
|
683 else |
|
684 { |
|
685 *dest-- = *pb--; |
|
686 ++bcount; |
|
687 acount = 0; |
|
688 --nb; |
|
689 if (nb == 1) |
|
690 goto CopyA; |
|
691 if (bcount >= min_gallop) |
|
692 break; |
|
693 } |
|
694 } |
|
695 |
|
696 /* One run is winning so consistently that galloping may |
|
697 * be a huge win. So try that, and continue galloping until |
|
698 * (if ever) neither run appears to be winning consistently |
|
699 * anymore. |
|
700 */ |
|
701 ++min_gallop; |
|
702 do |
|
703 { |
|
704 min_gallop -= min_gallop > 1; |
|
705 ms.min_gallop = min_gallop; |
|
706 k = gallop_right(*pb, basea, na, na-1); |
|
707 if (k < 0) |
|
708 goto Fail; |
|
709 k = na - k; |
|
710 acount = k; |
|
711 if (k) |
|
712 { |
|
713 dest -= k; |
|
714 pa -= k; |
|
715 memmove(dest+1, pa+1, k * sizeof(T )); |
|
716 na -= k; |
|
717 if (na == 0) |
|
718 goto Succeed; |
|
719 } |
|
720 *dest-- = *pb--; |
|
721 --nb; |
|
722 if (nb == 1) |
|
723 goto CopyA; |
|
724 |
|
725 k = gallop_left(*pa, baseb, nb, nb-1); |
|
726 if (k < 0) |
|
727 goto Fail; |
|
728 k = nb - k; |
|
729 bcount = k; |
|
730 if (k) |
|
731 { |
|
732 dest -= k; |
|
733 pb -= k; |
|
734 memcpy(dest+1, pb+1, k * sizeof(T)); |
|
735 nb -= k; |
|
736 if (nb == 1) |
|
737 goto CopyA; |
|
738 /* nb==0 is impossible now if the comparison |
|
739 * function is consistent, but we can't assume |
|
740 * that it is. |
|
741 */ |
|
742 if (nb == 0) |
|
743 goto Succeed; |
|
744 } |
|
745 *dest-- = *pa--; |
|
746 --na; |
|
747 if (na == 0) |
|
748 goto Succeed; |
|
749 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); |
|
750 ++min_gallop; /* penalize it for leaving galloping mode */ |
|
751 ms.min_gallop = min_gallop; |
|
752 } |
|
753 Succeed: |
|
754 result = 0; |
|
755 Fail: |
|
756 if (nb) |
|
757 memcpy(dest-(nb-1), baseb, nb * sizeof(T)); |
|
758 return result; |
|
759 CopyA: |
|
760 /* The first element of pb belongs at the front of the merge. */ |
|
761 dest -= na; |
|
762 pa -= na; |
|
763 memmove(dest+1, pa+1, na * sizeof(T)); |
|
764 *dest = *pb; |
|
765 return 0; |
|
766 } |
|
767 |
|
768 /* Merge the two runs at stack indices i and i+1. |
|
769 * Returns 0 on success, -1 on error. |
|
770 */ |
|
771 template <class T> |
|
772 int |
|
773 octave_sort<T>::merge_at(int i) |
|
774 { |
|
775 T *pa, *pb; |
|
776 int na, nb; |
|
777 int k; |
|
778 |
|
779 pa = ms.pending[i].base; |
|
780 na = ms.pending[i].len; |
|
781 pb = ms.pending[i+1].base; |
|
782 nb = ms.pending[i+1].len; |
|
783 |
|
784 /* Record the length of the combined runs; if i is the 3rd-last |
|
785 * run now, also slide over the last run (which isn't involved |
|
786 * in this merge). The current run i+1 goes away in any case. |
|
787 */ |
|
788 ms.pending[i].len = na + nb; |
|
789 if (i == ms.n - 3) |
|
790 ms.pending[i+1] = ms.pending[i+2]; |
|
791 --ms.n; |
|
792 |
|
793 /* Where does b start in a? Elements in a before that can be |
|
794 * ignored (already in place). |
|
795 */ |
|
796 k = gallop_right(*pb, pa, na, 0); |
|
797 if (k < 0) |
|
798 return -1; |
|
799 pa += k; |
|
800 na -= k; |
|
801 if (na == 0) |
|
802 return 0; |
|
803 |
|
804 /* Where does a end in b? Elements in b after that can be |
|
805 * ignored (already in place). |
|
806 */ |
|
807 nb = gallop_left(pa[na-1], pb, nb, nb-1); |
|
808 if (nb <= 0) |
|
809 return nb; |
|
810 |
|
811 /* Merge what remains of the runs, using a temp array with |
|
812 * min(na, nb) elements. |
|
813 */ |
|
814 if (na <= nb) |
|
815 return merge_lo(pa, na, pb, nb); |
|
816 else |
|
817 return merge_hi(pa, na, pb, nb); |
|
818 } |
|
819 |
|
820 /* Examine the stack of runs waiting to be merged, merging adjacent runs |
|
821 * until the stack invariants are re-established: |
|
822 * |
|
823 * 1. len[-3] > len[-2] + len[-1] |
|
824 * 2. len[-2] > len[-1] |
|
825 * |
|
826 * See listsort.txt for more info. |
|
827 * |
|
828 * Returns 0 on success, -1 on error. |
|
829 */ |
|
830 template <class T> |
|
831 int |
|
832 octave_sort<T>::merge_collapse(void) |
|
833 { |
|
834 struct s_slice *p = ms.pending; |
|
835 |
|
836 while (ms.n > 1) |
|
837 { |
|
838 int n = ms.n - 2; |
|
839 if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) |
|
840 { |
|
841 if (p[n-1].len < p[n+1].len) |
|
842 --n; |
|
843 if (merge_at(n) < 0) |
|
844 return -1; |
|
845 } |
|
846 else if (p[n].len <= p[n+1].len) |
|
847 { |
|
848 if (merge_at(n) < 0) |
|
849 return -1; |
|
850 } |
|
851 else |
|
852 break; |
|
853 } |
|
854 return 0; |
|
855 } |
|
856 |
|
857 /* Regardless of invariants, merge all runs on the stack until only one |
|
858 * remains. This is used at the end of the mergesort. |
|
859 * |
|
860 * Returns 0 on success, -1 on error. |
|
861 */ |
|
862 template <class T> |
|
863 int |
|
864 octave_sort<T>::merge_force_collapse(void) |
|
865 { |
|
866 struct s_slice *p = ms.pending; |
|
867 |
|
868 while (ms.n > 1) |
|
869 { |
|
870 int n = ms.n - 2; |
|
871 if (n > 0 && p[n-1].len < p[n+1].len) |
|
872 --n; |
|
873 if (merge_at(n) < 0) |
|
874 return -1; |
|
875 } |
|
876 return 0; |
|
877 } |
|
878 |
|
879 /* Compute a good value for the minimum run length; natural runs shorter |
|
880 * than this are boosted artificially via binary insertion. |
|
881 * |
|
882 * If n < 64, return n (it's too small to bother with fancy stuff). |
|
883 * Else if n is an exact power of 2, return 32. |
|
884 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but |
|
885 * strictly less than, an exact power of 2. |
|
886 * |
|
887 * See listsort.txt for more info. |
|
888 */ |
|
889 template <class T> |
|
890 int |
|
891 octave_sort<T>::merge_compute_minrun(int n) |
|
892 { |
|
893 int r = 0; /* becomes 1 if any 1 bits are shifted off */ |
|
894 |
|
895 while (n >= 64) { |
|
896 r |= n & 1; |
|
897 n >>= 1; |
|
898 } |
|
899 return n + r; |
|
900 } |
|
901 |
|
902 template <class T> |
|
903 void |
|
904 octave_sort<T>::sort (T *v, int elements) |
|
905 { |
|
906 /* Re-initialize the Mergestate as this might be the second time called */ |
|
907 ms.n = 0; |
|
908 ms.min_gallop = MIN_GALLOP; |
|
909 |
|
910 if (elements > 1) |
|
911 { |
|
912 int nremaining = elements; |
|
913 T *lo = v; |
|
914 T *hi = v + elements; |
|
915 |
|
916 /* March over the array once, left to right, finding natural runs, |
|
917 * and extending short natural runs to minrun elements. |
|
918 */ |
|
919 int minrun = merge_compute_minrun(nremaining); |
|
920 do |
|
921 { |
|
922 int descending; |
|
923 int n; |
|
924 |
|
925 /* Identify next run. */ |
|
926 n = count_run(lo, hi, &descending); |
|
927 if (n < 0) |
|
928 goto fail; |
|
929 if (descending) |
|
930 reverse_slice(lo, lo + n); |
|
931 /* If short, extend to min(minrun, nremaining). */ |
|
932 if (n < minrun) |
|
933 { |
|
934 const int force = nremaining <= minrun ? nremaining : minrun; |
|
935 binarysort(lo, lo + force, lo + n); |
|
936 n = force; |
|
937 } |
|
938 /* Push run onto pending-runs stack, and maybe merge. */ |
|
939 assert(ms.n < MAX_MERGE_PENDING); |
|
940 ms.pending[ms.n].base = lo; |
|
941 ms.pending[ms.n].len = n; |
|
942 ++ms.n; |
|
943 if (merge_collapse( ) < 0) |
|
944 goto fail; |
|
945 /* Advance to find next run. */ |
|
946 lo += n; |
|
947 nremaining -= n; |
|
948 } while (nremaining); |
|
949 |
|
950 merge_force_collapse( ); |
|
951 } |
|
952 |
|
953 fail: |
|
954 return; |
|
955 } |
|
956 |
|
957 /* |
|
958 ;;; Local Variables: *** |
|
959 ;;; mode: C++ *** |
|
960 ;;; End: *** |
|
961 */ |