EqualToMaxOfIntArray.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.integer;

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

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

/**
 * Constraint specifying that one specific integer variable is the maximum of
 * the integer variables of a given array.
 */
public class EqualToMaxOfIntArray extends UnsizedConstraint<IntValue> {

    /** Array of variables. */
    private List<IntVar> array_;

    /** Maximum. */
    private IntVar max_;

    /**
     * Constructor.
     * @param max
     *            Maximum of the array
     * @param array
     *            Array of variables
     */
    public EqualToMaxOfIntArray(final IntVar max, final List<IntVar> array) {
        super(max.getName() + "=MAX" + array,
                new ArrayList<Variable<IntValue>>());
        // Add the values of the array and the maximum to the array of variables
        for (IntVar variable : array) {
            addVariable(variable);
        }
        addVariable(max);
        // Initialize attributes
        max_ = max;
        array_ = array;
    }

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

        // Modification indicator
        boolean minModif = false;
        boolean maxModif = false;

        // New min and max for each variable (initialized with the absolute
        // minimum value since the max function is applied on it)
        IntValue newMin = IntValue.MIN_INT_VALUE;
        IntValue newMax = IntValue.MIN_INT_VALUE;
        // Variables iterator
        Iterator<IntVar> var = array_.iterator();

        // Computes the minimum and maximum values of all the values of the
        // right hand
        while (var.hasNext()) {
            final IntVar variable = var.next();
            if (!variable.isDomainEmpty()) {
                // New minimum
                if (newMin.compareTo(variable.getMinValue()) < 0) {
                    newMin = variable.getMinValue();
                }
                // New maximum
                if (newMax.compareTo(variable.getMaxValue()) < 0) {
                    newMax = variable.getMaxValue();
                }
            }
        }

        // Reduce the maximum variable
        minModif = max_.reduceWithMinValue(newMin);
        maxModif = max_.reduceWithMaxValue(newMax);
        if (minModif || maxModif) {
            addRecentChangedVariable(max_);
        }

        // Reduce the array of variables
        var = array_.iterator();
        while (var.hasNext()) {
            // Propagate on each variable
            final IntVar variable = var.next();
            if (!max_.isDomainEmpty()) {
                // Reduce the domain
                if (variable.reduceWithMaxValue(max_.getMaxValue())) {
                    addRecentChangedVariable(variable);
                }
            }
        }
    }

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

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

        // Display the constraint
        builder.append(max_.getName());
        builder.append("=MAX(");
        final Iterator<IntVar> vars = array_.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();
    }

}