Mercurial > jwe > octave

comparison liboctave/util/oct-sort.cc @ 21139:538b57866b90

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
consistently use "typename" intead of "class" in template declarations * Object.h, QtHandlesUtils.cc, QtHandlesUtils.h, ToolBarButton.cc, ToolBarButton.h, Cell.h, __lin_interpn__.cc, bitfcns.cc, bsxfun.cc, cellfun.cc, data.cc, filter.cc, gcd.cc, graphics.cc, help.cc, kron.cc, lookup.cc, ls-mat5.cc, ls-oct-text.h, lu.cc, max.cc, mgorth.cc, oct-map.cc, oct-map.h, oct-stream.cc, oct-stream.h, octave-link.h, pr-output.cc, profiler.h, schur.cc, sparse-xdiv.cc, sparse-xpow.cc, sqrtm.cc, symtab.h, tril.cc, typecast.cc, variables.cc, xdiv.cc, zfstream.h, __init_fltk__.cc, __magick_read__.cc, chol.cc, qr.cc, ov-base-diag.cc, ov-base-diag.h, ov-base-int.cc, ov-base-int.h, ov-base-mat.cc, ov-base-mat.h, ov-base-scalar.cc, ov-base-scalar.h, ov-base-sparse.cc, ov-base-sparse.h, ov-base.h, ov-classdef.cc, ov-int-traits.h, ov-java.h, ov-usr-fcn.h, ov.cc, ov.h, op-dms-template.cc, oct-parse.in.yy, parse.h, pt-mat.cc, Array-b.cc, Array.cc, Array.h, CDiagMatrix.h, CMatrix.h, CNDArray.h, DiagArray2.cc, DiagArray2.h, MArray.cc, MArray.h, MDiagArray2.cc, MDiagArray2.h, MSparse.cc, MSparse.h, MatrixType.cc, Sparse.cc, Sparse.h, dDiagMatrix.h, dMatrix.h, dNDArray.h, fCDiagMatrix.h, fCMatrix.h, fCNDArray.h, fDiagMatrix.h, fMatrix.h, fNDArray.h, idx-vector.cc, idx-vector.h, intNDArray.cc, intNDArray.h, DET.h, base-aepbal.h, base-lu.cc, base-lu.h, base-qr.cc, base-qr.h, bsxfun-defs.cc, eigs-base.cc, lo-mappers.h, lo-specfun.cc, lo-specfun.h, oct-convn.cc, oct-fftw.cc, oct-norm.cc, sparse-base-chol.cc, sparse-base-chol.h, sparse-base-lu.cc, sparse-base-lu.h, sparse-dmsolve.cc, mx-inlines.cc, action-container.h, base-list.h, lo-traits.h, lo-utils.h, oct-base64.h, oct-binmap.h, oct-cmplx.h, oct-inttypes.cc, oct-inttypes.h, oct-locbuf.h, oct-refcount.h, oct-sort.cc, oct-sort.h: Use "typename" instead of "class" in template declarations.
author John W. Eaton <jwe@octave.org>
date Sun, 24 Jan 2016 13:50:04 -0500
parents 4197fc428c7d
children 26f85aa072de
comparison
equal deleted inserted replaced
21138:e2fca7d79169 21139:538b57866b90
114 #include "lo-mappers.h" 114 #include "lo-mappers.h"
115 #include "quit.h" 115 #include "quit.h"
116 #include "oct-sort.h" 116 #include "oct-sort.h"
117 #include "oct-locbuf.h" 117 #include "oct-locbuf.h"
118 118
119 template <class T> 119 template <typename T>
120 octave_sort<T>::octave_sort (void) : 120 octave_sort<T>::octave_sort (void) :
121 compare (ascending_compare), ms (0) 121 compare (ascending_compare), ms (0)
122 { 122 {
123 } 123 }
124 124
125 template <class T> 125 template <typename T>
126 octave_sort<T>::octave_sort (compare_fcn_type comp) 126 octave_sort<T>::octave_sort (compare_fcn_type comp)
127 : compare (comp), ms (0) 127 : compare (comp), ms (0)
128 { 128 {
129 } 129 }
130 130
131 template <class T> 131 template <typename T>
132 octave_sort<T>::~octave_sort () 132 octave_sort<T>::~octave_sort ()
133 { 133 {
134 delete ms; 134 delete ms;
135 } 135 }
136 136
137 template <class T> 137 template <typename T>
138 void 138 void
139 octave_sort<T>::set_compare (sortmode mode) 139 octave_sort<T>::set_compare (sortmode mode)
140 { 140 {
141 if (mode == ASCENDING) 141 if (mode == ASCENDING)
142 compare = ascending_compare; 142 compare = ascending_compare;
144 compare = descending_compare; 144 compare = descending_compare;
145 else 145 else
146 compare = 0; 146 compare = 0;
147 } 147 }
148 148
149 template <class T> 149 template <typename T>
150 template <class Comp> 150 template <typename Comp>
151 void 151 void
152 octave_sort<T>::binarysort (T *data, octave_idx_type nel, 152 octave_sort<T>::binarysort (T *data, octave_idx_type nel,
153 octave_idx_type start, Comp comp) 153 octave_idx_type start, Comp comp)
154 { 154 {
155 if (start == 0) 155 if (start == 0)
189 } 189 }
190 190
191 return; 191 return;
192 } 192 }
193 193
194 template <class T> 194 template <typename T>
195 template <class Comp> 195 template <typename Comp>
196 void 196 void
197 octave_sort<T>::binarysort (T *data, octave_idx_type *idx, octave_idx_type nel, 197 octave_sort<T>::binarysort (T *data, octave_idx_type *idx, octave_idx_type nel,
198 octave_idx_type start, Comp comp) 198 octave_idx_type start, Comp comp)
199 { 199 {
200 if (start == 0) 200 if (start == 0)
256 sequence without violating stability (strict > ensures there are no equal 256 sequence without violating stability (strict > ensures there are no equal
257 elements to get out of order). 257 elements to get out of order).
258 258
259 Returns -1 in case of error. 259 Returns -1 in case of error.
260 */ 260 */
261 template <class T> 261 template <typename T>
262 template <class Comp> 262 template <typename Comp>
263 octave_idx_type 263 octave_idx_type
264 octave_sort<T>::count_run (T *lo, octave_idx_type nel, bool& descending, 264 octave_sort<T>::count_run (T *lo, octave_idx_type nel, bool& descending,
265 Comp comp) 265 Comp comp)
266 { 266 {
267 octave_idx_type n; 267 octave_idx_type n;
316 key belongs at index k; or, IOW, the first k elements of a should precede 316 key belongs at index k; or, IOW, the first k elements of a should precede
317 key, and the last n-k should follow key. 317 key, and the last n-k should follow key.
318 318
319 Returns -1 on error. See listsort.txt for info on the method. 319 Returns -1 on error. See listsort.txt for info on the method.
320 */ 320 */
321 template <class T> 321 template <typename T>
322 template <class Comp> 322 template <typename Comp>
323 octave_idx_type 323 octave_idx_type
324 octave_sort<T>::gallop_left (T key, T *a, octave_idx_type n, 324 octave_sort<T>::gallop_left (T key, T *a, octave_idx_type n,
325 octave_idx_type hint, 325 octave_idx_type hint,
326 Comp comp) 326 Comp comp)
327 { 327 {
411 411
412 The code duplication is massive, but this is enough different given that 412 The code duplication is massive, but this is enough different given that
413 we're sticking to "<" comparisons that it's much harder to follow if 413 we're sticking to "<" comparisons that it's much harder to follow if
414 written as one routine with yet another "left or right?" flag. 414 written as one routine with yet another "left or right?" flag.
415 */ 415 */
416 template <class T> 416 template <typename T>
417 template <class Comp> 417 template <typename Comp>
418 octave_idx_type 418 octave_idx_type
419 octave_sort<T>::gallop_right (T key, T *a, octave_idx_type n, 419 octave_sort<T>::gallop_right (T key, T *a, octave_idx_type n,
420 octave_idx_type hint, 420 octave_idx_type hint,
421 Comp comp) 421 Comp comp)
422 { 422 {
532 } 532 }
533 533
534 /* Ensure enough temp memory for 'need' array slots is available. 534 /* Ensure enough temp memory for 'need' array slots is available.
535 * Returns 0 on success and -1 if the memory can't be gotten. 535 * Returns 0 on success and -1 if the memory can't be gotten.
536 */ 536 */
537 template <class T> 537 template <typename T>
538 void 538 void
539 octave_sort<T>::MergeState::getmem (octave_idx_type need) 539 octave_sort<T>::MergeState::getmem (octave_idx_type need)
540 { 540 {
541 if (need <= alloced) 541 if (need <= alloced)
542 return; 542 return;
550 a = new T [need]; 550 a = new T [need];
551 alloced = need; 551 alloced = need;
552 552
553 } 553 }
554 554
555 template <class T> 555 template <typename T>
556 void 556 void
557 octave_sort<T>::MergeState::getmemi (octave_idx_type need) 557 octave_sort<T>::MergeState::getmemi (octave_idx_type need)
558 { 558 {
559 if (ia && need <= alloced) 559 if (ia && need <= alloced)
560 return; 560 return;
575 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. 575 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
576 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the 576 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
577 * merge, and should have na <= nb. See listsort.txt for more info. 577 * merge, and should have na <= nb. See listsort.txt for more info.
578 * Return 0 if successful, -1 if error. 578 * Return 0 if successful, -1 if error.
579 */ 579 */
580 template <class T> 580 template <typename T>
581 template <class Comp> 581 template <typename Comp>
582 int 582 int
583 octave_sort<T>::merge_lo (T *pa, octave_idx_type na, 583 octave_sort<T>::merge_lo (T *pa, octave_idx_type na,
584 T *pb, octave_idx_type nb, 584 T *pb, octave_idx_type nb,
585 Comp comp) 585 Comp comp)
586 { 586 {
710 dest[nb] = *pa; 710 dest[nb] = *pa;
711 711
712 return 0; 712 return 0;
713 } 713 }
714 714
715 template <class T> 715 template <typename T>
716 template <class Comp> 716 template <typename Comp>
717 int 717 int
718 octave_sort<T>::merge_lo (T *pa, octave_idx_type *ipa, octave_idx_type na, 718 octave_sort<T>::merge_lo (T *pa, octave_idx_type *ipa, octave_idx_type na,
719 T *pb, octave_idx_type *ipb, octave_idx_type nb, 719 T *pb, octave_idx_type *ipb, octave_idx_type nb,
720 Comp comp) 720 Comp comp)
721 { 721 {
857 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. 857 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
858 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the 858 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
859 * merge, and should have na >= nb. See listsort.txt for more info. 859 * merge, and should have na >= nb. See listsort.txt for more info.
860 * Return 0 if successful, -1 if error. 860 * Return 0 if successful, -1 if error.
861 */ 861 */
862 template <class T> 862 template <typename T>
863 template <class Comp> 863 template <typename Comp>
864 int 864 int
865 octave_sort<T>::merge_hi (T *pa, octave_idx_type na, 865 octave_sort<T>::merge_hi (T *pa, octave_idx_type na,
866 T *pb, octave_idx_type nb, 866 T *pb, octave_idx_type nb,
867 Comp comp) 867 Comp comp)
868 { 868 {
994 *dest = *pb; 994 *dest = *pb;
995 995
996 return 0; 996 return 0;
997 } 997 }
998 998
999 template <class T> 999 template <typename T>
1000 template <class Comp> 1000 template <typename Comp>
1001 int 1001 int
1002 octave_sort<T>::merge_hi (T *pa, octave_idx_type *ipa, octave_idx_type na, 1002 octave_sort<T>::merge_hi (T *pa, octave_idx_type *ipa, octave_idx_type na,
1003 T *pb, octave_idx_type *ipb, octave_idx_type nb, 1003 T *pb, octave_idx_type *ipb, octave_idx_type nb,
1004 Comp comp) 1004 Comp comp)
1005 { 1005 {
1144 } 1144 }
1145 1145
1146 /* Merge the two runs at stack indices i and i+1. 1146 /* Merge the two runs at stack indices i and i+1.
1147 * Returns 0 on success, -1 on error. 1147 * Returns 0 on success, -1 on error.
1148 */ 1148 */
1149 template <class T> 1149 template <typename T>
1150 template <class Comp> 1150 template <typename Comp>
1151 int 1151 int
1152 octave_sort<T>::merge_at (octave_idx_type i, T *data, 1152 octave_sort<T>::merge_at (octave_idx_type i, T *data,
1153 Comp comp) 1153 Comp comp)
1154 { 1154 {
1155 T *pa, *pb; 1155 T *pa, *pb;
1195 return merge_lo (pa, na, pb, nb, comp); 1195 return merge_lo (pa, na, pb, nb, comp);
1196 else 1196 else
1197 return merge_hi (pa, na, pb, nb, comp); 1197 return merge_hi (pa, na, pb, nb, comp);
1198 } 1198 }
1199 1199
1200 template <class T> 1200 template <typename T>
1201 template <class Comp> 1201 template <typename Comp>
1202 int 1202 int
1203 octave_sort<T>::merge_at (octave_idx_type i, T *data, octave_idx_type *idx, 1203 octave_sort<T>::merge_at (octave_idx_type i, T *data, octave_idx_type *idx,
1204 Comp comp) 1204 Comp comp)
1205 { 1205 {
1206 T *pa, *pb; 1206 T *pa, *pb;
1259 * 1259 *
1260 * See listsort.txt for more info. 1260 * See listsort.txt for more info.
1261 * 1261 *
1262 * Returns 0 on success, -1 on error. 1262 * Returns 0 on success, -1 on error.
1263 */ 1263 */
1264 template <class T> 1264 template <typename T>
1265 template <class Comp> 1265 template <typename Comp>
1266 int 1266 int
1267 octave_sort<T>::merge_collapse (T *data, Comp comp) 1267 octave_sort<T>::merge_collapse (T *data, Comp comp)
1268 { 1268 {
1269 struct s_slice *p = ms->pending; 1269 struct s_slice *p = ms->pending;
1270 1270
1288 } 1288 }
1289 1289
1290 return 0; 1290 return 0;
1291 } 1291 }
1292 1292
1293 template <class T> 1293 template <typename T>
1294 template <class Comp> 1294 template <typename Comp>
1295 int 1295 int
1296 octave_sort<T>::merge_collapse (T *data, octave_idx_type *idx, Comp comp) 1296 octave_sort<T>::merge_collapse (T *data, octave_idx_type *idx, Comp comp)
1297 { 1297 {
1298 struct s_slice *p = ms->pending; 1298 struct s_slice *p = ms->pending;
1299 1299
1322 /* Regardless of invariants, merge all runs on the stack until only one 1322 /* Regardless of invariants, merge all runs on the stack until only one
1323 * remains. This is used at the end of the mergesort. 1323 * remains. This is used at the end of the mergesort.
1324 * 1324 *
1325 * Returns 0 on success, -1 on error. 1325 * Returns 0 on success, -1 on error.
1326 */ 1326 */
1327 template <class T> 1327 template <typename T>
1328 template <class Comp> 1328 template <typename Comp>
1329 int 1329 int
1330 octave_sort<T>::merge_force_collapse (T *data, Comp comp) 1330 octave_sort<T>::merge_force_collapse (T *data, Comp comp)
1331 { 1331 {
1332 struct s_slice *p = ms->pending; 1332 struct s_slice *p = ms->pending;
1333 1333
1341 } 1341 }
1342 1342
1343 return 0; 1343 return 0;
1344 } 1344 }
1345 1345
1346 template <class T> 1346 template <typename T>
1347 template <class Comp> 1347 template <typename Comp>
1348 int 1348 int
1349 octave_sort<T>::merge_force_collapse (T *data, octave_idx_type *idx, Comp comp) 1349 octave_sort<T>::merge_force_collapse (T *data, octave_idx_type *idx, Comp comp)
1350 { 1350 {
1351 struct s_slice *p = ms->pending; 1351 struct s_slice *p = ms->pending;
1352 1352
1370 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but 1370 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
1371 * strictly less than, an exact power of 2. 1371 * strictly less than, an exact power of 2.
1372 * 1372 *
1373 * See listsort.txt for more info. 1373 * See listsort.txt for more info.
1374 */ 1374 */
1375 template <class T> 1375 template <typename T>
1376 octave_idx_type 1376 octave_idx_type
1377 octave_sort<T>::merge_compute_minrun (octave_idx_type n) 1377 octave_sort<T>::merge_compute_minrun (octave_idx_type n)
1378 { 1378 {
1379 octave_idx_type r = 0; /* becomes 1 if any 1 bits are shifted off */ 1379 octave_idx_type r = 0; /* becomes 1 if any 1 bits are shifted off */
1380 1380
1385 } 1385 }
1386 1386
1387 return n + r; 1387 return n + r;
1388 } 1388 }
1389 1389
1390 template <class T> 1390 template <typename T>
1391 template <class Comp> 1391 template <typename Comp>
1392 void 1392 void
1393 octave_sort<T>::sort (T *data, octave_idx_type nel, Comp comp) 1393 octave_sort<T>::sort (T *data, octave_idx_type nel, Comp comp)
1394 { 1394 {
1395 /* Re-initialize the Mergestate as this might be the second time called */ 1395 /* Re-initialize the Mergestate as this might be the second time called */
1396 if (! ms) ms = new MergeState; 1396 if (! ms) ms = new MergeState;
1444 1444
1445 fail: 1445 fail:
1446 return; 1446 return;
1447 } 1447 }
1448 1448
1449 template <class T> 1449 template <typename T>
1450 template <class Comp> 1450 template <typename Comp>
1451 void 1451 void
1452 octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel, 1452 octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel,
1453 Comp comp) 1453 Comp comp)
1454 { 1454 {
1455 /* Re-initialize the Mergestate as this might be the second time called */ 1455 /* Re-initialize the Mergestate as this might be the second time called */
1507 1507
1508 fail: 1508 fail:
1509 return; 1509 return;
1510 } 1510 }
1511 1511
1512 template <class T> 1512 template <typename T>
1513 void 1513 void
1514 octave_sort<T>::sort (T *data, octave_idx_type nel) 1514 octave_sort<T>::sort (T *data, octave_idx_type nel)
1515 { 1515 {
1516 #ifdef INLINE_ASCENDING_SORT 1516 #ifdef INLINE_ASCENDING_SORT
1517 if (compare == ascending_compare) 1517 if (compare == ascending_compare)
1525 #endif 1525 #endif
1526 if (compare) 1526 if (compare)
1527 sort (data, nel, compare); 1527 sort (data, nel, compare);
1528 } 1528 }
1529 1529
1530 template <class T> 1530 template <typename T>
1531 void 1531 void
1532 octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel) 1532 octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel)
1533 { 1533 {
1534 #ifdef INLINE_ASCENDING_SORT 1534 #ifdef INLINE_ASCENDING_SORT
1535 if (compare == ascending_compare) 1535 if (compare == ascending_compare)
1543 #endif 1543 #endif
1544 if (compare) 1544 if (compare)
1545 sort (data, idx, nel, compare); 1545 sort (data, idx, nel, compare);
1546 } 1546 }
1547 1547
1548 template <class T> template <class Comp> 1548 template <typename T>
1549 template <typename Comp>
1549 bool 1550 bool
1550 octave_sort<T>::is_sorted (const T *data, octave_idx_type nel, Comp comp) 1551 octave_sort<T>::is_sorted (const T *data, octave_idx_type nel, Comp comp)
1551 { 1552 {
1552 const T *end = data + nel; 1553 const T *end = data + nel;
1553 if (data != end) 1554 if (data != end)
1563 } 1564 }
1564 1565
1565 return data == end; 1566 return data == end;
1566 } 1567 }
1567 1568
1568 template <class T> 1569 template <typename T>
1569 bool 1570 bool
1570 octave_sort<T>::is_sorted (const T *data, octave_idx_type nel) 1571 octave_sort<T>::is_sorted (const T *data, octave_idx_type nel)
1571 { 1572 {
1572 bool retval = false; 1573 bool retval = false;
1573 #ifdef INLINE_ASCENDING_SORT 1574 #ifdef INLINE_ASCENDING_SORT
1593 : col (c), ofs (o), nel (n) { } 1594 : col (c), ofs (o), nel (n) { }
1594 octave_idx_type col, ofs, nel; 1595 octave_idx_type col, ofs, nel;
1595 }; 1596 };
1596 1597
1597 1598
1598 template <class T> template <class Comp> 1599 template <typename T>
1600 template <typename Comp>
1599 void 1601 void
1600 octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx, 1602 octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx,
1601 octave_idx_type rows, octave_idx_type cols, 1603 octave_idx_type rows, octave_idx_type cols,
1602 Comp comp) 1604 Comp comp)
1603 { 1605 {
1651 runs.push (run_t (col+1, ofs + lst, nel - lst)); 1653 runs.push (run_t (col+1, ofs + lst, nel - lst));
1652 } 1654 }
1653 } 1655 }
1654 } 1656 }
1655 1657
1656 template <class T> 1658 template <typename T>
1657 void 1659 void
1658 octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx, 1660 octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx,
1659 octave_idx_type rows, octave_idx_type cols) 1661 octave_idx_type rows, octave_idx_type cols)
1660 { 1662 {
1661 #ifdef INLINE_ASCENDING_SORT 1663 #ifdef INLINE_ASCENDING_SORT
1670 #endif 1672 #endif
1671 if (compare) 1673 if (compare)
1672 sort_rows (data, idx, rows, cols, compare); 1674 sort_rows (data, idx, rows, cols, compare);
1673 } 1675 }
1674 1676
1675 template <class T> template <class Comp> 1677 template <typename T>
1678 template <typename Comp>
1676 bool 1679 bool
1677 octave_sort<T>::is_sorted_rows (const T *data, octave_idx_type rows, 1680 octave_sort<T>::is_sorted_rows (const T *data, octave_idx_type rows,
1678 octave_idx_type cols, Comp comp) 1681 octave_idx_type cols, Comp comp)
1679 { 1682 {
1680 if (rows <= 1 || cols == 0) 1683 if (rows <= 1 || cols == 0)
1727 } 1730 }
1728 1731
1729 return sorted; 1732 return sorted;
1730 } 1733 }
1731 1734
1732 template <class T> 1735 template <typename T>
1733 bool 1736 bool
1734 octave_sort<T>::is_sorted_rows (const T *data, octave_idx_type rows, 1737 octave_sort<T>::is_sorted_rows (const T *data, octave_idx_type rows,
1735 octave_idx_type cols) 1738 octave_idx_type cols)
1736 { 1739 {
1737 bool retval = false; 1740 bool retval = false;
1752 return retval; 1755 return retval;
1753 } 1756 }
1754 1757
1755 // The simple binary lookup. 1758 // The simple binary lookup.
1756 1759
1757 template <class T> template <class Comp> 1760 template <typename T>
1761 template <typename Comp>
1758 octave_idx_type 1762 octave_idx_type
1759 octave_sort<T>::lookup (const T *data, octave_idx_type nel, 1763 octave_sort<T>::lookup (const T *data, octave_idx_type nel,
1760 const T& value, Comp comp) 1764 const T& value, Comp comp)
1761 { 1765 {
1762 octave_idx_type lo = 0; 1766 octave_idx_type lo = 0;
1772 } 1776 }
1773 1777
1774 return lo; 1778 return lo;
1775 } 1779 }
1776 1780
1777 template <class T> 1781 template <typename T>
1778 octave_idx_type 1782 octave_idx_type
1779 octave_sort<T>::lookup (const T *data, octave_idx_type nel, 1783 octave_sort<T>::lookup (const T *data, octave_idx_type nel,
1780 const T& value) 1784 const T& value)
1781 { 1785 {
1782 octave_idx_type retval = 0; 1786 octave_idx_type retval = 0;
1795 retval = lookup (data, nel, value, std::ptr_fun (compare)); 1799 retval = lookup (data, nel, value, std::ptr_fun (compare));
1796 1800
1797 return retval; 1801 return retval;
1798 } 1802 }
1799 1803
1800 template <class T> template <class Comp> 1804 template <typename T>
1805 template <typename Comp>
1801 void 1806 void
1802 octave_sort<T>::lookup (const T *data, octave_idx_type nel, 1807 octave_sort<T>::lookup (const T *data, octave_idx_type nel,
1803 const T *values, octave_idx_type nvalues, 1808 const T *values, octave_idx_type nvalues,
1804 octave_idx_type *idx, Comp comp) 1809 octave_idx_type *idx, Comp comp)
1805 { 1810 {
1808 // elsewhere. 1813 // elsewhere.
1809 for (octave_idx_type j = 0; j < nvalues; j++) 1814 for (octave_idx_type j = 0; j < nvalues; j++)
1810 idx[j] = lookup (data, nel, values[j], comp); 1815 idx[j] = lookup (data, nel, values[j], comp);
1811 } 1816 }
1812 1817
1813 template <class T> 1818 template <typename T>
1814 void 1819 void
1815 octave_sort<T>::lookup (const T *data, octave_idx_type nel, 1820 octave_sort<T>::lookup (const T *data, octave_idx_type nel,
1816 const T* values, octave_idx_type nvalues, 1821 const T* values, octave_idx_type nvalues,
1817 octave_idx_type *idx) 1822 octave_idx_type *idx)
1818 { 1823 {
1828 #endif 1833 #endif
1829 if (compare) 1834 if (compare)
1830 lookup (data, nel, values, nvalues, idx, std::ptr_fun (compare)); 1835 lookup (data, nel, values, nvalues, idx, std::ptr_fun (compare));
1831 } 1836 }
1832 1837
1833 template <class T> template <class Comp> 1838 template <typename T>
1839 template <typename Comp>
1834 void 1840 void
1835 octave_sort<T>::lookup_sorted (const T *data, octave_idx_type nel, 1841 octave_sort<T>::lookup_sorted (const T *data, octave_idx_type nel,
1836 const T *values, octave_idx_type nvalues, 1842 const T *values, octave_idx_type nvalues,
1837 octave_idx_type *idx, bool rev, Comp comp) 1843 octave_idx_type *idx, bool rev, Comp comp)
1838 { 1844 {
1882 for (; j != nvalues; j++) 1888 for (; j != nvalues; j++)
1883 idx[j] = i; 1889 idx[j] = i;
1884 } 1890 }
1885 } 1891 }
1886 1892
1887 template <class T> 1893 template <typename T>
1888 void 1894 void
1889 octave_sort<T>::lookup_sorted (const T *data, octave_idx_type nel, 1895 octave_sort<T>::lookup_sorted (const T *data, octave_idx_type nel,
1890 const T* values, octave_idx_type nvalues, 1896 const T* values, octave_idx_type nvalues,
1891 octave_idx_type *idx, bool rev) 1897 octave_idx_type *idx, bool rev)
1892 { 1898 {
1903 if (compare) 1909 if (compare)
1904 lookup_sorted (data, nel, values, nvalues, idx, rev, 1910 lookup_sorted (data, nel, values, nvalues, idx, rev,
1905 std::ptr_fun (compare)); 1911 std::ptr_fun (compare));
1906 } 1912 }
1907 1913
1908 template <class T> template <class Comp> 1914 template <typename T>
1915 template <typename Comp>
1909 void 1916 void
1910 octave_sort<T>::nth_element (T *data, octave_idx_type nel, 1917 octave_sort<T>::nth_element (T *data, octave_idx_type nel,
1911 octave_idx_type lo, octave_idx_type up, 1918 octave_idx_type lo, octave_idx_type up,
1912 Comp comp) 1919 Comp comp)
1913 { 1920 {
1929 else 1936 else
1930 std::partial_sort (data + lo + 1, data + up, data + nel, comp); 1937 std::partial_sort (data + lo + 1, data + up, data + nel, comp);
1931 } 1938 }
1932 } 1939 }
1933 1940
1934 template <class T> 1941 template <typename T>
1935 void 1942 void
1936 octave_sort<T>::nth_element (T *data, octave_idx_type nel, 1943 octave_sort<T>::nth_element (T *data, octave_idx_type nel,
1937 octave_idx_type lo, octave_idx_type up) 1944 octave_idx_type lo, octave_idx_type up)
1938 { 1945 {
1939 if (up < 0) 1946 if (up < 0)
1950 #endif 1957 #endif
1951 if (compare) 1958 if (compare)
1952 nth_element (data, nel, lo, up, std::ptr_fun (compare)); 1959 nth_element (data, nel, lo, up, std::ptr_fun (compare));
1953 } 1960 }
1954 1961
1955 template <class T> 1962 template <typename T>
1956 bool 1963 bool
1957 octave_sort<T>::ascending_compare (typename ref_param<T>::type x, 1964 octave_sort<T>::ascending_compare (typename ref_param<T>::type x,
1958 typename ref_param<T>::type y) 1965 typename ref_param<T>::type y)
1959 { 1966 {
1960 return x < y; 1967 return x < y;
1961 } 1968 }
1962 1969
1963 template <class T> 1970 template <typename T>
1964 bool 1971 bool
1965 octave_sort<T>::descending_compare (typename ref_param<T>::type x, 1972 octave_sort<T>::descending_compare (typename ref_param<T>::type x,
1966 typename ref_param<T>::type y) 1973 typename ref_param<T>::type y)
1967 { 1974 {
1968 return x > y; 1975 return x > y;