tree.c

Genetic Programing of music

/*  lil-gp Genetic Programming System, version 1.0, 11 July 1995
 *  Copyright (C) 1995  Michigan State University
 * 
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of version 2 of the GNU General Public License as
 *  published by the Free Software Foundation.
 * 
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 * 
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *  
 *  Douglas Zongker       ([e-mail])
 *  Dr. Bill Punch        ([e-mail])
 *
 *  Computer Science Department
 *  A-714 Wells Hall
 *  Michigan State University
 *  East Lansing, Michigan  48824
 *  USA
 *  
 */

#include <lilgp.h>

/*
 * note:  that almost all these functions that recurse through the tree
 * come in two parts:  the wrapper and the recursive part.  the "standard"
 * method of traversing a tree like this is to set up a pointer to the
 * first node in the tree, then subsequent recursive calls step the
 * pointer forward, traversing the tree in preorder.  the wrapper function
 * sets up this pointer, then passes the address of that pointer [that's
 * an (lnode **)] to the recursive part.
 *
 * the first function in this file [tree_size()] is commented in detail,
 * others (which are just variations on this theme) are rather glossed over.
 *
 * note:  when I refer to a tree's "size" I almost always mean "how many
 * lnodes the tree takes to store", NOT how many nodes are in the tree.
 * watch out for this.  (the major exception is, of course, "tree_size()"
 * which returns the node count.)
 */

/*
 * tree_nodes:  return the number of nodes in the tree.
 */

int tree_nodes ( lnode *tree )
{
     lnode *l = tree;
     return tree_nodes_recurse ( &l );
}

int tree_nodes_recurse ( lnode **l )
{
     /*
      *  *l always points at a function node here; save the function.
      */
     function *f = (**l).f;
     int i, j = 1;

     /* step the pointer over the function. */
     ++*l;

     /* if the function is a terminal, then the recursion bottoms out. */
     if ( f->arity == 0 )
     {
          /* skip the pointer over the ERC value if this node has one. */
          if ( f->ephem_gen )
               ++*l;

          /* return this subtree size. */
          return 1;
     }
     else
     {
          /* function is not a terminal, so add up its subtrees and return
           * the total.
           */

          switch ( f->type )
          {
             case FUNC_DATA:
             case EVAL_DATA:
               for ( i = 0; i < f->arity; ++i )
                    j += tree_nodes_recurse ( l );
               break;
               
             case FUNC_EXPR:
             case EVAL_EXPR:
               for ( i = 0; i < f->arity; ++i )
               {
                    /* skip the pointer over the skipsize node. */
                    ++*l;
                    /* add this subtree's size to the total. */
                    j += tree_nodes_recurse ( l );
               }
               break;
          }
     }
     
     return j;
}

/*
 * tree_nodes_internal:  return number of internal (function) nodes in the
 *     tree.
 */

int tree_nodes_internal ( lnode *data )
{
     lnode *l = data;
     return tree_nodes_internal_recurse ( &l );
}

int tree_nodes_internal_recurse ( lnode **l )
{
     function *f = (**l).f;
     int i, j = 1;

     ++*l;
     
     if ( f->arity == 0 )
     {
          if ( f->ephem_gen )
               ++*l;
          return 0;
     }
     else
     {
          switch ( f->type )
          {
             case FUNC_DATA:
             case EVAL_DATA:
               for ( i = 0; i < f->arity; ++i )
                    j += tree_nodes_internal_recurse ( l );
               break;
             case FUNC_EXPR:
             case EVAL_EXPR:
               for ( i = 0; i < f->arity; ++i )
               {
                    ++*l;
                    j += tree_nodes_internal_recurse ( l );
               }
               break;
          }
     }

     return j;
}

/*
 * tree_nodes_external:  return number of external (terminal) nodes in the
 *     tree.
 */

int tree_nodes_external ( lnode *data )
{
     lnode *l = data;
     return tree_nodes_external_recurse ( &l );
}

int tree_nodes_external_recurse ( lnode **l )
{
     function *f = (**l).f;
     int i, j = 0;

     ++*l;
     
     if ( f->arity == 0 )
     {
          if ( f->ephem_gen )
               ++*l;
          return 1;
     }
     else
     {
          switch ( f->type )
          {
             case FUNC_DATA:
             case EVAL_DATA:
               for ( i = 0; i < f->arity; ++i )
                    j += tree_nodes_external_recurse ( l ) ;
               break;
             case FUNC_EXPR:
             case EVAL_EXPR:
               for ( i = 0; i < f->arity; ++i )
               {
                    ++*l;
                    j += tree_nodes_external_recurse ( l ) ;
               }
               break;
          }
     }
     return j;
}

/*
 * print_tree_array:  print the tree, as an array, on stdout.  primarily
 *     for debugging.
 */

void print_tree_array ( lnode *data )
{
     lnode *l = data;
     int i = 0;
     print_tree_array_recurse ( &l, &i );
}

void print_tree_array_recurse ( lnode **l, int *index )
{
     function *f = (**l).f;
     int i;

     printf ( "%3d: function: \"%s\"\n", *index, f->string );
     
     ++*l;
     ++*index;

     if ( f->arity == 0 )
     {
          if ( f->ephem_gen )
          {
               printf ( "%3d:    value: %s\n", *index, (f->ephem_str)((**l).d->d) );
               ++*l;
               ++*index;
          }
     }
     else
     {
          switch ( f->type )
          {
             case FUNC_DATA:
             case EVAL_DATA:
               for ( i = 0; i < f->arity; ++i )
               {
                    print_tree_array_recurse ( l, index );
               }
               break;
             case FUNC_EXPR:
             case EVAL_EXPR:
               for ( i = 0; i < f->arity; ++i )
               {
                    printf ( "%3d:    {skip %d}\n", *index, (**l).s );
                    ++*l;
                    ++*index;
                    print_tree_array_recurse ( l, index );
               }
               break;
          }
     }
}

/*
 * print_tree:  print the tree, as a LISP S-expression, to the given FILE *.
 */

void print_tree ( lnode *data, FILE *fil )
{
     lnode *c = data;
     print_tree_recurse ( &c, fil );
     fprintf ( fil, "\n" );
}

void print_tree_recurse ( lnode **l, FILE *fil )
{
     function *f;
     int i;

     f = (**l).f;

     fprintf ( fil, " " );
     if ( f->arity != 0 )
          fprintf ( fil, "(" );
     
     ++*l;
     if ( f->ephem_gen )
     {
          fprintf ( fil, "%s", (f->ephem_str)((**l).d->d) );
#ifdef DEBUG
          fprintf ( fil, " <%d>", (**l).d->refcount );
#endif
          ++*l;
     }
     else
          fprintf ( fil, "%s", f->string );
     
     switch ( f->type )
     {
        case FUNC_DATA:
        case EVAL_DATA:
          for ( i = 0; i < f->arity; ++i )
          {
               print_tree_recurse ( l, fil );
          }
          break;
        case FUNC_EXPR:
        case EVAL_EXPR:
          for ( i = 0; i < f->arity; ++i )
          {
#ifdef DEBUG               
               fprintf ( fil, " {skip %d}", (**l).s );
#endif               
               ++*l;
               print_tree_recurse ( l, fil );
          }
          break;
     }

     if ( f->arity != 0 )
          fprintf ( fil, ")" );
}

/*
 * generate_random_full_tree:  generates, in the given generation space,
 *     a random full tree of
 *     the specified depth. 
 */

void generate_random_full_tree ( int space, int depth, function_set *fset )
{
     int i, j;
     int save;

     if ( depth == 0 )
     {
          /* we've reached depth 0, so choose a terminal node for this
           * subtree.
           */
          
          i = random_int(fset->terminal_count)+(fset->function_count);
          gensp_next(space)->f = (fset->cset)+i;

          /* if this terminal is an ERC, then generate one and store it. */
          if ( (fset->cset)[i].ephem_gen )
               gensp_next(space)->d = new_ephemeral_const ( (fset->cset)+i );

          return;
     }

     /* we're not a depth 0, so generate a non-terminal node. */
     i = random_int(fset->function_count);
     gensp_next(space)->f = (fset->cset)+i;

     /* now generate the node's children. */
          switch ( (fset->cset)[i].type )
          {
             case FUNC_DATA:
             case EVAL_DATA:
               for ( j = 0; j < (fset->cset)[i].arity; ++j )
               {
                    /* generate a full tree of depth [depth-1]. */
                    generate_random_full_tree ( space, depth-1, fset );
               }
               break;
             case FUNC_EXPR:
             case EVAL_EXPR:
               for ( j = 0; j < (fset->cset)[i].arity; ++j )
               {
                    /* yes, so save where the skip value needs to be placed
                     * since we don't know what it is yet.
                     */
                    save = gensp_next_int ( space );
                    
                    /* generate a full tree of depth [depth-1]. */
                    generate_random_full_tree ( space, depth-1, fset );
                    
                    /* save the size of the subtree in the skip node, if we need to. */
                    gensp[space].data[save].s = gensp[space].used-save-1;
                    
               }
               break;
          }
     
     return;
     
}

/*
 * generate_random_grow_tree:  grow a random tree, of (maximum) depth [depth].
 *     works just like genereate_random_full_tree, except that a node with
 *     depth > 0 can be a terminal.
 */
       
void generate_random_grow_tree ( int space, int depth, function_set *fset )
{
     int i, j;
     int save;

     if ( depth == 0 )
     {
          i = random_int(fset->terminal_count)+(fset->function_count);
          gensp_next(space)->f = (fset->cset)+i;

          if ( (fset->cset)[i].ephem_gen )
               gensp_next(space)->d = new_ephemeral_const ( (fset->cset)+i );
          
          return;
     }

     /* note that here we can generate a terminal node. */
     i = random_int(fset->function_count+fset->terminal_count);
     gensp_next(space)->f = (fset->cset)+i;
     
     if ( (fset->cset)[i].arity )
     {
          switch ( (fset->cset)[i].type )
          {
             case FUNC_DATA:
             case EVAL_DATA:
               for ( j = 0; j < (fset->cset)[i].arity; ++j )
                    generate_random_grow_tree ( space, depth-1, fset );
               break;
             case FUNC_EXPR:
             case EVAL_EXPR:
               for ( j = 0; j < (fset->cset)[i].arity; ++j )
               {
                    save = gensp_next_int(space);
                    generate_random_grow_tree ( space, depth-1, fset );
                    gensp[space].data[save].s = gensp[space].used-save-1;
               }
               break;
          }
     }
     else
     {
          if ( (fset->cset)[i].ephem_gen )
               gensp_next(space)->d = new_ephemeral_const ( (fset->cset)+i );
     }
     return;
}

/*
 * tree_depth:  return the depth of the tree.  a tree with one node has
 *     depth 0.
 */

int tree_depth ( lnode *data )
{
     lnode *l = data;
     return tree_depth_recurse ( &l );
}

int tree_depth_recurse ( lnode **l )
{

     function *f = (**l).f;
     int i, j, k = 0;

     ++*l;
     if ( f->arity == 0 )
     {
          /* a terminal node; advance the pointer and return 0. */
          
          if ( f->ephem_gen )
               ++*l;
          return 0;
     }

     /* a nonterminal; find the deepest child and return its depth plus one. */
     
          switch ( f->type )
          {
             case FUNC_DATA:
             case EVAL_DATA:
               for ( i = 0; i < f->arity; ++i )
               {
                    j = tree_depth_recurse ( l );
                    if ( j > k )
                         k = j;
               }
               break;
             case FUNC_EXPR:
             case EVAL_EXPR:
               for ( i = 0; i < f->arity; ++i )
               {
                    ++*l;
                    j = tree_depth_recurse ( l );
                    if ( j > k )
                         k = j;
               }
               break;
          }
     
     return k+1;
}

int tree_depth_to_subtree ( lnode *data, lnode *sub )
{
     lnode *l = data;
     return tree_depth_to_subtree_recurse ( &l, sub, 0 );
}

int tree_depth_to_subtree_recurse ( lnode **l, lnode *sub, int depth )
{
     function *f = (**l).f;
     int i, j;

     if ( *l == sub )
          return depth;

     ++*l;
     if ( f->arity == 0 )
     {
          if ( f->ephem_gen )