btree.c

#include <stdlib.h>
#include <stdio.h>
#include "globals.h"
#include "btree.h"

struct _BoolNode {
  int val; // si left != 0, val prends la valeur de la variable concerné. Sinon val prends une valeure booléenne de feuille
  struct _BoolNode* left; // si 0
  struct _BoolNode* right; // si 1
};

struct _BoolTree {
  BoolNode* root;
};

static void bnode_free(BoolNode* n) {
  if(n==0) return;
  bnode_free(n->left);
  bnode_free(n->right);
  free(n);
}
extern void btree_free(BoolTree* tree) {
  bnode_free(tree->root);
}

extern BoolTree* btree_createTreeWith(BoolNode* root) {
  BoolTree* tree = malloc(sizeof(*tree));
  tree->root = root;
  return tree;
}

extern BoolNode* btree_newNode(BoolNode* l, char var, BoolNode* r) {
  BoolNode* node = malloc(sizeof(*node));
  node -> val = var;
  node -> left = l;
  node -> right = r;
  return node;
}

extern BoolNode* btree_newLeaf(int b) {
  BoolNode* node = malloc(sizeof(*node));
  node -> val = b;
  node -> left = 0;
  node -> right = 0;
  return node;
}

extern int btree_equals(BoolNode* a, BoolNode* b) {
  if(a==0) return (b==0);
  if(b==0) return FALSE;
  if(a->left==0) return b!=0 && b->left==0 && a->val == b->val;
  return btree_equals(a->left, b->left) && btree_equals(a->right, b->right);
}

static BoolNode* rec_btree_simplify(BoolNode* node) {
  if(node!=0 && node->left!=0) {
    node->left = rec_btree_simplify(node->left);
    node->right = rec_btree_simplify(node->right);
    if(btree_equals(node->left, node->right)) {
      return node->left;
    }
  }
  return node;
}

extern BoolTree* btree_simplify(BoolTree* tree) {
  tree->root = rec_btree_simplify(tree->root);
  return tree;
}

extern FunctionNode* btree_toFunctionNode(BoolNode* node, FunctionNode* conjClause, FunctionNode* root) {
  if(node==0) return 0;
  if(node->left==0) {
    if(node->val==1) { // attach conjonctive clause to root only if leaf is true
      root = (root==0) ? conjClause : ftree_newBin(root, '+', conjClause);
    }
    return root;
  }
  FunctionNode *left, *right;
  left = ftree_newNot(ftree_newVar((char)node->val)); // left is NOT for the current var
  if(conjClause!=0) {
    left = ftree_newBin(left, '*', conjClause);
  }
  right = ftree_newVar((char)node->val);
  if(conjClause!=0) {
    right = ftree_newBin(right, '*', conjClause);
  }
  
  root = btree_toFunctionNode(node->left, left, root);
  root = btree_toFunctionNode(node->right, right, root);
  return root;
}

extern FunctionTree* btree_toFunctionTree(BoolTree* tree) {
  FunctionNode* root = btree_toFunctionNode(tree->root, 0, 0);
  if(root==0)
    root = ftree_newBool(1);
  return ftree_createWithNode(root);
}

/**
 * id = 1 at first call
 */
static void rec_btree_printDot(BoolNode* node, FILE* out) {
  if(node==0) return;
  if(node->left==0) {
    // Leaf
    fprintf(out, "  n%p [label=\"%d\"]\n", node, node->val);
  }
  else {
    // Node
    fprintf(out, "  n%p [label=\"%c\"]\n", node, (char)node->val);
    fprintf(out, "  n%p -- n%p\n", node, node->left);
    fprintf(out, "  n%p -- n%p\n", node, node->right);
    rec_btree_printDot(node->left, out);
    rec_btree_printDot(node->right, out);
  }
}

extern void btree_printDot(BoolTree* btree, FILE* out) {
  fprintf(out, "## Generated by Boolean Functions v%g\n", VERSION);
  fprintf(out, "graph {\n");
  rec_btree_printDot(btree->root, out);
  fprintf(out, "}\n");
}