001package org.cpsolver.ifs.extension;
002
003import java.util.ArrayList;
004import java.util.HashMap;
005import java.util.HashSet;
006import java.util.Iterator;
007import java.util.List;
008import java.util.Map;
009import java.util.Set;
010
011import org.cpsolver.ifs.assignment.Assignment;
012import org.cpsolver.ifs.assignment.context.AssignmentContext;
013import org.cpsolver.ifs.assignment.context.ExtensionWithContext;
014import org.cpsolver.ifs.model.Constraint;
015import org.cpsolver.ifs.model.Value;
016import org.cpsolver.ifs.model.Variable;
017import org.cpsolver.ifs.solver.Solver;
018import org.cpsolver.ifs.util.DataProperties;
019import org.cpsolver.ifs.util.Progress;
020
021
022/**
023 * Another implementation of MAC propagation.
024 * 
025 * @see MacPropagation
026 * 
027 * @version IFS 1.3 (Iterative Forward Search)<br>
028 *          Copyright (C) 2006 - 2014 Tomas Muller<br>
029 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
030 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
031 * <br>
032 *          This library is free software; you can redistribute it and/or modify
033 *          it under the terms of the GNU Lesser General Public License as
034 *          published by the Free Software Foundation; either version 3 of the
035 *          License, or (at your option) any later version. <br>
036 * <br>
037 *          This library is distributed in the hope that it will be useful, but
038 *          WITHOUT ANY WARRANTY; without even the implied warranty of
039 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
040 *          Lesser General Public License for more details. <br>
041 * <br>
042 *          You should have received a copy of the GNU Lesser General Public
043 *          License along with this library; if not see
044 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
045 * @param <V> Variable
046 * @param <T> Value
047 */
048
049public class MacRevised<V extends Variable<V, T>, T extends Value<V, T>> extends ExtensionWithContext<V, T, MacRevised<V, T>.NoGood> {
050    private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(MacRevised.class);
051    private boolean iDbt = false;
052    private Progress iProgress;
053
054    /** List of constraints on which arc-consistency is to be maintained */
055    protected List<Constraint<V, T>> iConstraints = null;
056    /** Current iteration */
057    protected long iIteration = 0;
058
059    /** Constructor 
060     * @param solver current solver
061     * @param properties solver configuration
062     **/
063    public MacRevised(Solver<V, T> solver, DataProperties properties) {
064        super(solver, properties);
065        iDbt = properties.getPropertyBoolean("MacRevised.Dbt", false);
066    }
067
068    /** Adds a constraint on which arc-consistency is to be maintained 
069     * @param constraint a hard constraint to be added
070     **/
071    public void addConstraint(Constraint<V, T> constraint) {
072        if (iConstraints == null)
073            iConstraints = new ArrayList<Constraint<V, T>>();
074        iConstraints.add(constraint);
075    }
076
077    /**
078     * Returns true, if arc-consistency is to be maintained on the given
079     * constraint
080     * @param constraint a constraint
081     * @return true if the constraint is in the set
082     */
083    public boolean contains(Constraint<V, T> constraint) {
084        if (iConstraints == null)
085            return true;
086        return iConstraints.contains(constraint);
087    }
088
089    /**
090     * Before a value is unassigned: until the value is inconsistent with the
091     * current solution, an assignment from its explanation is picked and
092     * unassigned.
093     */
094    @Override
095    public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) {
096        if (value == null)
097            return;
098        sLogger.debug("Before assign " + value.variable().getName() + " = " + value.getName());
099        iIteration = iteration;
100        while (!isGood(assignment, value) && !noGood(assignment, value).isEmpty()) {
101            if (iDbt)
102                sLogger.warn("Going to assign a no-good value " + value + " (noGood:" + noGood(assignment, value) + ").");
103            T noGoodValue = noGood(assignment, value).iterator().next();
104            assignment.unassign(iteration, noGoodValue.variable());
105        }
106        if (!isGood(assignment, value)) {
107            sLogger.warn("Going to assign a bad value " + value + " with empty no-good.");
108        }
109    }
110
111    /**
112     * After a value is assigned: explanations of other values of the value's
113     * variable are reset (to contain only the assigned value), propagation over
114     * the assigned variable takes place.
115     */
116    @Override
117    public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) {
118        sLogger.debug("After assign " + value.variable().getName() + " = " + value.getName());
119        iIteration = iteration;
120        if (!isGood(assignment, value)) {
121            sLogger.warn(value.variable().getName() + " = " + value.getName() + " -- not good value assigned (noGood:" + noGood(assignment, value) + ")");
122            setGood(assignment, value);
123        }
124
125        Set<T> noGood = new HashSet<T>(1);
126        noGood.add(value);
127        List<T> queue = new ArrayList<T>();
128        for (Iterator<T> i = value.variable().values(assignment).iterator(); i.hasNext();) {
129            T anotherValue = i.next();
130            if (anotherValue.equals(value) || !isGood(assignment, anotherValue))
131                continue;
132            setNoGood(assignment, anotherValue, noGood);
133            queue.add(anotherValue);
134        }
135        propagate(assignment, queue);
136    }
137
138    /**
139     * After a value is unassigned: explanations of all values of unassigned
140     * variable are recomputed ({@link Value#conflicts(Assignment)}), propagation undo
141     * over the unassigned variable takes place.
142     */
143    @Override
144    public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) {
145        sLogger.debug("After unassign " + value.variable().getName() + " = " + value.getName());
146        iIteration = iteration;
147        if (!isGood(assignment, value))
148            sLogger.error(value.variable().getName() + " = " + value.getName()
149                    + " -- not good value unassigned (noGood:" + noGood(assignment, value) + ")");
150
151        List<T> back = new ArrayList<T>(supportValues(assignment, value.variable()));
152        for (T aValue : back) {
153            T current = assignment.getValue(aValue.variable());
154            if (current != null) {
155                Set<T> noGood = new HashSet<T>(1);
156                noGood.add(current);
157                setNoGood(assignment, aValue, noGood);
158            } else
159                setGood(assignment, aValue);
160        }
161
162        List<T> queue = new ArrayList<T>();
163        for (T aValue : back) {
164            if (!isGood(assignment, aValue) || revise(assignment, aValue))
165                queue.add(aValue);
166        }
167
168        propagate(assignment, queue);
169    }
170
171    public void propagate(Assignment<V, T> assignment, List<T> queue) {
172        int idx = 0;
173        while (queue.size() > idx) {
174            T value = queue.get(idx++);
175            sLogger.debug("  -- propagate " + value.variable().getName() + " = " + value.getName() + " (noGood:"
176                    + noGood(assignment, value) + ")");
177            if (goodValues(assignment, value.variable()).isEmpty()) {
178                sLogger.info("Empty domain detected for variable " + value.variable().getName());
179                continue;
180            }
181            for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
182                if (!contains(constraint))
183                    continue;
184                propagate(assignment, constraint, value, queue);
185            }
186        }
187    }
188
189    public void propagate(Assignment<V, T> assignment, Constraint<V, T> constraint, T noGoodValue, List<T> queue) {
190        for (V aVariable : constraint.variables()) {
191            if (aVariable.equals(noGoodValue.variable()))
192                continue;
193            for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) {
194                T aValue = j.next();
195                if (isGood(assignment, aValue) && constraint.isConsistent(noGoodValue, aValue)
196                        && !hasSupport(assignment, constraint, aValue, noGoodValue.variable())) {
197                    setNoGood(assignment, aValue, explanation(assignment, constraint, aValue, noGoodValue.variable()));
198                    queue.add(aValue);
199                }
200            }
201        }
202    }
203
204    public boolean revise(Assignment<V, T> assignment, T value) {
205        sLogger.debug("  -- revise " + value.variable().getName() + " = " + value.getName());
206        for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
207            if (!contains(constraint))
208                continue;
209            if (revise(assignment, constraint, value))
210                return true;
211        }
212        return false;
213    }
214
215    public boolean revise(Assignment<V, T> assignment, Constraint<V, T> constraint, T value) {
216        for (V aVariable : constraint.variables()) {
217            if (aVariable.equals(value.variable()))
218                continue;
219            if (!hasSupport(assignment, constraint, value, aVariable)) {
220                setNoGood(assignment, value, explanation(assignment, constraint, value, aVariable));
221                return true;
222            }
223        }
224        return false;
225    }
226
227    public Set<T> explanation(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) {
228        Set<T> expl = new HashSet<T>();
229        for (T aValue : variable.values(assignment)) {
230            if (constraint.isConsistent(aValue, value)) {
231                expl.addAll(noGood(assignment, aValue));
232            }
233        }
234        return expl;
235    }
236
237    public Set<T> supports(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) {
238        Set<T> sup = new HashSet<T>();
239        for (T aValue : variable.values(assignment)) {
240            if (!isGood(assignment, aValue))
241                continue;
242            if (!constraint.isConsistent(aValue, value))
243                continue;
244            sup.add(aValue);
245        }
246        return sup;
247    }
248
249    public boolean hasSupport(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) {
250        for (T aValue : variable.values(assignment)) {
251            if (isGood(assignment, aValue) && constraint.isConsistent(aValue, value)) {
252                // sLogger.debug("    -- "+variable.getName()+" = "+aValue.getName()+" supports "
253                // +
254                // value.variable().getName()+" = "+value.getName()+" (constraint:"+constraint.getName()+")");
255                return true;
256            }
257        }
258        // sLogger.debug("    -- value "+value.variable().getName()+" = " +
259        // value.getName()+" has no support from values of variable "+variable.getName()+" (constraint:"+constraint.getName()+")");
260        /*
261         * for (Enumeration e=variable.values().elements();e.hasMoreElements();)
262         * { T aValue = (T)e.nextElement(); if
263         * (constraint.isConsistent(aValue,value)) {
264         * //sLogger.debug("      -- support "
265         * +aValue.getName()+" is not good: "+expl2str(noGood(aValue))); } }
266         */
267        return false;
268    }
269
270    /**
271     * Initialization. Enforce arc-consistency over the current (initial)
272     * solution. AC3 algorithm is used.
273     */
274    @Override
275    public boolean init(Solver<V, T> solver) {
276        return true;
277    }
278
279    /** support values of a variable */
280    @SuppressWarnings("unchecked")
281    private Set<T> supportValues(Assignment<V, T> assignment, V variable) {
282        Set<T>[] ret = getContext(assignment).getNoGood(variable);
283        if (ret == null) {
284            ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() };
285            getContext(assignment).setNoGood(variable, ret);
286        }
287        return ret[0];
288    }
289
290    /** good values of a variable (values not removed from variables domain) 
291     * @param assignment current assignment 
292     * @param variable given variable
293     * @return good values for the variable (i.e., values from the domain of the variable that have no no-good set)
294     **/
295    @SuppressWarnings("unchecked")
296    public Set<T> goodValues(Assignment<V, T> assignment, V variable) {
297        Set<T>[] ret = getContext(assignment).getNoGood(variable);
298        if (ret == null) {
299            ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() };
300            getContext(assignment).setNoGood(variable, ret);
301        }
302        return ret[1];
303    }
304
305    /** notification that a no-good value becomes good or vice versa */
306    private void goodnessChanged(Assignment<V, T> assignment, T value) {
307        if (isGood(assignment, value)) {
308            goodValues(assignment, value.variable()).add(value);
309        } else {
310            goodValues(assignment, value.variable()).remove(value);
311        }
312    }
313
314    /** removes support of a variable */
315    private void removeSupport(Assignment<V, T> assignment, V variable, T value) {
316        supportValues(assignment, variable).remove(value);
317    }
318
319    /** adds support of a variable */
320    private void addSupport(Assignment<V, T> assignment, V variable, T value) {
321        supportValues(assignment, variable).add(value);
322    }
323
324    /** variables explanation 
325     * @param assignment current assignment
326     * @param value given value
327     * @return no-good set for the value 
328     **/
329    public Set<T> noGood(Assignment<V, T> assignment, T value) {
330        return getContext(assignment).getNoGood(value);
331    }
332
333    /** is variable good 
334     * @param assignment current assignment
335     * @param value given value
336     * @return true if good, i.e., the value has no no-good set 
337     **/
338    public boolean isGood(Assignment<V, T> assignment, T value) {
339        return (getContext(assignment).getNoGood(value) == null);
340    }
341
342    /** sets value to be good 
343     * @param assignment current assignment
344     * @param value given value
345     **/
346    protected void setGood(Assignment<V, T> assignment, T value) {
347        sLogger.debug("    -- set good " + value.variable().getName() + " = " + value.getName());
348        Set<T> noGood = noGood(assignment, value);
349        if (noGood != null)
350            for (T v : noGood)
351                removeSupport(assignment, v.variable(), value);
352        getContext(assignment).setNoGood(value, null);
353        goodnessChanged(assignment, value);
354    }
355
356    /** sets values explanation (initialization) */
357    private void initNoGood(Assignment<V, T> assignment, T value, Set<T> reason) {
358        getContext(assignment).setNoGood(value, reason);
359    }
360
361    private String expl2str(Set<T> expl) {
362        StringBuffer sb = new StringBuffer("[");
363        for (Iterator<T> i = expl.iterator(); i.hasNext();) {
364            T value = i.next();
365            sb.append(value.variable().getName() + "=" + value.getName());
366            if (i.hasNext())
367                sb.append(", ");
368        }
369        sb.append("]");
370        return sb.toString();
371    }
372
373    private void checkExpl(Assignment<V, T> assignment, Set<T> expl) {
374        sLogger.debug("    -- checking explanation: " + expl2str(expl));
375        for (Iterator<T> i = expl.iterator(); i.hasNext();) {
376            T value = i.next();
377            T current = assignment.getValue(value.variable());
378            if (!value.equals(current)) {
379                if (current == null)
380                    sLogger.warn("      -- variable " + value.variable().getName() + " unassigned");
381                else
382                    sLogger.warn("      -- variable " + value.variable().getName() + " assigned to a different value " + current.getName());
383            }
384        }
385    }
386
387    private void printAssignments(Assignment<V, T> assignment) {
388        sLogger.debug("    -- printing assignments: ");
389        for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
390            V variable = i.next();
391            T value = assignment.getValue(variable);
392            if (value != null)
393                sLogger.debug("      -- " + variable.getName() + " = " + value.getName());
394        }
395    }
396
397    /** sets value's explanation 
398     * @param assignment current assignment
399     * @param value a value
400     * @param reason no-good set for the value
401     **/
402    public void setNoGood(Assignment<V, T> assignment, T value, Set<T> reason) {
403        sLogger.debug("    -- set nogood " + value.variable().getName() + " = " + value.getName() + "(expl:" + expl2str(reason) + ")");
404        if (value.equals(assignment.getValue(value.variable()))) {
405            try {
406                throw new Exception("An assigned value " + value.variable().getName() + " = " + value.getName() + " become no good (noGood:" + reason + ")!!");
407            } catch (Exception e) {
408                sLogger.warn(e.getMessage(), e);
409            }
410            checkExpl(assignment, reason);
411            printAssignments(assignment);
412        }
413        Set<T> noGood = noGood(assignment, value);
414        if (noGood != null)
415            for (T v : noGood)
416                removeSupport(assignment, v.variable(), value);
417        getContext(assignment).setNoGood(value, reason);
418        for (T aValue : reason) {
419            addSupport(assignment, aValue.variable(), value);
420        }
421        goodnessChanged(assignment, value);
422    }
423    
424    @Override
425    public NoGood createAssignmentContext(Assignment<V, T> assignment) {
426        return new NoGood(assignment);
427    }
428
429    /**
430     * Assignment context
431     */
432    public class NoGood implements AssignmentContext {
433        private Map<V, Set<T>[]> iNoGood = new HashMap<V, Set<T>[]>();
434        private Map<V, Map<T, Set<T>>> iNoGoodVal = new HashMap<V, Map<T, Set<T>>>();
435        
436        public NoGood(Assignment<V, T> assignment) {
437            iProgress = Progress.getInstance(getModel());
438            iProgress.save();
439            iProgress.setPhase("Initializing propagation:", getModel().variables().size());
440            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
441                V aVariable = i.next();
442                supportValues(assignment, aVariable).clear();
443                goodValues(assignment, aVariable).clear();
444            }
445            List<T> queue = new ArrayList<T>();
446            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
447                V aVariable = i.next();
448                for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) {
449                    T aValue = j.next();
450                    initNoGood(assignment, aValue, null);
451                    goodValues(assignment, aVariable).add(aValue);
452                    T current = assignment.getValue(aVariable);
453                    if (revise(assignment, aValue)) {
454                        queue.add(aValue);
455                    } else if (current != null && !aValue.equals(current)) {
456                        Set<T> noGood = new HashSet<T>();
457                        noGood.add(current);
458                        MacRevised.this.setNoGood(assignment, aValue, noGood);
459                        queue.add(aValue);
460                    }
461                }
462                iProgress.incProgress();
463            }
464            propagate(assignment, queue);
465            iProgress.restore();
466        }
467        
468        public Set<T>[] getNoGood(V variable) {
469            return iNoGood.get(variable);
470        }
471        
472        public void setNoGood(V variable, Set<T>[] noGood) {
473            if (noGood == null)
474                iNoGood.remove(variable);
475            else
476                iNoGood.put(variable, noGood);
477        }
478        
479        public Set<T> getNoGood(T value) {
480            Map<T, Set<T>> ng = iNoGoodVal.get(value.variable());
481            if (ng == null) return null;
482            return ng.get(value);
483        }
484        
485        public void setNoGood(T value, Set<T> noGood) {
486            Map<T, Set<T>> ng = iNoGoodVal.get(value.variable());
487            if (ng == null) {
488                ng = new HashMap<T, Set<T>>();
489                iNoGoodVal.put(value.variable(), ng);
490            }
491            if (noGood == null)
492                ng.remove(value);
493            else
494                ng.put(value, noGood);
495        }
496    }
497}