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