package ifs.example.csp;

import ifs.util.*;
import ifs.model.*;
import java.util.*;

/**
 * Random Binary CSP with uniform distribution.
 * <br><br>
 * A random CSP is defined by a four-tuple (n, d, p1, p2), where n denotes the number of variables and d denotes the 
 * domain size of each variable, p1 and p2 are two probabilities. They are used to generate randomly the binary 
 * constraints among the variables. p1 represents the probability that a constraint exists between two different 
 * variables and p2 represents the probability that a pair of values in the domains of two variables connected by a 
 * constraint are incompatible.
 * <br><br>
 * We use a so called model B of Random CSP (n, d, n1, n2) where n1 = p1*n*(n-1)/2 pairs of variables are randomly 
 * and uniformly selected and binary constraints are posted between them. For each constraint, n2 = p1*d^2 randomly 
 * and uniformly selected pairs of values are picked as incompatible.
 * 
 * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomas Muller</a>
 * @version 1.0
 */
public class CSPModel extends Model {

    /**
     * Constructor
     * @param nrVariables number of variables in the problem
     * @param nrValues number of values of each variable
     * @param nrConstraints number of constraints in the problem
     * @param nrCompatiblePairs number of compatible pairs of values for every constraint
     * @param seed seed for random number generator (use {@link System#currentTimeMillis} if not bother)
     */
    public CSPModel(int nrVariables, int nrValues, int nrConstraints, int nrCompatiblePairs, long seed) {
        generate(nrVariables, nrValues, nrConstraints, nrCompatiblePairs, seed);
    }
    
    private void swap(Variable[][] allPairs, int first, int second) {
        Variable[] a = allPairs[first];
        allPairs[first]=allPairs[second];
        allPairs[second]=a;
    }

    private void buildBinaryConstraintGraph(Random rnd) {
        int numberOfAllPairs = variables().size()*(variables().size()-1)/2;
        Variable[][] allPairs = new Variable[numberOfAllPairs][];
        int idx=0;
        for (Enumeration i1=variables().elements();i1.hasMoreElements();) {
            Variable v1 = (Variable)i1.nextElement();
            for (Enumeration i2=variables().elements();i2.hasMoreElements();) {
                Variable v2 = (Variable)i2.nextElement();
                if (v1.getId()>=v2.getId()) continue;
                allPairs[idx++]=new Variable[] {v1,v2};
            }
        }
        idx = 0;
        for (Enumeration i1=constraints().elements();i1.hasMoreElements();) {
            CSPBinaryConstraint c = (CSPBinaryConstraint) i1.nextElement();
            swap(allPairs, idx, idx+(int)(rnd.nextDouble()*(numberOfAllPairs-idx)));
            c.addVariable(allPairs[idx][0]);
            c.addVariable(allPairs[idx][1]);
            c.init(rnd);
            idx++;
        }
    }
    
    private void generate(int nrVariables, int nrValues, int nrConstraints, int nrCompatiblePairs, long seed) {
        Random rnd = new Random(seed);

        for (int i=0;i<nrVariables;i++) {
            CSPVariable var = new CSPVariable(i+1,nrValues);
            addVariable(var);
        }
        
        for (int i=0;i<nrConstraints;i++) {
            CSPBinaryConstraint c = new CSPBinaryConstraint(i+1,nrCompatiblePairs);
            addConstraint(c);
        }
        
        buildBinaryConstraintGraph(rnd);
    }
}
