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