001 package net.sf.cpsolver.ifs.example.rpp;
002
003 import java.util.*;
004
005 import net.sf.cpsolver.ifs.model.*;
006 import net.sf.cpsolver.ifs.util.*;
007
008 /**
009 * Resource constraint (rectangular area where the rectangles are to be placed). It prohibits overlapping of the placed rectangles.
010 *
011 * @version
012 * IFS 1.1 (Iterative Forward Search)<br>
013 * Copyright (C) 2006 Tomáš Müller<br>
014 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
015 * Lazenska 391, 76314 Zlin, Czech Republic<br>
016 * <br>
017 * This library is free software; you can redistribute it and/or
018 * modify it under the terms of the GNU Lesser General Public
019 * License as published by the Free Software Foundation; either
020 * version 2.1 of the License, or (at your option) any later version.
021 * <br><br>
022 * This library is distributed in the hope that it will be useful,
023 * but 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.
026 * <br><br>
027 * You should have received a copy of the GNU Lesser General Public
028 * License along with this library; if not, write to the Free Software
029 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
030 */
031 public class ResourceConstraint extends Constraint {
032 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(ResourceConstraint.class);
033 private Variable[][] iResource;
034 private int iWidth, iHeight;
035
036 /**
037 * Constructor.
038 * @param width area width
039 * @param height area height
040 */
041 public ResourceConstraint(int width, int height) {
042 super();
043 iWidth = width;
044 iHeight = height;
045 iResource = new Variable[width][height];
046 for (int x = 0; x < width; x++)
047 for (int y = 0; y < height; y++)
048 iResource[x][y] = null;
049 }
050
051 /**
052 * Compute conflicts with the given placement of the rectangle.
053 * This means the rectangles which are already placed and which are overlapping with the given assignment.
054 */
055 public void computeConflicts(Value value, Set conflicts) {
056 Rectangle rectangle = (Rectangle)value.variable();
057 Location placement = (Location)value;
058 for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
059 for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++)
060 if (iResource[x][y] != null)
061 conflicts.add(iResource[x][y].getAssignment());
062 }
063
064 /**
065 * Returns true if there is a rectangle which overlaps with the given assignment.
066 */
067 public boolean inConflict(Value value) {
068 Rectangle rectangle = (Rectangle)value.variable();
069 Location placement = (Location)value;
070 for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
071 for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++)
072 if (iResource[x][y] != null)
073 return true;
074 return false;
075 }
076
077 /**
078 * Returns true if the given rectangles (assignments) do not overlap.
079 */
080 public boolean isConsistent(Value value1, Value value2) {
081 Rectangle r1 = (Rectangle)value1.variable();
082 Location p1 = (Location)value1;
083 Rectangle r2 = (Rectangle)value2.variable();
084 Location p2 = (Location)value2;
085 if (p2.getX() + r2.getWidth() <= p1.getX()) return true;
086 if (p2.getX() >= p1.getX() + r1.getWidth()) return true;
087 if (p2.getY() + r2.getHeight() <= p1.getY()) return true;
088 if (p2.getY() >= p1.getY() + r1.getHeight()) return true;
089 return false;
090 }
091
092 /**
093 * Notification, when a rectangle is placed.
094 * It memorizes the rectangle's new position in 2D ([0..width][0..height]) array.
095 * It is used for faster lookup when computing conflicts.
096 */
097 public void assigned(long iteration, Value value) {
098 super.assigned(iteration, value);
099 Rectangle rectangle = (Rectangle)value.variable();
100 Location placement = (Location)value;
101 for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
102 for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++) {
103 iResource[x][y] = value.variable();
104 }
105 }
106
107 /**
108 * Notification, when a rectangle is unplaced.
109 * It removes the rectangle from the 2D ([0..width][0..height]) array.
110 */
111 public void unassigned(long iteration, Value value) {
112 super.unassigned(iteration, value);
113 Rectangle rectangle = (Rectangle)value.variable();
114 Location placement = (Location)value;
115 for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
116 for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++) {
117 iResource[x][y] = null;
118 }
119 }
120
121 public void check() {
122 sLogger.debug("check");
123 for (Enumeration e=variables().elements();e.hasMoreElements();) {
124 Rectangle rectangle = (Rectangle)e.nextElement();
125 Location placement = (Location)rectangle.getAssignment();
126 if (placement==null) {
127 sLogger.warn("Rectangle "+rectangle.getName()+" is not assigned.");
128 continue;
129 }
130 sLogger.debug("Checking "+rectangle.getName()+" (assigned:"+placement.getName()+", prohibited:"+rectangle.isProhibited(placement.getX(),placement.getY())+", initial:"+rectangle.getInitialAssignment()+", prohibited:["+rectangle.getProhibitedX()+","+rectangle.getProhibitedY()+"])");
131 if (placement.getX()==rectangle.getProhibitedX() || placement.getY()==rectangle.getProhibitedY())
132 sLogger.error("Placement is prohibited.");
133 if (placement.getX()<rectangle.getMinX() || placement.getX()>rectangle.getMaxX() ||
134 placement.getY()<rectangle.getMinY() || placement.getY()>rectangle.getMaxY())
135 sLogger.error("Placement is outside bounds.");
136 for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
137 for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++) {
138 if (iResource[x][y]==null || !iResource[x][y].equals(rectangle))
139 sLogger.error("Problem at ["+x+","+y+"], "+iResource[x][y]+" is assigned there.");
140 }
141 }
142 sLogger.debug(toString());
143 }
144
145 /**
146 * String representation of the constraint (for debugging and printing purposes).
147 */
148 public String toString() {
149 StringBuffer sb = new StringBuffer("ResourceConstraint{\n ");
150 for (int y = 0; y < iHeight; y++) {
151 for (int x = 0; x < iWidth; x++) {
152 sb.append(ToolBox.trim( iResource[x][y] == null ? "" : ((Rectangle)iResource[x][y]).getName().substring(4), 4));
153 }
154 sb.append("\n ");
155 }
156 sb.append("\n }");
157 return sb.toString();
158 }
159 }