rules.c

it is tree Dtree algorithm. so see it. it is in c++

/*----------------------------------------------------------------------
  File    : rules.c
  Contents: rule and rule set management
  Author  : Christian Borgelt
  History : 17.05.1998 file created
            26.05.1998 function rs_desc added
            27.05.1998 comparison operators added
            23.06.1998 adapted to modified attset functions
            13.08.1998 parameter delas added to function rs_delete
            24.08.1998 management of subsets of values added
            26.08.1998 function rs_ruleexg added
            29.09.1998 assertions added, minor improvements
            19.07.2001 global variables removed, rs_desc improved
            06.06.2002 rule and rule set parsing functions added
            25.09.2003 bug in function r_check fixed (condition dir)
            12.08.2004 adapted to new module parse
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <assert.h>
#include "rules.h"
#include "vecops.h"
#ifdef STORAGE
#include "storage.h"
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define BLKSIZE  32             /* block size for rule vector */
#define MARK     0x80           /* mark for conditions to adapt */
#define MSBIT    31             /* most significant bit */

/*----------------------------------------------------------------------
  Type Definitions
----------------------------------------------------------------------*/
#ifdef RS_DESC
typedef struct {                /* --- description information --- */
  FILE   *file;                 /* output file */
  int    pos;                   /* position in output line */
  int    max;                   /* maximal length of output line */
  ATTSET *attset;               /* attribute set */
} DESC;                         /* (description information) */

#endif
/*----------------------------------------------------------------------
  Constants
----------------------------------------------------------------------*/
#if defined(RS_DESC) || defined(RS_PARSE)
static const char *_opsigns[] = {
  NULL, "=", "<", "<=", ">", ">=", "!=", NULL, "in", "in" };
#endif                          /* signs for comparison operators */

/*----------------------------------------------------------------------
  Auxiliary Functions
----------------------------------------------------------------------*/

static int _valcmp (const void *p1, const void *p2)
{                               /* --- compare two attribute values */
  if (*(const int*)p1 < *(const int*)p2) return -1;
  if (*(const int*)p1 > *(const int*)p2) return  1;
  return 0;                     /* return sign of difference */
}  /* _valcmp() */

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

static int _condset (COND *cond, int att, int op, INST *val)
{                               /* --- set a rule condition */
  int i;                        /* loop variable, number of values */
  int *sv, *dv, *tmp;           /* to traverse attribute values */
  unsigned int bits;            /* bitflag rep. of a value set */

  assert(cond && val);          /* check the function arguments */
  if (op != R_IN) {             /* if there is no value vector, */
    cond->op  = op;             /* simply copy the operator */
    cond->val = *val; }         /* and the attribute value */
  else {                        /* if there is a value vector, */
    sv = val->p; i = *sv;       /* get vector and number of values */
    if (i == 1) {               /* if there is only one value */
      cond->op = R_EQ; cond->val.i = sv[1]; }
    else {                      /* if there is more than one value */
      for (bits = 0, sv++; --i >= 0; ) {
        if (*sv > MSBIT) break; /* traverse the value vector */
        bits |= 1 << *sv++;     /* and try to convert it to */
      }                         /* a bitflag representation */
      if (i < 0) {              /* if conversion was successful */
        cond->op = R_BF; cond->val.i = bits; }
      else {                    /* if conversion was not successful */
        sv = val->p; i = *sv+1; /* get vector and number of values */
        dv = tmp = malloc(i *sizeof(int));
        if (!dv) return -1;     /* allocate a value vector */
        do { *dv++ = *sv++; } while (--i >= 0);
        qsort(tmp+1, *tmp, sizeof(int), _valcmp);
        cond->op = R_IN; cond->val.p = tmp;
      }                         /* copy and sort the given */
    }                           /* value vector and set it */
  }                             /* as the value of the condition */
  cond->att = att;              /* set attribute identifier */
  return 0;                     /* return 'ok' */
}  /* _condset() */

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

static int _condcopy (COND *dst, COND *src)
{                               /* --- set a rule condition */
  int i;                        /* loop variable, number of values */
  int *sv, *dv;                 /* to traverse attribute values */

  assert(dst && src);           /* check the function arguments */
  if (src->op != R_IN) {        /* if there is no value vector, */
    *dst = *src; return 0; }    /* simply copy the condition */
  sv = src->val.p; i = *sv;     /* get vector and number of values */
  dv = malloc((i+1) *sizeof(int));
  if (!dv) return -1;           /* allocate a value vector */
  dst->att   = src->att;        /* set attribute identifier, */
  dst->op    = src->op;         /* comparison operator, */
  dst->val.p = dv;              /* and new value vector */
  do { *dv++ = *sv++; } while (--i >= 0);
  return 0;                     /* copy value vector and return 'ok' */
}  /* _condcopy() */

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

static int _condcmp (const void *p1, const void *p2)
{                               /* --- compare two conditions */
  const COND *c1 = p1, *c2 = p2;/* conditions to compare */

  if (c1->att < c2->att) return -1;
  if (c1->att > c2->att) return  1;
  if (c1->op  < c2->op)  return  1;
  if (c1->op  > c2->op)  return -1;
  return 0;                     /* compare attribute and operator */
}  /* _condcmp() */

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

static int _isect (COND *dst, COND *src)
{                               /* --- intersect two conditions */
                                /*     with a subset in one of them */
  int sn,  dn;                  /* numbers of values in subsets */
  int *sv, *dv;                 /* to traverse value vectors */
  unsigned int bits;            /* bitflag rep. of a value set */

  assert(dst && src);           /* check the function arguments */

  /* --- only source contains a subset --- */
  if (dst->op == R_EQ) {        /* if dest. equal to some value */
    if (src->op == R_BF)        /* if bitflag rep. in source, */
      return (src->val.i & (1 << dst->val.i));   /* check bit */
    sv = src->val.p; sn = *sv++;/* if vector rep. in source */
    return (bsearch(&dst->val.i, sv, sn, sizeof(int),_valcmp) != NULL);
  }                             /* search for the value */
  if (dst->op == R_NE) {        /* if dest. not equal to some value */
    if (src->op == R_BF) {      /* if bitflag rep. in source, */
      dst->op    = R_BF;        /* remove value from the value set */
      dst->val.i = src->val.i & ~(1 << dst->val.i);
      return (dst->val.i != 0); /* return whether the value set */
    }                           /* without the value is not empty */
    sv = src->val.p;            /* if vector rep. in source */
    return ((*sv > 1) || (sv[1] != dst->val.i));
  }                             /* check for remaining values */

  /* --- only destination contains a subset --- */
  if (src->op == R_EQ) {        /* if source equal to some value */
    if (dst->op == R_BF) {      /* if bitflag rep. in destination */
      dst->val.i &= 1 << src->val.i;     /* remove other values from */
      if (dst->val.i == 0) return 0; }   /* the set and check result */
    else {                      /* if vector rep. in destination */
      dv = dst->val.p;          /* search the vector for the value */
      if (bsearch(&src->val.i, dv+1, *dv, sizeof(int),_valcmp) == NULL)
        return *dv = 0;         /* if value not found, empty */
      free(dv);                 /* the value vector and abort, */
    }                           /* otherwise delete the value vector */
    dst->op    = R_EQ;          /* replace the destination condition */
    dst->val.i = src->val.i;    /* by the source condition, which is */
    return 1;                   /* stronger, and return 'compatible' */
  }
  if (src->op == R_NE) {        /* if source not equal to some value */
    if (dst->op == R_BF) {      /* if bitflag rep. in destination */
      dst->val.i &= ~(1 << src->val.i);
      return (dst->val.i != 0); /* remove value from the set */
    }                           /* and check for an empty set */
    dv = dst->val.p; dn = *dv;  /* search the value vector */
    sv = bsearch(&src->val.i, dv+1, dn, sizeof(int), _valcmp);
    if (!sv) return 1;          /* if value not found, abort */
    for (dn -= (int)(sv -dv); --dn >= 0; sv++)
      *sv = sv[1];              /* remove value from the vector */
    return (--(*dv) > 0);       /* return whether the resulting */
  }                             /* value set is not empty */

  /* --- both conditions contain subsets --- */
  if ((src->op == R_BF)         /* if bitflag representation */
  ||  (dst->op == R_BF)) {      /* in source or in destination */
    if (dst->op == R_IN) {      /* if vector rep. in destination, */
      dv = src->val.p;          /* traverse value vector of dest. */
      for (bits = 0, dn = *dv++; --dn >= 0; )
        bits |= 1 << *dv++;     /* set bits corresponding to values */
      dst->op = R_BF; dst->val.i = bits;
    }                           /* (convert dest. to bitflag rep.) */
    if (src->op == R_BF)        /* if bitflag rep. in source, */
      bits = src->val.i;        /* get the bitflag representation */
    else {                      /* if vector rep. in source, */
      sv = src->val.p;          /* traverse value vector of source */
      for (bits = 0, sn = *sv++; --sn >= 0; )
        bits |= 1 << *sv++;     /* set bits corresponding to values */
    }                           /* (convert source to bitflag rep.) */
    dst->val.i &= bits;         /* intersect bitflag representations */
    return (dst->val.i != 0);   /* return whether the intersection */
  }                             /* of the value sets is not empty */

  sv = src->val.p; sn = *sv++;  /* vectors in source and destination */
  dv = dst->val.p; dn = *dv++;  /* traverse both value vectors */
  if ((dn <= 0) || (sn <= 0))   /* if either set is empty, */
    return *--dv = 0;           /* the intersection is empty */
  while (1) {                   /* intersection loop */
    if      (*sv < *dv) {       /* source value not in destination */
      sv++;       if (--sn <= 0) break; }  /* skip source value */
    else if (*sv > *dv) {       /* destination value not in source */
      *dv++ = -1; if (--dn <= 0) break; }  /* mark dest. value */
    else {                      /* value in source and destination */
      sv++, dv++; if ((--dn <= 0) || (--sn <= 0)) break; }
  }                             /* skip both values */
  sv = dv = dst->val.p;         /* traverse destination again */
  for (dn = *sv++ -= dn; --dn >= 0; sv++)
    if (*sv >= 0) *++dv = *sv;  /* group together remaining values, */
  sv  = dst->val.p;             /* set new number of values, and */
  *sv = (int)(dv -sv);          /* return whether the resulting */
  return (*sv > 0);             /* value set is not empty */
}  /* _isect() */

/*----------------------------------------------------------------------
  Rule Functions
----------------------------------------------------------------------*/

RULE* r_create (ATTSET *attset, int maxcond)
{                               /* --- create a rule */
  RULE *rule;                   /* created rule */

  assert(attset && (maxcond >= 0)); /* check the function arguments */