tree.c

source codes for ltr

/*********************************************************************/
/*        LINEAR TREE for Supervised Learning                        */
/*        Versao 1.0 (10/12/1997)                                    */
/*        Developed by: Joao Gama                                    */
/*                LIACC - Uni.do Porto                               */
/*                [e-mail]                                    */
/*-------------------------------------------------------------------*/
/*  File: tree.c                                                     */
/*********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
#include <math.h>
#include "tree.h"
#include "utils.h"

/******************************/
/* PRIVATE Prototyps          */
/******************************/
static void writetree(int fo, Tree *tree,  int (func)(int, void *, int), int nr_cl);
static int write_node(int fd, Tree *tree,  int (func)(int, void *, int), int nr_cl);
static Tree *readtree(int fd, void *(func)(int, int), int nr_cl);
static Tree *read_node(int fd, TYPE_NODE tipo, void *(func)(int, int), int Nr_Cl);
/******************************/
/* PUBLIC  FUNCTIONS          */
/******************************/
/******************************/
/*         Make Tree INFO     */
/******************************/
TreeInfo *MakeTreeInfo()
{
  TreeInfo *treeinfo;

  treeinfo = (TreeInfo *) calloc(1, sizeof(TreeInfo));
  return treeinfo;
}
/******************************/
/*         Make Tree          */
/******************************/
Tree *Make_Tree\
(void *data, int node, int nr_desc, Tree *ascen, TYPE_NODE tipo)
{
  Tree *arvore = NULL, **descendents = NULL;
  
  if ((arvore = (Tree *) malloc(sizeof(Tree))) != NULL) {
    arvore->data = data;
    arvore->node = node;
    arvore->tipo = tipo;
    arvore->nr_descendents = nr_desc;
    arvore->ascendent = ascen;
    arvore->descendents = NULL;
    if (nr_desc) {
      if ((descendents = (Tree **) calloc(nr_desc, sizeof(Tree *))) != NULL) {
	arvore->descendents = --descendents;
	return arvore;
      }
    }
    else
      return arvore;
  }
  fprintf(stderr, "Make_Tree: Out of memory !\n");
  return NULL;
}

void Set_Descendent(Tree *tree, int nr, Tree *descendent)
{
  if (nr > 0 && nr <= tree->nr_descendents)
    tree->descendents[nr] = descendent;
  else
    fprintf(stderr, "Set_Descendent: Invalid offset !\n");
}


TreeInfo *Recompute_Nodes(Tree *tree, int *depth)
{
  register int i;
  int act_depth = 0;
  static TreeInfo *treeinfo = NULL;

  if (!treeinfo) treeinfo = MakeTreeInfo();

  ++(NODES(treeinfo));
  switch(tree->tipo) {
  case leaf:
    ++(LEAVES(treeinfo));
    *depth = 1;
    /*    return treeinfo;*/
    break;
  case split_discrete:
    ++DEPTH(treeinfo);
    for(i = 1; i <= NR_DESCENDENTS(tree); i++) {
      act_depth = 0;
      Recompute_Nodes(DESCENDENT(tree, i), &act_depth);
      if (act_depth > *depth)  *depth = act_depth;
    }
    ++(*depth);
    /*    return treeinfo;*/
    break;
  case split_continuous:
  case split_linear:
    ++DEPTH(treeinfo);
    Recompute_Nodes(DESCENDENT(tree, 1), &act_depth);
    if (act_depth > *depth)  *depth = act_depth;
    act_depth = 0;
    Recompute_Nodes(DESCENDENT(tree, 2), &act_depth);
    if (act_depth > *depth)  *depth = act_depth;
    ++(*depth);
    /*    return treeinfo;*/
    break;
  }
  return treeinfo;
}
/**********************************************************/
/*          Write Tree to a file                          */
/**********************************************************/
int Write_Tree(char *FileName, Tree *tree, int (func)(int, void *, int),int nr_cl)
{
  int fd;

  if ((fd = creat(new_strcat(FileName, ".tree"), 0660)) != -1) {
    writetree(fd, tree, func, nr_cl);
    close(fd);
    return TRUE;
  }
  fprintf(stderr, "Can not open file %s.tree\n", FileName);
  return FALSE;
}

static void writetree(int fo, Tree *tree,  int (func)(int, void *, int), int nr_cl)
{
  register int i;

  switch(tree->tipo) {
  case leaf:
    break;
  case split_discrete:
    for(i = 1; i <= tree->nr_descendents; i++) 
      writetree(fo, tree->descendents[i], func, nr_cl);
    break;  
  case split_continuous:
  case split_linear:
    writetree(fo, tree->descendents[1], func, nr_cl);
    writetree(fo, tree->descendents[2], func, nr_cl);
    break;
  }
  write_node(fo, tree, func, nr_cl);
}

static int write_node(int fd, Tree *tree,  int (func)(int, void *, int), int nr_cl)
{
  if (write(fd, &tree->tipo, sizeof(TYPE_NODE)) == sizeof(TYPE_NODE))
    if (write(fd, &tree->node, sizeof(int)) == sizeof(int))   
      if (write(fd, &tree->nr_descendents, sizeof(int)) == sizeof(int)) {
	/*	printf("Escrever no %d %d\n", tree->node, tree->nr_descendents);*/
	func(fd, tree->data, nr_cl);
	return TRUE;
      }
  return FALSE;
}
/**********************************************************/
/*          Read Tree from a file                         */
/**********************************************************/
Tree *Read_Tree(char *FileName, void *(func)(int, int), int nr_cl)
{
  int fd;
  Tree *tree = NULL;
  
  if ((fd = open(new_strcat(FileName, ".tree"), O_RDONLY)) != -1) {
    tree = readtree(fd, func, nr_cl);
    close(fd);
  }
  else
    fprintf(stderr, "Can not open file %s.tree\n", FileName);
  return tree;  
}

static Tree *readtree(int fd, void *(func)(int, int), int nr_cl)
{
  register int i;
  Tree *node = NULL, *no = NULL;
  Stack *s = NULL;
  TYPE_NODE tipo;

  while (read(fd, &tipo, sizeof(TYPE_NODE)) == sizeof(TYPE_NODE)) { 
    if (tipo != -1) {
      if ((node = read_node(fd, tipo, func, nr_cl)) != NULL) {
	if (node->nr_descendents) {
	  node->descendents = (Tree **) calloc(node->nr_descendents, sizeof(Tree *));
	  --(node->descendents);
	  for(i = node->nr_descendents; i > 0; i--) {
	    if ((no = (Tree *) pop(s)) != NULL)
	      no->ascendent = node;
	    node->descendents[i] = no;
	  }
	}
      }
    }
    else node = NULL;
    s = push(node, s);
  }
  return (Tree *) pop(s);
}

static Tree *read_node(int fd, TYPE_NODE tipo, void *(func)(int, int), int Nr_Cl)
{
  Tree *tree = NULL;

  if ((tree = (Tree *) malloc(sizeof(Tree))) != NULL) {
    tree->tipo = tipo;
    if (read(fd, &tree->node, sizeof(int)) == sizeof(int))
      if (read(fd, &tree->nr_descendents, sizeof(int)) == sizeof(int)) {
	tree->data = (void *) func(fd, Nr_Cl);
	return tree;
      }
  }
  return NULL;
}
/**********************************************************/
/*                  Show Tree                             */
/**********************************************************/
void show_tree\
(Tree *tree, void *p1, void (* func)(void *, void *,int,TYPE_NODE), int off)
{
  register int i = 0, j;

  switch (tree->tipo) {
  case leaf:
    for(j = 0; j < off; j++)    printf("|\t");
    func(p1, tree->data, i, tree->tipo);
    break;
  case split_discrete:
  case split_continuous:
  case split_linear:
    for(i = 1; i <= tree->nr_descendents; i++) {
      for(j = 0; j < off; j++)    printf("|\t");
      func(p1, tree->data, i, tree->tipo);
      show_tree(tree->descendents[i], p1, func, off+1);
    }
    break;
  }
}