Mercurial > hg > octave-nkf
annotate liboctave/oct-sort.cc @ 8816:a4a8f871be81
fix missing init in octave_sort<T>::sortrows
| author | Jaroslav Hajek <highegg@gmail.com> |
|---|---|
| date | Thu, 19 Feb 2009 17:04:28 +0100 |
| parents | de16ebeef93d |
| children | 89b95972e178 |
| rev | line source |
|---|---|
| 4851 | 1 /* |
| 7017 | 2 Copyright (C) 2003, 2004, 2005, 2006, 2007 David Bateman |
| 8700 | 3 Copyright (C) 2008, 2009 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 | |
|
8206
0168d22e6bba
fix sorting of non-POD objects
Jaroslav Hajek <highegg@gmail.com>
parents:
7929
diff
changeset
|
31 * replaced usages of malloc, free, memcpy and memmove by standard C++ |
|
8678
e2b4c19c455c
redo changeset 4238f2600a17 with fixes to sorting
Jaroslav Hajek <highegg@gmail.com>
parents:
8206
diff
changeset
|
32 new [], delete [] and std::copy and std::copy_backward. Note that replacing |
|
e2b4c19c455c
redo changeset 4238f2600a17 with fixes to sorting
Jaroslav Hajek <highegg@gmail.com>
parents:
8206
diff
changeset
|
33 memmove by std::copy is possible if the destination starts before the source. |
|
e2b4c19c455c
redo changeset 4238f2600a17 with fixes to sorting
Jaroslav Hajek <highegg@gmail.com>
parents:
8206
diff
changeset
|
34 If not, std::copy_backward needs to be used. |
|
8206
0168d22e6bba
fix sorting of non-POD objects
Jaroslav Hajek <highegg@gmail.com>
parents:
7929
diff
changeset
|
35 |
| 8700 | 36 * templatize comparison operator in most methods, provide possible dispatch |
| 37 | |
| 38 * duplicate methods to avoid by-the-way indexed sorting | |
| 39 | |
|
8206
0168d22e6bba
fix sorting of non-POD objects
Jaroslav Hajek <highegg@gmail.com>
parents:
7929
diff
changeset
|
40 |
| 4851 | 41 The Python license is |
| 42 | |
| 43 PSF LICENSE AGREEMENT FOR PYTHON 2.3 | |
| 44 -------------------------------------- | |
| 45 | |
| 46 1. This LICENSE AGREEMENT is between the Python Software Foundation | |
| 47 ("PSF"), and the Individual or Organization ("Licensee") accessing and | |
| 48 otherwise using Python 2.3 software in source or binary form and its | |
| 49 associated documentation. | |
| 50 | |
| 51 2. Subject to the terms and conditions of this License Agreement, PSF | |
| 52 hereby grants Licensee a nonexclusive, royalty-free, world-wide | |
| 53 license to reproduce, analyze, test, perform and/or display publicly, | |
| 54 prepare derivative works, distribute, and otherwise use Python 2.3 | |
| 55 alone or in any derivative version, provided, however, that PSF's | |
| 56 License Agreement and PSF's notice of copyright, i.e., "Copyright (c) | |
| 57 2001, 2002, 2003 Python Software Foundation; All Rights Reserved" are | |
| 58 retained in Python 2.3 alone or in any derivative version prepared by | |
| 59 Licensee. | |
| 60 | |
| 61 3. In the event Licensee prepares a derivative work that is based on | |
| 62 or incorporates Python 2.3 or any part thereof, and wants to make | |
| 63 the derivative work available to others as provided herein, then | |
| 64 Licensee hereby agrees to include in any such work a brief summary of | |
| 65 the changes made to Python 2.3. | |
| 66 | |
| 67 4. PSF is making Python 2.3 available to Licensee on an "AS IS" | |
| 68 basis. PSF MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR | |
| 69 IMPLIED. BY WAY OF EXAMPLE, BUT NOT LIMITATION, PSF MAKES NO AND | |
| 70 DISCLAIMS ANY REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR FITNESS | |
| 71 FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF PYTHON 2.3 WILL NOT | |
| 72 INFRINGE ANY THIRD PARTY RIGHTS. | |
| 73 | |
| 74 5. PSF SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PYTHON | |
| 75 2.3 FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR LOSS AS | |
| 76 A RESULT OF MODIFYING, DISTRIBUTING, OR OTHERWISE USING PYTHON 2.3, | |
| 77 OR ANY DERIVATIVE THEREOF, EVEN IF ADVISED OF THE POSSIBILITY THEREOF. | |
| 78 | |
| 79 6. This License Agreement will automatically terminate upon a material | |
| 80 breach of its terms and conditions. | |
| 81 | |
| 82 7. Nothing in this License Agreement shall be deemed to create any | |
| 83 relationship of agency, partnership, or joint venture between PSF and | |
| 84 Licensee. This License Agreement does not grant permission to use PSF | |
| 85 trademarks or trade name in a trademark sense to endorse or promote | |
| 86 products or services of Licensee, or any third party. | |
| 87 | |
| 88 8. By copying, installing or otherwise using Python 2.3, Licensee | |
| 89 agrees to be bound by the terms and conditions of this License | |
| 90 Agreement. | |
| 91 */ | |
| 92 | |
| 93 #ifdef HAVE_CONFIG_H | |
| 94 #include <config.h> | |
| 95 #endif | |
| 96 | |
| 5883 | 97 #include <cassert> |
|
8206
0168d22e6bba
fix sorting of non-POD objects
Jaroslav Hajek <highegg@gmail.com>
parents:
7929
diff
changeset
|
98 #include <algorithm> |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
99 #include <functional> |
| 7480 | 100 #include <cstring> |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
101 #include <stack> |
| 5883 | 102 |
| 4851 | 103 #include "lo-mappers.h" |
| 104 #include "quit.h" | |
| 105 #include "oct-sort.h" | |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
106 #include "oct-locbuf.h" |
| 4851 | 107 |
| 108 template <class T> | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
109 octave_sort<T>::octave_sort (void) : |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
110 compare (ascending_compare), ms (0) |
| 4851 | 111 { |
| 112 } | |
| 113 | |
| 114 template <class T> | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
115 octave_sort<T>::octave_sort (compare_fcn_type comp) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
116 : compare (comp), ms (0) |
| 4851 | 117 { |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
118 } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
119 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
120 template <class T> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
121 octave_sort<T>::~octave_sort () |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
122 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
123 merge_freemem (); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
124 delete ms; |
| 4851 | 125 } |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
126 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
127 template <class T> |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
128 void |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
129 octave_sort<T>::set_compare (sortmode mode) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
130 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
131 if (mode == ASCENDING) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
132 compare = ascending_compare; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
133 else if (mode == DESCENDING) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
134 compare = descending_compare; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
135 else |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
136 compare = 0; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
137 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
138 |
| 4851 | 139 template <class T> |
| 8700 | 140 template <class Comp> |
| 4851 | 141 void |
| 8700 | 142 octave_sort<T>::binarysort (T *data, octave_idx_type nel, |
| 143 octave_idx_type start, Comp comp) | |
| 4851 | 144 { |
| 8700 | 145 if (start == 0) |
| 4851 | 146 ++start; |
| 147 | |
| 8700 | 148 for (; start < nel; ++start) |
| 4851 | 149 { |
| 150 /* set l to where *start belongs */ | |
| 8700 | 151 octave_idx_type l = 0, r = start; |
| 152 T pivot = data[start]; | |
| 4851 | 153 /* Invariants: |
| 154 * pivot >= all in [lo, l). | |
| 155 * pivot < all in [r, start). | |
| 156 * The second is vacuously true at the start. | |
| 157 */ | |
| 158 do | |
| 159 { | |
| 8700 | 160 octave_idx_type p = l + ((r - l) >> 1); |
| 161 if (comp (pivot, data[p])) | |
| 4851 | 162 r = p; |
| 163 else | |
| 164 l = p+1; | |
| 165 } | |
| 166 while (l < r); | |
| 167 /* The invariants still hold, so pivot >= all in [lo, l) and | |
| 168 pivot < all in [l, start), so pivot belongs at l. Note | |
| 169 that if there are elements equal to pivot, l points to the | |
| 170 first slot after them -- that's why this sort is stable. | |
| 171 Slide over to make room. | |
| 172 Caution: using memmove is much slower under MSVC 5; | |
| 173 we're not usually moving many slots. */ | |
| 8700 | 174 // NOTE: using swap and going upwards appears to be faster. |
| 175 for (octave_idx_type p = l; p < start; p++) | |
| 176 std::swap (pivot, data[p]); | |
| 177 data[start] = pivot; | |
| 178 } | |
| 179 | |
| 180 return; | |
| 181 } | |
| 182 | |
| 183 template <class T> | |
| 184 template <class Comp> | |
| 185 void | |
| 186 octave_sort<T>::binarysort (T *data, octave_idx_type *idx, octave_idx_type nel, | |
| 187 octave_idx_type start, Comp comp) | |
| 188 { | |
| 189 if (start == 0) | |
| 190 ++start; | |
| 191 | |
| 192 for (; start < nel; ++start) | |
| 193 { | |
| 194 /* set l to where *start belongs */ | |
| 195 octave_idx_type l = 0, r = start; | |
| 196 T pivot = data[start]; | |
| 197 /* Invariants: | |
| 198 * pivot >= all in [lo, l). | |
| 199 * pivot < all in [r, start). | |
| 200 * The second is vacuously true at the start. | |
| 201 */ | |
| 202 do | |
| 203 { | |
| 204 octave_idx_type p = l + ((r - l) >> 1); | |
| 205 if (comp (pivot, data[p])) | |
| 206 r = p; | |
| 207 else | |
| 208 l = p+1; | |
| 209 } | |
| 210 while (l < r); | |
| 211 /* The invariants still hold, so pivot >= all in [lo, l) and | |
| 212 pivot < all in [l, start), so pivot belongs at l. Note | |
| 213 that if there are elements equal to pivot, l points to the | |
| 214 first slot after them -- that's why this sort is stable. | |
| 215 Slide over to make room. | |
| 216 Caution: using memmove is much slower under MSVC 5; | |
| 217 we're not usually moving many slots. */ | |
| 218 // NOTE: using swap and going upwards appears to be faster. | |
| 219 for (octave_idx_type p = l; p < start; p++) | |
| 220 std::swap (pivot, data[p]); | |
| 221 data[start] = pivot; | |
| 222 octave_idx_type ipivot = idx[start]; | |
| 223 for (octave_idx_type p = l; p < start; p++) | |
| 224 std::swap (ipivot, idx[p]); | |
| 225 idx[start] = ipivot; | |
| 4851 | 226 } |
| 227 | |
| 228 return; | |
| 229 } | |
| 230 | |
| 231 /* | |
| 232 Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi | |
| 233 is required on entry. "A run" is the longest ascending sequence, with | |
| 234 | |
| 235 lo[0] <= lo[1] <= lo[2] <= ... | |
| 236 | |
| 237 or the longest descending sequence, with | |
| 238 | |
| 239 lo[0] > lo[1] > lo[2] > ... | |
| 240 | |
| 7929 | 241 DESCENDING is set to false in the former case, or to true in the latter. |
| 4851 | 242 For its intended use in a stable mergesort, the strictness of the defn of |
| 243 "descending" is needed so that the caller can safely reverse a descending | |
| 244 sequence without violating stability (strict > ensures there are no equal | |
| 245 elements to get out of order). | |
| 246 | |
| 247 Returns -1 in case of error. | |
| 248 */ | |
| 249 template <class T> | |
| 8700 | 250 template <class Comp> |
| 7433 | 251 octave_idx_type |
| 8700 | 252 octave_sort<T>::count_run (T *lo, octave_idx_type nel, bool& descending, Comp comp) |
| 4851 | 253 { |
| 7433 | 254 octave_idx_type n; |
| 8700 | 255 T *hi = lo + nel; |
| 4851 | 256 |
| 7929 | 257 descending = false; |
| 4851 | 258 ++lo; |
| 259 if (lo == hi) | |
| 260 return 1; | |
| 261 | |
| 262 n = 2; | |
| 263 | |
| 8700 | 264 if (comp (*lo, *(lo-1))) |
| 4851 | 265 { |
| 7929 | 266 descending = true; |
| 4851 | 267 for (lo = lo+1; lo < hi; ++lo, ++n) |
| 268 { | |
| 8700 | 269 if (comp (*lo, *(lo-1))) |
| 4851 | 270 ; |
| 271 else | |
| 272 break; | |
| 273 } | |
| 274 } | |
| 275 else | |
| 276 { | |
| 277 for (lo = lo+1; lo < hi; ++lo, ++n) | |
| 278 { | |
| 8700 | 279 if (comp (*lo, *(lo-1))) |
| 4851 | 280 break; |
| 281 } | |
| 282 } | |
| 283 | |
| 284 return n; | |
| 285 } | |
| 286 | |
| 287 /* | |
| 288 Locate the proper position of key in a sorted vector; if the vector contains | |
| 289 an element equal to key, return the position immediately to the left of | |
| 290 the leftmost equal element. [gallop_right() does the same except returns | |
| 291 the position to the right of the rightmost equal element (if any).] | |
| 292 | |
| 293 "a" is a sorted vector with n elements, starting at a[0]. n must be > 0. | |
| 294 | |
| 295 "hint" is an index at which to begin the search, 0 <= hint < n. The closer | |
| 296 hint is to the final result, the faster this runs. | |
| 297 | |
| 298 The return value is the int k in 0..n such that | |
| 299 | |
| 300 a[k-1] < key <= a[k] | |
| 301 | |
| 302 pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW, | |
| 303 key belongs at index k; or, IOW, the first k elements of a should precede | |
| 304 key, and the last n-k should follow key. | |
| 305 | |
| 306 Returns -1 on error. See listsort.txt for info on the method. | |
| 307 */ | |
| 308 template <class T> | |
| 8700 | 309 template <class Comp> |
| 7433 | 310 octave_idx_type |
| 8700 | 311 octave_sort<T>::gallop_left (T key, T *a, octave_idx_type n, octave_idx_type hint, |
| 312 Comp comp) | |
| 4851 | 313 { |
| 7433 | 314 octave_idx_type ofs; |
| 315 octave_idx_type lastofs; | |
| 316 octave_idx_type k; | |
| 4851 | 317 |
| 318 a += hint; | |
| 319 lastofs = 0; | |
| 320 ofs = 1; | |
| 8700 | 321 if (comp (*a, key)) |
| 4851 | 322 { |
| 323 /* a[hint] < key -- gallop right, until | |
| 324 * a[hint + lastofs] < key <= a[hint + ofs] | |
| 325 */ | |
| 7433 | 326 const octave_idx_type maxofs = n - hint; /* &a[n-1] is highest */ |
| 4851 | 327 while (ofs < maxofs) |
| 328 { | |
| 8700 | 329 if (comp (a[ofs], key)) |
| 4851 | 330 { |
| 331 lastofs = ofs; | |
| 332 ofs = (ofs << 1) + 1; | |
| 333 if (ofs <= 0) /* int overflow */ | |
| 334 ofs = maxofs; | |
| 335 } | |
| 336 else /* key <= a[hint + ofs] */ | |
| 337 break; | |
| 338 } | |
| 339 if (ofs > maxofs) | |
| 340 ofs = maxofs; | |
| 341 /* Translate back to offsets relative to &a[0]. */ | |
| 342 lastofs += hint; | |
| 343 ofs += hint; | |
| 344 } | |
| 345 else | |
| 346 { | |
| 347 /* key <= a[hint] -- gallop left, until | |
| 348 * a[hint - ofs] < key <= a[hint - lastofs] | |
| 349 */ | |
| 7433 | 350 const octave_idx_type maxofs = hint + 1; /* &a[0] is lowest */ |
| 4851 | 351 while (ofs < maxofs) |
| 352 { | |
| 8700 | 353 if (comp (*(a-ofs), key)) |
| 4851 | 354 break; |
| 355 /* key <= a[hint - ofs] */ | |
| 356 lastofs = ofs; | |
| 357 ofs = (ofs << 1) + 1; | |
| 358 if (ofs <= 0) /* int overflow */ | |
| 359 ofs = maxofs; | |
| 360 } | |
| 361 if (ofs > maxofs) | |
| 362 ofs = maxofs; | |
| 363 /* Translate back to positive offsets relative to &a[0]. */ | |
| 364 k = lastofs; | |
| 365 lastofs = hint - ofs; | |
| 366 ofs = hint - k; | |
| 367 } | |
| 368 a -= hint; | |
| 369 | |
| 370 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the | |
| 371 * right of lastofs but no farther right than ofs. Do a binary | |
| 372 * search, with invariant a[lastofs-1] < key <= a[ofs]. | |
| 373 */ | |
| 374 ++lastofs; | |
| 375 while (lastofs < ofs) | |
| 376 { | |
| 7433 | 377 octave_idx_type m = lastofs + ((ofs - lastofs) >> 1); |
| 4851 | 378 |
| 8700 | 379 if (comp (a[m], key)) |
| 4851 | 380 lastofs = m+1; /* a[m] < key */ |
| 381 else | |
| 382 ofs = m; /* key <= a[m] */ | |
| 383 } | |
| 7234 | 384 |
| 4851 | 385 return ofs; |
| 386 } | |
| 387 | |
| 388 /* | |
| 389 Exactly like gallop_left(), except that if key already exists in a[0:n], | |
| 390 finds the position immediately to the right of the rightmost equal value. | |
| 391 | |
| 392 The return value is the int k in 0..n such that | |
| 393 | |
| 394 a[k-1] <= key < a[k] | |
| 395 | |
| 396 or -1 if error. | |
| 397 | |
| 398 The code duplication is massive, but this is enough different given that | |
| 399 we're sticking to "<" comparisons that it's much harder to follow if | |
| 400 written as one routine with yet another "left or right?" flag. | |
| 401 */ | |
| 402 template <class T> | |
| 8700 | 403 template <class Comp> |
| 7433 | 404 octave_idx_type |
| 8700 | 405 octave_sort<T>::gallop_right (T key, T *a, octave_idx_type n, octave_idx_type hint, |
| 406 Comp comp) | |
| 4851 | 407 { |
| 7433 | 408 octave_idx_type ofs; |
| 409 octave_idx_type lastofs; | |
| 410 octave_idx_type k; | |
| 4851 | 411 |
| 412 a += hint; | |
| 413 lastofs = 0; | |
| 414 ofs = 1; | |
| 8700 | 415 if (comp (key, *a)) |
| 4851 | 416 { |
| 417 /* key < a[hint] -- gallop left, until | |
| 418 * a[hint - ofs] <= key < a[hint - lastofs] | |
| 419 */ | |
| 7433 | 420 const octave_idx_type maxofs = hint + 1; /* &a[0] is lowest */ |
| 4851 | 421 while (ofs < maxofs) |
| 422 { | |
| 8700 | 423 if (comp (key, *(a-ofs))) |
| 4851 | 424 { |
| 425 lastofs = ofs; | |
| 426 ofs = (ofs << 1) + 1; | |
| 427 if (ofs <= 0) /* int overflow */ | |
| 428 ofs = maxofs; | |
| 429 } | |
| 430 else /* a[hint - ofs] <= key */ | |
| 431 break; | |
| 432 } | |
| 433 if (ofs > maxofs) | |
| 434 ofs = maxofs; | |
| 435 /* Translate back to positive offsets relative to &a[0]. */ | |
| 436 k = lastofs; | |
| 437 lastofs = hint - ofs; | |
| 438 ofs = hint - k; | |
| 439 } | |
| 440 else | |
| 441 { | |
| 442 /* a[hint] <= key -- gallop right, until | |
| 443 * a[hint + lastofs] <= key < a[hint + ofs] | |
| 444 */ | |
| 7433 | 445 const octave_idx_type maxofs = n - hint; /* &a[n-1] is highest */ |
| 4851 | 446 while (ofs < maxofs) |
| 447 { | |
| 8700 | 448 if (comp (key, a[ofs])) |
| 4851 | 449 break; |
| 450 /* a[hint + ofs] <= key */ | |
| 451 lastofs = ofs; | |
| 452 ofs = (ofs << 1) + 1; | |
| 453 if (ofs <= 0) /* int overflow */ | |
| 454 ofs = maxofs; | |
| 455 } | |
| 456 if (ofs > maxofs) | |
| 457 ofs = maxofs; | |
| 458 /* Translate back to offsets relative to &a[0]. */ | |
| 459 lastofs += hint; | |
| 460 ofs += hint; | |
| 461 } | |
| 462 a -= hint; | |
| 463 | |
| 464 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the | |
| 465 * right of lastofs but no farther right than ofs. Do a binary | |
| 466 * search, with invariant a[lastofs-1] <= key < a[ofs]. | |
| 467 */ | |
| 468 ++lastofs; | |
| 469 while (lastofs < ofs) | |
| 470 { | |
| 7433 | 471 octave_idx_type m = lastofs + ((ofs - lastofs) >> 1); |
| 4851 | 472 |
| 8700 | 473 if (comp (key, a[m])) |
| 4851 | 474 ofs = m; /* key < a[m] */ |
| 475 else | |
| 476 lastofs = m+1; /* a[m] <= key */ | |
| 477 } | |
| 7234 | 478 |
| 4851 | 479 return ofs; |
| 480 } | |
| 481 | |
| 482 /* Conceptually a MergeState's constructor. */ | |
| 483 template <class T> | |
| 484 void | |
| 7234 | 485 octave_sort<T>::merge_init (void) |
| 4851 | 486 { |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
487 if (! ms) ms = new MergeState; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
488 ms->a = 0; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
489 ms->ia = 0; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
490 ms->alloced = 0; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
491 ms->n = 0; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
492 ms->min_gallop = MIN_GALLOP; |
| 4851 | 493 } |
| 494 | |
| 495 /* Free all the temp memory owned by the MergeState. This must be called | |
| 496 * when you're done with a MergeState, and may be called before then if | |
| 497 * you want to free the temp memory early. | |
| 498 */ | |
| 499 template <class T> | |
| 500 void | |
| 7234 | 501 octave_sort<T>::merge_freemem (void) |
| 4851 | 502 { |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
503 if (ms) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
504 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
505 delete [] ms->a; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
506 delete [] ms->ia; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
507 ms->alloced = 0; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
508 ms->a = 0; |
|
8816
a4a8f871be81
fix missing init in octave_sort<T>::sortrows
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
509 ms->ia = 0; |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
510 } |
| 4851 | 511 } |
| 512 | |
| 7433 | 513 static inline octave_idx_type |
| 514 roundupsize (octave_idx_type n) | |
| 4851 | 515 { |
| 516 unsigned int nbits = 3; | |
| 7433 | 517 octave_idx_type n2 = static_cast<octave_idx_type> (n) >> 8; |
| 4851 | 518 |
| 519 /* Round up: | |
| 520 * If n < 256, to a multiple of 8. | |
| 521 * If n < 2048, to a multiple of 64. | |
| 522 * If n < 16384, to a multiple of 512. | |
| 523 * If n < 131072, to a multiple of 4096. | |
| 524 * If n < 1048576, to a multiple of 32768. | |
| 525 * If n < 8388608, to a multiple of 262144. | |
| 526 * If n < 67108864, to a multiple of 2097152. | |
| 527 * If n < 536870912, to a multiple of 16777216. | |
| 528 * ... | |
| 529 * If n < 2**(5+3*i), to a multiple of 2**(3*i). | |
| 530 * | |
| 531 * This over-allocates proportional to the list size, making room | |
| 532 * for additional growth. The over-allocation is mild, but is | |
| 533 * enough to give linear-time amortized behavior over a long | |
| 534 * sequence of appends() in the presence of a poorly-performing | |
| 535 * system realloc() (which is a reality, e.g., across all flavors | |
| 536 * of Windows, with Win9x behavior being particularly bad -- and | |
| 537 * we've still got address space fragmentation problems on Win9x | |
| 538 * even with this scheme, although it requires much longer lists to | |
| 539 * provoke them than it used to). | |
| 540 */ | |
| 7234 | 541 while (n2) |
| 542 { | |
| 543 n2 >>= 3; | |
| 544 nbits += 3; | |
| 545 } | |
| 546 | |
| 4851 | 547 return ((n >> nbits) + 1) << nbits; |
| 548 } | |
| 549 | |
| 550 /* Ensure enough temp memory for 'need' array slots is available. | |
| 551 * Returns 0 on success and -1 if the memory can't be gotten. | |
| 552 */ | |
| 553 template <class T> | |
| 554 int | |
| 7433 | 555 octave_sort<T>::merge_getmem (octave_idx_type need) |
| 4851 | 556 { |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
557 if (need <= ms->alloced) |
| 4851 | 558 return 0; |
| 559 | |
| 7234 | 560 need = roundupsize (need); |
| 4851 | 561 /* Don't realloc! That can cost cycles to copy the old data, but |
| 562 * we don't care what's in the block. | |
| 563 */ | |
| 7234 | 564 merge_freemem (); |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
565 ms->a = new T[need]; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
566 if (ms->a) |
| 7234 | 567 { |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
568 ms->alloced = need; |
| 7234 | 569 return 0; |
| 570 } | |
| 571 merge_freemem (); /* reset to sane state */ | |
| 572 | |
| 4851 | 573 return -1; |
| 574 } | |
| 575 | |
| 8700 | 576 template <class T> |
| 577 int | |
| 578 octave_sort<T>::merge_getmemi (octave_idx_type need) | |
| 579 { | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
580 if (need <= ms->alloced && ms->a && ms->ia) |
| 8700 | 581 return 0; |
| 582 | |
| 583 need = roundupsize (need); | |
| 584 /* Don't realloc! That can cost cycles to copy the old data, but | |
| 585 * we don't care what's in the block. | |
| 586 */ | |
| 587 merge_freemem (); | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
588 ms->a = new T[need]; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
589 ms->ia = new octave_idx_type[need]; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
590 if (ms->a && ms->ia) |
| 8700 | 591 { |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
592 ms->alloced = need; |
| 8700 | 593 return 0; |
| 594 } | |
| 595 merge_freemem (); /* reset to sane state */ | |
| 596 | |
| 597 return -1; | |
| 598 } | |
| 4851 | 599 |
| 600 /* Merge the na elements starting at pa with the nb elements starting at pb | |
| 601 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. | |
| 602 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the | |
| 603 * merge, and should have na <= nb. See listsort.txt for more info. | |
| 604 * Return 0 if successful, -1 if error. | |
| 605 */ | |
| 606 template <class T> | |
| 8700 | 607 template <class Comp> |
| 4851 | 608 int |
| 8700 | 609 octave_sort<T>::merge_lo (T *pa, octave_idx_type na, |
| 610 T *pb, octave_idx_type nb, | |
| 611 Comp comp) | |
| 4851 | 612 { |
| 7433 | 613 octave_idx_type k; |
| 4851 | 614 T *dest; |
| 615 int result = -1; /* guilty until proved innocent */ | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
616 octave_idx_type min_gallop = ms->min_gallop; |
| 4851 | 617 |
| 8700 | 618 if (merge_getmem (na) < 0) |
| 4851 | 619 return -1; |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
620 std::copy (pa, pa + na, ms->a); |
| 4851 | 621 dest = pa; |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
622 pa = ms->a; |
| 4851 | 623 |
| 624 *dest++ = *pb++; | |
| 625 --nb; | |
| 626 if (nb == 0) | |
| 627 goto Succeed; | |
| 628 if (na == 1) | |
| 629 goto CopyB; | |
| 630 | |
| 7234 | 631 for (;;) |
| 632 { | |
| 7433 | 633 octave_idx_type acount = 0; /* # of times A won in a row */ |
| 634 octave_idx_type bcount = 0; /* # of times B won in a row */ | |
| 7234 | 635 |
| 636 /* Do the straightforward thing until (if ever) one run | |
| 637 * appears to win consistently. | |
| 638 */ | |
| 639 for (;;) | |
| 640 { | |
| 4851 | 641 |
| 8700 | 642 // FIXME: these loops are candidates for further optimizations. |
| 643 // Rather than testing everything in each cycle, it may be more | |
| 644 // efficient to do it in hunks. | |
| 645 if (comp (*pb, *pa)) | |
| 7234 | 646 { |
| 647 *dest++ = *pb++; | |
| 648 ++bcount; | |
| 649 acount = 0; | |
| 650 --nb; | |
| 651 if (nb == 0) | |
| 652 goto Succeed; | |
| 653 if (bcount >= min_gallop) | |
| 654 break; | |
| 655 } | |
| 656 else | |
| 657 { | |
| 658 *dest++ = *pa++; | |
| 659 ++acount; | |
| 660 bcount = 0; | |
| 661 --na; | |
| 662 if (na == 1) | |
| 663 goto CopyB; | |
| 664 if (acount >= min_gallop) | |
| 665 break; | |
| 666 } | |
| 667 } | |
| 4851 | 668 |
| 7234 | 669 /* One run is winning so consistently that galloping may |
| 670 * be a huge win. So try that, and continue galloping until | |
| 671 * (if ever) neither run appears to be winning consistently | |
| 672 * anymore. | |
| 673 */ | |
| 674 ++min_gallop; | |
| 675 do | |
| 4851 | 676 { |
| 7234 | 677 min_gallop -= min_gallop > 1; |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
678 ms->min_gallop = min_gallop; |
| 8700 | 679 k = gallop_right (*pb, pa, na, 0, comp); |
| 7234 | 680 acount = k; |
| 681 if (k) | |
| 682 { | |
| 683 if (k < 0) | |
| 684 goto Fail; | |
| 8700 | 685 dest = std::copy (pa, pa + k, dest); |
| 7234 | 686 pa += k; |
| 687 na -= k; | |
| 688 if (na == 1) | |
| 689 goto CopyB; | |
| 690 /* na==0 is impossible now if the comparison | |
| 691 * function is consistent, but we can't assume | |
| 692 * that it is. | |
| 693 */ | |
| 694 if (na == 0) | |
| 695 goto Succeed; | |
| 696 } | |
| 4851 | 697 *dest++ = *pb++; |
| 698 --nb; | |
| 699 if (nb == 0) | |
| 700 goto Succeed; | |
| 7234 | 701 |
| 8700 | 702 k = gallop_left (*pa, pb, nb, 0, comp); |
| 7234 | 703 bcount = k; |
| 704 if (k) | |
| 705 { | |
| 706 if (k < 0) | |
| 707 goto Fail; | |
| 8700 | 708 dest = std::copy (pb, pb + k, dest); |
| 7234 | 709 pb += k; |
| 710 nb -= k; | |
| 711 if (nb == 0) | |
| 712 goto Succeed; | |
| 713 } | |
| 4851 | 714 *dest++ = *pa++; |
| 715 --na; | |
| 716 if (na == 1) | |
| 717 goto CopyB; | |
| 718 } | |
| 7234 | 719 while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); |
| 720 | |
| 721 ++min_gallop; /* penalize it for leaving galloping mode */ | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
722 ms->min_gallop = min_gallop; |
| 4851 | 723 } |
| 724 | |
| 725 Succeed: | |
| 726 result = 0; | |
| 7234 | 727 |
| 4851 | 728 Fail: |
| 729 if (na) | |
|
8206
0168d22e6bba
fix sorting of non-POD objects
Jaroslav Hajek <highegg@gmail.com>
parents:
7929
diff
changeset
|
730 std::copy (pa, pa + na, dest); |
| 4851 | 731 return result; |
| 7234 | 732 |
| 4851 | 733 CopyB: |
| 734 /* The last element of pa belongs at the end of the merge. */ | |
|
8206
0168d22e6bba
fix sorting of non-POD objects
Jaroslav Hajek <highegg@gmail.com>
parents:
7929
diff
changeset
|
735 std::copy (pb, pb + nb, dest); |
| 4851 | 736 dest[nb] = *pa; |
| 7234 | 737 |
| 4851 | 738 return 0; |
| 739 } | |
| 740 | |
| 8700 | 741 template <class T> |
| 742 template <class Comp> | |
| 743 int | |
| 744 octave_sort<T>::merge_lo (T *pa, octave_idx_type *ipa, octave_idx_type na, | |
| 745 T *pb, octave_idx_type *ipb, octave_idx_type nb, | |
| 746 Comp comp) | |
| 747 { | |
| 748 octave_idx_type k; | |
| 749 T *dest; | |
| 750 octave_idx_type *idest; | |
| 751 int result = -1; /* guilty until proved innocent */ | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
752 octave_idx_type min_gallop = ms->min_gallop; |
| 8700 | 753 |
| 754 if (merge_getmemi (na) < 0) | |
| 755 return -1; | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
756 std::copy (pa, pa + na, ms->a); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
757 std::copy (ipa, ipa + na, ms->ia); |
| 8700 | 758 dest = pa; idest = ipa; |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
759 pa = ms->a; ipa = ms->ia; |
| 8700 | 760 |
| 761 *dest++ = *pb++; *idest++ = *ipb++; | |
| 762 --nb; | |
| 763 if (nb == 0) | |
| 764 goto Succeed; | |
| 765 if (na == 1) | |
| 766 goto CopyB; | |
| 767 | |
| 768 for (;;) | |
| 769 { | |
| 770 octave_idx_type acount = 0; /* # of times A won in a row */ | |
| 771 octave_idx_type bcount = 0; /* # of times B won in a row */ | |
| 772 | |
| 773 /* Do the straightforward thing until (if ever) one run | |
| 774 * appears to win consistently. | |
| 775 */ | |
| 776 for (;;) | |
| 777 { | |
| 778 | |
| 779 if (comp (*pb, *pa)) | |
| 780 { | |
| 781 *dest++ = *pb++; *idest++ = *ipb++; | |
| 782 ++bcount; | |
| 783 acount = 0; | |
| 784 --nb; | |
| 785 if (nb == 0) | |
| 786 goto Succeed; | |
| 787 if (bcount >= min_gallop) | |
| 788 break; | |
| 789 } | |
| 790 else | |
| 791 { | |
| 792 *dest++ = *pa++; *idest++ = *ipa++; | |
| 793 ++acount; | |
| 794 bcount = 0; | |
| 795 --na; | |
| 796 if (na == 1) | |
| 797 goto CopyB; | |
| 798 if (acount >= min_gallop) | |
| 799 break; | |
| 800 } | |
| 801 } | |
| 802 | |
| 803 /* One run is winning so consistently that galloping may | |
| 804 * be a huge win. So try that, and continue galloping until | |
| 805 * (if ever) neither run appears to be winning consistently | |
| 806 * anymore. | |
| 807 */ | |
| 808 ++min_gallop; | |
| 809 do | |
| 810 { | |
| 811 min_gallop -= min_gallop > 1; | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
812 ms->min_gallop = min_gallop; |
| 8700 | 813 k = gallop_right (*pb, pa, na, 0, comp); |
| 814 acount = k; | |
| 815 if (k) | |
| 816 { | |
| 817 if (k < 0) | |
| 818 goto Fail; | |
| 819 dest = std::copy (pa, pa + k, dest); | |
| 820 idest = std::copy (ipa, ipa + k, idest); | |
| 821 pa += k; ipa += k; | |
| 822 na -= k; | |
| 823 if (na == 1) | |
| 824 goto CopyB; | |
| 825 /* na==0 is impossible now if the comparison | |
| 826 * function is consistent, but we can't assume | |
| 827 * that it is. | |
| 828 */ | |
| 829 if (na == 0) | |
| 830 goto Succeed; | |
| 831 } | |
| 832 *dest++ = *pb++; *idest++ = *ipb++; | |
| 833 --nb; | |
| 834 if (nb == 0) | |
| 835 goto Succeed; | |
| 836 | |
| 837 k = gallop_left (*pa, pb, nb, 0, comp); | |
| 838 bcount = k; | |
| 839 if (k) | |
| 840 { | |
| 841 if (k < 0) | |
| 842 goto Fail; | |
| 843 dest = std::copy (pb, pb + k, dest); | |
| 844 idest = std::copy (ipb, ipb + k, idest); | |
| 845 pb += k; ipb += k; | |
| 846 nb -= k; | |
| 847 if (nb == 0) | |
| 848 goto Succeed; | |
| 849 } | |
| 850 *dest++ = *pa++; *idest++ = *ipa++; | |
| 851 --na; | |
| 852 if (na == 1) | |
| 853 goto CopyB; | |
| 854 } | |
| 855 while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); | |
| 856 | |
| 857 ++min_gallop; /* penalize it for leaving galloping mode */ | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
858 ms->min_gallop = min_gallop; |
| 8700 | 859 } |
| 860 | |
| 861 Succeed: | |
| 862 result = 0; | |
| 863 | |
| 864 Fail: | |
| 865 if (na) | |
| 866 { | |
| 867 std::copy (pa, pa + na, dest); | |
| 868 std::copy (ipa, ipa + na, idest); | |
| 869 } | |
| 870 return result; | |
| 871 | |
| 872 CopyB: | |
| 873 /* The last element of pa belongs at the end of the merge. */ | |
| 874 std::copy (pb, pb + nb, dest); | |
| 875 std::copy (ipb, ipb + nb, idest); | |
| 876 dest[nb] = *pa; | |
| 877 idest[nb] = *ipa; | |
| 878 | |
| 879 return 0; | |
| 880 } | |
| 881 | |
| 4851 | 882 /* Merge the na elements starting at pa with the nb elements starting at pb |
| 883 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. | |
| 884 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the | |
| 885 * merge, and should have na >= nb. See listsort.txt for more info. | |
| 886 * Return 0 if successful, -1 if error. | |
| 887 */ | |
| 888 template <class T> | |
| 8700 | 889 template <class Comp> |
| 4851 | 890 int |
| 8700 | 891 octave_sort<T>::merge_hi (T *pa, octave_idx_type na, |
| 892 T *pb, octave_idx_type nb, | |
| 893 Comp comp) | |
| 4851 | 894 { |
| 7433 | 895 octave_idx_type k; |
| 4851 | 896 T *dest; |
| 897 int result = -1; /* guilty until proved innocent */ | |
| 8700 | 898 T *basea, *baseb; |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
899 octave_idx_type min_gallop = ms->min_gallop; |
| 4851 | 900 |
| 8700 | 901 if (merge_getmem (nb) < 0) |
| 4851 | 902 return -1; |
| 903 dest = pb + nb - 1; | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
904 std::copy (pb, pb + nb, ms->a); |
| 4851 | 905 basea = pa; |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
906 baseb = ms->a; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
907 pb = ms->a + nb - 1; |
| 4851 | 908 pa += na - 1; |
| 909 | |
| 910 *dest-- = *pa--; | |
| 911 --na; | |
| 912 if (na == 0) | |
| 913 goto Succeed; | |
| 914 if (nb == 1) | |
| 915 goto CopyA; | |
| 916 | |
| 917 for (;;) | |
| 918 { | |
| 7433 | 919 octave_idx_type acount = 0; /* # of times A won in a row */ |
| 920 octave_idx_type bcount = 0; /* # of times B won in a row */ | |
| 4851 | 921 |
| 922 /* Do the straightforward thing until (if ever) one run | |
| 923 * appears to win consistently. | |
| 924 */ | |
| 925 for (;;) | |
| 926 { | |
| 8700 | 927 if (comp (*pb, *pa)) |
| 4851 | 928 { |
| 929 *dest-- = *pa--; | |
| 930 ++acount; | |
| 931 bcount = 0; | |
| 932 --na; | |
| 933 if (na == 0) | |
| 934 goto Succeed; | |
| 935 if (acount >= min_gallop) | |
| 936 break; | |
| 937 } | |
| 938 else | |
| 939 { | |
| 940 *dest-- = *pb--; | |
| 941 ++bcount; | |
| 942 acount = 0; | |
| 943 --nb; | |
| 944 if (nb == 1) | |
| 945 goto CopyA; | |
| 946 if (bcount >= min_gallop) | |
| 947 break; | |
| 948 } | |
| 949 } | |
| 950 | |
| 951 /* One run is winning so consistently that galloping may | |
| 952 * be a huge win. So try that, and continue galloping until | |
| 953 * (if ever) neither run appears to be winning consistently | |
| 954 * anymore. | |
| 955 */ | |
| 956 ++min_gallop; | |
| 957 do | |
| 958 { | |
| 959 min_gallop -= min_gallop > 1; | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
960 ms->min_gallop = min_gallop; |
| 8700 | 961 k = gallop_right (*pb, basea, na, na-1, comp); |
| 4851 | 962 if (k < 0) |
| 963 goto Fail; | |
| 964 k = na - k; | |
| 965 acount = k; | |
| 966 if (k) | |
| 967 { | |
| 8700 | 968 dest = std::copy_backward (pa+1 - k, pa+1, dest+1) - 1; |
| 4851 | 969 pa -= k; |
| 970 na -= k; | |
| 971 if (na == 0) | |
| 972 goto Succeed; | |
| 973 } | |
| 974 *dest-- = *pb--; | |
| 975 --nb; | |
| 976 if (nb == 1) | |
| 977 goto CopyA; | |
| 978 | |
| 8700 | 979 k = gallop_left (*pa, baseb, nb, nb-1, comp); |
| 4851 | 980 if (k < 0) |
| 981 goto Fail; | |
| 982 k = nb - k; | |
| 983 bcount = k; | |
| 984 if (k) | |
| 985 { | |
| 986 dest -= k; | |
| 987 pb -= k; | |
|
8206
0168d22e6bba
fix sorting of non-POD objects
Jaroslav Hajek <highegg@gmail.com>
parents:
7929
diff
changeset
|
988 std::copy (pb+1, pb+1 + k, dest+1); |
| 4851 | 989 nb -= k; |
| 990 if (nb == 1) | |
| 991 goto CopyA; | |
| 992 /* nb==0 is impossible now if the comparison | |
| 993 * function is consistent, but we can't assume | |
| 994 * that it is. | |
| 995 */ | |
| 996 if (nb == 0) | |
| 997 goto Succeed; | |
| 998 } | |
| 999 *dest-- = *pa--; | |
| 1000 --na; | |
| 1001 if (na == 0) | |
| 1002 goto Succeed; | |
| 1003 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); | |
| 1004 ++min_gallop; /* penalize it for leaving galloping mode */ | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1005 ms->min_gallop = min_gallop; |
| 4851 | 1006 } |
| 7234 | 1007 |
| 4851 | 1008 Succeed: |
| 1009 result = 0; | |
| 7234 | 1010 |
| 4851 | 1011 Fail: |
| 1012 if (nb) | |
|
8206
0168d22e6bba
fix sorting of non-POD objects
Jaroslav Hajek <highegg@gmail.com>
parents:
7929
diff
changeset
|
1013 std::copy (baseb, baseb + nb, dest-(nb-1)); |
| 4851 | 1014 return result; |
| 7234 | 1015 |
| 4851 | 1016 CopyA: |
| 1017 /* The first element of pb belongs at the front of the merge. */ | |
| 8700 | 1018 dest = std::copy_backward (pa+1 - na, pa+1, dest+1) - 1; |
| 4851 | 1019 pa -= na; |
| 1020 *dest = *pb; | |
| 7234 | 1021 |
| 4851 | 1022 return 0; |
| 1023 } | |
| 1024 | |
| 8700 | 1025 template <class T> |
| 1026 template <class Comp> | |
| 1027 int | |
| 1028 octave_sort<T>::merge_hi (T *pa, octave_idx_type *ipa, octave_idx_type na, | |
| 1029 T *pb, octave_idx_type *ipb, octave_idx_type nb, | |
| 1030 Comp comp) | |
| 1031 { | |
| 1032 octave_idx_type k; | |
| 1033 T *dest; | |
| 1034 octave_idx_type *idest; | |
| 1035 int result = -1; /* guilty until proved innocent */ | |
| 1036 T *basea, *baseb; | |
| 1037 octave_idx_type *ibasea, *ibaseb; | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1038 octave_idx_type min_gallop = ms->min_gallop; |
| 8700 | 1039 |
| 1040 if (merge_getmemi (nb) < 0) | |
| 1041 return -1; | |
| 1042 dest = pb + nb - 1; | |
| 1043 idest = ipb + nb - 1; | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1044 std::copy (pb, pb + nb, ms->a); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1045 std::copy (ipb, ipb + nb, ms->ia); |
| 8700 | 1046 basea = pa; ibasea = ipa; |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1047 baseb = ms->a; ibaseb = ms->ia; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1048 pb = ms->a + nb - 1; ipb = ms->ia + nb - 1; |
| 8700 | 1049 pa += na - 1; ipa += na - 1; |
| 1050 | |
| 1051 *dest-- = *pa--; *idest-- = *ipa--; | |
| 1052 --na; | |
| 1053 if (na == 0) | |
| 1054 goto Succeed; | |
| 1055 if (nb == 1) | |
| 1056 goto CopyA; | |
| 1057 | |
| 1058 for (;;) | |
| 1059 { | |
| 1060 octave_idx_type acount = 0; /* # of times A won in a row */ | |
| 1061 octave_idx_type bcount = 0; /* # of times B won in a row */ | |
| 1062 | |
| 1063 /* Do the straightforward thing until (if ever) one run | |
| 1064 * appears to win consistently. | |
| 1065 */ | |
| 1066 for (;;) | |
| 1067 { | |
| 1068 if (comp (*pb, *pa)) | |
| 1069 { | |
| 1070 *dest-- = *pa--; *idest-- = *ipa--; | |
| 1071 ++acount; | |
| 1072 bcount = 0; | |
| 1073 --na; | |
| 1074 if (na == 0) | |
| 1075 goto Succeed; | |
| 1076 if (acount >= min_gallop) | |
| 1077 break; | |
| 1078 } | |
| 1079 else | |
| 1080 { | |
| 1081 *dest-- = *pb--; *idest-- = *ipb--; | |
| 1082 ++bcount; | |
| 1083 acount = 0; | |
| 1084 --nb; | |
| 1085 if (nb == 1) | |
| 1086 goto CopyA; | |
| 1087 if (bcount >= min_gallop) | |
| 1088 break; | |
| 1089 } | |
| 1090 } | |
| 1091 | |
| 1092 /* One run is winning so consistently that galloping may | |
| 1093 * be a huge win. So try that, and continue galloping until | |
| 1094 * (if ever) neither run appears to be winning consistently | |
| 1095 * anymore. | |
| 1096 */ | |
| 1097 ++min_gallop; | |
| 1098 do | |
| 1099 { | |
| 1100 min_gallop -= min_gallop > 1; | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1101 ms->min_gallop = min_gallop; |
| 8700 | 1102 k = gallop_right (*pb, basea, na, na-1, comp); |
| 1103 if (k < 0) | |
| 1104 goto Fail; | |
| 1105 k = na - k; | |
| 1106 acount = k; | |
| 1107 if (k) | |
| 1108 { | |
| 1109 dest = std::copy_backward (pa+1 - k, pa+1, dest+1) - 1; | |
| 1110 idest = std::copy_backward (ipa+1 - k, ipa+1, idest+1) - 1; | |
| 1111 pa -= k; ipa -= k; | |
| 1112 na -= k; | |
| 1113 if (na == 0) | |
| 1114 goto Succeed; | |
| 1115 } | |
| 1116 *dest-- = *pb--; *idest-- = *ipb--; | |
| 1117 --nb; | |
| 1118 if (nb == 1) | |
| 1119 goto CopyA; | |
| 1120 | |
| 1121 k = gallop_left (*pa, baseb, nb, nb-1, comp); | |
| 1122 if (k < 0) | |
| 1123 goto Fail; | |
| 1124 k = nb - k; | |
| 1125 bcount = k; | |
| 1126 if (k) | |
| 1127 { | |
| 1128 dest -= k; idest -= k; | |
| 1129 pb -= k; ipb -= k; | |
| 1130 std::copy (pb+1, pb+1 + k, dest+1); | |
| 1131 std::copy (ipb+1, ipb+1 + k, idest+1); | |
| 1132 nb -= k; | |
| 1133 if (nb == 1) | |
| 1134 goto CopyA; | |
| 1135 /* nb==0 is impossible now if the comparison | |
| 1136 * function is consistent, but we can't assume | |
| 1137 * that it is. | |
| 1138 */ | |
| 1139 if (nb == 0) | |
| 1140 goto Succeed; | |
| 1141 } | |
| 1142 *dest-- = *pa--; *idest-- = *ipa--; | |
| 1143 --na; | |
| 1144 if (na == 0) | |
| 1145 goto Succeed; | |
| 1146 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); | |
| 1147 ++min_gallop; /* penalize it for leaving galloping mode */ | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1148 ms->min_gallop = min_gallop; |
| 8700 | 1149 } |
| 1150 | |
| 1151 Succeed: | |
| 1152 result = 0; | |
| 1153 | |
| 1154 Fail: | |
| 1155 if (nb) | |
| 1156 { | |
| 1157 std::copy (baseb, baseb + nb, dest-(nb-1)); | |
| 1158 std::copy (ibaseb, ibaseb + nb, idest-(nb-1)); | |
| 1159 } | |
| 1160 return result; | |
| 1161 | |
| 1162 CopyA: | |
| 1163 /* The first element of pb belongs at the front of the merge. */ | |
| 1164 dest = std::copy_backward (pa+1 - na, pa+1, dest+1) - 1; | |
| 1165 idest = std::copy_backward (ipa+1 - na, ipa+1, idest+1) - 1; | |
| 1166 pa -= na; ipa -= na; | |
| 1167 *dest = *pb; *idest = *ipb; | |
| 1168 | |
| 1169 return 0; | |
| 1170 } | |
| 1171 | |
| 4851 | 1172 /* Merge the two runs at stack indices i and i+1. |
| 1173 * Returns 0 on success, -1 on error. | |
| 1174 */ | |
| 1175 template <class T> | |
| 8700 | 1176 template <class Comp> |
| 4851 | 1177 int |
| 8700 | 1178 octave_sort<T>::merge_at (octave_idx_type i, T *data, |
| 1179 Comp comp) | |
| 4851 | 1180 { |
| 1181 T *pa, *pb; | |
| 7433 | 1182 octave_idx_type na, nb; |
| 1183 octave_idx_type k; | |
| 4851 | 1184 |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1185 pa = data + ms->pending[i].base; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1186 na = ms->pending[i].len; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1187 pb = data + ms->pending[i+1].base; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1188 nb = ms->pending[i+1].len; |
| 4851 | 1189 |
| 1190 /* Record the length of the combined runs; if i is the 3rd-last | |
| 1191 * run now, also slide over the last run (which isn't involved | |
| 1192 * in this merge). The current run i+1 goes away in any case. | |
| 1193 */ | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1194 ms->pending[i].len = na + nb; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1195 if (i == ms->n - 3) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1196 ms->pending[i+1] = ms->pending[i+2]; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1197 ms->n--; |
| 4851 | 1198 |
| 1199 /* Where does b start in a? Elements in a before that can be | |
| 1200 * ignored (already in place). | |
| 1201 */ | |
| 8700 | 1202 k = gallop_right (*pb, pa, na, 0, comp); |
| 4851 | 1203 if (k < 0) |
| 1204 return -1; | |
| 1205 pa += k; | |
| 1206 na -= k; | |
| 1207 if (na == 0) | |
| 1208 return 0; | |
| 1209 | |
| 1210 /* Where does a end in b? Elements in b after that can be | |
| 1211 * ignored (already in place). | |
| 1212 */ | |
| 8700 | 1213 nb = gallop_left (pa[na-1], pb, nb, nb-1, comp); |
| 4851 | 1214 if (nb <= 0) |
| 1215 return nb; | |
| 1216 | |
| 1217 /* Merge what remains of the runs, using a temp array with | |
| 1218 * min(na, nb) elements. | |
| 1219 */ | |
| 1220 if (na <= nb) | |
| 8700 | 1221 return merge_lo (pa, na, pb, nb, comp); |
| 4851 | 1222 else |
| 8700 | 1223 return merge_hi (pa, na, pb, nb, comp); |
| 1224 } | |
| 1225 | |
| 1226 template <class T> | |
| 1227 template <class Comp> | |
| 1228 int | |
| 1229 octave_sort<T>::merge_at (octave_idx_type i, T *data, octave_idx_type *idx, | |
| 1230 Comp comp) | |
| 1231 { | |
| 1232 T *pa, *pb; | |
| 1233 octave_idx_type *ipa, *ipb; | |
| 1234 octave_idx_type na, nb; | |
| 1235 octave_idx_type k; | |
| 1236 | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1237 pa = data + ms->pending[i].base; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1238 ipa = idx + ms->pending[i].base; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1239 na = ms->pending[i].len; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1240 pb = data + ms->pending[i+1].base; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1241 ipb = idx + ms->pending[i+1].base; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1242 nb = ms->pending[i+1].len; |
| 8700 | 1243 |
| 1244 /* Record the length of the combined runs; if i is the 3rd-last | |
| 1245 * run now, also slide over the last run (which isn't involved | |
| 1246 * in this merge). The current run i+1 goes away in any case. | |
| 1247 */ | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1248 ms->pending[i].len = na + nb; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1249 if (i == ms->n - 3) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1250 ms->pending[i+1] = ms->pending[i+2]; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1251 ms->n--; |
| 8700 | 1252 |
| 1253 /* Where does b start in a? Elements in a before that can be | |
| 1254 * ignored (already in place). | |
| 1255 */ | |
| 1256 k = gallop_right (*pb, pa, na, 0, comp); | |
| 1257 if (k < 0) | |
| 1258 return -1; | |
| 1259 pa += k; ipa += k; | |
| 1260 na -= k; | |
| 1261 if (na == 0) | |
| 1262 return 0; | |
| 1263 | |
| 1264 /* Where does a end in b? Elements in b after that can be | |
| 1265 * ignored (already in place). | |
| 1266 */ | |
| 1267 nb = gallop_left (pa[na-1], pb, nb, nb-1, comp); | |
| 1268 if (nb <= 0) | |
| 1269 return nb; | |
| 1270 | |
| 1271 /* Merge what remains of the runs, using a temp array with | |
| 1272 * min(na, nb) elements. | |
| 1273 */ | |
| 1274 if (na <= nb) | |
| 1275 return merge_lo (pa, ipa, na, pb, ipb, nb, comp); | |
| 1276 else | |
| 1277 return merge_hi (pa, ipa, na, pb, ipb, nb, comp); | |
| 4851 | 1278 } |
| 1279 | |
| 1280 /* Examine the stack of runs waiting to be merged, merging adjacent runs | |
| 1281 * until the stack invariants are re-established: | |
| 1282 * | |
| 1283 * 1. len[-3] > len[-2] + len[-1] | |
| 1284 * 2. len[-2] > len[-1] | |
| 1285 * | |
| 1286 * See listsort.txt for more info. | |
| 1287 * | |
| 1288 * Returns 0 on success, -1 on error. | |
| 1289 */ | |
| 1290 template <class T> | |
| 8700 | 1291 template <class Comp> |
| 4851 | 1292 int |
| 8700 | 1293 octave_sort<T>::merge_collapse (T *data, Comp comp) |
| 4851 | 1294 { |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1295 struct s_slice *p = ms->pending; |
| 4851 | 1296 |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1297 while (ms->n > 1) |
| 4851 | 1298 { |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1299 octave_idx_type n = ms->n - 2; |
| 4851 | 1300 if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) |
| 1301 { | |
| 1302 if (p[n-1].len < p[n+1].len) | |
| 1303 --n; | |
| 8700 | 1304 if (merge_at (n, data, comp) < 0) |
| 4851 | 1305 return -1; |
| 1306 } | |
| 1307 else if (p[n].len <= p[n+1].len) | |
| 1308 { | |
| 8700 | 1309 if (merge_at (n, data, comp) < 0) |
| 1310 return -1; | |
| 1311 } | |
| 1312 else | |
| 1313 break; | |
| 1314 } | |
| 1315 | |
| 1316 return 0; | |
| 1317 } | |
| 1318 | |
| 1319 template <class T> | |
| 1320 template <class Comp> | |
| 1321 int | |
| 1322 octave_sort<T>::merge_collapse (T *data, octave_idx_type *idx, Comp comp) | |
| 1323 { | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1324 struct s_slice *p = ms->pending; |
| 8700 | 1325 |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1326 while (ms->n > 1) |
| 8700 | 1327 { |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1328 octave_idx_type n = ms->n - 2; |
| 8700 | 1329 if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) |
| 1330 { | |
| 1331 if (p[n-1].len < p[n+1].len) | |
| 1332 --n; | |
| 1333 if (merge_at (n, data, idx, comp) < 0) | |
| 1334 return -1; | |
| 1335 } | |
| 1336 else if (p[n].len <= p[n+1].len) | |
| 1337 { | |
| 1338 if (merge_at (n, data, idx, comp) < 0) | |
| 4851 | 1339 return -1; |
| 1340 } | |
| 1341 else | |
| 1342 break; | |
| 1343 } | |
| 7234 | 1344 |
| 4851 | 1345 return 0; |
| 1346 } | |
| 1347 | |
| 1348 /* Regardless of invariants, merge all runs on the stack until only one | |
| 1349 * remains. This is used at the end of the mergesort. | |
| 1350 * | |
| 1351 * Returns 0 on success, -1 on error. | |
| 1352 */ | |
| 1353 template <class T> | |
| 8700 | 1354 template <class Comp> |
| 4851 | 1355 int |
| 8700 | 1356 octave_sort<T>::merge_force_collapse (T *data, Comp comp) |
| 4851 | 1357 { |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1358 struct s_slice *p = ms->pending; |
| 4851 | 1359 |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1360 while (ms->n > 1) |
| 4851 | 1361 { |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1362 octave_idx_type n = ms->n - 2; |
| 4851 | 1363 if (n > 0 && p[n-1].len < p[n+1].len) |
| 1364 --n; | |
| 8700 | 1365 if (merge_at (n, data, comp) < 0) |
| 1366 return -1; | |
| 1367 } | |
| 1368 | |
| 1369 return 0; | |
| 1370 } | |
| 1371 | |
| 1372 template <class T> | |
| 1373 template <class Comp> | |
| 1374 int | |
| 1375 octave_sort<T>::merge_force_collapse (T *data, octave_idx_type *idx, Comp comp) | |
| 1376 { | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1377 struct s_slice *p = ms->pending; |
| 8700 | 1378 |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1379 while (ms->n > 1) |
| 8700 | 1380 { |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1381 octave_idx_type n = ms->n - 2; |
| 8700 | 1382 if (n > 0 && p[n-1].len < p[n+1].len) |
| 1383 --n; | |
| 1384 if (merge_at (n, data, idx, comp) < 0) | |
| 4851 | 1385 return -1; |
| 1386 } | |
| 7234 | 1387 |
| 4851 | 1388 return 0; |
| 1389 } | |
| 1390 | |
| 1391 /* Compute a good value for the minimum run length; natural runs shorter | |
| 1392 * than this are boosted artificially via binary insertion. | |
| 1393 * | |
| 1394 * If n < 64, return n (it's too small to bother with fancy stuff). | |
| 1395 * Else if n is an exact power of 2, return 32. | |
| 1396 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but | |
| 1397 * strictly less than, an exact power of 2. | |
| 1398 * | |
| 1399 * See listsort.txt for more info. | |
| 1400 */ | |
| 1401 template <class T> | |
| 7433 | 1402 octave_idx_type |
| 1403 octave_sort<T>::merge_compute_minrun (octave_idx_type n) | |
| 4851 | 1404 { |
| 7433 | 1405 octave_idx_type r = 0; /* becomes 1 if any 1 bits are shifted off */ |
| 4851 | 1406 |
| 7234 | 1407 while (n >= 64) |
| 1408 { | |
| 1409 r |= n & 1; | |
| 1410 n >>= 1; | |
| 1411 } | |
| 1412 | |
| 4851 | 1413 return n + r; |
| 1414 } | |
| 1415 | |
| 1416 template <class T> | |
| 8700 | 1417 template <class Comp> |
| 4851 | 1418 void |
| 8700 | 1419 octave_sort<T>::sort (T *data, octave_idx_type nel, Comp comp) |
| 4851 | 1420 { |
| 1421 /* Re-initialize the Mergestate as this might be the second time called */ | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1422 if (ms) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1423 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1424 ms->n = 0; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1425 ms->min_gallop = MIN_GALLOP; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1426 } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1427 else |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1428 merge_init (); |
| 4851 | 1429 |
| 8700 | 1430 if (nel > 1) |
| 4851 | 1431 { |
| 8700 | 1432 octave_idx_type nremaining = nel; |
| 1433 octave_idx_type lo = 0; | |
| 1434 | |
| 1435 /* March over the array once, left to right, finding natural runs, | |
| 1436 * and extending short natural runs to minrun elements. | |
| 1437 */ | |
| 1438 octave_idx_type minrun = merge_compute_minrun (nremaining); | |
| 1439 do | |
| 1440 { | |
| 1441 bool descending; | |
| 1442 octave_idx_type n; | |
| 1443 | |
| 1444 /* Identify next run. */ | |
| 1445 n = count_run (data + lo, nremaining, descending, comp); | |
| 1446 if (n < 0) | |
| 1447 goto fail; | |
| 1448 if (descending) | |
| 1449 std::reverse (data + lo, data + lo + n); | |
| 1450 /* If short, extend to min(minrun, nremaining). */ | |
| 1451 if (n < minrun) | |
| 1452 { | |
| 1453 const octave_idx_type force = nremaining <= minrun ? nremaining : minrun; | |
| 1454 binarysort (data + lo, force, n, comp); | |
| 1455 n = force; | |
| 1456 } | |
| 1457 /* Push run onto pending-runs stack, and maybe merge. */ | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1458 assert (ms->n < MAX_MERGE_PENDING); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1459 ms->pending[ms->n].base = lo; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1460 ms->pending[ms->n].len = n; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1461 ms->n++; |
| 8700 | 1462 if (merge_collapse (data, comp) < 0) |
| 1463 goto fail; | |
| 1464 /* Advance to find next run. */ | |
| 1465 lo += n; | |
| 1466 nremaining -= n; | |
| 1467 } | |
| 1468 while (nremaining); | |
| 1469 | |
| 1470 merge_force_collapse (data, comp); | |
| 1471 } | |
| 1472 | |
| 1473 fail: | |
| 1474 return; | |
| 1475 } | |
| 1476 | |
| 1477 template <class T> | |
| 1478 template <class Comp> | |
| 1479 void | |
| 1480 octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel, | |
| 1481 Comp comp) | |
| 1482 { | |
| 1483 if (nel > 1) | |
| 1484 { | |
| 1485 octave_idx_type nremaining = nel; | |
| 1486 octave_idx_type lo = 0; | |
| 4851 | 1487 |
| 1488 /* March over the array once, left to right, finding natural runs, | |
| 1489 * and extending short natural runs to minrun elements. | |
| 1490 */ | |
| 7433 | 1491 octave_idx_type minrun = merge_compute_minrun (nremaining); |
| 4851 | 1492 do |
| 1493 { | |
| 7929 | 1494 bool descending; |
| 7433 | 1495 octave_idx_type n; |
| 4851 | 1496 |
| 1497 /* Identify next run. */ | |
| 8700 | 1498 n = count_run (data + lo, nremaining, descending, comp); |
| 4851 | 1499 if (n < 0) |
| 1500 goto fail; | |
| 1501 if (descending) | |
| 8700 | 1502 { |
| 1503 std::reverse (data + lo, data + lo + n); | |
| 1504 std::reverse (idx + lo, idx + lo + n); | |
| 1505 } | |
| 4851 | 1506 /* If short, extend to min(minrun, nremaining). */ |
| 1507 if (n < minrun) | |
| 1508 { | |
| 7433 | 1509 const octave_idx_type force = nremaining <= minrun ? nremaining : minrun; |
| 8700 | 1510 binarysort (data + lo, idx + lo, force, n, comp); |
| 4851 | 1511 n = force; |
| 1512 } | |
| 1513 /* Push run onto pending-runs stack, and maybe merge. */ | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1514 assert (ms->n < MAX_MERGE_PENDING); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1515 ms->pending[ms->n].base = lo; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1516 ms->pending[ms->n].len = n; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1517 ms->n++; |
| 8700 | 1518 if (merge_collapse (data, idx, comp) < 0) |
| 4851 | 1519 goto fail; |
| 1520 /* Advance to find next run. */ | |
| 1521 lo += n; | |
| 1522 nremaining -= n; | |
| 7234 | 1523 } |
| 1524 while (nremaining); | |
| 4851 | 1525 |
| 8700 | 1526 merge_force_collapse (data, idx, comp); |
| 4851 | 1527 } |
| 1528 | |
| 1529 fail: | |
| 1530 return; | |
| 1531 } | |
| 1532 | |
| 8700 | 1533 template <class T> |
| 1534 void | |
| 1535 octave_sort<T>::sort (T *data, octave_idx_type nel) | |
| 1536 { | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1537 /* Re-initialize the Mergestate as this might be the second time called */ |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1538 if (ms) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1539 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1540 ms->n = 0; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1541 ms->min_gallop = MIN_GALLOP; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1542 } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1543 else |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1544 merge_init (); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1545 |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1546 merge_getmem (1024); |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1547 |
| 8700 | 1548 #ifdef INLINE_ASCENDING_SORT |
| 1549 if (compare == ascending_compare) | |
| 1550 sort (data, nel, std::less<T> ()); | |
| 1551 else | |
| 1552 #endif | |
| 1553 #ifdef INLINE_DESCENDING_SORT | |
| 1554 if (compare == descending_compare) | |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1555 sort (data, nel, std::greater<T> ()); |
| 8700 | 1556 else |
| 1557 #endif | |
| 1558 if (compare) | |
| 1559 sort (data, nel, compare); | |
| 1560 } | |
| 1561 | |
| 1562 template <class T> | |
| 1563 void | |
| 1564 octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel) | |
| 1565 { | |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1566 /* Re-initialize the Mergestate as this might be the second time called */ |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1567 if (ms) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1568 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1569 ms->n = 0; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1570 ms->min_gallop = MIN_GALLOP; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1571 } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1572 else |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1573 merge_init (); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1574 |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1575 merge_getmemi (1024); |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1576 |
| 8700 | 1577 #ifdef INLINE_ASCENDING_SORT |
| 1578 if (compare == ascending_compare) | |
| 1579 sort (data, idx, nel, std::less<T> ()); | |
| 1580 else | |
| 1581 #endif | |
| 1582 #ifdef INLINE_DESCENDING_SORT | |
| 1583 if (compare == descending_compare) | |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1584 sort (data, idx, nel, std::greater<T> ()); |
| 8700 | 1585 else |
| 1586 #endif | |
| 1587 if (compare) | |
| 1588 sort (data, idx, nel, compare); | |
| 1589 } | |
| 1590 | |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1591 template <class T> template <class Comp> |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1592 bool |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1593 octave_sort<T>::is_sorted (const T *data, octave_idx_type nel, Comp comp) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1594 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1595 const T *end = data + nel; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1596 if (data != end) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1597 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1598 const T *next = data; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1599 while (++next != end) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1600 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1601 if (comp (*next, *data)) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1602 break; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1603 data = next; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1604 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1605 data = next; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1606 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1607 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1608 return data == end; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1609 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1610 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1611 template <class T> |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1612 bool |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1613 octave_sort<T>::is_sorted (const T *data, octave_idx_type nel) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1614 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1615 bool retval = false; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1616 #ifdef INLINE_ASCENDING_SORT |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1617 if (compare == ascending_compare) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1618 retval = is_sorted (data, nel, std::less<T> ()); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1619 else |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1620 #endif |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1621 #ifdef INLINE_DESCENDING_SORT |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1622 if (compare == descending_compare) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1623 retval = is_sorted (data, nel, std::greater<T> ()); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1624 else |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1625 #endif |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1626 if (compare) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1627 retval = is_sorted (data, nel, compare); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1628 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1629 return retval; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1630 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1631 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1632 // FIXME: is there really no way to make this local to the following function? |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1633 struct sortrows_run_t |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1634 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1635 sortrows_run_t (octave_idx_type c, octave_idx_type o, octave_idx_type n) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1636 : col (c), ofs (o), nel (n) { } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1637 octave_idx_type col, ofs, nel; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1638 }; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1639 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1640 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1641 template <class T> template <class Comp> |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1642 void |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1643 octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx, |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1644 octave_idx_type rows, octave_idx_type cols, |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1645 Comp comp) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1646 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1647 OCTAVE_LOCAL_BUFFER (T, buf, rows); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1648 for (octave_idx_type i = 0; i < rows; i++) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1649 idx[i] = i; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1650 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1651 if (cols == 0 || rows <= 1) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1652 return; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1653 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1654 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1655 // This is a breadth-first traversal. |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1656 typedef sortrows_run_t run_t; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1657 std::stack<run_t> runs; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1658 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1659 runs.push (run_t (0, 0, rows)); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1660 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1661 while (! runs.empty ()) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1662 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1663 octave_idx_type col = runs.top ().col; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1664 octave_idx_type ofs = runs.top ().ofs; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1665 octave_idx_type nel = runs.top ().nel; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1666 runs.pop (); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1667 assert (nel > 1); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1668 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1669 T *lbuf = buf + ofs; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1670 const T *ldata = data + rows*col; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1671 octave_idx_type *lidx = idx + ofs; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1672 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1673 // Gather. |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1674 for (octave_idx_type i = 0; i < nel; i++) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1675 lbuf[i] = ldata[lidx[i]]; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1676 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1677 // Sort. |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1678 sort (lbuf, lidx, nel, comp); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1679 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1680 // Identify constant runs and schedule subsorts. |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1681 if (col < cols-1) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1682 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1683 octave_idx_type lst = 0; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1684 for (octave_idx_type i = 0; i < nel; i++) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1685 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1686 if (comp (lbuf[lst], lbuf[i])) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1687 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1688 if (i > lst + 1) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1689 runs.push (run_t (col+1, lst, i - lst)); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1690 lst = i; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1691 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1692 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1693 if (nel > lst + 1) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1694 runs.push (run_t (col+1, lst, nel - lst)); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1695 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1696 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1697 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1698 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1699 template <class T> |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1700 void |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1701 octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx, |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1702 octave_idx_type rows, octave_idx_type cols) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1703 { |
|
8816
a4a8f871be81
fix missing init in octave_sort<T>::sortrows
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
1704 /* Re-initialize the Mergestate as this might be the second time called */ |
|
a4a8f871be81
fix missing init in octave_sort<T>::sortrows
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
1705 if (ms) |
|
a4a8f871be81
fix missing init in octave_sort<T>::sortrows
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
1706 { |
|
a4a8f871be81
fix missing init in octave_sort<T>::sortrows
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
1707 ms->n = 0; |
|
a4a8f871be81
fix missing init in octave_sort<T>::sortrows
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
1708 ms->min_gallop = MIN_GALLOP; |
|
a4a8f871be81
fix missing init in octave_sort<T>::sortrows
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
1709 } |
|
a4a8f871be81
fix missing init in octave_sort<T>::sortrows
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
1710 else |
|
a4a8f871be81
fix missing init in octave_sort<T>::sortrows
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
1711 merge_init (); |
|
a4a8f871be81
fix missing init in octave_sort<T>::sortrows
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
1712 |
|
a4a8f871be81
fix missing init in octave_sort<T>::sortrows
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
1713 merge_getmemi (1024); |
|
a4a8f871be81
fix missing init in octave_sort<T>::sortrows
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
1714 |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1715 #ifdef INLINE_ASCENDING_SORT |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1716 if (compare == ascending_compare) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1717 sort_rows (data, idx, rows, cols, std::less<T> ()); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1718 else |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1719 #endif |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1720 #ifdef INLINE_DESCENDING_SORT |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1721 if (compare == descending_compare) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1722 sort_rows (data, idx, rows, cols, std::greater<T> ()); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1723 else |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1724 #endif |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1725 if (compare) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1726 sort_rows (data, idx, rows, cols, compare); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1727 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1728 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1729 template <class T> template <class Comp> |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1730 bool |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1731 octave_sort<T>::is_sorted_rows (const T *data, octave_idx_type rows, |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1732 octave_idx_type cols, Comp comp) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1733 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1734 if (rows <= 1 || cols == 0) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1735 return true; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1736 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1737 // This is a breadth-first traversal. |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1738 const T *lastrow = data + rows*(cols - 1); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1739 typedef std::pair<const T *, octave_idx_type> run_t; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1740 std::stack<run_t> runs; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1741 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1742 bool sorted = true; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1743 runs.push (run_t (data, rows)); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1744 while (sorted && ! runs.empty ()) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1745 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1746 const T *lo = runs.top ().first; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1747 octave_idx_type n = runs.top ().second; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1748 runs.pop (); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1749 if (lo < lastrow) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1750 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1751 // Not the final column. |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1752 assert (n > 1); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1753 const T *hi = lo + n, *lst = lo; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1754 for (lo++; lo < hi; lo++) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1755 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1756 if (comp (*lst, *lo)) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1757 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1758 if (lo > lst + 1) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1759 runs.push (run_t (lst + rows, lo - lst)); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1760 lst = lo; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1761 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1762 else if (comp (*lo, *lst)) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1763 break; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1764 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1765 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1766 if (lo == hi) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1767 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1768 if (lo > lst + 1) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1769 runs.push (run_t (lst + rows, lo - lst)); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1770 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1771 else |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1772 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1773 sorted = false; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1774 break; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1775 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1776 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1777 else |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1778 // The final column - use fast code. |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1779 sorted = is_sorted (lo, n, comp); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1780 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1781 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1782 return sorted; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1783 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1784 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1785 template <class T> |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1786 bool |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1787 octave_sort<T>::is_sorted_rows (const T *data, octave_idx_type rows, |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1788 octave_idx_type cols) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1789 { |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1790 bool retval = false; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1791 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1792 #ifdef INLINE_ASCENDING_SORT |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1793 if (compare == ascending_compare) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1794 retval = is_sorted_rows (data, rows, cols, std::less<T> ()); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1795 else |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1796 #endif |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1797 #ifdef INLINE_DESCENDING_SORT |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1798 if (compare == descending_compare) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1799 retval = is_sorted_rows (data, rows, cols, std::greater<T> ()); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1800 else |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1801 #endif |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1802 if (compare) |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1803 retval = is_sorted_rows (data, rows, cols, compare); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1804 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1805 return retval; |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1806 } |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1807 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1808 |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1809 template <class T> template <class Comp> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1810 octave_idx_type |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1811 octave_sort<T>::lookup (const T *data, octave_idx_type nel, |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1812 const T& value, Comp comp) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1813 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1814 return std::upper_bound (data, data + nel, value, comp) - data; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1815 } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1816 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1817 template <class T> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1818 octave_idx_type |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1819 octave_sort<T>::lookup (const T *data, octave_idx_type nel, |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1820 const T& value) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1821 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1822 octave_idx_type retval = 0; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1823 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1824 #ifdef INLINE_ASCENDING_SORT |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1825 if (compare == ascending_compare) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1826 retval = lookup (data, nel, value, std::less<T> ()); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1827 else |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1828 #endif |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1829 #ifdef INLINE_DESCENDING_SORT |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1830 if (compare == descending_compare) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1831 retval = lookup (data, nel, value, std::greater<T> ()); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1832 else |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1833 #endif |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1834 if (compare) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1835 retval = lookup (data, nel, value, std::ptr_fun (compare)); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1836 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1837 return retval; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1838 } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1839 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1840 // a unary functor that checks whether a value is outside [a,b) range |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1841 template<class T, class Comp> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1842 class out_of_range_pred : public std::unary_function<T, bool> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1843 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1844 public: |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1845 out_of_range_pred (const T& aa, const T& bb, Comp c) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1846 : a (aa), b (bb), comp (c) { } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1847 bool operator () (const T& x) { return comp (x, a) || ! comp (x, b); } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1848 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1849 private: |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1850 T a, b; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1851 Comp comp; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1852 }; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1853 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1854 // a unary functor that checks whether a value is < a |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1855 template<class T, class Comp> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1856 class less_than_pred : public std::unary_function<T, bool> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1857 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1858 typedef typename ref_param<T>::type param_type; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1859 public: |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1860 less_than_pred (param_type aa, Comp c) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1861 : a (aa), comp (c) { } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1862 bool operator () (const T& x) { return comp (x, a); } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1863 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1864 private: |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1865 T a; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1866 Comp comp; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1867 }; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1868 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1869 // a unary functor that checks whether a value is >= a |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1870 template<class T, class Comp> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1871 class greater_or_equal_pred : public std::unary_function<T, bool> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1872 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1873 public: |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1874 greater_or_equal_pred (const T& aa, Comp c) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1875 : a (aa), comp (c) { } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1876 bool operator () (const T& x) { return ! comp (x, a); } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1877 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1878 private: |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1879 T a; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1880 Comp comp; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1881 }; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1882 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1883 // conveniently constructs the above functors. |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1884 // NOTE: with SGI extensions, this one can be written as |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1885 // compose2 (logical_and<bool>(), bind2nd (less<T>(), a), |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1886 // not1 (bind2nd (less<T>(), b))) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1887 template<class T, class Comp> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1888 inline out_of_range_pred<T, Comp> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1889 out_of_range (const T& a, |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1890 const T& b, Comp comp) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1891 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1892 return out_of_range_pred<T, Comp> (a, b, comp); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1893 } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1894 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1895 // Note: these could be written as |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1896 // std::not1 (std::bind2nd (comp, *cur)) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1897 // and |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1898 // std::bind2nd (comp, *(cur-1))); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1899 // but that doesn't work for functions with reference parameters in g++ 4.3. |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1900 template<class T, class Comp> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1901 inline less_than_pred<T, Comp> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1902 less_than (const T& a, Comp comp) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1903 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1904 return less_than_pred<T, Comp> (a, comp); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1905 } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1906 template<class T, class Comp> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1907 inline greater_or_equal_pred<T, Comp> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1908 greater_or_equal (const T& a, Comp comp) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1909 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1910 return greater_or_equal_pred<T, Comp> (a, comp); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1911 } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1912 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1913 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1914 template <class T> template <class Comp> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1915 void |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1916 octave_sort<T>::lookup (const T *data, octave_idx_type nel, |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1917 const T *values, octave_idx_type nvalues, |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1918 octave_idx_type *idx, octave_idx_type offset, Comp comp) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1919 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1920 if (nel == 0) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1921 // the trivial case of empty table |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1922 std::fill_n (idx, nvalues, offset); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1923 else |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1924 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1925 const T *vcur = values; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1926 const T *vend = values + nvalues; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1927 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1928 const T *cur = data; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1929 const T *end = data + nel; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1930 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1931 while (vcur != vend) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1932 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1933 // determine the enclosing interval for next value, trying |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1934 // ++cur as a special case; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1935 if (cur == end || comp (*vcur, *cur)) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1936 cur = std::upper_bound (data, cur, *vcur, comp); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1937 else |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1938 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1939 ++cur; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1940 if (cur != end && ! comp (*vcur, *cur)) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1941 cur = std::upper_bound (cur + 1, end, *vcur, comp); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1942 } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1943 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1944 octave_idx_type vidx = cur - data + offset; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1945 // store index of the current interval. |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1946 *(idx++) = vidx; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1947 ++vcur; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1948 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1949 // find first value not in current subrange |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1950 const T *vnew; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1951 if (cur != end) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1952 if (cur != data) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1953 // inner interval |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1954 vnew = std::find_if (vcur, vend, |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1955 out_of_range (*(cur-1), *cur, comp)); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1956 else |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1957 // special case: lowermost range (-Inf, min) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1958 vnew = std::find_if (vcur, vend, greater_or_equal (*cur, comp)); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1959 else |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1960 // special case: uppermost range [max, Inf) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1961 vnew = std::find_if (vcur, vend, less_than (*(cur-1), comp)); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1962 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1963 // store index of the current interval. |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1964 std::fill_n (idx, vnew - vcur, vidx); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1965 idx += (vnew - vcur); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1966 vcur = vnew; |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1967 } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1968 } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1969 } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1970 |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1971 template <class T> |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1972 void |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1973 octave_sort<T>::lookup (const T *data, octave_idx_type nel, |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1974 const T* values, octave_idx_type nvalues, |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1975 octave_idx_type *idx, octave_idx_type offset) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1976 { |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1977 #ifdef INLINE_ASCENDING_SORT |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1978 if (compare == ascending_compare) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1979 lookup (data, nel, values, nvalues, idx, offset, std::less<T> ()); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1980 else |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1981 #endif |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1982 #ifdef INLINE_DESCENDING_SORT |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1983 if (compare == descending_compare) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1984 lookup (data, nel, values, nvalues, idx, offset, std::greater<T> ()); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1985 else |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1986 #endif |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1987 if (compare) |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1988 lookup (data, nel, values, nvalues, idx, offset, std::ptr_fun (compare)); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1989 } |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1990 |
| 8700 | 1991 template <class T> |
| 1992 bool | |
| 8725 | 1993 octave_sort<T>::ascending_compare (typename ref_param<T>::type x, |
| 1994 typename ref_param<T>::type y) | |
| 8700 | 1995 { |
| 1996 return x < y; | |
| 1997 } | |
| 1998 | |
| 1999 template <class T> | |
| 2000 bool | |
| 8725 | 2001 octave_sort<T>::descending_compare (typename ref_param<T>::type x, |
| 2002 typename ref_param<T>::type y) | |
| 8700 | 2003 { |
| 2004 return x > y; | |
| 2005 } | |
| 2006 | |
| 4851 | 2007 /* |
| 2008 ;;; Local Variables: *** | |
| 2009 ;;; mode: C++ *** | |
| 2010 ;;; End: *** | |
| 2011 */ |