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;

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

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

  28.     /**
  29.      * Intervals of the domain.
  30.      */
  31.     private TreeSet<Interval<T>> values_;

  33.     /**
  34.      * Default constructor.
  35.      */
  36.     protected IntervalDomain() {
  37.         values_ = new TreeSet<Interval<T>>();
  38.     }

  40.     /**
  41.      * Usual constructor.
  42.      * @param min
  43.      *            Lower bound of the domain
  44.      * @param max
  45.      *            Upper bound of the domain
  46.      */
  47.     public IntervalDomain(final T min, final T max) {
  48.         values_ = new TreeSet<Interval<T>>();
  49.         values_.add(new Interval<T>(min, max));
  50.     }

  52.     /**
  53.      * {@inheritDoc}
  54.      */
  55.     @Override
  56.     public boolean contains(final Value<T> value) {

  58.         // Result
  59.         boolean contains = false;
  60.         // Intervals of the domain
  61.         final Iterator<Interval<T>> intervals = values_.iterator();
  62.         while (intervals.hasNext() && !contains) {
  63.             contains = intervals.next().isInInterval(value.value());
  64.         }
  65.         return contains;
  66.     }

  68.     /**
  69.      * {@inheritDoc}
  70.      */
  71.     @Override
  72.     public Domain<T> copy() {
  73.         final IntervalDomain<T> copy = new IntervalDomain<T>();
  74.         for (Interval<T> interval : values_) {
  75.             copy.values_.add(new Interval<T>(interval.getMinValue(), interval
  76.                     .getMaxValue()));
  77.         }
  78.         return copy;
  79.     }

  81.     /**
  82.      * {@inheritDoc}
  83.      */
  84.     @Override
  85.     public T getFirstValue() throws EmptyDomainException {
  86.         return getMinValue();
  87.     }

  89.     /**
  90.      * Returns the maximum value of the domain.
  91.      * @return The upper bound of the domain
  92.      * @throws EmptyDomainException
  93.      *             Attempt to get a value from an empty domain
  94.      */
  95.     public T getMaxValue() throws EmptyDomainException {
  96.         if (isEmpty()) {
  97.             throw new EmptyDomainException();
  98.         }
  99.         return values_.last().getMaxValue();
  100.     }

  102.     /**
  103.      * Returns the minimum value of the domain.
  104.      * @return The lower bound of the domain
  105.      * @throws EmptyDomainException
  106.      *             Attempt to get a value from an empty domain
  107.      */
  108.     public T getMinValue() throws EmptyDomainException {
  109.         if (isEmpty()) {
  110.             throw new EmptyDomainException();
  111.         }
  112.         return values_.first().getMinValue();
  113.     }

  115.     /**
  116.      * {@inheritDoc}
  117.      */
  118.     @Override
  119.     public int getSize() {
  120.         // Domain size
  121.         int size = 0;

  123.         // Iterate on intervals
  124.         for (Interval<T> interval : values_) {
  125.             size = size + interval.getSize();
  126.         }

  128.         return size;
  129.     }

  131.     /**
  132.      * {@inheritDoc}
  133.      */
  134.     @Override
  135.     public T getValue() throws UnboundDomainException {
  136.         if (!hasSingleValue()) {
  137.             throw new UnboundDomainException();
  138.         }
  139.         return getMinValue();
  140.     }

  142.     /**
  143.      * Get the values of the domain.
  144.      * @return Values of the domain
  145.      */
  146.     protected TreeSet<Interval<T>> getValues() {
  147.         return values_;
  148.     }

  150.     /**
  151.      * {@inheritDoc}
  152.      */
  153.     @Override
  154.     public boolean hasSingleValue() {
  155.         return getSize() == 1;
  156.     }

  158.     /**
  159.      * {@inheritDoc}
  160.      */
  161.     @Override
  162.     public boolean isEmpty() {
  163.         return getSize() == 0;
  164.     }

  166.     /**
  167.      * {@inheritDoc}
  168.      */
  169.     @Override
  170.     public boolean isInDomain(final Value<T> value) {
  171.         // Local variables
  172.         boolean inDomain = false;
  173.         final Iterator<Interval<T>> index = values_.iterator();

  175.         // Check intervals
  176.         while (index.hasNext() && !inDomain) {
  177.             inDomain = index.next().isInInterval(value.value());
  178.         }

  180.         return inDomain;
  181.     }

  183.     /**
  184.      * {@inheritDoc}
  185.      */
  186.     @Override
  187.     public Iterator<T> iterator() {
  188.         return new IntervalDomainIterator<T>(this);
  189.     }

  191.     /**
  192.      * {@inheritDoc}
  193.      */
  194.     @Override
  195.     public boolean reduceToDomainIntersection(final Domain<T> other) {

  197.         // Local variables
  198.         boolean domainChanged = false;

  200.         if (other.isEmpty()) {

  202.             // The domain becomes empty
  203.             domainChanged = !isEmpty();
  204.             values_.clear();

  206.         } else if (other instanceof IntervalDomain) {

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

  211.         } else {

  213.             // Prune successively the values
  214.             final Iterator<T> values = other.iterator();
  215.             while (values.hasNext()) {
  216.                 domainChanged = removeValue(values.next()) || domainChanged;
  217.             }
  218.         }

  220.         return domainChanged;
  221.     }

  223.     /**
  224.      * Reduce the current domain with the values of the other interval domain.
  225.      * @param other
  226.      *            Other domain to intersect with
  227.      * @return "true" if a reduction of the domain has been performed
  228.      */
  229.     private boolean reduceToDomainIntersection(final IntervalDomain<T> other) {
  230.         // Local variables
  231.         boolean domainChanged = false;

  233.         // Intervals of values and gaps
  234.         final Iterator<Interval<T>> index = other.values_.iterator();
  235.         T gapMin = index.next().getMaxValue().nextValue();
  236.         T gapMax;

  238.         // Reduce the variable min
  239.         domainChanged = reduceWithMinValue(other.getMinValue());

  241.         // Reduce with the other domain gaps
  242.         while (index.hasNext()) {

  244.             final Interval<T> interval = index.next();
  245.             // Get a gap of the other domain
  246.             gapMax = interval.getMinValue().previousValue();
  247.             // Remove the gap
  248.             removeInterval(gapMin, gapMax);
  249.             // Prepare next gap
  250.             gapMin = interval.getMaxValue().nextValue();
  251.         }

  253.         // Reduce the variable max
  254.         domainChanged = reduceWithMaxValue(other.getMaxValue()) ||
  255.                 domainChanged;

  257.         return domainChanged;
  258.     }

  260.     /**
  261.      * Reduces the domain with a new maximum value.
  262.      * @param value
  263.      *            New maximum value of the domain
  264.      * @return True if the domain been reduced
  265.      */
  266.     public boolean reduceWithMaxValue(final T value) {
  267.         // Local variables
  268.         boolean domainChanged = false;
  269.         boolean finished = false;
  270.         Iterator<Interval<T>> index = values_.descendingIterator();

  272.         while (index.hasNext() && !finished) {
  273.             final Interval<T> interval = index.next();
  274.             if (interval.getMinValue().compareTo(value) > 0) {
  275.                 // The whole interval is removed
  276.                 index.remove();
  277.                 domainChanged = true;
  278.                 index = values_.descendingIterator();
  279.             } else if (interval.getMaxValue().compareTo(value) > 0) {
  280.                 // The current interval is reduced
  281.                 interval.setMaxValue(value);
  282.                 domainChanged = true;
  283.                 // Reduction is over
  284.                 finished = true;
  285.             } else {
  286.                 // Reduction is over
  287.                 finished = true;
  288.             }
  289.         }

  291.         return domainChanged;
  292.     }

  294.     /**
  295.      * Reduces the domain with a new minimum value.
  296.      * @param value
  297.      *            New minimum value of the domain
  298.      * @return True if the domain has changed
  299.      */
  300.     public boolean reduceWithMinValue(final T value) {
  301.         // Local variables
  302.         boolean domainChanged = false;
  303.         boolean finished = false;
  304.         Iterator<Interval<T>> index = values_.iterator();

  306.         while (index.hasNext() && !finished) {
  307.             final Interval<T> interval = index.next();
  308.             if (interval.getMaxValue().compareTo(value) < 0) {
  309.                 // The whole interval is removed
  310.                 values_.remove(interval);
  311.                 domainChanged = true;
  312.                 index = values_.iterator();
  313.             } else if (interval.getMinValue().compareTo(value) < 0) {
  314.                 // The current interval is reduced
  315.                 interval.setMinValue(value);
  316.                 domainChanged = true;
  317.                 // Reduction is over
  318.                 finished = true;
  319.             } else {
  320.                 // Reduction is over
  321.                 finished = true;
  322.             }
  323.         }

  325.         return domainChanged;
  326.     }

  328.     /**
  329.      * Removes an interval of values of the domain.
  330.      * @param min
  331.      *            Lower bound of the interval of values to remove
  332.      * @param max
  333.      *            Upper bound of the interval of values to remove
  334.      * @return True if the domain has changed
  335.      */
  336.     public boolean removeInterval(final T min, final T max) {

  338.         // Local variables
  339.         boolean domainChanged = false;
  340.         boolean finished = false;
  341.         final Iterator<Interval<T>> index = values_.iterator();

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

  347.                 // Nothing is removed, next values interval
  348.                 // to remove |----------|
  349.                 // current |-------|

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

  354.                     // to remove |--------------|
  355.                     // current |------------|
  356.                     interval.setMaxValue(min.previousValue());
  357.                     if (interval.isEmpty()) {
  358.                         // The current interval is now empty
  359.                         index.remove();
  360.                     }

  362.                 } else {

  364.                     // to remove |----------|
  365.                     // current |-------------------|
  366.                     final Interval<T> newInterval = new Interval<T>(
  367.                             max.nextValue(), interval.getMaxValue());
  368.                     interval.setMaxValue(min.previousValue());
  369.                     values_.add(newInterval);
  370.                     finished = true;

  372.                 }
  373.                 // Domain changed
  374.                 domainChanged = true;

  376.             } else if (interval.getMinValue().compareTo(min) >= 0 &&
  377.                     interval.getMinValue().compareTo(max) <= 0) {
  378.                 if (interval.getMaxValue().compareTo(max) <= 0) {

  380.                     // to remove |----------------|
  381.                     // current |----------|
  382.                     index.remove();

  384.                 } else {

  386.                     // to remove |----------------|
  387.                     // current |-------------------|
  388.                     interval.setMinValue(max.nextValue());
  389.                     finished = true;

  391.                 }
  392.                 // Domain changed
  393.                 domainChanged = true;
  394.             } else {

  396.                 // Nothing more to be removed
  397.                 // to remove |------------|
  398.                 // current |--------|
  399.                 finished = true;

  401.             }
  402.         }

  404.         return domainChanged;
  405.     }

  407.     /**
  408.      * {@inheritDoc}
  409.      */
  410.     @Override
  411.     public boolean removeValue(final Value<T> value) {

  413.         // Local variables
  414.         boolean domainChanged = false;
  415.         final Iterator<Interval<T>> index = values_.iterator();
  416.         Interval<T> interval = null;

  418.         // Search the first interval having a max value greater or equal to the
  419.         // value to remove
  420.         while ((index.hasNext()) && interval == null) {
  421.             interval = index.next();
  422.             if (interval.getMaxValue().compareTo(value.value()) < 0) {
  423.                 interval = null;
  424.             }
  425.         }

  427.         if (interval != null && interval.isInInterval(value.value())) {
  428.             if (interval.getSize() == 1) {
  429.                 // The interval has only one element : it becomes empty
  430.                 values_.remove(interval);
  431.             } else if (interval.getMinValue().equals(value)) {
  432.                 // The removed value is at the beginning of the interval
  433.                 interval.setMinValue(value.nextValue());
  434.             } else if (interval.getMaxValue().equals(value)) {
  435.                 // The removed value is at the end of the interval
  436.                 interval.setMaxValue(value.previousValue());
  437.             } else {
  438.                 // The removed value is in the middle of the interval
  439.                 final Interval<T> newInterval = new Interval<T>(
  440.                         interval.getMinValue(), value.previousValue());
  441.                 interval.setMinValue(value.nextValue());
  442.                 values_.add(newInterval);
  443.             }
  444.             domainChanged = true;
  445.         }

  447.         return domainChanged;
  448.     }

  450.     /**
  451.      * Changes the upper bound of the domain. The domain can be extended or
  452.      * reduced.
  453.      * @param value
  454.      *            New maximum of the domain
  455.      */
  456.     public void setMaxValue(final T value) {
  457.         if (isEmpty()) {
  458.             // When the domain is empty, a new max value means that all the
  459.             // values
  460.             // less than the parameter are allowed.
  461.             final Interval<T> interval = new Interval<T>(value.minValue(),
  462.                     value);
  463.             values_.add(interval);
  464.         } else if (getMaxValue().compareTo(value) <= 0) {
  465.             // The domain is extended
  466.             values_.last().setMaxValue(value);
  467.         } else {
  468.             // The domain is reduced
  469.             reduceWithMaxValue(value);
  470.         }
  471.     }

  473.     /**
  474.      * Changes the lower bound of the domain. The domain can be extended or
  475.      * reduced.
  476.      * @param value
  477.      *            New minimum of the domain
  478.      */
  479.     public void setMinValue(final T value) {
  480.         if (isEmpty()) {
  481.             // When the domain is empty, a new min value means that all the
  482.             // values greater than the parameter are allowed.
  483.             final Interval<T> interval = new Interval<T>(value,
  484.                     value.maxValue());
  485.             values_.add(interval);
  486.         } else if (getMinValue().compareTo(value) >= 0) {
  487.             // The domain is extended
  488.             values_.first().setMinValue(value);
  489.         } else {
  490.             // The domain is reduced
  491.             reduceWithMinValue(value);
  492.         }
  493.     }

  495.     /**
  496.      * {@inheritDoc}
  497.      */
  498.     @Override
  499.     public boolean setValue(final Value<T> value) {
  500.         final boolean domainChanged = !hasSingleValue() || getValue() != value;
  501.         // Only one interval is defined
  502.         values_.clear();
  503.         values_.add(new Interval<T>(value.value(), value.value()));

  505.         return domainChanged;
  506.     }

  508.     /**
  509.      * {@inheritDoc}
  510.      */
  511.     @Override
  512.     public String toString() {

  514.         // Display intervals
  515.         final StringBuilder builder = new StringBuilder();
  516.         final Iterator<Interval<T>> intervals = values_.iterator();

  518.         while (intervals.hasNext()) {

  520.             // Display one interval
  521.             builder.append(intervals.next());

  523.             // Display a union symbol if there is another interval
  524.             if (intervals.hasNext()) {
  525.                 builder.append("U");
  526.             }
  527.         }

  529.         return builder.toString();
  530.     }

  532. };
Created with JaCoCo 0.7.4.201502262128