octave: liboctave/oct-sort.cc comparison

comparison liboctave/oct-sort.cc @ 11586:12df7854fa7c

strip trailing whitespace from source files

author	John W. Eaton <jwe@octave.org>
date	Thu, 20 Jan 2011 17:24:59 -0500
parents	fd0a3ac60b0e
children	01b7a60e2ff0

comparison

equal deleted inserted replaced

-:1473d0cf86d2
+:12df7854fa7c
 code I ripped-off.
 As required in the Python license the short description of the changes
 made are
 * convert the sorting code in listobject.cc into a generic class,
 replacing PyObject* with the type of the class T.
 * replaced usages of malloc, free, memcpy and memmove by standard C++
 new [], delete [] and std::copy and std::copy_backward. Note that replacing
 memmove by std::copy is possible if the destination starts before the source.
 If not, std::copy_backward needs to be used.
 * templatize comparison operator in most methods, provide possible dispatch
 * duplicate methods to avoid by-the-way indexed sorting
 * add methods for verifying sortedness of array
 #include "quit.h"
 #include "oct-sort.h"
 #include "oct-locbuf.h"
 template <class T>
 octave_sort<T>::octave_sort (void) :
 compare (ascending_compare), ms (0)
 {
 }
 template <class T>
 octave_sort<T>::octave_sort (compare_fcn_type comp)
 : compare (comp), ms (0)
 {
 }
 template <class T>
 octave_sort<T>::~octave_sort ()
 {
 delete ms;
 }
 template <class T>
 void
 }
 template <class T>
 template <class Comp>
 void
 octave_sort<T>::binarysort (T *data, octave_idx_type nel,
 octave_idx_type start, Comp comp)
 {
 if (start == 0)
 ++start;
 for (; start < nel; ++start)
 {
 /* set l to where *start belongs */
 octave_idx_type l = 0, r = start;
 T pivot = data[start];
 /* Invariants:
 * pivot >= all in [lo, l).
 * pivot  < all in [r, start).
 * The second is vacuously true at the start.
 */
 do
 {
 octave_idx_type p = l + ((r - l) >> 1);
 if (comp (pivot, data[p]))
 r = p;
 else
 l = p+1;
 }
 while (l < r);
 /* The invariants still hold, so pivot >= all in [lo, l) and
 pivot < all in [l, start), so pivot belongs at l.  Note
 that if there are elements equal to pivot, l points to the
 first slot after them -- that's why this sort is stable.
 }
 template <class T>
 template <class Comp>
 void
 octave_sort<T>::binarysort (T *data, octave_idx_type *idx, octave_idx_type nel,
 octave_idx_type start, Comp comp)
 {
 if (start == 0)
 ++start;
 for (; start < nel; ++start)
 {
 /* set l to where *start belongs */
 octave_idx_type l = 0, r = start;
 T pivot = data[start];
 /* Invariants:
 * pivot >= all in [lo, l).
 * pivot  < all in [r, start).
 * The second is vacuously true at the start.
 */
 do
 {
 octave_idx_type p = l + ((r - l) >> 1);
 if (comp (pivot, data[p]))
 r = p;
 else
 l = p+1;
 }
 while (l < r);
 /* The invariants still hold, so pivot >= all in [lo, l) and
 pivot < all in [l, start), so pivot belongs at l.  Note
 that if there are elements equal to pivot, l points to the
 first slot after them -- that's why this sort is stable.
 n = 2;
 if (comp (*lo, *(lo-1)))
 {
 descending = true;
 for (lo = lo+1; lo < hi; ++lo, ++n)
 {
 if (comp (*lo, *(lo-1)))
 ;
 else
 break;
 }
 }
 else
 {
 for (lo = lo+1; lo < hi; ++lo, ++n)
 {
 if (comp (*lo, *(lo-1)))
 break;
 }
 }
 {
 /* a[hint] < key -- gallop right, until
 * a[hint + lastofs] < key <= a[hint + ofs]
 */
 const octave_idx_type maxofs = n - hint;  /* &a[n-1] is highest */
 while (ofs < maxofs)
 {
 if (comp (a[ofs], key))
 {
 lastofs = ofs;
 ofs = (ofs << 1) + 1;
 ofs = maxofs;
 /* Translate back to offsets relative to &a[0]. */
 lastofs += hint;
 ofs += hint;
 }
 else
 {
 /* key <= a[hint] -- gallop left, until
 * a[hint - ofs] < key <= a[hint - lastofs]
 */
 const octave_idx_type maxofs = hint + 1;  /* &a[0] is lowest */
 while (ofs < maxofs)
 {
 if (comp (*(a-ofs), key))
 break;
 /* key <= a[hint - ofs] */
 lastofs = ofs;
 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
 * right of lastofs but no farther right than ofs.  Do a binary
 * search, with invariant a[lastofs-1] < key <= a[ofs].
 */
 ++lastofs;
 while (lastofs < ofs)
 {
 octave_idx_type m = lastofs + ((ofs - lastofs) >> 1);
 if (comp (a[m], key))
 lastofs = m+1;  /* a[m] < key */
 {
 /* key < a[hint] -- gallop left, until
 * a[hint - ofs] <= key < a[hint - lastofs]
 */
 const octave_idx_type maxofs = hint + 1;  /* &a[0] is lowest */
 while (ofs < maxofs)
 {
 if (comp (key, *(a-ofs)))
 {
 lastofs = ofs;
 ofs = (ofs << 1) + 1;
 /* Translate back to positive offsets relative to &a[0]. */
 k = lastofs;
 lastofs = hint - ofs;
 ofs = hint - k;
 }
 else
 {
 /* a[hint] <= key -- gallop right, until
 * a[hint + lastofs] <= key < a[hint + ofs]
 */
 const octave_idx_type maxofs = n - hint;  /* &a[n-1] is highest */
 while (ofs < maxofs)
 {
 if (comp (key, a[ofs]))
 break;
 /* a[hint + ofs] <= key */
 lastofs = ofs;
 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
 * right of lastofs but no farther right than ofs.  Do a binary
 * search, with invariant a[lastofs-1] <= key < a[ofs].
 */
 ++lastofs;
 while (lastofs < ofs)
 {
 octave_idx_type m = lastofs + ((ofs - lastofs) >> 1);
 if (comp (key, a[m]))
 ofs = m;        /* key < a[m] */
 octave_sort<T>::MergeState::getmem (octave_idx_type need)
 {
 if (need <= alloced)
 return;
 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.
 */
 delete [] a;
 delete [] ia; // Must do this or fool possible next getmemi.
 octave_sort<T>::MergeState::getmemi (octave_idx_type need)
 {
 if (ia && need <= alloced)
 return;
 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.
 */
 delete [] a;
 delete [] ia;
 * Return 0 if successful, -1 if error.
 */
 template <class T>
 template <class Comp>
 int
 octave_sort<T>::merge_lo (T *pa, octave_idx_type na,
 T *pb, octave_idx_type nb,
 Comp comp)
 {
 octave_idx_type k;
 T *dest;
 for (;;)
 {
 // FIXME: these loops are candidates for further optimizations.
 // Rather than testing everything in each cycle, it may be more
 // efficient to do it in hunks.
 if (comp (*pb, *pa))
 {
 *dest++ = *pb++;
 ++bcount;
 acount = 0;
 }
 template <class T>
 template <class Comp>
 int
 octave_sort<T>::merge_lo (T *pa, octave_idx_type *ipa, octave_idx_type na,
 T *pb, octave_idx_type *ipb, octave_idx_type nb,
 Comp comp)
 {
 octave_idx_type k;
 T *dest;
 * Return 0 if successful, -1 if error.
 */
 template <class T>
 template <class Comp>
 int
 octave_sort<T>::merge_hi (T *pa, octave_idx_type na,
 T *pb, octave_idx_type nb,
 Comp comp)
 {
 octave_idx_type k;
 T *dest;
 if (na == 0)
 goto Succeed;
 if (nb == 1)
 goto CopyA;
 for (;;)
 {
 octave_idx_type acount = 0;       /* # of times A won in a row */
 octave_idx_type bcount = 0;       /* # of times B won in a row */
 /* Do the straightforward thing until (if ever) one run
 * appears to win consistently.
 */
 for (;;)
 {
 if (comp (*pb, *pa))
 {
 *dest-- = *pa--;
 ++acount;
 if (na == 0)
 goto Succeed;
 if (acount >= min_gallop)
 break;
 }
 else
 {
 *dest-- = *pb--;
 ++bcount;
 acount = 0;
 --nb;
 * 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, basea, na, na-1, comp);
 if (k < 0)
 goto Fail;
 k = na - k;
 acount = k;
 if (k)
 {
 dest = std::copy_backward (pa+1 - k, pa+1, dest+1) - 1;
 pa -= k;
 na -= k;
 if (na == 0)
 k = gallop_left (*pa, baseb, nb, nb-1, comp);
 if (k < 0)
 goto Fail;
 k = nb - k;
 bcount = k;
 if (k)
 {
 dest -= k;
 pb -= k;
 std::copy (pb+1, pb+1 + k, dest+1);
 nb -= k;
 }
 template <class T>
 template <class Comp>
 int
 octave_sort<T>::merge_hi (T *pa, octave_idx_type *ipa, octave_idx_type na,
 T *pb, octave_idx_type *ipb, octave_idx_type nb,
 Comp comp)
 {
 octave_idx_type k;
 T *dest;
 if (na == 0)
 goto Succeed;
 if (nb == 1)
 goto CopyA;
 for (;;)
 {
 octave_idx_type acount = 0;       /* # of times A won in a row */
 octave_idx_type bcount = 0;       /* # of times B won in a row */
 /* Do the straightforward thing until (if ever) one run
 * appears to win consistently.
 */
 for (;;)
 {
 if (comp (*pb, *pa))
 {
 *dest-- = *pa--; *idest-- = *ipa--;
 ++acount;
 if (na == 0)
 goto Succeed;
 if (acount >= min_gallop)
 break;
 }
 else
 {
 *dest-- = *pb--; *idest-- = *ipb--;
 ++bcount;
 acount = 0;
 --nb;
 * 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, basea, na, na-1, comp);
 if (k < 0)
 goto Fail;
 k = na - k;
 acount = k;
 if (k)
 {
 dest = std::copy_backward (pa+1 - k, pa+1, dest+1) - 1;
 idest = std::copy_backward (ipa+1 - k, ipa+1, idest+1) - 1;
 pa -= k; ipa -= k;
 na -= k;
 k = gallop_left (*pa, baseb, nb, nb-1, comp);
 if (k < 0)
 goto Fail;
 k = nb - k;
 bcount = k;
 if (k)
 {
 dest -= k; idest -= k;
 pb -= k; ipb -= k;
 std::copy (pb+1, pb+1 + k, dest+1);
 std::copy (ipb+1, ipb+1 + k, idest+1);
 int
 octave_sort<T>::merge_collapse (T *data, Comp comp)
 {
 struct s_slice *p = ms->pending;
 while (ms->n > 1)
 {
 octave_idx_type n = ms->n - 2;
 if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len)
 {
 if (p[n-1].len < p[n+1].len)
 --n;
 if (merge_at (n, data, comp) < 0)
 return -1;
 }
 else if (p[n].len <= p[n+1].len)
 {
 if (merge_at (n, data, comp) < 0)
 return -1;
 }
 else
 int
 octave_sort<T>::merge_collapse (T *data, octave_idx_type *idx, Comp comp)
 {
 struct s_slice *p = ms->pending;
 while (ms->n > 1)
 {
 octave_idx_type n = ms->n - 2;
 if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len)
 {
 if (p[n-1].len < p[n+1].len)
 --n;
 if (merge_at (n, data, idx, comp) < 0)
 return -1;
 }
 else if (p[n].len <= p[n+1].len)
 {
 if (merge_at (n, data, idx, comp) < 0)
 return -1;
 }
 else
 int
 octave_sort<T>::merge_force_collapse (T *data, Comp comp)
 {
 struct s_slice *p = ms->pending;
 while (ms->n > 1)
 {
 octave_idx_type n = ms->n - 2;
 if (n > 0 && p[n-1].len < p[n+1].len)
 --n;
 if (merge_at (n, data, comp) < 0)
 int
 octave_sort<T>::merge_force_collapse (T *data, octave_idx_type *idx, Comp comp)
 {
 struct s_slice *p = ms->pending;
 while (ms->n > 1)
 {
 octave_idx_type n = ms->n - 2;
 if (n > 0 && p[n-1].len < p[n+1].len)
 --n;
 if (merge_at (n, data, idx, comp) < 0)
 ms->reset ();
 ms->getmem (1024);
 if (nel > 1)
 {
 octave_idx_type nremaining = nel;
 octave_idx_type lo = 0;
 /* March over the array once, left to right, finding natural runs,
 * and extending short natural runs to minrun elements.
 */
 octave_idx_type minrun = merge_compute_minrun (nremaining);
 do
 {
 bool descending;
 octave_idx_type n;
 /* Identify next run. */
 if (n < 0)
 goto fail;
 if (descending)
 std::reverse (data + lo, data + lo + n);
 /* If short, extend to min(minrun, nremaining). */
 if (n < minrun)
 {
 const octave_idx_type force = nremaining <= minrun ? nremaining : minrun;
 binarysort (data + lo, force, n, comp);
 n = force;
 }
 }
 template <class T>
 template <class Comp>
 void
 octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel,
 Comp comp)
 {
 /* Re-initialize the Mergestate as this might be the second time called */
 if (! ms) ms = new MergeState;
 ms->reset ();
 ms->getmemi (1024);
 if (nel > 1)
 {
 octave_idx_type nremaining = nel;
 octave_idx_type lo = 0;
 /* March over the array once, left to right, finding natural runs,
 * and extending short natural runs to minrun elements.
 */
 octave_idx_type minrun = merge_compute_minrun (nremaining);
 do
 {
 bool descending;
 octave_idx_type n;
 /* Identify next run. */
 {
 std::reverse (data + lo, data + lo + n);
 std::reverse (idx + lo, idx + lo + n);
 }
 /* If short, extend to min(minrun, nremaining). */
 if (n < minrun)
 {
 const octave_idx_type force = nremaining <= minrun ? nremaining : minrun;
 binarysort (data + lo, idx + lo, force, n, comp);
 n = force;
 }
 #ifdef INLINE_ASCENDING_SORT
 if (compare == ascending_compare)
 sort (data, nel, std::less<T> ());
 else
 #endif
 #ifdef INLINE_DESCENDING_SORT
 if (compare == descending_compare)
 sort (data, nel, std::greater<T> ());
 else
 #endif
 if (compare)
 #ifdef INLINE_ASCENDING_SORT
 if (compare == ascending_compare)
 sort (data, idx, nel, std::less<T> ());
 else
 #endif
 #ifdef INLINE_DESCENDING_SORT
 if (compare == descending_compare)
 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)
 {
 }
 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)
 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);
 }
 }
 }
 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;
 }
 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)
 }
 // The simple binary lookup.
 template <class T> template <class Comp>
 octave_idx_type
 octave_sort<T>::lookup (const T *data, octave_idx_type nel,
 const T& value, Comp comp)
 {
 octave_idx_type lo = 0, hi = nel;
 return lo;
 }
 template <class T>
 octave_idx_type
 octave_sort<T>::lookup (const T *data, octave_idx_type nel,
 const T& value)
 {
 octave_idx_type retval = 0;
 #ifdef INLINE_ASCENDING_SORT
 if (compare == ascending_compare)
 retval = lookup (data, nel, value, std::less<T> ());
 else
 #endif
 #ifdef INLINE_DESCENDING_SORT
 if (compare == descending_compare)
 retval = lookup (data, nel, value, std::greater<T> ());
 else
 #endif
 if (compare)
 return retval;
 }
 template <class T> template <class Comp>
 void
 octave_sort<T>::lookup (const T *data, octave_idx_type nel,
 const T *values, octave_idx_type nvalues,
 octave_idx_type *idx, Comp comp)
 {
 // Use a sequence of binary lookups.
 for (octave_idx_type j = 0; j < nvalues; j++)
 idx[j] = lookup (data, nel, values[j], comp);
 }
 template <class T>
 void
 octave_sort<T>::lookup (const T *data, octave_idx_type nel,
 const T* values, octave_idx_type nvalues,
 octave_idx_type *idx)
 {
 #ifdef INLINE_ASCENDING_SORT
 if (compare == ascending_compare)
 lookup (data, nel, values, nvalues, idx, std::less<T> ());
 else
 #endif
 #ifdef INLINE_DESCENDING_SORT
 if (compare == descending_compare)
 lookup (data, nel, values, nvalues, idx, std::greater<T> ());
 else
 #endif
 if (compare)
 lookup (data, nel, values, nvalues, idx, std::ptr_fun (compare));
 }
 template <class T> template <class Comp>
 void
 octave_sort<T>::lookup_sorted (const T *data, octave_idx_type nel,
 const T *values, octave_idx_type nvalues,
 octave_idx_type *idx, bool rev, Comp comp)
 {
 if (rev)
 idx[j] = i;
 }
 }
 template <class T>
 void
 octave_sort<T>::lookup_sorted (const T *data, octave_idx_type nel,
 const T* values, octave_idx_type nvalues,
 octave_idx_type *idx, bool rev)
 {
 #ifdef INLINE_ASCENDING_SORT
 if (compare == ascending_compare)
 lookup_sorted (data, nel, values, nvalues, idx, rev, std::less<T> ());
 else
 #endif
 #ifdef INLINE_DESCENDING_SORT
 if (compare == descending_compare)
 lookup_sorted (data, nel, values, nvalues, idx, rev, std::greater<T> ());
 else
 #endif
 if (compare)
 lookup_sorted (data, nel, values, nvalues, idx, rev, std::ptr_fun (compare));
 }
 template <class T> template <class Comp>
 void
 octave_sort<T>::nth_element (T *data, octave_idx_type nel,
 octave_idx_type lo, octave_idx_type up,
 Comp comp)
 {
 // Simply wrap the STL algorithms.
 {
 std::nth_element (data, data + lo, data + nel, comp);
 if (up == lo + 2)
 {
 // Finding two subsequent elements.
 std::swap (data[lo+1],
 *std::min_element (data + lo + 1, data + nel, comp));
 }
 else
 std::partial_sort (data + lo + 1, data + up, data + nel, comp);
 }
 }
 template <class T>
 void
 octave_sort<T>::nth_element (T *data, octave_idx_type nel,
 octave_idx_type lo, octave_idx_type up)
 {
 if (up < 0)
 up = lo + 1;
 #ifdef INLINE_ASCENDING_SORT
 if (compare == ascending_compare)
 nth_element (data, nel, lo, up, std::less<T> ());
 else
 #endif
 #ifdef INLINE_DESCENDING_SORT
 if (compare == descending_compare)
 nth_element (data, nel, lo, up, std::greater<T> ());
 else
 #endif
 if (compare)
 nth_element (data, nel, lo, up, std::ptr_fun (compare));
 }
 template <class T>
 bool
 octave_sort<T>::ascending_compare (typename ref_param<T>::type x,
 typename ref_param<T>::type y)
 {
 return x < y;
 }
 template <class T>
 bool
 octave_sort<T>::descending_compare (typename ref_param<T>::type x,
 typename ref_param<T>::type y)
 {
 return x > y;
 }

Mercurial > octave

comparison liboctave/oct-sort.cc @ 11586:12df7854fa7c