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