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}