dtree1.c

dTree是一个运行在WinCE上的文件管理软件。类似文件管理器,功能强大

  assert(out);                  /* check the function arguments */
  if (newline) {                /* terminate line */
    fputc('\n', out->file); out->pos = 0; }
  for (i = out->pos; i < out->ind; i++)
    fputc(' ',  out->file);     /* indent next line */
  if (out->ind > out->pos) out->pos = out->ind;
}  /* _indent() */              /* note new position */

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

static void _clsout (DTOUT *out, DTNODE *node)
{                               /* --- output of class frequencies */
  int    i, k;                  /* loop variables, buffer */
  ATT    *att;                  /* class attribute */
  DTDATA *data;                 /* to traverse node's data vector */
  int    len;                   /* length of the class output */
  double sum = 0;               /* sum of class frequencies */

  att = as_att(out->attset, node->attid);
  if (out->mode & DT_REL) {     /* if to print relative numbers */
    data = node->vec +node->size;
    for (i = node->size; --i >= 0; ) sum += (--data)->frq;
  }                             /* compute the frequency sum */
  data = node->vec;             /* traverse the classes */
  for (i = k = 0; i < node->size; data++, i++) {
    if (data->frq <= 0)         /* if a class does not occur, */
      continue;                 /* skip it, otherwise get its name */
    if (k > 0) {                /* if not the first class value, */
      fputc(',', out->file); out->pos++; }  /* print a separator */
    len  = sc_format(out->buf, att_valname(att, i), 0);
    len += sprintf(out->buf +len, ": %g", data->frq);
    if (out->mode & DT_REL)     /* if to print relative numbers */
      len += sprintf(out->buf +len, " (%.1f%%)", (data->frq /sum)*100);
    if ((out->pos +len > out->max -4)   /* if the current line */
    &&  (out->pos      > out->ind))     /* would get too long, */
      _indent(out, 1);          /* start a new line and indent */
    else if (k > 0) {           /* if there is sufficient space, */
      fputc(' ', out->file); out->pos += 1; }   /* print a blank */
    fputs(out->buf, out->file); /* print the class information */
    out->pos += len; k++;       /* compute the new position */
  }                             /* and count the printed class */
}  /* _clsout() */

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

static void _dtout (DTOUT *out, DTNODE *node)
{                               /* --- output of decision tree */
  int    i, k, n;               /* loop variables */
  ATT    *att;                  /* target/test attribute */
  DTDATA *data, *d2;            /* to traverse node's data vector */
  int    len, swd;              /* length of the class output */
  int    type;                  /* attribute type */

  assert(out && node);          /* check the function arguments */
  fputs("{ ", out->file);       /* start a branch and */
  out->pos = out->ind += 2;     /* compute the new position */

  /* --- print class frequencies/predicted value --- */
  if (node->flags & DT_LEAF) {  /* if the node is a leaf */
    if (out->type == AT_SYM)    /* if the target is symbolic, */
      _clsout(out, node);       /* print the class frequencies */
    else {                      /* if the target is numeric */
      out->pos += fprintf(out->file, "%g ", node->trg.f);
      out->pos += fprintf(out->file, "~%g ", (node->frq > 0)
                          ? sqrt(node->err/node->frq) : 0);
      out->pos += fprintf(out->file, "[%g]", node->frq);
    }                           /* print the predicted value */
    fputs(" }", out->file);     /* terminate the leaf, */
    out->pos += 2;              /* compute the new position, */
    out->ind -= 2; return;      /* reset the indentation, */
  }                             /* and terminate the function */

  /* --- print attribute test --- */
  att = as_att(out->attset, node->attid);
  sc_format(out->buf, att_name(att), 0);
  fputc('(', out->file);        /* format and print */
  fputs(out->buf, out->file);   /* the attribute name */
  type = att_type(att);         /* get the attribute type */
  if (type != AT_SYM) fprintf(out->file, "|%g", node->cut);
  fputc(')', out->file);        /* print cut value for numeric atts. */
  _indent(out, 1);              /* start a new line for the children */
  data = node->vec;             /* traverse child nodes (subtrees) */
  for (i = k = 0; i < node->size; data++, i++) {
    if (!data->child || islink(data, node))
      continue;                 /* skip empty subtrees and links */
    if (k++ > 0) {              /* if this is not the first subtree, */
      fputc(',', out->file); _indent(out, 1); } /* print a separator */
    if (type != AT_SYM) {       /* if numeric attribute */
      out->buf[0] = (i > 0) ? '>' : '<';
      out->buf[1] = '\0';       /* get one a character name */
      len = swd = 1; }          /* representing the comparison */
    else {                      /* if symbolic attribute */
      len = sc_format(out->buf, att_valname(att, i), 0);
      swd = att_valwd(att, 1);  /* get value name and column width */
      for (n = 0; n < node->size; n++) {
        if (n == i) continue;   /* traverse children except current */
        d2 = node->vec +n;      /* follow link chain */
        while (islink(d2, node)) d2 = d2->link;
        if (d2 != data)         /* skip children that are */
          continue;             /* not linked to current child */
        fputs(out->buf, out->file);
        fputc(',', out->file);  /* print value name and separator */
        if (out->mode & DT_ALIGN)  /* if to align values, */
          _indent(out, 1);         /* start a new line */
        len = sc_format(out->buf, att_valname(att, n), 0);
      }                         /* get name of next value */
    }                           /* (in the value subset) */
    fputs(out->buf, out->file); /* print name of attribute value */
    out->pos += len;            /* calculate new position */
    out->ind += (out->mode & DT_ALIGN) ? swd : 1;
    _indent(out, 0);            /* set indentation and indent */
    fputc(':', out->file); out->pos++; out->ind++;
    _dtout(out, data->child);   /* print next level (recursively) */
    out->ind -= (out->mode & DT_ALIGN) ? swd : 1;
    out->ind--;                 /* reset indentation */
  }
  out->ind -= 2;                /* reset indentation */
  if ((out->pos >= out->max)    /* if line would get too long */
  || ((out->ind <= 0) && (out->pos >= out->max-1)))
    _indent(out, 1);            /* start a new line */
  fputc('}', out->file); out->pos++;
}  /* _dtout() */               /* terminate branch */

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

int dt_desc (DTREE *dt, FILE *file, int mode, int maxlen)
{                               /* --- describe a decision tree */
  int   i, k;                   /* loop variables */
  DTOUT out;                    /* output information */

  assert(dt && file);           /* check the function arguments */

  /* --- print header (as a comment) --- */
  if (mode & DT_TITLE) {        /* if the title flag is set */
    i = k = (maxlen > 0) ? maxlen -2 : 70;
    fputs("/*", file); while (--i >= 0) putc('-', file);
    fprintf(file, (dt->type == AT_SYM)
            ? "\n  decision tree\n" : "\n  regression tree\n");
    while (--k >= 0) putc('-', file); fputs("*/\n", file);
  }                             /* print a title header */
  out.max    = (maxlen <= 0) ? INT_MAX : maxlen;
  out.file   = file;            /* note the function arguments */
  out.attset = dt->attset;      /* in the output structure */
  out.mode   = mode;            /* that will be passed down */
  out.type   = dt->type;

  /* --- print decision tree --- */
  fputs("dtree(", file);        /* decision tree indicator */
  sc_format(out.buf, att_name(as_att(dt->attset, dt->trgid)), 0);
  fputs(out.buf, file);         /* format and print */
  fputs(") =\n", file);         /* the target attribute's name */
  out.ind = 0;                  /* initialize the indentation */
  if (dt->root) _dtout(&out, dt->root);
  else fputs("{ }", file);      /* recursively print the tree */
  fputs(";\n", file);           /* terminate the last output line */

  /* --- print additional information (as a comment) --- */
  if (mode & DT_INFO) {         /* if the add. info. flag is set */
    i = k = (maxlen > 0) ? maxlen -2 : 70;
    fputs("\n/*", file); while (--i >= 0) putc('-', file);
    fprintf(file, "\n  number of attributes: %d",   dt_attcnt(dt));
    fprintf(file, "\n  tree height         : %d",   dt->height);
    fprintf(file, "\n  number of nodes     : %d",   dt->size);
    fprintf(file, "\n  number of tuples    : %g\n", dt_total(dt));
    while (--k >= 0) putc('-', file); fputs("*/\n", file);
  }                             /* print add. tree information */
  return (ferror(file)) ? -1 : 0;
}  /* dt_desc() */              /* return the writing result */

/*----------------------------------------------------------------------
  Parse Functions
----------------------------------------------------------------------*/
#ifdef DT_PARSE

static int _clsin (DTREE *dt, SCAN *scan, DTNODE *node)
{                               /* --- read class frequencies */
  ATT    *att;                  /* class attribute */
  DTDATA *data;                 /* to traverse the data vector */
  int    cls;                   /* class value identifier */
  int    t;                     /* buffer for token/result */
  double f;                     /* buffer for class frequency */

  assert(dt && scan && node);   /* check the function arguments */
  for (data = node->vec +(cls = dt->clscnt); --cls >= 0; )
    (--data)->frq = -1.0F;      /* clear the class frequencies */
  att = as_att(dt->attset, node->attid);
  while (1) {                   /* class read loop */
    t = sc_token(scan);         /* check for a name */
    if ((t != T_ID) && (t != T_NUM)) ERROR(E_VALEXP);
    cls = att_valid(att, sc_value(scan));
    if (cls < 0)                     ERROR(E_UNKVAL);
    if (data[cls].frq >= 0)          ERROR(E_DUPVAL);
    GET_TOK();                  /* get and check the class value */
    GET_CHR(':');               /* consume ':' */
    if (sc_token(scan) != T_NUM)     ERROR(E_NUMEXP);
    f = atof(sc_value(scan));   /* get and check the value frequency */
    if ((f < 0) || (f > FLT_MAX))    ERROR(E_ILLNUM);
    data[cls].frq = (float)f;   /* set the class frequency */
    GET_TOK();                  /* and consume it */
    if (sc_token(scan) == '('){ /* if a relative number follows */
      GET_TOK();                /* consume '(' */
      if (sc_token(scan) != T_NUM)   ERROR(E_NUMEXP);
      f = atof(sc_value(scan)); /* get and check the rel. frequency */
      if ((f < 0) || (f > 100))      ERROR(E_ILLNUM);
      GET_TOK();                /* consume the rel. frequency */
      GET_CHR('%');             /* consume '%' */
      GET_CHR(')');             /* consume ')' */
    }
    if (sc_token(scan) != ',') break; 
    GET_TOK();                  /* if at the end of the list, abort, */
  }                             /* otherwise consume ',' */
  for (data = node->vec +(cls = dt->clscnt); --cls >= 0; )
    if ((--data)->frq < 0) data->frq = 0.0F;
  return 0;                     /* clear the unset frequencies */
}  /* _clsin() */               /* and return 'ok' */

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

static int _getval (DTREE *dt, SCAN *scan, ATT *att)
{                               /* --- read (list of) values */
  int v1, v2;                   /* attribute values */
  int t;                        /* buffer for token */

  assert(dt && scan && att);    /* check the function arguments */
  t = sc_token(scan);           /* check for a name */
  if ((t != T_ID) && (t != T_NUM))   ERROR(E_VALEXP);
  v1 = att_valid(att, sc_value(scan));
  if (v1 < 0)                        ERROR(E_UNKVAL);
  if (dt->curr->vec[v1].child)       ERROR(E_DUPVAL);
  GET_TOK();                    /* get and consume an attribute value */
  while (sc_token(scan) == ','){/* read a value list (subset) */
    GET_TOK();                  /* consume ',' */
    t = sc_token(scan);         /* check for a name */
    if ((t != T_ID) && (t != T_NUM)) ERROR(E_VALEXP);
    v2 = att_valid(att, sc_value(scan));
    if (v2 < 0)                      ERROR(E_UNKVAL);
    if ((v2 == v1)              /* get and check the attribute value */
    ||  (dt_link(dt, v2, v1) < 0))   ERROR(E_DUPVAL);
    GET_TOK();                  /* link subtrees of decision tree */
  }                             /* and consume the attribute value */
  GET_CHR(':');                 /* consume ':' */
  return v1;                    /* return the value identifier */
}  /* _getval() */

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

static int _dtin (DTREE *dt, SCAN *scan)
{                               /* --- recursively read dec. tree */
  int    type;                  /* type of test attribute */