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