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


/*
 *  RandTree as described by Hitoshi Iba
 *  Author: Alexander Chircop
 *  Date:   28th Nov 2000
 */
 
package ec.gp.build;
import ec.gp.*;
import ec.*;
import ec.util.*;
import java.util.*;

public class RandTree extends GPNodeBuilder
    {
    public static final String P_RANDOMBRANCH = "randtree";
    int[] arities;
    boolean aritySetupDone=false;

    LinkedList permutations;

    public static class ArityObject extends Object
        {
        public int arity;
        public ArityObject(int a) { arity=a; }
        }

    public Parameter defaultBase()
        {
        return GPBuildDefaults.base().push(P_RANDOMBRANCH);
        }

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

        // we use size distributions -- did the user specify any?
        if (!canPick())
            state.output.fatal("RandTree requires some kind of size distribution set, either with " + P_MINSIZE + "/" + P_MAXSIZE + ", or with " + P_NUMSIZES + ".",
                base, defaultBase());
        }

    // Added method to enhance linked list functionality with ArityObject
    boolean contains(LinkedList initArities,int a)
        {
        boolean truth=false;
        int counter=0;
        ArityObject b;

        if (initArities.size()!=0)
            while ((counter marker)
                    {
                    marker=max.arity;
                    }
                }

            // Place maximum found on the array
            arities[current]=marker;
            remove(initArities,marker);
            current++;
            }

        aritySetupDone=true;
        }

    long fact(long num)
        {
        if (num==0) { return 1; }
        else { return num*fact(num-1); }
        }

    int[] select(LinkedList permutations,int size)
        {
        int counter1,counter2,total=0;
        long residue,denominator=1;
        int selection;
        int[] current;
        int[] quantity=new int[permutations.size()];

        for (counter1=0;counter1=(treeSize*2)-1) {state.output.fatal("Not able to find valid permutation for generated Dyck word: "+word);}
                }
            }
        return buildTree(state,thread,parent,argposition,set,word);
        }

    // recursive function to work out all combinations and push them onto ArrayList
    void Permute(int current,int[] sol,int size)
        {
        int counter=0,result=0;
        // base case
        if (current==arities.length-1) /* set last one to maximum allowable */
            {
            while(result<=size)
                {
                counter++;
                result=result+arities[current];
                }
            result=result-arities[current];
            counter--;
            if (result<0)
                {
                result=0;
                counter=0;
                }
            sol[current]=counter;

            //Adding this solution to the list.
            permutations.add(sol);
            }
        // end of base case
        else
            {
            while(result<=size)
                {
                if (result<=size)
                    {
                    sol[current]=counter;
                    Permute(current+1,sol,size-result);
                    }
                result=result+arities[current];
                counter++;
                }
            }
        }

    public String buildDyckWord(int requestedSize,int[] arities,int[] s,EvolutionState state,int thread)
        {
        int counter,choices,choice,pos,arity=0,checksum=0,size=0;
        int[] scheme=new int[s.length];

        String dyck="";
        String addStr="";

        scheme=s;
        for(counter=0;counter0)
                {
                arity=arities[counter];
                scheme[counter]--;
                }
            counter++;
            }

        while(arity!=0)
            {
            choice=state.random[thread].nextInt(choices--)+1;
            pos=-1;
            counter=0;
            // find insertion position within the string
            while(counter!=choice)
                {
                pos++;
                if (dyck.charAt(pos)=='*') { counter++; }
                }
            // building no of y's in string
            addStr="";
            while (addStr.length()0)
                    {
                    arity=arities[counter];
                    scheme[counter]--;
                    }
                counter++;
                }
            }
        //Clean up leftover *'s
        for (counter=0;counter0)
                    {
                    childcount--;
                    if (s.size()==0) { state.output.fatal("Stack underflow when building tree."); }
                    GPNode child=(GPNode) s.pop();
                    child.parent=nT;
                    child.argposition=(byte)childcount;
                    nT.children[childcount]=child;
                    }
                nT.argposition=0;
                nT.parent=null;
                s.push(nT);
                if (counter!=dyckWord.length()) counter--;
                }
            }
        return (GPNode) s.pop();
        }
    }