484 lines
12 KiB
C
484 lines
12 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <malloc.h>
|
|
#include "lceb.h"
|
|
|
|
static TREE *trees=NULL;
|
|
static int ntrees=0;
|
|
static NODE *freenodes=NULL;
|
|
static int totnodes=0;
|
|
|
|
NODE *get_node()
|
|
{
|
|
NODE *ret;
|
|
|
|
if (!freenodes) {
|
|
register int i;
|
|
totnodes+=ALLOCSIZE;
|
|
# ifdef DEBUG_MEM
|
|
printf("get_node: allocating %d new nodes - total nodes=%d\n", ALLOCSIZE, totnodes);
|
|
# endif
|
|
freenodes=malloc(ALLOCSIZE*sizeof(NODE));
|
|
for (i=0; i<ALLOCSIZE-1; ++i) { /* create chained list */
|
|
(freenodes+i)->left=NULL;
|
|
(freenodes+i)->right=NULL;
|
|
(freenodes+i)->next=freenodes+i+1;
|
|
}
|
|
(freenodes+ALLOCSIZE-1)->next=NULL;
|
|
}
|
|
ret=freenodes;
|
|
freenodes=ret->next;
|
|
ret->op=Nop;
|
|
ret->val=-1;
|
|
ret->eval=-1;
|
|
ret->next=NULL;
|
|
ret->left=NULL;
|
|
ret->right=NULL;
|
|
|
|
return ret;
|
|
}
|
|
|
|
int free_node(node)
|
|
NODE *node;
|
|
{
|
|
int n=0;
|
|
if (node->type==TREE_NODE) {
|
|
# ifdef DEBUG_TREE2
|
|
printf("free tree: ");
|
|
print_node(node, 3);
|
|
# endif
|
|
n+=free_node(node->left);
|
|
node->left=NULL;
|
|
n+=free_node(node->right);
|
|
node->right=NULL;
|
|
# ifdef DEBUG_TREE2
|
|
printf("free tree: ");
|
|
print_node(node, 3);
|
|
# endif
|
|
}
|
|
node->next=freenodes;
|
|
freenodes=node;
|
|
n++;
|
|
return n;
|
|
}
|
|
|
|
int compare_nodes(node1, node2, depth)
|
|
NODE *node1, *node2;
|
|
int depth;
|
|
{
|
|
int equal=0;
|
|
|
|
// we must also consider the case n1->left == n2->right, and vice-et-versa.
|
|
# ifdef DEBUG_TREE
|
|
if (depth==0) {
|
|
printf("compare trees: [ ");
|
|
print_node(node1, TREE_TOP, 0, 4);
|
|
printf(" ] and [ ");
|
|
print_node(node2, TREE_TOP, 0, 4);
|
|
printf(" ] ");
|
|
}
|
|
# endif
|
|
if (node1->type==node2->type) {
|
|
switch (node1->type) {
|
|
case TREE_LEAF:
|
|
if (node1->val==node2->val)
|
|
equal=1;
|
|
break;
|
|
case TREE_NODE:
|
|
if (node1->op == node2->op) {
|
|
if (compare_nodes(node1->left, node2->left, depth+1) &&
|
|
compare_nodes(node1->right, node2->right, depth+1)) {
|
|
equal=1;
|
|
} else if (compare_nodes(node1->left, node2->right, depth+1) &&
|
|
compare_nodes(node1->right, node2->left, depth+1)) {
|
|
equal=1;
|
|
}
|
|
}
|
|
break;
|
|
}
|
|
}
|
|
# ifdef DEBUG_TREE
|
|
if (depth==0) {
|
|
printf(" = %d\n", equal);
|
|
}
|
|
# endif
|
|
return equal;
|
|
}
|
|
|
|
void print_node(node, side, depth, details)
|
|
NODE *node;
|
|
char side;
|
|
int depth;
|
|
int details;
|
|
{
|
|
int i;
|
|
|
|
if (!node)
|
|
return;
|
|
|
|
switch (details) {
|
|
case 1: /* prefix */
|
|
if (node->type==TREE_NODE) {
|
|
printf("%c ", node->op);
|
|
} else {
|
|
printf("%d ", node->val);
|
|
}
|
|
print_node(node->left, TREE_LEFT, depth+1, details);
|
|
print_node(node->right, TREE_RIGHT, depth+1, details);
|
|
break;
|
|
case 0: /* postfix */
|
|
case 5: /* dc suitable */
|
|
print_node(node->left, TREE_LEFT, depth+1, details);
|
|
print_node(node->right, TREE_RIGHT, depth+1, details);
|
|
if (node->type==TREE_NODE) {
|
|
printf("%c ", node->op);
|
|
} else {
|
|
printf("%d ", node->val);
|
|
}
|
|
if (details==5 && depth==0)
|
|
printf("p");
|
|
break;
|
|
case 3: /* lisp */
|
|
if (node->type==TREE_NODE) {
|
|
if (!depth) {
|
|
printf("(%c", node->op);
|
|
//printf("(op");
|
|
} else {
|
|
//printf(" (op");
|
|
printf(" (%c", node->op);
|
|
}
|
|
} else {
|
|
printf(" %d", node->val);
|
|
}
|
|
print_node(node->left, TREE_LEFT, depth+1, details);
|
|
print_node(node->right, TREE_RIGHT, depth+1, details);
|
|
if (node->type==TREE_NODE) {
|
|
printf(")");
|
|
}
|
|
break;
|
|
case 4: /* infix */
|
|
if (node->type==TREE_NODE) {
|
|
printf("(");
|
|
}
|
|
print_node(node->left, TREE_LEFT, depth+1, details);
|
|
if (node->type==TREE_NODE) {
|
|
printf(" %c ", node->op);
|
|
} else {
|
|
printf("%d", node->val);
|
|
}
|
|
print_node(node->right, TREE_RIGHT, depth+1, details);
|
|
if (node->type==TREE_NODE) {
|
|
printf(")");
|
|
}
|
|
break;
|
|
case 2: /* tree */
|
|
/* left padding */
|
|
for (i=0; i<=depth; ++i)
|
|
printf(" ");
|
|
printf("%c: type:%s ", side, node->type==TREE_NODE? "node": "leaf");
|
|
if (details) {
|
|
printf("op=%c val=%d eval=%d", node->op, node->val, node->eval);
|
|
}
|
|
putchar('\n');
|
|
print_node(node->left, TREE_LEFT, depth+1, details);
|
|
print_node(node->right, TREE_RIGHT, depth+1, details);
|
|
break;;
|
|
}
|
|
}
|
|
|
|
void print_tree(tree, details)
|
|
TREE *tree;
|
|
int details;
|
|
{
|
|
switch (details) {
|
|
case 2:
|
|
print_node(tree->head, TREE_TOP, 0, details);
|
|
break;
|
|
case 0:
|
|
case 1:
|
|
case 3:
|
|
case 4:
|
|
//printf("Tree [%s] : ", tree->name);
|
|
print_node(tree->head, TREE_TOP, 0, details);
|
|
printf("\n");
|
|
break;
|
|
}
|
|
}
|
|
|
|
void print_trees(details)
|
|
int details;
|
|
{
|
|
TREE *tree=trees;
|
|
printf("There are %d trees:\n", ntrees);
|
|
while (tree) {
|
|
print_tree(tree, details);
|
|
tree=tree->next;
|
|
}
|
|
}
|
|
|
|
TREE *new_tree(name)
|
|
char *name;
|
|
{
|
|
TREE *tree;
|
|
|
|
tree=malloc(sizeof(TREE));
|
|
strcpy(tree->name, name);
|
|
tree->nodes=0;
|
|
tree->leaves=0;
|
|
tree->depth=0;
|
|
tree->head=NULL;
|
|
tree->next=trees;
|
|
trees=tree;
|
|
return tree;
|
|
}
|
|
|
|
|
|
NODE *dup_node(src)
|
|
NODE *src;
|
|
{
|
|
NODE *dst;
|
|
dst=get_node();
|
|
dst->type=src->type;
|
|
if (src->type==TREE_NODE) {
|
|
dst->op=src->op;
|
|
dst->left=dup_node(src->left);
|
|
dst->right=dup_node(src->right);
|
|
} else {
|
|
dst->val=src->val;
|
|
}
|
|
return dst;
|
|
}
|
|
|
|
/* untested - unused */
|
|
int calc_prof_node(node)
|
|
NODE *node;
|
|
{
|
|
int left, right;
|
|
|
|
if (node->type==TREE_LEAF) {
|
|
return 0;
|
|
} else {
|
|
left=calc_prof_node(node->left);
|
|
right=calc_prof_node(node->right);
|
|
node->prof=MAX(left, right)+1;
|
|
}
|
|
return node->prof;
|
|
}
|
|
|
|
NODE *build_tree(desc, size)
|
|
char *desc;
|
|
int size;
|
|
{
|
|
NODE *root, *node;
|
|
NODE *nodestack[1024]; /* TODO: make it dynamic */
|
|
int i, curnode=0;
|
|
|
|
# ifdef DEBUG_TREE
|
|
printf("tree %d desc=", ntrees);
|
|
for (i=0; i<size; ++i)
|
|
printf("%c", desc[i]);
|
|
putchar('\n');
|
|
# endif
|
|
root=get_node();
|
|
root->type=TREE_NODE;
|
|
nodestack[curnode++]=root;
|
|
|
|
for(i=1; i<size; ++i) {
|
|
node = get_node();
|
|
if (desc[i-1]=='1') {
|
|
nodestack[curnode-1]->left = node;
|
|
} else {
|
|
nodestack[curnode-1]->right = node;
|
|
curnode--;
|
|
}
|
|
if (desc[i]=='1') {
|
|
node->type=TREE_NODE;
|
|
nodestack[curnode++]=node;
|
|
} else {
|
|
node->type=TREE_LEAF;
|
|
}
|
|
}
|
|
return root;
|
|
}
|
|
|
|
/* generate reduced trees from static description */
|
|
void gen_reduced_trees(n)
|
|
int n;
|
|
{
|
|
int size=n*2+1, i;
|
|
TREE *tree;
|
|
char name[80];
|
|
char *seq1[]= {
|
|
"100"
|
|
};
|
|
char *seq2[]= {
|
|
"10100"
|
|
};
|
|
char *seq3[]= {
|
|
"1010100",
|
|
"1100100"
|
|
};
|
|
char *seq4[]= {
|
|
"101010100",
|
|
"101100100",
|
|
"110010100"
|
|
};
|
|
char *seq5[]= {
|
|
"10101010100",
|
|
"10101100100",
|
|
"10110010100",
|
|
"11001010100",
|
|
"11001100100",
|
|
"11010010100"
|
|
};
|
|
|
|
if (n<1 || n>=MAXINPUT) {
|
|
fprintf(stderr, "gen_reduced_trees: wrong leaves %d\n", n);
|
|
return;
|
|
}
|
|
# ifdef DEBUG_TREE
|
|
printf("gen_reduced_trees(leaves=%d)\n", n);
|
|
# endif
|
|
|
|
switch (n) {
|
|
case 1:
|
|
ntrees++;
|
|
sprintf(name, "Tree %d", ntrees);
|
|
tree=new_tree(name);
|
|
tree->head=build_tree(seq1[0], size);
|
|
break;
|
|
case 2:
|
|
ntrees++;
|
|
sprintf(name, "Tree %d", ntrees);
|
|
tree=new_tree(name);
|
|
tree->head=build_tree(seq2[0], size);
|
|
break;
|
|
case 3:
|
|
for (i=0; i<2; ++i) {
|
|
ntrees++;
|
|
sprintf(name, "Tree %d", ntrees);
|
|
tree=new_tree(name);
|
|
tree->head=build_tree(seq3[i], size);
|
|
}
|
|
break;
|
|
case 4:
|
|
for (i=0; i<3; ++i) {
|
|
ntrees++;
|
|
sprintf(name, "Tree %d", ntrees);
|
|
tree=new_tree(name);
|
|
tree->head=build_tree(seq4[i], size);
|
|
}
|
|
break;
|
|
case 5:
|
|
for (i=0; i<6; ++i) {
|
|
ntrees++;
|
|
sprintf(name, "Tree %d", ntrees);
|
|
tree=new_tree(name);
|
|
tree->head=build_tree(seq5[i], size);
|
|
}
|
|
break;
|
|
}
|
|
return;
|
|
}
|
|
|
|
void gen_tree(seq, n, nb1, nb0, reduced)
|
|
char *seq;
|
|
int n; /* number of nodes */
|
|
int nb1; /* number of "1" */
|
|
int nb0; /* number of "0" */
|
|
int reduced;
|
|
{
|
|
char name[80];
|
|
TREE *tree;
|
|
NODE *node;
|
|
int i;
|
|
|
|
# ifdef DEBUG_TREE
|
|
printf("gen_tree(n=%d, nb1=%d, nb0=%d)\n", n, nb1, nb0);
|
|
# endif
|
|
if ((nb1 + nb0) == 2*n) { /* end */
|
|
seq[2*n] = '0';
|
|
seq[2*n+1] = 0;
|
|
node=build_tree(seq, 2*n+1);
|
|
if (reduced) {
|
|
for (i=0; i<ntrees; ++i) {
|
|
if (compare_nodes(node, nth_tree(i)->head, 0)) {
|
|
# ifdef DEBUG_TREE
|
|
printf("gen_tree: skipping unused tree (%d nodes freed)\n", free_node(node));
|
|
# else
|
|
free_node(node);
|
|
# endif
|
|
node=NULL;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
if (node) {
|
|
ntrees++;
|
|
sprintf(name, "Tree %d", ntrees);
|
|
tree=new_tree(name);
|
|
tree->head=node;
|
|
}
|
|
return;
|
|
}
|
|
|
|
if (nb1 >= nb0 && nb1 < n) {
|
|
seq[nb1+nb0] = '1';
|
|
gen_tree(seq, n, nb1+1, nb0, reduced);
|
|
}
|
|
|
|
if(nb0 < nb1 && nb1 <=n) {
|
|
seq[nb1+nb0] = '0';
|
|
gen_tree(seq, n, nb1, nb0+1, reduced);
|
|
}
|
|
}
|
|
|
|
TREE *nth_tree(n)
|
|
int n;
|
|
{
|
|
int i;
|
|
TREE *tree=trees;
|
|
for (i=0; i<n && tree; ++i) {
|
|
tree=tree->next;
|
|
}
|
|
return tree;
|
|
}
|
|
|
|
int n_trees()
|
|
{
|
|
return ntrees;
|
|
}
|
|
|
|
#ifdef STANDALONE
|
|
int main(ac, av)
|
|
int ac;
|
|
char **av;
|
|
{
|
|
int n, details=0, type=0;
|
|
char array[1024];
|
|
|
|
if (ac<3 || ac>4) {
|
|
fprintf(stderr, "usage: %s type nodes [display]\n", *av);
|
|
fprintf(stderr, "type : 0 for Catalan, 1 for Wedderburn\n");
|
|
fprintf(stderr, "display can be 0 (RPN, default, 1 (polish), 2 (details), 3 (lisp notation), 4 (parenthesed notation)\n");
|
|
exit (1);
|
|
}
|
|
if (ac==4) {
|
|
details=atoi(av[3]);
|
|
}
|
|
type=atoi(av[1]);
|
|
n=atoi(av[2]);
|
|
if (type == 0) {
|
|
printf("generating Calalan tree...\n");
|
|
gen_tree(array, n, 0, 0, 0);
|
|
} else {
|
|
printf("generating Wedderburn tree...\n");
|
|
gen_tree(array, n, 0, 0, 1);
|
|
//gen_reduced_trees(n);
|
|
}
|
|
print_trees(details);
|
|
exit(0);
|
|
}
|
|
#endif
|