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

import org.apache.log4j.Category;
import com.koalog.jcs.ConstraintInconsistencyException;
import com.koalog.jcs.VariableInconsistencyException;
import com.koalog.jcs.variable.IntegerVariable;
import com.koalog.jcs.solver.DefaultSplitSolver;

/**
 * A solver for the Golomb problem.
 *
 * @author Yan Georget
 */
public class GolombSolver extends DefaultSplitSolver {
    //------------------------------------------------------------------------
    // STATIC PROPERTIES
    //------------------------------------------------------------------------
    private static Category cat = Category.getInstance(GolombSolver.class);

    //------------------------------------------------------------------------
    // PROPERTIES
    //------------------------------------------------------------------------
    /** The size of the problem. */
    private int n;
    /** The distances between marks. */
    private IntegerVariable[][] dist;
    /** 
        A reusable array for storing the minimal sum of different integers:
        sum[i] will be the minimal sum of i different integers chosen among a 
        set of possible integers.
    */
    private int[] sum;
    /** 
        A boolean array for marking already existing distances as used numbers.
    */
    private boolean[] used;

    //------------------------------------------------------------------------
    // CONSTRUCTORS
    //------------------------------------------------------------------------
    /**
     * Sole constructor.
     * @param problem a golomb problem
     */
    public GolombSolver(GolombProblem problem) {
        super(problem);
        dist = problem.dist;
        n = problem.n;
        sum = new int[n-1];
        sum[0] = 0;
        used = new boolean[GolombProblem.sum(n-2)+1];
    }
    
    //------------------------------------------------------------------------
    // METHODS
    //------------------------------------------------------------------------
    /** @see com.koalog.jcs.solver.BacktrackSolver */
    public void filter() throws ConstraintInconsistencyException {
        prune();
        consistencyFilter();
    }

    /**
     * A method for pruning the search space.
     *
     * @throws VariableInconsistencyException when there is no solution
     */
    public void prune() 
        throws VariableInconsistencyException {
        // we compute the index of the first non instantiated var 
        // at least 1 since dist[0][0] = 0
        int index = 0;
        while (++index < n) {
            if (dist[0][index].isNotInstantiated()) {
                break;
            } 
        }
        if (1 < index && index < n-1) { // otherwise useless
            for (int i=used.length; --i>=0;) {
                used[i] = false;
            }
            // used[0] = true;
            // the following will mark at most sum(n-3) numbers as used
            // hence there will be at least n-2 unused numbers greater than 0
            for (int i=0; i<index-1; i++) {
                final int di = dist[0][i].getMin();
                for (int j=i+1; j<index; j++) {
                    final int d = dist[0][j].getMin() - di;
                    if (d < used.length) {
                        used[d] = true;
                    }
                }
            }
            // computing the sums of non marked numbers
            int l = 0;
            final int sumMaxIdx = n - index; // (n-1)-(index-1)
            for (int j=1; j<=sumMaxIdx; j++) {
                while (used[++l]) {}
                sum[j] = sum[j-1] + l;
            }
            for (int i=index-1; i<n-1; i++) {
                for (int j=i+1; j<n; j++) { 
                    dist[i][j].adjustMin(choicePoints, 
                                         constraintScheduler,
                                         null,
                                         sum[j-i]);
                }
            }
        }
    }
}