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 for (int i = 2; i < mylits.length; i++) {
138 mylits[i - 1] = mylits[i];
139 }
140 mylits[mylits.length - 1] = previous;
141 this.voc.watch(p, this);
142 // propagates first watched literal
143 return s.enqueue(mylits[0], this);
144 }
145
146 /*
147 * For learnt clauses only @author leberre
148 */
149 public boolean locked() {
150 return this.voc.getReason(this.lits[0]) == this;
151 }
152
153 /**
154 * @return the activity of the clause
155 */
156 public double getActivity() {
157 return this.activity;
158 }
159
160 public void setActivity(double d) {
161 this.activity = d;
162 }
163
164 @Override
165 public String toString() {
166 StringBuffer stb = new StringBuffer();
167 for (int lit : this.lits) {
168 stb.append(Lits.toString(lit));
169 stb.append("["); //$NON-NLS-1$
170 stb.append(this.voc.valueToString(lit));
171 stb.append("]"); //$NON-NLS-1$
172 stb.append(" "); //$NON-NLS-1$
173 }
174 return stb.toString();
175 }
176
177 /**
178 * Retourne le ieme literal de la clause. Attention, cet ordre change durant
179 * la recherche.
180 *
181 * @param i
182 * the index of the literal
183 * @return the literal
184 */
185 public int get(int i) {
186 return this.lits[i];
187 }
188
189 /**
190 * @param d
191 */
192 public void rescaleBy(double d) {
193 this.activity *= d;
194 }
195
196 public int size() {
197 return this.lits.length;
198 }
199
200 public void assertConstraint(UnitPropagationListener s) {
201 boolean ret = s.enqueue(this.lits[0], this);
202 assert ret;
203 }
204
205 public ILits getVocabulary() {
206 return this.voc;
207 }
208
209 public int[] getLits() {
210 int[] tmp = new int[size()];
211 System.arraycopy(this.lits, 0, tmp, 0, size());
212 return tmp;
213 }
214
215 @Override
216 public boolean equals(Object obj) {
217 if (obj == null) {
218 return false;
219 }
220 try {
221 WLClause wcl = (WLClause) obj;
222 if (this.lits.length != wcl.lits.length) {
223 return false;
224 }
225 boolean ok;
226 for (int lit : this.lits) {
227 ok = false;
228 for (int lit2 : wcl.lits) {
229 if (lit == lit2) {
230 ok = true;
231 break;
232 }
233 }
234 if (!ok) {
235 return false;
236 }
237 }
238 return true;
239 } catch (ClassCastException e) {
240 return false;
241 }
242 }
243
244 @Override
245 public int hashCode() {
246 long sum = 0;
247 for (int p : this.lits) {
248 sum += p;
249 }
250 return (int) sum / this.lits.length;
251 }
252
253 public boolean canBePropagatedMultipleTimes() {
254 return false;
255 }
256
257 public Constr toConstraint() {
258 return this;
259 }
260 }