001 package net.sf.cpsolver.ifs.example.rpp;
002
003 import java.util.Set;
004
005 import net.sf.cpsolver.ifs.model.Constraint;
006 import 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 Tomas Muller<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 */
031 public 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 }