Mercurial > hg > octave-terminal
changeset 7234:6992e9face25
[project @ 2007-11-30 20:45:42 by jwe]
author | jwe |
---|---|
date | Fri, 30 Nov 2007 20:45:42 +0000 |
parents | c92f452c385f |
children | ee0820d8b4ac |
files | liboctave/ChangeLog liboctave/oct-sort.cc liboctave/oct-sort.h src/ChangeLog src/DLD-FUNCTIONS/sort.cc |
diffstat | 5 files changed, 220 insertions(+), 199 deletions(-) [+] |
line wrap: on
line diff
--- a/liboctave/ChangeLog +++ b/liboctave/ChangeLog @@ -1,5 +1,7 @@ 2007-11-30 John W. Eaton <jwe@octave.org> + * oct-sort.cc, oct-sort.h: Style fixes. + * lo-math.h: New file. * Makefile.in (INCLUDES): Add it to the list. * liboctave/Array2.h, liboctave/ArrayN.h, liboctave/CmplxDET.cc,
--- a/liboctave/oct-sort.cc +++ b/liboctave/oct-sort.cc @@ -90,12 +90,12 @@ #include "quit.h" #include "oct-sort.h" -#define IFLT(a,b) if (compare == NULL ? ((a) < (b)) : compare ((a), (b))) +#define IFLT(a,b) if (compare ? compare ((a), (b)) : ((a) < (b))) template <class T> -octave_sort<T>::octave_sort (void) : compare (NULL) +octave_sort<T>::octave_sort (void) : compare (0) { - merge_init (); + merge_init (); merge_getmem (1024); } @@ -109,7 +109,7 @@ /* Reverse a slice of a list in place, from lo up to (exclusive) hi. */ template <class T> void -octave_sort<T>::reverse_slice(T *lo, T *hi) +octave_sort<T>::reverse_slice (T *lo, T *hi) { --hi; while (lo < hi) @@ -187,7 +187,7 @@ */ template <class T> int -octave_sort<T>::count_run(T *lo, T *hi, int *descending) +octave_sort<T>::count_run (T *lo, T *hi, int *descending) { int n; @@ -244,7 +244,7 @@ */ template <class T> int -octave_sort<T>::gallop_left(T key, T *a, int n, int hint) +octave_sort<T>::gallop_left (T key, T *a, int n, int hint) { int ofs; int lastofs; @@ -316,6 +316,7 @@ else ofs = m; /* key <= a[m] */ } + return ofs; } @@ -335,7 +336,7 @@ */ template <class T> int -octave_sort<T>::gallop_right(T key, T *a, int n, int hint) +octave_sort<T>::gallop_right (T key, T *a, int n, int hint) { int ofs; int lastofs; @@ -407,15 +408,16 @@ else lastofs = m+1; /* a[m] <= key */ } + return ofs; } /* Conceptually a MergeState's constructor. */ template <class T> void -octave_sort<T>::merge_init(void) +octave_sort<T>::merge_init (void) { - ms.a = NULL; + ms.a = 0; ms.alloced = 0; ms.n = 0; ms.min_gallop = MIN_GALLOP; @@ -427,16 +429,16 @@ */ template <class T> void -octave_sort<T>::merge_freemem(void) +octave_sort<T>::merge_freemem (void) { if (ms.a) free (ms.a); ms.alloced = 0; - ms.a = NULL; + ms.a = 0; } static inline int -roundupsize(int n) +roundupsize (int n) { unsigned int nbits = 3; unsigned int n2 = static_cast<unsigned int> (n) >> 8; @@ -463,10 +465,12 @@ * even with this scheme, although it requires much longer lists to * provoke them than it used to). */ - while (n2) { - n2 >>= 3; - nbits += 3; - } + while (n2) + { + n2 >>= 3; + nbits += 3; + } + return ((n >> nbits) + 1) << nbits; } @@ -475,27 +479,28 @@ */ template <class T> int -octave_sort<T>::merge_getmem(int need) +octave_sort<T>::merge_getmem (int need) { if (need <= ms.alloced) return 0; - need = roundupsize(need); + need = roundupsize (need); /* Don't realloc! That can cost cycles to copy the old data, but * we don't care what's in the block. */ - merge_freemem( ); + merge_freemem (); ms.a = static_cast <T *> (malloc (need * sizeof (T))); - if (ms.a) { - ms.alloced = need; - return 0; - } - merge_freemem( ); /* reset to sane state */ + if (ms.a) + { + ms.alloced = need; + return 0; + } + merge_freemem (); /* reset to sane state */ + return -1; } -#define MERGE_GETMEM(NEED) ((NEED) <= ms.alloced ? 0 : \ - merge_getmem(NEED)) +#define MERGE_GETMEM(NEED) ((NEED) <= ms.alloced ? 0 : merge_getmem (NEED)) /* Merge the na elements starting at pa with the nb elements starting at pb * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. @@ -505,16 +510,16 @@ */ template <class T> int -octave_sort<T>::merge_lo(T *pa, int na, T *pb, int nb) +octave_sort<T>::merge_lo (T *pa, int na, T *pb, int nb) { int k; T *dest; int result = -1; /* guilty until proved innocent */ int min_gallop = ms.min_gallop; - if (MERGE_GETMEM(na) < 0) + if (MERGE_GETMEM (na) < 0) return -1; - memcpy(ms.a, pa, na * sizeof(T)); + memcpy (ms.a, pa, na * sizeof (T)); dest = pa; pa = ms.a; @@ -525,103 +530,112 @@ if (na == 1) goto CopyB; - for (;;) { - int acount = 0; /* # of times A won in a row */ - int bcount = 0; /* # of times B won in a row */ + for (;;) + { + int acount = 0; /* # of times A won in a row */ + int bcount = 0; /* # of times B won in a row */ + + /* Do the straightforward thing until (if ever) one run + * appears to win consistently. + */ + for (;;) + { - /* Do the straightforward thing until (if ever) one run - * appears to win consistently. - */ - for (;;) { + IFLT (*pb, *pa) + { + *dest++ = *pb++; + ++bcount; + acount = 0; + --nb; + if (nb == 0) + goto Succeed; + if (bcount >= min_gallop) + break; + } + else + { + *dest++ = *pa++; + ++acount; + bcount = 0; + --na; + if (na == 1) + goto CopyB; + if (acount >= min_gallop) + break; + } + } - IFLT (*pb, *pa) + /* One run is winning so consistently that galloping may + * be a huge win. So try that, and continue galloping until + * (if ever) neither run appears to be winning consistently + * anymore. + */ + ++min_gallop; + do { + min_gallop -= min_gallop > 1; + ms.min_gallop = min_gallop; + k = gallop_right (*pb, pa, na, 0); + acount = k; + if (k) + { + if (k < 0) + goto Fail; + memcpy (dest, pa, k * sizeof (T)); + dest += k; + pa += k; + na -= k; + if (na == 1) + goto CopyB; + /* na==0 is impossible now if the comparison + * function is consistent, but we can't assume + * that it is. + */ + if (na == 0) + goto Succeed; + } *dest++ = *pb++; - ++bcount; - acount = 0; --nb; if (nb == 0) goto Succeed; - if (bcount >= min_gallop) - break; - } - else - { + + k = gallop_left (*pa, pb, nb, 0); + bcount = k; + if (k) + { + if (k < 0) + goto Fail; + memmove (dest, pb, k * sizeof (T)); + dest += k; + pb += k; + nb -= k; + if (nb == 0) + goto Succeed; + } *dest++ = *pa++; - ++acount; - bcount = 0; --na; if (na == 1) goto CopyB; - if (acount >= min_gallop) - break; } + while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); + + ++min_gallop; /* penalize it for leaving galloping mode */ + ms.min_gallop = min_gallop; } - /* One run is winning so consistently that galloping may - * be a huge win. So try that, and continue galloping until - * (if ever) neither run appears to be winning consistently - * anymore. - */ - ++min_gallop; - do - { - min_gallop -= min_gallop > 1; - ms.min_gallop = min_gallop; - k = gallop_right(*pb, pa, na, 0); - acount = k; - if (k) - { - if (k < 0) - goto Fail; - memcpy(dest, pa, k * sizeof(T)); - dest += k; - pa += k; - na -= k; - if (na == 1) - goto CopyB; - /* na==0 is impossible now if the comparison - * function is consistent, but we can't assume - * that it is. - */ - if (na == 0) - goto Succeed; - } - *dest++ = *pb++; - --nb; - if (nb == 0) - goto Succeed; - - k = gallop_left(*pa, pb, nb, 0); - bcount = k; - if (k) { - if (k < 0) - goto Fail; - memmove(dest, pb, k * sizeof(T)); - dest += k; - pb += k; - nb -= k; - if (nb == 0) - goto Succeed; - } - *dest++ = *pa++; - --na; - if (na == 1) - goto CopyB; - } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); - ++min_gallop; /* penalize it for leaving galloping mode */ - ms.min_gallop = min_gallop; - } Succeed: result = 0; + Fail: if (na) - memcpy(dest, pa, na * sizeof(T)); + memcpy (dest, pa, na * sizeof (T)); return result; + CopyB: /* The last element of pa belongs at the end of the merge. */ - memmove(dest, pb, nb * sizeof(T)); + memmove (dest, pb, nb * sizeof (T)); dest[nb] = *pa; + return 0; } @@ -633,7 +647,7 @@ */ template <class T> int -octave_sort<T>::merge_hi(T *pa, int na, T *pb, int nb) +octave_sort<T>::merge_hi (T *pa, int na, T *pb, int nb) { int k; T *dest; @@ -642,10 +656,10 @@ T *baseb; int min_gallop = ms.min_gallop; - if (MERGE_GETMEM(nb) < 0) + if (MERGE_GETMEM (nb) < 0) return -1; dest = pb + nb - 1; - memcpy(ms.a, pb, nb * sizeof(T)); + memcpy (ms.a, pb, nb * sizeof (T)); basea = pa; baseb = ms.a; pb = ms.a + nb - 1; @@ -702,7 +716,7 @@ { min_gallop -= min_gallop > 1; ms.min_gallop = min_gallop; - k = gallop_right(*pb, basea, na, na-1); + k = gallop_right (*pb, basea, na, na-1); if (k < 0) goto Fail; k = na - k; @@ -711,7 +725,7 @@ { dest -= k; pa -= k; - memmove(dest+1, pa+1, k * sizeof(T )); + memmove (dest+1, pa+1, k * sizeof (T)); na -= k; if (na == 0) goto Succeed; @@ -721,7 +735,7 @@ if (nb == 1) goto CopyA; - k = gallop_left(*pa, baseb, nb, nb-1); + k = gallop_left (*pa, baseb, nb, nb-1); if (k < 0) goto Fail; k = nb - k; @@ -730,7 +744,7 @@ { dest -= k; pb -= k; - memcpy(dest+1, pb+1, k * sizeof(T)); + memcpy (dest+1, pb+1, k * sizeof (T)); nb -= k; if (nb == 1) goto CopyA; @@ -749,18 +763,22 @@ ++min_gallop; /* penalize it for leaving galloping mode */ ms.min_gallop = min_gallop; } + Succeed: result = 0; + Fail: if (nb) - memcpy(dest-(nb-1), baseb, nb * sizeof(T)); + memcpy (dest-(nb-1), baseb, nb * sizeof (T)); return result; + CopyA: /* The first element of pb belongs at the front of the merge. */ dest -= na; pa -= na; - memmove(dest+1, pa+1, na * sizeof(T)); + memmove (dest+1, pa+1, na * sizeof (T)); *dest = *pb; + return 0; } @@ -769,7 +787,7 @@ */ template <class T> int -octave_sort<T>::merge_at(int i) +octave_sort<T>::merge_at (int i) { T *pa, *pb; int na, nb; @@ -792,7 +810,7 @@ /* Where does b start in a? Elements in a before that can be * ignored (already in place). */ - k = gallop_right(*pb, pa, na, 0); + k = gallop_right (*pb, pa, na, 0); if (k < 0) return -1; pa += k; @@ -803,7 +821,7 @@ /* Where does a end in b? Elements in b after that can be * ignored (already in place). */ - nb = gallop_left(pa[na-1], pb, nb, nb-1); + nb = gallop_left (pa[na-1], pb, nb, nb-1); if (nb <= 0) return nb; @@ -811,9 +829,9 @@ * min(na, nb) elements. */ if (na <= nb) - return merge_lo(pa, na, pb, nb); + return merge_lo (pa, na, pb, nb); else - return merge_hi(pa, na, pb, nb); + return merge_hi (pa, na, pb, nb); } /* Examine the stack of runs waiting to be merged, merging adjacent runs @@ -828,7 +846,7 @@ */ template <class T> int -octave_sort<T>::merge_collapse(void) +octave_sort<T>::merge_collapse (void) { struct s_slice *p = ms.pending; @@ -839,17 +857,18 @@ { if (p[n-1].len < p[n+1].len) --n; - if (merge_at(n) < 0) + if (merge_at (n) < 0) return -1; } else if (p[n].len <= p[n+1].len) { - if (merge_at(n) < 0) + if (merge_at (n) < 0) return -1; } else break; } + return 0; } @@ -860,7 +879,7 @@ */ template <class T> int -octave_sort<T>::merge_force_collapse(void) +octave_sort<T>::merge_force_collapse (void) { struct s_slice *p = ms.pending; @@ -869,9 +888,10 @@ int n = ms.n - 2; if (n > 0 && p[n-1].len < p[n+1].len) --n; - if (merge_at(n) < 0) + if (merge_at (n) < 0) return -1; } + return 0; } @@ -887,14 +907,16 @@ */ template <class T> int -octave_sort<T>::merge_compute_minrun(int n) +octave_sort<T>::merge_compute_minrun (int n) { int r = 0; /* becomes 1 if any 1 bits are shifted off */ - while (n >= 64) { - r |= n & 1; - n >>= 1; - } + while (n >= 64) + { + r |= n & 1; + n >>= 1; + } + return n + r; } @@ -915,38 +937,39 @@ /* March over the array once, left to right, finding natural runs, * and extending short natural runs to minrun elements. */ - int minrun = merge_compute_minrun(nremaining); + int minrun = merge_compute_minrun (nremaining); do { int descending; int n; /* Identify next run. */ - n = count_run(lo, hi, &descending); + n = count_run (lo, hi, &descending); if (n < 0) goto fail; if (descending) - reverse_slice(lo, lo + n); + reverse_slice (lo, lo + n); /* If short, extend to min(minrun, nremaining). */ if (n < minrun) { const int force = nremaining <= minrun ? nremaining : minrun; - binarysort(lo, lo + force, lo + n); + binarysort (lo, lo + force, lo + n); n = force; } /* Push run onto pending-runs stack, and maybe merge. */ - assert(ms.n < MAX_MERGE_PENDING); + assert (ms.n < MAX_MERGE_PENDING); ms.pending[ms.n].base = lo; ms.pending[ms.n].len = n; ++ms.n; - if (merge_collapse( ) < 0) + if (merge_collapse () < 0) goto fail; /* Advance to find next run. */ lo += n; nremaining -= n; - } while (nremaining); + } + while (nremaining); - merge_force_collapse( ); + merge_force_collapse (); } fail:
--- a/liboctave/oct-sort.h +++ b/liboctave/oct-sort.h @@ -82,20 +82,18 @@ #if !defined (octave_sort_h) #define octave_sort_h 1 -/* The maximum number of entries in a MergeState's pending-runs stack. - * This is enough to sort arrays of size up to about - * 32 * phi ** MAX_MERGE_PENDING - * where phi ~= 1.618. 85 is ridiculously large enough, good for an array - * with 2**64 elements. - */ +// The maximum number of entries in a MergeState's pending-runs stack. +// This is enough to sort arrays of size up to about +// 32 * phi ** MAX_MERGE_PENDING +// where phi ~= 1.618. 85 is ridiculously large enough, good for an array +// with 2**64 elements. #define MAX_MERGE_PENDING 85 -/* When we get into galloping mode, we stay there until both runs win less - * often than MIN_GALLOP consecutive times. See listsort.txt for more info. - */ +// When we get into galloping mode, we stay there until both runs win less +// often than MIN_GALLOP consecutive times. See listsort.txt for more info. #define MIN_GALLOP 7 -/* Avoid malloc for small temp arrays. */ +// Avoid malloc for small temp arrays. #define MERGESTATE_TEMP_SIZE 1024 template <class T> @@ -116,13 +114,13 @@ private: - /* One MergeState exists on the stack per invocation of mergesort. It's just - * a convenient way to pass state around among the helper functions. - * - * DGB: This isn't needed with mergesort in a class, but it doesn't slow - * things up, and it is likely to make my life easier for any potential - * backporting of changes in the Python code. - */ + // One MergeState exists on the stack per invocation of mergesort. + // It's just a convenient way to pass state around among the helper + // functions. + // + // DGB: This isn't needed with mergesort in a class, but it doesn't + // slow things up, and it is likely to make my life easier for any + // potential backporting of changes in the Python code. struct s_slice { @@ -130,34 +128,32 @@ int len; }; - typedef struct s_MergeState + struct MergeState { - /* This controls when we get *into* galloping mode. It's initialized - * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for - * random data, and lower for highly structured data. - */ + // This controls when we get *into* galloping mode. It's + // initialized to MIN_GALLOP. merge_lo and merge_hi tend to nudge + // it higher for random data, and lower for highly structured + // data. int min_gallop; - /* 'a' is temp storage to help with merges. It contains room for - * alloced entries. - */ - T *a; /* may point to temparray below */ + // 'a' is temp storage to help with merges. It contains room for + // alloced entries. + T *a; // may point to temparray below int alloced; - /* A stack of n pending runs yet to be merged. Run #i starts at - * address base[i] and extends for len[i] elements. It's always - * true (so long as the indices are in bounds) that - * - * pending[i].base + pending[i].len == pending[i+1].base - * - * so we could cut the storage for this, but it's a minor amount, - * and keeping all the info explicit simplifies the code. - */ + // A stack of n pending runs yet to be merged. Run #i starts at + // address base[i] and extends for len[i] elements. It's always + // true (so long as the indices are in bounds) that + // + // pending[i].base + pending[i].len == pending[i+1].base + // + // so we could cut the storage for this, but it's a minor amount, + // and keeping all the info explicit simplifies the code. int n; struct s_slice pending[MAX_MERGE_PENDING]; - } MergeState; + }; - bool (*compare)(T, T); + bool (*compare) (T, T); MergeState ms; @@ -165,29 +161,29 @@ void binarysort (T *lo, T *hi, T *start); - int count_run(T *lo, T *hi, int *descending); + int count_run (T *lo, T *hi, int *descending); - int gallop_left(T key, T *a, int n, int hint); + int gallop_left (T key, T *a, int n, int hint); - int gallop_right(T key, T *a, int n, int hint); + int gallop_right (T key, T *a, int n, int hint); - void merge_init(void); + void merge_init (void); - void merge_freemem(void); + void merge_freemem (void); - int merge_getmem(int need); + int merge_getmem (int need); - int merge_lo(T *pa, int na, T *pb, int nb); + int merge_lo (T *pa, int na, T *pb, int nb); - int merge_hi(T *pa, int na, T *pb, int nb); + int merge_hi (T *pa, int na, T *pb, int nb); - int merge_at(int i); + int merge_at (int i); - int merge_collapse(void); + int merge_collapse (void); - int merge_force_collapse(void); + int merge_force_collapse (void); - int merge_compute_minrun(int n); + int merge_compute_minrun (int n); }; #endif
--- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,15 +1,15 @@ 2007-11-30 John W. Eaton <jwe@octave.org> + * DLD-FUNCTIONS/sort.cc (operator < (const Complex&, const Complex&), + operator > (const Complex&, const Complex&)): + Pass args by const reference, not value. + * src/data.cc, src/matherr.c, src/pr-output.cc, src/sysdep.cc, src/DLD-FUNCTIONS/__dsearchn__.cc, src/DLD-FUNCTIONS/minmax.cc, src/DLD-FUNCTIONS/qz.cc, src/DLD-FUNCTIONS/sort.cc, src/DLD-FUNCTIONS/tsearch.cc: Include lo-math.h instead of cmath or math.h. - * DLD-FUNCTIONS/sort.cc (ascending_compare, descending_compare, - operator < (const Complex&, const Complex&)): - Pass args by const reference, not value. - 2007-11-30 Moritz Borgmann <octave@moriborg.de> * ls-mat5.h (mat5_data_type): Delete trailing comma in enum decl.
--- a/src/DLD-FUNCTIONS/sort.cc +++ b/src/DLD-FUNCTIONS/sort.cc @@ -802,30 +802,30 @@ bool ascending_compare (Complex a, Complex b) { - return (xisnan (b) || (xabs (a) < xabs (b)) || ((xabs (a) == xabs (b)) - && (arg (a) < arg (b)))); + return (xisnan (b) || (xabs (a) < xabs (b)) + || ((xabs (a) == xabs (b)) && (arg (a) < arg (b)))); } bool -operator < (const Complex a, const Complex b) +operator < (const Complex& a, const Complex& b) { - return (xisnan (b) || (xabs (a) < xabs (b)) || ((xabs (a) == xabs (b)) - && (arg (a) < arg (b)))); + return (xisnan (b) || (xabs (a) < xabs (b)) + || ((xabs (a) == xabs (b)) && (arg (a) < arg (b)))); } template <> bool descending_compare (Complex a, Complex b) { - return (xisnan (a) || (xabs (a) > xabs (b)) || ((xabs (a) == xabs (b)) - && (arg (a) > arg (b)))); + return (xisnan (a) || (xabs (a) > xabs (b)) + || ((xabs (a) == xabs (b)) && (arg (a) > arg (b)))); } bool -operator > (const Complex a, const Complex b) +operator > (const Complex& a, const Complex& b) { - return (xisnan (a) || (xabs (a) > xabs (b)) || ((xabs (a) == xabs (b)) - && (arg (a) > arg (b)))); + return (xisnan (a) || (xabs (a) > xabs (b)) + || ((xabs (a) == xabs (b)) && (arg (a) > arg (b)))); } template <>