/*
 * Copyright 2002, 2003, 2004, 2005 - <A href="http://www.koalog.com">Koalog</A>
 */
package com.koalog.jcs.examples;

import java.util.Collection;
import java.util.ArrayList;
import org.apache.log4j.PropertyConfigurator;
import com.koalog.jcs.variable.IntegerVariable;
import com.koalog.jcs.constraint.BaseProblem;
import com.koalog.jcs.constraint.arithmetic.AllDifferent_SPARSE;
import com.koalog.jcs.constraint.arithmetic.GCC_SPARSE;
import com.koalog.jcs.constraint.arithmetic.Relation_SPARSE;
import com.koalog.jcs.domain.SparseDomain;

/**
 * <P>The problem consists of scheduling games between n teams over n-1 weeks 
 * (here n for the sake of uniformity). Each week is divided into n/2 periods.
 * The goal is to schedule a game for each period of every week so that:
 * <UL>
 * <LI>every team plays against every other team,
 * <LI>a team plays exactly once a week,
 * <LI>a team plays at most twice 
 * (here exactly twice for the sake of uniformity) 
 * in the same period.
 * </UL>
 *
 * @author Yan Georget
 */
public class RoundRobinProblem extends BaseProblem {
    //------------------------------------------------------------------------
    // PROPERTIES
    //------------------------------------------------------------------------
    /** The number of teams. */
    int n;
    
    //------------------------------------------------------------------------
    // CONSTRUCTORS
    //------------------------------------------------------------------------
    /**
     * Sole constructor.
     * @param n the number of teams.
     */
    public RoundRobinProblem(int n) {
        super();
        this.n = n;
        // The problem constraints. 
        Collection vars = new ArrayList((n/2) * (n-1));
        // The games per periods and weeks.
        IntegerVariable[][] g = new IntegerVariable[n/2][n-1];
        for (int p=0; p<n/2; p++) {
            for (int w=0; w<n-1; w++) {
                g[p][w] = new IntegerVariable("g_" + p + "_" + w, 
                                              new SparseDomain(0,n*n-1));
                vars.add(g[p][w]);
            }
        }
        // The teams per periods, weeks and location (home/away). 
        IntegerVariable[][][] t = new IntegerVariable[n/2][n][2];
        for (int w=0; w<n; w++) {
            Collection teamsPerWeek = new ArrayList(n*n);
            for (int p=0; p<n/2; p++) {
                for (int a = 0; a<2; a++) {
                    t[p][w][a] =
                        new IntegerVariable(new SparseDomain(0,n-1));
                    teamsPerWeek.add(t[p][w][a]);
                }
            }
            // This enforces that a team plays once a week.
            add(new AllDifferent_SPARSE((IntegerVariable[]) teamsPerWeek
                                        .toArray(new IntegerVariable[]{})));
            
        }
        for (int p=0; p<n/2; p++) {
            Collection teamsPerPeriod = new ArrayList(n*n);
            for (int w = 0; w<n; w++) {
                for (int a = 0; a<2; a++) {
                    teamsPerPeriod.add(t[p][w][a]);
                }
            }
            int[] val = new int[n];
            int[] occ = new int[n];
            for (int i=0; i<n; i++) {
                val[i] = i;
                occ[i] = 2;
            }
            // This enforces that a team plays twice per period.
            add(new GCC_SPARSE((IntegerVariable[]) teamsPerPeriod
                               .toArray(new IntegerVariable[]{}), 
                               val, 
                               occ)); 
        }
        // To enforce that each team meets each other team, 
        // we will consider the games/plays (pair of teams) and enforces 
        // that these are different.
        // The plays : each play is represented as a pair (h,a) where h<a.
        // where h is the team playing home and a the team playing away.
        // The pair is encoded as a number.
        int[][] plays = new int[n*(n-1)/2][3];
        int k=0;
        for (int i=0; i<n-1; i++) {
            for (int j=i+1; j<n; j++) {
                plays[k] = new int[] {i, j, i*n+j};
                k++;
            } 
        }
        // Relation team home, team away, game (plays).
        for (int w = 0; w<n-1; w++) {
            for (int p=0; p<n/2; p++) {
                add(new Relation_SPARSE(new IntegerVariable[] {
                    t[p][w][0],
                    t[p][w][1],
                    g[p][w]
                },
                                              plays));
            }
        }
        add(new AllDifferent_SPARSE((IntegerVariable[])vars
                                    .toArray(new IntegerVariable[]{})));

        setVariables((IntegerVariable[])vars
                     .toArray(new IntegerVariable[]{}));
    }

    //------------------------------------------------------------------------
    // STATIC METHODS
    //------------------------------------------------------------------------
    /**
     * Runs the problem.
     * @param args the command line arguments:
     * args[0] must contain a log4j properties file location
     */
    public static void main(String[] args) {
        PropertyConfigurator.configure(args[0]);
        new RoundRobinSolver(new RoundRobinProblem(8)).solve(1);
    }
}