vecops.c

数据挖掘中的关联规则算法

/*----------------------------------------------------------------------
  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
            21.08.2003 function v_heapsort 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() */

/*--------------------------------------------------------------------*/

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 */