    001package org.cpsolver.ifs.example.rpp;
    002
    003import java.util.Set;
    004
    005import org.cpsolver.ifs.assignment.Assignment;
    006import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
    007import org.cpsolver.ifs.assignment.context.ConstraintWithContext;
    008
    009
    010/**
    011 * Resource constraint (rectangular area where the rectangles are to be placed).
    012 * It prohibits overlapping of the placed rectangles.
    013 *
    014 * @author  Tomáš Müller
    015 * @version IFS 1.3 (Iterative Forward Search)<br>
    016 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    017 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    018 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    019 * <br>
    020 *          This library is free software; you can redistribute it and/or modify
    021 *          it under the terms of the GNU Lesser General Public License as
    022 *          published by the Free Software Foundation; either version 3 of the
    023 *          License, or (at your option) any later version. <br>
    024 * <br>
    025 *          This library is distributed in the hope that it will be useful, but
    026 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    027 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    028 *          Lesser General Public License for more details. <br>
    029 * <br>
    030 *          You should have received a copy of the GNU Lesser General Public
    031 *          License along with this library; if not see
    032 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    033 */
    034public class ResourceConstraint extends ConstraintWithContext<Rectangle, Location, ResourceConstraint.Context> {
    035    private static org.apache.logging.log4j.Logger sLogger = org.apache.logging.log4j.LogManager.getLogger(ResourceConstraint.class);
    036    private int iWidth, iHeight;
    037
    038    /**
    039     * Constructor.
    040     *
    041     * @param width
    042     *            area width
    043     * @param height
    044     *            area height
    045     */
    046    public ResourceConstraint(int width, int height) {
    047        super();
    048        iWidth = width;
    049        iHeight = height;
    050    }
    051
    052    /**
    053     * Compute conflicts with the given placement of the rectangle. This means
    054     * the rectangles which are already placed and which are overlapping with
    055     * the given assignment.
    056     */
    057    @Override
    058    public void computeConflicts(Assignment<Rectangle, Location> assignment, Location placement, Set<Location> conflicts) {
    059        Rectangle rectangle = placement.variable();
    060        Context context = getContext(assignment);
    061        for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
    062            for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++)
    063                if (context.getRectangle(x, y) != null)
    064                    conflicts.add(context.getRectangle(x, y).getAssignment(assignment));
    065    }
    066
    067    /**
    068     * Returns true if there is a rectangle which overlaps with the given
    069     * assignment.
    070     */
    071    @Override
    072    public boolean inConflict(Assignment<Rectangle, Location> assignment, Location placement) {
    073        Rectangle rectangle = placement.variable();
    074        Context context = getContext(assignment);
    075        for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
    076            for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++)
    077                if (context.getRectangle(x, y) != null)
    078                    return true;
    079        return false;
    080    }
    081
    082    /**
    083     * Returns true if the given rectangles (assignments) do not overlap.
    084     */
    085    @Override
    086    public boolean isConsistent(Location p1, Location p2) {
    087        Rectangle r1 = p1.variable();
    088        Rectangle r2 = p2.variable();
    089        if (p2.getX() + r2.getWidth() <= p1.getX())
    090            return true;
    091        if (p2.getX() >= p1.getX() + r1.getWidth())
    092            return true;
    093        if (p2.getY() + r2.getHeight() <= p1.getY())
    094            return true;
    095        if (p2.getY() >= p1.getY() + r1.getHeight())
    096            return true;
    097        return false;
    098    }
    099
    100    public void check(Assignment<Rectangle, Location> assignment) {
    101        sLogger.debug("check");
    102        Context context = getContext(assignment);
    103        for (Rectangle rectangle : variables()) {
    104            Location placement = assignment.getValue(rectangle);
    105            if (placement == null) {
    106                sLogger.warn("Rectangle " + rectangle.getName() + " is not assigned.");
    107                continue;
    108            }
    109            sLogger.debug("Checking " + rectangle.getName() + "    (assigned:" + placement.getName() + ", prohibited:"
    110                    + rectangle.isProhibited(placement.getX(), placement.getY()) + ", initial:"
    111                    + rectangle.getInitialAssignment() + ", prohibited:[" + rectangle.getProhibitedX() + ","
    112                    + rectangle.getProhibitedY() + "])");
    113            if (placement.getX() == rectangle.getProhibitedX() || placement.getY() == rectangle.getProhibitedY())
    114                sLogger.error("Placement is prohibited.");
    115            if (placement.getX() < rectangle.getMinX() || placement.getX() > rectangle.getMaxX()
    116                    || placement.getY() < rectangle.getMinY() || placement.getY() > rectangle.getMaxY())
    117                sLogger.error("Placement is outside bounds.");
    118            for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
    119                for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++) {
    120                    if (context.getRectangle(x, y) == null || !context.getRectangle(x, y).equals(rectangle))
    121                        sLogger.error("Problem at [" + x + "," + y + "], " + context.getRectangle(x, y) + " is assigned there.");
    122                }
    123        }
    124        sLogger.debug(toString());
    125    }
    126
    127    /**
    128     * String representation of the constraint (for debugging and printing
    129     * purposes).
    130     */
    131    @Override
    132    public String toString() {
    133        return "ResourceConstraint{" + iWidth + "x" + iHeight + "}";
    134    }
    135
    136    @Override
    137    public Context createAssignmentContext(Assignment<Rectangle, Location> assignment) {
    138        return new Context(assignment);
    139    }
    140
    141    /**
    142     * Assignment context
    143     */
    144    public class Context implements AssignmentConstraintContext<Rectangle, Location> {
    145        private Rectangle[][] iResource;
    146
    147        public Context(Assignment<Rectangle, Location> assignment) {
    148            iResource = new Rectangle[iWidth][iHeight];
    149            for (int x = 0; x < iWidth; x++)
    150                for (int y = 0; y < iHeight; y++)
    151                    iResource[x][y] = null;
    152            for (Location location: assignment.assignedValues())
    153                assigned(assignment, location);
    154        }
    155
    156        /**
    157         * Notification, when a rectangle is placed. It memorizes the rectangle's
    158         * new position in 2D ([0..width][0..height]) array. It is used for faster
    159         * lookup when computing conflicts.
    160         */
    161        @Override
    162        public void assigned(Assignment<Rectangle, Location> assignment, Location placement) {
    163            Rectangle rectangle = placement.variable();
    164            for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
    165                for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++) {
    166                    iResource[x][y] = rectangle;
    167                }
    168        }
    169
    170        public Rectangle getRectangle(int x, int y) {
    171            return iResource[x][y];
    172        }
    173
    174        /**
    175         * Notification, when a rectangle is unplaced. It removes the rectangle from
    176         * the 2D ([0..width][0..height]) array.
    177         */
    178        @Override
    179        public void unassigned(Assignment<Rectangle, Location> assignment, Location placement) {
    180            Rectangle rectangle = placement.variable();
    181            for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
    182                for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++) {
    183                    iResource[x][y] = null;
    184                }
    185        }
    186
    187    }
    188}