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