tree.c

Genetic Programing of music

               ++*l;
          return -1;
     }

          switch ( f->type )
          {
             case FUNC_DATA:
             case EVAL_DATA:
               for ( i = 0; i < f->arity; ++i )
               {
                    j = tree_depth_to_subtree_recurse ( l, sub, depth+1 );
                    if ( j != -1 )
                         return j;
               }
               break;
             case FUNC_EXPR:
             case EVAL_EXPR:
               for ( i = 0; i < f->arity; ++i )
               {
                    ++*l;
                    j = tree_depth_to_subtree_recurse ( l, sub, depth+1 );
                    if ( j != -1 )
                         return j;
               }
               break;
          }

     return -1;
}
     

/*
 * get_subtree:  returns the start'th subtree of the tree, where start
 *     ranges from 0..(nodecount-1).  the zeroth subtree is the tree itself.
 *     the subtrees are returned in preorder.
 */

lnode *get_subtree ( lnode *data, int start )
{
     lnode *l = data;
     /* initialize a counter with start.  the counter is passed by address,
      * and so is shared across all recursive calls.  it is decremented once
      * for every node in the tree -- the current node when it reaches zero
      * is returned.
      */
     int c = start;
     
     return get_subtree_recurse ( &l, &c );
}

lnode *get_subtree_recurse ( lnode **l, int *c )
{
     function *f = (**l).f;
     lnode *r;
     int i;

     /* if the counter is zero, return the current subtree. */
     if ( *c == 0 )
          return *l;

     ++*l;
     --*c;

     if ( f->arity == 0 )
     {
          /* skip over the terminal nodes. */
          if ( f->ephem_gen )
               ++*l;
     }
     else
     {
          /* recurse into this node's children.  if one of them returns
           * non-NULL, it means that the subtree has been found and the
           * return value is immediately propagated up the call chain.
           * if all of them return NULL, then the desired subtree is
           * not in this subtree and we return NULL. */
          
          switch ( f->type )
          {
             case FUNC_DATA:
             case EVAL_DATA:
               for ( i = 0; i < f->arity; ++i )
               {
                    r = get_subtree_recurse ( l, c );
                    if ( r != NULL )
                         return r;
               }
               break;
             case FUNC_EXPR:
             case EVAL_EXPR:
               for ( i = 0; i < f->arity; ++i )
               {
                    ++*l;
                    r = get_subtree_recurse ( l, c );
                    if ( r != NULL )
                         return r;
               }
               break;
          }
     }

     return NULL;
}

/*
 * get_subtree_internal:  just like get_subtree, but only selects nonterminal
 *     points.  start should range from 0..(internalnodecount-1).
 */

lnode *get_subtree_internal ( lnode *data, int start )
{
     lnode *l = data;
     int c = start;
     return get_subtree_internal_recurse ( &l, &c );
}

lnode *get_subtree_internal_recurse ( lnode **l, int *c )
{
     function *f = (**l).f;
     int i;
     lnode *r;

     /* if the current subtree is a terminal node, skip it immediately. */
     if ( f->arity == 0 )
     {
          if ( f->ephem_gen )
               ++*l;
          ++*l;
     }
     else
     {
          if ( *c == 0 )
               return *l;

          ++*l;
          --*c;

          switch ( f->type )
          {
             case FUNC_DATA:
             case EVAL_DATA:
               for ( i = 0; i < f->arity; ++i )
               {
                    r = get_subtree_internal_recurse ( l, c );
                    if ( r != NULL )
                         return r;
               }
               break;
             case FUNC_EXPR:
             case EVAL_EXPR:
               for ( i = 0; i < f->arity; ++i )
               {
                    ++*l;
                    r = get_subtree_internal_recurse ( l, c );
                    if ( r != NULL )
                         return r;
               }
               break;
          }
     }

     return NULL;
}

/*
 * get_subtree_external:  just like get_subtree, but only selects terminal
 *     nodes (that is, 1-node subtrees).  start ranges from
 *     0..(externalnodecount-1).
 */

lnode *get_subtree_external ( lnode *data, int start )
{
     lnode *l = data;
     int c = start;
     return get_subtree_external_recurse ( &l, &c );
}

lnode *get_subtree_external_recurse ( lnode **l, int *c )
{
     function *f = (**l).f;
     int i;
     lnode *r;

     if ( f->arity == 0 )
     {
          if ( *c == 0 )
               return *l;

          ++*l;
          --*c;

          if ( f->ephem_gen )
               ++*l;
     }
     else
     {
          ++*l;

          switch ( f->type )
          {
             case FUNC_DATA:
             case EVAL_DATA:
               for ( i = 0; i < f->arity; ++i )
               {
                    r = get_subtree_external_recurse ( l, c );
                    if ( r != NULL )
                         return r;
               }
               break;
             case FUNC_EXPR:
             case EVAL_EXPR:
               for ( i = 0; i < f->arity; ++i )
               {
                    ++*l;
                    r = get_subtree_external_recurse ( l, c );
                    if ( r != NULL )
                         return r;
               }
               break;
          }
     }

     return NULL;
}

/*
 * copy_tree:  allocates space for and makes a copy of a tree.
 */

void copy_tree ( tree *to, tree *from )
{
     to->data = (lnode *)MALLOC ( from->size * sizeof ( lnode ) );
     to->size = from->size;
     to->nodes = from->nodes;
     memcpy ( to->data, from->data, from->size * sizeof ( lnode ) );
}

/*
 * free_tree:  frees the memory allocated by a tree, and resets variables.
 */

void free_tree ( tree *t )
{
     FREE ( t->data );
     t->data = NULL;
     t->size = -1;
     t->nodes = -1;
}

/*
 * tree_size:  returns the number of lnodes used to store the tree.
 *     this is equal to
 *        (node count)+(ERC count)+(conditionally evaluated subtree count).
 */

int tree_size ( lnode *data )
{
     lnode *l = data;
     return tree_size_recurse ( &l );
}

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

     ++*l;

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

     return j;

}

/*
 * copy_tree_replace_many:  copies a tree, replacing some of its subtrees
 *     with other subtrees.  arguments:
 *
 *         space      - the generation space to put the new tree in
 *         parent     - the tree to copy from
 *         replace    - a list of subtrees to replace
 *         with       - a list of subtrees to replace them with
 *         count      - the size of the replace and width arrays
 *         repcount   - returns the number of subtrees replaced
 *
 *     this function starts to recursively copy the "parent" tree to "dest".
 *     when the recursive copy hits any subtree in the "replace" array,
 *     the corresponding subtree in the "with" array is copied in its
 *     place.  repcount returns the number of subtrees that were hit and
 *     replaced.  this can be less than count, as some subtrees may never
 *     be found (if, for instance, one of the subtrees in the "replace"
 *     array is the subtree of another).
 */

void copy_tree_replace_many ( int space, lnode *parent, lnode **replace,
                            lnode **with, int count, int *repcount )
{
     lnode *lp = parent;

     gensp_reset ( space );
     *repcount = 0;
     copy_tree_replace_many_recurse ( space, &lp, replace,
                                     with, count, repcount );
}

void copy_tree_replace_many_recurse ( int space, lnode **lp, lnode **lr,
                                    lnode **lw, int count, int *repcount )
{
     function *f = (**lp).f;
     int i;
     int save;
     lnode *new;

     /* only do the comparison if the lr is non-NULL. */
     if ( lr )
     {
          /* check the current subtree against everything in the lr array. */
          for ( i = 0; i < count; ++i )
               if ( *lp == lr[i] )
               {
                    /* we have a match! */

                    /* increment the replacement count. */
                    ++*repcount;
                    
                    /* copy the new tree into the destination.  note that the
                     * lr and lw arguments are passed as NULL to prevent
                     * further replacement within the replacement tree.
                     */
                    new = lw[i];
                    copy_tree_replace_many_recurse ( space, &new, NULL,
                                                    NULL, count, repcount );
                    
                    /* now skip the lp pointer over the lr subtree. */
                    skip_over_subtree ( lp );

                    return;
               }
     }

     /* copy the node from the parent to the destination. */

     gensp_next(space)->f = (**lp).f;
     ++*lp;

     if ( f->arity == 0 )
     {
          if ( f->ephem_gen )
          {
               /* copy the ERC pointer. */

               gensp_next(space)->d = (**lp).d;
               ++*lp;
          }
     }
     else
     {
          switch ( f->type )
          {
             case FUNC_DATA:
             case EVAL_DATA:
               for ( i = 0; i < f->arity; ++i )
               {
                    copy_tree_replace_many_recurse ( space, lp, lr, lw,
                                                    count, repcount );
               }
               break;
             case FUNC_EXPR:
             case EVAL_EXPR:
               for ( i = 0; i < f->arity; ++i )
               {
                    /* note that we just can't copy the skip value, since
                     * replacement within the subtree may change it.  we
                     * have to save where it is needed and fill it in 
                     * afterwards, just like generate_random_full_tree(). */
                    
                    save = gensp_next_int ( space );
                    ++*lp;
                    copy_tree_replace_many_recurse ( space, lp, lr, lw,
                                                    count, repcount );
                    gensp[space].data[save].s = gensp[space].used-save-1;
               }
               break;
          }
     }
     return;
}

/*
 * skip_over_subtree:  takes a traversal pointer and skips it over the
 *     subtree it points to.
 */

void skip_over_subtree ( lnode **l )
{
     function *f = (**l).f;
     int i;

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

/*
 * reference_ephem_constants:  traverses a tree, adding "count" to the
 *     refcount of each ERC that is used within the tree.
 */

void reference_ephem_constants ( lnode *data, int count )
{
     lnode *l = data;
     reference_ephem_constants_recurse ( &l, count );
}

void reference_ephem_constants_recurse ( lnode **l, int count )
{
     function *f = (**l).f;
     int i;

     ++*l;

     if ( f->arity == 0 )
     {
          if ( f->ephem_gen )
          {
               if ( (**l).d )
               {
                    (**l).d->refcount += count;
                    ++*l;
               }
               else
                    error ( E_FATAL_ERROR, "aarg: this can't happen." );
          }
     }
     else
     {
          switch ( f->type )
          {
             case FUNC_DATA:
             case EVAL_DATA:
               for ( i = 0; i < f->arity; ++i )
                    reference_ephem_constants_recurse ( l, count );
               break;
             case FUNC_EXPR:
             case EVAL_EXPR:
               for ( i = 0; i < f->arity; ++i )
               {
                    ++*l;
                    reference_ephem_constants_recurse ( l, count );
               }
               break;
          }
     }

}