IntervalDomain.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.Iterator;
import java.util.TreeSet;
/**
* Represents a non continuous interval of integer values. The size of the
* domain is is the number of included values.
*/
public class IntervalDomain<T extends Value<T>> implements Domain<T> {
/**
* Intervals of the domain.
*/
private TreeSet<Interval<T>> values_;
/**
* Default constructor.
*/
protected IntervalDomain() {
values_ = new TreeSet<Interval<T>>();
}
/**
* Usual constructor.
* @param min
* Lower bound of the domain
* @param max
* Upper bound of the domain
*/
public IntervalDomain(final T min, final T max) {
values_ = new TreeSet<Interval<T>>();
values_.add(new Interval<T>(min, max));
}
/**
* {@inheritDoc}
*/
@Override
public boolean contains(final Value<T> value) {
// Result
boolean contains = false;
// Intervals of the domain
final Iterator<Interval<T>> intervals = values_.iterator();
while (intervals.hasNext() && !contains) {
contains = intervals.next().isInInterval(value.value());
}
return contains;
}
/**
* {@inheritDoc}
*/
@Override
public Domain<T> copy() {
final IntervalDomain<T> copy = new IntervalDomain<T>();
for (Interval<T> interval : values_) {
copy.values_.add(new Interval<T>(interval.getMinValue(), interval
.getMaxValue()));
}
return copy;
}
/**
* {@inheritDoc}
*/
@Override
public T getFirstValue() throws EmptyDomainException {
return getMinValue();
}
/**
* Returns the maximum value of the domain.
* @return The upper bound of the domain
* @throws EmptyDomainException
* Attempt to get a value from an empty domain
*/
public T getMaxValue() throws EmptyDomainException {
if (isEmpty()) {
throw new EmptyDomainException();
}
return values_.last().getMaxValue();
}
/**
* Returns the minimum value of the domain.
* @return The lower bound of the domain
* @throws EmptyDomainException
* Attempt to get a value from an empty domain
*/
public T getMinValue() throws EmptyDomainException {
if (isEmpty()) {
throw new EmptyDomainException();
}
return values_.first().getMinValue();
}
/**
* {@inheritDoc}
*/
@Override
public int getSize() {
// Domain size
int size = 0;
// Iterate on intervals
for (Interval<T> interval : values_) {
size = size + interval.getSize();
}
return size;
}
/**
* {@inheritDoc}
*/
@Override
public T getValue() throws UnboundDomainException {
if (!hasSingleValue()) {
throw new UnboundDomainException();
}
return getMinValue();
}
/**
* Get the values of the domain.
* @return Values of the domain
*/
protected TreeSet<Interval<T>> getValues() {
return values_;
}
/**
* {@inheritDoc}
*/
@Override
public boolean hasSingleValue() {
return getSize() == 1;
}
/**
* {@inheritDoc}
*/
@Override
public boolean isEmpty() {
return getSize() == 0;
}
/**
* {@inheritDoc}
*/
@Override
public boolean isInDomain(final Value<T> value) {
// Local variables
boolean inDomain = false;
final Iterator<Interval<T>> index = values_.iterator();
// Check intervals
while (index.hasNext() && !inDomain) {
inDomain = index.next().isInInterval(value.value());
}
return inDomain;
}
/**
* {@inheritDoc}
*/
@Override
public Iterator<T> iterator() {
return new IntervalDomainIterator<T>(this);
}
/**
* {@inheritDoc}
*/
@Override
public boolean reduceToDomainIntersection(final Domain<T> other) {
// Local variables
boolean domainChanged = false;
if (other.isEmpty()) {
// The domain becomes empty
domainChanged = !isEmpty();
values_.clear();
} else if (other instanceof IntervalDomain) {
// Specific interval domain reduction
domainChanged = reduceToDomainIntersection((IntervalDomain<T>) other);
} else {
// Prune successively the values
final Iterator<T> values = other.iterator();
while (values.hasNext()) {
domainChanged = removeValue(values.next()) || domainChanged;
}
}
return domainChanged;
}
/**
* Reduce the current domain with the values of the other interval domain.
* @param other
* Other domain to intersect with
* @return "true" if a reduction of the domain has been performed
*/
private boolean reduceToDomainIntersection(final IntervalDomain<T> other) {
// Local variables
boolean domainChanged = false;
// Intervals of values and gaps
final Iterator<Interval<T>> index = other.values_.iterator();
T gapMin = index.next().getMaxValue().nextValue();
T gapMax;
// Reduce the variable min
domainChanged = reduceWithMinValue(other.getMinValue());
// Reduce with the other domain gaps
while (index.hasNext()) {
final Interval<T> interval = index.next();
// Get a gap of the other domain
gapMax = interval.getMinValue().previousValue();
// Remove the gap
removeInterval(gapMin, gapMax);
// Prepare next gap
gapMin = interval.getMaxValue().nextValue();
}
// Reduce the variable max
domainChanged = reduceWithMaxValue(other.getMaxValue()) ||
domainChanged;
return domainChanged;
}
/**
* Reduces the domain with a new maximum value.
* @param value
* New maximum value of the domain
* @return True if the domain been reduced
*/
public boolean reduceWithMaxValue(final T value) {
// Local variables
boolean domainChanged = false;
boolean finished = false;
Iterator<Interval<T>> index = values_.descendingIterator();
while (index.hasNext() && !finished) {
final Interval<T> interval = index.next();
if (interval.getMinValue().compareTo(value) > 0) {
// The whole interval is removed
index.remove();
domainChanged = true;
index = values_.descendingIterator();
} else if (interval.getMaxValue().compareTo(value) > 0) {
// The current interval is reduced
interval.setMaxValue(value);
domainChanged = true;
// Reduction is over
finished = true;
} else {
// Reduction is over
finished = true;
}
}
return domainChanged;
}
/**
* Reduces the domain with a new minimum value.
* @param value
* New minimum value of the domain
* @return True if the domain has changed
*/
public boolean reduceWithMinValue(final T value) {
// Local variables
boolean domainChanged = false;
boolean finished = false;
Iterator<Interval<T>> index = values_.iterator();
while (index.hasNext() && !finished) {
final Interval<T> interval = index.next();
if (interval.getMaxValue().compareTo(value) < 0) {
// The whole interval is removed
values_.remove(interval);
domainChanged = true;
index = values_.iterator();
} else if (interval.getMinValue().compareTo(value) < 0) {
// The current interval is reduced
interval.setMinValue(value);
domainChanged = true;
// Reduction is over
finished = true;
} else {
// Reduction is over
finished = true;
}
}
return domainChanged;
}
/**
* Removes an interval of values of the domain.
* @param min
* Lower bound of the interval of values to remove
* @param max
* Upper bound of the interval of values to remove
* @return True if the domain has changed
*/
public boolean removeInterval(final T min, final T max) {
// Local variables
boolean domainChanged = false;
boolean finished = false;
final Iterator<Interval<T>> index = values_.iterator();
while (index.hasNext() && !finished) {
final Interval<T> interval = index.next();
if (interval.getMaxValue().compareTo(min) < 0) {
// Nothing is removed, next values interval
// to remove |----------|
// current |-------|
} else if (interval.getMinValue().compareTo(min) < 0) {
if (interval.getMaxValue().compareTo(max) <= 0) {
// to remove |--------------|
// current |------------|
interval.setMaxValue(min.previousValue());
if (interval.isEmpty()) {
// The current interval is now empty
index.remove();
}
} else {
// to remove |----------|
// current |-------------------|
final Interval<T> newInterval = new Interval<T>(
max.nextValue(), interval.getMaxValue());
interval.setMaxValue(min.previousValue());
values_.add(newInterval);
finished = true;
}
// Domain changed
domainChanged = true;
} else if (interval.getMinValue().compareTo(min) >= 0 &&
interval.getMinValue().compareTo(max) <= 0) {
if (interval.getMaxValue().compareTo(max) <= 0) {
// to remove |----------------|
// current |----------|
index.remove();
} else {
// to remove |----------------|
// current |-------------------|
interval.setMinValue(max.nextValue());
finished = true;
}
// Domain changed
domainChanged = true;
} else {
// Nothing more to be removed
// to remove |------------|
// current |--------|
finished = true;
}
}
return domainChanged;
}
/**
* {@inheritDoc}
*/
@Override
public boolean removeValue(final Value<T> value) {
// Local variables
boolean domainChanged = false;
final Iterator<Interval<T>> index = values_.iterator();
Interval<T> interval = null;
// Search the first interval having a max value greater or equal to the
// value to remove
while ((index.hasNext()) && interval == null) {
interval = index.next();
if (interval.getMaxValue().compareTo(value.value()) < 0) {
interval = null;
}
}
if (interval != null && interval.isInInterval(value.value())) {
if (interval.getSize() == 1) {
// The interval has only one element : it becomes empty
values_.remove(interval);
} else if (interval.getMinValue().equals(value)) {
// The removed value is at the beginning of the interval
interval.setMinValue(value.nextValue());
} else if (interval.getMaxValue().equals(value)) {
// The removed value is at the end of the interval
interval.setMaxValue(value.previousValue());
} else {
// The removed value is in the middle of the interval
final Interval<T> newInterval = new Interval<T>(
interval.getMinValue(), value.previousValue());
interval.setMinValue(value.nextValue());
values_.add(newInterval);
}
domainChanged = true;
}
return domainChanged;
}
/**
* Changes the upper bound of the domain. The domain can be extended or
* reduced.
* @param value
* New maximum of the domain
*/
public void setMaxValue(final T value) {
if (isEmpty()) {
// When the domain is empty, a new max value means that all the
// values
// less than the parameter are allowed.
final Interval<T> interval = new Interval<T>(value.minValue(),
value);
values_.add(interval);
} else if (getMaxValue().compareTo(value) <= 0) {
// The domain is extended
values_.last().setMaxValue(value);
} else {
// The domain is reduced
reduceWithMaxValue(value);
}
}
/**
* Changes the lower bound of the domain. The domain can be extended or
* reduced.
* @param value
* New minimum of the domain
*/
public void setMinValue(final T value) {
if (isEmpty()) {
// When the domain is empty, a new min value means that all the
// values greater than the parameter are allowed.
final Interval<T> interval = new Interval<T>(value,
value.maxValue());
values_.add(interval);
} else if (getMinValue().compareTo(value) >= 0) {
// The domain is extended
values_.first().setMinValue(value);
} else {
// The domain is reduced
reduceWithMinValue(value);
}
}
/**
* {@inheritDoc}
*/
@Override
public boolean setValue(final Value<T> value) {
final boolean domainChanged = !hasSingleValue() || getValue() != value;
// Only one interval is defined
values_.clear();
values_.add(new Interval<T>(value.value(), value.value()));
return domainChanged;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
// Display intervals
final StringBuilder builder = new StringBuilder();
final Iterator<Interval<T>> intervals = values_.iterator();
while (intervals.hasNext()) {
// Display one interval
builder.append(intervals.next());
// Display a union symbol if there is another interval
if (intervals.hasNext()) {
builder.append("U");
}
}
return builder.toString();
}
};