1 /* 2 * ExtensionalSupportMDD.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.core.IntDomain; 35 import org.jacop.core.IntVar; 36 import org.jacop.core.Store; 37 import org.jacop.core.TimeStamp; 38 import org.jacop.util.IndexDomainView; 39 import org.jacop.util.MDD; 40 import org.jacop.util.SparseSet; 41 42 import java.util.concurrent.atomic.AtomicInteger; 43 44 45 /** 46 * Extensional constraint assures that one of the tuples is enforced in the 47 * relation. 48 * <p> 49 * This implementation uses technique developed/improved by Roland Yap and his student. 50 * Paper presented at CP2008. We would like to thank Roland for answering our detailed 51 * questions about the implementation. It is a slightly improved version to what was 52 * presented at the conference. 53 * <p> 54 * This constraint uses a lot of memory, despite using an MDD. However, if the constraint 55 * is imposed multiple times (50+) its overall usage of memory maybe advantageous. Always 56 * test against STR version. 57 * 58 * @author Radoslaw Szymanek 59 * @version 4.8 60 */ 61 62 public class ExtensionalSupportMDD extends Constraint implements SatisfiedPresent { 63 64 /** 65 * It specifies if the debugging information is printed. 66 */ 67 public static final boolean debugAll = false; 68 69 static AtomicInteger idNumber = new AtomicInteger(0); 70 71 TimeStamp<Integer> G_no_size; 72 73 SparseSet G_no; 74 75 /** 76 * It specifies a multiple value decision diagram used by this constraint. 77 */ 78 public MDD mdd; 79 80 SparseSet G_yes; 81 82 IndexDomainView[] views; 83 84 /** 85 * It creates an extensional constraint. 86 * 87 * @param diagram multiple-valued decision diagram describing allowed tuples. 88 */ ExtensionalSupportMDD(MDD diagram)89 public ExtensionalSupportMDD(MDD diagram) { 90 91 checkInputForNullness("diagram", new Object[] {diagram}); 92 checkInputForNullness("diagram.vars", diagram.vars); 93 checkInputForNullness("diagram.views", diagram.views); 94 95 queueIndex = 1; 96 97 this.mdd = diagram; 98 this.views = diagram.views; 99 G_no = new SparseSet(diagram.freePosition); 100 numberId = idNumber.incrementAndGet(); 101 102 setScope(this.mdd.vars); 103 104 } 105 106 /** 107 * It constructs extensional support constraint. Please note 108 * that parameters will be stored internally as references 109 * until the impose of the constraint takes place. 110 * Changing parameters after constructing the constraint and 111 * before its imposition will change the constraint too. 112 * 113 * @param vars the variables in the scope of the constraint. 114 * @param table list of tuples which are allowed. 115 */ ExtensionalSupportMDD(IntVar[] vars, int[][] table)116 public ExtensionalSupportMDD(IntVar[] vars, int[][] table) { 117 this(new MDD(vars, table)); 118 } 119 impose(Store store)120 @Override public void impose(Store store) { 121 122 super.impose(store); 123 124 this.G_no_size = new TimeStamp<Integer>(store, 0); 125 126 store.raiseLevelBeforeConsistency = true; 127 128 if (mdd.freePosition > store.sparseSetSize) 129 store.sparseSetSize = mdd.freePosition; 130 131 } 132 133 // data structures to support for a given variable 134 // signaling what value index is supported. 135 consistency(Store s)136 @Override public void consistency(Store s) { 137 138 G_yes = s.sparseSet; 139 140 G_yes.clear(); 141 142 G_no.setSize(G_no_size.value()); 143 144 //TODO initialize notSupportedIndexesYes to 0..domainLimits 145 for (int i = 0; i < views.length; i++) 146 views[i].intializeSupportSweep(); 147 148 seekSupport(0, 0); 149 150 for (int i = 0; i < views.length; i++) 151 views[i].removeUnSupportedValues(s); 152 153 G_no_size.update(G_no.members); 154 155 } 156 157 /** 158 * It checks if the node at a given level of MDD has a support. 159 * 160 * @param nodeId the position of the node in the MDD. 161 * @param level number of variable associated with the node. 162 * @return true if node is supported by current domains of variables. 163 */ seekSupport(int nodeId, int level)164 public boolean seekSupport(int nodeId, int level) { 165 166 if (G_yes.isMember(nodeId)) 167 return true; 168 169 if (G_no.isMember(nodeId)) 170 return false; 171 172 173 boolean result = false; 174 175 // optimization possible if variable level-th did not change 176 177 for (int i = 0; i < mdd.domainLimits[level]; i++) { 178 int shift = nodeId + i; 179 if (mdd.diagram[shift] != MDD.NOEDGE) 180 if (views[level].contains(i)) 181 if (mdd.diagram[shift] == MDD.TERMINAL || seekSupport(mdd.diagram[shift], level + 1)) { 182 183 // ith-value has a support 184 // returns true is new support was found 185 // it always checks the preliminary finish condition 186 // at least once if new support was found. 187 if (!views[level].setSupport(i) || !result) { 188 189 result = true; 190 191 //TODO check if allIndexesSupported needs updating 192 // if it needs updating check the break condition below. 193 // break if for all following levels variables 194 // have all values been signaled as already supported 195 // notSupportYet is empty for all variables level..vars.length 196 197 int j = level; 198 for (; j < views.length && views[j].isSupported(); j++) 199 ; 200 if (j == views.length) 201 break; 202 203 } 204 205 } 206 } 207 208 if (result) 209 G_yes.addMember(nodeId); 210 else 211 G_no.addMember(nodeId); 212 213 return result; 214 215 } 216 getDefaultConsistencyPruningEvent()217 @Override public int getDefaultConsistencyPruningEvent() { 218 return IntDomain.ANY; 219 } 220 satisfied()221 @Override public boolean satisfied() { 222 return mdd.checkIfAllowed(); 223 } 224 225 toString()226 @Override public String toString() { 227 228 StringBuffer result = new StringBuffer(id()); 229 230 result.append(" : extensionalSupportMDD( "); 231 232 IntVar[] vars = mdd.vars; 233 234 for (int i = 0; i < vars.length; i++) 235 result.append(vars[i]).append(" "); 236 237 if (mdd.vars != null) 238 result.append(")").append("size = ").append(mdd.freePosition); 239 240 result.append(")\n"); 241 242 return result.toString(); 243 } 244 245 } 246