AllDiff.java

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

  18. import java.util.Iterator;
  19. import java.util.List;

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

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

  27.     /**
  28.      * Constructor.
  29.      * @param array
  30.      *            Array of variables
  31.      */
  32.     public AllDiff(final List<Variable<T>> array) {
  33.         super("ALLDIFF" + array, array);
  34.     }

  35.     /**
  36.      * {@inheritDoc}
  37.      */
  38.     @Override
  39.     public void propagate() {

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

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

  45.             if (var.isBound()) {

  46.                 // When a variable is bound, all other variables of the array
  47.                 // must have a different value.
  48.                 for (Variable<T> other : getVariables()) {
  49.                     if (other != var) {
  50.                         if (other.removeValue(var.getValue())) {
  51.                             addRecentChangedVariable(other);
  52.                         }
  53.                     }
  54.                 }
  55.             }
  56.         }

  57.     }

  58.     /**
  59.      * {@inheritDoc}
  60.      */
  61.     @Override
  62.     public String toString() {

  63.         // String builder
  64.         final StringBuilder builder = new StringBuilder();

  65.         // Display the constraint
  66.         builder.append("ALLDIFF(");
  67.         final Iterator<Variable<T>> vars = getVariables().iterator();
  68.         while (vars.hasNext()) {
  69.             // Display every variable
  70.             builder.append(vars.next().getName());
  71.             if (vars.hasNext()) {
  72.                 // Next variable
  73.                 builder.append(", ");
  74.             } else {
  75.                 // Last variable
  76.                 builder.append(")");
  77.             }
  78.         }

  79.         return builder.toString();
  80.     }

  81. }