IntervalDomain.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;

  18. import java.util.Iterator;
  19. import java.util.TreeSet;

  20. /**
  21.  * Represents a non continuous interval of integer values. The size of the
  22.  * domain is is the number of included values.
  23.  */
  24. public class IntervalDomain<T extends Value<T>> implements Domain<T> {

  25.     /**
  26.      * Intervals of the domain.
  27.      */
  28.     private TreeSet<Interval<T>> values_;

  29.     /**
  30.      * Default constructor.
  31.      */
  32.     protected IntervalDomain() {
  33.         values_ = new TreeSet<Interval<T>>();
  34.     }

  35.     /**
  36.      * Usual constructor.
  37.      * @param min
  38.      *            Lower bound of the domain
  39.      * @param max
  40.      *            Upper bound of the domain
  41.      */
  42.     public IntervalDomain(final T min, final T max) {
  43.         values_ = new TreeSet<Interval<T>>();
  44.         values_.add(new Interval<T>(min, max));
  45.     }

  46.     /**
  47.      * {@inheritDoc}
  48.      */
  49.     @Override
  50.     public boolean contains(final Value<T> value) {

  51.         // Result
  52.         boolean contains = false;
  53.         // Intervals of the domain
  54.         final Iterator<Interval<T>> intervals = values_.iterator();
  55.         while (intervals.hasNext() && !contains) {
  56.             contains = intervals.next().isInInterval(value.value());
  57.         }
  58.         return contains;
  59.     }

  60.     /**
  61.      * {@inheritDoc}
  62.      */
  63.     @Override
  64.     public Domain<T> copy() {
  65.         final IntervalDomain<T> copy = new IntervalDomain<T>();
  66.         for (Interval<T> interval : values_) {
  67.             copy.values_.add(new Interval<T>(interval.getMinValue(), interval
  68.                     .getMaxValue()));
  69.         }
  70.         return copy;
  71.     }

  72.     /**
  73.      * {@inheritDoc}
  74.      */
  75.     @Override
  76.     public T getFirstValue() throws EmptyDomainException {
  77.         return getMinValue();
  78.     }

  79.     /**
  80.      * Returns the maximum value of the domain.
  81.      * @return The upper bound of the domain
  82.      * @throws EmptyDomainException
  83.      *             Attempt to get a value from an empty domain
  84.      */
  85.     public T getMaxValue() throws EmptyDomainException {
  86.         if (isEmpty()) {
  87.             throw new EmptyDomainException();
  88.         }
  89.         return values_.last().getMaxValue();
  90.     }

  91.     /**
  92.      * Returns the minimum value of the domain.
  93.      * @return The lower bound of the domain
  94.      * @throws EmptyDomainException
  95.      *             Attempt to get a value from an empty domain
  96.      */
  97.     public T getMinValue() throws EmptyDomainException {
  98.         if (isEmpty()) {
  99.             throw new EmptyDomainException();
  100.         }
  101.         return values_.first().getMinValue();
  102.     }

  103.     /**
  104.      * {@inheritDoc}
  105.      */
  106.     @Override
  107.     public int getSize() {
  108.         // Domain size
  109.         int size = 0;

  110.         // Iterate on intervals
  111.         for (Interval<T> interval : values_) {
  112.             size = size + interval.getSize();
  113.         }

  114.         return size;
  115.     }

  116.     /**
  117.      * {@inheritDoc}
  118.      */
  119.     @Override
  120.     public T getValue() throws UnboundDomainException {
  121.         if (!hasSingleValue()) {
  122.             throw new UnboundDomainException();
  123.         }
  124.         return getMinValue();
  125.     }

  126.     /**
  127.      * Get the values of the domain.
  128.      * @return Values of the domain
  129.      */
  130.     protected TreeSet<Interval<T>> getValues() {
  131.         return values_;
  132.     }

  133.     /**
  134.      * {@inheritDoc}
  135.      */
  136.     @Override
  137.     public boolean hasSingleValue() {
  138.         return getSize() == 1;
  139.     }

  140.     /**
  141.      * {@inheritDoc}
  142.      */
  143.     @Override
  144.     public boolean isEmpty() {
  145.         return getSize() == 0;
  146.     }

  147.     /**
  148.      * {@inheritDoc}
  149.      */
  150.     @Override
  151.     public boolean isInDomain(final Value<T> value) {
  152.         // Local variables
  153.         boolean inDomain = false;
  154.         final Iterator<Interval<T>> index = values_.iterator();

  155.         // Check intervals
  156.         while (index.hasNext() && !inDomain) {
  157.             inDomain = index.next().isInInterval(value.value());
  158.         }

  159.         return inDomain;
  160.     }

  161.     /**
  162.      * {@inheritDoc}
  163.      */
  164.     @Override
  165.     public Iterator<T> iterator() {
  166.         return new IntervalDomainIterator<T>(this);
  167.     }

  168.     /**
  169.      * {@inheritDoc}
  170.      */
  171.     @Override
  172.     public boolean reduceToDomainIntersection(final Domain<T> other) {

  173.         // Local variables
  174.         boolean domainChanged = false;

  175.         if (other.isEmpty()) {

  176.             // The domain becomes empty
  177.             domainChanged = !isEmpty();
  178.             values_.clear();

  179.         } else if (other instanceof IntervalDomain) {

  180.             // Specific interval domain reduction
  181.             domainChanged = reduceToDomainIntersection((IntervalDomain<T>) other);

  182.         } else {

  183.             // Prune successively the values
  184.             final Iterator<T> values = other.iterator();
  185.             while (values.hasNext()) {
  186.                 domainChanged = removeValue(values.next()) || domainChanged;
  187.             }
  188.         }

  189.         return domainChanged;
  190.     }

  191.     /**
  192.      * Reduce the current domain with the values of the other interval domain.
  193.      * @param other
  194.      *            Other domain to intersect with
  195.      * @return "true" if a reduction of the domain has been performed
  196.      */
  197.     private boolean reduceToDomainIntersection(final IntervalDomain<T> other) {
  198.         // Local variables
  199.         boolean domainChanged = false;

  200.         // Intervals of values and gaps
  201.         final Iterator<Interval<T>> index = other.values_.iterator();
  202.         T gapMin = index.next().getMaxValue().nextValue();
  203.         T gapMax;

  204.         // Reduce the variable min
  205.         domainChanged = reduceWithMinValue(other.getMinValue());

  206.         // Reduce with the other domain gaps
  207.         while (index.hasNext()) {

  208.             final Interval<T> interval = index.next();
  209.             // Get a gap of the other domain
  210.             gapMax = interval.getMinValue().previousValue();
  211.             // Remove the gap
  212.             removeInterval(gapMin, gapMax);
  213.             // Prepare next gap
  214.             gapMin = interval.getMaxValue().nextValue();
  215.         }

  216.         // Reduce the variable max
  217.         domainChanged = reduceWithMaxValue(other.getMaxValue()) ||
  218.                 domainChanged;

  219.         return domainChanged;
  220.     }

  221.     /**
  222.      * Reduces the domain with a new maximum value.
  223.      * @param value
  224.      *            New maximum value of the domain
  225.      * @return True if the domain been reduced
  226.      */
  227.     public boolean reduceWithMaxValue(final T value) {
  228.         // Local variables
  229.         boolean domainChanged = false;
  230.         boolean finished = false;
  231.         Iterator<Interval<T>> index = values_.descendingIterator();

  232.         while (index.hasNext() && !finished) {
  233.             final Interval<T> interval = index.next();
  234.             if (interval.getMinValue().compareTo(value) > 0) {
  235.                 // The whole interval is removed
  236.                 index.remove();
  237.                 domainChanged = true;
  238.                 index = values_.descendingIterator();
  239.             } else if (interval.getMaxValue().compareTo(value) > 0) {
  240.                 // The current interval is reduced
  241.                 interval.setMaxValue(value);
  242.                 domainChanged = true;
  243.                 // Reduction is over
  244.                 finished = true;
  245.             } else {
  246.                 // Reduction is over
  247.                 finished = true;
  248.             }
  249.         }

  250.         return domainChanged;
  251.     }

  252.     /**
  253.      * Reduces the domain with a new minimum value.
  254.      * @param value
  255.      *            New minimum value of the domain
  256.      * @return True if the domain has changed
  257.      */
  258.     public boolean reduceWithMinValue(final T value) {
  259.         // Local variables
  260.         boolean domainChanged = false;
  261.         boolean finished = false;
  262.         Iterator<Interval<T>> index = values_.iterator();

  263.         while (index.hasNext() && !finished) {
  264.             final Interval<T> interval = index.next();
  265.             if (interval.getMaxValue().compareTo(value) < 0) {
  266.                 // The whole interval is removed
  267.                 values_.remove(interval);
  268.                 domainChanged = true;
  269.                 index = values_.iterator();
  270.             } else if (interval.getMinValue().compareTo(value) < 0) {
  271.                 // The current interval is reduced
  272.                 interval.setMinValue(value);
  273.                 domainChanged = true;
  274.                 // Reduction is over
  275.                 finished = true;
  276.             } else {
  277.                 // Reduction is over
  278.                 finished = true;
  279.             }
  280.         }

  281.         return domainChanged;
  282.     }

  283.     /**
  284.      * Removes an interval of values of the domain.
  285.      * @param min
  286.      *            Lower bound of the interval of values to remove
  287.      * @param max
  288.      *            Upper bound of the interval of values to remove
  289.      * @return True if the domain has changed
  290.      */
  291.     public boolean removeInterval(final T min, final T max) {

  292.         // Local variables
  293.         boolean domainChanged = false;
  294.         boolean finished = false;
  295.         final Iterator<Interval<T>> index = values_.iterator();

  296.         while (index.hasNext() && !finished) {
  297.             final Interval<T> interval = index.next();
  298.             if (interval.getMaxValue().compareTo(min) < 0) {

  299.                 // Nothing is removed, next values interval
  300.                 // to remove |----------|
  301.                 // current |-------|

  302.             } else if (interval.getMinValue().compareTo(min) < 0) {
  303.                 if (interval.getMaxValue().compareTo(max) <= 0) {

  304.                     // to remove |--------------|
  305.                     // current |------------|
  306.                     interval.setMaxValue(min.previousValue());
  307.                     if (interval.isEmpty()) {
  308.                         // The current interval is now empty
  309.                         index.remove();
  310.                     }

  311.                 } else {

  312.                     // to remove |----------|
  313.                     // current |-------------------|
  314.                     final Interval<T> newInterval = new Interval<T>(
  315.                             max.nextValue(), interval.getMaxValue());
  316.                     interval.setMaxValue(min.previousValue());
  317.                     values_.add(newInterval);
  318.                     finished = true;

  319.                 }
  320.                 // Domain changed
  321.                 domainChanged = true;

  322.             } else if (interval.getMinValue().compareTo(min) >= 0 &&
  323.                     interval.getMinValue().compareTo(max) <= 0) {
  324.                 if (interval.getMaxValue().compareTo(max) <= 0) {

  325.                     // to remove |----------------|
  326.                     // current |----------|
  327.                     index.remove();

  328.                 } else {

  329.                     // to remove |----------------|
  330.                     // current |-------------------|
  331.                     interval.setMinValue(max.nextValue());
  332.                     finished = true;

  333.                 }
  334.                 // Domain changed
  335.                 domainChanged = true;
  336.             } else {

  337.                 // Nothing more to be removed
  338.                 // to remove |------------|
  339.                 // current |--------|
  340.                 finished = true;

  341.             }
  342.         }

  343.         return domainChanged;
  344.     }

  345.     /**
  346.      * {@inheritDoc}
  347.      */
  348.     @Override
  349.     public boolean removeValue(final Value<T> value) {

  350.         // Local variables
  351.         boolean domainChanged = false;
  352.         final Iterator<Interval<T>> index = values_.iterator();
  353.         Interval<T> interval = null;

  354.         // Search the first interval having a max value greater or equal to the
  355.         // value to remove
  356.         while ((index.hasNext()) && interval == null) {
  357.             interval = index.next();
  358.             if (interval.getMaxValue().compareTo(value.value()) < 0) {
  359.                 interval = null;
  360.             }
  361.         }

  362.         if (interval != null && interval.isInInterval(value.value())) {
  363.             if (interval.getSize() == 1) {
  364.                 // The interval has only one element : it becomes empty
  365.                 values_.remove(interval);
  366.             } else if (interval.getMinValue().equals(value)) {
  367.                 // The removed value is at the beginning of the interval
  368.                 interval.setMinValue(value.nextValue());
  369.             } else if (interval.getMaxValue().equals(value)) {
  370.                 // The removed value is at the end of the interval
  371.                 interval.setMaxValue(value.previousValue());
  372.             } else {
  373.                 // The removed value is in the middle of the interval
  374.                 final Interval<T> newInterval = new Interval<T>(
  375.                         interval.getMinValue(), value.previousValue());
  376.                 interval.setMinValue(value.nextValue());
  377.                 values_.add(newInterval);
  378.             }
  379.             domainChanged = true;
  380.         }

  381.         return domainChanged;
  382.     }

  383.     /**
  384.      * Changes the upper bound of the domain. The domain can be extended or
  385.      * reduced.
  386.      * @param value
  387.      *            New maximum of the domain
  388.      */
  389.     public void setMaxValue(final T value) {
  390.         if (isEmpty()) {
  391.             // When the domain is empty, a new max value means that all the
  392.             // values
  393.             // less than the parameter are allowed.
  394.             final Interval<T> interval = new Interval<T>(value.minValue(),
  395.                     value);
  396.             values_.add(interval);
  397.         } else if (getMaxValue().compareTo(value) <= 0) {
  398.             // The domain is extended
  399.             values_.last().setMaxValue(value);
  400.         } else {
  401.             // The domain is reduced
  402.             reduceWithMaxValue(value);
  403.         }
  404.     }

  405.     /**
  406.      * Changes the lower bound of the domain. The domain can be extended or
  407.      * reduced.
  408.      * @param value
  409.      *            New minimum of the domain
  410.      */
  411.     public void setMinValue(final T value) {
  412.         if (isEmpty()) {
  413.             // When the domain is empty, a new min value means that all the
  414.             // values greater than the parameter are allowed.
  415.             final Interval<T> interval = new Interval<T>(value,
  416.                     value.maxValue());
  417.             values_.add(interval);
  418.         } else if (getMinValue().compareTo(value) >= 0) {
  419.             // The domain is extended
  420.             values_.first().setMinValue(value);
  421.         } else {
  422.             // The domain is reduced
  423.             reduceWithMinValue(value);
  424.         }
  425.     }

  426.     /**
  427.      * {@inheritDoc}
  428.      */
  429.     @Override
  430.     public boolean setValue(final Value<T> value) {
  431.         final boolean domainChanged = !hasSingleValue() || getValue() != value;
  432.         // Only one interval is defined
  433.         values_.clear();
  434.         values_.add(new Interval<T>(value.value(), value.value()));

  435.         return domainChanged;
  436.     }

  437.     /**
  438.      * {@inheritDoc}
  439.      */
  440.     @Override
  441.     public String toString() {

  442.         // Display intervals
  443.         final StringBuilder builder = new StringBuilder();
  444.         final Iterator<Interval<T>> intervals = values_.iterator();

  445.         while (intervals.hasNext()) {

  446.             // Display one interval
  447.             builder.append(intervals.next());

  448.             // Display a union symbol if there is another interval
  449.             if (intervals.hasNext()) {
  450.                 builder.append("U");
  451.             }
  452.         }

  453.         return builder.toString();
  454.     }

  455. };