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;

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

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

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

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

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

  50.     /**
  51.      * Table of the n-ary constraints associated with the variable.
  52.      */
  53.     private List<NAryConstraint<T>> nAryConstraints_;

  55.     /** Name of the variable. */
  56.     private String name_;

  58.     /**
  59.      * Constructor.
  60.      * @param name
  61.      *            Name of the variable
  62.      */
  63.     public Variable(final String name) {
  64.         name_ = name;
  65.         domains_ = new Stack<Domain<T>>();
  66.         domainChanges_ = new Stack<Boolean>();
  67.         canBeSelected_ = new Stack<Boolean>();
  68.         nAryConstraints_ = new ArrayList<NAryConstraint<T>>();
  69.     }

  71.     /**
  72.      * Add a new domain to the current stack.
  73.      * @param domain
  74.      *            Domain to add to the stack
  75.      */
  76.     protected void addDomain(final Domain<T> domain) {
  77.         domains_.add(domain);
  78.     }

  80.     /**
  81.      * Add a new domain change to the current stack.
  82.      * @param changed
  83.      *            Domain change to add to the stack
  84.      */
  85.     protected void addDomainChange(final boolean changed) {
  86.         domainChanges_.add(changed);
  87.     }

  89.     /**
  90.      * Add a new N-ary constraint referenced by the variable.
  91.      * @param constraint
  92.      *            Constraint to add
  93.      */
  94.     public void addNAryConstraint(final NAryConstraint<T> constraint) {
  95.         nAryConstraints_.add(constraint);
  96.     }

  98.     /**
  99.      * Add a new selection flag to the current stack.
  100.      * @param canBeSelected
  101.      *            Selection flag to add to the stack
  102.      */
  103.     protected void addSelectionFlag(final boolean canBeSelected) {
  104.         canBeSelected_.add(canBeSelected);
  105.     }

  107.     /**
  108.      * Test if the variable can be selected to be assigned.
  109.      * @return True if the variable can be selected
  110.      */
  111.     public boolean canBeSelected() {
  112.         return canBeSelected_.peek();
  113.     }

  115.     /**
  116.      * Check if the current domain of the variable contain the given value.
  117.      * @param value
  118.      *            Value to look for in the current domain
  119.      * @return "true" if the domain contains the variable
  120.      */
  121.     public boolean contains(final Value<T> value) {
  122.         return getDomain().contains(value);
  123.     }

  125.     /**
  126.      * Disable selection of the variable until its domain has changed.
  127.      */
  128.     public void disableSelection() {
  129.         canBeSelected_.pop();
  130.         canBeSelected_.push(false);
  131.     }

  133.     /**
  134.      * Get the current domain of the variable.
  135.      * @return The current domain of the variable
  136.      */
  137.     public Domain<T> getDomain() {
  138.         return domains_.peek();
  139.     }

  141.     /**
  142.      * Get the size of the domain.
  143.      * @return The number of elements in the variable domain
  144.      */
  145.     public int getDomainSize() {
  146.         return getDomain().getSize();
  147.     }

  149.     /**
  150.      * Get the first value of the domain. The notion "first" is meaningful only
  151.      * if the values are ordered. Otherwise an arbitrary value is selected in
  152.      * the domain.
  153.      * @return The first value of the domain.
  154.      * @throws EmptyDomainException
  155.      *             The current domain is empty
  156.      */
  157.     public Value<T> getFirstValue() throws EmptyDomainException {
  158.         return getDomain().getFirstValue();
  159.     }

  161.     /**
  162.      * Get the name of the variable.
  163.      * @return Name of the variable
  164.      */
  165.     public String getName() {
  166.         return name_;
  167.     }

  169.     /**
  170.      * Get the N-ary constraints associated with the variable.
  171.      * @return The list of N-ary constraint associated with the variable
  172.      */
  173.     public List<NAryConstraint<T>> getNAryConstraints() {
  174.         return nAryConstraints_;
  175.     }

  177.     /**
  178.      * Get the number of n-ary constraints associated with the variable.
  179.      * @return The number of n-ary constraints
  180.      */
  181.     public int getNAryConstraintsNumber() {
  182.         return nAryConstraints_.size();
  183.     }

  185.     /**
  186.      * Get the value of the variable when it is bound.
  187.      * @return The value of the variable
  188.      */
  189.     public Value<T> getValue() {

  191.         // Calling the method is legal if and only if the variable is bound
  192.         if (!isBound()) {
  193.             throw new UnboundDomainException();
  194.         }

  196.         return getFirstValue();
  197.     }

  199.     /**
  200.      * Test if the variable is bound (the domain has only one value).
  201.      * @return True if the variable is bound
  202.      */
  203.     public boolean isBound() {
  204.         return getDomain().hasSingleValue();
  205.     }

  207.     /**
  208.      * Test if the variable has an empty domain (the domain contains no value).
  209.      * @return True if the domain of the variable is empty
  210.      */
  211.     public boolean isDomainEmpty() {
  212.         return getDomain().isEmpty();
  213.     }

  215.     /**
  216.      * Remove the value of the domain of the variable.
  217.      * @param value
  218.      *            Value to remove of the domain
  219.      * @return True if the domain is changed
  220.      */
  221.     public boolean removeValue(final Value<T> value) {
  222.         return setDomainChanged(domains_.peek().removeValue(value));
  223.     }

  225.     /**
  226.      * Restore the more recently saved domain of the variable. The current value
  227.      * of the domain is replaced.
  228.      */
  229.     public void restoreDomain() {

  231.         // This is only possible when previous domains exist
  232.         if (domains_.size() > 1) {
  233.             // Pop the unchanged domain to delete it (smart pointer)
  234.             domains_.pop();
  235.             domainChanges_.pop();
  236.             canBeSelected_.pop();

  238.             // The last domain must not be a reference to an implementation
  239.             // referenced by other stored domains
  240.             if (!domainChanges_.peek() && domains_.size() > 1) {
  241.                 // Create a copy of the last domain
  242.                 final Domain<T> lastDomain = getDomain().copy();
  243.                 // Pop the last domain
  244.                 domains_.pop();
  245.                 // The last domain can be freely modified
  246.                 domains_.push(lastDomain);
  247.             }
  248.         }
  249.     };

  251.     /**
  252.      * Save the current domain of the variable.
  253.      */
  254.     public void saveDomain() {

  256.         // If the current domain has changed it must be kept as is. Otherwise
  257.         // the older version, if it exists, can be referenced to avoid useless
  258.         // memory use.
  259.         if (!domainChanges_.peek() && domains_.size() > 1) {
  260.             // Pop the unchanged domain to delete it
  261.             domains_.pop();
  262.             // Reference the previous domain
  263.             domains_.push(domains_.peek());
  264.         }

  266.         // Create a copy of the last domain. The copy is initially considered as
  267.         // not modified. The "can be selected" flag is not changed.
  268.         final Domain<T> lastDomain = getDomain().copy();
  269.         domains_.push(lastDomain);
  270.         domainChanges_.push(false);
  271.         canBeSelected_.push(canBeSelected_.peek());
  272.     };

  274.     /**
  275.      * Set the value of the last "domain changed" and "can be selected"
  276.      * indicators.
  277.      * @param changed
  278.      *            Tell if the domain has just changed
  279.      * @return True if the domain has just changed
  280.      */
  281.     public boolean setDomainChanged(final boolean changed) {
  282.         // Store the domain change
  283.         if (!domainChanges_.isEmpty()) {
  284.             final boolean previous = domainChanges_.pop();
  285.             domainChanges_.push(previous || changed);
  286.         }
  287.         // A domain that has changed can always be selected
  288.         if (changed) {
  289.             canBeSelected_.pop();
  290.             canBeSelected_.push(true);
  291.         }
  292.         return changed;
  293.     }

  295.     /**
  296.      * Set the name of the variable.
  297.      * @param name
  298.      *            Name of the variable
  299.      */
  300.     public void setName(final String name) {
  301.         name_ = name;
  302.     }

  304.     /**
  305.      * Set the value of the variable (reduce its domain to a single value).
  306.      * @param value
  307.      *            Unique value of the variable
  308.      * @return True if the domain is changed
  309.      */
  310.     public boolean setValue(final Value<T> value) {
  311.         return setDomainChanged(domains_.peek().setValue(value));
  312.     }

  314.     /**
  315.      * {@inheritDoc}
  316.      */
  317.     @Override
  318.     public String toString() {
  319.         return name_ + " / " + getDomain() + "(changed = " +
  320.                 domainChanges_.peek() + ")";
  321.     }

  323. }
Created with JaCoCo 0.7.4.201502262128