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}