Mercurial > hg > octave-nkf
changeset 8721:e9cb742df9eb
imported patch sort3.diff
author | Jaroslav Hajek <highegg@gmail.com> |
---|---|
date | Wed, 11 Feb 2009 15:25:53 +0100 |
parents | dda421a1f1e6 |
children | 3cedb606145d |
files | liboctave/Array-C.cc liboctave/Array-b.cc liboctave/Array-ch.cc liboctave/Array-d.cc liboctave/Array-f.cc liboctave/Array-fC.cc liboctave/Array-i.cc liboctave/Array-s.cc liboctave/Array.cc liboctave/Array.h liboctave/ChangeLog liboctave/CmplxQR.cc liboctave/Range.cc liboctave/Range.h liboctave/dbleQR.cc liboctave/dim-vector.h liboctave/fCmplxQR.cc liboctave/floatQR.cc liboctave/oct-sort.cc liboctave/oct-sort.h scripts/ChangeLog scripts/general/sortrows.m src/ChangeLog src/TEMPLATE-INST/Array-sym.cc src/TEMPLATE-INST/Array-tc.cc src/data.cc src/ov-base-diag.h src/ov-base-mat.h src/ov-base-scalar.h src/ov-base-sparse.h src/ov-base.cc src/ov-base.h src/ov-perm.h src/ov-range.h src/ov.h |
diffstat | 35 files changed, 949 insertions(+), 142 deletions(-) [+] |
line wrap: on
line diff
--- a/liboctave/Array-C.cc +++ b/liboctave/Array-C.cc @@ -28,41 +28,79 @@ // Instantiate Arrays of Complex values. #include "oct-cmplx.h" +#include "lo-mappers.h" #include "Array.h" #include "Array.cc" #include "oct-sort.cc" -static double -xabs (const Complex& x) +template <> +inline bool _sort_isnan (Complex x) { - return (xisinf (x.real ()) || xisinf (x.imag ())) ? octave_Inf : abs (x); + return xisnan (x); } template <> bool octave_sort<Complex>::ascending_compare (Complex a, Complex b) { - return (xisnan (b) || (xabs (a) < xabs (b)) - || ((xabs (a) == xabs (b)) && (arg (a) < arg (b)))); + return ((std::abs (a) < std::abs (b)) + || ((std::abs (a) == std::abs (b)) && (arg (a) < arg (b)))); } template <> bool octave_sort<Complex>::descending_compare (Complex a, Complex b) { - return (xisnan (a) || (xabs (a) > xabs (b)) - || ((xabs (a) == xabs (b)) && (arg (a) > arg (b)))); + return ((std::abs (a) > std::abs (b)) + || ((std::abs (a) == std::abs (b)) && (arg (a) > arg (b)))); +} + +static bool nan_ascending_compare (Complex x, Complex y) +{ + return xisnan (y) ? ! xisnan (x) : ((std::abs (x) < std::abs (x)) + || ((std::abs (x) == std::abs (x)) && (arg (x) < arg (x)))); +} + +static bool nan_descending_compare (Complex x, Complex y) +{ + return xisnan (x) ? ! xisnan (y) : ((std::abs (x) > std::abs (x)) + || ((std::abs (x) == std::abs (x)) && (arg (x) > arg (x)))); +} + +bool (*_sortrows_comparator (sortmode mode, + const Array<Complex>& a , bool allow_chk)) +(Complex, Complex) +{ + bool (*result) (Complex, Complex) = 0; + + if (allow_chk) + { + octave_idx_type k = 0; + for (; k < a.numel () && ! xisnan (a(k)); k++) ; + if (k == a.numel ()) + { + if (mode == ASCENDING) + result = octave_sort<Complex>::ascending_compare; + else if (mode == DESCENDING) + result = octave_sort<Complex>::descending_compare; + } + } + + if (! result) + { + if (mode == ASCENDING) + result = nan_ascending_compare; + else if (mode == DESCENDING) + result = nan_descending_compare; + } + + return result; } INSTANTIATE_ARRAY_SORT (Complex); -INSTANTIATE_ARRAY_AND_ASSIGN (Complex, OCTAVE_API); - -INSTANTIATE_ARRAY_ASSIGN (Complex, double, OCTAVE_API) -INSTANTIATE_ARRAY_ASSIGN (Complex, int, OCTAVE_API) -INSTANTIATE_ARRAY_ASSIGN (Complex, short, OCTAVE_API) -INSTANTIATE_ARRAY_ASSIGN (Complex, char, OCTAVE_API) +INSTANTIATE_ARRAY (Complex, OCTAVE_API); #include "Array2.h"
--- a/liboctave/Array-b.cc +++ b/liboctave/Array-b.cc @@ -33,7 +33,7 @@ INSTANTIATE_ARRAY_SORT (bool); -INSTANTIATE_ARRAY_AND_ASSIGN (bool, OCTAVE_API); +INSTANTIATE_ARRAY (bool, OCTAVE_API); #include "Array2.h"
--- a/liboctave/Array-ch.cc +++ b/liboctave/Array-ch.cc @@ -33,7 +33,7 @@ INSTANTIATE_ARRAY_SORT (char); -INSTANTIATE_ARRAY_AND_ASSIGN (char, OCTAVE_API); +INSTANTIATE_ARRAY (char, OCTAVE_API); #include "Array2.h"
--- a/liboctave/Array-d.cc +++ b/liboctave/Array-d.cc @@ -42,13 +42,49 @@ return lo_ieee_isnan (x); } +static bool nan_ascending_compare (double x, double y) +{ + return lo_ieee_isnan (y) ? ! lo_ieee_isnan (x) : x < y; +} + +static bool nan_descending_compare (double x, double y) +{ + return lo_ieee_isnan (x) ? ! lo_ieee_isnan (y) : x > y; +} + +bool (*_sortrows_comparator (sortmode mode, + const Array<double>& a , bool allow_chk)) +(double, double) +{ + bool (*result) (double, double) = 0; + + if (allow_chk) + { + octave_idx_type k = 0; + for (; k < a.numel () && ! xisnan (a(k)); k++) ; + if (k == a.numel ()) + { + if (mode == ASCENDING) + result = octave_sort<double>::ascending_compare; + else if (mode == DESCENDING) + result = octave_sort<double>::descending_compare; + } + } + + if (! result) + { + if (mode == ASCENDING) + result = nan_ascending_compare; + else if (mode == DESCENDING) + result = nan_descending_compare; + } + + return result; +} + INSTANTIATE_ARRAY_SORT (double); -INSTANTIATE_ARRAY_AND_ASSIGN (double, OCTAVE_API); - -INSTANTIATE_ARRAY_ASSIGN (double, int, OCTAVE_API) -INSTANTIATE_ARRAY_ASSIGN (double, short, OCTAVE_API) -INSTANTIATE_ARRAY_ASSIGN (double, char, OCTAVE_API) +INSTANTIATE_ARRAY (double, OCTAVE_API); #include "Array2.h"
--- a/liboctave/Array-f.cc +++ b/liboctave/Array-f.cc @@ -42,13 +42,49 @@ return lo_ieee_isnan (x); } +static bool nan_ascending_compare (float x, float y) +{ + return lo_ieee_isnan (y) ? ! lo_ieee_isnan (x) : x < y; +} + +static bool nan_descending_compare (float x, float y) +{ + return lo_ieee_isnan (x) ? ! lo_ieee_isnan (y) : x > y; +} + +bool (*_sortrows_comparator (sortmode mode, + const Array<float>& a , bool allow_chk)) +(float, float) +{ + bool (*result) (float, float) = 0; + + if (allow_chk) + { + octave_idx_type k = 0; + for (; k < a.numel () && ! xisnan (a(k)); k++) ; + if (k == a.numel ()) + { + if (mode == ASCENDING) + result = octave_sort<float>::ascending_compare; + else if (mode == DESCENDING) + result = octave_sort<float>::descending_compare; + } + } + + if (! result) + { + if (mode == ASCENDING) + result = nan_ascending_compare; + else if (mode == DESCENDING) + result = nan_descending_compare; + } + + return result; +} + INSTANTIATE_ARRAY_SORT (float); -INSTANTIATE_ARRAY_AND_ASSIGN (float, OCTAVE_API); - -INSTANTIATE_ARRAY_ASSIGN (float, int, OCTAVE_API) -INSTANTIATE_ARRAY_ASSIGN (float, short, OCTAVE_API) -INSTANTIATE_ARRAY_ASSIGN (float, char, OCTAVE_API) +INSTANTIATE_ARRAY (float, OCTAVE_API); #include "Array2.h"
--- a/liboctave/Array-fC.cc +++ b/liboctave/Array-fC.cc @@ -28,41 +28,79 @@ // Instantiate Arrays of FloatComplex values. #include "oct-cmplx.h" +#include "lo-mappers.h" #include "Array.h" #include "Array.cc" #include "oct-sort.cc" -static float -xabs (const FloatComplex& x) +template <> +inline bool _sort_isnan (FloatComplex x) { - return (xisinf (x.real ()) || xisinf (x.imag ())) ? octave_Float_Inf : abs (x); + return xisnan (x); } template <> bool octave_sort<FloatComplex>::ascending_compare (FloatComplex a, FloatComplex b) { - return (xisnan (b) || (xabs (a) < xabs (b)) - || ((xabs (a) == xabs (b)) && (arg (a) < arg (b)))); + return ((std::abs (a) < std::abs (b)) + || ((std::abs (a) == std::abs (b)) && (arg (a) < arg (b)))); } template <> bool octave_sort<FloatComplex>::descending_compare (FloatComplex a, FloatComplex b) { - return (xisnan (a) || (xabs (a) > xabs (b)) - || ((xabs (a) == xabs (b)) && (arg (a) > arg (b)))); + return ((std::abs (a) > std::abs (b)) + || ((std::abs (a) == std::abs (b)) && (arg (a) > arg (b)))); +} + +static bool nan_ascending_compare (FloatComplex x, FloatComplex y) +{ + return xisnan (y) ? ! xisnan (x) : ((std::abs (x) < std::abs (x)) + || ((std::abs (x) == std::abs (x)) && (arg (x) < arg (x)))); +} + +static bool nan_descending_compare (FloatComplex x, FloatComplex y) +{ + return xisnan (x) ? ! xisnan (y) : ((std::abs (x) > std::abs (x)) + || ((std::abs (x) == std::abs (x)) && (arg (x) > arg (x)))); +} + +bool (*_sortrows_comparator (sortmode mode, + const Array<FloatComplex>& a , bool allow_chk)) +(FloatComplex, FloatComplex) +{ + bool (*result) (FloatComplex, FloatComplex) = 0; + + if (allow_chk) + { + octave_idx_type k = 0; + for (; k < a.numel () && ! xisnan (a(k)); k++) ; + if (k == a.numel ()) + { + if (mode == ASCENDING) + result = octave_sort<FloatComplex>::ascending_compare; + else if (mode == DESCENDING) + result = octave_sort<FloatComplex>::descending_compare; + } + } + + if (! result) + { + if (mode == ASCENDING) + result = nan_ascending_compare; + else if (mode == DESCENDING) + result = nan_descending_compare; + } + + return result; } INSTANTIATE_ARRAY_SORT (FloatComplex); -INSTANTIATE_ARRAY_AND_ASSIGN (FloatComplex, OCTAVE_API); - -INSTANTIATE_ARRAY_ASSIGN (FloatComplex, float, OCTAVE_API) -INSTANTIATE_ARRAY_ASSIGN (FloatComplex, int, OCTAVE_API) -INSTANTIATE_ARRAY_ASSIGN (FloatComplex, short, OCTAVE_API) -INSTANTIATE_ARRAY_ASSIGN (FloatComplex, char, OCTAVE_API) +INSTANTIATE_ARRAY (FloatComplex, OCTAVE_API); #include "Array2.h"
--- a/liboctave/Array-i.cc +++ b/liboctave/Array-i.cc @@ -42,34 +42,31 @@ INSTANTIATE_ARRAY_SORT (long long); #endif -INSTANTIATE_ARRAY_AND_ASSIGN (int, OCTAVE_API); -INSTANTIATE_ARRAY_AND_ASSIGN (long, OCTAVE_API); +INSTANTIATE_ARRAY (int, OCTAVE_API); +INSTANTIATE_ARRAY (long, OCTAVE_API); #if defined (HAVE_LONG_LONG_INT) -INSTANTIATE_ARRAY_AND_ASSIGN (long long, OCTAVE_API); +INSTANTIATE_ARRAY (long long, OCTAVE_API); #endif -INSTANTIATE_ARRAY_ASSIGN (int, short, OCTAVE_API) -INSTANTIATE_ARRAY_ASSIGN (int, char, OCTAVE_API) - INSTANTIATE_ARRAY_SORT (octave_int8); INSTANTIATE_ARRAY_SORT (octave_int16); INSTANTIATE_ARRAY_SORT (octave_int32); INSTANTIATE_ARRAY_SORT (octave_int64); -INSTANTIATE_ARRAY_AND_ASSIGN (octave_int8, OCTAVE_API); -INSTANTIATE_ARRAY_AND_ASSIGN (octave_int16, OCTAVE_API); -INSTANTIATE_ARRAY_AND_ASSIGN (octave_int32, OCTAVE_API); -INSTANTIATE_ARRAY_AND_ASSIGN (octave_int64, OCTAVE_API); +INSTANTIATE_ARRAY (octave_int8, OCTAVE_API); +INSTANTIATE_ARRAY (octave_int16, OCTAVE_API); +INSTANTIATE_ARRAY (octave_int32, OCTAVE_API); +INSTANTIATE_ARRAY (octave_int64, OCTAVE_API); INSTANTIATE_ARRAY_SORT (octave_uint8); INSTANTIATE_ARRAY_SORT (octave_uint16); INSTANTIATE_ARRAY_SORT (octave_uint32); INSTANTIATE_ARRAY_SORT (octave_uint64); -INSTANTIATE_ARRAY_AND_ASSIGN (octave_uint8, OCTAVE_API); -INSTANTIATE_ARRAY_AND_ASSIGN (octave_uint16, OCTAVE_API); -INSTANTIATE_ARRAY_AND_ASSIGN (octave_uint32, OCTAVE_API); -INSTANTIATE_ARRAY_AND_ASSIGN (octave_uint64, OCTAVE_API); +INSTANTIATE_ARRAY (octave_uint8, OCTAVE_API); +INSTANTIATE_ARRAY (octave_uint16, OCTAVE_API); +INSTANTIATE_ARRAY (octave_uint32, OCTAVE_API); +INSTANTIATE_ARRAY (octave_uint64, OCTAVE_API); #include "Array2.h"
--- a/liboctave/Array-s.cc +++ b/liboctave/Array-s.cc @@ -36,9 +36,7 @@ INSTANTIATE_ARRAY_SORT (short); -INSTANTIATE_ARRAY_AND_ASSIGN (short, OCTAVE_API); - -INSTANTIATE_ARRAY_ASSIGN (short, char, OCTAVE_API) +INSTANTIATE_ARRAY (short, OCTAVE_API); #include "Array2.h"
--- a/liboctave/Array.cc +++ b/liboctave/Array.cc @@ -1987,6 +1987,13 @@ Array<T> Array<T>::sort (octave_idx_type dim, sortmode mode) const { + if (dim < 0 || dim >= ndims ()) + { + (*current_liboctave_error_handler) + ("sort: invalid dimension"); + return Array<T> (); + } + Array<T> m (dims ()); dim_vector dv = m.dims (); @@ -2006,12 +2013,10 @@ octave_sort<T> lsort; - if (mode == ASCENDING) - lsort.set_compare (octave_sort<T>::ascending_compare); - else if (mode == DESCENDING) - lsort.set_compare (octave_sort<T>::descending_compare); + if (mode) + lsort.set_compare (mode); else - abort (); + return m; if (stride == 1) { @@ -2098,6 +2103,13 @@ Array<T>::sort (Array<octave_idx_type> &sidx, octave_idx_type dim, sortmode mode) const { + if (dim < 0 || dim >= ndims ()) + { + (*current_liboctave_error_handler) + ("sort: invalid dimension"); + return Array<T> (); + } + Array<T> m (dims ()); dim_vector dv = m.dims (); @@ -2123,12 +2135,10 @@ sidx = Array<octave_idx_type> (dv); octave_idx_type *vi = sidx.fortran_vec (); - if (mode == ASCENDING) - lsort.set_compare (octave_sort<T>::ascending_compare); - else if (mode == DESCENDING) - lsort.set_compare (octave_sort<T>::descending_compare); + if (mode) + lsort.set_compare (mode); else - abort (); + return m; if (stride == 1) { @@ -2239,6 +2249,171 @@ } template <class T> +sortmode +Array<T>::is_sorted (sortmode mode) const +{ + if (nelem () <= 1) + return ASCENDING; + + const T *lo = data (), *hi = data () + nelem () - 1; + + // Check for NaNs at the beginning and end. + if (mode != ASCENDING && _sort_isnan (*lo)) + { + mode = DESCENDING; + do + ++lo; + while (lo < hi && _sort_isnan (*lo)); + } + else if (mode != DESCENDING && _sort_isnan (*hi)) + { + mode = ASCENDING; + do + --hi; + while (lo < hi && _sort_isnan (*hi)); + } + + octave_sort<T> lsort; + + // If mode is still unknown, compare lo and hi + if (! mode) + { + if (lsort.descending_compare (*lo, *hi)) + mode = DESCENDING; + else if (lsort.ascending_compare (*lo, *hi)) + mode = ASCENDING; + else + mode = ASCENDING; + } + + lsort.set_compare (mode); + + if (! lsort.is_sorted (lo, hi - lo + 1)) + mode = UNSORTED; + + return mode; +} + +template <class T> +bool (*_sortrows_comparator (sortmode mode, + const Array<T>& /* a */, bool /* allow_chk */)) (T, T) +{ + if (mode == ASCENDING) + return octave_sort<T>::ascending_compare; + else if (mode == DESCENDING) + return octave_sort<T>::descending_compare; + else + return 0; +} + +template <class T> +Array<octave_idx_type> +Array<T>::sort_rows_idx (sortmode mode) const +{ + Array<octave_idx_type> idx; + + octave_sort<T> lsort; + + lsort.set_compare (_sortrows_comparator (mode, *this, true)); + + octave_idx_type r = rows (), c = cols (); + + idx = Array<octave_idx_type> (r); + + lsort.sort_rows (data (), idx.fortran_vec (), r, c); + + return idx; +} + + +template <class T> +sortmode +Array<T>::is_sorted_rows (sortmode mode) const +{ + octave_sort<T> lsort; + + octave_idx_type r = rows (), c = cols (); + + if (r <= 1 || c == 0) + return mode ? mode : ASCENDING; + + if (! mode) + { + // Auto-detect mode. + bool (*compare) (T, T) = _sortrows_comparator (ASCENDING, *this, false); + + octave_idx_type i; + for (i = 0; i < cols (); i++) + { + T l = elem (0, i), u = elem (rows () - 1, i); + if (compare (l, u)) + { + if (mode == DESCENDING) + { + mode = UNSORTED; + break; + } + else + mode = ASCENDING; + } + else if (compare (u, l)) + { + if (mode == ASCENDING) + { + mode = UNSORTED; + break; + } + else + mode = DESCENDING; + } + } + if (! mode && i == cols ()) + mode = ASCENDING; + } + + if (mode) + { + lsort.set_compare (_sortrows_comparator (mode, *this, false)); + + if (! lsort.is_sorted_rows (data (), r, c)) + mode = UNSORTED; + } + + return mode; + +} + +#define INSTANTIATE_ARRAY_SORT(T) template class octave_sort<T>; + +#define NO_INSTANTIATE_ARRAY_SORT(T) \ + \ +template <> Array<T> \ +Array<T>::sort (octave_idx_type, sortmode) const { return *this; } \ + \ +template <> Array<T> \ +Array<T>::sort (Array<octave_idx_type> &sidx, octave_idx_type, sortmode) const \ +{ sidx = Array<octave_idx_type> (); return *this; } \ + \ +template <> sortmode \ +Array<T>::is_sorted (sortmode) const \ +{ return UNSORTED; } \ + \ +template <> \ +bool (*_sortrows_comparator (sortmode, \ + const Array<T>&, bool)) (T, T) \ +{ return 0; } \ + \ +template <> Array<octave_idx_type> \ +Array<T>::sort_rows_idx (sortmode) const \ +{ return Array<octave_idx_type> (); } \ + \ +template <> sortmode \ +Array<T>::is_sorted_rows (sortmode) const \ +{ return UNSORTED; } \ + + + +template <class T> Array<T> Array<T>::diag (octave_idx_type k) const { @@ -2342,6 +2517,9 @@ // << prefix << "cols: " << cols () << "\n"; } +#define INSTANTIATE_ARRAY(T, API) \ + template class API Array<T> + /* ;;; Local Variables: *** ;;; mode: C++ ***
--- a/liboctave/Array.h +++ b/liboctave/Array.h @@ -554,6 +554,15 @@ Array<T> sort (Array<octave_idx_type> &sidx, octave_idx_type dim = 0, sortmode mode = ASCENDING) const; + // Ordering is auto-detected or can be specified. + sortmode is_sorted (sortmode mode = UNSORTED) const; + + // Sort by rows returns only indices. + Array<octave_idx_type> sort_rows_idx (sortmode mode = ASCENDING) const; + + // Ordering is auto-detected or can be specified. + sortmode is_sorted_rows (sortmode mode = UNSORTED) const; + Array<T> diag (octave_idx_type k = 0) const; template <class U, class F> @@ -578,30 +587,6 @@ } }; -#define INSTANTIATE_ARRAY(T, API) \ - template class API Array<T> - -// FIXME -- these are here for compatibility. In the current -// implementation, only homogeneous array assignments are actually -// instantiated. I think heterogeneous indexed assignments are rare -// enough to be implemented via conversion first. This decision may -// still be revised, that's why these macros stay here. -#define INSTANTIATE_ARRAY_AND_ASSIGN(T, API) \ - INSTANTIATE_ARRAY(T, API) - -#define INSTANTIATE_ARRAY_ASSIGN(LT, RT, API) - // do nothing - -#define INSTANTIATE_ARRAY_SORT(T) \ - template class octave_sort<T>; \ - -#define NO_INSTANTIATE_ARRAY_SORT(T) \ - template <> Array<T> Array<T>::sort \ - (octave_idx_type, sortmode) const { return *this; } \ - template <> Array<T> Array<T>::sort (Array<octave_idx_type> &sidx, \ - octave_idx_type, sortmode) const \ - { sidx = Array<octave_idx_type> (); return *this; } - #endif /*
--- a/liboctave/ChangeLog +++ b/liboctave/ChangeLog @@ -1,3 +1,23 @@ +2009-02-11 Jaroslav Hajek <highegg@gmail.com> + + * oct-sort.cc (octave_sort<T>::is_sorted, octave_sort<T>::sort_rows, + octave_sort<T>::is_sorted_rows): New methods. + * oct-sort.h: Declare them. + + * Array.cc (Array<T>::is_sorted): New method. + (INSTANTIATE_ARRAY_SORT, NO_INSTANTIATE_ARRAY_SORT, + INSTANTIATE_ARRAY_AND_ASSIGN, INSTANTIATE_ARRAY): Move macros here. + * Array.h: Reflect changes. + + * dim-vector.h (dim_vector::is_vector): New method. + * Array-C.cc, Array-fC.cc: Override _sort_isnan, don't check for + NaN in default comparators. Provide NaN-safe comparators, override + _sortrows_comparator. + * Array-d.cc, Array-f.cc: Provide NaN-safe comparators, override + _sortrows_comparator. + * Range.cc (Range::is_sorted): New method. + * Range.h: Declare it. + 2009-02-09 Jaroslav Hajek <highegg@gmail.com> * oct-sort.cc (octave_sort<T>): Rewrite for optimizations. Allow
--- a/liboctave/CmplxQR.cc +++ b/liboctave/CmplxQR.cc @@ -293,7 +293,7 @@ octave_idx_type k = q.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, ASCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++) @@ -365,7 +365,7 @@ octave_idx_type k = q.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, DESCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++) @@ -590,7 +590,7 @@ octave_idx_type n = r.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, ASCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++) @@ -636,7 +636,7 @@ octave_idx_type n = r.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, DESCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++)
--- a/liboctave/Range.cc +++ b/liboctave/Range.cc @@ -223,8 +223,6 @@ retval.sort_internal (true); else if (mode == DESCENDING) retval.sort_internal (false); - else - abort (); } else if (dim != 0) (*current_liboctave_error_handler) ("Range::sort: invalid dimension"); @@ -244,8 +242,6 @@ retval.sort_internal (sidx, true); else if (mode == DESCENDING) retval.sort_internal (sidx, false); - else - abort (); } else if (dim != 0) (*current_liboctave_error_handler) ("Range::sort: invalid dimension"); @@ -253,6 +249,17 @@ return retval; } +sortmode +Range::is_sorted (sortmode mode) const +{ + if (rng_nelem > 1 && rng_inc < 0) + mode = (mode == ASCENDING) ? UNSORTED : DESCENDING; + else if (rng_nelem > 1 && rng_inc > 0) + mode = (mode == DESCENDING) ? UNSORTED : ASCENDING; + else + mode = mode ? mode : ASCENDING; +} + std::ostream& operator << (std::ostream& os, const Range& a) {
--- a/liboctave/Range.h +++ b/liboctave/Range.h @@ -77,6 +77,8 @@ Range sort (Array<octave_idx_type>& sidx, octave_idx_type dim = 0, sortmode mode = ASCENDING) const; + sortmode is_sorted (sortmode mode = ASCENDING) const; + void set_base (double b) { if (rng_base != b)
--- a/liboctave/dbleQR.cc +++ b/liboctave/dbleQR.cc @@ -289,7 +289,7 @@ octave_idx_type k = q.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, ASCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++) @@ -361,7 +361,7 @@ octave_idx_type k = q.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, DESCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++) @@ -584,7 +584,7 @@ octave_idx_type n = r.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, ASCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++) @@ -630,7 +630,7 @@ octave_idx_type n = r.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, DESCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++)
--- a/liboctave/dim-vector.h +++ b/liboctave/dim-vector.h @@ -503,6 +503,12 @@ return retval; } } + + bool is_vector (void) const + { + return (length () == 2 && (elem (0) == 1 || elem (1) == 1)); + } + }; static inline bool
--- a/liboctave/fCmplxQR.cc +++ b/liboctave/fCmplxQR.cc @@ -293,7 +293,7 @@ octave_idx_type k = q.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, ASCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++) @@ -364,7 +364,7 @@ octave_idx_type k = q.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, DESCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++) @@ -589,7 +589,7 @@ octave_idx_type n = r.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, ASCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++) @@ -635,7 +635,7 @@ octave_idx_type n = r.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, DESCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++)
--- a/liboctave/floatQR.cc +++ b/liboctave/floatQR.cc @@ -289,7 +289,7 @@ octave_idx_type k = q.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, ASCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++) @@ -361,7 +361,7 @@ octave_idx_type k = q.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, DESCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++) @@ -584,7 +584,7 @@ octave_idx_type n = r.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, ASCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++) @@ -630,7 +630,7 @@ octave_idx_type n = r.columns (); Array<octave_idx_type> jsi; - Array<octave_idx_type> js = j.sort (jsi, DESCENDING); + Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING); octave_idx_type nj = js.length (); bool dups = false; for (octave_idx_type i = 0; i < nj - 1; i++)
--- a/liboctave/oct-sort.cc +++ b/liboctave/oct-sort.cc @@ -97,25 +97,37 @@ #include <cassert> #include <algorithm> #include <cstring> +#include <stack> #include "lo-mappers.h" #include "quit.h" #include "oct-sort.h" +#include "oct-locbuf.h" template <class T> octave_sort<T>::octave_sort (void) : compare (ascending_compare) { merge_init (); - merge_getmem (1024); } template <class T> octave_sort<T>::octave_sort (bool (*comp) (T, T)) : compare (comp) { merge_init (); - merge_getmem (1024); } - + +template <class T> +void +octave_sort<T>::set_compare (sortmode mode) +{ + if (mode == ASCENDING) + compare = ascending_compare; + else if (mode == DESCENDING) + compare = descending_compare; + else + compare = 0; +} + template <class T> template <class Comp> void @@ -1508,6 +1520,7 @@ void octave_sort<T>::sort (T *data, octave_idx_type nel) { + merge_getmem (1024); #ifdef INLINE_ASCENDING_SORT if (compare == ascending_compare) sort (data, nel, std::less<T> ()); @@ -1515,7 +1528,7 @@ #endif #ifdef INLINE_DESCENDING_SORT if (compare == descending_compare) - sort (data, nel, std::greater<T> ()); + sort (data, nel, std::greater<T> ()); else #endif if (compare) @@ -1526,6 +1539,7 @@ void octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel) { + merge_getmemi (1024); #ifdef INLINE_ASCENDING_SORT if (compare == ascending_compare) sort (data, idx, nel, std::less<T> ()); @@ -1533,13 +1547,220 @@ #endif #ifdef INLINE_DESCENDING_SORT if (compare == descending_compare) - sort (data, idx, nel, std::greater<T> ()); + sort (data, idx, nel, std::greater<T> ()); else #endif if (compare) sort (data, idx, nel, compare); } +template <class T> template <class Comp> +bool +octave_sort<T>::is_sorted (const T *data, octave_idx_type nel, Comp comp) +{ + const T *end = data + nel; + if (data != end) + { + const T *next = data; + while (++next != end) + { + if (comp (*next, *data)) + break; + data = next; + } + data = next; + } + + return data == end; +} + +template <class T> +bool +octave_sort<T>::is_sorted (const T *data, octave_idx_type nel) +{ + bool retval = false; +#ifdef INLINE_ASCENDING_SORT + if (compare == ascending_compare) + retval = is_sorted (data, nel, std::less<T> ()); + else +#endif +#ifdef INLINE_DESCENDING_SORT + if (compare == descending_compare) + retval = is_sorted (data, nel, std::greater<T> ()); + else +#endif + if (compare) + retval = is_sorted (data, nel, compare); + + return retval; +} + +// FIXME: is there really no way to make this local to the following function? +struct sortrows_run_t +{ + sortrows_run_t (octave_idx_type c, octave_idx_type o, octave_idx_type n) + : col (c), ofs (o), nel (n) { } + octave_idx_type col, ofs, nel; +}; + + +template <class T> template <class Comp> +void +octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx, + octave_idx_type rows, octave_idx_type cols, + Comp comp) +{ + OCTAVE_LOCAL_BUFFER (T, buf, rows); + for (octave_idx_type i = 0; i < rows; i++) + idx[i] = i; + + if (cols == 0 || rows <= 1) + return; + + + // This is a breadth-first traversal. + typedef sortrows_run_t run_t; + std::stack<run_t> runs; + + runs.push (run_t (0, 0, rows)); + + while (! runs.empty ()) + { + octave_idx_type col = runs.top ().col; + octave_idx_type ofs = runs.top ().ofs; + octave_idx_type nel = runs.top ().nel; + runs.pop (); + assert (nel > 1); + + T *lbuf = buf + ofs; + const T *ldata = data + rows*col; + octave_idx_type *lidx = idx + ofs; + + // Gather. + for (octave_idx_type i = 0; i < nel; i++) + lbuf[i] = ldata[lidx[i]]; + + // Sort. + sort (lbuf, lidx, nel, comp); + + // Identify constant runs and schedule subsorts. + if (col < cols-1) + { + octave_idx_type lst = 0; + for (octave_idx_type i = 0; i < nel; i++) + { + if (comp (lbuf[lst], lbuf[i])) + { + if (i > lst + 1) + runs.push (run_t (col+1, lst, i - lst)); + lst = i; + } + } + if (nel > lst + 1) + runs.push (run_t (col+1, lst, nel - lst)); + } + } +} + +template <class T> +void +octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx, + octave_idx_type rows, octave_idx_type cols) +{ +#ifdef INLINE_ASCENDING_SORT + if (compare == ascending_compare) + sort_rows (data, idx, rows, cols, std::less<T> ()); + else +#endif +#ifdef INLINE_DESCENDING_SORT + if (compare == descending_compare) + sort_rows (data, idx, rows, cols, std::greater<T> ()); + else +#endif + if (compare) + sort_rows (data, idx, rows, cols, compare); +} + +template <class T> template <class Comp> +bool +octave_sort<T>::is_sorted_rows (const T *data, octave_idx_type rows, + octave_idx_type cols, Comp comp) +{ + if (rows <= 1 || cols == 0) + return true; + + // This is a breadth-first traversal. + const T *lastrow = data + rows*(cols - 1); + typedef std::pair<const T *, octave_idx_type> run_t; + std::stack<run_t> runs; + + bool sorted = true; + runs.push (run_t (data, rows)); + while (sorted && ! runs.empty ()) + { + const T *lo = runs.top ().first; + octave_idx_type n = runs.top ().second; + runs.pop (); + if (lo < lastrow) + { + // Not the final column. + assert (n > 1); + const T *hi = lo + n, *lst = lo; + for (lo++; lo < hi; lo++) + { + if (comp (*lst, *lo)) + { + if (lo > lst + 1) + runs.push (run_t (lst + rows, lo - lst)); + lst = lo; + } + else if (comp (*lo, *lst)) + break; + + } + if (lo == hi) + { + if (lo > lst + 1) + runs.push (run_t (lst + rows, lo - lst)); + } + else + { + sorted = false; + break; + } + } + else + // The final column - use fast code. + sorted = is_sorted (lo, n, comp); + } + + return sorted; +} + +template <class T> +bool +octave_sort<T>::is_sorted_rows (const T *data, octave_idx_type rows, + octave_idx_type cols) +{ + bool retval = false; + +#ifdef INLINE_ASCENDING_SORT + if (compare == ascending_compare) + retval = is_sorted_rows (data, rows, cols, std::less<T> ()); + else +#endif +#ifdef INLINE_DESCENDING_SORT + if (compare == descending_compare) + retval = is_sorted_rows (data, rows, cols, std::greater<T> ()); + else +#endif + if (compare) + retval = is_sorted_rows (data, rows, cols, compare); + + return retval; +} + + template <class T> bool octave_sort<T>::ascending_compare (T x, T y)
--- a/liboctave/oct-sort.h +++ b/liboctave/oct-sort.h @@ -97,7 +97,7 @@ #define MERGESTATE_TEMP_SIZE 1024 // Enum for type of sort function -enum sortmode { ASCENDING, DESCENDING }; +enum sortmode { UNSORTED = 0, ASCENDING, DESCENDING }; template <class T> class @@ -113,10 +113,26 @@ void set_compare (bool (*comp) (T, T)) { compare = comp; } + void set_compare (sortmode mode); + + // Sort an array in-place. void sort (T *data, octave_idx_type nel); + // Ditto, but also permute the passed indices (may not be valid indices). void sort (T *data, octave_idx_type *idx, octave_idx_type nel); + // Check whether an array is sorted. + bool is_sorted (const T *data, octave_idx_type nel); + + // Sort a matrix by rows, return a permutation + // vector. + void sort_rows (const T *data, octave_idx_type *idx, + octave_idx_type rows, octave_idx_type cols); + + // Determine whether a matrix (as a contiguous block) is sorted by rows. + bool is_sorted_rows (const T *data, + octave_idx_type rows, octave_idx_type cols); + static bool ascending_compare (T, T); static bool descending_compare (T, T); @@ -241,6 +257,18 @@ template <class Comp> void sort (T *data, octave_idx_type *idx, octave_idx_type nel, Comp comp); + template <class Comp> + bool is_sorted (const T *data, octave_idx_type nel, Comp comp); + + template <class Comp> + void sort_rows (const T *data, octave_idx_type *idx, + octave_idx_type rows, octave_idx_type cols, + Comp comp); + + template <class Comp> + bool is_sorted_rows (const T *data, octave_idx_type rows, + octave_idx_type cols, Comp comp); + }; template <class T>
--- a/scripts/ChangeLog +++ b/scripts/ChangeLog @@ -1,3 +1,8 @@ +2009-02-11 Jaroslav Hajek <highegg@gmail.com> + + * general/sortrows.m: Employ __sortrows_idx__ when applicable, + gripe for sparse matrices. + 2009-02-11 John W. Eaton <jwe@octave.org> * miscellaneous/news.m: Look in octetcdir for NEWS file.
--- a/scripts/general/sortrows.m +++ b/scripts/general/sortrows.m @@ -1,4 +1,5 @@ ## Copyright (C) 2000, 2005, 2007 Daniel Calvelo +## Copyright (C) 2009 Jaroslav Hajek ## ## This file is part of Octave. ## @@ -32,10 +33,20 @@ default_mode = "ascend"; other_mode = "descend"; - if (nargin < 2) - indices = [1:size(m,2)]'; - mode(1:size(m,2)) = {default_mode}; + + if (issparse (m)) + error ("sortrows: sparse matrices not yet supported"); + endif + + ## If the sort is homogeneous, we use the built-in faster algorithm. + if (nargin == 1) + i = __sortrows_idx__ (m, default_mode); + elseif (all (c > 0)) + i = __sortrows_idx__ (m(:,c), default_mode); + elseif (all (c < 0)) + i = __sortrows_idx__ (m(:,c), other_mode); else + ## Otherwise, fall back to the old algorithm for ii = 1:length (c); if (c(ii) < 0) mode{ii} = other_mode; @@ -44,30 +55,21 @@ endif endfor indices = abs(c(:)); - endif - if (ischar (m)) - s = toascii (m); - else - s = m; + ## Since sort is 'stable' the order of identical elements will be + ## preserved, so by traversing the sort indices in reverse order we + ## will make sure that identical elements in index i are subsorted by + ## index j. + indices = flipud (indices); + mode = flipud (mode'); + i = [1:size(m,1)]'; + for ii = 1:length (indices); + [trash, idx] = sort (m(i, indices(ii)), mode{ii}); + i = i(idx); + endfor endif - ## Since sort is 'stable' the order of identical elements will be - ## preserved, so by traversing the sort indices in reverse order we - ## will make sure that identical elements in index i are subsorted by - ## index j. - indices = flipud (indices); - mode = flipud (mode'); - i = [1:size(m,1)]'; - for ii = 1:length (indices); - [trash, idx] = sort (s(:,indices(ii)), mode{ii}); - s = s(idx,:); - i = i(idx); - endfor - - if (ischar (m)) - s = char (s); - endif + s = m(i,:); endfunction
--- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,3 +1,25 @@ +2009-02-11 Jaroslav Hajek <highegg@gmail.com> + + * ov.h (octave_value::issorted, octave_value::sortrows_idx, + octave_value::issorted_rows): New methods. + * ov.cc (octave_base_value::issorted, octave_base_value::sortrows_idx, + octave_base_value::issorted_rows): New methods. + * ov.cc: Declare them. + + * ov-base-mat.h (octave_base_matrix::issorted, octave_base_matrix::sortrows_idx, + octave_base_matrix::issorted_rows): New methods. + + * ov-base-diag.h (octave_base_diag::issorted, octave_base_diag::sortrows_idx, + octave_base_diag::issorted_rows): New methods. + + * ov-perm.h (octave_perm_matrix::issorted, octave_perm_matrix::sortrows_idx, + octave_perm_matrix::issorted_rows): New methods. + + * ov-range.h (octave_range::issorted, octave_range::sortrows_idx, + octave_range::issorted_rows): New methods. + + * data.cc (F__sortrows_idx__, Fissorted): New defuns. + 2009-02-11 John W. Eaton <jwe@octave.org> * toplev.cc (octave_config_info): Add octetcdir to the struct.
--- a/src/TEMPLATE-INST/Array-sym.cc +++ b/src/TEMPLATE-INST/Array-sym.cc @@ -34,6 +34,8 @@ typedef symbol_record* symbol_record_ptr; +NO_INSTANTIATE_ARRAY_SORT (symbol_record_ptr); + INSTANTIATE_ARRAY (symbol_record_ptr, OCTINTERP_API); /*
--- a/src/TEMPLATE-INST/Array-tc.cc +++ b/src/TEMPLATE-INST/Array-tc.cc @@ -58,9 +58,7 @@ INSTANTIATE_ARRAY_SORT (octave_value); -template class OCTINTERP_API Array<octave_value>; - -INSTANTIATE_ARRAY_ASSIGN (octave_value, octave_value, OCTINTERP_API); +INSTANTIATE_ARRAY (octave_value, OCTINTERP_API); template class OCTINTERP_API Array2<octave_value>;
--- a/src/data.cc +++ b/src/data.cc @@ -2,6 +2,7 @@ Copyright (C) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007 John W. Eaton +Copyright (C) 2009 Jaroslav Hajek This file is part of Octave. @@ -5573,6 +5574,106 @@ */ +DEFUN (__sortrows_idx__, args, , + "-*- texinfo -*-\n\ +@deftypefn {Function File} {} __sortrows_idx__ (@var{a}, @var{mode})\n\ +Sort the rows of the matrix @var{a} according to the order specified\n\ +by @var{mode}, which can either be `ascend' or `descend'.\n\ +Returns the index vector.\n\ +\n\ +This function does not yet support sparse matrices.\n\ +@end deftypefn\n") +{ + octave_value retval; + + int nargin = args.length (); + sortmode smode = ASCENDING; + + if (nargin < 1 || nargin > 2 || (nargin == 2 && ! args(1).is_string ())) + { + print_usage (); + return retval; + } + + if (nargin > 1) + { + std::string mode = args(1).string_value(); + if (mode == "ascend") + smode = ASCENDING; + else if (mode == "descend") + smode = DESCENDING; + else + { + error ("__sortrows_idx__: mode must be either \"ascend\" or \"descend\""); + return retval; + } + } + + octave_value arg = args(0); + + if (arg.is_sparse_type ()) + error ("__sortrows_idx__: sparse matrices not yet supported"); + if (arg.ndims () == 2) + { + Array<octave_idx_type> idx = arg.sortrows_idx (smode); + + retval = NDArray (idx, true); + } + else + error ("__sortrows_idx__: needs a 2-dimensional object"); + + return retval; +} + +DEFUN (issorted, args, , + "-*- texinfo -*-\n\ +@deftypefn {Function File} {} issorted (@var{a}, @var{rows})\n\ +Returns true if the array is sorted, ascending or descending.\n\ +NaNs are treated is by @code{sort}. If @var{rows} is supplied and\n\ +has the value \"rows\", checks whether the array is sorted by rows\n\ +as if output by @code{sortrows} (with no options).\n\ +\n\ +This function does not yet support sparse matrices.\n\ +@seealso{sortrows, sort}\n\ +@end deftypefn\n") +{ + octave_value retval; + + int nargin = args.length (); + + if (nargin == 1) + { + octave_value arg = args(0); + if (arg.dims ().is_vector ()) + retval = args(0).issorted () != UNSORTED; + else + error ("issorted: needs a vector"); + } + else if (nargin == 2) + { + if (args(1).is_string () && args(1).string_value () == "rows") + { + octave_value arg = args(0); + sortmode smode = ASCENDING; + + if (arg.is_sparse_type ()) + error ("issorted: sparse matrices not yet supported"); + if (arg.ndims () == 2) + retval = arg.issorted_rows (smode) != UNSORTED; + else + error ("issorted: needs a 2-dimensional object"); + } + else + error ("issorted: second argument must be \"rows\""); + } + else + print_usage (); + + return retval; +} + + + /* ;;; Local Variables: *** ;;; mode: C++ ***
--- a/src/ov-base-diag.h +++ b/src/ov-base-diag.h @@ -106,6 +106,15 @@ sortmode mode = ASCENDING) const { return to_dense ().sort (sidx, dim, mode); } + sortmode issorted (sortmode mode = UNSORTED) const + { return to_dense ().issorted (mode); } + + Array<octave_idx_type> sortrows_idx (sortmode mode = ASCENDING) const + { return to_dense ().sortrows_idx (mode); } + + sortmode issorted_rows (sortmode mode = UNSORTED) const + { return to_dense ().issorted_rows (mode); } + bool is_matrix_type (void) const { return true; } bool is_numeric_type (void) const { return true; }
--- a/src/ov-base-mat.h +++ b/src/ov-base-mat.h @@ -124,6 +124,15 @@ sortmode mode = ASCENDING) const { return octave_value (matrix.sort (sidx, dim, mode)); } + sortmode issorted (sortmode mode = UNSORTED) const + { return matrix.is_sorted (mode); } + + Array<octave_idx_type> sortrows_idx (sortmode mode = ASCENDING) const + { return matrix.sort_rows_idx (mode); } + + sortmode issorted_rows (sortmode mode = UNSORTED) const + { return matrix.is_sorted_rows (mode); } + bool is_matrix_type (void) const { return true; } bool is_numeric_type (void) const { return true; }
--- a/src/ov-base-scalar.h +++ b/src/ov-base-scalar.h @@ -108,6 +108,15 @@ return octave_value (scalar); } + sortmode issorted (sortmode mode = UNSORTED) const + { return mode ? mode : ASCENDING; } + + Array<octave_idx_type> sortrows_idx (sortmode) const + { return Array<octave_idx_type> (1, 0); } + + sortmode issorted_rows (sortmode mode = UNSORTED) const + { return mode ? mode : ASCENDING; } + MatrixType matrix_type (void) const { return typ; } MatrixType matrix_type (const MatrixType& _typ) const { MatrixType ret = typ; typ = _typ; return ret; }
--- a/src/ov-base-sparse.h +++ b/src/ov-base-sparse.h @@ -126,6 +126,9 @@ sortmode mode = ASCENDING) const { return octave_value (matrix.sort (sidx, dim, mode)); } + sortmode issorted (sortmode mode = UNSORTED) const + { return full_value ().issorted (mode); } + MatrixType matrix_type (void) const { return typ; } MatrixType matrix_type (const MatrixType& _typ) const { MatrixType ret = typ; typ = _typ; return ret; }
--- a/src/ov-base.cc +++ b/src/ov-base.cc @@ -978,6 +978,30 @@ return octave_value(); } +sortmode +octave_base_value::issorted (sortmode) const +{ + gripe_wrong_type_arg ("octave_base_value::issorted ()", type_name ()); + + return UNSORTED; +} + +Array<octave_idx_type> +octave_base_value::sortrows_idx (sortmode) const +{ + gripe_wrong_type_arg ("octave_base_value::sortrows_idx ()", type_name ()); + + return Array<octave_idx_type> (); +} + +sortmode +octave_base_value::issorted_rows (sortmode) const +{ + gripe_wrong_type_arg ("octave_base_value::issorted_rows ()", type_name ()); + + return UNSORTED; +} + #define UNDEFINED_MAPPER(F) \ octave_value \ octave_base_value::F (void) const \
--- a/src/ov-base.h +++ b/src/ov-base.h @@ -515,6 +515,12 @@ octave_idx_type dim = 0, sortmode mode = ASCENDING) const; + virtual sortmode issorted (sortmode mode = UNSORTED) const; + + virtual Array<octave_idx_type> sortrows_idx (sortmode mode = ASCENDING) const; + + virtual sortmode issorted_rows (sortmode mode = UNSORTED) const; + virtual void lock (void); virtual void unlock (void);
--- a/src/ov-perm.h +++ b/src/ov-perm.h @@ -93,6 +93,15 @@ sortmode mode = ASCENDING) const { return to_dense ().sort (sidx, dim, mode); } + sortmode issorted (sortmode mode = UNSORTED) const + { return to_dense ().issorted (mode); } + + Array<octave_idx_type> sortrows_idx (sortmode mode = ASCENDING) const + { return to_dense ().sortrows_idx (mode); } + + sortmode issorted_rows (sortmode mode = UNSORTED) const + { return to_dense ().issorted_rows (mode); } + bool is_perm_matrix (void) const { return true; } bool is_matrix_type (void) const { return true; }
--- a/src/ov-range.h +++ b/src/ov-range.h @@ -140,6 +140,15 @@ sortmode mode = ASCENDING) const { return range.sort (sidx, dim, mode); } + sortmode issorted (sortmode mode = UNSORTED) const + { return range.is_sorted (mode); } + + Array<octave_idx_type> sortrows_idx (sortmode) const + { return Array<octave_idx_type> (1, 0); } + + sortmode issorted_rows (sortmode mode = UNSORTED) const + { return mode ? mode : ASCENDING; } + bool is_real_type (void) const { return true; } bool is_double_type (void) const { return true; }
--- a/src/ov.h +++ b/src/ov.h @@ -996,6 +996,15 @@ sortmode mode = ASCENDING) const { return rep->sort (sidx, dim, mode); } + sortmode issorted (sortmode mode = UNSORTED) const + { return rep->issorted (mode); } + + Array<octave_idx_type> sortrows_idx (sortmode mode = ASCENDING) const + { return rep->sortrows_idx (mode); } + + sortmode issorted_rows (sortmode mode = UNSORTED) const + { return rep->issorted_rows (mode); } + void lock (void) { rep->lock (); } void unlock (void) { rep->unlock (); }