|
5000
|
1 /* |
|
2928
|
2 |
|
7017
|
3 Copyright (C) 2004, 2005, 2006, 2007 David Bateman and John W. Eaton |
|
|
4 Copyright (C) 1996, 1997, 1999, 2000, 2001, 2002, 2003 John W. Eaton |
|
2928
|
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. |
|
2928
|
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/>. |
|
2928
|
21 |
|
|
22 */ |
|
|
23 |
|
|
24 #ifdef HAVE_CONFIG_H |
|
|
25 #include <config.h> |
|
|
26 #endif |
|
|
27 |
|
5164
|
28 #include <vector> |
|
|
29 |
|
3826
|
30 #include "lo-mappers.h" |
|
4153
|
31 #include "quit.h" |
|
3826
|
32 |
|
2928
|
33 #include "defun-dld.h" |
|
|
34 #include "error.h" |
|
|
35 #include "gripes.h" |
|
|
36 #include "oct-obj.h" |
|
4850
|
37 #include "lo-ieee.h" |
|
|
38 #include "data-conv.h" |
|
|
39 #include "ov-cx-mat.h" |
|
4996
|
40 #include "ov-cell.h" |
|
4850
|
41 #include "oct-sort.cc" |
|
2928
|
42 |
|
4997
|
43 enum sortmode { UNDEFINED, ASCENDING, DESCENDING }; |
|
4996
|
44 |
|
|
45 template <class T> |
|
|
46 class |
|
|
47 vec_index |
|
|
48 { |
|
4997
|
49 public: |
|
4996
|
50 T vec; |
|
5275
|
51 octave_idx_type indx; |
|
4996
|
52 }; |
|
|
53 |
|
|
54 template <class T> |
|
5009
|
55 bool |
|
|
56 ascending_compare (T a, T b) |
|
|
57 { |
|
|
58 return (a < b); |
|
|
59 } |
|
|
60 |
|
|
61 template <class T> |
|
|
62 bool |
|
|
63 descending_compare (T a, T b) |
|
|
64 { |
|
|
65 return (a > b); |
|
|
66 } |
|
|
67 |
|
|
68 template <class T> |
|
|
69 bool |
|
|
70 ascending_compare (vec_index<T> *a, vec_index<T> *b) |
|
|
71 { |
|
|
72 return (a->vec < b->vec); |
|
|
73 } |
|
|
74 |
|
|
75 template <class T> |
|
|
76 bool |
|
|
77 descending_compare (vec_index<T> *a, vec_index<T> *b) |
|
|
78 { |
|
|
79 return (a->vec > b->vec); |
|
|
80 } |
|
|
81 |
|
|
82 template <class T> |
|
4998
|
83 static octave_value |
|
4996
|
84 mx_sort (ArrayN<T> &m, int dim, sortmode mode = UNDEFINED) |
|
|
85 { |
|
4998
|
86 octave_value retval; |
|
4996
|
87 |
|
5366
|
88 dim_vector dv = m.dims (); |
|
|
89 |
|
4996
|
90 if (m.length () < 1) |
|
5366
|
91 return ArrayN<T> (dv); |
|
4996
|
92 |
|
5275
|
93 octave_idx_type ns = dv(dim); |
|
|
94 octave_idx_type iter = dv.numel () / ns; |
|
|
95 octave_idx_type stride = 1; |
|
|
96 for (int i = 0; i < dim; i++) |
|
4996
|
97 stride *= dv(i); |
|
|
98 |
|
|
99 T *v = m.fortran_vec (); |
|
|
100 octave_sort<T> sort; |
|
|
101 |
|
|
102 if (mode == ASCENDING) |
|
|
103 sort.set_compare (ascending_compare); |
|
|
104 else if (mode == DESCENDING) |
|
|
105 sort.set_compare (descending_compare); |
|
|
106 |
|
|
107 if (stride == 1) |
|
4997
|
108 { |
|
5275
|
109 for (octave_idx_type j = 0; j < iter; j++) |
|
4997
|
110 { |
|
|
111 sort.sort (v, ns); |
|
|
112 v += ns; |
|
|
113 } |
|
|
114 } |
|
4996
|
115 else |
|
|
116 { |
|
|
117 OCTAVE_LOCAL_BUFFER (T, vi, ns); |
|
5275
|
118 for (octave_idx_type j = 0; j < iter; j++) |
|
4996
|
119 { |
|
5275
|
120 octave_idx_type offset = j; |
|
|
121 octave_idx_type offset2 = 0; |
|
4996
|
122 while (offset >= stride) |
|
|
123 { |
|
|
124 offset -= stride; |
|
|
125 offset2++; |
|
|
126 } |
|
|
127 offset += offset2 * stride * ns; |
|
|
128 |
|
5275
|
129 for (octave_idx_type i = 0; i < ns; i++) |
|
4996
|
130 vi[i] = v[i*stride + offset]; |
|
|
131 |
|
|
132 sort.sort (vi, ns); |
|
|
133 |
|
5275
|
134 for (octave_idx_type i = 0; i < ns; i++) |
|
4996
|
135 v[i*stride + offset] = vi[i]; |
|
|
136 } |
|
|
137 } |
|
|
138 |
|
4998
|
139 retval = m; |
|
4997
|
140 |
|
4996
|
141 return retval; |
|
|
142 } |
|
|
143 |
|
|
144 template <class T> |
|
|
145 static octave_value_list |
|
|
146 mx_sort_indexed (ArrayN<T> &m, int dim, sortmode mode = UNDEFINED) |
|
|
147 { |
|
|
148 octave_value_list retval; |
|
|
149 |
|
5366
|
150 dim_vector dv = m.dims (); |
|
|
151 |
|
4996
|
152 if (m.length () < 1) |
|
5360
|
153 { |
|
5366
|
154 retval(1) = NDArray (dv); |
|
|
155 retval(0) = ArrayN<T> (dv); |
|
5360
|
156 return retval; |
|
|
157 } |
|
4996
|
158 |
|
5275
|
159 octave_idx_type ns = dv(dim); |
|
|
160 octave_idx_type iter = dv.numel () / ns; |
|
|
161 octave_idx_type stride = 1; |
|
|
162 for (int i = 0; i < dim; i++) |
|
4996
|
163 stride *= dv(i); |
|
|
164 |
|
|
165 T *v = m.fortran_vec (); |
|
|
166 octave_sort<vec_index<T> *> indexed_sort; |
|
|
167 |
|
|
168 if (mode == ASCENDING) |
|
|
169 indexed_sort.set_compare (ascending_compare); |
|
|
170 else if (mode == DESCENDING) |
|
|
171 indexed_sort.set_compare (descending_compare); |
|
|
172 |
|
|
173 OCTAVE_LOCAL_BUFFER (vec_index<T> *, vi, ns); |
|
|
174 OCTAVE_LOCAL_BUFFER (vec_index<T>, vix, ns); |
|
|
175 |
|
5275
|
176 for (octave_idx_type i = 0; i < ns; i++) |
|
4996
|
177 vi[i] = &vix[i]; |
|
|
178 |
|
|
179 NDArray idx (dv); |
|
|
180 |
|
|
181 if (stride == 1) |
|
|
182 { |
|
5275
|
183 for (octave_idx_type j = 0; j < iter; j++) |
|
4996
|
184 { |
|
5275
|
185 octave_idx_type offset = j * ns; |
|
4996
|
186 |
|
5275
|
187 for (octave_idx_type i = 0; i < ns; i++) |
|
4996
|
188 { |
|
|
189 vi[i]->vec = v[i]; |
|
|
190 vi[i]->indx = i + 1; |
|
|
191 } |
|
|
192 |
|
|
193 indexed_sort.sort (vi, ns); |
|
|
194 |
|
5275
|
195 for (octave_idx_type i = 0; i < ns; i++) |
|
4996
|
196 { |
|
|
197 v[i] = vi[i]->vec; |
|
|
198 idx(i + offset) = vi[i]->indx; |
|
|
199 } |
|
|
200 v += ns; |
|
|
201 } |
|
|
202 } |
|
|
203 else |
|
|
204 { |
|
5275
|
205 for (octave_idx_type j = 0; j < iter; j++) |
|
4996
|
206 { |
|
5275
|
207 octave_idx_type offset = j; |
|
|
208 octave_idx_type offset2 = 0; |
|
4996
|
209 while (offset >= stride) |
|
|
210 { |
|
|
211 offset -= stride; |
|
|
212 offset2++; |
|
|
213 } |
|
|
214 offset += offset2 * stride * ns; |
|
|
215 |
|
5275
|
216 for (octave_idx_type i = 0; i < ns; i++) |
|
4996
|
217 { |
|
|
218 vi[i]->vec = v[i*stride + offset]; |
|
|
219 vi[i]->indx = i + 1; |
|
|
220 } |
|
|
221 |
|
|
222 indexed_sort.sort (vi, ns); |
|
|
223 |
|
5275
|
224 for (octave_idx_type i = 0; i < ns; i++) |
|
4996
|
225 { |
|
|
226 v[i*stride+offset] = vi[i]->vec; |
|
|
227 idx(i*stride+offset) = vi[i]->indx; |
|
|
228 } |
|
|
229 } |
|
|
230 } |
|
|
231 |
|
4997
|
232 retval(1) = idx; |
|
|
233 retval(0) = octave_value (m); |
|
4999
|
234 |
|
4996
|
235 return retval; |
|
|
236 } |
|
|
237 |
|
6863
|
238 template <class T> |
|
|
239 static octave_value |
|
|
240 mx_sort_sparse (Sparse<T> &m, int dim, sortmode mode = UNDEFINED) |
|
|
241 { |
|
|
242 octave_value retval; |
|
|
243 |
|
|
244 octave_idx_type nr = m.rows (); |
|
|
245 octave_idx_type nc = m.columns (); |
|
|
246 |
|
|
247 if (m.length () < 1) |
|
|
248 return Sparse<T> (nr, nc); |
|
|
249 |
|
|
250 if (dim > 0) |
|
|
251 { |
|
|
252 m = m.transpose (); |
|
|
253 nr = m.rows (); |
|
|
254 nc = m.columns (); |
|
|
255 } |
|
|
256 |
|
|
257 octave_sort<T> sort; |
|
|
258 |
|
|
259 if (mode == ASCENDING) |
|
|
260 sort.set_compare (ascending_compare); |
|
|
261 else if (mode == DESCENDING) |
|
|
262 sort.set_compare (descending_compare); |
|
|
263 |
|
|
264 T *v = m.data (); |
|
|
265 octave_idx_type *cidx = m.cidx (); |
|
|
266 octave_idx_type *ridx = m.ridx (); |
|
|
267 |
|
|
268 for (octave_idx_type j = 0; j < nc; j++) |
|
|
269 { |
|
|
270 octave_idx_type ns = cidx [j + 1] - cidx [j]; |
|
|
271 sort.sort (v, ns); |
|
|
272 |
|
|
273 octave_idx_type i; |
|
|
274 if (mode == ASCENDING) |
|
|
275 { |
|
|
276 for (i = 0; i < ns; i++) |
|
|
277 if (ascending_compare (static_cast<T> (0), v [i])) |
|
|
278 break; |
|
|
279 } |
|
|
280 else |
|
|
281 { |
|
|
282 for (i = 0; i < ns; i++) |
|
|
283 if (descending_compare (static_cast<T> (0), v [i])) |
|
|
284 break; |
|
|
285 } |
|
|
286 for (octave_idx_type k = 0; k < i; k++) |
|
|
287 ridx [k] = k; |
|
|
288 for (octave_idx_type k = i; k < ns; k++) |
|
|
289 ridx [k] = k - ns + nr; |
|
|
290 |
|
|
291 v += ns; |
|
|
292 ridx += ns; |
|
|
293 } |
|
|
294 |
|
|
295 if (dim > 0) |
|
|
296 m = m.transpose (); |
|
|
297 |
|
|
298 retval = m; |
|
|
299 |
|
|
300 return retval; |
|
|
301 } |
|
|
302 |
|
|
303 template <class T> |
|
|
304 static octave_value_list |
|
|
305 mx_sort_sparse_indexed (Sparse<T> &m, int dim, sortmode mode = UNDEFINED) |
|
|
306 { |
|
|
307 octave_value_list retval; |
|
|
308 |
|
|
309 octave_idx_type nr = m.rows (); |
|
|
310 octave_idx_type nc = m.columns (); |
|
|
311 |
|
|
312 if (m.length () < 1) |
|
|
313 { |
|
|
314 retval (1) = NDArray (dim_vector (nr, nc)); |
|
|
315 retval (0) = octave_value (SparseMatrix (nr, nc)); |
|
|
316 return retval; |
|
|
317 } |
|
|
318 |
|
|
319 if (dim > 0) |
|
|
320 { |
|
|
321 m = m.transpose (); |
|
|
322 nr = m.rows (); |
|
|
323 nc = m.columns (); |
|
|
324 } |
|
|
325 |
|
|
326 octave_sort<vec_index<T> *> indexed_sort; |
|
|
327 |
|
|
328 if (mode == ASCENDING) |
|
|
329 indexed_sort.set_compare (ascending_compare); |
|
|
330 else if (mode == DESCENDING) |
|
|
331 indexed_sort.set_compare (descending_compare); |
|
|
332 |
|
|
333 T *v = m.data (); |
|
|
334 octave_idx_type *cidx = m.cidx (); |
|
|
335 octave_idx_type *ridx = m.ridx (); |
|
|
336 |
|
|
337 OCTAVE_LOCAL_BUFFER (vec_index<T> *, vi, nr); |
|
|
338 OCTAVE_LOCAL_BUFFER (vec_index<T>, vix, nr); |
|
|
339 |
|
|
340 for (octave_idx_type i = 0; i < nr; i++) |
|
|
341 vi[i] = &vix[i]; |
|
|
342 |
|
|
343 Matrix idx (nr, nc); |
|
|
344 |
|
|
345 for (octave_idx_type j = 0; j < nc; j++) |
|
|
346 { |
|
|
347 octave_idx_type ns = cidx [j + 1] - cidx [j]; |
|
|
348 octave_idx_type offset = j * nr; |
|
|
349 |
|
|
350 if (ns == 0) |
|
|
351 { |
|
|
352 for (octave_idx_type k = 0; k < nr; k++) |
|
|
353 idx (offset + k) = k + 1; |
|
|
354 } |
|
|
355 else |
|
|
356 { |
|
|
357 for (octave_idx_type i = 0; i < ns; i++) |
|
|
358 { |
|
|
359 vi[i]->vec = v[i]; |
|
|
360 vi[i]->indx = ridx[i] + 1; |
|
|
361 } |
|
|
362 |
|
|
363 indexed_sort.sort (vi, ns); |
|
|
364 |
|
|
365 octave_idx_type i; |
|
|
366 if (mode == ASCENDING) |
|
|
367 { |
|
|
368 for (i = 0; i < ns; i++) |
|
|
369 if (ascending_compare (static_cast<T> (0), vi [i] -> vec)) |
|
|
370 break; |
|
|
371 } |
|
|
372 else |
|
|
373 { |
|
|
374 for (i = 0; i < ns; i++) |
|
|
375 if (descending_compare (static_cast<T> (0), vi [i] -> vec)) |
|
|
376 break; |
|
|
377 } |
|
|
378 |
|
|
379 octave_idx_type ii = 0; |
|
|
380 octave_idx_type jj = i; |
|
|
381 for (octave_idx_type k = 0; k < nr; k++) |
|
|
382 { |
|
|
383 if (ii < ns && ridx[ii] == k) |
|
|
384 ii++; |
|
|
385 else |
|
|
386 idx (offset + jj++) = k + 1; |
|
|
387 } |
|
|
388 |
|
|
389 for (octave_idx_type k = 0; k < i; k++) |
|
|
390 { |
|
|
391 v [k] = vi [k] -> vec; |
|
|
392 idx (k + offset) = vi [k] -> indx; |
|
|
393 ridx [k] = k; |
|
|
394 } |
|
|
395 |
|
|
396 for (octave_idx_type k = i; k < ns; k++) |
|
|
397 { |
|
|
398 v [k] = vi [k] -> vec; |
|
|
399 idx (k - ns + nr + offset) = vi [k] -> indx; |
|
|
400 ridx [k] = k - ns + nr; |
|
|
401 } |
|
|
402 |
|
|
403 v += ns; |
|
|
404 ridx += ns; |
|
|
405 } |
|
|
406 } |
|
|
407 |
|
|
408 if (dim > 0) |
|
|
409 { |
|
|
410 m = m.transpose (); |
|
|
411 idx = idx.transpose (); |
|
|
412 } |
|
|
413 |
|
|
414 retval (1) = idx; |
|
|
415 retval(0) = octave_value (m); |
|
|
416 |
|
|
417 return retval; |
|
|
418 } |
|
|
419 |
|
4853
|
420 // If we have IEEE 754 data format, then we can use the trick of |
|
|
421 // casting doubles as unsigned eight byte integers, and with a little |
|
|
422 // bit of magic we can automatically sort the NaN's correctly. |
|
2928
|
423 |
|
5828
|
424 #if defined (HAVE_IEEE754_DATA_FORMAT) |
|
4850
|
425 |
|
5828
|
426 static inline uint64_t |
|
|
427 FloatFlip (uint64_t f) |
|
2928
|
428 { |
|
5828
|
429 uint64_t mask |
|
|
430 = -static_cast<int64_t>(f >> 63) | 0x8000000000000000ULL; |
|
4999
|
431 |
|
4850
|
432 return f ^ mask; |
|
|
433 } |
|
2928
|
434 |
|
5828
|
435 static inline uint64_t |
|
|
436 IFloatFlip (uint64_t f) |
|
4850
|
437 { |
|
5828
|
438 uint64_t mask = ((f >> 63) - 1) | 0x8000000000000000ULL; |
|
4999
|
439 |
|
4850
|
440 return f ^ mask; |
|
|
441 } |
|
2928
|
442 |
|
5009
|
443 template <> |
|
4996
|
444 bool |
|
5828
|
445 ascending_compare (uint64_t a, |
|
|
446 uint64_t b) |
|
4850
|
447 { |
|
4996
|
448 return (a < b); |
|
|
449 } |
|
2928
|
450 |
|
5009
|
451 template <> |
|
4850
|
452 bool |
|
5828
|
453 ascending_compare (vec_index<uint64_t> *a, |
|
|
454 vec_index<uint64_t> *b) |
|
4850
|
455 { |
|
|
456 return (a->vec < b->vec); |
|
2928
|
457 } |
|
|
458 |
|
5009
|
459 template <> |
|
4996
|
460 bool |
|
5828
|
461 descending_compare (uint64_t a, |
|
|
462 uint64_t b) |
|
4850
|
463 { |
|
4996
|
464 return (a > b); |
|
4850
|
465 } |
|
2928
|
466 |
|
5009
|
467 template <> |
|
4850
|
468 bool |
|
5828
|
469 descending_compare (vec_index<uint64_t> *a, |
|
|
470 vec_index<uint64_t> *b) |
|
4850
|
471 { |
|
4996
|
472 return (a->vec > b->vec); |
|
4850
|
473 } |
|
|
474 |
|
5828
|
475 template class octave_sort<uint64_t>; |
|
|
476 template class vec_index<uint64_t>; |
|
|
477 template class octave_sort<vec_index<uint64_t> *>; |
|
2928
|
478 |
|
4996
|
479 template <> |
|
5275
|
480 octave_value |
|
4996
|
481 mx_sort (ArrayN<double> &m, int dim, sortmode mode) |
|
2928
|
482 { |
|
4998
|
483 octave_value retval; |
|
2928
|
484 |
|
5366
|
485 dim_vector dv = m.dims (); |
|
|
486 |
|
4850
|
487 if (m.length () < 1) |
|
5366
|
488 return ArrayN<double> (dv); |
|
4850
|
489 |
|
5275
|
490 octave_idx_type ns = dv(dim); |
|
|
491 octave_idx_type iter = dv.numel () / ns; |
|
|
492 octave_idx_type stride = 1; |
|
|
493 for (int i = 0; i < dim; i++) |
|
4850
|
494 stride *= dv(i); |
|
|
495 |
|
|
496 double *v = m.fortran_vec (); |
|
|
497 |
|
5828
|
498 uint64_t *p = reinterpret_cast<uint64_t *> (v); |
|
4850
|
499 |
|
5828
|
500 octave_sort<uint64_t> sort; |
|
4996
|
501 |
|
|
502 if (mode == ASCENDING) |
|
|
503 sort.set_compare (ascending_compare); |
|
|
504 else if (mode == DESCENDING) |
|
|
505 sort.set_compare (descending_compare); |
|
|
506 |
|
|
507 if (stride == 1) |
|
4850
|
508 { |
|
5275
|
509 for (octave_idx_type j = 0; j < iter; j++) |
|
4996
|
510 { |
|
|
511 // Flip the data in the vector so that int compares on |
|
|
512 // IEEE754 give the correct ordering. |
|
|
513 |
|
5275
|
514 for (octave_idx_type i = 0; i < ns; i++) |
|
4996
|
515 p[i] = FloatFlip (p[i]); |
|
|
516 |
|
|
517 sort.sort (p, ns); |
|
|
518 |
|
|
519 // Flip the data out of the vector so that int compares |
|
|
520 // on IEEE754 give the correct ordering. |
|
|
521 |
|
5275
|
522 for (octave_idx_type i = 0; i < ns; i++) |
|
4996
|
523 p[i] = IFloatFlip (p[i]); |
|
4850
|
524 |
|
4996
|
525 // There are two representations of NaN. One will be |
|
|
526 // sorted to the beginning of the vector and the other |
|
5009
|
527 // to the end. If it will be sorted incorrectly, fix |
|
|
528 // things up. |
|
4850
|
529 |
|
5009
|
530 if (lo_ieee_signbit (octave_NaN)) |
|
6484
|
531 { |
|
|
532 if (mode == UNDEFINED || mode == ASCENDING) |
|
|
533 { |
|
|
534 octave_idx_type i = 0; |
|
|
535 double *vtmp = reinterpret_cast<double *> (p); |
|
|
536 while (xisnan (vtmp[i++]) && i < ns); |
|
|
537 for (octave_idx_type l = 0; l < ns - i + 1; l++) |
|
|
538 vtmp[l] = vtmp[l+i-1]; |
|
|
539 for (octave_idx_type l = ns - i + 1; l < ns; l++) |
|
|
540 vtmp[l] = octave_NaN; |
|
|
541 } |
|
|
542 else |
|
|
543 { |
|
|
544 octave_idx_type i = ns; |
|
|
545 double *vtmp = reinterpret_cast<double *> (p); |
|
|
546 while (xisnan (vtmp[--i]) && i > 0); |
|
|
547 for (octave_idx_type l = i; l >= 0; l--) |
|
|
548 vtmp[l-i+ns-1] = vtmp[l]; |
|
|
549 for (octave_idx_type l = 0; l < ns - i - 1; l++) |
|
|
550 vtmp[l] = octave_NaN; |
|
|
551 } |
|
|
552 } |
|
4996
|
553 |
|
|
554 p += ns; |
|
|
555 } |
|
|
556 } |
|
|
557 else |
|
|
558 { |
|
5828
|
559 OCTAVE_LOCAL_BUFFER (uint64_t, vi, ns); |
|
4996
|
560 |
|
5275
|
561 for (octave_idx_type j = 0; j < iter; j++) |
|
4850
|
562 { |
|
5275
|
563 octave_idx_type offset = j; |
|
|
564 octave_idx_type offset2 = 0; |
|
4850
|
565 while (offset >= stride) |
|
|
566 { |
|
|
567 offset -= stride; |
|
|
568 offset2++; |
|
|
569 } |
|
|
570 offset += offset2 * stride * ns; |
|
2928
|
571 |
|
4853
|
572 // Flip the data in the vector so that int compares on |
|
|
573 // IEEE754 give the correct ordering. |
|
|
574 |
|
5275
|
575 for (octave_idx_type i = 0; i < ns; i++) |
|
4996
|
576 vi[i] = FloatFlip (p[i*stride + offset]); |
|
4850
|
577 |
|
4996
|
578 sort.sort (vi, ns); |
|
4850
|
579 |
|
4996
|
580 // Flip the data out of the vector so that int compares |
|
|
581 // on IEEE754 give the correct ordering. |
|
4853
|
582 |
|
5275
|
583 for (octave_idx_type i = 0; i < ns; i++) |
|
4996
|
584 p[i*stride + offset] = IFloatFlip (vi[i]); |
|
|
585 |
|
|
586 // There are two representations of NaN. One will be |
|
|
587 // sorted to the beginning of the vector and the other |
|
|
588 // to the end. If it will be sorted to the beginning, |
|
|
589 // fix things up. |
|
2928
|
590 |
|
5009
|
591 if (lo_ieee_signbit (octave_NaN)) |
|
6484
|
592 { |
|
|
593 if (mode == UNDEFINED || mode == ASCENDING) |
|
|
594 { |
|
|
595 octave_idx_type i = 0; |
|
|
596 while (xisnan (v[i++*stride + offset]) && i < ns); |
|
|
597 for (octave_idx_type l = 0; l < ns - i + 1; l++) |
|
|
598 v[l*stride + offset] = v[(l+i-1)*stride + offset]; |
|
|
599 for (octave_idx_type l = ns - i + 1; l < ns; l++) |
|
|
600 v[l*stride + offset] = octave_NaN; |
|
|
601 } |
|
|
602 else |
|
|
603 { |
|
|
604 octave_idx_type i = ns; |
|
|
605 while (xisnan (v[--i*stride + offset]) && i > 0); |
|
|
606 for (octave_idx_type l = i; l >= 0; l--) |
|
|
607 v[(l-i+ns-1)*stride + offset] = v[l*stride + offset]; |
|
|
608 for (octave_idx_type l = 0; l < ns - i - 1; l++) |
|
|
609 v[l*stride + offset] = octave_NaN; |
|
|
610 } |
|
|
611 } |
|
2928
|
612 } |
|
|
613 } |
|
|
614 |
|
4998
|
615 retval = m; |
|
|
616 |
|
2928
|
617 return retval; |
|
|
618 } |
|
|
619 |
|
5275
|
620 // Should other overloaded functions have their static keywords removed? |
|
4996
|
621 template <> |
|
5275
|
622 octave_value_list |
|
4996
|
623 mx_sort_indexed (ArrayN<double> &m, int dim, sortmode mode) |
|
2928
|
624 { |
|
|
625 octave_value_list retval; |
|
|
626 |
|
5366
|
627 dim_vector dv = m.dims (); |
|
|
628 |
|
4850
|
629 if (m.length () < 1) |
|
5360
|
630 { |
|
5419
|
631 retval(1) = NDArray (dv); |
|
|
632 retval(0) = ArrayN<double> (dv); |
|
5360
|
633 return retval; |
|
|
634 } |
|
4850
|
635 |
|
5275
|
636 octave_idx_type ns = dv(dim); |
|
|
637 octave_idx_type iter = dv.numel () / ns; |
|
|
638 octave_idx_type stride = 1; |
|
|
639 for (int i = 0; i < dim; i++) |
|
4850
|
640 stride *= dv(i); |
|
2928
|
641 |
|
4996
|
642 double *v = m.fortran_vec (); |
|
4850
|
643 |
|
5828
|
644 uint64_t *p = reinterpret_cast<uint64_t *> (v); |
|
4996
|
645 |
|
5828
|
646 octave_sort<vec_index<uint64_t> *> indexed_sort; |
|
2928
|
647 |
|
4996
|
648 if (mode == ASCENDING) |
|
|
649 indexed_sort.set_compare (ascending_compare); |
|
|
650 else if (mode == DESCENDING) |
|
|
651 indexed_sort.set_compare (descending_compare); |
|
4850
|
652 |
|
5828
|
653 OCTAVE_LOCAL_BUFFER (vec_index<uint64_t> *, vi, ns); |
|
|
654 OCTAVE_LOCAL_BUFFER (vec_index<uint64_t>, vix, ns); |
|
4996
|
655 |
|
5275
|
656 for (octave_idx_type i = 0; i < ns; i++) |
|
4850
|
657 vi[i] = &vix[i]; |
|
2928
|
658 |
|
4850
|
659 NDArray idx (dv); |
|
4996
|
660 |
|
5275
|
661 for (octave_idx_type j = 0; j < iter; j++) |
|
2928
|
662 { |
|
5275
|
663 octave_idx_type offset = j; |
|
|
664 octave_idx_type offset2 = 0; |
|
4996
|
665 while (offset >= stride) |
|
2928
|
666 { |
|
4996
|
667 offset -= stride; |
|
|
668 offset2++; |
|
|
669 } |
|
|
670 offset += offset2 * stride * ns; |
|
2928
|
671 |
|
4996
|
672 // Flip the data in the vector so that int compares on |
|
|
673 // IEEE754 give the correct ordering. |
|
|
674 |
|
5275
|
675 for (octave_idx_type i = 0; i < ns; i++) |
|
4996
|
676 { |
|
|
677 vi[i]->vec = FloatFlip (p[i*stride + offset]); |
|
|
678 vi[i]->indx = i + 1; |
|
4850
|
679 } |
|
4996
|
680 |
|
|
681 indexed_sort.sort (vi, ns); |
|
|
682 |
|
|
683 // Flip the data out of the vector so that int compares on |
|
|
684 // IEEE754 give the correct ordering |
|
|
685 |
|
5275
|
686 for (octave_idx_type i = 0; i < ns; i++) |
|
4850
|
687 { |
|
4996
|
688 p[i*stride + offset] = IFloatFlip (vi[i]->vec); |
|
|
689 idx(i*stride + offset) = vi[i]->indx; |
|
|
690 } |
|
|
691 |
|
|
692 // There are two representations of NaN. One will be sorted |
|
|
693 // to the beginning of the vector and the other to the end. |
|
|
694 // If it will be sorted to the beginning, fix things up. |
|
2928
|
695 |
|
5009
|
696 if (lo_ieee_signbit (octave_NaN)) |
|
6484
|
697 { |
|
|
698 if (mode == UNDEFINED || mode == ASCENDING) |
|
|
699 { |
|
|
700 octave_idx_type i = 0; |
|
|
701 while (xisnan (v[i++*stride+offset]) && i < ns); |
|
|
702 OCTAVE_LOCAL_BUFFER (double, itmp, i - 1); |
|
|
703 for (octave_idx_type l = 0; l < i -1; l++) |
|
|
704 itmp[l] = idx(l*stride + offset); |
|
|
705 for (octave_idx_type l = 0; l < ns - i + 1; l++) |
|
|
706 { |
|
|
707 v[l*stride + offset] = v[(l+i-1)*stride + offset]; |
|
|
708 idx(l*stride + offset) = idx((l+i-1)*stride + offset); |
|
|
709 } |
|
|
710 for (octave_idx_type k = 0, l = ns - i + 1; l < ns; l++, k++) |
|
|
711 { |
|
|
712 v[l*stride + offset] = octave_NaN; |
|
|
713 idx(l*stride + offset) = itmp[k]; |
|
|
714 } |
|
|
715 } |
|
|
716 else |
|
|
717 { |
|
|
718 octave_idx_type i = ns; |
|
|
719 while (xisnan (v[--i*stride+offset]) && i > 0); |
|
|
720 OCTAVE_LOCAL_BUFFER (double, itmp, ns - i - 1); |
|
|
721 for (octave_idx_type l = 0; l < ns - i -1; l++) |
|
|
722 itmp[l] = idx((l+i+1)*stride + offset); |
|
|
723 for (octave_idx_type l = i; l >= 0; l--) |
|
|
724 { |
|
|
725 v[(l-i+ns-1)*stride + offset] = v[l*stride + offset]; |
|
|
726 idx((l-i+ns-1)*stride + offset) = idx(l*stride + offset); |
|
|
727 } |
|
|
728 for (octave_idx_type k = 0, l = 0; l < ns - i - 1; l++, k++) |
|
|
729 { |
|
|
730 v[l*stride + offset] = octave_NaN; |
|
|
731 idx(l*stride + offset) = itmp[k]; |
|
|
732 } |
|
|
733 } |
|
|
734 } |
|
2928
|
735 } |
|
|
736 |
|
4997
|
737 retval(1) = idx; |
|
|
738 retval(0) = m; |
|
4998
|
739 |
|
2928
|
740 return retval; |
|
|
741 } |
|
|
742 |
|
4996
|
743 #else |
|
|
744 |
|
5009
|
745 template <> |
|
4996
|
746 bool |
|
|
747 ascending_compare (double a, double b) |
|
4991
|
748 { |
|
4997
|
749 return (xisnan (b) || (a < b)); |
|
4996
|
750 } |
|
|
751 |
|
5009
|
752 template <> |
|
4996
|
753 bool |
|
|
754 ascending_compare (vec_index<double> *a, vec_index<double> *b) |
|
|
755 { |
|
4997
|
756 return (xisnan (b->vec) || (a->vec < b->vec)); |
|
4996
|
757 } |
|
|
758 |
|
5009
|
759 template <> |
|
4996
|
760 bool |
|
|
761 descending_compare (double a, double b) |
|
|
762 { |
|
4997
|
763 return (xisnan (a) || (a > b)); |
|
4996
|
764 } |
|
4991
|
765 |
|
5009
|
766 template <> |
|
4991
|
767 bool |
|
4996
|
768 descending_compare (vec_index<double> *a, vec_index<double> *b) |
|
|
769 { |
|
4997
|
770 return (xisnan (a->vec) || (a->vec > b->vec)); |
|
4996
|
771 } |
|
|
772 |
|
|
773 template class octave_sort<double>; |
|
|
774 template class vec_index<double>; |
|
|
775 template class octave_sort<vec_index<double> *>; |
|
|
776 |
|
|
777 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
778 static octave_value_list |
|
|
779 mx_sort (ArrayN<double> &m, int dim, sortmode mode); |
|
|
780 |
|
|
781 static octave_value_list |
|
|
782 mx_sort_indexed (ArrayN<double> &m, int dim, sortmode mode); |
|
|
783 #endif |
|
|
784 #endif |
|
|
785 |
|
6863
|
786 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
787 static octave_value_list |
|
|
788 mx_sort_sparse (Sparse<double> &m, int dim, sortmode mode); |
|
|
789 |
|
|
790 static octave_value_list |
|
|
791 mx_sort_sparse_indexed (Sparse<double> &m, int dim, sortmode mode); |
|
|
792 #endif |
|
|
793 |
|
4996
|
794 // std::abs(Inf) returns NaN!! |
|
|
795 static inline double |
|
|
796 xabs (const Complex& x) |
|
|
797 { |
|
|
798 return (xisinf (x.real ()) || xisinf (x.imag ())) ? octave_Inf : abs (x); |
|
|
799 } |
|
|
800 |
|
5009
|
801 template <> |
|
4996
|
802 bool |
|
6863
|
803 ascending_compare (Complex a, Complex b) |
|
|
804 { |
|
|
805 return (xisnan (b) || (xabs (a) < xabs (b)) || ((xabs (a) == xabs (b)) |
|
|
806 && (arg (a) < arg (b)))); |
|
|
807 } |
|
|
808 |
|
|
809 bool |
|
|
810 operator < (const Complex a, const Complex b) |
|
|
811 { |
|
|
812 return (xisnan (b) || (xabs (a) < xabs (b)) || ((xabs (a) == xabs (b)) |
|
|
813 && (arg (a) < arg (b)))); |
|
|
814 } |
|
|
815 |
|
|
816 template <> |
|
|
817 bool |
|
|
818 descending_compare (Complex a, Complex b) |
|
|
819 { |
|
|
820 return (xisnan (a) || (xabs (a) > xabs (b)) || ((xabs (a) == xabs (b)) |
|
|
821 && (arg (a) > arg (b)))); |
|
|
822 } |
|
|
823 |
|
|
824 bool |
|
|
825 operator > (const Complex a, const Complex b) |
|
|
826 { |
|
|
827 return (xisnan (a) || (xabs (a) > xabs (b)) || ((xabs (a) == xabs (b)) |
|
|
828 && (arg (a) > arg (b)))); |
|
|
829 } |
|
|
830 |
|
|
831 template <> |
|
|
832 bool |
|
4996
|
833 ascending_compare (vec_index<Complex> *a, vec_index<Complex> *b) |
|
|
834 { |
|
4997
|
835 return (xisnan (b->vec) |
|
|
836 || (xabs (a->vec) < xabs (b->vec)) |
|
|
837 || ((xabs (a->vec) == xabs (b->vec)) |
|
|
838 && (arg (a->vec) < arg (b->vec)))); |
|
4996
|
839 } |
|
|
840 |
|
5009
|
841 template <> |
|
4996
|
842 bool |
|
|
843 descending_compare (vec_index<Complex> *a, vec_index<Complex> *b) |
|
|
844 { |
|
4997
|
845 return (xisnan (a->vec) |
|
|
846 || (xabs (a->vec) > xabs (b->vec)) |
|
|
847 || ((xabs (a->vec) == xabs (b->vec)) |
|
|
848 && (arg (a->vec) > arg (b->vec)))); |
|
4996
|
849 } |
|
|
850 |
|
6863
|
851 template class octave_sort<Complex>; |
|
4996
|
852 template class vec_index<Complex>; |
|
|
853 template class octave_sort<vec_index<Complex> *>; |
|
|
854 |
|
|
855 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
856 static octave_value_list |
|
6863
|
857 mx_sort (ArrayN<Complex> &m, int dim, sortmode mode); |
|
|
858 |
|
|
859 static octave_value_list |
|
4996
|
860 mx_sort_indexed (ArrayN<Complex> &m, int dim, sortmode mode); |
|
6863
|
861 |
|
|
862 static octave_value_list |
|
|
863 mx_sort_sparse (Sparse<Complex> &m, int dim, sortmode mode); |
|
|
864 |
|
|
865 static octave_value_list |
|
|
866 mx_sort_sparse_indexed (Sparse<Complex> &m, int dim, sortmode mode); |
|
4996
|
867 #endif |
|
|
868 |
|
4991
|
869 template class octave_sort<char>; |
|
4996
|
870 template class vec_index<char>; |
|
|
871 template class octave_sort<vec_index<char> *>; |
|
|
872 |
|
|
873 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
5009
|
874 bool |
|
|
875 ascending_compare (char a, char b); |
|
|
876 |
|
|
877 bool |
|
|
878 ascending_compare (vec_index<char> *a, vec_index<char> *b); |
|
|
879 |
|
|
880 bool |
|
|
881 descending_compare (char a, char b); |
|
|
882 |
|
|
883 bool |
|
|
884 descending_compare (vec_index<char> *a, vec_index<char> *b); |
|
|
885 |
|
4996
|
886 static octave_value_list |
|
|
887 mx_sort (ArrayN<char> &m, int dim, sortmode mode); |
|
4991
|
888 |
|
|
889 static octave_value_list |
|
4996
|
890 mx_sort_indexed (ArrayN<char> &m, int dim, sortmode mode); |
|
|
891 #endif |
|
4991
|
892 |
|
7064
|
893 template class octave_sort<octave_int8>; |
|
|
894 template class vec_index<octave_int8>; |
|
|
895 template class octave_sort<vec_index<octave_int8> *>; |
|
|
896 |
|
|
897 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
898 bool |
|
|
899 ascending_compare (octave_int8 a, octave_int8 b); |
|
|
900 |
|
|
901 bool |
|
|
902 ascending_compare (vec_index<octave_int8> *a, vec_index<octave_int8> *b); |
|
|
903 |
|
|
904 bool |
|
|
905 descending_compare (octave_int8 a, octave_int8 b); |
|
|
906 |
|
|
907 bool |
|
|
908 descending_compare (vec_index<octave_int8> *a, vec_index<octave_int8> *b); |
|
|
909 |
|
|
910 static octave_value_list |
|
|
911 mx_sort (ArrayN<octave_int8> &m, int dim, sortmode mode); |
|
|
912 |
|
|
913 static octave_value_list |
|
|
914 mx_sort_indexed (ArrayN<octave_int8> &m, int dim, sortmode mode); |
|
|
915 #endif |
|
|
916 |
|
|
917 template class octave_sort<octave_uint8>; |
|
|
918 template class vec_index<octave_uint8>; |
|
|
919 template class octave_sort<vec_index<octave_uint8> *>; |
|
|
920 |
|
|
921 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
922 bool |
|
|
923 ascending_compare (octave_uint8 a, octave_uint8 b); |
|
|
924 |
|
|
925 bool |
|
|
926 ascending_compare (vec_index<octave_uint8> *a, vec_index<octave_uint8> *b); |
|
|
927 |
|
|
928 bool |
|
|
929 descending_compare (octave_uint8 a, octave_uint8 b); |
|
|
930 |
|
|
931 bool |
|
|
932 descending_compare (vec_index<octave_uint8> *a, vec_index<octave_uint8> *b); |
|
|
933 |
|
|
934 static octave_value_list |
|
|
935 mx_sort (ArrayN<octave_uint8> &m, int dim, sortmode mode); |
|
|
936 |
|
|
937 static octave_value_list |
|
|
938 mx_sort_indexed (ArrayN<octave_uint8> &m, int dim, sortmode mode); |
|
|
939 #endif |
|
|
940 |
|
|
941 template class octave_sort<octave_int16>; |
|
|
942 template class vec_index<octave_int16>; |
|
|
943 template class octave_sort<vec_index<octave_int16> *>; |
|
|
944 |
|
|
945 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
946 bool |
|
|
947 ascending_compare (octave_int16 a, octave_int16 b); |
|
|
948 |
|
|
949 bool |
|
|
950 ascending_compare (vec_index<octave_int16> *a, vec_index<octave_int16> *b); |
|
|
951 |
|
|
952 bool |
|
|
953 descending_compare (octave_int16 a, octave_int16 b); |
|
|
954 |
|
|
955 bool |
|
|
956 descending_compare (vec_index<octave_int16> *a, vec_index<octave_int16> *b); |
|
|
957 |
|
|
958 static octave_value_list |
|
|
959 mx_sort (ArrayN<octave_int16> &m, int dim, sortmode mode); |
|
|
960 |
|
|
961 static octave_value_list |
|
|
962 mx_sort_indexed (ArrayN<octave_int16> &m, int dim, sortmode mode); |
|
|
963 #endif |
|
|
964 |
|
|
965 template class octave_sort<octave_uint16>; |
|
|
966 template class vec_index<octave_uint16>; |
|
|
967 template class octave_sort<vec_index<octave_uint16> *>; |
|
|
968 |
|
|
969 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
970 bool |
|
|
971 ascending_compare (octave_uint16 a, octave_uint16 b); |
|
|
972 |
|
|
973 bool |
|
|
974 ascending_compare (vec_index<octave_uint16> *a, vec_index<octave_uint16> *b); |
|
|
975 |
|
|
976 bool |
|
|
977 descending_compare (octave_uint16 a, octave_uint16 b); |
|
|
978 |
|
|
979 bool |
|
|
980 descending_compare (vec_index<octave_uint16> *a, vec_index<octave_uint16> *b); |
|
|
981 |
|
|
982 static octave_value_list |
|
|
983 mx_sort (ArrayN<octave_uint16> &m, int dim, sortmode mode); |
|
|
984 |
|
|
985 static octave_value_list |
|
|
986 mx_sort_indexed (ArrayN<octave_uint16> &m, int dim, sortmode mode); |
|
|
987 #endif |
|
|
988 |
|
|
989 template class octave_sort<octave_int32>; |
|
|
990 template class vec_index<octave_int32>; |
|
|
991 template class octave_sort<vec_index<octave_int32> *>; |
|
|
992 |
|
|
993 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
994 bool |
|
|
995 ascending_compare (octave_int32 a, octave_int32 b); |
|
|
996 |
|
|
997 bool |
|
|
998 ascending_compare (vec_index<octave_int32> *a, vec_index<octave_int32> *b); |
|
|
999 |
|
|
1000 bool |
|
|
1001 descending_compare (octave_int32 a, octave_int32 b); |
|
|
1002 |
|
|
1003 bool |
|
|
1004 descending_compare (vec_index<octave_int32> *a, vec_index<octave_int32> *b); |
|
|
1005 |
|
|
1006 static octave_value_list |
|
|
1007 mx_sort (ArrayN<octave_int32> &m, int dim, sortmode mode); |
|
|
1008 |
|
|
1009 static octave_value_list |
|
|
1010 mx_sort_indexed (ArrayN<octave_int32> &m, int dim, sortmode mode); |
|
|
1011 #endif |
|
|
1012 |
|
|
1013 template class octave_sort<octave_uint32>; |
|
|
1014 template class vec_index<octave_uint32>; |
|
|
1015 template class octave_sort<vec_index<octave_uint32> *>; |
|
|
1016 |
|
|
1017 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
1018 bool |
|
|
1019 ascending_compare (octave_uint32 a, octave_uint32 b); |
|
|
1020 |
|
|
1021 bool |
|
|
1022 ascending_compare (vec_index<octave_uint32> *a, vec_index<octave_uint32> *b); |
|
|
1023 |
|
|
1024 bool |
|
|
1025 descending_compare (octave_uint32 a, octave_uint32 b); |
|
|
1026 |
|
|
1027 bool |
|
|
1028 descending_compare (vec_index<octave_uint32> *a, vec_index<octave_uint32> *b); |
|
|
1029 |
|
|
1030 static octave_value_list |
|
|
1031 mx_sort (ArrayN<octave_uint32> &m, int dim, sortmode mode); |
|
|
1032 |
|
|
1033 static octave_value_list |
|
|
1034 mx_sort_indexed (ArrayN<octave_uint32> &m, int dim, sortmode mode); |
|
|
1035 #endif |
|
|
1036 |
|
|
1037 template class octave_sort<octave_int64>; |
|
|
1038 template class vec_index<octave_int64>; |
|
|
1039 template class octave_sort<vec_index<octave_int64> *>; |
|
|
1040 |
|
|
1041 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
1042 bool |
|
|
1043 ascending_compare (octave_int64 a, octave_int64 b); |
|
|
1044 |
|
|
1045 bool |
|
|
1046 ascending_compare (vec_index<octave_int64> *a, vec_index<octave_int64> *b); |
|
|
1047 |
|
|
1048 bool |
|
|
1049 descending_compare (octave_int64 a, octave_int64 b); |
|
|
1050 |
|
|
1051 bool |
|
|
1052 descending_compare (vec_index<octave_int64> *a, vec_index<octave_int64> *b); |
|
|
1053 |
|
|
1054 static octave_value_list |
|
|
1055 mx_sort (ArrayN<octave_int64> &m, int dim, sortmode mode); |
|
|
1056 |
|
|
1057 static octave_value_list |
|
|
1058 mx_sort_indexed (ArrayN<octave_int64> &m, int dim, sortmode mode); |
|
|
1059 #endif |
|
|
1060 |
|
|
1061 template class octave_sort<octave_uint64>; |
|
|
1062 template class vec_index<octave_uint64>; |
|
|
1063 template class octave_sort<vec_index<octave_uint64> *>; |
|
|
1064 |
|
|
1065 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
1066 bool |
|
|
1067 ascending_compare (octave_uint64 a, octave_uint64 b); |
|
|
1068 |
|
|
1069 bool |
|
|
1070 ascending_compare (vec_index<octave_uint64> *a, vec_index<octave_uint64> *b); |
|
|
1071 |
|
|
1072 bool |
|
|
1073 descending_compare (octave_uint64 a, octave_uint64 b); |
|
|
1074 |
|
|
1075 bool |
|
|
1076 descending_compare (vec_index<octave_uint64> *a, vec_index<octave_uint64> *b); |
|
|
1077 |
|
|
1078 static octave_value_list |
|
|
1079 mx_sort (ArrayN<octave_uint64> &m, int dim, sortmode mode); |
|
|
1080 |
|
|
1081 static octave_value_list |
|
|
1082 mx_sort_indexed (ArrayN<octave_uint64> &m, int dim, sortmode mode); |
|
|
1083 #endif |
|
|
1084 |
|
5009
|
1085 template <> |
|
4996
|
1086 bool |
|
|
1087 ascending_compare (vec_index<octave_value> *a, vec_index<octave_value> *b) |
|
|
1088 { |
|
|
1089 return (a->vec.string_value () < b->vec.string_value ()); |
|
|
1090 } |
|
4991
|
1091 |
|
5009
|
1092 template <> |
|
4996
|
1093 bool |
|
|
1094 descending_compare (vec_index<octave_value> *a, vec_index<octave_value> *b) |
|
|
1095 { |
|
|
1096 return (a->vec.string_value () > b->vec.string_value ()); |
|
|
1097 } |
|
4991
|
1098 |
|
4996
|
1099 template class vec_index<octave_value>; |
|
|
1100 template class octave_sort<vec_index<octave_value> *>; |
|
4991
|
1101 |
|
4996
|
1102 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
1103 static octave_value_list |
|
|
1104 mx_sort_indexed (ArrayN<octave_value> &m, int dim, sortmode mode); |
|
|
1105 #endif |
|
4991
|
1106 |
|
2928
|
1107 DEFUN_DLD (sort, args, nargout, |
|
3369
|
1108 "-*- texinfo -*-\n\ |
|
|
1109 @deftypefn {Loadable Function} {[@var{s}, @var{i}] =} sort (@var{x})\n\ |
|
4850
|
1110 @deftypefnx {Loadable Function} {[@var{s}, @var{i}] =} sort (@var{x}, @var{dim})\n\ |
|
5000
|
1111 @deftypefnx {Loadable Function} {[@var{s}, @var{i}] =} sort (@var{x}, @var{mode})\n\ |
|
|
1112 @deftypefnx {Loadable Function} {[@var{s}, @var{i}] =} sort (@var{x}, @var{dim}, @var{mode})\n\ |
|
5499
|
1113 Return a copy of @var{x} with the elements arranged in increasing\n\ |
|
|
1114 order. For matrices, @code{sort} orders the elements in each column.\n\ |
|
3369
|
1115 \n\ |
|
|
1116 For example,\n\ |
|
|
1117 \n\ |
|
|
1118 @example\n\ |
|
|
1119 @group\n\ |
|
|
1120 sort ([1, 2; 2, 3; 3, 1])\n\ |
|
|
1121 @result{} 1 1\n\ |
|
|
1122 2 2\n\ |
|
|
1123 3 3\n\ |
|
|
1124 @end group\n\ |
|
|
1125 @end example\n\ |
|
2928
|
1126 \n\ |
|
3369
|
1127 The @code{sort} function may also be used to produce a matrix\n\ |
|
|
1128 containing the original row indices of the elements in the sorted\n\ |
|
|
1129 matrix. For example,\n\ |
|
|
1130 \n\ |
|
|
1131 @example\n\ |
|
|
1132 @group\n\ |
|
|
1133 [s, i] = sort ([1, 2; 2, 3; 3, 1])\n\ |
|
|
1134 @result{} s = 1 1\n\ |
|
|
1135 2 2\n\ |
|
|
1136 3 3\n\ |
|
|
1137 @result{} i = 1 3\n\ |
|
|
1138 2 1\n\ |
|
|
1139 3 2\n\ |
|
|
1140 @end group\n\ |
|
|
1141 @end example\n\ |
|
4850
|
1142 \n\ |
|
|
1143 If the optional argument @var{dim} is given, then the matrix is sorted\n\ |
|
4996
|
1144 along the dimension defined by @var{dim}. The optional argument @code{mode}\n\ |
|
|
1145 defines the order in which the values will be sorted. Valid values of\n\ |
|
|
1146 @code{mode} are `ascend' or `descend'.\n\ |
|
4850
|
1147 \n\ |
|
|
1148 For equal elements, the indices are such that the equal elements are listed\n\ |
|
|
1149 in the order that appeared in the original list.\n\ |
|
|
1150 \n\ |
|
4996
|
1151 The @code{sort} function may also be used to sort strings and cell arrays\n\ |
|
5499
|
1152 of strings, in which case the dictionary order of the strings is used.\n\ |
|
4996
|
1153 \n\ |
|
4850
|
1154 The algorithm used in @code{sort} is optimized for the sorting of partially\n\ |
|
|
1155 ordered lists.\n\ |
|
3369
|
1156 @end deftypefn") |
|
2928
|
1157 { |
|
|
1158 octave_value_list retval; |
|
|
1159 |
|
|
1160 int nargin = args.length (); |
|
4996
|
1161 sortmode smode = ASCENDING; |
|
2928
|
1162 |
|
5001
|
1163 if (nargin < 1 || nargin > 3) |
|
2928
|
1164 { |
|
5823
|
1165 print_usage (); |
|
2928
|
1166 return retval; |
|
|
1167 } |
|
|
1168 |
|
4850
|
1169 bool return_idx = nargout > 1; |
|
2928
|
1170 |
|
|
1171 octave_value arg = args(0); |
|
|
1172 |
|
4850
|
1173 int dim = 0; |
|
4996
|
1174 if (nargin > 1) |
|
|
1175 { |
|
|
1176 if (args(1).is_string ()) |
|
|
1177 { |
|
|
1178 std::string mode = args(1).string_value(); |
|
|
1179 if (mode == "ascend") |
|
|
1180 smode = ASCENDING; |
|
|
1181 else if (mode == "descend") |
|
|
1182 smode = DESCENDING; |
|
|
1183 else |
|
|
1184 { |
|
5000
|
1185 error ("sort: mode must be either \"ascend\" or \"descend\""); |
|
4996
|
1186 return retval; |
|
|
1187 } |
|
|
1188 } |
|
|
1189 else |
|
|
1190 dim = args(1).nint_value () - 1; |
|
|
1191 } |
|
|
1192 |
|
|
1193 if (nargin > 2) |
|
|
1194 { |
|
|
1195 if (args(1).is_string ()) |
|
|
1196 { |
|
5823
|
1197 print_usage (); |
|
4996
|
1198 return retval; |
|
|
1199 } |
|
|
1200 |
|
|
1201 if (! args(2).is_string ()) |
|
|
1202 { |
|
|
1203 error ("sort: mode must be a string"); |
|
|
1204 return retval; |
|
|
1205 } |
|
|
1206 std::string mode = args(2).string_value(); |
|
|
1207 if (mode == "ascend") |
|
|
1208 smode = ASCENDING; |
|
|
1209 else if (mode == "descend") |
|
|
1210 smode = DESCENDING; |
|
|
1211 else |
|
|
1212 { |
|
5000
|
1213 error ("sort: mode must be either \"ascend\" or \"descend\""); |
|
4996
|
1214 return retval; |
|
|
1215 } |
|
|
1216 } |
|
4850
|
1217 |
|
5275
|
1218 dim_vector dv = arg.dims (); |
|
4850
|
1219 if (error_state) |
|
|
1220 { |
|
|
1221 gripe_wrong_type_arg ("sort", arg); |
|
|
1222 return retval; |
|
|
1223 } |
|
4996
|
1224 if (nargin == 1 || args(1).is_string ()) |
|
4850
|
1225 { |
|
|
1226 // Find first non singleton dimension |
|
|
1227 for (int i = 0; i < dv.length (); i++) |
|
|
1228 if (dv(i) > 1) |
|
|
1229 { |
|
|
1230 dim = i; |
|
|
1231 break; |
|
|
1232 } |
|
|
1233 } |
|
|
1234 else |
|
|
1235 { |
|
|
1236 if (dim < 0 || dim > dv.length () - 1) |
|
|
1237 { |
|
|
1238 error ("sort: dim must be a valid dimension"); |
|
|
1239 return retval; |
|
|
1240 } |
|
|
1241 } |
|
|
1242 |
|
7064
|
1243 // FIXME Perhaps sort should be made a method of the octave_value classes |
|
|
1244 // and then the mess of if statements both might be replaced with |
|
|
1245 // retval = arg.sort (dim, smode, return_idx); |
|
|
1246 |
|
2928
|
1247 if (arg.is_real_type ()) |
|
|
1248 { |
|
6863
|
1249 if (arg.is_sparse_type ()) |
|
4996
|
1250 { |
|
6863
|
1251 SparseMatrix m = arg.sparse_matrix_value (); |
|
|
1252 |
|
|
1253 if (! error_state) |
|
4996
|
1254 { |
|
|
1255 if (return_idx) |
|
6863
|
1256 retval = mx_sort_sparse_indexed (m, dim, smode); |
|
4996
|
1257 else |
|
6863
|
1258 retval = mx_sort_sparse (m, dim, smode); |
|
|
1259 } |
|
|
1260 } |
|
7064
|
1261 else if (arg.is_int8_type ()) |
|
|
1262 { |
|
|
1263 int8NDArray m = arg.int8_array_value (); |
|
|
1264 if (! error_state) |
|
|
1265 { |
|
|
1266 if (return_idx) |
|
|
1267 retval = mx_sort_indexed (m, dim, smode); |
|
|
1268 else |
|
|
1269 retval = mx_sort (m, dim, smode); |
|
|
1270 } |
|
|
1271 } |
|
|
1272 else if (arg.is_uint8_type ()) |
|
|
1273 { |
|
|
1274 uint8NDArray m = arg.uint8_array_value (); |
|
|
1275 if (! error_state) |
|
|
1276 { |
|
|
1277 if (return_idx) |
|
|
1278 retval = mx_sort_indexed (m, dim, smode); |
|
|
1279 else |
|
|
1280 retval = mx_sort (m, dim, smode); |
|
|
1281 } |
|
|
1282 } |
|
|
1283 else if (arg.is_int16_type ()) |
|
|
1284 { |
|
|
1285 int16NDArray m = arg.int16_array_value (); |
|
|
1286 if (! error_state) |
|
|
1287 { |
|
|
1288 if (return_idx) |
|
|
1289 retval = mx_sort_indexed (m, dim, smode); |
|
|
1290 else |
|
|
1291 retval = mx_sort (m, dim, smode); |
|
|
1292 } |
|
|
1293 } |
|
|
1294 else if (arg.is_uint16_type ()) |
|
|
1295 { |
|
|
1296 uint16NDArray m = arg.uint16_array_value (); |
|
|
1297 if (! error_state) |
|
|
1298 { |
|
|
1299 if (return_idx) |
|
|
1300 retval = mx_sort_indexed (m, dim, smode); |
|
|
1301 else |
|
|
1302 retval = mx_sort (m, dim, smode); |
|
|
1303 } |
|
|
1304 } |
|
|
1305 else if (arg.is_int32_type ()) |
|
|
1306 { |
|
|
1307 int32NDArray m = arg.int32_array_value (); |
|
|
1308 if (! error_state) |
|
|
1309 { |
|
|
1310 if (return_idx) |
|
|
1311 retval = mx_sort_indexed (m, dim, smode); |
|
|
1312 else |
|
|
1313 retval = mx_sort (m, dim, smode); |
|
|
1314 } |
|
|
1315 } |
|
|
1316 else if (arg.is_uint32_type ()) |
|
|
1317 { |
|
|
1318 uint32NDArray m = arg.uint32_array_value (); |
|
|
1319 if (! error_state) |
|
|
1320 { |
|
|
1321 if (return_idx) |
|
|
1322 retval = mx_sort_indexed (m, dim, smode); |
|
|
1323 else |
|
|
1324 retval = mx_sort (m, dim, smode); |
|
|
1325 } |
|
|
1326 } |
|
|
1327 else if (arg.is_int64_type ()) |
|
|
1328 { |
|
|
1329 int64NDArray m = arg.int64_array_value (); |
|
|
1330 if (! error_state) |
|
|
1331 { |
|
|
1332 if (return_idx) |
|
|
1333 retval = mx_sort_indexed (m, dim, smode); |
|
|
1334 else |
|
|
1335 retval = mx_sort (m, dim, smode); |
|
|
1336 } |
|
|
1337 } |
|
|
1338 else if (arg.is_uint64_type ()) |
|
|
1339 { |
|
|
1340 uint64NDArray m = arg.uint64_array_value (); |
|
|
1341 if (! error_state) |
|
|
1342 { |
|
|
1343 if (return_idx) |
|
|
1344 retval = mx_sort_indexed (m, dim, smode); |
|
|
1345 else |
|
|
1346 retval = mx_sort (m, dim, smode); |
|
|
1347 } |
|
|
1348 } |
|
6863
|
1349 else |
|
|
1350 { |
|
|
1351 NDArray m = arg.array_value (); |
|
|
1352 |
|
|
1353 if (! error_state) |
|
|
1354 { |
|
|
1355 #ifdef HAVE_IEEE754_DATA_FORMAT |
|
|
1356 // As operator > gives the right result, can special case here |
|
|
1357 if (! return_idx && smode == ASCENDING) |
|
|
1358 retval = mx_sort (m, dim); |
|
|
1359 else |
|
|
1360 #endif |
|
|
1361 { |
|
|
1362 if (return_idx) |
|
|
1363 retval = mx_sort_indexed (m, dim, smode); |
|
|
1364 else |
|
|
1365 retval = mx_sort (m, dim, smode); |
|
|
1366 } |
|
4996
|
1367 } |
|
|
1368 } |
|
2928
|
1369 } |
|
|
1370 else if (arg.is_complex_type ()) |
|
|
1371 { |
|
6863
|
1372 if (arg.is_sparse_type ()) |
|
|
1373 { |
|
|
1374 SparseComplexMatrix cm = arg.sparse_complex_matrix_value (); |
|
2928
|
1375 |
|
6863
|
1376 if (! error_state) |
|
|
1377 { |
|
|
1378 if (return_idx) |
|
|
1379 retval = mx_sort_sparse_indexed (cm, dim, smode); |
|
|
1380 else |
|
|
1381 retval = mx_sort_sparse (cm, dim, smode); |
|
|
1382 } |
|
|
1383 } |
|
|
1384 else |
|
|
1385 { |
|
|
1386 ComplexNDArray cm = arg.complex_array_value (); |
|
|
1387 |
|
|
1388 if (! error_state) |
|
|
1389 { |
|
|
1390 // The indexed version seems to be slightly faster |
|
|
1391 retval = mx_sort_indexed (cm, dim, smode); |
|
|
1392 } |
|
|
1393 } |
|
2928
|
1394 } |
|
4991
|
1395 else if (arg.is_string ()) |
|
|
1396 { |
|
|
1397 charNDArray chm = arg.char_array_value (); |
|
|
1398 |
|
|
1399 if (! error_state) |
|
4996
|
1400 { |
|
|
1401 // As operator > gives the right result, can special case here |
|
|
1402 if (! return_idx && smode == ASCENDING) |
|
|
1403 retval = mx_sort (chm, dim); |
|
|
1404 else |
|
|
1405 { |
|
|
1406 if (return_idx) |
|
|
1407 retval = mx_sort_indexed (chm, dim, smode); |
|
|
1408 else |
|
|
1409 retval = mx_sort (chm, dim, smode); |
|
|
1410 } |
|
|
1411 |
|
5775
|
1412 // FIXME It would have been better to call |
|
4996
|
1413 // "octave_value(m, true)" but how can that be done |
|
|
1414 // within the template |
|
|
1415 retval(0) = retval(0).convert_to_str (false, true); |
|
|
1416 } |
|
|
1417 } |
|
|
1418 else if (arg.is_cell ()) |
|
|
1419 { |
|
|
1420 Cell cellm = arg.cell_value (); |
|
|
1421 |
|
|
1422 // Need to check that all elements are strings |
|
5275
|
1423 for (octave_idx_type i = 0; i < cellm.numel (); i++) |
|
4996
|
1424 if (! cellm(i).is_string ()) |
|
|
1425 { |
|
|
1426 gripe_wrong_type_arg ("sort", arg); |
|
|
1427 break; |
|
|
1428 } |
|
|
1429 |
|
|
1430 // Don't have unindexed version as ">" operator doesn't return bool |
|
|
1431 if (!error_state) |
|
|
1432 retval = mx_sort_indexed (cellm, dim, smode); |
|
4991
|
1433 } |
|
2928
|
1434 else |
|
|
1435 gripe_wrong_type_arg ("sort", arg); |
|
|
1436 |
|
|
1437 return retval; |
|
|
1438 } |
|
|
1439 |
|
|
1440 /* |
|
|
1441 ;;; Local Variables: *** |
|
|
1442 ;;; mode: C++ *** |
|
|
1443 ;;; End: *** |
|
|
1444 */ |
