1 /* 2 * Assignment.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 package org.jacop.constraints; 32 33 import org.jacop.api.SatisfiedPresent; 34 import org.jacop.api.Stateful; 35 import org.jacop.api.UsesQueueVariable; 36 import org.jacop.core.*; 37 38 import java.util.Arrays; 39 import java.util.LinkedHashSet; 40 import java.util.List; 41 import java.util.Map; 42 import java.util.concurrent.atomic.AtomicInteger; 43 import java.util.stream.Stream; 44 45 /** 46 * Assignment constraint implements facility to improve channeling constraints 47 * between dual viewpoints of permutation models. 48 * It enforces the relationship x[d[i]-shiftX]=i+shiftD and d[x[i]-shiftD]=i+shiftX. 49 * 50 * @author Radoslaw Szymanek and Krzysztof Kuchcinski 51 * @version 4.8 52 */ 53 54 public class Assignment extends Constraint implements UsesQueueVariable, Stateful, SatisfiedPresent { 55 56 final static AtomicInteger idNumber = new AtomicInteger(0); 57 58 /** 59 * It specifies a list of variables d. 60 */ 61 final public IntVar d[]; 62 63 /** 64 * It specifies a shift applied to variables d. 65 */ 66 public int shiftD = 0; 67 68 Map<IntVar, Integer> ds; 69 70 /** 71 * It specifies a list of variables x. 72 */ 73 public IntVar x[]; 74 /** 75 * It specifies a shift applied to variables x. 76 */ 77 public int shiftX = 0; 78 79 Map<IntVar, Integer> xs; 80 81 82 LinkedHashSet<IntVar> variableQueue = new LinkedHashSet<IntVar>(); 83 boolean firstConsistencyCheck = true; 84 int firstConsistencyLevel; 85 86 /** 87 * It enforces the relationship x[d[i]-shiftX]=i+shiftD and 88 * d[x[i]-shiftD]=i+shiftX. 89 * 90 * @param xs array of variables x 91 * @param ds array of variables d 92 * @param shiftX a shift of indexes in X array. 93 * @param shiftD a shift of indexes in D array. 94 */ Assignment(IntVar[] xs, IntVar[] ds, int shiftX, int shiftD)95 public Assignment(IntVar[] xs, IntVar[] ds, int shiftX, int shiftD) { 96 97 checkInputForNullness(new String[] {"xs", "ds"}, xs, ds); 98 99 numberId = idNumber.incrementAndGet(); 100 101 this.shiftX = shiftX; 102 this.shiftD = shiftD; 103 this.x = Arrays.copyOf(xs, xs.length); 104 this.d = Arrays.copyOf(ds, ds.length); 105 this.queueIndex = 1; 106 107 this.xs = Var.createEmptyPositioning(); 108 this.ds = Var.createEmptyPositioning(); 109 110 for (int i = 0; i < xs.length; i++) { 111 this.xs.put(x[i], i + shiftX); 112 this.ds.put(d[i], i + shiftD); 113 } 114 115 setScope(Stream.concat(Arrays.stream(xs), Arrays.stream(ds))); 116 117 } 118 119 /** 120 * It enforces the relationship x[d[i]-shiftX]=i+shiftD and 121 * d[x[i]-shiftD]=i+shiftX. 122 * 123 * @param xs arraylist of variables x 124 * @param ds arraylist of variables d 125 * @param shiftX shift for parameter xs 126 * @param shiftD shift for parameter ds 127 */ Assignment(List<? extends IntVar> xs, List<? extends IntVar> ds, int shiftX, int shiftD)128 public Assignment(List<? extends IntVar> xs, List<? extends IntVar> ds, int shiftX, int shiftD) { 129 this(xs.toArray(new IntVar[xs.size()]), ds.toArray(new IntVar[ds.size()]), shiftX, shiftD); 130 } 131 132 133 /** 134 * It constructs an Assignment constraint with shift equal 0. It 135 * enforces relation - d[x[j]] = i and x[d[i]] = j. 136 * 137 * @param xs arraylist of x variables 138 * @param ds arraylist of d variables 139 */ Assignment(List<? extends IntVar> xs, List<? extends IntVar> ds)140 public Assignment(List<? extends IntVar> xs, List<? extends IntVar> ds) { 141 this(xs.toArray(new IntVar[xs.size()]), ds.toArray(new IntVar[ds.size()]), 0, 0); 142 } 143 144 /** 145 * It enforces the relationship x[d[i]-min]=i+min and 146 * d[x[i]-min]=i+min. 147 * 148 * @param xs arraylist of variables x 149 * @param ds arraylist of variables d 150 * @param min shift 151 */ Assignment(List<? extends Var> xs, List<? extends Var> ds, int min)152 public Assignment(List<? extends Var> xs, List<? extends Var> ds, int min) { 153 this(xs.toArray(new IntVar[xs.size()]), ds.toArray(new IntVar[ds.size()]), min, min); 154 } 155 156 157 /** 158 * It constructs an Assignment constraint with shift equal 0. It 159 * enforces relation - d[x[i]] = i and x[d[i]] = i. 160 * 161 * @param xs array of x variables 162 * @param ds array of d variables 163 */ Assignment(IntVar[] xs, IntVar[] ds)164 public Assignment(IntVar[] xs, IntVar[] ds) { 165 this(xs, ds, 0, 0); 166 } 167 168 /** 169 * It enforces the relationship x[d[i]-min]=i+min and 170 * d[x[i]-min]=i+min. 171 * 172 * @param xs array of variables x 173 * @param ds array of variables d 174 * @param min shift 175 */ Assignment(IntVar[] xs, IntVar[] ds, int min)176 public Assignment(IntVar[] xs, IntVar[] ds, int min) { 177 this(xs, ds, min, min); 178 } 179 removeLevel(int level)180 @Override public void removeLevel(int level) { 181 variableQueue.clear(); 182 if (level == firstConsistencyLevel) 183 firstConsistencyCheck = true; 184 } 185 186 187 IntervalDomain rangeX; 188 IntervalDomain rangeD; 189 consistency(Store store)190 @Override public void consistency(Store store) { 191 192 if (firstConsistencyCheck) { 193 194 rangeX = new IntervalDomain(0 + shiftX, x.length - 1 + shiftX); 195 196 rangeD = new IntervalDomain(0 + shiftD, x.length - 1 + shiftD); 197 198 for (int i = 0; i < x.length; i++) { 199 200 IntDomain alreadyRemoved = rangeD.subtract(x[i].domain); 201 202 x[i].domain.in(store.level, x[i], shiftD, x.length - 1 + shiftD); 203 204 if (!alreadyRemoved.isEmpty()) 205 for (ValueEnumeration enumer = alreadyRemoved.valueEnumeration(); enumer.hasMoreElements(); ) { 206 207 int xValue = enumer.nextElement(); 208 209 d[xValue - shiftD].domain.inComplement(store.level, d[xValue - shiftD], i + shiftX); 210 211 } 212 213 if (x[i].singleton()) { 214 int position = x[i].value() - shiftD; 215 d[position].domain.in(store.level, d[position], i + shiftX, i + shiftX); 216 } 217 218 } 219 220 for (int i = 0; i < d.length; i++) { 221 222 IntDomain alreadyRemoved = rangeX.subtract(d[i].domain); 223 224 d[i].domain.in(store.level, d[i], shiftX, x.length - 1 + shiftX); 225 226 if (!alreadyRemoved.isEmpty()) 227 for (ValueEnumeration enumer = alreadyRemoved.valueEnumeration(); enumer.hasMoreElements(); ) { 228 229 int dValue = enumer.nextElement(); 230 231 x[dValue - shiftX].domain.inComplement(store.level, x[dValue - shiftX], i + shiftD); 232 233 } 234 235 if (d[i].singleton()) { 236 237 x[d[i].value() - shiftX].domain.in(store.level, x[d[i].value() - shiftX], i + shiftD, i + shiftD); 238 } 239 240 } 241 242 firstConsistencyCheck = false; 243 firstConsistencyLevel = store.level; 244 245 } 246 247 while (!variableQueue.isEmpty()) { 248 249 LinkedHashSet<IntVar> fdvs = variableQueue; 250 251 variableQueue = new LinkedHashSet<IntVar>(); 252 253 for (IntVar V : fdvs) { 254 255 IntDomain vPrunedDomain = V.recentDomainPruning(); 256 257 if (!vPrunedDomain.isEmpty()) { 258 259 Integer position = xs.get(V); 260 if (position == null) { 261 // d variable has been changed 262 position = ds.get(V); 263 264 vPrunedDomain = vPrunedDomain.intersect(rangeX); 265 266 if (vPrunedDomain.isEmpty()) 267 continue; 268 269 for (ValueEnumeration enumer = vPrunedDomain.valueEnumeration(); enumer.hasMoreElements(); ) { 270 271 int dValue = enumer.nextElement() - shiftX; 272 273 if (dValue >= 0 && dValue < x.length) 274 x[dValue].domain.inComplement(store.level, x[dValue], position); 275 } 276 277 if (V.singleton()) 278 x[V.value() - shiftX].domain.in(store.level, x[V.value() - shiftX], position, position); 279 280 } else { 281 // x variable has been changed 282 283 vPrunedDomain = vPrunedDomain.intersect(rangeD); 284 285 if (vPrunedDomain.isEmpty()) 286 continue; 287 288 for (ValueEnumeration enumer = vPrunedDomain.valueEnumeration(); enumer.hasMoreElements(); ) { 289 290 int xValue = enumer.nextElement() - shiftD; 291 292 if (xValue >= 0 && xValue < d.length) 293 d[xValue].domain.inComplement(store.level, d[xValue], position); 294 295 if (V.singleton()) 296 d[V.value() - shiftD].domain.in(store.level, d[V.value() - shiftD], position, position); 297 298 } 299 300 } 301 302 } 303 304 } 305 306 } 307 308 } 309 satisfied()310 @Override public boolean satisfied() { 311 312 if (!grounded()) 313 return false; 314 315 for (int i = 0; i < x.length; i++) { 316 int position = x[i].value() - shiftD; 317 if (d[position].value() != i + shiftX) { 318 return false; 319 } 320 } 321 322 for (int i = 0; i < d.length; i++) { 323 if (x[d[i].value() - shiftX].value() != i + shiftD) { 324 return false; 325 } 326 } 327 328 return true; 329 330 } 331 332 getDefaultConsistencyPruningEvent()333 public int getDefaultConsistencyPruningEvent() { 334 return IntDomain.ANY; 335 } 336 337 // registers the constraint in the constraint store impose(Store store)338 @Override public void impose(Store store) { 339 340 super.impose(store); 341 342 store.raiseLevelBeforeConsistency = true; 343 344 } 345 queueVariable(int level, Var var)346 @Override public void queueVariable(int level, Var var) { 347 variableQueue.add((IntVar) var); 348 } 349 toString()350 @Override public String toString() { 351 352 StringBuffer result = new StringBuffer(id()); 353 354 result.append(" : assignment(["); 355 356 for (int i = 0; i < x.length; i++) { 357 result.append(x[i]); 358 if (i < x.length - 1) 359 result.append(", "); 360 } 361 result.append("], ["); 362 363 for (int i = 0; i < d.length; i++) { 364 result.append(d[i]); 365 if (i < d.length - 1) 366 result.append(", "); 367 } 368 result.append("], "); 369 result.append(shiftX + ", " + shiftD + ")"); 370 371 return result.toString(); 372 } 373 374 } 375