frqtab.c

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

  double *df; const double *sf; /* to traverse the table elements */
  int    *di; const int    *si; /* to traverse the dest. vectors */
  
  assert(dst && src             /* check the function arguments */
      && (dst->xsize >= src->xcnt)
      && (dst->ysize >= src->ycnt));
  dst->xcnt = src->xcnt;        /* copy the current size */
  dst->ycnt = src->ycnt;        /* of the frequency table */
  for (x = dst->xcnt +1; --x >= 0; ) {
    sf = src->frq_xy[x] +dst->ycnt;
    df = dst->frq_xy[x] +dst->ycnt;
    for (y = dst->ycnt +1; --y >= 0; )
      *--df = *--sf;            /* traverse and copy the elements */
  }                             /* of the joint frequency table */
  si = src->dsts  +dst->xcnt;   /* traverse and copy the */
  di = dst->dsts  +dst->xcnt;   /* destination indicators */
  for (x = dst->xcnt +1; --x >= 0; ) *--di = *--si;
  sf = src->frq_x +dst->xcnt;   /* traverse and copy the */
  df = dst->frq_x +dst->xcnt;   /* marginal x-frequencies */
  for (x = dst->xcnt +1; --x >= 0; ) *--df = *--sf;            
  sf = src->frq_y +dst->ycnt;   /* traverse and copy the */
  df = dst->frq_y +dst->ycnt;   /* marginal y-frequencies */
  for (y = dst->ycnt +1; --y >= 0; ) *--df = *--sf;
  dst->known = src->known;      /* copy number of cases */
  dst->frq   = src->frq;        /* with known value and */
}  /* ft_copy() */              /* the total number of cases */

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

void ft_marg (FRQTAB *ftab)
{                               /* --- marginalize a frequency table */
  int    x, y;                  /* loop variables */
  int    *d;                    /* to traverse destination references */
  double **p;                   /* to traverse joint table columns */
  double *fxy, *fx, *fy;        /* to traverse frequencies */

  assert(ftab);                 /* check the function arguments */
  ftab->known = 0;              /* clear the total for knowns */
  for (fx = ftab->frq_x +(x = ftab->xcnt), ++x; --x >= 0; )
    *--fx = 0;                  /* clear the marginal x-frequencies */
  for (fy = ftab->frq_y +(y = ftab->ycnt), ++y; --y >= 0; )
    *--fy = 0;                  /* clear the marginal y-frequencies */
  fx = ftab->frq_x  +ftab->xcnt;
  p  = ftab->frq_xy +ftab->xcnt +1;
  for (d = ftab->dsts +(x = ftab->xcnt); --x >= 0; ) {
    --p; --fx;                  /* traverse the other columns */
    if (*--d >= 0) {            /* skip combined columns and */
      *fx = -1; continue; }     /* invalidate their marginals */
    fy  = ftab->frq_y +ftab->ycnt;
    fxy = *p +ftab->ycnt;       /* traverse the rows of the column */
    for (y = ftab->ycnt; --y >= 0; ) {
      *--fy += *--fxy;          /* marginalize for known y */
      *  fx += *  fxy;          /* and         for known x */
    }                           /* (sum rows and columns) */
    *--fy += *--fxy;            /* marginalize for unknown y */
    ftab->known += *fx;         /* compute total for knowns */
  }
  for (--fx, fxy = *--p +(y = ftab->ycnt); --y >= 0; )
    *fx += *--fxy;              /* marginalize for unknown x */
  ftab->frq = ftab->known       /* compute the overall total */
            + ftab->frq_x    [-1]
            + ftab->frq_y    [-1]
            + ftab->frq_xy[0][-1];
}  /* ft_marg() */

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

void ft_addwm (FRQTAB *ftab, int x, int y, double frq)
{                               /* --- add frequency with marginals */
  assert(ftab                   /* check the function arguments */
     &&  (x <= ftab->xcnt) && (y <= ftab->ycnt));
  ftab->frq_xy[x+1][y] += frq;  /* add the frequency */
  ftab->frq_x [x]      += frq;  /* to the joint and */
  ftab->frq_y [y]      += frq;  /* to the marginal tables */
}  /* ft_addwm() */

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

void ft_move (FRQTAB *ftab, int xsrc, int xdst, int y, double frq)
{                               /* --- move frequency */
  assert(ftab                   /* check the function arguments */
      && (xsrc >= 0) && (xsrc < ftab->xcnt)
      && (xdst >= 0) && (xdst < ftab->xcnt)
      && (y    >= 0) && (y    < ftab->ycnt));
  ftab->frq_xy[xsrc+1][y] -= frq;  /* move the frequency */
  ftab->frq_xy[xdst+1][y] += frq;
  ftab->frq_x [xsrc]      -= frq;
  ftab->frq_x [xdst]      += frq;
}  /* ft_move() */

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

void ft_comb (FRQTAB *ftab, int xsrc, int xdst)
{                               /* --- combine two columns */
  int    i;                     /* loop variable */
  double *src, *dst;            /* to traverse the frequencies */
  double marg;                  /* marginal frequency */

  assert(ftab                   /* check the function arguments */
      && (xsrc >= 0) && (xsrc < ftab->xcnt)
      && (xdst >= 0) && (xdst < ftab->xcnt)
      && (ftab->dsts[xsrc] < 0));
  ftab->dsts[xsrc] = xdst;      /* note reference to destination */
  src  = ftab->frq_x +xsrc;     /* get pointer to source marginal */
  marg = *src; *src = -1;       /* and note and invalidate it */
  do {                          /* traverse destination columns */
    i   = ftab->ycnt +1;        /* get pointers to the table columns */
    src = ftab->frq_xy[xsrc+1] +i; /* traverse the joint frequencies */
    dst = ftab->frq_xy[xdst+1] +i; /* and sum them in the destination */
    while (--i >= 0) *--dst += *--src;
    ftab->frq_x[xdst] += marg;  /* sum marginal frequencies */
    xdst = ftab->dsts[xdst];    /* get next destination column */
  } while (xdst >= 0);          /* loop, while next column found */
}  /* ft_comb() */

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

void ft_uncomb (FRQTAB *ftab, int xsrc)
{                               /* --- uncombine a column */
  int    i, xdst;               /* loop variable, buffer */
  double *src, *dst;            /* to traverse the frequencies */
  double marg = 0;              /* marginal frequency */

  assert(ftab                   /* check the function arguments */
      && (xsrc >= 0) && (xsrc < ftab->xcnt));
  xdst = ftab->dsts[xsrc];      /* get the first destination column */
  if (xdst < 0) return;         /* if column is not combined, abort */
  ftab->dsts[xsrc] = -1;        /* clear the destination reference */
  for (src = ftab->frq_xy[xsrc+1] +(i = ftab->ycnt); --i >= 0; )
    marg += *--src;             /* sum the joint frequencies */
  ftab->frq_x[xsrc] = marg;     /* and store this marginal */
  do {                          /* traverse destination columns */
    i   = ftab->ycnt +1;        /* get pointers to the table columns */
    src = ftab->frq_xy[xsrc+1] +i; /* traverse the joint frequencies */
    dst = ftab->frq_xy[xdst+1] +i; /* and subtract them */
    while (--i >= 0) *--dst -= *--src;
    ftab->frq_x[xdst] -= marg;  /* get pointer to dest. marginal */
    xdst = ftab->dsts[xdst];    /* get next destination column */
  } while (xdst >= 0);          /* loop, while next column found */
}  /* ft_uncomb() */

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

int ft_dest (FRQTAB *ftab, int x)
{                               /* --- get the destination of a column */
  int t;                        /* temporary buffer */

  assert(ftab                   /* check the function arguments */
      && (x >= 0) && (x < ftab->xcnt));
  while ((t = ftab->dsts[x]) >= 0) x = t;
  return x;                     /* follow references and return id */
}  /* ft_dest() */

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

void ft_alldst (FRQTAB *ftab, int *dsts)
{                               /* --- get all column destinations */
  int i;                        /* loop variable */
  int x, t;                     /* temporary buffers */

  assert(ftab && dsts);         /* check the function arguments */
  for (i = 0; i < ftab->xcnt; i++) {
    x = i;                      /* default: index of source column */
    while ((t = ftab->dsts[x]) >= 0) x = t;
    *dsts++ = x;                /* follow references and */
  }                             /* set id of destination column */
}  /* ft_alldst() */

/*--------------------------------------------------------------------*/
#ifdef FT_EVAL

double ft_eval (FRQTAB *ftab, int measure, double *params)
{                               /* --- evaluate a frequency table */
  int m = measure & 0xff;       /* flagless measure */

  assert(ftab);                 /* check the function arguments */
  if ((m <= FEM_NONE) || (m >= FEM_UNKNOWN))
    return 0;                   /* check the measure code */
  return _evalfn[m](ftab, measure, params);
}  /* ft_eval() */              /* return the evaluation result */

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

const char* ft_mname (int measure)
{                               /* --- get name of evaluation measure */
  static char buf[64];          /* buffer for measure name */
  int m = measure & 0xff;       /* index in names vector */

  if ((m < FEM_NONE) || (m > FEM_UNKNOWN))
    m = FEM_UNKNOWN;            /* check measure code */
  strcpy(buf, (measure & FEF_WGTD) ? "weighted " : "");
  strcat(buf, mnames[m]);       /* build measure name */
  return buf;                   /* and return it */
}  /* ft_mname() */

#endif
/*--------------------------------------------------------------------*/
#ifndef NDEBUG

void ft_show (FRQTAB *ftab)
{                               /* --- show a frequency table */
  int    x, y;                  /* loop variables */
  double **p;                   /* to traverse joint table columns */
  double *fx, *fy;              /* to traverse frequencies */

  assert(ftab);                 /* check the function argument */
  p = ftab->frq_xy;             /* get a pointer to the table and */
  printf("%6.1f |", p[0][-1]);  /* print the frequency of unknowns */
  for (x = ftab->xcnt; --x >= 0; ) /* print the frequency */
    printf(" %6.1f", (*++p)[-1]);  /* of unknown x and y */
  fy = ftab->frq_y;             /* get a pointer to the row dist. */
  printf(" | %6.1f\n", fy[-1]); /* and print the row marginal */
  for (x = ftab->xcnt; --x >= 0; ) printf("-------");
  printf("-----------------\n");/* print a separator */

  for (y = ftab->ycnt; --y >= 0; ) {
    p = ftab->frq_xy;           /* get a pointer to the table */
    printf("%6.1f |", p[0][y]); /* print the frequency of unknowns */
    for (x = ftab->xcnt; --x >= 0; )  /* traverse the columns and */
      printf(" %6.1f", (*++p)[y]); /* print the joint frequencies */
    printf(" | %6.1f\n", fy[y]);   /* and the row marginal */
  }
  for (x = ftab->xcnt; --x >= 0; ) printf("-------");
  printf("-----------------\n");/* print separator */

  fx = ftab->frq_x -1;          /* get a pointer to the column dist. */
  printf("%6.1f |", *fx);       /* print marginal for unknowns */
  for (x = ftab->xcnt; --x >= 0; ) /* traverse marginal frequencies */
    printf(" %6.1f", *++fx);       /* for knowns and print them */
  printf(" | %6.1f\n", ftab->known);
}  /* ft_show() */              /* finally print the total freq. */

#endif