110 #include <functional> 119 template <
typename T>
121 compare (ascending_compare), ms (nullptr)
124 template <
typename T>
126 : compare (comp), ms (nullptr)
129 template <
typename T>
135 template <
typename T>
140 compare = ascending_compare;
142 compare = descending_compare;
147 template <
typename T>
148 template <
typename Comp>
161 T pivot = data[
start];
170 if (comp (pivot, data[
p]))
192 template <
typename T>
193 template <
typename Comp>
206 T pivot = data[
start];
215 if (comp (pivot, data[
p]))
259 template <
typename T>
260 template <
typename Comp>
275 if (comp (*lo, *(lo-1)))
278 for (lo = lo+1; lo < hi; ++lo, ++n)
280 if (comp (*lo, *(lo-1)))
288 for (lo = lo+1; lo < hi; ++lo, ++n)
290 if (comp (*lo, *(lo-1)))
319 template <
typename T>
320 template <
typename Comp>
341 if (comp (
a[ofs], key))
344 ofs = (ofs << 1) + 1;
365 if (comp (*(
a-ofs), key))
369 ofs = (ofs << 1) + 1;
377 lastofs = hint - ofs;
387 while (lastofs < ofs)
391 if (comp (
a[m], key))
414 template <
typename T>
415 template <
typename Comp>
436 if (comp (key, *(
a-ofs)))
439 ofs = (ofs << 1) + 1;
450 lastofs = hint - ofs;
461 if (comp (key,
a[ofs]))
465 ofs = (ofs << 1) + 1;
482 while (lastofs < ofs)
486 if (comp (key,
a[m]))
498 unsigned int nbits = 3;
529 return ((n >> nbits) + 1) << nbits;
535 template <
typename T>
553 template <
typename T>
557 if (ia && need <= alloced)
578 template <
typename T>
579 template <
typename Comp>
592 std::copy (pa, pa + na,
ms->
a);
625 if (bcount >= min_gallop)
636 if (acount >= min_gallop)
649 min_gallop -= min_gallop > 1;
657 dest = std::copy (pa, pa +
k, dest);
680 dest = std::copy (pb, pb +
k, dest);
702 std::copy (pa, pa + na, dest);
707 std::copy (pb, pb + nb, dest);
713 template <
typename T>
714 template <
typename Comp>
728 std::copy (pa, pa + na,
ms->
a);
729 std::copy (ipa, ipa + na,
ms->
ia);
730 dest = pa; idest = ipa;
733 *dest++ = *pb++; *idest++ = *ipb++;
753 *dest++ = *pb++; *idest++ = *ipb++;
759 if (bcount >= min_gallop)
764 *dest++ = *pa++; *idest++ = *ipa++;
770 if (acount >= min_gallop)
783 min_gallop -= min_gallop > 1;
791 dest = std::copy (pa, pa +
k, dest);
792 idest = std::copy (ipa, ipa +
k, idest);
804 *dest++ = *pb++; *idest++ = *ipb++;
815 dest = std::copy (pb, pb +
k, dest);
816 idest = std::copy (ipb, ipb +
k, idest);
822 *dest++ = *pa++; *idest++ = *ipa++;
839 std::copy (pa, pa + na, dest);
840 std::copy (ipa, ipa + na, idest);
846 std::copy (pb, pb + nb, dest);
847 std::copy (ipb, ipb + nb, idest);
860 template <
typename T>
861 template <
typename Comp>
876 std::copy (pb, pb + nb,
ms->
a);
907 if (acount >= min_gallop)
918 if (bcount >= min_gallop)
931 min_gallop -= min_gallop > 1;
940 dest = std::copy_backward (pa+1 -
k, pa+1, dest+1) - 1;
960 std::copy (pb+1, pb+1 +
k, dest+1);
985 std::copy (baseb, baseb + nb, dest-(nb-1));
990 dest = std::copy_backward (pa+1 - na, pa+1, dest+1) - 1;
997 template <
typename T>
998 template <
typename Comp>
1015 idest = ipb + nb - 1;
1016 std::copy (pb, pb + nb,
ms->
a);
1017 std::copy (ipb, ipb + nb,
ms->
ia);
1019 baseb =
ms->
a; ibaseb =
ms->
ia;
1020 pb =
ms->
a + nb - 1; ipb =
ms->
ia + nb - 1;
1021 pa += na - 1; ipa += na - 1;
1023 *dest-- = *pa--; *idest-- = *ipa--;
1040 if (comp (*pb, *pa))
1042 *dest-- = *pa--; *idest-- = *ipa--;
1048 if (acount >= min_gallop)
1053 *dest-- = *pb--; *idest-- = *ipb--;
1059 if (bcount >= min_gallop)
1072 min_gallop -= min_gallop > 1;
1081 dest = std::copy_backward (pa+1 -
k, pa+1, dest+1) - 1;
1082 idest = std::copy_backward (ipa+1 -
k, ipa+1, idest+1) - 1;
1088 *dest-- = *pb--; *idest-- = *ipb--;
1100 dest -=
k; idest -=
k;
1102 std::copy (pb+1, pb+1 +
k, dest+1);
1103 std::copy (ipb+1, ipb+1 +
k, idest+1);
1114 *dest-- = *pa--; *idest-- = *ipa--;
1129 std::copy (baseb, baseb + nb, dest-(nb-1));
1130 std::copy (ibaseb, ibaseb + nb, idest-(nb-1));
1136 dest = std::copy_backward (pa+1 - na, pa+1, dest+1) - 1;
1137 idest = std::copy_backward (ipa+1 - na, ipa+1, idest+1) - 1;
1138 pa -= na; ipa -= na;
1139 *dest = *pb; *idest = *ipb;
1147 template <
typename T>
1148 template <
typename Comp>
1193 return merge_lo (pa, na, pb, nb, comp);
1195 return merge_hi (pa, na, pb, nb, comp);
1198 template <
typename T>
1199 template <
typename Comp>
1247 return merge_lo (pa, ipa, na, pb, ipb, nb, comp);
1249 return merge_hi (pa, ipa, na, pb, ipb, nb, comp);
1262 template <
typename T>
1263 template <
typename Comp>
1272 if (n > 0 &&
p[n-1].len <=
p[n].len +
p[n+1].len)
1274 if (
p[n-1].len <
p[n+1].len)
1279 else if (
p[n].len <=
p[n+1].len)
1291 template <
typename T>
1292 template <
typename Comp>
1301 if (n > 0 &&
p[n-1].len <=
p[n].len +
p[n+1].len)
1303 if (
p[n-1].len <
p[n+1].len)
1305 if (
merge_at (n, data, idx, comp) < 0)
1308 else if (
p[n].len <=
p[n+1].len)
1310 if (
merge_at (n, data, idx, comp) < 0)
1325 template <
typename T>
1326 template <
typename Comp>
1335 if (n > 0 &&
p[n-1].len <
p[n+1].len)
1344 template <
typename T>
1345 template <
typename Comp>
1354 if (n > 0 &&
p[n-1].len <
p[n+1].len)
1356 if (
merge_at (n, data, idx, comp) < 0)
1373 template <
typename T>
1388 template <
typename T>
1389 template <
typename Comp>
1414 n =
count_run (data + lo, nremaining, descending, comp);
1418 std::reverse (data + lo, data + lo + n);
1444 template <
typename T>
1445 template <
typename Comp>
1471 n =
count_run (data + lo, nremaining, descending, comp);
1476 std::reverse (data + lo, data + lo + n);
1477 std::reverse (idx + lo, idx + lo + n);
1484 binarysort (data + lo, idx + lo, force, n, comp);
1504 template <
typename T>
1508 #if defined (INLINE_ASCENDING_SORT) 1510 sort (data, nel, std::less<T> ());
1513 #if defined (INLINE_DESCENDING_SORT) 1515 sort (data, nel, std::greater<T> ());
1522 template <
typename T>
1526 #if defined (INLINE_ASCENDING_SORT) 1528 sort (data, idx, nel, std::less<T> ());
1531 #if defined (INLINE_DESCENDING_SORT) 1533 sort (data, idx, nel, std::greater<T> ());
1540 template <
typename T>
1541 template <
typename Comp>
1545 const T *end = data + nel;
1548 const T *
next = data;
1549 while (++
next != end)
1551 if (comp (*
next, *data))
1561 template <
typename T>
1566 #if defined (INLINE_ASCENDING_SORT) 1571 #if defined (INLINE_DESCENDING_SORT) 1586 : col (
c), ofs (o), nel (n) { }
1590 template <
typename T>
1591 template <
typename Comp>
1601 if (cols == 0 || rows <= 1)
1606 std::stack<run_t> runs;
1608 runs.push (run_t (0, 0, rows));
1610 while (! runs.empty ())
1618 T *lbuf = buf + ofs;
1619 const T *ldata = data + rows*col;
1624 lbuf[
i] = ldata[lidx[
i]];
1627 sort (lbuf, lidx, nel, comp);
1635 if (comp (lbuf[lst], lbuf[
i]))
1638 runs.push (run_t (col+1, ofs + lst,
i - lst));
1643 runs.push (run_t (col+1, ofs + lst, nel - lst));
1648 template <
typename T>
1653 #if defined (INLINE_ASCENDING_SORT) 1655 sort_rows (data, idx, rows, cols, std::less<T> ());
1658 #if defined (INLINE_DESCENDING_SORT) 1660 sort_rows (data, idx, rows, cols, std::greater<T> ());
1667 template <
typename T>
1668 template <
typename Comp>
1673 if (rows <= 1 || cols == 0)
1677 const T *lastrow = data + rows*(cols - 1);
1678 typedef std::pair<const T *, octave_idx_type> run_t;
1679 std::stack<run_t> runs;
1682 runs.push (run_t (data, rows));
1683 while (sorted && ! runs.empty ())
1685 const T *lo = runs.top ().first;
1692 const T *hi = lo + n;
1694 for (lo++; lo < hi; lo++)
1696 if (comp (*lst, *lo))
1699 runs.push (run_t (lst + rows, lo - lst));
1702 else if (comp (*lo, *lst))
1709 runs.push (run_t (lst + rows, lo - lst));
1725 template <
typename T>
1732 #if defined (INLINE_ASCENDING_SORT) 1737 #if defined (INLINE_DESCENDING_SORT) 1750 template <
typename T>
1751 template <
typename Comp>
1754 const T&
value, Comp comp)
1762 if (comp (
value, data[mid]))
1771 template <
typename T>
1778 #if defined (INLINE_ASCENDING_SORT) 1783 #if defined (INLINE_DESCENDING_SORT) 1794 template <
typename T>
1795 template <
typename Comp>
1808 template <
typename T>
1814 #if defined (INLINE_ASCENDING_SORT) 1816 lookup (data, nel,
values, nvalues, idx, std::less<T> ());
1819 #if defined (INLINE_DESCENDING_SORT) 1821 lookup (data, nel,
values, nvalues, idx, std::greater<T> ());
1828 template <
typename T>
1829 template <
typename Comp>
1840 if (nvalues > 0 && nel > 0)
1844 if (comp (
values[j], data[
i]))
1850 else if (++
i == nel)
1863 if (nvalues > 0 && nel > 0)
1867 if (comp (
values[j], data[
i]))
1873 else if (++
i == nel)
1878 for (; j != nvalues; j++)
1883 template <
typename T>
1889 #if defined (INLINE_ASCENDING_SORT) 1894 #if defined (INLINE_DESCENDING_SORT) 1904 template <
typename T>
1905 template <
typename Comp>
1914 std::nth_element (data, data + lo, data + nel, comp);
1916 std::partial_sort (data, data + up, data + nel, comp);
1919 std::nth_element (data, data + lo, data + nel, comp);
1924 *std::min_element (data + lo + 1, data + nel, comp));
1927 std::partial_sort (data + lo + 1, data + up, data + nel, comp);
1931 template <
typename T>
1938 #if defined (INLINE_ASCENDING_SORT) 1943 #if defined (INLINE_DESCENDING_SORT) 1945 nth_element (data, nel, lo, up, std::greater<T> ());
1952 template <
typename T>
1960 template <
typename T>
int merge_at(octave_idx_type i, T *data, Comp comp)
void sort_rows(const T *data, octave_idx_type *idx, octave_idx_type rows, octave_idx_type cols)
octave_idx_type lookup(const T *data, octave_idx_type nel, const T &value)
octave_idx_type gallop_left(T key, T *a, octave_idx_type n, octave_idx_type hint, Comp comp)
Return the CPU time used by your Octave session The first output is the total time spent executing your process and is equal to the sum of second and third which are the number of CPU seconds spent executing in user mode and the number of CPU seconds spent executing in system mode
void set_compare(compare_fcn_type comp)
sortrows_run_t(octave_idx_type c, octave_idx_type o, octave_idx_type n)
void binarysort(T *data, octave_idx_type nel, octave_idx_type start, Comp comp)
octave_idx_type count_run(T *lo, octave_idx_type n, bool &descending, Comp comp)
nd example oindent opens the file binary numeric values will be read assuming they are stored in IEEE format with the least significant bit and then converted to the native representation Opening a file that is already open simply opens it again and returns a separate file id It is not an error to open a file several though writing to the same file through several different file ids may produce unexpected results The possible values of text mode reading and writing automatically converts linefeeds to the appropriate line end character for the you may append a you must also open the file in binary mode The parameter conversions are currently only supported for and permissions will be set to and then everything is written in a single operation This is very efficient and improves performance c
cell array If invoked with two or more scalar integer or a vector of integer values
calling an anonymous function involves an overhead quite comparable to the overhead of an m file function Passing a handle to a built in function is because the interpreter is not involved in the internal loop For a
int merge_hi(T *pa, octave_idx_type na, T *pb, octave_idx_type nb, Comp comp)
bool issorted(const T *data, octave_idx_type nel)
void getmemi(octave_idx_type need)
static octave_idx_type roundupsize(octave_idx_type n)
static bool descending_compare(typename ref_param< T >::type, typename ref_param< T >::type)
#define MAX_MERGE_PENDING
bool is_sorted_rows(const T *data, octave_idx_type rows, octave_idx_type cols)
With real return the complex result
if_then_else< is_class_type< T >::no, T, T const & >::result type
octave_idx_type gallop_right(T key, T *a, octave_idx_type n, octave_idx_type hint, Comp comp)
void sort(T *data, octave_idx_type nel)
int merge_force_collapse(T *data, Comp comp)
void lookup_sorted(const T *data, octave_idx_type nel, const T *values, octave_idx_type nvalues, octave_idx_type *idx, bool rev=false)
void getmem(octave_idx_type need)
the element is set to zero In other the statement xample y
#define OCTAVE_LOCAL_BUFFER(T, buf, size)
struct s_slice pending[85]
void nth_element(T *data, octave_idx_type nel, octave_idx_type lo, octave_idx_type up=-1)
int merge_collapse(T *data, Comp comp)
octave_idx_type merge_compute_minrun(octave_idx_type n)
octave_idx_type min_gallop
nd group nd example For each display the value
F77_RET_T const F77_REAL const F77_REAL F77_REAL &F77_RET_T const F77_DBLE const F77_DBLE F77_DBLE &F77_RET_T const F77_DBLE F77_DBLE &F77_RET_T const F77_REAL F77_REAL &F77_RET_T const F77_DBLE * x
static bool ascending_compare(typename ref_param< T >::type, typename ref_param< T >::type)
int merge_lo(T *pa, octave_idx_type na, T *pb, octave_idx_type nb, Comp comp)