1 /* 2 * Geost.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 package org.jacop.constraints.geost; 31 32 import org.jacop.api.RemoveLevelLate; 33 import org.jacop.api.Stateful; 34 import org.jacop.api.UsesQueueVariable; 35 import org.jacop.constraints.Constraint; 36 import org.jacop.core.*; 37 import org.jacop.util.SimpleArrayList; 38 import org.jacop.util.SimpleHashSet; 39 40 import java.util.*; 41 import java.util.concurrent.atomic.AtomicInteger; 42 43 /** 44 * @author Marc-Olivier Fleury and Radoslaw Szymanek 45 * @version 4.8 46 * <p> 47 * 1) DONE. FlushAndQueue function should be changed and some functionality 48 * moved to firstConsistencyCheck. 49 * <p> 50 * 2) DONE. No propagation inside queueVariable function. 51 * <p> 52 * 3) DONE. How to incorporate GUI code within Geost constraint. 53 * <p> 54 * 4) DONE. Move part of the functionality of onObjectUpdate to consistency function. 55 * <p> 56 * 5) Refactor use of TimeBoundConstraint 57 * 5b) DONE. remove runTimeConstraint boolean variable. 58 * <p> 59 * 6) DONE. asserts for Shape register 60 * 6b) asserts about possible values of MaxInt and MinInt. 61 * <p> 62 * 7) DONE. Use simpleHashSet instead of LinkedHashSet for objectQueue. 63 * <p> 64 * 8) DONE. Discuss pruning events, do we really need ANY for all variables? For example, 65 * maybe time variables always BOUND pruning event. 66 * <p> 67 * 9) DONE. Simplify queueObject by removing if statements and make sure that 68 * this function is being called properly (avoid non-asserts checks 69 * inside it). 70 * <p> 71 * 10) DONE. Discuss the possible implementation of satisfied function. 72 * <p> 73 * 11) Introduce time switch so geost can work without time dimension. 74 * <p> 75 * 12) Lessen the feature of geost that it does not work with variables used 76 * multiple times within different objects 77 * 12b) DONE. (at least for singleton variables). 78 * <p> 79 * 13) DONE. Verify fix to address bug in case of multiple level removals, or level 80 * removals for which no consistency function has been called. Functionality 81 * around variable currentLevel. It is still needed. 82 * <p> 83 * 14. DONE. Fixing a bug connected with timestamps and multiple remove levels calls. 84 * 14b Check lastLevelVar (possibly needs to be done similarly as setStart). 85 * <p> 86 * Future Work : 87 * <p> 88 * 1. InArea should support subset of objects and dimensions. 89 * <p> 90 * 2. Reuse previously generated outboxes. Create a function to create a hashkey 91 * from points coordinates for which an outbox is required. Later, for each 92 * new point we check if we have proper outbox for a given hash-key generated 93 * from this outbox. 94 * <p> 95 * 3. Not always finishing at consistency fixpoint, speculative fixpoint. 96 * <p> 97 * 4. consider polymorphism due to rotations only, and see if 98 * better performance can be reached under this assumption. 99 * <p> 100 * 5. If objects have the same shape, and they are indistingushable 101 * then symmetry breaking can be employed. 102 */ 103 public class Geost extends Constraint implements UsesQueueVariable, Stateful, RemoveLevelLate { 104 105 /** 106 * It specifies different debugging switches to print out diverse information about 107 * execution of the geost constraint. 108 */ 109 final static boolean DEBUG_ALL = false; 110 111 final static boolean DEBUG_MAIN = DEBUG_ALL || false; 112 113 final static boolean DEBUG_SUBSETS = DEBUG_ALL || false; 114 115 final static boolean DEBUG_DOUBLE_LAYER = DEBUG_ALL || false; 116 117 final static boolean DEBUG_SHAPE_SKIP = DEBUG_ALL || false; 118 119 final static boolean DEBUG_VAR_SKIP = DEBUG_ALL || false; 120 121 final static boolean DEBUG_OBJECT_GROUNDING = DEBUG_ALL || false; 122 123 final static boolean DEBUG_BACKTRACK = DEBUG_ALL || false; 124 125 final static boolean GATHER_STATS = true; 126 127 final static boolean DEBUG_REORDER = false; 128 129 /** 130 * It counts how many constraints we discounted in outbox generation procedure as not useful ones. 131 */ 132 long filteredConstraintCount; 133 134 /** 135 * It counts the number of times the minimum values of geost objects origins are being examined for pruning. 136 */ 137 long pruneMinCount = 0; 138 139 /** 140 * It counts the number of times the minimum values of geost objects origins are being examined for pruning. 141 * It may be different (smaller than) prunedMinCount as constraint may have failed during min domain pruning. 142 */ 143 long pruneMaxCount = 0; 144 145 /** 146 * It counts number of executions of outboxes generation. 147 */ 148 long findForbiddenDomainCount = 0; 149 150 /** 151 * It counts the number of object updates. 152 */ 153 long onObjectUpdateCount = 0; 154 155 /** 156 * It counts how many times the feasibility check is being performed by internal constraint on a supplied 157 * point. 158 */ 159 long isFeasibleCount = 0; 160 161 /** 162 * It counts how many times the object has been queued. 163 */ 164 long queuedObjectCount = 0; 165 166 /** 167 * It specifies the unique number used to differentiate geost constraints. 168 */ 169 static AtomicInteger idNumber = new AtomicInteger(0); 170 171 /** 172 * It indicates whether we are currently running the consistency function or not. 173 */ 174 boolean inConsistency; 175 176 /** 177 * If equal to true then modifying one object implies that all objects have to be added 178 * to object queue. 179 */ 180 boolean allLinked = false; 181 182 /** 183 * It is used to signal that some shape ID was pruned. 184 * It is required because pruning skip condition (var grounded, and not in the queue) 185 * can only be safely used if no shape id field was pruned. 186 * Indeed, if some shape ID was pruned, feasibility can change, thus a check is needed. 187 */ 188 boolean changedShapeID = false; 189 190 /** 191 * if set to true, a variable will never be skipped, even if grounded and not in queue 192 */ 193 public boolean enforceNoSkip = true; // setting to false is causing a bug that allows incorrect solution to be accepted. 194 195 /** 196 * It remembers if it is the first time the consistency check is being performed. 197 * If not, then the initial consistency checks which have to be done only once 198 * will be done during the first consistency check. This flag is set back to true 199 * if the remove level function is removing the level onto which the changes 200 * caused by the initial consistency were applied to. 201 */ 202 boolean firstConsistencyCheck; 203 204 /** 205 * It remembers the level at which the consistency function was applied for the first time. 206 * If that level is being removed then the initial consistency function must be executed again. 207 */ 208 int firstConsistencyLevel; 209 210 211 /** 212 * It specifies for each object if consistency function should be run if this object becomes grounded. 213 * It is set to true if the object was grounded outside consistency function call or after a shape variable 214 * has been changed. It is set to false only after exactly one consistency check during which the object 215 * was grounded. 216 */ 217 final boolean[] pruneIfGrounded; 218 219 /** 220 * It maps any variable in the scope of the geost constraint to the object it belongs to. 221 */ 222 final Map<Var, GeostObject> variableObjectMap; 223 224 225 /** 226 * It stores all variables which have changed outside the consistency function of this constraint. 227 */ 228 LinkedHashSet<Var> variableQueue; 229 230 /** 231 * It stores the position of the last variable grounded in the previous level. 232 */ 233 TimeStamp<Integer> lastLevelLastVar; 234 235 /** 236 * It contains all the objects which have been updated in the previous levels. 237 */ 238 SimpleArrayList<GeostObject> objectList; 239 240 /** 241 * It contains all the objects which have been updated at current level. The objects 242 * from this set are moved to the array objectList as soon as level is increased. If 243 * level is being removed then for every object in this set we inform the external constraints 244 * that their state in connection to this object may have changed. 245 */ 246 Set<GeostObject> updatedObjectSet; 247 248 /** 249 * it stores the index of the first object which have changed at current level. It allows 250 * to inform the external constraints about objects being changed due to backtracking. 251 */ 252 TimeStamp<Integer> setStart; 253 254 /** 255 * It stores the information about left bound of the interval of objects which are 256 * updated by backtracking. It is set by removeLevel function and it is used by 257 * removeLevelLate function. It simply denotes the stopping condition. 258 */ 259 //int lowerBound; 260 261 /** 262 * It contains objects that need to be checked in the next sweep. 263 */ 264 SimpleHashSet<GeostObject> objectQueue; 265 266 /** 267 * It is a locally used array which stores the enumeration of values for 268 * the current shape variable. The enumeration is lexicographical with 269 * one exception the previously found best shape is put on the first position. 270 */ 271 final int[] shapeIdsToPrune; 272 273 /** 274 * set to false to disable relaxed shape pruning 275 */ 276 public boolean partialShapeSweep = true; 277 278 /** 279 * It stores all generated internal constraints for all objects/constraints. It 280 * is used to speed up some visualization functions. If not for that reason it could 281 * have been a local variable within a function generating internal constraints. 282 */ 283 public Collection<InternalConstraint> internalConstraints; 284 285 /** 286 * For each object, the set of constraint that apply to it 287 * we use object ids as keys, and can thus use an array to store 288 * the map. This is the input set to the filtering process 289 * before pruning any object. 290 */ 291 Set<InternalConstraint>[] objectConstraints; 292 293 294 295 /** 296 * It stores the special constraints responsible for the handling of holes in the domain. 297 * It is indexed by object id. 298 */ 299 final DomainHoles[] domainHolesConstraints; 300 301 302 /** 303 * It specifies the order between dimensions which is used by the 304 * pruning algorithm. The order may have influence on the algorithm 305 * efficiency. The geost constraint chooses the order based on average 306 * length of objects in the particular dimension. The dimension with 307 * higher average length in this dimension will have the preference. 308 */ 309 public final LexicographicalOrder order; 310 311 /** 312 * A preallocated array of ints used extensively within sweeping algorithm. 313 */ 314 final int[] c; 315 /** 316 * A preallocated array of ints used extensively within sweeping algorithm. 317 */ 318 final int[] n; 319 320 /** 321 * It keeps a reference to the store. 322 */ 323 protected Store store; 324 325 /** 326 * It stores all variables which have been grounded. It is used to upon backtracking 327 * to update objects to their previous state. 328 */ 329 final SimpleArrayList<Var> groundedVars; 330 331 /** 332 * It contains all not filtered out, useful internal constraints which should 333 * be used to generate outboxes. The initial array of internal constraints 334 * associate with a given object being pruned can be significantly shrank 335 * and the remaining objects (still useful) are store in this array. 336 */ 337 InternalConstraint[] stillUsefulInternalConstraints; 338 339 /** 340 * It specifies the last useful constraint in the array of useful internal 341 * constraints. 342 */ 343 int lastConstraintToCheck = 0; 344 345 /** 346 * It specifies that filtering of useless internal constraint takes place 347 * before an object is being pruned. It may be costly for small instances. 348 */ 349 public final boolean filterUseless = true; 350 351 /** 352 * It defines whether outbox generation should always rely on overlapping frames. 353 * For problems that contain objects that have small domains compared to their size, then 354 * using only frames may provide a better performance (up to 50% faster). It can only 355 * be changed before impose() function, changing it afterwards will lead to improper 356 * behavior. 357 */ 358 public boolean alwaysUseFrames = false; 359 360 361 /** 362 * It is a flag set to true during remove level late function execution so objects which 363 * are being updated upon backtracking can be handled properly. 364 */ 365 public boolean backtracking; 366 367 /** 368 * If running a complete sweep for each shape is costly, because some shapes may require 369 * a significant sweep, even though a weaker bound has already been found. 370 * However, to be able to prune shapes, such a costly sweep needs to be done. 371 * A tradeoff solution consists in running a complete sweep for each shape once per 372 * node, and optimize the following runs. 373 * This implies remembering which object have already been fully pruned. 374 */ 375 final boolean[] fullyPruned; 376 377 /** 378 * It stores temporarily objects for which pruning is suggested by external constraints. 379 * The geost constraint checks every object from this set to see if that is actually 380 * necessary to invoke the pruning for that object. 381 */ 382 final SimpleHashSet<GeostObject> temporaryObjectSet; 383 384 385 /** 386 * A temporary list to collect bounding boxes for each shape of the given object 387 * to compute one bounding box whatever the shape of the object. It is made 388 * as a member of the geost constraint to avoid multiple memory allocations. 389 */ 390 final SimpleArrayList<DBox> workingList; 391 392 393 /** 394 * It specifies the number of dimensions of each object given to the geost constraint. 395 */ 396 final int dimension; 397 398 /** 399 * It is set by queueVariable after a time variable has been changed. It indicates 400 * that we should run the consistency function of the time constraint. 401 */ 402 private boolean oneTimeVarChanged; 403 404 /** 405 * It is used inside flushQueue function to separate timeconsistency execution from 406 * object update (potentially expensive if for example object frame is recomputed). 407 */ 408 SimpleArrayList<GeostObject> objectList4Flush = new SimpleArrayList<GeostObject>(); 409 410 /** 411 * It stores the reference to the collection of objects provided to 412 * the constructor. It does not perform cloning so the collection can 413 * not change after geost constraint was imposed. 414 */ 415 public final GeostObject[] objects; 416 417 418 /** 419 * It stores the reference to the collection of external constraints 420 * which must be satisfied within this constraint. This is a reference 421 * to the collection provided within the constructor. No copying is employed 422 * therefore the collection can not change even after the constraint is imposed. 423 */ 424 public final ExternalConstraint[] externalConstraints; 425 426 427 /** 428 * It stores information about shapes used by objects within this geost constraint. 429 * It is based on shapes information provided in the constructor. 430 */ 431 public final Shape[] shapeRegister; 432 433 @SuppressWarnings("all") Geost(Collection<GeostObject> objects, Collection<ExternalConstraint> constraints, Collection<Shape> shapes)434 public Geost(Collection<GeostObject> objects, Collection<ExternalConstraint> constraints, Collection<Shape> shapes) { 435 this(objects.toArray(new GeostObject[objects.size()]), constraints.toArray(new ExternalConstraint[constraints.size()]), 436 shapes.toArray(new Shape[shapes.size()])); 437 } 438 439 /** 440 * It creates a geost constraint from provided objects, external constraints, 441 * as well as shapes. The construct parameters are not cloned so do not 442 * reuse them in creation in other constraints if changes are necessary. 443 * Make sure that the largest object id is as small as possible to avoid 444 * unnecessary memory cost. 445 * 446 * @param objects objects in the scope of the geost constraint. 447 * @param constraints the collection of external constraints enforced by geost. 448 * @param shapes the list of different shapes used by the objects in scope of the geost. 449 */ Geost(GeostObject[] objects, ExternalConstraint[] constraints, Shape[] shapes)450 @SuppressWarnings("unchecked") public Geost(GeostObject[] objects, ExternalConstraint[] constraints, Shape[] shapes) { 451 452 checkInputForDuplicationSkipSingletons("objects", 453 Arrays.stream(objects).map(obj -> obj.getVariables().stream()).flatMap(i -> i).toArray(IntVar[]::new)); 454 455 // This comes from the frame computation for NonOverlapping external constraint. 456 assert (IntDomain.MaxInt < Integer.MAX_VALUE / 4 - 1) : "Geost can not work with too large Constants.MaxInt"; 457 assert (IntDomain.MinInt > Integer.MIN_VALUE / 4 + 1) : "Geost can not work with too small Constants.MinInt"; 458 459 assert (objects.length > 0) : "empty collection of objects"; 460 assert (shapes.length > 0) : "empty collection of shapes"; 461 assert (constraints.length > 0) : "empty collection of constraints"; 462 463 this.queueIndex = 2; 464 this.objects = objects.clone(); 465 this.externalConstraints = constraints.clone(); 466 467 this.numberId = idNumber.incrementAndGet(); 468 this.variableQueue = new LinkedHashSet<Var>(); 469 470 //objectQueue = new LinkedHashSet<GeostObject>( objects.size() ); 471 //objectQueue.addAll(objects); 472 473 objectQueue = new SimpleHashSet<GeostObject>(objects.length); 474 for (GeostObject o : objects) 475 objectQueue.add(o); 476 477 Map<Integer, Shape> idShapeMap = new HashMap<Integer, Shape>(); 478 479 //add all shapes to the register 480 for (Shape s : shapes) { 481 if (s.no < 0) 482 throw new IllegalArgumentException("shape ID has to be positive"); 483 idShapeMap.put(s.no, s); 484 } 485 486 //make sure that all objects have the same dimension 487 //make sure that IDs are unique 488 //make sure that the shapes used are defined 489 Set<Integer> objectIds = new HashSet<Integer>(); 490 int dim = -1; 491 int idMax = 0; 492 493 for (GeostObject o : objects) { 494 495 if (objectIds.contains(o.no)) 496 throw new IllegalArgumentException("all objects must have a different ID"); 497 else if (o.no < 0) 498 throw new IllegalArgumentException("object ID has to be positive"); 499 else { 500 objectIds.add(o.no); 501 idMax = Math.max(o.no, idMax); 502 } 503 504 if (dim == -1) 505 dim = o.dimension; 506 else if (dim != o.dimension) 507 throw new IllegalArgumentException("all objects must have the same number of dimensions"); 508 509 //make sure that the shapes used are defined 510 ValueEnumeration shapeIDVals = o.shapeID.domain.valueEnumeration(); 511 while (shapeIDVals.hasMoreElements()) { 512 int sid = shapeIDVals.nextElement(); 513 if (!idShapeMap.containsKey(sid)) 514 throw new IllegalArgumentException("shape id " + sid + " does not correspond to any shape"); 515 } 516 517 } 518 519 dimension = dim; 520 521 objectConstraints = new Set[idMax + 1]; 522 domainHolesConstraints = new DomainHoles[idMax + 1]; 523 524 pruneIfGrounded = new boolean[idMax + 1]; 525 Arrays.fill(pruneIfGrounded, false); 526 527 shapeRegister = new Shape[idShapeMap.size()]; 528 529 for (Map.Entry<Integer, Shape> e : idShapeMap.entrySet()) { 530 assert (e.getKey() < idShapeMap.size()) : "Shapes do not have unique ids between 0 and n-1, where n is number of shapes."; 531 shapeRegister[e.getKey()] = e.getValue(); 532 } 533 534 if (partialShapeSweep) 535 fullyPruned = new boolean[idMax + 1]; 536 else 537 fullyPruned = null; 538 539 //make sure the DBox pool is correctly initialized 540 DBox.supportDimension(dimension); 541 DBox.supportDimension(dimension + 1); //one more slot for time 542 543 shapeIdsToPrune = new int[shapeRegister.length]; 544 545 assert (dimension > 0) : "No dimensions"; 546 547 // one extra dimension for time 548 c = new int[dimension + 1]; 549 n = new int[dimension + 1]; 550 551 //use an ordering based on average box sizes: longer dimension first 552 int[] shapeNb = new int[shapeRegister.length]; 553 int totShapes = 0; 554 555 //compute cumulated box sizes 556 double[] averageSizes = new double[dimension + 1]; 557 558 Arrays.fill(shapeNb, 0); 559 560 for (GeostObject o : objects) { 561 ValueEnumeration vals = o.shapeID.domain.valueEnumeration(); 562 while (vals.hasMoreElements()) { 563 shapeNb[vals.nextElement()]++; 564 totShapes++; 565 } 566 averageSizes[dimension] += o.end.max() - o.start.min(); 567 } 568 569 for (int i = 0; i < shapeRegister.length; i++) 570 for (int j = 0; j < averageSizes.length - 1; j++) 571 averageSizes[j] += shapeRegister[i].boundingBox.length[j] * shapeNb[i]; 572 573 for (int j = 0; j < averageSizes.length - 1; j++) 574 averageSizes[j] /= totShapes; 575 576 averageSizes[dimension] /= objects.length; 577 578 //now, averageSizes contains, for each dimension, the average box size 579 //we can now get the corresponding ordering of dimensions 580 581 //smallest dimension first 582 int[] ordering = new int[dimension + 1]; 583 for (int i = 0; i < ordering.length; i++) { 584 //find smallest value 585 double smallestYet = Double.MAX_VALUE; 586 int smallestIndex = 0; 587 for (int j = 0; j < ordering.length; j++) 588 if (averageSizes[j] < smallestYet) { 589 smallestYet = averageSizes[j]; 590 smallestIndex = j; 591 } 592 ordering[i] = smallestIndex; 593 averageSizes[smallestIndex] = Double.MAX_VALUE; 594 } 595 596 //ordering now corresponds to average box sizes, smallest first 597 order = new PredefinedOrder(ordering, 0); 598 599 600 variableObjectMap = Var.createEmptyPositioning(); 601 602 for (GeostObject o : objects) 603 for (Var v : o.getVariables()) { 604 if (!v.singleton()) { 605 GeostObject previousValue = variableObjectMap.put(v, o); 606 assert (previousValue == null) : "Current implementation of Geost does not allow reuse of not singleton variables."; 607 } 608 } 609 610 inConsistency = false; 611 612 temporaryObjectSet = new SimpleHashSet<GeostObject>(); 613 614 615 backtracking = false; 616 workingList = new SimpleArrayList<DBox>(); 617 618 assert (checkInvariants() == null) : checkInvariants(); 619 620 groundedVars = new SimpleArrayList<Var>(); 621 622 setScope(variableObjectMap.keySet()); 623 624 // boxDisplay = new BoxDisplay(20, "inside"); 625 } 626 627 /** 628 * It checks that this constraint has consistent data structures. 629 * 630 * @return a string describing the consistency problem with data structures, null if no problem encountered. 631 */ 632 checkInvariants()633 public String checkInvariants() { 634 635 if (order == null) 636 return "lexical order is null"; 637 if (variableQueue == null) 638 return "variable queue is null"; 639 // if(objectQueue == null) return "object queue is null"; 640 if (objectQueue == null) 641 return "object queue is null"; 642 if (c.length != n.length) 643 return "c and n must have the same size"; 644 if (objects.length == 0) 645 return "empty collection of objects"; 646 if (externalConstraints.length == 0) 647 return "empty collection of constraints"; 648 649 return null; 650 } 651 652 653 654 /** 655 * It returns the shape with a given id if such exists. 656 * 657 * @param id the unique id of the shape we are looking for. 658 * @return the shape of a given id previously provided. 659 */ getShape(int id)660 public final Shape getShape(int id) { 661 662 assert id >= 0 && id < shapeRegister.length && shapeRegister[id] != null : "unknown shape id: " + id; 663 664 return shapeRegister[id]; 665 666 } 667 668 669 670 protected void genInternalConstraints() { 671 672 internalConstraints = new ArrayList<InternalConstraint>(); 673 674 int constraintCount = 0; 675 676 for (ExternalConstraint ec : externalConstraints) { 677 678 final Collection<? extends InternalConstraint> ics = ec.genInternalConstraints(this); 679 680 //prepare all data structures 681 for (GeostObject o : objects) 682 ec.onObjectUpdate(o); 683 684 internalConstraints.addAll(ics); 685 686 constraintCount += ics.size(); 687 688 } 689 690 assert constraintCount == internalConstraints.size() : "some constraints were not added correctly"; 691 692 //initialize array used to stored filtered constraints. Has to be large enough to store all constraints 693 stillUsefulInternalConstraints = internalConstraints.toArray(new InternalConstraint[internalConstraints.size()]); 694 695 /* 696 * TODO reuse different scopes if equal so that quadratic use of memory is avoided 697 * 698 * For a moment a simple solution is implemented: simple case where all constraints apply to all objects 699 */ 700 701 //find out if all constraints apply on the whole collection of objects 702 allLinked = true; 703 704 Set<Object> scope = new HashSet<Object>(); 705 706 for (ExternalConstraint ec : externalConstraints) { 707 708 GeostObject[] constraintScope = ec.getObjectScope(); 709 710 if (constraintScope != null) { 711 712 int prevSize = scope.size(); 713 714 List<GeostObject> constraintScopeArr = new ArrayList<GeostObject>(constraintScope.length); 715 for (GeostObject o : constraintScope) 716 constraintScopeArr.add(o); 717 718 boolean changed = scope.addAll(constraintScopeArr); 719 720 if (changed && prevSize != 0) { 721 //some constraint applies to a subset of objects only 722 allLinked = false; 723 break; 724 } 725 726 } 727 728 } 729 730 if (allLinked && scope.size() != objects.length) { 731 //may appear if only one constraint applies to a subset of objects 732 allLinked = false; 733 } 734 735 /* 736 * generate constraint corresponding to holes in the domain. 737 * They are handled separately because they are relevant only for 738 * the object being placed 739 * 740 */ 741 if (!allLinked) { 742 for (GeostObject o : objects) { 743 domainHolesConstraints[o.no] = new DomainHoles(o); 744 745 //collect related constraints 746 Set<InternalConstraint> relatedConstraints = new HashSet<InternalConstraint>(); 747 for (ExternalConstraint ec : externalConstraints) 748 relatedConstraints.addAll(ec.getObjectConstraints(o)); 749 objectConstraints[o.no] = relatedConstraints; 750 751 } 752 } else { 753 754 Set<InternalConstraint> commonConstraints = new HashSet<InternalConstraint>(); 755 commonConstraints.addAll(internalConstraints); 756 757 for (GeostObject o : objects) { 758 domainHolesConstraints[o.no] = new DomainHoles(o); 759 objectConstraints[o.no] = commonConstraints; 760 } 761 } 762 763 764 765 } 766 767 /** 768 * the sweeping routine for minimal bounds. Since in the polymorphic case, it is run for each possible shape, 769 * and only the weakest result is used, it cannot have side-effects. In particular, it cannot 770 * directly update domain values. 771 * If any data structure is updated here, make sure that it is done carefully enough. 772 * 773 * @param store the store 774 * @param o the object to prune 775 * @param currentShape the shape of the object 776 * @param d the current most significant dimension 777 * @param limit stop pruning if going beyond this value 778 * @return the bound found if there is one, and Constants.MaxInt if there is no feasible placement. 779 */ 780 781 protected int pruneMin(Store store, GeostObject o, int currentShape, int d, 782 // Set<InternalConstraint> I, 783 int limit) { 784 785 boolean feasiblePointFound = true; 786 787 // if(USE_DISPLAY) 788 // display.eraseAll(); 789 790 if (DEBUG_MAIN) 791 System.out.println("pruneMin"); 792 793 Geost.SweepDirection dir = Geost.SweepDirection.PRUNEMIN; 794 795 order.setMostSignificantDimension(d); 796 797 //c is initialized with the lower bound of the object's domain, n with the upper bound+1 798 for (int i = 0, size = o.dimension; i < size; i++) { 799 c[i] = o.coords[i].min(); 800 n[i] = o.coords[i].max() + 1; 801 } 802 803 c[dimension] = o.start.min(); 804 n[dimension] = o.start.max() + 1; 805 806 if (DEBUG_MAIN) 807 System.out.println("shape ID in pruneMin: " + currentShape); 808 809 if (DEBUG_MAIN) { 810 System.out.println("inital, c and n:"); 811 System.out.println("c:" + Arrays.toString(c)); 812 System.out.println("n:" + Arrays.toString(n)); 813 } 814 815 DBox f = null; 816 817 while (feasiblePointFound && (f = findForbiddenDomain(o, currentShape, c, dir, order)) != null) { 818 819 assert f.containsPoint(c) : "bad forbidden region, c is not contained"; 820 821 //update n 822 for (int i = 0, size = o.dimension + 1; i < size; i++) { 823 824 n[i] = Math.min(n[i], f.origin[i] + f.length[i]); 825 assert n[i] > c[i] : "n is not larger than c in pruneMin"; 826 827 } 828 829 feasiblePointFound = false; 830 //sweep in each dimension, from the less significant to the most 831 832 for (int i = o.dimension; i >= 0; i--) { 833 834 int lexI = order.dimensionAt(i); 835 836 final int domainMin = lexI != dimension ? o.coords[lexI].min() : o.start.min(); 837 final int domainMax = lexI != dimension ? o.coords[lexI].max() : o.start.max(); 838 839 c[lexI] = n[lexI]; 840 n[lexI] = domainMax + 1; 841 842 if (c[lexI] <= domainMax) { 843 feasiblePointFound = true; 844 break; 845 } else { 846 assert feasiblePointFound == false; 847 c[lexI] = domainMin; 848 } 849 } 850 851 if (c[d] >= limit) 852 //we were asked to stop searching here 853 return limit; 854 855 // if(USE_DISPLAY) { 856 // display.display2DBox(f, Color.red); 857 // display.display2DPoint(c, Color.green); 858 // display.display2DPoint(n, Color.blue); 859 // } 860 861 if (DEBUG_MAIN) { 862 System.out.println("outbox found, c and n:"); 863 System.out.println("c:" + Arrays.toString(c)); 864 System.out.println("n:" + Arrays.toString(n)); 865 } 866 867 } 868 869 if (feasiblePointFound) { 870 assert 871 c[d] >= (d != dimension ? o.coords[d].min() : o.start.min()) : 872 "feasible point found " + c[d] + " is outside domain " + (d != dimension ? o.coords[d] : o.start); 873 return c[d]; // the check for sweep advance is done later by the consistency function 874 } else 875 return IntDomain.MaxInt; 876 877 } 878 879 /** 880 * the sweeping routine for minimal bounds. Since in the polymorphic case, it is run for each possible shape, 881 * and only the weakest result is used, it cannot have side-effects. In particular, it cannot 882 * directly update domain values. 883 * If any data structure is updated here, make sure that it is done carefully enough. 884 * 885 * @param store the store 886 * @param o the object to prune 887 * @param d the current most significant dimension 888 * @param currentShape the shape of the object 889 * @param limit stop pruning if going beyond this value 890 * @return the bound found if there is one, and Constants.MinInt if there is no feasible placement. 891 */ pruneMax(Store store, GeostObject o, int currentShape, int d, int limit)892 protected int pruneMax(Store store, GeostObject o, int currentShape, int d, 893 // Set<InternalConstraint> I, 894 int limit) { 895 896 boolean feasiblePointFound = true; 897 898 // if(USE_DISPLAY) 899 // display.eraseAll(); 900 901 if (DEBUG_MAIN) { 902 System.out.println("pruneMax"); 903 } 904 905 Geost.SweepDirection dir = Geost.SweepDirection.PRUNEMAX; 906 order.setMostSignificantDimension(d); 907 908 //c is initialized with the upper bound of the object's domain, n with the lower bound-1 909 for (int i = 0, size = o.dimension; i < size; i++) { 910 c[i] = o.coords[i].max(); 911 n[i] = o.coords[i].min() - 1; 912 } 913 //when considering time, pruneMax will try to reduce the upper bound of the domain (start+duration) 914 c[dimension] = o.end.max(); 915 n[dimension] = o.end.min() - 1; 916 917 if (DEBUG_MAIN) { 918 System.out.println("shape ID in pruneMax: " + currentShape); 919 } 920 if (DEBUG_MAIN) { 921 System.out.println("initial c and n:"); 922 System.out.println("c:" + Arrays.toString(c)); 923 System.out.println("n:" + Arrays.toString(n)); 924 } 925 926 DBox f = null; 927 while (feasiblePointFound && (f = findForbiddenDomain(o, currentShape, c, dir, order)) != null) { 928 929 assert f.containsPoint(c) : "bad forbidden region, c is not contained"; 930 931 //update n 932 for (int i = 0, size = o.dimension + 1; i < size; i++) { 933 /* 934 * need to subtract 1 to the origin of the outbox because we want 935 * the next feasible point, and the outbox origin is still infeasible 936 */ 937 n[i] = Math.max(n[i], f.origin[i] - 1); 938 939 assert n[i] < c[i] : "n is not smaller than c in pruneMax"; 940 } 941 942 feasiblePointFound = false; 943 //sweep in each dimension, from the less significant to the most 944 for (int i = o.dimension; i >= 0; i--) { 945 int lexI = order.dimensionAt(i); 946 final int domainMin = lexI != dimension ? o.coords[lexI].min() : o.end.min(); 947 final int domainMax = lexI != dimension ? o.coords[lexI].max() : o.end.max(); 948 949 c[lexI] = n[lexI]; 950 n[lexI] = domainMin - 1; 951 952 if (c[lexI] >= domainMin) { 953 feasiblePointFound = true; 954 break; 955 } else { 956 assert feasiblePointFound == false; 957 c[lexI] = domainMax; 958 } 959 960 // if(USE_DISPLAY){ 961 // display.display2DBox(f, Color.red); 962 // display.display2DPoint(c, Color.green); 963 // display.display2DPoint(n, Color.blue); 964 // } 965 966 } 967 if (c[d] <= limit) { 968 //we were asked to stop searching here 969 return limit; 970 } 971 972 if (DEBUG_MAIN) { 973 System.out.println("outbox found, c and n:"); 974 System.out.println("c:" + Arrays.toString(c)); 975 System.out.println("n:" + Arrays.toString(n)); 976 } 977 978 } 979 980 if (feasiblePointFound) { 981 assert 982 c[d] <= (d != dimension ? o.coords[d].max() : o.end.max()) : 983 "feasible point found " + c[d] + " is outside domain " + (d != dimension ? o.coords[d] : o.end); 984 return c[d]; // the check for sweep advance is done later by the consistency function 985 } else 986 return IntDomain.MinInt; 987 988 } 989 findForbiddenDomain(GeostObject o, int currentShape, int[] point, Geost.SweepDirection dir, LexicographicalOrder order)990 protected DBox findForbiddenDomain(GeostObject o, int currentShape, int[] point, 991 // Collection<InternalConstraint> constraints, 992 Geost.SweepDirection dir, LexicographicalOrder order) { 993 994 if (DEBUG_MAIN) { 995 // System.out.println("findForbidenDomain: constraints:" + constraints.size()); 996 System.out.println("shape ID in findForbiddenDomain: " + currentShape); 997 } 998 999 if (GATHER_STATS) 1000 findForbiddenDomainCount++; 1001 1002 // assert constraints != null : "not using correct version"; 1003 1004 //if there are holes in the domain, consider these first 1005 DomainHoles holeConstraint = domainHolesConstraints[o.no]; 1006 1007 if (DomainHoles.debug) { 1008 System.out.println("checking for holes of object " + o); 1009 System.out.println("associated constraint: " + holeConstraint); 1010 } 1011 1012 // If the hole within domain can be used to generate the outbox then it is checked first. 1013 if (holeConstraint.stillHasHole()) { 1014 1015 if (GATHER_STATS) 1016 isFeasibleCount++; 1017 1018 DBox f = holeConstraint.isFeasible(dir, order, o, currentShape, point); 1019 1020 if (f != null) 1021 return f; 1022 1023 } 1024 1025 if (GATHER_STATS) 1026 // BUG? 1027 // length is not ok to use since this array is allocated initially based on the count of 1028 // ALL internal constraints for all objects and not the internal constraints associated with 1029 // a given object. Should be objectConstraints[o.id].size() ? 1030 filteredConstraintCount += stillUsefulInternalConstraints.length - lastConstraintToCheck; 1031 1032 //then go on with the standard filtered constraints 1033 for (int ci = lastConstraintToCheck - 1; ci >= 0; ci--) { 1034 1035 final InternalConstraint c = stillUsefulInternalConstraints[ci]; 1036 1037 if (GATHER_STATS) 1038 isFeasibleCount++; 1039 1040 DBox f = c.isFeasible(dir, order, o, currentShape, point); 1041 1042 if (f != null) 1043 return f; 1044 1045 } 1046 1047 return null; 1048 } 1049 consistency(Store store)1050 @Override @SuppressWarnings("all") public void consistency(Store store) { 1051 1052 try { 1053 1054 inConsistency = true; 1055 changedShapeID = false; 1056 1057 if (DEBUG_MAIN || DEBUG_SHAPE_SKIP || DEBUG_VAR_SKIP || DEBUG_OBJECT_GROUNDING) 1058 System.out.println("consistency(" + store.level + ")"); 1059 1060 if (firstConsistencyCheck) { 1061 1062 // enforce duration > 0 constraint 1063 1064 for (GeostObject o : objects) { 1065 o.timeConstraint.consistencyDurationGtZero(store); 1066 1067 if (o.timeConstraint.consistencyStartPlusDurationEqEnd(store)) { 1068 // queueObject(o); 1069 onObjectUpdate(o); 1070 } 1071 1072 } 1073 1074 firstConsistencyCheck = false; 1075 firstConsistencyLevel = store.level; 1076 1077 } 1078 1079 1080 if (partialShapeSweep) 1081 Arrays.fill(fullyPruned, false); 1082 1083 //update the objects that are defined by some variables that changed 1084 flushQueue(variableQueue); 1085 1086 while (!objectQueue.isEmpty()) { 1087 1088 GeostObject o = objectQueue.removeFirst(); 1089 1090 boolean emptyQueue = false; 1091 1092 //an object can be in the queue even though it is grounded, 1093 //if it was grounded twice in the same pruning 1094 while (o.isGrounded() && !pruneIfGrounded[o.no] && !emptyQueue) 1095 if (!objectQueue.isEmpty()) 1096 o = objectQueue.removeFirst(); 1097 else 1098 emptyQueue = true; 1099 1100 if (emptyQueue) 1101 break; // all objects done, get out of consistency() 1102 1103 // object o will be checked now and since it is grounded then there is no need for 1104 // another check after that. 1105 pruneIfGrounded[o.no] = false; 1106 1107 if (DEBUG_OBJECT_GROUNDING) 1108 System.out.println("pruning object " + o); 1109 1110 1111 boolean fullSweep = true; 1112 if (partialShapeSweep) { 1113 //if object already had a full sweep in this node, do partial sweep only 1114 if (fullyPruned[o.no] == true) 1115 fullSweep = false; 1116 else 1117 fullyPruned[o.no] = true; 1118 } 1119 1120 updateInternalConstraintsGeneratingOutboxes(o); 1121 1122 if (DEBUG_MAIN || DEBUG_SHAPE_SKIP || DEBUG_VAR_SKIP || DEBUG_OBJECT_GROUNDING) { 1123 1124 System.out.println("pruning " + o); 1125 1126 if (DEBUG_SHAPE_SKIP) 1127 System.out.println("o.bestShapeID = " + Arrays.toString(o.bestShapeID)); 1128 1129 } 1130 1131 boolean inconsistent = false; 1132 1133 // Sweep using master ordering. Later on, for each dimension in the 1134 // loop below we will be changing most significant dimension. 1135 int[] ordering = order.masterOrdering(); 1136 1137 for (int di = 0, size = dimension + 1; di < size; di++) { //time is the additional dimension 1138 1139 int d = ordering[di]; 1140 1141 /* 1142 * if the variable is a singleton and is not in the variable queue, 1143 * it means that it has been either grounded or checked by geost. 1144 * If no shape was removed, result would not change, therefore there is 1145 * no need to run the pruning for that variable 1146 * Another exception is if shapeID is not a singleton. Indeed, in this case, 1147 * we may be able to remove a shape that is not useful. 1148 */ 1149 boolean needPruning = true; 1150 //if no shape ID changed and o.shapeID is a singleton, consider skipping variable 1151 if (!changedShapeID && o.shapeID.singleton()) 1152 if (d != dimension) { 1153 final Var prunedVar = o.coords[d]; 1154 needPruning = !(prunedVar.singleton() && !variableQueue.contains(prunedVar)); 1155 } else { 1156 needPruning = !(o.start.singleton() && o.end.singleton() && !variableQueue.contains(o.start) && !variableQueue 1157 .contains(o.end) && !variableQueue.contains(o.duration)); 1158 1159 } 1160 1161 if (enforceNoSkip) 1162 needPruning = true; 1163 1164 if (needPruning) { 1165 1166 // It specifies the lowest lower bound found for the origin across multiple shapes. 1167 int minLowerBound = IntDomain.MaxInt; 1168 // It specifies the highest upper bound for for the origin across multiple shapes. 1169 int maxUpperBound = IntDomain.MinInt; 1170 1171 int lastSidIndex = 0; 1172 boolean bestShapeIDFound = false; 1173 int bestSidLastPrune = o.bestShapeID[d]; 1174 1175 final ValueEnumeration vals = o.shapeID.domain.valueEnumeration(); 1176 while (vals.hasMoreElements()) { 1177 1178 int sid = vals.nextElement(); 1179 1180 if (sid == bestSidLastPrune) { 1181 bestShapeIDFound = true; 1182 shapeIdsToPrune[0] = sid; 1183 } else { 1184 lastSidIndex++; 1185 shapeIdsToPrune[lastSidIndex] = sid; 1186 } 1187 1188 } 1189 1190 if (!bestShapeIDFound) { 1191 //best shape ID was removed from o.shapeID 1192 shapeIdsToPrune[0] = shapeIdsToPrune[lastSidIndex]; 1193 assert lastSidIndex >= 1; 1194 lastSidIndex--; 1195 } 1196 1197 1198 int bestLowerBound = IntDomain.MaxInt; 1199 int bestUpperBound = IntDomain.MinInt; 1200 1201 for (int i = 0; i <= lastSidIndex; i++) { 1202 1203 int sid = shapeIdsToPrune[i]; 1204 1205 if (DEBUG_MAIN) 1206 System.out.println("shape ID in consistency: " + sid); 1207 1208 if (GATHER_STATS) 1209 pruneMinCount++; 1210 1211 int lowerBound = pruneMin(store, o, sid, d, 1212 // internalConstraintsToUse, 1213 fullSweep ? IntDomain.MaxInt : minLowerBound); 1214 1215 if (lowerBound >= IntDomain.MaxInt) { 1216 1217 //remove shape ID, it is infeasible 1218 if (DEBUG_DOUBLE_LAYER) 1219 System.out.println("geost " + id() + " changing " + o.shapeID + ", removing " + sid); 1220 1221 changedShapeID = true; 1222 1223 //don't skip objects again if some shape ID changed 1224 Arrays.fill(pruneIfGrounded, true); 1225 1226 // o.shapeID.domain.in(store.level, o.shapeID, o.shapeID.domain.subtract(sid)); 1227 // CHANGED. replaced the above with the line below. 1228 o.shapeID.domain.inComplement(store.level, o.shapeID, sid); 1229 1230 } else { 1231 1232 minLowerBound = Math.min(minLowerBound, lowerBound); 1233 1234 //consider pruning in the other direction only if the first did not fail 1235 if (GATHER_STATS) 1236 pruneMaxCount++; 1237 1238 int upperBound = pruneMax(store, o, sid, d, 1239 // internalConstraintsToUse, 1240 fullSweep ? IntDomain.MinInt : maxUpperBound); 1241 1242 if (upperBound <= IntDomain.MinInt) { 1243 1244 //remove shape ID, it is infeasible 1245 if (DEBUG_DOUBLE_LAYER) 1246 System.out.println("geost " + id() + " changing " + o.shapeID + ", removing " + sid); 1247 1248 changedShapeID = true; 1249 1250 //don't skip objects if some shape ID changed 1251 Arrays.fill(pruneIfGrounded, true); 1252 1253 // o.shapeID.domain.in(store.level, o.shapeID, o.shapeID.domain.subtract(sid)); 1254 // CHANGED. replaced the above with the line below. 1255 o.shapeID.domain.inComplement(store.level, o.shapeID, sid); 1256 1257 } else { 1258 maxUpperBound = Math.max(maxUpperBound, upperBound); 1259 1260 //update bestShapeID if better than previous one 1261 if (lowerBound <= bestLowerBound && upperBound >= bestUpperBound) { 1262 bestLowerBound = lowerBound; 1263 bestUpperBound = upperBound; 1264 o.bestShapeID[d] = sid; 1265 } 1266 1267 } 1268 } 1269 } 1270 1271 assert minLowerBound > IntDomain.MinInt; 1272 assert maxUpperBound < IntDomain.MaxInt; 1273 1274 if (minLowerBound < IntDomain.MaxInt) { 1275 1276 IntVar prunedVariable = d != dimension ? o.coords[d] : o.start; 1277 1278 if (DEBUG_DOUBLE_LAYER) 1279 if (minLowerBound > prunedVariable.min()) 1280 System.out.println("geost " + id() + " changing " + prunedVariable + " min bound to " + minLowerBound); 1281 1282 prunedVariable.domain.inMin(store.level, prunedVariable, minLowerBound); 1283 1284 if (oneTimeVarChanged) { 1285 o.timeConstraint.consistencyStartPlusDurationEqEnd(store); 1286 // if(o.timeConstraint.consistencyStartPlusDurationEqEnd(store)) 1287 // //modification of some of the time variables, sweep again 1288 // queueObject(o); 1289 oneTimeVarChanged = false; 1290 } 1291 1292 } else 1293 inconsistent = true; 1294 1295 if (!inconsistent && maxUpperBound > IntDomain.MinInt) { 1296 1297 IntVar prunedVariable = d != dimension ? o.coords[d] : o.end; 1298 1299 if (DEBUG_DOUBLE_LAYER) 1300 if (maxUpperBound < prunedVariable.max()) 1301 System.out.println("geost " + id() + " changing " + prunedVariable + " max bound to " + maxUpperBound); 1302 1303 prunedVariable.domain.inMax(store.level, prunedVariable, maxUpperBound); 1304 1305 if (oneTimeVarChanged) { 1306 o.timeConstraint.consistencyStartPlusDurationEqEnd(store); 1307 // if(o.timeConstraint.consistencyStartPlusDurationEqEnd(store)) 1308 // //modification of some of the time variables, sweep again 1309 // queueObject(o); 1310 oneTimeVarChanged = false; 1311 } 1312 1313 } else 1314 inconsistent = true; 1315 1316 } 1317 } 1318 1319 if (inconsistent) 1320 throw Store.failException; 1321 1322 if (DEBUG_MAIN) { 1323 System.out.print("pruned " + o); 1324 System.out.println(""); //just to place breakpoint 1325 } 1326 1327 1328 } 1329 1330 1331 //backtracking data storage 1332 if (!updatedObjectSet.isEmpty()) { 1333 // if(setStart.stamp() < store.level) { 1334 1335 // TODO, think of easy way of preventing multiple objects being put to the list at the same level. 1336 //need to create the set for this level 1337 //flush last set 1338 for (GeostObject uo : updatedObjectSet) 1339 objectList.add(uo); 1340 1341 updatedObjectSet.clear(); 1342 1343 //mark beginning of new set 1344 setStart.update(objectList.size()); 1345 1346 if (DEBUG_BACKTRACK) 1347 System.out.println("new set, begins at " + setStart.value() + ", stamp: " + setStart); 1348 1349 } 1350 1351 1352 } finally { 1353 1354 inConsistency = false; 1355 variableQueue.clear(); 1356 1357 objectQueue.clear(); 1358 // objectQueue.clear();//may not be empty if an exception was raised 1359 1360 } 1361 } 1362 1363 1364 /** 1365 * It is called whenever the object currently being pruned changes. 1366 * useful for constraint pruning version of Geost. 1367 * 1368 * @param o the object currently being pruned for which internal constraints are being filtered. 1369 */ updateInternalConstraintsGeneratingOutboxes(GeostObject o)1370 protected void updateInternalConstraintsGeneratingOutboxes(GeostObject o) { 1371 1372 if (filterUseless) { 1373 1374 //maximal possible size of the object 1375 workingList.clearNoGC(); 1376 ValueEnumeration sids = o.shapeID.domain.valueEnumeration(); 1377 1378 while (sids.hasMoreElements()) 1379 workingList.add(getShape(sids.nextElement()).boundingBox); 1380 1381 // bb - boundingBox over all shapes. 1382 DBox bb = DBox.boundingBox(workingList).copyInto(DBox.newBox(dimension)); 1383 1384 1385 // bounds of the domain and the bounding box over all possible shapes counted above. 1386 DBox domainBox = DBox.newBox(dimension + 1); 1387 int[] domainBoxOriginShifted = domainBox.origin; 1388 int[] domainBoxLengthShifted = domainBox.length; 1389 1390 for (int i = 0; i < dimension; i++) { 1391 domainBoxOriginShifted[i] = o.coords[i].min() + bb.origin[i]; 1392 domainBoxLengthShifted[i] = o.coords[i].max() + bb.origin[i] + bb.length[i] - domainBoxOriginShifted[i]; 1393 } 1394 //TODO cache the results of the computation above and recompute upon object change. 1395 1396 domainBoxOriginShifted[dimension] = IntDomain.MinInt; 1397 domainBoxLengthShifted[dimension] = IntDomain.MaxInt * 2; 1398 1399 // it finds the box within which the constraint can propagate. 1400 DBox constraintBox = DBox.newBox(dimension + 1); 1401 int[] constraintBoxOrigin = constraintBox.origin; 1402 int[] constraintBoxLength = constraintBox.length; 1403 1404 lastConstraintToCheck = 0; 1405 for (InternalConstraint c : objectConstraints[o.no]) 1406 if (c.cardInfeasible() > 0) { 1407 1408 //increase size by one unit because intersection is empty if of size zero 1409 int[] lowerBound = c.absInfeasible(Geost.SweepDirection.PRUNEMIN); 1410 for (int i = 0; i < dimension + 1; i++) 1411 constraintBoxOrigin[i] = lowerBound[i] - 1; 1412 1413 //note: need to to them one after the other because of array reuse in absInfeasible 1414 int[] upperBound = c.absInfeasible(Geost.SweepDirection.PRUNEMAX); 1415 for (int i = 0; i < dimension + 1; i++) 1416 constraintBoxLength[i] = upperBound[i] - constraintBoxOrigin[i] + 2; 1417 1418 // if the constraint can propagate within current domains then the internal 1419 // constraint can be useful and can not be filtered out, otherwise the constraint 1420 // is not added to the list of useful constraints. 1421 if (domainBox.intersectWith(constraintBox) != null) { 1422 stillUsefulInternalConstraints[lastConstraintToCheck] = c; 1423 lastConstraintToCheck++; 1424 } 1425 1426 } 1427 1428 DBox.dispatchBox(bb); 1429 DBox.dispatchBox(constraintBox); 1430 DBox.dispatchBox(domainBox); 1431 1432 } else { 1433 1434 lastConstraintToCheck = 0; 1435 for (InternalConstraint c : objectConstraints[o.no]) 1436 if (c.cardInfeasible() > 0) { 1437 stillUsefulInternalConstraints[lastConstraintToCheck] = c; 1438 lastConstraintToCheck++; 1439 } 1440 1441 } 1442 1443 if (DEBUG_REORDER) 1444 System.out.println("changed pruning object"); 1445 1446 } 1447 1448 1449 /** 1450 * It does the processing needed given the set of variables that was updated 1451 * between two consecutive calls to the consistency function. 1452 * 1453 * @param variables variables in the queue 1454 */ flushQueue(Collection<Var> variables)1455 protected void flushQueue(Collection<Var> variables) { 1456 1457 objectList4Flush.clearNoGC(); 1458 1459 for (Var v : variables) { 1460 1461 GeostObject o = variableObjectMap.get(v); 1462 1463 if (o == null) 1464 // can be ignored as the variable was singleton upon imposition. 1465 continue; 1466 1467 //if it is a time variable, run time constraint 1468 if (v == o.start || v == o.end || v == o.duration) 1469 o.timeConstraint.consistencyStartPlusDurationEqEnd(store); 1470 else if (v == o.shapeID) 1471 //some shape ID was changed by some external source, remember it 1472 changedShapeID = true; 1473 1474 objectList4Flush.add(o); 1475 } 1476 1477 for (GeostObject o : objectList4Flush) 1478 onObjectUpdate(o); 1479 } 1480 1481 /** 1482 * It puts the object into the queue if it can be still pruned or cause failure. 1483 * 1484 * @param o the object which is possibly put into the queue. 1485 */ queueObject(GeostObject o)1486 final public void queueObject(GeostObject o) { 1487 1488 // Important to keep and ensure. 1489 assert (inConsistency) : "It is improperly called outside the consistency function."; 1490 1491 if (!(o.isGrounded() && pruneIfGrounded[o.no] == false)) { 1492 1493 if (DEBUG_OBJECT_GROUNDING) 1494 System.out.println("queued " + o); 1495 1496 if (GATHER_STATS) 1497 queuedObjectCount++; 1498 1499 objectQueue.add(o); 1500 1501 1502 } else if (DEBUG_OBJECT_GROUNDING) 1503 System.out.println("The object " + o + " was skipped."); 1504 1505 1506 } 1507 1508 /** 1509 * It performs the necessary operations for a given changed object. 1510 * <p> 1511 * If the change occurred due to backtracking then only external constraints 1512 * are being informed about the change, so they can restore proper state in 1513 * connection to the object. If this function is not called during backtracking 1514 * then also the following is executed. 1515 * <p> 1516 * If the change occurs due to search progress downwards then it stores 1517 * the information about object change as well as schedules pruning 1518 * check for all connected objects. 1519 * 1520 * @param o the object which had a domain change 1521 */ onObjectUpdate(GeostObject o)1522 protected void onObjectUpdate(GeostObject o) { 1523 1524 if (GATHER_STATS) 1525 onObjectUpdateCount++; 1526 1527 if (DEBUG_MAIN) 1528 System.out.println("adding objects to the queue"); 1529 1530 /** 1531 * for now, all constraints are applied to all objects, so the set of objects 1532 * connected by an external constraint to o is the whole set of objects 1533 * (see technical report, page 12, last phrase in the algorithm caption) 1534 * 1535 */ 1536 for (ExternalConstraint ec : externalConstraints) 1537 ec.onObjectUpdate(o); 1538 1539 1540 //no need to queue objects if backtracking 1541 if (!backtracking) { 1542 1543 //add object to the set of this level 1544 updatedObjectSet.add(o); 1545 1546 if (DEBUG_BACKTRACK) 1547 System.out.println("updating object " + o); 1548 1549 if (allLinked) { 1550 //executing the else part would end up in the same result 1551 for (GeostObject lo : objects) 1552 queueObject(lo); 1553 1554 } else { 1555 1556 queueObject(o); // needed because if dimension 1 was pruned, dimension 0 might now be pruned 1557 1558 temporaryObjectSet.clear(); 1559 1560 for (ExternalConstraint ec : externalConstraints) { 1561 1562 ec.addPrunableObjects(o, temporaryObjectSet); 1563 while (!temporaryObjectSet.isEmpty()) 1564 queueObject(temporaryObjectSet.removeFirst()); 1565 1566 } 1567 1568 } 1569 } 1570 1571 } 1572 getConsistencyPruningEvent(Var var)1573 @Override public int getConsistencyPruningEvent(Var var) { 1574 1575 // If consistency function mode 1576 if (consistencyPruningEvents != null) { 1577 Integer possibleEvent = consistencyPruningEvents.get(var); 1578 if (possibleEvent != null) 1579 return possibleEvent; 1580 } 1581 1582 GeostObject o = variableObjectMap.get(var); 1583 1584 if (o == null) 1585 return Domain.NONE; 1586 1587 if (o.shapeID == var) 1588 return IntDomain.ANY; 1589 1590 return IntDomain.BOUND; 1591 1592 } 1593 getDefaultConsistencyPruningEvent()1594 @Override public int getDefaultConsistencyPruningEvent() { 1595 throw new IllegalStateException("Not implemented as more precise implementation exists."); 1596 1597 } 1598 impose(Store store)1599 @Override public void impose(Store store) { 1600 1601 super.impose(store); 1602 1603 this.store = store; 1604 1605 lastLevelLastVar = new TimeStamp<Integer>(store, store.level); 1606 lastLevelLastVar.update(-1); 1607 1608 genInternalConstraints(); 1609 1610 store.registerRemoveLevelLateListener(this); 1611 1612 setStart = new TimeStamp<Integer>(store, store.level); 1613 setStart.update(0); 1614 1615 objectList = new SimpleArrayList<GeostObject>(); 1616 updatedObjectSet = new HashSet<GeostObject>(); 1617 1618 } 1619 increaseWeight()1620 @Override public void increaseWeight() { 1621 1622 if (increaseWeight) 1623 for (GeostObject o : objects) 1624 for (Var v : o.getVariables()) 1625 v.weight++; 1626 1627 } 1628 1629 1630 private int currentLevel; 1631 1632 /** 1633 * It specifies the first position of the variables being removed 1634 * from grounded list upon backtracking. 1635 * <p> 1636 * If there is no change in lastLevelVar.value between removeLevel ( 1637 * stored in removeLimit) and removeLevelLate then this indicates 1638 * that no variable was grounded at removed level. 1639 */ 1640 private int removeLimit; 1641 queueVariable(int level, Var v)1642 @Override @SuppressWarnings("all") public void queueVariable(int level, Var v) { 1643 1644 currentLevel = level; 1645 1646 if (v.singleton()) { 1647 1648 GeostObject o = variableObjectMap.get(v); 1649 1650 if (o == null) { 1651 // can be ignored as the variable was singleton upon imposition. 1652 return; 1653 } 1654 1655 o.onGround(v); 1656 1657 if (DEBUG_OBJECT_GROUNDING) 1658 System.out.println("grounding " + v); 1659 1660 if (!inConsistency) 1661 pruneIfGrounded[o.no] = true; 1662 1663 if (lastLevelLastVar.stamp() < store.level) 1664 lastLevelLastVar.update(groundedVars.size()); 1665 1666 groundedVars.add(v); 1667 } 1668 1669 if (inConsistency) { 1670 1671 assert (variableObjectMap.containsKey(v) || v.singleton()) : "The variable " + v + " does not exist in variable-object map."; 1672 1673 //if this variable can modify the sweep result, process it right away 1674 GeostObject o = variableObjectMap.get(v); 1675 1676 if (o == null) { 1677 // can be ignored as the variable was singleton upon imposition. 1678 return; 1679 } 1680 1681 //if it is a time variable, run time constraint 1682 if (v == o.start || v == o.end || v == o.duration) 1683 oneTimeVarChanged = true; 1684 1685 1686 onObjectUpdate(o); 1687 1688 } else { 1689 // keep it for later 1690 variableQueue.add(v); 1691 } 1692 1693 1694 if (DEBUG_VAR_SKIP || DEBUG_OBJECT_GROUNDING) 1695 if (inConsistency) 1696 System.out.println("The variable " + v + " was pruned by geost consistency function itself"); 1697 else 1698 System.out.println("The variable " + v + " was pruned by outside constraints and it is queued as changed within geost"); 1699 1700 1701 } 1702 1703 removeLevel(int level)1704 @Override @SuppressWarnings("all") public void removeLevel(int level) { 1705 1706 // added. 1707 if (level > currentLevel) 1708 return; 1709 1710 if (DEBUG_MAIN || DEBUG_SHAPE_SKIP || DEBUG_VAR_SKIP || DEBUG_OBJECT_GROUNDING) 1711 System.out.println("removeLevel(" + store.level + ")"); 1712 1713 assert !inConsistency; 1714 1715 if (firstConsistencyLevel == level) 1716 firstConsistencyCheck = true; 1717 1718 removeLimit = lastLevelLastVar.value(); 1719 1720 // lowerBound = setStart.value(); 1721 } 1722 removeLevelLate(int level)1723 @Override public void removeLevelLate(int level) { 1724 1725 assert !inConsistency; 1726 1727 // added. to mask a bug if multiple remove levels are being executed for the same level. 1728 if (level > currentLevel) 1729 return; 1730 1731 if (lastLevelLastVar.value() < removeLimit) 1732 for (int i = groundedVars.size() - 1; i >= removeLimit; i--) { 1733 1734 Var v = groundedVars.remove(i); 1735 assert v != null; 1736 1737 if (DEBUG_OBJECT_GROUNDING) 1738 System.out.println("The variable " + v + " is being ungrounded"); 1739 1740 // no need to check for null as only not null variables are put in groundedVars. 1741 variableObjectMap.get(v).onUnGround(v); 1742 } 1743 1744 backtracking = true; 1745 1746 if (!updatedObjectSet.isEmpty()) 1747 for (GeostObject o : updatedObjectSet) { 1748 1749 onObjectUpdate(o); 1750 if (DEBUG_BACKTRACK) 1751 System.out.println("restored object " + o); 1752 } 1753 1754 updatedObjectSet.clear(); 1755 1756 int lowerBound = setStart.value(); 1757 for (int i = objectList.size() - 1; i >= lowerBound; i--) { 1758 1759 GeostObject o = objectList.remove(i); 1760 1761 assert o != null; 1762 1763 // if(!updatedObjectSet.contains(o)) 1764 // // else it was already updated 1765 onObjectUpdate(o); 1766 1767 if (DEBUG_BACKTRACK) 1768 System.out.println("restored object " + o); 1769 1770 } 1771 1772 /** 1773 * It is cleared out as the objects changed at the level being removed are no longer needed. 1774 */ 1775 // updatedObjectSet.clear(); 1776 1777 backtracking = false; 1778 1779 } 1780 toString()1781 @Override public String toString() { 1782 //TODO, proper string representation of the constraint. 1783 return "Geost"; 1784 } 1785 1786 1787 /** 1788 * It returns all the statistics gathered by geost constraint during the search. 1789 * 1790 * @return an array list consisting of different statistics collected during search. 1791 */ getStatistics()1792 public List<Long> getStatistics() { 1793 1794 List<Long> stats = new ArrayList<Long>(); 1795 1796 stats.add(pruneMinCount); 1797 stats.add(pruneMaxCount); 1798 stats.add(findForbiddenDomainCount); 1799 stats.add(isFeasibleCount); 1800 stats.add(onObjectUpdateCount); 1801 stats.add(queuedObjectCount); 1802 stats.add(filteredConstraintCount); 1803 1804 return stats; 1805 1806 } 1807 1808 /** 1809 * @author Marc-Olivier Fleury and Radoslaw Szymanek 1810 * <p> 1811 * It specifies in what direction the sweep algorithm is progressing. 1812 */ 1813 1814 public enum SweepDirection { 1815 /** 1816 * The sweep algorithm prunes the minimal values for the origins. 1817 */ 1818 PRUNEMIN, /** 1819 * The sweep algorithm prunes the maximal values for the origins. 1820 */ 1821 PRUNEMAX 1822 } 1823 1824 1825 } 1826