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