Problem.java

/* Copyright 2015 Laurent COCAULT
 * Licensed to Laurent COCAULT under one or more contributor license agreements.
 * See the NOTICE file distributed with this work for additional information
 * regarding copyright ownership. Laurent COCAULT licenses this file to You
 * under the Apache License, Version 2.0 (the "License"); you may not use this
 * file except in compliance with the License.  You may obtain a copy of the
 * License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.csp.constraint.solver;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import org.csp.constraint.model.BinaryConstraint;
import org.csp.constraint.model.Constraint;
import org.csp.constraint.model.NAryConstraint;
import org.csp.constraint.model.TernaryConstraint;
import org.csp.constraint.model.UnaryConstraint;
import org.csp.constraint.model.UnsizedConstraint;
import org.csp.constraint.model.Variable;

/**
 * Represents a constraint solving problem.
 */
public class Problem<T> {

    /**
     * True when the problem is being solved.
     */
    private boolean searching_;

    /**
     * Number of fails since the beginning of the search session.
     */
    private int failsCounter_;

    /**
     * Number of choice points since the beginning of the search session.
     */
    private int choicePointsCounter_;

    /**
     * During the search, variable states are saved and restored in a stack.
     * This attribute counts the number of states currently stored in this
     * stack.
     */
    private int stackDepth_;

    /**
     * Table of variables declared in the problem. A variable is considered
     * declared once it has been successfully added to problem and until it is
     * removed.
     */
    private List<Variable<T>> variables_;

    /**
     * Table of unary constraints declared in the problem. An unary constraint
     * is considered declared once it has been successfully added to problem and
     * until it is removed.
     */
    private List<UnaryConstraint<T>> unaryConstraints_;

    /**
     * Table of N-ary constraints declared in the problem. An N-ary constraint
     * is considered declared once it has been successfully added to problem and
     * until it is removed.
     */
    private List<NAryConstraint<T>> nAryConstraints_;

    /**
     * Constructor.
     */
    public Problem() {
        // Counters and flags
        searching_ = false;
        failsCounter_ = 0;
        choicePointsCounter_ = 0;
        stackDepth_ = 1;
        // Collection of variables and constraints
        variables_ = new ArrayList<Variable<T>>();
        unaryConstraints_ = new ArrayList<UnaryConstraint<T>>();
        nAryConstraints_ = new ArrayList<NAryConstraint<T>>();
    }

    // -----------------------------------------------------------------------//
    // Search services //
    // -----------------------------------------------------------------------//

    /**
     * Add a binary constraint to the problem. A binary constraint can not be
     * added while the problem is being solved or if one of the referenced
     * variables has not been previously added to the problem. A constraint can
     * not be added twice.
     * @param constraint
     *            Constraint to add to the problem
     * @return True if the constraint has been added
     */
    private boolean add(final BinaryConstraint<T> constraint) {

        // Can the constraint be added ?
        final boolean canAdd = !searching_ &&
                isVariableDeclared(constraint.getFirstVariable()) &&
                isVariableDeclared(constraint.getSecondVariable()) &&
                !isNAryConstraintDeclared(constraint);

        if (canAdd) {
            // The problem is not being solved, the two referenced variables are
            // declared : the constraint is added.
            nAryConstraints_.add(constraint);
        }

        return canAdd;
    }

    /**
     * Add a constraint to the problem. A constraint can not be added while the
     * problem is being solved or if one of the referenced variables has not
     * been previously added to the problem. A constraint can not be added
     * twice.
     * @param constraint
     *            Constraint to add to the problem
     * @return True if the constraint has been added
     */
    public boolean add(final Constraint<T> constraint) {

        // Can the constraint be added
        boolean canAdd = false;
        if (constraint.isUnary()) {
            // Unary constraint
            canAdd = add((UnaryConstraint<T>) constraint);
        } else if (constraint.isBinary()) {
            // Binary constraint
            canAdd = add((BinaryConstraint<T>) constraint);
        } else if (constraint.isTernary()) {
            // Ternary constraint
            canAdd = add((TernaryConstraint<T>) constraint);
        } else if (constraint.isUnsized()) {
            // Unsized N-ary constraint
            canAdd = add((UnsizedConstraint<T>) constraint);
        }
        if (canAdd) {
            constraint.enablePropagate(true);
        }

        return canAdd;
    }

    /**
     * Add a ternary constraint to the problem. A ternary constraint can not be
     * added while the problem is being solved or if one of the referenced
     * variables has not been previously added to the problem. A constraint can
     * not be added twice.
     * @param constraint
     *            Constraint to add to the problem
     * @return True if the constraint has been added
     */
    private boolean add(final TernaryConstraint<T> constraint) {

        // Can the constraint be added ?
        final boolean canAdd = !searching_ &&
                isVariableDeclared(constraint.getFirstVariable()) &&
                isVariableDeclared(constraint.getSecondVariable()) &&
                isVariableDeclared(constraint.getThirdVariable()) &&
                !isNAryConstraintDeclared(constraint);

        if (canAdd) {
            // The problem is not being solved, the three referenced variables
            // are declared : the constraint is added.
            nAryConstraints_.add(constraint);
        }

        return canAdd;
    }

    /**
     * Add an unary constraint to the problem. An unary constraint can not be
     * added while the problem is being solved or if the referenced variable has
     * not been previously added to the problem. A constraint can not be added
     * twice.
     * @param constraint
     *            Constraint to add to the problem
     * @return True if the constraint has been added
     */
    private boolean add(final UnaryConstraint<T> constraint) {

        // Can the constraint be added ?
        final boolean canAdd = !searching_ &&
                isVariableDeclared(constraint.getVariable()) &&
                !isUnaryConstraintDeclared(constraint);

        if (canAdd) {
            // The problem is not being solved, the referenced variable is
            // declared : the constraint is added.
            unaryConstraints_.add(constraint);
        }

        return canAdd;
    }

    /**
     * Add an unsized constraint to the problem. An unsized constraint can not
     * be added while the problem is being solved or if one of the referenced
     * variables has not been previously added to the problem. A constraint can
     * not be added twice.
     * @param constraint
     *            Constraint to add to the problem
     * @return True if the constraint has been added
     */
    private boolean add(final UnsizedConstraint<T> constraint) {

        // Can the constraint be added ?
        boolean canAdd = !searching_ && !isNAryConstraintDeclared(constraint);
        final Iterator<Variable<T>> var = constraint.getVariablesIterator();
        while (var.hasNext() && canAdd) {
            canAdd = isVariableDeclared(var.next());
        }

        if (canAdd) {
            // The problem is not being solved, the referenced variables are
            // declared : the constraint is added.
            nAryConstraints_.add(constraint);
        }

        return canAdd;
    }

    /**
     * Add a variable to the problem. A variable can not be added while the
     * problem is being solved. A variable can not be added twice.
     * @param variable
     *            Variable to add to the problem
     * @return True if the variable has been added
     */
    public boolean add(final Variable<T> variable) {

        // Can the variable be added ?
        final boolean canAdd = !searching_ && !isVariableDeclared(variable);
        if (canAdd) {
            // The problem is not being solved and the variable has not already
            // been added : the variable is added
            variables_.add(variable);
        }
        return canAdd;
    }

    /**
     * Apply arc consistency 3 algorithm to the problem. The list of constraints
     * to evaluate is initialized with all the constraints of the problem. This
     * consistency can be applied only when the problem is being solved. If this
     * method is called before the start of the search it returns false.
     * @return True if the problem is being solved and arc consistent
     */
    private boolean applyAC3() {
        // Get a copy of the N-ary constraints table
        return applyAC3(nAryConstraints_);
    }

    /**
     * Apply arc consistency 3 algorithm to the problem. The list of constraints
     * to evaluate is initialized with the parameter. This consistency can be
     * applied only when the problem is being solved. If this method is called
     * before the start of the search it returns false.
     * @param constraints
     *            List of constraints to revise
     * @return True if the problem is being solved and arc consistent
     */
    private boolean applyAC3(final List<NAryConstraint<T>> constraints) {

        // Local variables
        NAryConstraint<T> cst;
        boolean consistent = searching_;
        final List<NAryConstraint<T>> toRevise = new ArrayList<NAryConstraint<T>>(
                constraints);

        // The arc consistency can be applied only when the problem is being
        // solved
        if (searching_) {
            while (consistent && !toRevise.isEmpty()) {

                // Get a constraint to revise
                cst = toRevise.remove(0);
                consistent = cst.revise();

                // Get the list of constraint to be revised once more
                final List<Variable<T>> vars = new ArrayList<Variable<T>>(
                        cst.getRecentChangedVariables());
                while (!vars.isEmpty()) {

                    // Get one changed variable
                    final Variable<T> var = vars.remove(0);

                    // Get the associated constraints to merge them with the
                    // current constraints to revise
                    final List<NAryConstraint<T>> varCsts = var
                            .getNAryConstraints();
                    for (NAryConstraint<T> cstToAdd : varCsts) {
                        if (!toRevise.contains(cstToAdd)) {
                            toRevise.add(cstToAdd);
                        }
                    }
                }
            }
        }

        return consistent;
    }

    /**
     * Apply arc consistency 3 algorithm to the problem. The list of constraints
     * to evaluate is initialized with constraints associated with the variable
     * given as parameter. This consistency can be applied only when the problem
     * is being solved. If this method is called before the start of the search
     * it returns false.
     * @param variable
     *            Variable for which the consistency must be checked
     * @return True if the problem is being solved and arc consistent
     */
    public boolean applyAC3(final Variable<T> variable) {
        // Get a copy of the N-ary constraints table
        return applyAC3(variable.getNAryConstraints());
    }

    /**
     * Apply node consistency algorithm to the problem. This consistence can be
     * applied only when the problem is being solved. If this method is called
     * before the start of the search it returns false.
     * @return True if the problem is being solved and node consistent
     */
    private boolean applyNC() {
        final boolean consistent = searching_;

        // The node consistency can be applied only when the problem is being
        // solved
        if (searching_) {

            // Revise unary constraints
            final Iterator<UnaryConstraint<T>> cst = unaryConstraints_
                    .iterator();
            while (cst.hasNext()) {
                cst.next().revise();
            }
        }
        return consistent;
    }

    /**
     * Restore the previous state of each variable.
     */
    void backtrack() {

        // Restore the domains
        final Iterator<Variable<T>> var = variables_.iterator();
        while (var.hasNext()) {
            var.next().restoreDomain();
        }

        // The domains stack has decreased
        stackDepth_--;
    }

    /**
     * Restore the stack of the domain stack corresponding to the given depth.
     * If the current stack depth is lesser than the given stack depth, no
     * backtrack is performed. Warning : All the domain deeper in the stack are
     * lost.
     * @param stackDepth
     *            Depth of the stack to reach
     */
    private void backtrackToStackDepth(final int stackDepth) {
        while (stackDepth_ > stackDepth) {
            backtrack();
        }
    }

    /**
     * Clear the problem. All the added elements are removed. This method can
     * not be called while the problem is being solved.
     * @return True if the problem has been cleared
     */
    public boolean clear() {
        final boolean canClear = !searching_;
        if (canClear) {
            // The problem lists are cleared
            variables_.clear();
            unaryConstraints_.clear();
            nAryConstraints_.clear();
        }
        return canClear;
    }

    // -----------------------------------------------------------------------//
    // Problem definition services //
    // -----------------------------------------------------------------------//

    /**
     * Get the number of choice points in the current search session.
     * @return The number of choice points
     */
    public int getChoicePointsCounter() {
        return choicePointsCounter_;
    }

    /**
     * Get the number of fails in the current search session.
     * @return The number of fails
     */
    public int getFailsCounter() {
        return failsCounter_;
    }

    /**
     * Get the first unbound variable of the problem.
     * @return The first unbound variable found in the list of variables (the
     *         order of the list is the order in which they have been added),
     *         null if no variable has been found
     */
    public Variable<T> getFirstUnboundVariable() {

        // Variable found ?
        Variable<T> found = null;

        // Run through all the variables
        final Iterator<Variable<T>> var = variables_.iterator();
        while (var.hasNext() && found == null) {

            // Get the next variable and check if it is bound
            found = var.next();
            if (found.isBound()) {
                found = null;
            }
        }

        return found;
    }

    /**
     * Get the unbound variable with the greatest number of n-ary constraints.
     * Only the N-ary constraints are taken into account because the unary
     * constraints are not evaluated after the beginning of the search
     * @return The unbound variable with the greatest number of constraints,
     *         null if no unbound variable is found
     */
    public Variable<T> getMostConstraintUnboundVariable() {

        // Variable found
        Variable<T> found = null;

        // Run through all the variables
        final Iterator<Variable<T>> var = variables_.iterator();
        while (var.hasNext()) {

            // Get the next variable, then check if it is unbound and with a
            // higher number of constraint
            final Variable<T> next = var.next();
            if (found == null ||
                    !next.isBound() &&
                    next.getNAryConstraintsNumber() > found
                            .getNAryConstraintsNumber()) {
                found = next;
            }
        }

        return found;
    }

    /**
     * Get the unbound variable with the smallest not empty domain.
     * @return The unbound variable with the smallest domain, null if no
     *         variable is unbound
     */
    public Variable<T> getMostReducedUnboundVariable() {

        // Variable found
        Variable<T> found = null;

        // Run through all the variables
        final Iterator<Variable<T>> var = variables_.iterator();
        while (var.hasNext()) {

            // Get the next variable, then check if it is unbound and with a
            // most reduced domain
            final Variable<T> next = var.next();
            if (!next.isBound() &&
                    (found == null || next.getDomainSize() < found
                            .getDomainSize())) {
                found = next;
            }
        }

        return found;
    }

    /**
     * Get the number of declared constraints.
     * @return The number of constraints
     */
    public int getNumberOfConstraints() {
        return unaryConstraints_.size() + nAryConstraints_.size();
    }

    /**
     * Get the number of declared variables.
     * @return The number of variables
     */
    public int getNumberOfVariables() {
        return variables_.size();
    }

    // -----------------------------------------------------------------------//
    // Variable selectors //
    // -----------------------------------------------------------------------//

    /**
     * Get the current stack depth of the problem.
     * @return The accumulated number of calls to backtrack substracted to the
     *         accumulated number of calls to store.
     */
    public int getStackDepth() {
        return stackDepth_;
    }

    /**
     * Increase the number of choice points.
     */
    public void increaseChoicePointsCounter() {
        choicePointsCounter_++;
    }

    /**
     * Increase the number of fails.
     */
    protected void increaseFailsCounter() {
        failsCounter_++;
    }

    /**
     * Search the constraint given as parameter in the table of declared N-ary
     * constraints and return true if it found.
     * @param constraint
     *            Constraint to find in the N-ary constraints table of the
     *            problem
     * @return True if the constraint is found, false otherwise
     */
    private boolean isNAryConstraintDeclared(final NAryConstraint<T> constraint) {
        return nAryConstraints_.contains(constraint);
    }

    /**
     * Search the constraint given as parameter in the table of declared unary
     * constraints and return true if it found.
     * @param constraint
     *            Constraint to find in the unary constraints table of the
     *            problem
     * @return True if the constraint is found, false otherwise
     */
    private boolean isUnaryConstraintDeclared(
            final UnaryConstraint<T> constraint) {
        return unaryConstraints_.contains(constraint);
    }

    /**
     * Search the variable given as parameter in the table of declared variables
     * and return true if it found.
     * @param variable
     *            Variable to find in the variables table of the problem
     * @return True if the variable is found, false otherwise
     */
    private boolean isVariableDeclared(final Variable<T> variable) {
        return variables_.contains(variable);
    }

    /**
     * Search if the variable given as parameter is referenced by one more
     * constraints of the problem.
     * @param variable
     *            Variable whose references are checked
     * @return True if the variable is referenced, false otherwise
     */
    private boolean isVariableReferenced(final Variable<T> variable) {

        // Variables locales
        boolean isReferenced = false;
        final Iterator<UnaryConstraint<T>> unary = unaryConstraints_.iterator();
        final Iterator<NAryConstraint<T>> nary = nAryConstraints_.iterator();

        // Check if the variable is referenced by an unary constraint
        while (!isReferenced && unary.hasNext()) {
            isReferenced = unary.next().isVariableReferenced(variable);
        }

        // Check if the variable is referenced by a N-ary constraint
        while (!isReferenced && nary.hasNext()) {
            isReferenced = nary.next().isVariableReferenced(variable);
        }

        return isReferenced;
    }

    /**
     * Remove a constraint of the problem. A constraint can not be removed while
     * the problem is being solved.
     * @param constraint
     *            Constraint to remove
     * @return True if the constraint has been removed
     */
    public boolean remove(final Constraint<T> constraint) {
        boolean canRemove = !searching_;
        if (canRemove) {
            if (constraint.isUnary()) {
                // Remove the unary constraint
                canRemove = unaryConstraints_.remove(constraint);
            } else {
                // Remove the N-ary constraint
                canRemove = nAryConstraints_.remove(constraint);
            }
        }

        if (canRemove) {
            constraint.enablePropagate(false);
        }

        return canRemove;
    }

    /**
     * Remove a variable of the problem. A variable can not be removed while the
     * problem is being solved or if the variable is referenced by one or more
     * constraints.
     * @param variable
     *            Variable to remove
     * @return True if the variable has been removed
     */
    public boolean remove(final Variable<T> variable) {

        // Can the variable be removed
        final boolean canRemove = !searching_ &&
                !isVariableReferenced(variable);
        if (canRemove) {
            // Remove the variable
            variables_.remove(variable);
        }
        return canRemove;
    }

    /**
     * Start the search for a solution.
     * @return True when the problem is consistent. The search can be performed
     *         only when the problem is consistent. When the return is false,
     *         search is forbidden.
     */
    public boolean startSearch() {

        // Initializes attributes
        failsCounter_ = 0;
        choicePointsCounter_ = 0;
        searching_ = true;

        // Apply node and arc consistency
        store();
        if (!(applyNC() && applyAC3())) {
            increaseFailsCounter();
            stopSearch();
        }

        return searching_;
    }

    /**
     * Stop the search for a solution.
     */
    public void stopSearch() {
        // Initializes attributes
        searching_ = false;
        // Restore domains stack
        backtrackToStackDepth(1);
    }

    /**
     * Store the current state of each variable.
     */
    public void store() {

        // Store the variables domain
        final Iterator<Variable<T>> var = variables_.iterator();
        while (var.hasNext()) {
            var.next().saveDomain();
        }

        // The domains stack has increased
        stackDepth_++;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public String toString() {

        // String builder
        final StringBuilder builder = new StringBuilder();

        // Iterators
        final Iterator<Variable<T>> var = variables_.iterator();
        final Iterator<UnaryConstraint<T>> unary = unaryConstraints_.iterator();
        final Iterator<NAryConstraint<T>> nary = nAryConstraints_.iterator();

        // List of variables
        builder.append("List of variables\n");
        while (var.hasNext()) {
            builder.append("   ");
            builder.append(var.next().toString());
            builder.append("\n");
        }

        // List of unary constraints
        builder.append("\nList of unary constraints\n");
        while (unary.hasNext()) {
            builder.append("   ");
            builder.append(unary.next().toString());
            builder.append("\n");
        }

        // List of nary constraints
        builder.append("\nList of N-ary constraints\n");
        while (nary.hasNext()) {
            builder.append("   ");
            builder.append(nary.next().toString());
            builder.append("\n");
        }

        return builder.toString();
    }

}