#include<stdio.h>
#include<strings.h>

/* Math 322 sample solution homework 3.
   University of Miami, Fall 94 (951).
   (c) Burton Rosenberg, 1994.
*/

/* Assume ascii codes, '@'==('A'-1) */

#define MORSE_CODE "(((((H)S(V))I((F)U))E(((L)R)A((P)W(J))))@((((B)D(X))N((C)K(Y)))T(((Z)G(Q))M(O))))" ;
#define DOT '.'
#define DASH '_'
#define MAXCODELENGTH 4

struct tree {
     struct tree * left, * right, * parent ;
     int data ; } ;

void init_access_table( struct tree * t, struct tree * a_tbl[] )
{
    if (t!=NULL) {
          init_access_table( t->left, a_tbl ) ;
          a_tbl[t->data-'@'] = t ;
          init_access_table( t->right, a_tbl ) ;
    }
}

char * build_tree_global ;

struct tree * build_tree( void ) 
{
    struct tree * t ;

    /* tree is empty or (XyZ) where y is a single char, 
       and Z, Z are trees. */

    /* precondition, b_t_g = alpha beta , alpha a tree, beta a string.
       postcondition, b_t_g = beta, alpha has been built into a tree,
         the returned pointer points to this tree.
    */

    /* string is a GLOBAL, and it cannot be the empty tree! */

    t = (struct tree *) malloc(sizeof(struct tree)) ;
    build_tree_global++ ; /* skip '(' */
    if (*build_tree_global=='(')
       t->left = build_tree() ;    /* X not empty */
    else t->left = NULL ;
    t->data = *(build_tree_global++) ;
    if (*build_tree_global=='(')
       t->right = build_tree() ;   /* Z not empty */
    else t->right = NULL ;
    *build_tree_global++ ;
    /* recursion invariant restored */

    return t ;
}

void add_parent_ptrs( struct tree * t, struct tree * parent ) 
{
    if ( t==NULL ) return ;
    t->parent = parent ;
    add_parent_ptrs( t->left, t ) ;
    add_parent_ptrs( t->right, t ) ;
}

void print_tree_aux( struct tree * t, char * prefix_string )
{
   /* recursion invariant: let C be the output column when this
      program is entered. This line's output up till C is
      done, and for each line, prefix_string is the output
      for columns up till C.
  */
  char * p ;
  if ( t!=NULL ) {
      printf("%c\n%s`--", t->data, prefix_string ) ;
      for ( p=prefix_string ; *p!='\0' ; p++ ) ;
      prefix_string = strcat( prefix_string, "|  ") ;
      print_tree_aux( t->left, prefix_string ) ;
      *p = '\0' ;
      printf("%s`--", prefix_string ) ;
      prefix_string = strcat( prefix_string, "   ") ;
      print_tree_aux( t->right, prefix_string ) ;
   }
   else printf("\n") ;
}

void print_tree( struct tree * r )
{  
   char buffer[200] ;
   buffer[0] = '\0' ;
   print_tree_aux( r, buffer ) ; 
}

int * encode_char( int c, struct tree * tbl[] )
/* Code is placed into the static array 
   in locations code[code[0]]..code[MAXCODELENGTH]
*/
{
   struct tree * p ;
   static int code[MAXCODELENGTH+1] ;
   int i ;

   if (( c<'A') || ( c>'Z')) {
       printf("encode_char: illegal input\n") ;
       return ;
   }
   for ( p=tbl[c-'@'], i=MAXCODELENGTH; p->parent!=NULL; p = p->parent, i-- )
      if (p==p->parent->left) code[i] = DOT ;
      else code[i] = DASH ;

   code[0] = i+1 ;
   return code ;
}

void test_access_table( struct tree * tbl[] )
{
   int i ;
   int * code ;

   for (i=0;i<26;i++) {
      printf("%c ", i+'A' ) ;
      code = encode_char( i+'A', tbl ) ;
      for ( ; code[0]<=MAXCODELENGTH ; code[0]++ )
         printf("%c", code[code[0]] ) ;
      printf("\n" ) ;
   }
}

int main ( int argc, char * argv[] )
{
    struct tree * morse_tree ;
    struct tree * access_table[27] ;

    build_tree_global = MORSE_CODE ;
    morse_tree = build_tree() ;
    add_parent_ptrs( morse_tree, NULL ) ;
    print_tree( morse_tree ) ;
    init_access_table( morse_tree, access_table ) ;
    test_access_table( access_table ) ;

}