AllDiff.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.model.general;

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

import org.csp.constraint.model.UnsizedConstraint;
import org.csp.constraint.model.Variable;

/**
 * Constraint specifying that all the variables of an array have a different
 * value.
 */
public class AllDiff<T> extends UnsizedConstraint<T> {

    /**
     * Constructor.
     * @param array
     *            Array of variables
     */
    public AllDiff(final List<Variable<T>> array) {
        super("ALLDIFF" + array, array);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public void propagate() {

        // NOTE : The current implementation of the propagation algorithm is
        // quite dummy. More complex assumption could be made to prune variable
        // more efficiently, i.e. without waiting for a variable to be bound.

        // Propagate once a variable is bound
        for (Variable<T> var : getVariables()) {

            if (var.isBound()) {

                // When a variable is bound, all other variables of the array
                // must have a different value.
                for (Variable<T> other : getVariables()) {
                    if (other != var) {
                        if (other.removeValue(var.getValue())) {
                            addRecentChangedVariable(other);
                        }
                    }
                }
            }
        }

    }

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

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

        // Display the constraint
        builder.append("ALLDIFF(");
        final Iterator<Variable<T>> vars = getVariables().iterator();
        while (vars.hasNext()) {
            // Display every variable
            builder.append(vars.next().getName());
            if (vars.hasNext()) {
                // Next variable
                builder.append(", ");
            } else {
                // Last variable
                builder.append(")");
            }
        }

        return builder.toString();
    }

}