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