/*
  Copyright 2006 by Sean Luke
  Licensed under the Academic Free License version 3.0
  See the file "LICENSE" for more information
*/


package ec.gp.breed;
import ec.*;
import ec.util.*;
import ec.gp.*; 

/* 
 * RehangPipeline.java
 * 
 * Created: Wed Dec 15 21:41:30 1999
 * By: Sean Luke
 */

/**
 * RehangPipeline picks a nonterminal node other than the root
 * and "rehangs" it as
 * a new root. Imagine if the tree were nodes connected with string.
 * Grab the new node and pick it up, letting the other nodes hang
 * underneath it as a new "root".  That's in effect what you're doing.
 *
 * 
Important Note: Because it must be free of any constraints
 * by nature, RehangPipeline does not work with strong typing.  You must
 * not have more than one type defined in order to use RehangPipeline.  
 *
 * 
RehangPipeline picks a random tree, then picks randomly from
 * all the nonterminals in the tree other than the root, and rehangs the
 * chosen nonterminal 
 * as the new root. If its chosen tree has no nonterminals, it repeats
 * the choose-tree process.  If after tries times
 * it has failed to find a tree with nonterminals (other than the root),
 * it gives up and simply
 * copies the individual.  As you might guess, determining if a tree has
 * nonterminals is very fast, so tries can be pretty large with
 * little to no detriment to evolution speed.
 *
 * 
"Rehanging" is complicated to describe.  First, you pick a random
 * child of your chosen nonterminal n, 
 * and remove this subtree from the tree.
 * Call this subtree T.  Next, you set the nonterminal as a new root; its
 * former parent p now fills the slot left behind by the missing subtree.
 * The p's former parent q now fills the slot left behind by 
 * n.  q's former parent r now fills the slot left behind
 * by p, and so on.  This proceeds all the way up to the old root, which
 * will be left with one empty slot (where its former child was that is now its new
 * parent).  This slot is then filled with T

 
Typical Number of Individuals Produced Per produce(...) call

 ...as many as the source produces

 
Number of Sources

 1

 
Parameters

 

 
base.tries

 int >= 1
 
(number of times to try finding valid pairs of nodes)

 
base.tree.0

 0 < int < (num trees in individuals), if exists
 
(tree chosen for mutation; if parameter doesn't exist, tree is picked at random)

 

 
Default Base

 gp.breed.rehang


 * @author Sean Luke
 * @version 1.0 
 */

public class RehangPipeline extends GPBreedingPipeline
    {
    public static final String P_REHANG = "rehang";
    public static final String P_NUM_TRIES = "tries";
    public static final int NUM_SOURCES = 1;
   
    /** The number of times the pipeline tries to find a tree with a
        nonterminal before giving up and just copying the individual. */
    int numTries;

    /** Is our tree fixed?  If not, this is -1 */
    int tree;

    public Parameter defaultBase() { return GPBreedDefaults.base().push(P_REHANG); }

    public int numSources() { return NUM_SOURCES; }

    public void setup(final EvolutionState state, final Parameter base)
        {
        super.setup(state,base);
        
        Parameter def = defaultBase();

        numTries = state.parameters.getInt(base.push(P_NUM_TRIES),
            def.push(P_NUM_TRIES),1);
        if (numTries == 0)
            state.output.fatal("RehangPipeline has an invalid number of tries (it must be >= 1).",base.push(P_NUM_TRIES),def.push(P_NUM_TRIES));

        if (((GPInitializer)state.initializer).numAtomicTypes + ((GPInitializer)state.initializer).numSetTypes > 1)
            state.output.fatal("RehangPipeline only works when there is only one type (the system is typeless", base,def);

        tree = TREE_UNFIXED;
        if (state.parameters.exists(base.push(P_TREE).push(""+0),
                def.push(P_TREE).push(""+0)))
            {
            tree = state.parameters.getInt(base.push(P_TREE).push(""+0),
                def.push(P_TREE).push(""+0),0);
            if (tree==-1)
                state.output.fatal("Tree fixed value, if defined, must be >= 0");
            }
        }



    private int numRehangableNodes(final GPNode root, int soFar)
        {
        // we don't include the tree root
        for(int x=0;x0) soFar++;  // rehangable
        for(int x=0;x0)  // rehangable
            {
            num--;
            if (num==-1)  // found it
                {
                rehangableNode = root;
                return num;
                }
            }
        for(int x=0;x= i.trees.length))
                // uh oh
                state.output.fatal("RehangPipeline attempted to fix tree.0 to a value which was out of bounds of the array of the individual's trees.  Check the pipeline's fixed tree values -- they may be negative or greater than the number of trees in an individual"); 

            GPIndividual j;
            if (sources[0] instanceof BreedingPipeline)
                // it's already a copy, so just smash the tree in
                {
                j=i;
                }
            else // need to copy it
                {
                j = (GPIndividual)(i.lightClone());
                
                // Fill in various tree information that didn't get filled in there
                j.trees = new GPTree[i.trees.length];
                
                for(int x=0;x1) t = state.random[thread].nextInt(i.trees.length);
                    else t = 0;
                else t = tree;
                
                // is the tree rehangable?              
                if (j.trees[t].child.children.length==0) continue; // uh oh, try again
                boolean rehangable = false;
                for(int y=0;y0) // nonterminal
                        { rehangable = true; break; }
                if (!rehangable) continue;  // the root's children are all terminals

                int numrehang = numRehangableNodes(j.trees[t].child,0);
                pickRehangableNode(j.trees[t].child,
                    state.random[thread].nextInt(numrehang));
                
                rehang(state,thread,rehangableNode,j.trees[t].child);

                j.evaluated = false;
                }

            // add the new individual, replacing its previous source
            inds[q] = j;
            }
        return n;
        }
    }