1 /* 2 * Disjoint.java 3 * This file is part of JaCoP. 4 * <p> 5 * JaCoP is a Java Constraint Programming solver. 6 * <p> 7 * Copyright (C) 2000-2008 Krzysztof Kuchcinski and Radoslaw Szymanek 8 * <p> 9 * This program is free software: you can redistribute it and/or modify 10 * it under the terms of the GNU Affero General Public License as published by 11 * the Free Software Foundation, either version 3 of the License, or 12 * (at your option) any later version. 13 * <p> 14 * This program is distributed in the hope that it will be useful, 15 * but WITHOUT ANY WARRANTY; without even the implied warranty of 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 * GNU Affero General Public License for more details. 18 * <p> 19 * Notwithstanding any other provision of this License, the copyright 20 * owners of this work supplement the terms of this License with terms 21 * prohibiting misrepresentation of the origin of this work and requiring 22 * that modified versions of this work be marked in reasonable ways as 23 * different from the original version. This supplement of the license 24 * terms is in accordance with Section 7 of GNU Affero General Public 25 * License version 3. 26 * <p> 27 * You should have received a copy of the GNU Affero General Public License 28 * along with this program. If not, see <http://www.gnu.org/licenses/>. 29 */ 30 31 32 package org.jacop.constraints; 33 34 import org.jacop.core.IntDomain; 35 import org.jacop.core.IntVar; 36 import org.jacop.core.Store; 37 38 import java.util.ArrayList; 39 import java.util.Arrays; 40 import java.util.List; 41 import java.util.Set; 42 import java.util.concurrent.atomic.AtomicInteger; 43 44 /** 45 * Disjoint constraint assures that any two rectangles from a vector of 46 * rectangles does not overlap in at least one direction. 47 * <p> 48 * Zero-width rectangles does not overlap with any other rectangle. 49 * 50 * @author Krzysztof Kuchcinski and Radoslaw Szymanek 51 * @version 4.8 52 */ 53 54 public class Disjoint extends Diff { 55 56 static AtomicInteger idNumber = new AtomicInteger(0); 57 58 Diff2Var evalRects[]; 59 60 /** 61 * @param rectangles a list of rectangles. 62 * @param doProfile should profile be computed and used. 63 */ Disjoint(Rectangle[] rectangles, boolean doProfile)64 public Disjoint(Rectangle[] rectangles, boolean doProfile) { 65 66 checkInputForNullness("rectangles", rectangles); 67 checkInput(rectangles, r -> r.dim == 2, "rectangle has to have exactly two dimensions"); 68 69 this.queueIndex = 2; 70 71 this.rectangles = Arrays.copyOf(rectangles, rectangles.length); 72 this.doProfile = doProfile; 73 this.numberId = idNumber.incrementAndGet(); 74 75 setScope(Rectangle.getStream(this.rectangles)); 76 } 77 78 /** 79 * It creates a diff2 constraint. 80 * 81 * @param o1 list of variables denoting the origin in the first dimension. 82 * @param o2 list of variables denoting the origin in the second dimension. 83 * @param l1 list of variables denoting the length in the first dimension. 84 * @param l2 list of variables denoting the length in the second dimension. 85 * @param profile specifies if the profile should be computed. 86 */ Disjoint(List<IntVar> o1, List<IntVar> o2, List<IntVar> l1, List<IntVar> l2, boolean profile)87 public Disjoint(List<IntVar> o1, List<IntVar> o2, List<IntVar> l1, List<IntVar> l2, boolean profile) { 88 this(o1, o2, l1, l2); 89 doProfile = profile; 90 } 91 92 /** 93 * It creates a diff2 constraint. 94 * 95 * @param rectangles list of rectangles with origins and lengths in both dimensions. 96 */ 97 Disjoint(List<? extends List<? extends IntVar>> rectangles)98 public Disjoint(List<? extends List<? extends IntVar>> rectangles) { 99 100 queueIndex = 2; 101 this.rectangles = Rectangle.toArrayOf2DRectangles(rectangles); 102 numberId = idNumber.incrementAndGet(); 103 104 setScope(Rectangle.getStream(this.rectangles)); 105 106 } 107 108 /** 109 * It creates a diff2 constraint. 110 * 111 * @param rectangles list of rectangles with origins and lengths in both dimensions. 112 * @param profile specifies if the profile is computed and used. 113 */ 114 Disjoint(List<? extends List<? extends IntVar>> rectangles, boolean profile)115 public Disjoint(List<? extends List<? extends IntVar>> rectangles, boolean profile) { 116 this(rectangles); 117 doProfile = profile; 118 } 119 120 121 /** 122 * It creates a diff2 constraint. 123 * 124 * @param o1 list of variables denoting the origin in the first dimension. 125 * @param o2 list of variables denoting the origin in the second dimension. 126 * @param l1 list of variables denoting the length in the first dimension. 127 * @param l2 list of variables denoting the length in the second dimension. 128 */ Disjoint(List<? extends IntVar> o1, List<? extends IntVar> o2, List<? extends IntVar> l1, List<? extends IntVar> l2)129 public Disjoint(List<? extends IntVar> o1, List<? extends IntVar> o2, List<? extends IntVar> l1, List<? extends IntVar> l2) { 130 131 this(o1.toArray(new IntVar[o1.size()]), o2.toArray(new IntVar[o2.size()]), l1.toArray(new IntVar[l1.size()]), 132 l2.toArray(new IntVar[l2.size()])); 133 134 } 135 136 /** 137 * It creates a diff2 constraint. 138 * 139 * @param origin1 list of variables denoting the origin in the first dimension. 140 * @param origin2 list of variables denoting the origin in the second dimension. 141 * @param length1 list of variables denoting the length in the first dimension. 142 * @param length2 list of variables denoting the length in the second dimension. 143 */ 144 Disjoint(IntVar[] origin1, IntVar[] origin2, IntVar[] length1, IntVar[] length2)145 public Disjoint(IntVar[] origin1, IntVar[] origin2, IntVar[] length1, IntVar[] length2) { 146 147 checkInputForNullness(new String[] {"origin1", "origin2", "length1", "length2"}, 148 new Object[][] {origin1, origin2, length1, length2}); 149 150 queueIndex = 2; 151 this.rectangles = Rectangle.toArrayOf2DRectangles(origin1, origin2, length1, length2); 152 numberId = idNumber.incrementAndGet(); 153 154 setScope(Rectangle.getStream(this.rectangles)); 155 } 156 157 /** 158 * It creates a diff2 constraint. 159 * 160 * @param o1 list of variables denoting the origin in the first dimension. 161 * @param o2 list of variables denoting the origin in the second dimension. 162 * @param l1 list of variables denoting the length in the first dimension. 163 * @param l2 list of variables denoting the length in the second dimension. 164 * @param profile specifies if the profile should be computed. 165 */ Disjoint(IntVar[] o1, IntVar[] o2, IntVar[] l1, IntVar[] l2, boolean profile)166 public Disjoint(IntVar[] o1, IntVar[] o2, IntVar[] l1, IntVar[] l2, boolean profile) { 167 this(o1, o2, l1, l2); 168 doProfile = profile; 169 } 170 171 /** 172 * It creates a diff2 constraint. 173 * 174 * @param rectangles list of rectangles with origins and lengths in both dimensions. 175 */ 176 Disjoint(IntVar[][] rectangles)177 public Disjoint(IntVar[][] rectangles) { 178 179 assert (rectangles != null) : "Rectangles list is null"; 180 181 queueIndex = 2; 182 this.rectangles = Rectangle.toArrayOf2DRectangles(rectangles); 183 numberId = idNumber.incrementAndGet(); 184 185 setScope(Rectangle.getStream(this.rectangles)); 186 187 } 188 189 /** 190 * It creates a diff2 constraint. 191 * 192 * @param rectangles list of rectangles with origins and lengths in both dimensions. 193 * @param profile specifies if the profile is computed and used. 194 */ 195 Disjoint(IntVar[][] rectangles, boolean profile)196 public Disjoint(IntVar[][] rectangles, boolean profile) { 197 this(rectangles); 198 doProfile = profile; 199 } 200 impose(Store store)201 public void impose(Store store) { 202 203 super.impose(store); 204 205 evalRects = new Diff2Var[rectangles.length]; 206 207 for (int j = 0; j < evalRects.length; j++) 208 evalRects[j] = new Diff2Var(store, rectangles); 209 210 } 211 narrowRectangles(Set<IntVar> fdvQueue)212 @Override void narrowRectangles(Set<IntVar> fdvQueue) { 213 214 boolean needToNarrow = false; 215 216 for (int l = 0; l < rectangles.length; l++) { 217 Rectangle r = rectangles[l]; 218 219 boolean settled = true, minLengthEq0 = false; 220 int maxLevel = 0; 221 for (int i = 0; i < r.dim(); i++) { 222 IntDomain rOrigin = r.origin[i].dom(); 223 IntDomain rLength = r.length[i].dom(); 224 settled = settled && rOrigin.singleton() && rLength.singleton(); 225 226 minLengthEq0 = minLengthEq0 || (rLength.min() < 0); 227 228 int originStamp = rOrigin.stamp, lengthStamp = rLength.stamp; 229 if (maxLevel < originStamp) 230 maxLevel = originStamp; 231 if (maxLevel < lengthStamp) 232 maxLevel = lengthStamp; 233 } 234 235 if (!minLengthEq0 && // Check for rectangle r which has 236 // all lengths > 0 237 !(settled && maxLevel < currentStore.level)) { 238 // and are not fixed already 239 240 needToNarrow = needToNarrow || containsChangedVariable(r, fdvQueue); 241 242 List<IntRectangle> UsedRect = new ArrayList<IntRectangle>(); 243 List<Rectangle> ProfileCandidates = new ArrayList<Rectangle>(); 244 List<Rectangle> OverlappingRects = new ArrayList<Rectangle>(); 245 boolean ntN = findRectangles(r, l, UsedRect, ProfileCandidates, OverlappingRects, fdvQueue); 246 247 needToNarrow = needToNarrow || ntN; 248 249 // Checking r against all s with minUse in the domain of r 250 if (needToNarrow) { 251 252 if (OverlappingRects.size() != ((Diff2VarValue) evalRects[l].value()).Rects.length) { 253 Diff2VarValue newRects = new Diff2VarValue(); 254 newRects.setValue(OverlappingRects); 255 evalRects[l].update(newRects); 256 } 257 258 narrowRectangle(r, UsedRect, ProfileCandidates); 259 } 260 } 261 } 262 } 263 findRectangles(Rectangle r, int index, List<IntRectangle> UsedRect, List<Rectangle> ProfileCandidates, List<Rectangle> OverlappingRects, Set<IntVar> fdvQueue)264 private boolean findRectangles(Rectangle r, int index, List<IntRectangle> UsedRect, List<Rectangle> ProfileCandidates, 265 List<Rectangle> OverlappingRects, Set<IntVar> fdvQueue) { 266 267 boolean contains = false, checkArea = false; 268 269 long area = 0; 270 long commonArea = 0; 271 int totalNumberOfRectangles = 0; 272 int dim = r.dim(); 273 int startMin[] = new int[dim]; 274 int stopMax[] = new int[dim]; 275 int minLength[] = new int[dim]; 276 int r_min[] = new int[dim], r_max[] = new int[dim]; 277 for (int i = 0; i < startMin.length; i++) { 278 IntDomain rLengthDom = r.length[i].dom(); 279 startMin[i] = IntDomain.MaxInt; 280 stopMax[i] = 0; 281 minLength[i] = rLengthDom.min(); 282 283 IntDomain rOriginDom = r.origin[i].dom(); 284 r_min[i] = rOriginDom.min(); 285 r_max[i] = rOriginDom.max() + rLengthDom.max(); 286 } 287 288 for (Rectangle s : ((Diff2VarValue) evalRects[index].value()).Rects) { 289 boolean overlap = true; 290 291 if (r != s) { 292 293 boolean sChanged = containsChangedVariable(s, fdvQueue); 294 295 IntRectangle Use = new IntRectangle(dim); 296 long sArea = 1; 297 long partialCommonArea = 1; 298 299 boolean use = true, minLength0 = false; 300 int s_min, s_max, start, stop; 301 int m = 0, j = 0; 302 int sOriginMin[] = new int[dim], sOriginMax[] = new int[dim], sLengthMin[] = new int[dim]; 303 304 while (overlap && m < dim) { 305 // check if domains of r and s overlap 306 IntDomain sOriginIdom = s.origin[m].dom(); 307 IntDomain sLengthIdom = s.length[m].dom(); 308 int sLengthIMin = sLengthIdom.min(); 309 int sOriginIMax = sOriginIdom.max(); 310 s_min = sOriginIdom.min(); 311 s_max = sOriginIMax + sLengthIdom.max(); 312 overlap = overlap && intervalOverlap(r_min[m], r_max[m], s_min, s_max); 313 314 // min start, max stop and min length 315 sOriginMin[m] = s_min; 316 sOriginMax[m] = sOriginIMax + sLengthIMin; 317 sLengthMin[m] = sLengthIMin; 318 319 // check if s occupies some space 320 start = sOriginIMax; 321 stop = s_min + sLengthIMin; 322 if (start <= stop) { 323 Use.add(start, stop - start); 324 j++; 325 } else 326 use = false; 327 328 minLength0 = minLength0 || (sLengthMin[m] <= 0); 329 330 m++; 331 } 332 333 if (overlap) { 334 335 OverlappingRects.add(s); 336 337 if (use) { // rectangles taking space 338 UsedRect.add(Use); 339 contains = contains || sChanged; 340 } 341 342 if (!minLength0) { // profile candiates 343 if (j > 0) { 344 ProfileCandidates.add(s); 345 contains = contains || sChanged; 346 } 347 348 checkArea = true; 349 totalNumberOfRectangles++; 350 for (int i = 0; i < dim; i++) { 351 if (sOriginMin[i] < startMin[i]) 352 startMin[i] = sOriginMin[i]; 353 if (sOriginMax[i] > stopMax[i]) 354 stopMax[i] = sOriginMax[i]; 355 if (minLength[i] > sLengthMin[i]) 356 minLength[i] = sLengthMin[i]; 357 358 sArea = sArea * sLengthMin[i]; 359 } 360 area += sArea; 361 } // profile candidate end 362 363 // calculate area within rectangle r possible placement 364 for (int i = 0; i < dim; i++) { 365 if (sOriginMin[i] <= r_min[i]) { 366 if (sOriginMax[i] <= r_max[i]) { 367 int distance1 = sOriginMin[i] + sLengthMin[i] - r_min[i]; 368 sLengthMin[i] = (distance1 > 0) ? distance1 : 0; 369 } else { 370 // sOriginMax[i] > r_max[i]) 371 int rmax = r.origin[i].max() + r.length[i].min(); 372 373 int distance1 = sOriginMin[i] + sLengthMin[i] - r_min[i]; 374 int distance2 = sLengthMin[i] - (sOriginMax[i] - rmax); 375 if (distance1 > rmax - r_min[i]) 376 distance1 = rmax - r_min[i]; 377 if (distance2 > rmax - r_min[i]) 378 distance2 = rmax - r_min[i]; 379 if (distance1 < distance2) 380 sLengthMin[i] = (distance1 > 0) ? distance1 : 0; 381 else if (distance2 > 0) { 382 if (distance2 < sLengthMin[i]) 383 sLengthMin[i] = distance2; 384 } else 385 sLengthMin[i] = 0; 386 } 387 } else // sOriginMin[i] > r_min[i] 388 if (sOriginMax[i] > r_max[i]) { 389 int distance2 = sLengthMin[i] - (sOriginMax[i] - (r.origin[i].max() + r.length[i].min())); 390 if (distance2 > 0) { 391 if (distance2 < sLengthMin[i]) 392 sLengthMin[i] = distance2; 393 } else 394 sLengthMin[i] = 0; 395 } 396 partialCommonArea = partialCommonArea * sLengthMin[i]; 397 } 398 commonArea += partialCommonArea; 399 } 400 if (commonArea + r.minArea() > (r_max[0] - r_min[0]) * (r_max[1] - r_min[1])) 401 throw Store.failException; 402 } 403 } 404 405 if (checkArea) { // check whether there is 406 // enough room for all rectangles 407 area += r.minArea(); 408 long availArea = 1; 409 long rectNumber = 1; 410 for (int i = 0; i < startMin.length; i++) { 411 IntDomain rOriginIdom = r.origin[i].dom(); 412 IntDomain rLengthIdom = r.length[i].dom(); 413 int rOriginIMin = rOriginIdom.min(), rOriginIMax = rOriginIdom.max(), rLengthIMin = rLengthIdom.min(); 414 if (rOriginIMin < startMin[i]) 415 startMin[i] = rOriginIMin; 416 if (rOriginIMax + rLengthIMin > stopMax[i]) 417 stopMax[i] = rOriginIMax + rLengthIMin; 418 } 419 boolean minEqZero = false; 420 for (int i = 0; i < startMin.length; i++) { 421 availArea = availArea * (stopMax[i] - startMin[i]); 422 if (minLength[i] == 0) { 423 minEqZero = true; 424 } else 425 rectNumber = rectNumber * ((stopMax[i] - startMin[i]) / minLength[i]); 426 } 427 if (minEqZero) 428 rectNumber = Long.MAX_VALUE; 429 430 if (availArea < area) 431 throw Store.failException; 432 else 433 // check whether there is enough room for 434 // all minimal rectangles 435 if (rectNumber < (totalNumberOfRectangles + 1)) 436 throw Store.failException; 437 } 438 439 return contains; 440 } 441 profileNarrowing(int i, Rectangle r, List<Rectangle> ProfileCandidates)442 @Override void profileNarrowing(int i, Rectangle r, List<Rectangle> ProfileCandidates) { 443 // check profile first 444 445 IntDomain rOriginIdom = r.origin[i].dom(); 446 int rOriginIdomMin = rOriginIdom.min(); 447 int rOriginIdomMax = rOriginIdom.max(); 448 DiffnProfile Profile = new DiffnProfile(); 449 450 for (int j = 0; j < r.dim; j++) { 451 if (j != i && r.length[i].min() != 0) { 452 453 Profile.make(j, i, r, rOriginIdomMin, rOriginIdomMax + r.length[i].min(), ProfileCandidates); 454 455 if (Profile.size() != 0) { 456 if (trace) { 457 System.out.println(" *** " + r + "\n" + ProfileCandidates); 458 System.out.println("Profile in dimension " + i + " and " + j + "\n" + Profile); 459 } 460 461 profileCheckRectangle(Profile, r, i, j); 462 463 } 464 } 465 } 466 } 467 satisfied()468 @Override public boolean satisfied() { 469 boolean sat = true; 470 471 Rectangle recti, rectj; 472 int i = 0; 473 while (sat && i < rectangles.length) { 474 recti = rectangles[i]; 475 int j = 0; 476 Rectangle[] toEvaluate = ((Diff2VarValue) evalRects[i].value()).Rects; 477 while (sat && j < toEvaluate.length) { 478 rectj = toEvaluate[j]; 479 sat = sat && !recti.domOverlap(rectj); 480 j++; 481 } 482 i++; 483 } 484 return sat; 485 } 486 toString()487 @Override public String toString() { 488 489 StringBuffer result = new StringBuffer(id()); 490 491 result.append(" : disjoint( "); 492 493 for (int i = 0; i < rectangles.length - 1; i++) { 494 result.append(rectangles[i]); 495 result.append(", "); 496 497 } 498 result.append(rectangles[rectangles.length - 1]); 499 result.append(")"); 500 501 return result.toString(); 502 503 } 504 505 } 506