Variable.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;

  18. import java.util.ArrayList;
  19. import java.util.List;
  20. import java.util.Stack;

  21. /**
  22.  * Represents a variable of a constraint solving problem.
  23.  */
  24. public abstract class Variable<T> {

  25.     /**
  26.      * Table of the domains of the variable. Each domain of the table
  27.      * corresponds to a state of the variable propagation.
  28.      */
  29.     private Stack<Domain<T>> domains_;

  30.     /**
  31.      * Table of domain change indicators. An indicator is true if the
  32.      * corresponding domain (the domain that has the same index in the domains
  33.      * table) has been changed since its initialization.
  34.      */
  35.     private Stack<Boolean> domainChanges_;

  36.     /**
  37.      * Table of flags that indicate whether or not the domain can be selected to
  38.      * be assigned. An indicator is true if the corresponding domain (the domain
  39.      * that has the same index in the domains table) can be selected to be
  40.      * assigned. This indicator may be used in strategy that consist of
  41.      * postponing a variable assignment when it fails.
  42.      */
  43.     private Stack<Boolean> canBeSelected_;

  44.     /**
  45.      * Table of the n-ary constraints associated with the variable.
  46.      */
  47.     private List<NAryConstraint<T>> nAryConstraints_;

  48.     /** Name of the variable. */
  49.     private String name_;

  50.     /**
  51.      * Constructor.
  52.      * @param name
  53.      *            Name of the variable
  54.      */
  55.     public Variable(final String name) {
  56.         name_ = name;
  57.         domains_ = new Stack<Domain<T>>();
  58.         domainChanges_ = new Stack<Boolean>();
  59.         canBeSelected_ = new Stack<Boolean>();
  60.         nAryConstraints_ = new ArrayList<NAryConstraint<T>>();
  61.     }

  62.     /**
  63.      * Add a new domain to the current stack.
  64.      * @param domain
  65.      *            Domain to add to the stack
  66.      */
  67.     protected void addDomain(final Domain<T> domain) {
  68.         domains_.add(domain);
  69.     }

  70.     /**
  71.      * Add a new domain change to the current stack.
  72.      * @param changed
  73.      *            Domain change to add to the stack
  74.      */
  75.     protected void addDomainChange(final boolean changed) {
  76.         domainChanges_.add(changed);
  77.     }

  78.     /**
  79.      * Add a new N-ary constraint referenced by the variable.
  80.      * @param constraint
  81.      *            Constraint to add
  82.      */
  83.     public void addNAryConstraint(final NAryConstraint<T> constraint) {
  84.         nAryConstraints_.add(constraint);
  85.     }

  86.     /**
  87.      * Add a new selection flag to the current stack.
  88.      * @param canBeSelected
  89.      *            Selection flag to add to the stack
  90.      */
  91.     protected void addSelectionFlag(final boolean canBeSelected) {
  92.         canBeSelected_.add(canBeSelected);
  93.     }

  94.     /**
  95.      * Test if the variable can be selected to be assigned.
  96.      * @return True if the variable can be selected
  97.      */
  98.     public boolean canBeSelected() {
  99.         return canBeSelected_.peek();
  100.     }

  101.     /**
  102.      * Check if the current domain of the variable contain the given value.
  103.      * @param value
  104.      *            Value to look for in the current domain
  105.      * @return "true" if the domain contains the variable
  106.      */
  107.     public boolean contains(final Value<T> value) {
  108.         return getDomain().contains(value);
  109.     }

  110.     /**
  111.      * Disable selection of the variable until its domain has changed.
  112.      */
  113.     public void disableSelection() {
  114.         canBeSelected_.pop();
  115.         canBeSelected_.push(false);
  116.     }

  117.     /**
  118.      * Get the current domain of the variable.
  119.      * @return The current domain of the variable
  120.      */
  121.     public Domain<T> getDomain() {
  122.         return domains_.peek();
  123.     }

  124.     /**
  125.      * Get the size of the domain.
  126.      * @return The number of elements in the variable domain
  127.      */
  128.     public int getDomainSize() {
  129.         return getDomain().getSize();
  130.     }

  131.     /**
  132.      * Get the first value of the domain. The notion "first" is meaningful only
  133.      * if the values are ordered. Otherwise an arbitrary value is selected in
  134.      * the domain.
  135.      * @return The first value of the domain.
  136.      * @throws EmptyDomainException
  137.      *             The current domain is empty
  138.      */
  139.     public Value<T> getFirstValue() throws EmptyDomainException {
  140.         return getDomain().getFirstValue();
  141.     }

  142.     /**
  143.      * Get the name of the variable.
  144.      * @return Name of the variable
  145.      */
  146.     public String getName() {
  147.         return name_;
  148.     }

  149.     /**
  150.      * Get the N-ary constraints associated with the variable.
  151.      * @return The list of N-ary constraint associated with the variable
  152.      */
  153.     public List<NAryConstraint<T>> getNAryConstraints() {
  154.         return nAryConstraints_;
  155.     }

  156.     /**
  157.      * Get the number of n-ary constraints associated with the variable.
  158.      * @return The number of n-ary constraints
  159.      */
  160.     public int getNAryConstraintsNumber() {
  161.         return nAryConstraints_.size();
  162.     }

  163.     /**
  164.      * Get the value of the variable when it is bound.
  165.      * @return The value of the variable
  166.      */
  167.     public Value<T> getValue() {

  168.         // Calling the method is legal if and only if the variable is bound
  169.         if (!isBound()) {
  170.             throw new UnboundDomainException();
  171.         }

  172.         return getFirstValue();
  173.     }

  174.     /**
  175.      * Test if the variable is bound (the domain has only one value).
  176.      * @return True if the variable is bound
  177.      */
  178.     public boolean isBound() {
  179.         return getDomain().hasSingleValue();
  180.     }

  181.     /**
  182.      * Test if the variable has an empty domain (the domain contains no value).
  183.      * @return True if the domain of the variable is empty
  184.      */
  185.     public boolean isDomainEmpty() {
  186.         return getDomain().isEmpty();
  187.     }

  188.     /**
  189.      * Remove the value of the domain of the variable.
  190.      * @param value
  191.      *            Value to remove of the domain
  192.      * @return True if the domain is changed
  193.      */
  194.     public boolean removeValue(final Value<T> value) {
  195.         return setDomainChanged(domains_.peek().removeValue(value));
  196.     }

  197.     /**
  198.      * Restore the more recently saved domain of the variable. The current value
  199.      * of the domain is replaced.
  200.      */
  201.     public void restoreDomain() {

  202.         // This is only possible when previous domains exist
  203.         if (domains_.size() > 1) {
  204.             // Pop the unchanged domain to delete it (smart pointer)
  205.             domains_.pop();
  206.             domainChanges_.pop();
  207.             canBeSelected_.pop();

  208.             // The last domain must not be a reference to an implementation
  209.             // referenced by other stored domains
  210.             if (!domainChanges_.peek() && domains_.size() > 1) {
  211.                 // Create a copy of the last domain
  212.                 final Domain<T> lastDomain = getDomain().copy();
  213.                 // Pop the last domain
  214.                 domains_.pop();
  215.                 // The last domain can be freely modified
  216.                 domains_.push(lastDomain);
  217.             }
  218.         }
  219.     };

  220.     /**
  221.      * Save the current domain of the variable.
  222.      */
  223.     public void saveDomain() {

  224.         // If the current domain has changed it must be kept as is. Otherwise
  225.         // the older version, if it exists, can be referenced to avoid useless
  226.         // memory use.
  227.         if (!domainChanges_.peek() && domains_.size() > 1) {
  228.             // Pop the unchanged domain to delete it
  229.             domains_.pop();
  230.             // Reference the previous domain
  231.             domains_.push(domains_.peek());
  232.         }

  233.         // Create a copy of the last domain. The copy is initially considered as
  234.         // not modified. The "can be selected" flag is not changed.
  235.         final Domain<T> lastDomain = getDomain().copy();
  236.         domains_.push(lastDomain);
  237.         domainChanges_.push(false);
  238.         canBeSelected_.push(canBeSelected_.peek());
  239.     };

  240.     /**
  241.      * Set the value of the last "domain changed" and "can be selected"
  242.      * indicators.
  243.      * @param changed
  244.      *            Tell if the domain has just changed
  245.      * @return True if the domain has just changed
  246.      */
  247.     public boolean setDomainChanged(final boolean changed) {
  248.         // Store the domain change
  249.         if (!domainChanges_.isEmpty()) {
  250.             final boolean previous = domainChanges_.pop();
  251.             domainChanges_.push(previous || changed);
  252.         }
  253.         // A domain that has changed can always be selected
  254.         if (changed) {
  255.             canBeSelected_.pop();
  256.             canBeSelected_.push(true);
  257.         }
  258.         return changed;
  259.     }

  260.     /**
  261.      * Set the name of the variable.
  262.      * @param name
  263.      *            Name of the variable
  264.      */
  265.     public void setName(final String name) {
  266.         name_ = name;
  267.     }

  268.     /**
  269.      * Set the value of the variable (reduce its domain to a single value).
  270.      * @param value
  271.      *            Unique value of the variable
  272.      * @return True if the domain is changed
  273.      */
  274.     public boolean setValue(final Value<T> value) {
  275.         return setDomainChanged(domains_.peek().setValue(value));
  276.     }

  277.     /**
  278.      * {@inheritDoc}
  279.      */
  280.     @Override
  281.     public String toString() {
  282.         return name_ + " / " + getDomain() + "(changed = " +
  283.                 domainChanges_.peek() + ")";
  284.     }

  285. }