# include <stdio.h>
# include <stdlib.h>
# include "util.h"
# include "tree.h"

ARITY *label_arities;
LABEL max_label;


UINT tree_arity(t) TREE t; { return label_arities[t -> label]; }

TREE tree_new( l)
     LABEL  l;
     {
     ARITY n = label_arities[l];
     ARITY i;

     TREE t = (TREE) MALLOC ( (sizeof * t) );
     KIDS(t) = (TREE *) MALLOC(( n * (sizeof t) ));
     
     if (l > max_label) {
         printf("Invalid label %d to tree_new\n", l);
         }
     
     for (i = 0; i < n; i++)
          KID(t,i) = (TREE) 0;
     t -> reference_count = 0;
     t -> label = l;
     return t;
     }

static TREE tree_new_fast( l)
     LABEL  l;
     {
     ARITY n = label_arities[l];

     TREE t = (TREE) MALLOC ( (sizeof * t) );
     KIDS(t) = (TREE *) MALLOC(( n * (sizeof t) ));
     t -> reference_count = 0;
     t -> label = l;
     return t;
     }

TREE tree_copy(t)
     TREE t;
     {
     t -> reference_count++;
     return t;
     }

TREE tree_dup(t)
     TREE t;
     {
     LABEL l = t -> label;
     TREE  u = tree_new_fast(l);
     ARITY i;
     ARITY n = label_arities[l];
     
     for (i = 0; i < n; i++) KID(u,i) = tree_copy(KID(t,i));

     return u;
     }

UINT  tree_hash(t)
     TREE t;
     {
     UINT h = (UINT) (t -> label);
     ARITY n = label_arities[(LABEL)h];
     h++;
     if (n > (ARITY) 0) {
     	ARITY i;
     	for (i = 0; i < n; i++) {
            h = h + tree_hash(KID(t,i));
	    h = (h << 5) + (h >> 4);
	    }
	}
     return h;

/*   UINT h = (UINT) (t -> label);
     ARITY n = label_arities[(LABEL)h];
     if (n > 0) {
     	ARITY i;
     	for (i = 0; i < n; i++)
            h = (++h) * some_numbers[i] + tree_hash(KID(t,i));
	}
     return h & 0x7fffffff;
*/   }

UINT  tree_equal(s, t)
     TREE s;
     TREE t;
     {
     LABEL ls = s -> label;
     LABEL lt = t -> label;
     register ARITY nt = label_arities[lt];
     register ARITY i;
     register struct tree_struct ** ks;
     register struct tree_struct ** kt;

     if (s == t) return 1;
     if (ls != lt) return 0;
     ks = KIDS(s);
     kt = KIDS(t);
     for (i = 0; i < nt; i++)
         if (0 == tree_equal(ks[i], kt[i])) return 0;
     return 1;
     }

VOID tree_set_arity(l, i)
	LABEL l;
	ARITY i;
	{
	if (l < max_label && i < tree_MAXARITY) {
	     label_arities[l] = i;
	     return;
	     }
	if (l >= max_label) {
	     fprintf(stderr,"tree_set_arity: label out of range\n");
	     }
	if (i >= tree_MAXARITY) {
	     fprintf(stderr,"tree_set_arity: arity out of range\n");
	     }
	abort();
	}
     
VOID  tree_free(t)
     TREE t;
     {
     if (t == 0) return;
     if (t -> reference_count-- != 0) return;
     {
     ARITY n = label_arities[t -> label];
     ARITY i;
     TREE * k = KIDS(t);
     for (i = 0; i < n; i++) tree_free(k[i]);
     FREE (t);
     FREE (k);
     }
     }

VOID tree_init(n)
    unsigned char n;
    {
    unsigned char i;

    label_arities = (ARITY *) MALLOC (n * sizeof(ARITY));
    for (i = 0; i < n; i++) label_arities[i] = 0;
    max_label = n;
    }

static int write_counter = 0;

static TREE tree_read_private(f)
    FILE * f;
    {
    LABEL l = r_i(f);
    TREE t = tree_new_fast(l);
    ARITY n = label_arities[l];
    ARITY i;

    for (i = 0; i < n ; i++) KID(t,i) = tree_read_private(f);
    return t;
    }

static VOID tree_write_private(f, t)
    FILE * f;
    TREE t;
    {
    LABEL l = t -> label;
    ARITY n = label_arities[l];
    ARITY i;

    w_i(f,(int)l);
    for (i = 0; i < n; i++) tree_write_private(f,KID(t,i)); 
    if (write_counter++ > 20) {
       write_counter = 0;
       n_l(f);
       }
    }

VOID tree_read_labels(f)
    FILE * f;
    {
    unsigned char i;
    read_header(f,"LABELS");
    max_label = r_i(f);
    tree_init(max_label);
    for (i = 0; i < max_label; i ++) label_arities[i] = r_i(f);
    read_header(f,"LABELS");
    }

VOID tree_write_labels(f)
    FILE * f;
    {
    unsigned char i;
    write_header(f,"LABELS");
    w_i(f,(int)max_label);
    for (i = 0; i < max_label; i ++) w_i(f, (int) label_arities[i]);
    write_header(f,"LABELS");
    n_l(f);
    }

TREE tree_read(f)
    FILE * f;
    {
    TREE t;
    read_header(f,"TREE");
    t = tree_read_private(f);
    read_header(f,"TREE");
    return t;
    }

VOID tree_print(fd,t)
    FILE * fd;
    TREE t;
    {
    LABEL l = t -> label;
    ARITY n = label_arities[l];
    ARITY i;
    if (n == 0) {
       fprintf(fd,"%d", l);
       return;
       }
    fprintf(fd,"(%d ", l);
    for (i = 0; i < n-1; i++) {
       tree_print(fd,KID(t,i));
       fprintf(fd," ");
       }
    tree_print(fd,KID(t,n-1));
    fprintf(fd,")");
    return;
    }

VOID tree_write(f,t)
    FILE * f;
    TREE t;
    {
    write_header(f, "TREE");
    write_counter = 0;
    tree_write_private(f,t);
    write_header(f, "TREE");
    if (write_counter != 0) n_l(f);
    }