|
4998
|
1 v/* |
|
2928
|
2 |
|
|
3 Copyright (C) 1996, 1997 John W. Eaton |
|
4850
|
4 Copyright (C) 2004 David Bateman |
|
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 |
|
|
10 Free Software Foundation; either version 2, or (at your option) any |
|
|
11 later version. |
|
|
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 |
|
|
19 along with Octave; see the file COPYING. If not, write to the Free |
|
|
20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
|
|
21 |
|
|
22 */ |
|
|
23 |
|
|
24 #ifdef HAVE_CONFIG_H |
|
|
25 #include <config.h> |
|
|
26 #endif |
|
|
27 |
|
3826
|
28 #include "lo-mappers.h" |
|
4153
|
29 #include "quit.h" |
|
3826
|
30 |
|
2928
|
31 #include "defun-dld.h" |
|
|
32 #include "error.h" |
|
|
33 #include "gripes.h" |
|
|
34 #include "oct-obj.h" |
|
4850
|
35 #include "lo-ieee.h" |
|
|
36 #include "data-conv.h" |
|
|
37 #include "ov-cx-mat.h" |
|
4996
|
38 #include "ov-cell.h" |
|
4850
|
39 #include "oct-sort.cc" |
|
2928
|
40 |
|
4997
|
41 enum sortmode { UNDEFINED, ASCENDING, DESCENDING }; |
|
4996
|
42 |
|
|
43 template <class T> |
|
|
44 class |
|
|
45 vec_index |
|
|
46 { |
|
4997
|
47 public: |
|
4996
|
48 T vec; |
|
|
49 int indx; |
|
|
50 }; |
|
|
51 |
|
|
52 template <class T> |
|
4998
|
53 static octave_value |
|
4996
|
54 mx_sort (ArrayN<T> &m, int dim, sortmode mode = UNDEFINED) |
|
|
55 { |
|
4998
|
56 octave_value retval; |
|
4996
|
57 |
|
|
58 if (m.length () < 1) |
|
|
59 return retval; |
|
|
60 |
|
|
61 dim_vector dv = m.dims (); |
|
|
62 unsigned int ns = dv (dim); |
|
|
63 unsigned int iter = dv.numel () / ns; |
|
|
64 unsigned int stride = 1; |
|
|
65 for (unsigned int i = 0; i < (unsigned int)dim; i++) |
|
|
66 stride *= dv(i); |
|
|
67 |
|
|
68 T *v = m.fortran_vec (); |
|
|
69 octave_sort<T> sort; |
|
|
70 |
|
|
71 if (mode == ASCENDING) |
|
|
72 sort.set_compare (ascending_compare); |
|
|
73 else if (mode == DESCENDING) |
|
|
74 sort.set_compare (descending_compare); |
|
|
75 |
|
|
76 if (stride == 1) |
|
4997
|
77 { |
|
|
78 for (unsigned int j = 0; j < iter; j++) |
|
|
79 { |
|
|
80 sort.sort (v, ns); |
|
|
81 v += ns; |
|
|
82 } |
|
|
83 } |
|
4996
|
84 else |
|
|
85 { |
|
|
86 OCTAVE_LOCAL_BUFFER (T, vi, ns); |
|
|
87 for (unsigned int j = 0; j < iter; j++) |
|
|
88 { |
|
|
89 unsigned int offset = j; |
|
|
90 unsigned int offset2 = 0; |
|
|
91 while (offset >= stride) |
|
|
92 { |
|
|
93 offset -= stride; |
|
|
94 offset2++; |
|
|
95 } |
|
|
96 offset += offset2 * stride * ns; |
|
|
97 |
|
|
98 for (unsigned int i = 0; i < ns; i++) |
|
|
99 vi[i] = v[i*stride + offset]; |
|
|
100 |
|
|
101 sort.sort (vi, ns); |
|
|
102 |
|
|
103 for (unsigned int i = 0; i < ns; i++) |
|
|
104 v[i*stride + offset] = vi[i]; |
|
|
105 } |
|
|
106 } |
|
|
107 |
|
4998
|
108 retval = m; |
|
4997
|
109 |
|
4996
|
110 return retval; |
|
|
111 } |
|
|
112 |
|
|
113 template <class T> |
|
|
114 static octave_value_list |
|
|
115 mx_sort_indexed (ArrayN<T> &m, int dim, sortmode mode = UNDEFINED) |
|
|
116 { |
|
|
117 octave_value_list retval; |
|
|
118 |
|
|
119 if (m.length () < 1) |
|
|
120 return retval; |
|
|
121 |
|
|
122 dim_vector dv = m.dims (); |
|
|
123 unsigned int ns = dv (dim); |
|
|
124 unsigned int iter = dv.numel () / ns; |
|
|
125 unsigned int stride = 1; |
|
|
126 for (unsigned int i = 0; i < (unsigned int)dim; i++) |
|
|
127 stride *= dv(i); |
|
|
128 |
|
|
129 T *v = m.fortran_vec (); |
|
|
130 octave_sort<vec_index<T> *> indexed_sort; |
|
|
131 |
|
|
132 if (mode == ASCENDING) |
|
|
133 indexed_sort.set_compare (ascending_compare); |
|
|
134 else if (mode == DESCENDING) |
|
|
135 indexed_sort.set_compare (descending_compare); |
|
|
136 |
|
|
137 OCTAVE_LOCAL_BUFFER (vec_index<T> *, vi, ns); |
|
|
138 OCTAVE_LOCAL_BUFFER (vec_index<T>, vix, ns); |
|
|
139 |
|
|
140 for (unsigned int i = 0; i < ns; i++) |
|
|
141 vi[i] = &vix[i]; |
|
|
142 |
|
|
143 NDArray idx (dv); |
|
|
144 |
|
|
145 if (stride == 1) |
|
|
146 { |
|
|
147 for (unsigned int j = 0; j < iter; j++) |
|
|
148 { |
|
|
149 unsigned int offset = j * ns; |
|
|
150 |
|
|
151 for (unsigned int i = 0; i < ns; i++) |
|
|
152 { |
|
|
153 vi[i]->vec = v[i]; |
|
|
154 vi[i]->indx = i + 1; |
|
|
155 } |
|
|
156 |
|
|
157 indexed_sort.sort (vi, ns); |
|
|
158 |
|
|
159 for (unsigned int i = 0; i < ns; i++) |
|
|
160 { |
|
|
161 v[i] = vi[i]->vec; |
|
|
162 idx(i + offset) = vi[i]->indx; |
|
|
163 } |
|
|
164 v += ns; |
|
|
165 } |
|
|
166 } |
|
|
167 else |
|
|
168 { |
|
|
169 for (unsigned int j = 0; j < iter; j++) |
|
|
170 { |
|
|
171 unsigned int offset = j; |
|
|
172 unsigned int offset2 = 0; |
|
|
173 while (offset >= stride) |
|
|
174 { |
|
|
175 offset -= stride; |
|
|
176 offset2++; |
|
|
177 } |
|
|
178 offset += offset2 * stride * ns; |
|
|
179 |
|
|
180 for (unsigned int i = 0; i < ns; i++) |
|
|
181 { |
|
|
182 vi[i]->vec = v[i*stride + offset]; |
|
|
183 vi[i]->indx = i + 1; |
|
|
184 } |
|
|
185 |
|
|
186 indexed_sort.sort (vi, ns); |
|
|
187 |
|
|
188 for (unsigned int i = 0; i < ns; i++) |
|
|
189 { |
|
|
190 v[i*stride+offset] = vi[i]->vec; |
|
|
191 idx(i*stride+offset) = vi[i]->indx; |
|
|
192 } |
|
|
193 } |
|
|
194 } |
|
|
195 |
|
4997
|
196 retval(1) = idx; |
|
|
197 retval(0) = octave_value (m); |
|
4999
|
198 |
|
4996
|
199 return retval; |
|
|
200 } |
|
|
201 |
|
4853
|
202 // If we have IEEE 754 data format, then we can use the trick of |
|
|
203 // casting doubles as unsigned eight byte integers, and with a little |
|
|
204 // bit of magic we can automatically sort the NaN's correctly. |
|
2928
|
205 |
|
4853
|
206 #if defined (HAVE_IEEE754_DATA_FORMAT) && defined (EIGHT_BYTE_INT) |
|
4850
|
207 |
|
4999
|
208 static inline unsigned EIGHT_BYTE_INT |
|
|
209 FloatFlip (unsigned EIGHT_BYTE_INT f) |
|
2928
|
210 { |
|
4850
|
211 unsigned EIGHT_BYTE_INT mask = -(EIGHT_BYTE_INT)(f >> 63) | |
|
|
212 0x8000000000000000ULL; |
|
4999
|
213 |
|
4850
|
214 return f ^ mask; |
|
|
215 } |
|
2928
|
216 |
|
4850
|
217 inline unsigned EIGHT_BYTE_INT IFloatFlip(unsigned EIGHT_BYTE_INT f) |
|
|
218 { |
|
|
219 unsigned EIGHT_BYTE_INT mask = ((f >> 63) - 1) | 0x8000000000000000ULL; |
|
4999
|
220 |
|
4850
|
221 return f ^ mask; |
|
|
222 } |
|
2928
|
223 |
|
4996
|
224 bool |
|
|
225 ascending_compare (unsigned EIGHT_BYTE_INT a, |
|
4998
|
226 unsigned EIGHT_BYTE_INT b) |
|
4850
|
227 { |
|
4996
|
228 return (a < b); |
|
|
229 } |
|
2928
|
230 |
|
4850
|
231 bool |
|
4996
|
232 ascending_compare (vec_index<unsigned EIGHT_BYTE_INT> *a, |
|
|
233 vec_index<unsigned EIGHT_BYTE_INT> *b) |
|
4850
|
234 { |
|
|
235 return (a->vec < b->vec); |
|
2928
|
236 } |
|
|
237 |
|
4996
|
238 bool |
|
|
239 descending_compare (unsigned EIGHT_BYTE_INT a, |
|
|
240 unsigned EIGHT_BYTE_INT b) |
|
4850
|
241 { |
|
4996
|
242 return (a > b); |
|
4850
|
243 } |
|
2928
|
244 |
|
4850
|
245 bool |
|
4996
|
246 descending_compare (vec_index<unsigned EIGHT_BYTE_INT> *a, |
|
|
247 vec_index<unsigned EIGHT_BYTE_INT> *b) |
|
4850
|
248 { |
|
4996
|
249 return (a->vec > b->vec); |
|
4850
|
250 } |
|
|
251 |
|
4996
|
252 template class octave_sort<unsigned EIGHT_BYTE_INT>; |
|
|
253 template class vec_index<unsigned EIGHT_BYTE_INT>; |
|
|
254 template class octave_sort<vec_index<unsigned EIGHT_BYTE_INT> *>; |
|
2928
|
255 |
|
4996
|
256 template <> |
|
4998
|
257 static octave_value |
|
4996
|
258 mx_sort (ArrayN<double> &m, int dim, sortmode mode) |
|
2928
|
259 { |
|
4998
|
260 octave_value retval; |
|
2928
|
261 |
|
4850
|
262 if (m.length () < 1) |
|
|
263 return retval; |
|
|
264 |
|
|
265 dim_vector dv = m.dims (); |
|
4851
|
266 unsigned int ns = dv (dim); |
|
|
267 unsigned int iter = dv.numel () / ns; |
|
|
268 unsigned int stride = 1; |
|
|
269 for (unsigned int i = 0; i < (unsigned int)dim; i++) |
|
4850
|
270 stride *= dv(i); |
|
|
271 |
|
|
272 double *v = m.fortran_vec (); |
|
|
273 |
|
|
274 unsigned EIGHT_BYTE_INT *p = (unsigned EIGHT_BYTE_INT *)v; |
|
|
275 |
|
4996
|
276 octave_sort<unsigned EIGHT_BYTE_INT> sort; |
|
|
277 |
|
|
278 if (mode == ASCENDING) |
|
|
279 sort.set_compare (ascending_compare); |
|
|
280 else if (mode == DESCENDING) |
|
|
281 sort.set_compare (descending_compare); |
|
|
282 |
|
|
283 if (stride == 1) |
|
4850
|
284 { |
|
4996
|
285 for (unsigned int j = 0; j < iter; j++) |
|
|
286 { |
|
|
287 // Flip the data in the vector so that int compares on |
|
|
288 // IEEE754 give the correct ordering. |
|
|
289 |
|
|
290 for (unsigned int i = 0; i < ns; i++) |
|
|
291 p[i] = FloatFlip (p[i]); |
|
|
292 |
|
|
293 sort.sort (p, ns); |
|
|
294 |
|
|
295 // Flip the data out of the vector so that int compares |
|
|
296 // on IEEE754 give the correct ordering. |
|
|
297 |
|
|
298 for (unsigned int i = 0; i < ns; i++) |
|
|
299 p[i] = IFloatFlip (p[i]); |
|
4850
|
300 |
|
4996
|
301 // There are two representations of NaN. One will be |
|
|
302 // sorted to the beginning of the vector and the other |
|
|
303 // to the end. If it will be sorted to the beginning, |
|
|
304 // fix things up. |
|
4850
|
305 |
|
4996
|
306 if ((lo_ieee_signbit (octave_NaN) && (mode == ASCENDING)) || |
|
|
307 (! lo_ieee_signbit (octave_NaN) && (mode == DESCENDING))) |
|
|
308 { |
|
|
309 unsigned int i = 0; |
|
|
310 double *vtmp = (double *)p; |
|
4997
|
311 while (xisnan (vtmp[i++]) && i < ns); |
|
4996
|
312 for (unsigned int l = 0; l < ns - i + 1; l++) |
|
|
313 vtmp[l] = vtmp[l+i-1]; |
|
|
314 for (unsigned int l = ns - i + 1; l < ns; l++) |
|
|
315 vtmp[l] = octave_NaN; |
|
|
316 } |
|
|
317 |
|
|
318 p += ns; |
|
|
319 } |
|
|
320 } |
|
|
321 else |
|
|
322 { |
|
|
323 OCTAVE_LOCAL_BUFFER (unsigned EIGHT_BYTE_INT, vi, ns); |
|
|
324 |
|
4851
|
325 for (unsigned int j = 0; j < iter; j++) |
|
4850
|
326 { |
|
4851
|
327 unsigned int offset = j; |
|
|
328 unsigned int offset2 = 0; |
|
4850
|
329 while (offset >= stride) |
|
|
330 { |
|
|
331 offset -= stride; |
|
|
332 offset2++; |
|
|
333 } |
|
|
334 offset += offset2 * stride * ns; |
|
2928
|
335 |
|
4853
|
336 // Flip the data in the vector so that int compares on |
|
|
337 // IEEE754 give the correct ordering. |
|
|
338 |
|
4851
|
339 for (unsigned int i = 0; i < ns; i++) |
|
4996
|
340 vi[i] = FloatFlip (p[i*stride + offset]); |
|
4850
|
341 |
|
4996
|
342 sort.sort (vi, ns); |
|
4850
|
343 |
|
4996
|
344 // Flip the data out of the vector so that int compares |
|
|
345 // on IEEE754 give the correct ordering. |
|
4853
|
346 |
|
4851
|
347 for (unsigned int i = 0; i < ns; i++) |
|
4996
|
348 p[i*stride + offset] = IFloatFlip (vi[i]); |
|
|
349 |
|
|
350 // There are two representations of NaN. One will be |
|
|
351 // sorted to the beginning of the vector and the other |
|
|
352 // to the end. If it will be sorted to the beginning, |
|
|
353 // fix things up. |
|
2928
|
354 |
|
4996
|
355 if ((lo_ieee_signbit (octave_NaN) && (mode == ASCENDING)) || |
|
|
356 (! lo_ieee_signbit (octave_NaN) && (mode == DESCENDING))) |
|
4850
|
357 { |
|
|
358 unsigned int i = 0; |
|
4997
|
359 while (xisnan (v[i++*stride + offset]) && i < ns); |
|
4850
|
360 for (unsigned int l = 0; l < ns - i + 1; l++) |
|
4996
|
361 v[l*stride + offset] = v[(l+i-1)*stride + offset]; |
|
|
362 for (unsigned int l = ns - i + 1; l < ns; l++) |
|
|
363 v[l*stride + offset] = octave_NaN; |
|
4850
|
364 } |
|
2928
|
365 } |
|
|
366 } |
|
|
367 |
|
4998
|
368 retval = m; |
|
|
369 |
|
2928
|
370 return retval; |
|
|
371 } |
|
|
372 |
|
4996
|
373 template <> |
|
2928
|
374 static octave_value_list |
|
4996
|
375 mx_sort_indexed (ArrayN<double> &m, int dim, sortmode mode) |
|
2928
|
376 { |
|
|
377 octave_value_list retval; |
|
|
378 |
|
4850
|
379 if (m.length () < 1) |
|
|
380 return retval; |
|
|
381 |
|
|
382 dim_vector dv = m.dims (); |
|
4851
|
383 unsigned int ns = dv (dim); |
|
|
384 unsigned int iter = dv.numel () / ns; |
|
|
385 unsigned int stride = 1; |
|
|
386 for (unsigned int i = 0; i < (unsigned int)dim; i++) |
|
4850
|
387 stride *= dv(i); |
|
2928
|
388 |
|
4996
|
389 double *v = m.fortran_vec (); |
|
4850
|
390 |
|
4996
|
391 unsigned EIGHT_BYTE_INT *p = (unsigned EIGHT_BYTE_INT *)v; |
|
|
392 |
|
|
393 octave_sort<vec_index<unsigned EIGHT_BYTE_INT> *> indexed_sort; |
|
2928
|
394 |
|
4996
|
395 if (mode == ASCENDING) |
|
|
396 indexed_sort.set_compare (ascending_compare); |
|
|
397 else if (mode == DESCENDING) |
|
|
398 indexed_sort.set_compare (descending_compare); |
|
4850
|
399 |
|
4996
|
400 OCTAVE_LOCAL_BUFFER (vec_index<unsigned EIGHT_BYTE_INT> *, vi, ns); |
|
|
401 OCTAVE_LOCAL_BUFFER (vec_index<unsigned EIGHT_BYTE_INT>, vix, ns); |
|
|
402 |
|
4851
|
403 for (unsigned int i = 0; i < ns; i++) |
|
4850
|
404 vi[i] = &vix[i]; |
|
2928
|
405 |
|
4850
|
406 NDArray idx (dv); |
|
4996
|
407 |
|
|
408 for (unsigned int j = 0; j < iter; j++) |
|
2928
|
409 { |
|
4996
|
410 unsigned int offset = j; |
|
|
411 unsigned int offset2 = 0; |
|
|
412 while (offset >= stride) |
|
2928
|
413 { |
|
4996
|
414 offset -= stride; |
|
|
415 offset2++; |
|
|
416 } |
|
|
417 offset += offset2 * stride * ns; |
|
2928
|
418 |
|
4996
|
419 // Flip the data in the vector so that int compares on |
|
|
420 // IEEE754 give the correct ordering. |
|
|
421 |
|
|
422 for (unsigned int i = 0; i < ns; i++) |
|
|
423 { |
|
|
424 vi[i]->vec = FloatFlip (p[i*stride + offset]); |
|
|
425 vi[i]->indx = i + 1; |
|
4850
|
426 } |
|
4996
|
427 |
|
|
428 indexed_sort.sort (vi, ns); |
|
|
429 |
|
|
430 // Flip the data out of the vector so that int compares on |
|
|
431 // IEEE754 give the correct ordering |
|
|
432 |
|
|
433 for (unsigned int i = 0; i < ns; i++) |
|
4850
|
434 { |
|
4996
|
435 p[i*stride + offset] = IFloatFlip (vi[i]->vec); |
|
|
436 idx(i*stride + offset) = vi[i]->indx; |
|
|
437 } |
|
|
438 |
|
|
439 // There are two representations of NaN. One will be sorted |
|
|
440 // to the beginning of the vector and the other to the end. |
|
|
441 // If it will be sorted to the beginning, fix things up. |
|
2928
|
442 |
|
4996
|
443 if ((lo_ieee_signbit (octave_NaN) && (mode == ASCENDING)) || |
|
|
444 (! lo_ieee_signbit (octave_NaN) && (mode == DESCENDING))) |
|
|
445 { |
|
|
446 unsigned int i = 0; |
|
4997
|
447 while (xisnan (v[i++*stride+offset]) && i < ns); |
|
4996
|
448 OCTAVE_LOCAL_BUFFER (double, itmp, i - 1); |
|
|
449 for (unsigned int l = 0; l < i -1; l++) |
|
|
450 itmp[l] = idx(l*stride + offset); |
|
|
451 for (unsigned int l = 0; l < ns - i + 1; l++) |
|
4850
|
452 { |
|
4996
|
453 v[l*stride + offset] = v[(l+i-1)*stride + offset]; |
|
|
454 idx(l*stride + offset) = idx((l+i-1)*stride + offset); |
|
4850
|
455 } |
|
4996
|
456 for (unsigned int k = 0, l = ns - i + 1; l < ns; l++, k++) |
|
4850
|
457 { |
|
4996
|
458 v[l*stride + offset] = octave_NaN; |
|
|
459 idx(l*stride + offset) = itmp[k]; |
|
4850
|
460 } |
|
2928
|
461 } |
|
|
462 } |
|
|
463 |
|
4997
|
464 retval(1) = idx; |
|
|
465 retval(0) = m; |
|
4998
|
466 |
|
2928
|
467 return retval; |
|
|
468 } |
|
|
469 |
|
4996
|
470 #else |
|
|
471 |
|
|
472 bool |
|
|
473 ascending_compare (double a, double b) |
|
4991
|
474 { |
|
4997
|
475 return (xisnan (b) || (a < b)); |
|
4996
|
476 } |
|
|
477 |
|
|
478 bool |
|
|
479 ascending_compare (vec_index<double> *a, vec_index<double> *b) |
|
|
480 { |
|
4997
|
481 return (xisnan (b->vec) || (a->vec < b->vec)); |
|
4996
|
482 } |
|
|
483 |
|
|
484 bool |
|
|
485 descending_compare (double a, double b) |
|
|
486 { |
|
4997
|
487 return (xisnan (a) || (a > b)); |
|
4996
|
488 } |
|
4991
|
489 |
|
|
490 bool |
|
4996
|
491 descending_compare (vec_index<double> *a, vec_index<double> *b) |
|
|
492 { |
|
4997
|
493 return (xisnan (a->vec) || (a->vec > b->vec)); |
|
4996
|
494 } |
|
|
495 |
|
|
496 template class octave_sort<double>; |
|
|
497 template class vec_index<double>; |
|
|
498 template class octave_sort<vec_index<double> *>; |
|
|
499 |
|
|
500 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
501 static octave_value_list |
|
|
502 mx_sort (ArrayN<double> &m, int dim, sortmode mode); |
|
|
503 |
|
|
504 static octave_value_list |
|
|
505 mx_sort_indexed (ArrayN<double> &m, int dim, sortmode mode); |
|
|
506 #endif |
|
|
507 #endif |
|
|
508 |
|
|
509 // std::abs(Inf) returns NaN!! |
|
|
510 static inline double |
|
|
511 xabs (const Complex& x) |
|
|
512 { |
|
|
513 return (xisinf (x.real ()) || xisinf (x.imag ())) ? octave_Inf : abs (x); |
|
|
514 } |
|
|
515 |
|
|
516 bool |
|
|
517 ascending_compare (vec_index<Complex> *a, vec_index<Complex> *b) |
|
|
518 { |
|
4997
|
519 return (xisnan (b->vec) |
|
|
520 || (xabs (a->vec) < xabs (b->vec)) |
|
|
521 || ((xabs (a->vec) == xabs (b->vec)) |
|
|
522 && (arg (a->vec) < arg (b->vec)))); |
|
4996
|
523 } |
|
|
524 |
|
|
525 bool |
|
|
526 descending_compare (vec_index<Complex> *a, vec_index<Complex> *b) |
|
|
527 { |
|
4997
|
528 return (xisnan (a->vec) |
|
|
529 || (xabs (a->vec) > xabs (b->vec)) |
|
|
530 || ((xabs (a->vec) == xabs (b->vec)) |
|
|
531 && (arg (a->vec) > arg (b->vec)))); |
|
4996
|
532 } |
|
|
533 |
|
|
534 template class vec_index<Complex>; |
|
|
535 template class octave_sort<vec_index<Complex> *>; |
|
|
536 |
|
|
537 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
538 static octave_value_list |
|
|
539 mx_sort_indexed (ArrayN<Complex> &m, int dim, sortmode mode); |
|
|
540 #endif |
|
|
541 |
|
|
542 bool |
|
|
543 ascending_compare (char a, char b) |
|
|
544 { |
|
|
545 return (a < b); |
|
|
546 } |
|
|
547 |
|
|
548 bool |
|
|
549 ascending_compare (vec_index<char> *a, vec_index<char> *b) |
|
4991
|
550 { |
|
|
551 return (a->vec < b->vec); |
|
|
552 } |
|
|
553 |
|
4996
|
554 bool |
|
|
555 descending_compare (char a, char b) |
|
|
556 { |
|
|
557 return (a > b); |
|
|
558 } |
|
|
559 |
|
|
560 bool |
|
|
561 descending_compare (vec_index<char> *a, vec_index<char> *b) |
|
|
562 { |
|
|
563 return (a->vec > b->vec); |
|
|
564 } |
|
|
565 |
|
4991
|
566 template class octave_sort<char>; |
|
4996
|
567 template class vec_index<char>; |
|
|
568 template class octave_sort<vec_index<char> *>; |
|
|
569 |
|
|
570 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
571 static octave_value_list |
|
|
572 mx_sort (ArrayN<char> &m, int dim, sortmode mode); |
|
4991
|
573 |
|
|
574 static octave_value_list |
|
4996
|
575 mx_sort_indexed (ArrayN<char> &m, int dim, sortmode mode); |
|
|
576 #endif |
|
4991
|
577 |
|
4996
|
578 bool |
|
|
579 ascending_compare (vec_index<octave_value> *a, vec_index<octave_value> *b) |
|
|
580 { |
|
|
581 return (a->vec.string_value () < b->vec.string_value ()); |
|
|
582 } |
|
4991
|
583 |
|
4996
|
584 bool |
|
|
585 descending_compare (vec_index<octave_value> *a, vec_index<octave_value> *b) |
|
|
586 { |
|
|
587 return (a->vec.string_value () > b->vec.string_value ()); |
|
|
588 } |
|
4991
|
589 |
|
4996
|
590 template class vec_index<octave_value>; |
|
|
591 template class octave_sort<vec_index<octave_value> *>; |
|
4991
|
592 |
|
4996
|
593 #if !defined (CXX_NEW_FRIEND_TEMPLATE_DECL) |
|
|
594 static octave_value_list |
|
|
595 mx_sort_indexed (ArrayN<octave_value> &m, int dim, sortmode mode); |
|
|
596 #endif |
|
4991
|
597 |
|
2928
|
598 DEFUN_DLD (sort, args, nargout, |
|
3369
|
599 "-*- texinfo -*-\n\ |
|
|
600 @deftypefn {Loadable Function} {[@var{s}, @var{i}] =} sort (@var{x})\n\ |
|
4850
|
601 @deftypefnx {Loadable Function} {[@var{s}, @var{i}] =} sort (@var{x}, @var{dim})\n\ |
|
4996
|
602 @deftypefnx {Loadable Function} {[@var{s}, @var{i}] =} sort (@dots{}, @var{mode})\n\ |
|
3369
|
603 Return a copy of @var{x} with the elements elements arranged in\n\ |
|
|
604 increasing order. For matrices, @code{sort} orders the elements in each\n\ |
|
|
605 column.\n\ |
|
|
606 \n\ |
|
|
607 For example,\n\ |
|
|
608 \n\ |
|
|
609 @example\n\ |
|
|
610 @group\n\ |
|
|
611 sort ([1, 2; 2, 3; 3, 1])\n\ |
|
|
612 @result{} 1 1\n\ |
|
|
613 2 2\n\ |
|
|
614 3 3\n\ |
|
|
615 @end group\n\ |
|
|
616 @end example\n\ |
|
2928
|
617 \n\ |
|
3369
|
618 The @code{sort} function may also be used to produce a matrix\n\ |
|
|
619 containing the original row indices of the elements in the sorted\n\ |
|
|
620 matrix. For example,\n\ |
|
|
621 \n\ |
|
|
622 @example\n\ |
|
|
623 @group\n\ |
|
|
624 [s, i] = sort ([1, 2; 2, 3; 3, 1])\n\ |
|
|
625 @result{} s = 1 1\n\ |
|
|
626 2 2\n\ |
|
|
627 3 3\n\ |
|
|
628 @result{} i = 1 3\n\ |
|
|
629 2 1\n\ |
|
|
630 3 2\n\ |
|
|
631 @end group\n\ |
|
|
632 @end example\n\ |
|
4850
|
633 \n\ |
|
|
634 If the optional argument @var{dim} is given, then the matrix is sorted\n\ |
|
4996
|
635 along the dimension defined by @var{dim}. The optional argument @code{mode}\n\ |
|
|
636 defines the order in which the values will be sorted. Valid values of\n\ |
|
|
637 @code{mode} are `ascend' or `descend'.\n\ |
|
4850
|
638 \n\ |
|
|
639 For equal elements, the indices are such that the equal elements are listed\n\ |
|
|
640 in the order that appeared in the original list.\n\ |
|
|
641 \n\ |
|
4996
|
642 The @code{sort} function may also be used to sort strings and cell arrays\n\ |
|
|
643 of strings, it which case the dictionary order of the strings is used.\n\ |
|
|
644 \n\ |
|
4850
|
645 The algorithm used in @code{sort} is optimized for the sorting of partially\n\ |
|
|
646 ordered lists.\n\ |
|
3369
|
647 @end deftypefn") |
|
2928
|
648 { |
|
|
649 octave_value_list retval; |
|
|
650 |
|
|
651 int nargin = args.length (); |
|
4996
|
652 sortmode smode = ASCENDING; |
|
2928
|
653 |
|
4996
|
654 if (nargin < 1 && nargin > 3) |
|
2928
|
655 { |
|
|
656 print_usage ("sort"); |
|
|
657 return retval; |
|
|
658 } |
|
|
659 |
|
4850
|
660 bool return_idx = nargout > 1; |
|
2928
|
661 |
|
|
662 octave_value arg = args(0); |
|
|
663 |
|
4850
|
664 int dim = 0; |
|
4996
|
665 if (nargin > 1) |
|
|
666 { |
|
|
667 if (args(1).is_string ()) |
|
|
668 { |
|
|
669 std::string mode = args(1).string_value(); |
|
|
670 if (mode == "ascend") |
|
|
671 smode = ASCENDING; |
|
|
672 else if (mode == "descend") |
|
|
673 smode = DESCENDING; |
|
|
674 else |
|
|
675 { |
|
|
676 error ("sort: mode must be either `ascend' or `descend'"); |
|
|
677 return retval; |
|
|
678 } |
|
|
679 } |
|
|
680 else |
|
|
681 dim = args(1).nint_value () - 1; |
|
|
682 } |
|
|
683 |
|
|
684 if (nargin > 2) |
|
|
685 { |
|
|
686 if (args(1).is_string ()) |
|
|
687 { |
|
|
688 print_usage ("sort"); |
|
|
689 return retval; |
|
|
690 } |
|
|
691 |
|
|
692 if (! args(2).is_string ()) |
|
|
693 { |
|
|
694 error ("sort: mode must be a string"); |
|
|
695 return retval; |
|
|
696 } |
|
|
697 std::string mode = args(2).string_value(); |
|
|
698 if (mode == "ascend") |
|
|
699 smode = ASCENDING; |
|
|
700 else if (mode == "descend") |
|
|
701 smode = DESCENDING; |
|
|
702 else |
|
|
703 { |
|
|
704 error ("sort: mode must be either `ascend' or `descend'"); |
|
|
705 return retval; |
|
|
706 } |
|
|
707 } |
|
4850
|
708 |
|
|
709 dim_vector dv = ((const octave_complex_matrix&) arg) .dims (); |
|
|
710 if (error_state) |
|
|
711 { |
|
|
712 gripe_wrong_type_arg ("sort", arg); |
|
|
713 return retval; |
|
|
714 } |
|
4996
|
715 if (nargin == 1 || args(1).is_string ()) |
|
4850
|
716 { |
|
|
717 // Find first non singleton dimension |
|
|
718 for (int i = 0; i < dv.length (); i++) |
|
|
719 if (dv(i) > 1) |
|
|
720 { |
|
|
721 dim = i; |
|
|
722 break; |
|
|
723 } |
|
|
724 } |
|
|
725 else |
|
|
726 { |
|
|
727 if (dim < 0 || dim > dv.length () - 1) |
|
|
728 { |
|
|
729 error ("sort: dim must be a valid dimension"); |
|
|
730 return retval; |
|
|
731 } |
|
|
732 } |
|
|
733 |
|
2928
|
734 if (arg.is_real_type ()) |
|
|
735 { |
|
4850
|
736 NDArray m = arg.array_value (); |
|
2928
|
737 |
|
|
738 if (! error_state) |
|
4996
|
739 { |
|
|
740 #ifdef HAVE_IEEE754_DATA_FORMAT |
|
|
741 // As operator > gives the right result, can special case here |
|
|
742 if (! return_idx && smode == ASCENDING) |
|
|
743 retval = mx_sort (m, dim); |
|
|
744 else |
|
|
745 #endif |
|
|
746 { |
|
|
747 if (return_idx) |
|
|
748 retval = mx_sort_indexed (m, dim, smode); |
|
|
749 else |
|
|
750 retval = mx_sort (m, dim, smode); |
|
|
751 } |
|
|
752 } |
|
2928
|
753 } |
|
|
754 else if (arg.is_complex_type ()) |
|
|
755 { |
|
4850
|
756 ComplexNDArray cm = arg.complex_array_value (); |
|
2928
|
757 |
|
4996
|
758 // Don't have unindexed version as no ">" operator |
|
2928
|
759 if (! error_state) |
|
4996
|
760 retval = mx_sort_indexed (cm, dim, smode); |
|
2928
|
761 } |
|
4991
|
762 else if (arg.is_string ()) |
|
|
763 { |
|
|
764 charNDArray chm = arg.char_array_value (); |
|
|
765 |
|
|
766 if (! error_state) |
|
4996
|
767 { |
|
|
768 // As operator > gives the right result, can special case here |
|
|
769 if (! return_idx && smode == ASCENDING) |
|
|
770 retval = mx_sort (chm, dim); |
|
|
771 else |
|
|
772 { |
|
|
773 if (return_idx) |
|
|
774 retval = mx_sort_indexed (chm, dim, smode); |
|
|
775 else |
|
|
776 retval = mx_sort (chm, dim, smode); |
|
|
777 } |
|
|
778 |
|
|
779 // XXX FIXME XXX It would have been better to call |
|
|
780 // "octave_value(m, true)" but how can that be done |
|
|
781 // within the template |
|
|
782 retval(0) = retval(0).convert_to_str (false, true); |
|
|
783 } |
|
|
784 } |
|
|
785 else if (arg.is_cell ()) |
|
|
786 { |
|
|
787 Cell cellm = arg.cell_value (); |
|
|
788 |
|
|
789 // Need to check that all elements are strings |
|
|
790 for (int i = 0; i < cellm.numel (); i++) |
|
|
791 if (! cellm(i).is_string ()) |
|
|
792 { |
|
|
793 gripe_wrong_type_arg ("sort", arg); |
|
|
794 break; |
|
|
795 } |
|
|
796 |
|
|
797 // Don't have unindexed version as ">" operator doesn't return bool |
|
|
798 if (!error_state) |
|
|
799 retval = mx_sort_indexed (cellm, dim, smode); |
|
4991
|
800 } |
|
2928
|
801 else |
|
|
802 gripe_wrong_type_arg ("sort", arg); |
|
|
803 |
|
|
804 return retval; |
|
|
805 } |
|
|
806 |
|
|
807 /* |
|
|
808 ;;; Local Variables: *** |
|
|
809 ;;; mode: C++ *** |
|
|
810 ;;; End: *** |
|
|
811 */ |
