#!/bin/gawk -f
#
# 2004 Steven Gustafson smg@cs.nott.ac.uk 
#
# Some of this code was taken from Bill Langdon's lisp2dot.awk file 
#
# Description: awk script to translate a lisp expression to array 
# representation of nodes present.  
#
# Only valid of BINARY trees. 
#
# Inputs: file containing s-expression 
# Additionally: must modify arity2 function list below.
# Outputs: input into lattice.awk
#
# Revision History
# 16/09/2004 - Corrected length of points to be 2^depth maximum instead
#              of infeasible 2^half_number_points. 

BEGIN { 
	if(arity2=="") arity2 =",and,nand,or,nor,";
}

{
	code = sprintf("%s %s",code,$0);
}

END{
	l=split(code,inst,"[ \t()]"); 
	pc=0;
	parent=-1;
	args=1;
	depth=1;	
	maxdepth=1;	
	for(i=1;i<=l;i++) {
		if(length(inst[i])>0) {
			node_name[pc]=inst[i];
			node_nxt[pc]=0;
			node_arity[pc]=arity(node_name[pc]);
			args += node_arity[pc]-1;
		
			if(args<0) print "ERROR badly formed tree.";
			node_back[pc]=parent;
			node_nxt[parent]++;
			node_child[parent,node_nxt[parent]]=pc;
			if(node_arity[pc]>0){
				  	depth++; 
					if(maxdepth<depth)maxdepth=depth;		
				  	parent=pc;
			} 
			else {
			    for(j=parent; node_nxt[j]>=node_arity[j] && j>=0; ){
					j=node_back[j];
					parent=j;
					depth--;	
		 		}
			}
			pc++;
		}
	}
	if(args!=0) print "ERROR2 badly formed tree.";

	#print pc, maxdepth 

	for(p=0;p<pc;p++)addr[p]=0 
	#for(p=1;p<(2**((pc+1)/2));p++)array[p]=0 
	for(p=1;p<(2**(maxdepth));p++)array[p]=0 

	addr[0]=1	
	array[addr[0]]=1	
	for(p=0;p<pc;p++) {
		if(node_arity[p]==2){
			for(i=0;i<node_arity[p];i++) {
				q=node_child[p,(i+1)];
	 			addr[q]=(addr[p]*2+i)  	
				array[addr[q]]=1
	 		}
	 	}
	}
	#for(p=1;p<(2**((pc+1)/2));p++)print array[p]  
	for(p=1;p<(2**(maxdepth));p++)print array[p]  
}

function arity(name) {
	t_ = sprintf(",%s,",name);
	if(index(arity2,t_)>0) return 2;
	return 0;
}