/* * TesterTestingBISTPIMComb.java * * Created on 12 June 2003, 16:21 */package es.pj.circuits.control;import es.SampleData;import es.Genotype;import es.evolve.Evolver;import es.deploy.Deployment;import es.experiment.ConfigurableExperiment;import es.pj.circuits.fpgaft.SimulatorFaultyCircuit;import es.pj.circuits.fpgaft.FTLib;import java.util.Iterator;import java.util.Set;import java.util.HashSet;import java.util.Hashtable;import java.util.Collection;//import java.util.Vector;import java.awt.Point;/** Interaction Model for evolving circuits whose E line(s) go high before a number of faults * affect the output, no matter in what order or what inputs are fed into the circuit. * * @author  mmg20 */public class TestingTesterBISTPIMComb extends TestingTesterBISTPIM {        protected SimulatorFaultyCircuit circuit;        protected Hashtable noFaultQs;        protected double validChunkProp = 0.2; // Proportion at end of output data used to measure its value.            /** Creates a new instance of TesterTestingBISTPIMComb */    public TestingTesterBISTPIMComb(Evolver evo, Deployment deployment, ConfigurableExperiment experiment, SimulatorFaultyCircuit faultyCircuit, double[] thresholds, int sizeOfEHigh, int numOfELines, int roundForAverage, int howManySimultFaults ) {        super( evo, deployment, experiment, thresholds, sizeOfEHigh, numOfELines, roundForAverage, howManySimultFaults );        circuit = faultyCircuit;        defFitFunK = 990; // So that with 10 undetected faults, will have .99 fitness.  General formula is        // k=f*n/(1-f) where n is undetected faults and f is fitness for this n    }            protected double evalTask( Genotype ind, SampleData[] ins )    {        double rv;        circuit.randomReset();        SampleData[] outs = deploy.run( ins );        SampleData[] outsNoE = es.ESLib.getLines( outs, 0, outs.length - nrEs );        rv = exp.getFitness( ins, outsNoE );        // Check that E not high during no faults.  If it is high, somehow signal next round        // to not be evaluated.        boolean eHighNoF = BISTLib.getE( outs, eSize, nrEs, iss );        if( eHighNoF )        {            thisRoundIndsI[ 0 ].remove();        }else        {            int inVLen = ins[ 0 ].length();            int[] compactOuts = new int[ inVLen ];            for( int idl = 0; idl < inVLen; idl++ )            {                compactOuts[ idl ] = BISTLib.getOutAt( outs, idl, nrEs, iss, validChunkProp );            }            Hashtable ixByIns = ( Hashtable ) noFaultQs.get( ind );            if( ixByIns == null )            {                ixByIns = new Hashtable();                noFaultQs.put( ind, ixByIns );            }            ixByIns.put( exp.get( null ), compactOuts );        }        return rv;    }        protected int evalAllFaultCombs( int maxDepth, Genotype ind, SampleData[] ins )    {        int[] noFQ = ( int[] ) ( ( Hashtable ) noFaultQs.get( ind ) ).get( exp.get( null ) );        if( noFQ == null )        {            return Integer.MAX_VALUE;        }                // 1. Initialize        Collection F = BISTLib.buildAllFaultsColl( circuit );                Set A = new HashSet();        Set C = new HashSet();      C.add( new HashSet() );        Set D = null;        Hashtable CE = new Hashtable();        Hashtable DE = null;        int uf = 0;        int inpCombs = 1 << ins.length;        int currDepth = 0;        int nrEls = F.size() / 2; // !! hardcoded two fault types                // 2.        while( currDepth++ < maxDepth )        {            // Debug            /*            System.out.println("Depth: " + currDepth );            System.out.println("uf = " + uf);            System.out.println("A,C,D,CE,DE:" + A );            System.out.println(C);            System.out.println(D);            System.out.println(CE);            System.out.println(DE);            */            D = C;            DE = CE;            C = new HashSet();            CE = new Hashtable();            Iterator dit = D.iterator();            while( dit.hasNext() )            {                Set di = ( Set ) dit.next();                Iterator fit = F.iterator();                while( fit.hasNext() )                {                    Point fault = ( Point ) fit.next();                    if( !posClash( fault, di ) )                    {                        Set cij = new HashSet( di );                        cij.add( fault );                        Iterator ait = A.iterator();                        boolean aclash = false;                        while( ait.hasNext() && !aclash )                        {                            Set ar = ( Set ) ait.next();                            if( cij.containsAll( ar ) )                            {                                aclash = true;                            }                        }                        if( !aclash )                        {                            C.add( cij );                        }// !! else could add score, but could be incomplete                    }                }            }            if( C.isEmpty() )            {                break;            }                        // Debug            //System.out.println("Step 2 Over, now C,D = " + C + ", " + D);                        // 3.            // 3.1 Evaluate            Iterator cit = C.iterator();            while( cit.hasNext() )            {                Set ci = ( Set ) cit.next();                setFaults( ci );                SampleData[] outs = deploy.run( ins );                removeFaults( ci );                boolean[] es = getEs( outs );                Iterator djt = D.iterator();                boolean commonZero = false;                while( djt.hasNext() && !commonZero )                {                    Set dj = ( Set ) djt.next();                    if( dj.isEmpty() )                    {                        commonZero = true;                    }else if( ci.containsAll( dj ) )                    {                        boolean[] djes = ( boolean[] ) DE.get( dj );                        if( commonZero( es, djes ) )                        {                            commonZero = true;                        }                    }                }                if( commonZero )                {                    int undetectedFails = 0;                    for( int il = 0; il < inpCombs; il++ )                    {                        if( ( getQ( outs, il ) != noFQ[ il ] ) && !es[ il ] )                        {                            undetectedFails++;                        }                    }                    if( undetectedFails > 0 )                    {                        uf += undetectedFails;                        uf += sumCrx( nrEls, ci.size(), maxDepth );                        A.add( ci );                        cit.remove();                    }else                    {                        CE.put( ci, es );                    }                }else                {                    cit.remove();                }            } // Next ci        } // Back to step 2        return uf;    }        /** Returns true if there is in fs a Point whose x coord (fault pos) is equal to that of f     */    public static boolean posClash( Point f, Collection fs )    {        Iterator fit = fs.iterator();        while( fit.hasNext() )        {            Point fi = ( Point )fit.next();            if( f.x == fi.x )            {                return true;            }        }        return false;    }        /** Sets a number of faults inside the set fs     */    protected void setFaults( Set fs )    {        Iterator fit = fs.iterator();        while( fit.hasNext() )        {            Point fi = ( Point )fit.next();            circuit.setFault( fi );        }    }        /** Removes a number of faults inside the set fs     */    protected void removeFaults( Set fs )    {        Iterator fit = fs.iterator();        while( fit.hasNext() )        {            Point fi = ( Point )fit.next();            circuit.removeFault( fi );        }    }        /** Extracts the values of E during each input loop and puts it in an array.  If nrEs > 1     * then an oring of all of them is made.     */    public boolean[] getEs( SampleData[] outs )    {        int itplen = outs[ 0 ].length() / iss;        boolean[] rv = new boolean[ itplen ];        for( int il = 0; il < itplen; il++ )        {            rv[ il ] = BISTLib.getE( outs, il, eSize, nrEs, iss );        }        return rv;    }        /** Returns true if there exists an index n st. a[n]==false==b[n].     * Length of b must be >= length of a.     */    public static boolean commonZero( boolean[] a, boolean[] b )    {        for( int al = 0; al < a.length; al++ )        {            if( !a[ al ] && !b[ al ] )            {                return true;            }        }        return false;    }        /** GetQ is a forwarder for BISTLib.getOutAt to make code cleaner     */    protected int getQ( SampleData[] outs, int ix )    {        return BISTLib.getOutAt( outs, ix, nrEs, iss, validChunkProp );    }        /** SumCrx is a special summation to calculate how many nodes are cut off from the      * tree when a node is added to A.  This is equal to: SUM(r=1,maxDepth-1){ C(nrEls-ciSize,r) * 2^r }     * If maxDepth > nrEls then it was probably set to infinity so it should be = nrEls     */    public static int sumCrx( int nrEls, int ciSize, int maxDepth )    {        int rv = 0;        maxDepth = Math.min( nrEls, maxDepth );        for( int r = 1; r < maxDepth - 1; r++ )        {            rv += es.ESLib.binomialCoefficient( nrEls - ciSize, r ) * ( 1 << r );        }        return rv;    }        protected void resetForNewGeneration()    {        super.resetForNewGeneration();        noFaultQs = new Hashtable();    }        }