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() + ")";
}
}