/*----------------------------------------------------------------------  File    : fptree.c  Contents: frequent pattern tree management  Author  : Christian Borgelt  History : 2004.11.21 file created            2004.11.22 second projection added, bonsai pruning added            2004.12.09 adapted to changed report function            2004.12.10 adapted to general memory management system            2004.12.28 bug in function fpt_delete fixed            2005.12.06 bug in function _project2 fixed            2006.11.26 reuse of item set prefix made possible----------------------------------------------------------------------*/#include <stdio.h>#include <stdlib.h>#include <assert.h>#include "fptree.h"#ifdef STORAGE#include "storage.h"#endif/*----------------------------------------------------------------------  Preprocessor Definition----------------------------------------------------------------------*/#define BLKSIZE    6553         /* block size for memory management *//*----------------------------------------------------------------------  Type Definition----------------------------------------------------------------------*/typedef FPTREE* PROJFN (FPTREE *fpt, int item);typedef struct {                /* --- structure for rec. search */  int      min;                 /* minimum number of items */  int      max;                 /* maximum number of items */  int      supp;                /* minimum support (num. of trans.) */  int      bonsai;              /* flag for pruning to bonsai */  PROJFN   *proj;               /* projection function */  FPTREPFN *report;             /* report function for results */  void     *data;               /* user data for report function */  int      cnt;                 /* number of frequent item sets */  int      items[1];            /* item vector for reporting */} FPRS;                         /* (structure for rec. search) *//*----------------------------------------------------------------------  Main Functions----------------------------------------------------------------------*/static FPTREE* _create (MEMSYS *mem, int cnt){                               /* --- create a base f.p. tree */  FPTREE  *fpt;                 /* created frequent pattern tree */  FPTLIST *list;                /* to traverse the node lists */  assert(cnt > 0);              /* check the function arguments */  fpt = (FPTREE*)malloc(sizeof(FPTREE) +(cnt-1) *sizeof(FPTLIST));  if (!fpt) return NULL;        /* allocate the base structure */  fpt->cnt = cnt;               /* and note the number of items */  if (mem) fpt->mem = mem;      /* if a memory management is given, */  else {                        /* simply store it, otherwise */    fpt->mem = ms_create(sizeof(FPTNODE), BLKSIZE);    if (!fpt->mem) { free(fpt); return NULL; }  }                             /* allocate a memory system */  for (list = fpt->lists +cnt; --cnt >= 0; ) {    (--list)->cnt = 0; list->node = NULL; }  return fpt;                   /* initialize the node lists and */}  /* _create() */              /* return the created f.p. tree *//*--------------------------------------------------------------------*/static int _build (FPTREE *fpt, FPTNODE *parent,                   TASET *taset, int lft, int rgt, int pos){                               /* --- recursively build f.p. tree */  int     i, k;                 /* loop variable, buffer */  int     item;                 /* to traverse the items at pos */  FPTNODE *node;                /* created freq. pattern tree node */  assert(fpt && taset && (pos >= 0)); /* check the function arguments */  while ((lft <= rgt) && (tas_tsize(taset, lft) <= pos))    lft++;                      /* skip trans. that are too short */  if (lft > rgt) return 0;      /* check for an empty range */  item = k = tas_tract(taset, i = rgt)[pos];    /* get first item */  do {                          /* traverse the longer transactions */    while (--i >= lft) {        /* while not at start of section */      k = tas_tract(taset, i)[pos];      if (k != item) break;     /* try to find a transaction */    }                           /* with a different item */    node = ms_alloc(fpt->mem);  /* create a new tree node */    if (!node) return -1;       /* for the current item */    node->item   = item;        /* and store the item */    node->succ   = fpt->lists[item].node;    fpt->lists[item].node = node;    node->parent = parent;      /* insert the node into the item list */    node->copy   = NULL;        /* and compute and sum the support */    fpt->lists[item].cnt += node->cnt = rgt -i;    if (_build(fpt, node, taset, i+1, rgt, pos+1) != 0)      return -1;                /* build the child node recursively */    item = k; rgt = i;          /* remove processed transaction from */  } while (lft <= rgt);         /* the interval and note next item */  return 0;                     /* return 'ok' */}  /* _build() *//*--------------------------------------------------------------------*/FPTREE* fpt_create (TASET *taset){                               /* --- create a freq. pattern tree */  FPTREE *fpt;                  /* created frequent pattern tree */  assert(taset);                /* check the function argument */  fpt = _create(NULL, is_cnt(tas_itemset(taset)));  if (!fpt) return NULL;        /* allocate a base f.p. tree */  fpt->itemset = tas_itemset(taset);  fpt->tra     = tas_cnt(taset);  if ((fpt->tra > 0)            /* if there is at least one trans. */  &&  (_build(fpt, NULL, taset, 0, fpt->tra -1, 0) != 0)) {    fpt_delete(fpt); return NULL; }  return fpt;                   /* recursively build the frequent */}  /* fpt_create() */           /* pattern tree and return it *//*----------------------------------------------------------------------The above function assumes that the items in each transaction in tasetare sorted and that the transactions are sorted accordingly.----------------------------------------------------------------------*/void fpt_delete (FPTREE *fpt){                               /* --- delete a freq. pattern tree */  assert(fpt);                  /* check the function argument */  ms_delete(fpt->mem);          /* delete the memory system */  free(fpt);                    /* and the base structure */}  /* fpt_delete() *//*--------------------------------------------------------------------*/static void _prune (FPTREE *fpt){                               /* --- prune nodes for last item */  FPTNODE *node, *buf;          /* to traverse the nodes to delete */  assert(fpt);                  /* check the function argument */  for (node = fpt->lists[--fpt->cnt].node; node; ) {    buf  = node;                /* while there is another node */    node = node->succ;          /* note the current node and */    ms_free(fpt->mem, buf);     /* remove it from the list, */  }                             /* and then delete the node */}  /* _prune() *//*--------------------------------------------------------------------*/static void _detach (FPTREE *fpt){                               /* --- detach a projection */  FPTNODE *node, *anc;          /* to traverse the ancestors */  assert(fpt);                  /* check the function argument */  node = fpt->lists[--fpt->cnt].node;  while (node) {                /* while there is another node */    for (anc = node->parent; anc && anc->copy; anc = anc->parent)      anc->copy = NULL;         /* clear the copy pointers */    anc  = node;                /* note the current node and */    node = node->succ;          /* remove it from the list, */    ms_free(fpt->mem, anc);     /* then delete the node */  }                             /* (prune deepest tree level) */}  /* _detach() *//*--------------------------------------------------------------------*/static void _cleanup (FPTREE *fpt, FPTREE *proj){                               /* --- clean up after failure */  assert(fpt && proj);          /* check the function argument */  _detach(fpt);                 /* detach projection from tree */  while (proj->cnt > 0) _prune(proj);  free(proj);                   /* delete the projection */}  /* _cleanup() */             /* (only called on failure) *//*--------------------------------------------------------------------*/static FPTREE* _project1 (FPTREE *fpt, int item){                               /* --- project a freq. pattern tree */  int     i;                    /* loop variable */  FPTREE  *proj;                /* projected frequent pattern tree */  FPTNODE *node, *anc, *copy;   /* to traverse the tree nodes */  FPTNODE **prev;               /* to link copies to their ancestors */  FPTLIST *lists;               /* to access the node lists */  assert(fpt);                  /* check the function argument */  proj = _create(fpt->mem, item);  if (!proj) return NULL;       /* create a base freq. pattern tree */  proj->itemset = fpt->itemset; /* note the underlying item set */  lists = proj->lists;          /* get the node lists of the proj. */  for (node = fpt->lists[item].node; node; node = node->succ) {    prev = NULL;                /* traverse the nodes for the item */    for (anc = node->parent; anc && !anc->copy; anc = anc->parent) {      anc->copy =               /* traverse and copy all ancestors */      copy = ms_alloc(fpt->mem);        /* that are not yet copied */      if (!copy) { _cleanup(fpt, proj); return NULL; }      if (prev) *prev = copy;   /* set parent link from child */      copy->item = i = anc->item;      copy->succ = lists[i].node;      lists[i].node = copy;     /* insert copy into corresp. list */      lists[i].cnt += copy->cnt = node->cnt;      copy->copy = NULL;        /* set the support of the node */      prev = &copy->parent;     /* and note the parent pointer */    }                           /* for later linking */    if (prev)                   /* set last parent pointer */      *prev = (anc) ? anc->copy : NULL;    for ( ; anc; anc = anc->parent) {      anc->copy->cnt       += node->cnt;      lists[anc->item].cnt += node->cnt;