/*---------------------------------------------------------------------- File : vecops.c Contents: some special vector operations Author : Christian Borgelt History : 1996.09.16 file created 1999.02.04 long int changed to int 2001.06.03 function v_shuffle added 2002.01.02 functions v_intsort, v_fltsort, v_dblsort added 2002.03.03 functions v_reverse, v_intrev etc. added 2003.08.21 function v_heapsort added 2007.01.16 shuffle functions for basic data types added 2007.12.02 bug in reverse functions fixed ----------------------------------------------------------------------*/ #include #include "vecops.h" /*---------------------------------------------------------------------- Preprocessor Definitions ----------------------------------------------------------------------*/ #define TH_INSERT 16 /* threshold for insertion sort */ #define BUFSIZE 4096 /* size of buffers for shifting */ /*---------------------------------------------------------------------- Functions ----------------------------------------------------------------------*/ static void _rec (void **vec, int n, VCMPFN cmpfn, void *data) { /* --- recursive part of sort */ void **l, **r; /* pointers to exchange positions */ void *x, *t; /* pivot element and exchange buffer */ int m; /* number of elements in 2nd section */ do { /* sections sort loop */ l = vec; r = l +n -1; /* start at left and right boundary */ if (cmpfn(*l, *r, data) > 0) { /* bring the first and last */ t = *l; *l = *r; *r = t; } /* element into proper order */ x = vec[n >> 1]; /* get the middle element as pivot */ if (cmpfn(x, *l, data) < 0) x = *l; /* try to find a */ else if (cmpfn(x, *r, data) > 0) x = *r; /* better pivot */ while (1) { /* split and exchange loop */ while (cmpfn(*++l, x, data) < 0) /* skip left elements that */ ; /* are smaller than the pivot element */ while (cmpfn(*--r, x, data) > 0) /* skip right elements that */ ; /* are greater than the pivot element */ if (l >= r) { /* if less than two elements left, */ if (l <= r) { l++; r--; } break; } /* abort the loop */ t = *l; *l = *r; *r = t; /* otherwise exchange elements */ } m = (int)(vec +n -l); /* compute the number of elements */ n = (int)(r -vec +1); /* right and left of the split */ if (n > m) { /* if right section is smaller, */ if (m >= TH_INSERT) /* but larger than the threshold, */ _rec(l, m, cmpfn, data); } /* sort it by a recursive call, */ else { /* if the left section is smaller, */ if (n >= TH_INSERT) /* but larger than the threshold, */ _rec(vec, n, cmpfn, data); /* sort it by a recursive call, */ vec = l; n = m; /* then switch to the right section */ } /* keeping its size m in variable n */ } while (n >= TH_INSERT); /* while greater than threshold */ } /* _rec() */ /*--------------------------------------------------------------------*/ void v_sort (void *vec, int n, VCMPFN cmpfn, void *data) { /* --- quick sort for pointer vectors */ int k; /* size of first section */ void **l, **r; /* to traverse the vector */ void *t; /* exchange buffer */ assert(vec && (n >= 0) && cmpfn); /* check the function arguments */ if (n <= 1) return; /* do not sort less than two elements */ if (n < TH_INSERT) /* if fewer elements than threshold */ k = n; /* for insertion sort, note the */ else { /* number of elements, otherwise */ _rec(vec, n, cmpfn, data); /* call the recursive function */ k = TH_INSERT -1; /* and get the number of elements */ } /* in the first vector section */ for (l = r = vec; --k > 0; ) /* find the smallest element within */ if (cmpfn(*++r, *l, data) < 0) l = r; /* the first k elements */ r = vec; /* swap the smallest element */ t = *l; *l = *r; *r = t; /* to front as a sentinel */ while (--n > 0) { /* insertion sort loop */ t = *++r; /* note the element to insert */ for (l = r; cmpfn(*--l, t, data) > 0; ) /* shift right elements */ l[1] = *l; /* that are greater than the one to */ l[1] = t; /* insert and store the element to */ } /* insert in the place thus found */ } /* v_sort() */ /*--------------------------------------------------------------------*/ static void _sift (void **vec, int l, int r, VCMPFN cmpfn, void *data) { /* --- let element sift down in heap */ void *t; /* buffer for element */ int i; /* index of first successor in heap */ t = vec[l]; /* note sift element */ i = l +l +1; /* compute index of first successor */ do { /* sift loop */ if ((i < r) /* if second successor is greater */ && (cmpfn(vec[i], vec[i+1], data) < 0)) i++; /* go to the second successor */ if (cmpfn(t, vec[i], data) >= 0) /* if the successor is greater */ break; /* than the sift element, */ vec[l] = vec[i]; /* let the successor ascend in heap */ l = i; i += i +1; /* compute index of first successor */ } while (i <= r); /* while still within heap */ vec[l] = t; /* store the sift element */ } /* _sift() */ /*--------------------------------------------------------------------*/ void v_heapsort (void *vec, int n, VCMPFN cmpfn, void *data) { /* --- heap sort for pointer vectors */ int l, r; /* boundaries of heap section */ void *t, **v; /* exchange buffer, vector */ if (n <= 1) return; /* do not sort less than two elements */ l = n >> 1; /* at start, only the second half */ r = n -1; /* of the vector has heap structure */ while (--l >= 0) /* while the heap is not complete, */ _sift(vec, l, r, cmpfn, data); /* extend it by one element */ v = vec; /* type the vector pointer */ while (1) { /* heap reduction loop */ t = v[0]; v[0] = v[r]; /* swap the greatest element */ v[r] = t; /* to the end of the vector */ if (--r <= 0) break; /* if the heap is empty, abort */ _sift(v, 0, r, cmpfn, data); } /* let the element that has been */ } /* v_heapsort() */ /* swapped to front sift down */ /*--------------------------------------------------------------------*/ void v_move (void *vec, int off, int n, int pos, int esz) { /* --- move a vector section */ int i; /* loop variable */ int mid, end; /* middle and end index */ int *src, *dst; /* to traverse vector */ int buf[BUFSIZE]; /* buffer for vector elements */ assert(vec /* check the function arguments */ && (off >= 0) && (n >= 0) && (pos >= 0) && (esz >= 0)); esz /= (int)sizeof(int); /* adapt size, offsets, and counter */ pos *= esz; off *= esz; n *= esz; end = off +n; /* normalize vector indices */ if (pos <= off) { mid = off; off = pos; } else { mid = end; end = pos; } if (mid -off < end -mid) { /* if first section is smaller */ while (mid > off) { /* while there are elements to shift */ n = (mid -off < BUFSIZE) ? mid -off : BUFSIZE; src = (int*)vec +mid -n; /* get number of elements and */ dst = buf; /* copy source to the buffer */ for (i = n; --i >= 0; ) *dst++ = *src++; dst = (int*)vec +mid -n; /* shift down/left second section */ for (i = end -mid; --i >= 0; ) *dst++ = *src++; src = buf; /* copy buffer to destination */ for (i = n; --i >= 0; ) *dst++ = *src++; mid -= n; end -= n; /* second section has been shifted */ } } /* down/left cnt elements */ else { /* if second section is smaller */ while (end > mid) { /* while there are elements to shift */ n = (end -mid < BUFSIZE) ? end -mid : BUFSIZE; src = (int*)vec +mid +n; /* get number of elements and */ dst = buf +n; /* copy source to the buffer */ for (i = n; --i >= 0; ) *--dst = *--src; dst = (int*)vec +mid +n; /* shift up/right first section */ for (i = mid -off; --i >= 0; ) *--dst = *--src; src = buf +n; /* copy buffer to destination */ for (i = n; --i >= 0; ) *--dst = *--src; mid += n; off += n; /* first section has been shifted */ } /* up/right cnt elements */ } } /* v_move() */ /*--------------------------------------------------------------------*/ void v_shuffle (void *vec, int n, double randfn (void)) { /* --- shuffle vector entries */ int i; /* vector index */ void **v = vec, *t; /* vector and exchange buffer */ while (--n > 0) { /* shuffle loop (n random selections) */ i = (int)((n+1) *randfn()); /* compute a random index */ if (i > n) i = n; /* in the remaining section and */ if (i < 0) i = 0; /* exchange the vector elements */ t = v[i]; v[i] = v[n]; v[n] = t; } } /* v_shuffle() */ /*--------------------------------------------------------------------*/ void v_reverse (void *vec, int n) { /* --- reverse a pointer vector */ void **v, *t; /* vector and exchange buffer */ for (v = vec; --n > 0; ) { /* reverse the order of the elements */ t = v[n]; v[n--] = v[0]; *v++ = t; } } /* v_reverse() */ /*--------------------------------------------------------------------*/ #define REC(type,rec) \ static void rec (type *vec, int n) \ { /* --- recursive part of sort */ \ type *l, *r; /* pointers to exchange positions */ \ type x, t; /* pivot element and exchange buffer */\ int m; /* number of elements in sections */ \ \ do { /* sections sort loop */ \ l = vec; r = l +n -1; /* start at left and right boundary */ \ if (*l > *r) { t = *l; *l = *r; *r = t; } \ x = vec[n >> 1]; /* get the middle element as pivot */ \ if (x < *l) x = *l; /* compute median of three */ \ else if (x > *r) x = *r; /* to find a better pivot */ \ while (1) { /* split and exchange loop */ \ while (*++l < x) /* skip left elements that are */ \ ; /* smaller than the pivot element */ \ while (*--r > x) /* skip right elements that are */ \ ; /* greater than the pivot element */ \ if (l >= r) { /* if less than two elements left, */ \ if (l <= r) { l++; r--; } break; } /* abort the loop */ \ t = *l; *l = *r; *r = t; /* otherwise exchange elements */ \ } \ m = (int)(vec +n -l); /* compute the number of elements */ \ n = (int)(r -vec +1); /* right and left of the split */ \ if (n > m) { /* if right section is smaller, */ \ if (m >= TH_INSERT) /* but larger than the threshold, */ \ rec(l, m); } /* sort it by an recursive call */ \ else { /* if the left section is smaller, */ \ if (n >= TH_INSERT) /* but larger than the threshold, */ \ rec(vec, n); /* sort it by an recursive call, */ \ vec = l; n = m; /* then switch to the right section */ \ } /* keeping its size m in variable n */ \ } while (n >= TH_INSERT); /* while greater than threshold */ \ } /* rec() */ /*--------------------------------------------------------------------*/ #define SORT(type,rec,sort) \ void sort (type *vec, int n) \ { /* --- sort a number vector */ \ int k; /* size of first section */ \ type *l, *r; /* to traverse the vector */ \ type t; /* exchange buffer */ \ \ assert(vec && (n >= 0)); /* check the function arguments */ \ if (n <= 1) return; /* do not sort less than two elems. */ \ if (n < TH_INSERT) /* if less elements than threshold */ \ k = n; /* for insertion sort, note the */ \ else { /* number of elements, otherwise */ \ rec(vec, n); /* call the recursive sort function */ \ k = TH_INSERT -1; /* and get the number of elements */ \ } /* in the first vector section */ \ for (l = r = vec; --k > 0; ) /* find position of smallest element */\ if (*++r < *l) l = r; /* within the first k elements */ \ r = vec; /* swap the smallest element */ \ t = *l; *l = *r; *r = t; /* to front as a sentinel */ \ while (--n > 0) { /* standard insertion sort */ \ t = *++r; /* note the number to insert */ \ for (l = r; *--l > t; k--) /* shift right all numbers that are */ \ l[1] = *l; /* greater than the one to insert */ \ l[1] = t; /* and store the number to insert */ \ } /* in the place thus found */ \ } /* sort() */ /*--------------------------------------------------------------------*/ REC (int, _intrec) SORT(int, _intrec, v_intsort) /*--------------------------------------------------------------------*/ REC (float, _fltrec) SORT(float, _fltrec, v_fltsort) /*--------------------------------------------------------------------*/ REC (double, _dblrec) SORT(double, _dblrec, v_dblsort) /*--------------------------------------------------------------------*/ #define REVERSE(type,reverse) \ void reverse (type *vec, int n) \ { /* --- reverse a number vector */ \ type t; /* exchange buffer */ \ while (--n > 0) { /* reverse the order of the elems. */ \ t = vec[n]; vec[n--] = vec[0]; *vec++ = t; } \ } /* reverse() */ /*--------------------------------------------------------------------*/ REVERSE(int, v_intrev) REVERSE(float, v_fltrev) REVERSE(double, v_dblrev) /*--------------------------------------------------------------------*/ #define SHUFFLE(type,shuffle) \ void shuffle (type *vec, int n, double randfn (void)) \ { /* --- shuffle vector entries */ \ int i; /* vector index */ \ type t; /* exchange buffer */ \ \ while (--n > 0) { /* shuffle loop (n selections) */ \ i = (int)((n+1) *randfn()); /* compute a random index */ \ if (i > n) i = n; /* in the remaining section and */ \ if (i < 0) i = 0; /* exchange the vector elements */ \ t = vec[i]; vec[i] = vec[n]; vec[n] = t; \ } \ } /* shuffle() */ /*--------------------------------------------------------------------*/ SHUFFLE(int, v_intshfl) SHUFFLE(float, v_fltshfl) SHUFFLE(double, v_dblshfl)