1 /*******************************************************************************
2 * SAT4J: a SATisfiability library for Java Copyright (C) 2004, 2012 Artois University and CNRS
3 *
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
8 *
9 * Alternatively, the contents of this file may be used under the terms of
10 * either the GNU Lesser General Public License Version 2.1 or later (the
11 * "LGPL"), in which case the provisions of the LGPL are applicable instead
12 * of those above. If you wish to allow use of your version of this file only
13 * under the terms of the LGPL, and not to allow others to use your version of
14 * this file under the terms of the EPL, indicate your decision by deleting
15 * the provisions above and replace them with the notice and other provisions
16 * required by the LGPL. If you do not delete the provisions above, a recipient
17 * may use your version of this file under the terms of the EPL or the LGPL.
18 *
19 * Based on the original MiniSat specification from:
20 *
21 * An extensible SAT solver. Niklas Een and Niklas Sorensson. Proceedings of the
22 * Sixth International Conference on Theory and Applications of Satisfiability
23 * Testing, LNCS 2919, pp 502-518, 2003.
24 *
25 * See www.minisat.se for the original solver in C++.
26 *
27 * Contributors:
28 * CRIL - initial API and implementation
29 *******************************************************************************/
30 package org.sat4j.minisat.constraints.cnf;
31
32 import java.io.Serializable;
33
34 import org.sat4j.minisat.core.Constr;
35 import org.sat4j.minisat.core.ILits;
36 import org.sat4j.minisat.core.Propagatable;
37 import org.sat4j.minisat.core.UnitPropagationListener;
38 import org.sat4j.specs.IVecInt;
39
40 /**
41 * Lazy data structure for clause using Watched Literals.
42 *
43 * @author leberre
44 */
45 public abstract class WLClause implements Propagatable, Constr, Serializable {
46
47 private static final long serialVersionUID = 1L;
48
49 /**
50 * @since 2.1
51 */
52 protected double activity;
53
54 protected final int[] lits;
55
56 protected final ILits voc;
57
58 /**
59 * Creates a new basic clause
60 *
61 * @param voc
62 * the vocabulary of the formula
63 * @param ps
64 * A VecInt that WILL BE EMPTY after calling that method.
65 */
66 public WLClause(IVecInt ps, ILits voc) {
67 this.lits = new int[ps.size()];
68 ps.moveTo(this.lits);
69 assert ps.size() == 0;
70 this.voc = voc;
71 this.activity = 0;
72 }
73
74 /*
75 * (non-Javadoc)
76 *
77 * @see Constr#calcReason(Solver, Lit, Vec)
78 */
79 public void calcReason(int p, IVecInt outReason) {
80 // assert outReason.size() == 0
81 // && ((p == ILits.UNDEFINED) || (p == lits[0]));
82 final int[] mylits = this.lits;
83 for (int i = p == ILits.UNDEFINED ? 0 : 1; i < mylits.length; i++) {
84 assert this.voc.isFalsified(mylits[i]);
85 outReason.push(mylits[i] ^ 1);
86 }
87 }
88
89 /**
90 * @since 2.1
91 */
92 public void remove(UnitPropagationListener upl) {
93 this.voc.watches(this.lits[0] ^ 1).remove(this);
94 this.voc.watches(this.lits[1] ^ 1).remove(this);
95 // la clause peut etre effacee
96 }
97
98 /*
99 * (non-Javadoc)
100 *
101 * @see Constr#simplify(Solver)
102 */
103 public boolean simplify() {
104 for (int lit : this.lits) {
105 if (this.voc.isSatisfied(lit)) {
106 return true;
107 }
108 }
109 return false;
110 }
111
112 public boolean propagate(UnitPropagationListener s, int p) {
113 final int[] mylits = this.lits;
114 // Lits[1] must contain a falsified literal
115 if (mylits[0] == (p ^ 1)) {
116 mylits[0] = mylits[1];
117 mylits[1] = p ^ 1;
118 }
119 // assert mylits[1] == (p ^ 1);
120 int previous = p ^ 1, tmp;
121 // look for new literal to watch: applying move to front strategy
122 for (int i = 2; i < mylits.length; i++) {
123 if (this.voc.isFalsified(mylits[i])) {
124 tmp = previous;
125 previous = mylits[i];
126 mylits[i] = tmp;
127 } else {
128 mylits[1] = mylits[i];
129 mylits[i] = previous;
130 this.voc.watch(mylits[1] ^ 1, this);
131 return true;
132 }
133 }
134 // assert voc.isFalsified(mylits[1]);
135 // the clause is now either unit or null
136 // move back the literals to their initial position
137 System.arraycopy(mylits, 2, mylits, 1, mylits.length - 2);
138 mylits[mylits.length - 1] = previous;
139 this.voc.watch(p, this);
140 // propagates first watched literal
141 return s.enqueue(mylits[0], this);
142 }
143
144 /*
145 * For learnt clauses only @author leberre
146 */
147 public boolean locked() {
148 return this.voc.getReason(this.lits[0]) == this;
149 }
150
151 /**
152 * @return the activity of the clause
153 */
154 public double getActivity() {
155 return this.activity;
156 }
157
158 public void setActivity(double d) {
159 this.activity = d;
160 }
161
162 @Override
163 public String toString() {
164 StringBuffer stb = new StringBuffer();
165 for (int lit : this.lits) {
166 stb.append(Lits.toString(lit));
167 stb.append("["); //$NON-NLS-1$
168 stb.append(this.voc.valueToString(lit));
169 stb.append("]"); //$NON-NLS-1$
170 stb.append(" "); //$NON-NLS-1$
171 }
172 return stb.toString();
173 }
174
175 /**
176 * Retourne le ieme literal de la clause. Attention, cet ordre change durant
177 * la recherche.
178 *
179 * @param i
180 * the index of the literal
181 * @return the literal
182 */
183 public int get(int i) {
184 return this.lits[i];
185 }
186
187 /**
188 * @param d
189 */
190 public void rescaleBy(double d) {
191 this.activity *= d;
192 }
193
194 public int size() {
195 return this.lits.length;
196 }
197
198 public void assertConstraint(UnitPropagationListener s) {
199 boolean ret = s.enqueue(this.lits[0], this);
200 assert ret;
201 }
202
203 public ILits getVocabulary() {
204 return this.voc;
205 }
206
207 public int[] getLits() {
208 int[] tmp = new int[size()];
209 System.arraycopy(this.lits, 0, tmp, 0, size());
210 return tmp;
211 }
212
213 @Override
214 public boolean equals(Object obj) {
215 if (obj == null) {
216 return false;
217 }
218 try {
219 WLClause wcl = (WLClause) obj;
220 if (this.lits.length != wcl.lits.length) {
221 return false;
222 }
223 boolean ok;
224 for (int lit : this.lits) {
225 ok = false;
226 for (int lit2 : wcl.lits) {
227 if (lit == lit2) {
228 ok = true;
229 break;
230 }
231 }
232 if (!ok) {
233 return false;
234 }
235 }
236 return true;
237 } catch (ClassCastException e) {
238 return false;
239 }
240 }
241
242 @Override
243 public int hashCode() {
244 long sum = 0;
245 for (int p : this.lits) {
246 sum += p;
247 }
248 return (int) sum / this.lits.length;
249 }
250
251 public boolean canBePropagatedMultipleTimes() {
252 return false;
253 }
254
255 public Constr toConstraint() {
256 return this;
257 }
258
259 public void calcReasonOnTheFly(int p, IVecInt trail, IVecInt outReason) {
260 calcReason(p, outReason);
261 }
262 }