Variable.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;
- import java.util.ArrayList;
- import java.util.List;
- import java.util.Stack;
- /**
- * Represents a variable of a constraint solving problem.
- */
- public abstract class Variable<T> {
- /**
- * Table of the domains of the variable. Each domain of the table
- * corresponds to a state of the variable propagation.
- */
- private Stack<Domain<T>> domains_;
- /**
- * Table of domain change indicators. An indicator is true if the
- * corresponding domain (the domain that has the same index in the domains
- * table) has been changed since its initialization.
- */
- private Stack<Boolean> domainChanges_;
- /**
- * Table of flags that indicate whether or not the domain can be selected to
- * be assigned. An indicator is true if the corresponding domain (the domain
- * that has the same index in the domains table) can be selected to be
- * assigned. This indicator may be used in strategy that consist of
- * postponing a variable assignment when it fails.
- */
- private Stack<Boolean> canBeSelected_;
- /**
- * Table of the n-ary constraints associated with the variable.
- */
- private List<NAryConstraint<T>> nAryConstraints_;
- /** Name of the variable. */
- private String name_;
- /**
- * Constructor.
- * @param name
- * Name of the variable
- */
- public Variable(final String name) {
- name_ = name;
- domains_ = new Stack<Domain<T>>();
- domainChanges_ = new Stack<Boolean>();
- canBeSelected_ = new Stack<Boolean>();
- nAryConstraints_ = new ArrayList<NAryConstraint<T>>();
- }
- /**
- * Add a new domain to the current stack.
- * @param domain
- * Domain to add to the stack
- */
- protected void addDomain(final Domain<T> domain) {
- domains_.add(domain);
- }
- /**
- * Add a new domain change to the current stack.
- * @param changed
- * Domain change to add to the stack
- */
- protected void addDomainChange(final boolean changed) {
- domainChanges_.add(changed);
- }
- /**
- * Add a new N-ary constraint referenced by the variable.
- * @param constraint
- * Constraint to add
- */
- public void addNAryConstraint(final NAryConstraint<T> constraint) {
- nAryConstraints_.add(constraint);
- }
- /**
- * Add a new selection flag to the current stack.
- * @param canBeSelected
- * Selection flag to add to the stack
- */
- protected void addSelectionFlag(final boolean canBeSelected) {
- canBeSelected_.add(canBeSelected);
- }
- /**
- * Test if the variable can be selected to be assigned.
- * @return True if the variable can be selected
- */
- public boolean canBeSelected() {
- return canBeSelected_.peek();
- }
- /**
- * Check if the current domain of the variable contain the given value.
- * @param value
- * Value to look for in the current domain
- * @return "true" if the domain contains the variable
- */
- public boolean contains(final Value<T> value) {
- return getDomain().contains(value);
- }
- /**
- * Disable selection of the variable until its domain has changed.
- */
- public void disableSelection() {
- canBeSelected_.pop();
- canBeSelected_.push(false);
- }
- /**
- * Get the current domain of the variable.
- * @return The current domain of the variable
- */
- public Domain<T> getDomain() {
- return domains_.peek();
- }
- /**
- * Get the size of the domain.
- * @return The number of elements in the variable domain
- */
- public int getDomainSize() {
- return getDomain().getSize();
- }
- /**
- * Get the first value of the domain. The notion "first" is meaningful only
- * if the values are ordered. Otherwise an arbitrary value is selected in
- * the domain.
- * @return The first value of the domain.
- * @throws EmptyDomainException
- * The current domain is empty
- */
- public Value<T> getFirstValue() throws EmptyDomainException {
- return getDomain().getFirstValue();
- }
- /**
- * Get the name of the variable.
- * @return Name of the variable
- */
- public String getName() {
- return name_;
- }
- /**
- * Get the N-ary constraints associated with the variable.
- * @return The list of N-ary constraint associated with the variable
- */
- public List<NAryConstraint<T>> getNAryConstraints() {
- return nAryConstraints_;
- }
- /**
- * Get the number of n-ary constraints associated with the variable.
- * @return The number of n-ary constraints
- */
- public int getNAryConstraintsNumber() {
- return nAryConstraints_.size();
- }
- /**
- * Get the value of the variable when it is bound.
- * @return The value of the variable
- */
- public Value<T> getValue() {
- // Calling the method is legal if and only if the variable is bound
- if (!isBound()) {
- throw new UnboundDomainException();
- }
- return getFirstValue();
- }
- /**
- * Test if the variable is bound (the domain has only one value).
- * @return True if the variable is bound
- */
- public boolean isBound() {
- return getDomain().hasSingleValue();
- }
- /**
- * Test if the variable has an empty domain (the domain contains no value).
- * @return True if the domain of the variable is empty
- */
- public boolean isDomainEmpty() {
- return getDomain().isEmpty();
- }
- /**
- * Remove the value of the domain of the variable.
- * @param value
- * Value to remove of the domain
- * @return True if the domain is changed
- */
- public boolean removeValue(final Value<T> value) {
- return setDomainChanged(domains_.peek().removeValue(value));
- }
- /**
- * Restore the more recently saved domain of the variable. The current value
- * of the domain is replaced.
- */
- public void restoreDomain() {
- // This is only possible when previous domains exist
- if (domains_.size() > 1) {
- // Pop the unchanged domain to delete it (smart pointer)
- domains_.pop();
- domainChanges_.pop();
- canBeSelected_.pop();
- // The last domain must not be a reference to an implementation
- // referenced by other stored domains
- if (!domainChanges_.peek() && domains_.size() > 1) {
- // Create a copy of the last domain
- final Domain<T> lastDomain = getDomain().copy();
- // Pop the last domain
- domains_.pop();
- // The last domain can be freely modified
- domains_.push(lastDomain);
- }
- }
- };
- /**
- * Save the current domain of the variable.
- */
- public void saveDomain() {
- // If the current domain has changed it must be kept as is. Otherwise
- // the older version, if it exists, can be referenced to avoid useless
- // memory use.
- if (!domainChanges_.peek() && domains_.size() > 1) {
- // Pop the unchanged domain to delete it
- domains_.pop();
- // Reference the previous domain
- domains_.push(domains_.peek());
- }
- // Create a copy of the last domain. The copy is initially considered as
- // not modified. The "can be selected" flag is not changed.
- final Domain<T> lastDomain = getDomain().copy();
- domains_.push(lastDomain);
- domainChanges_.push(false);
- canBeSelected_.push(canBeSelected_.peek());
- };
- /**
- * Set the value of the last "domain changed" and "can be selected"
- * indicators.
- * @param changed
- * Tell if the domain has just changed
- * @return True if the domain has just changed
- */
- public boolean setDomainChanged(final boolean changed) {
- // Store the domain change
- if (!domainChanges_.isEmpty()) {
- final boolean previous = domainChanges_.pop();
- domainChanges_.push(previous || changed);
- }
- // A domain that has changed can always be selected
- if (changed) {
- canBeSelected_.pop();
- canBeSelected_.push(true);
- }
- return changed;
- }
- /**
- * Set the name of the variable.
- * @param name
- * Name of the variable
- */
- public void setName(final String name) {
- name_ = name;
- }
- /**
- * Set the value of the variable (reduce its domain to a single value).
- * @param value
- * Unique value of the variable
- * @return True if the domain is changed
- */
- public boolean setValue(final Value<T> value) {
- return setDomainChanged(domains_.peek().setValue(value));
- }
- /**
- * {@inheritDoc}
- */
- @Override
- public String toString() {
- return name_ + " / " + getDomain() + "(changed = " +
- domainChanges_.peek() + ")";
- }
- }