/*----------------------------------------------------------------------  File    : vecops.c  Contents: some special vector operations  Author  : Christian Borgelt  History : 16.09.1996 file created            04.02.1999 long int changed to int            03.06.2001 function v_shuffle added            02.01.2002 functions v_intsort, v_fltsort, v_dblsort added            03.03.2002 functions v_reverse, v_intrev etc. added----------------------------------------------------------------------*/#include <assert.h>#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() *//*--------------------------------------------------------------------*/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)