001package org.cpsolver.ifs.criteria;
002
003import java.util.ArrayList;
004import java.util.Collection;
005import java.util.Locale;
006import java.util.Map;
007import java.util.Set;
008
009import org.cpsolver.coursett.criteria.TimetablingCriterion;
010import org.cpsolver.ifs.assignment.Assignment;
011import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
012import org.cpsolver.ifs.assignment.context.AssignmentContext;
013import org.cpsolver.ifs.assignment.context.AssignmentContextHelper;
014import org.cpsolver.ifs.assignment.context.AssignmentContextReference;
015import org.cpsolver.ifs.assignment.context.CanHoldContext;
016import org.cpsolver.ifs.assignment.context.ConstraintWithContext;
017import org.cpsolver.ifs.assignment.context.HasAssignmentContext;
018import org.cpsolver.ifs.model.Constraint;
019import org.cpsolver.ifs.model.Model;
020import org.cpsolver.ifs.model.Value;
021import org.cpsolver.ifs.model.Variable;
022import org.cpsolver.ifs.solver.Solver;
023import org.cpsolver.ifs.util.DataProperties;
024
025
026/**
027 * Abstract Criterion. <br>
028 * <br>
029 * An optimization objective can be split into several (optimization) criteria
030 * and modeled as a weighted sum of these. This makes the implementation of a particular problem
031 * more versatile as it allows for an easier modification of the optimization objective.
032 * <br>
033 * This class implements most of the {@link Criterion} except of the {@link Criterion#getValue(Assignment, Value, Set)}.
034 * 
035 * @version IFS 1.3 (Iterative Forward Search)<br>
036 *          Copyright (C) 2006 - 2014 Tomas Muller<br>
037 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
038 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
039 * <br>
040 *          This library is free software; you can redistribute it and/or modify
041 *          it under the terms of the GNU Lesser General Public License as
042 *          published by the Free Software Foundation; either version 3 of the
043 *          License, or (at your option) any later version. <br>
044 * <br>
045 *          This library is distributed in the hope that it will be useful, but
046 *          WITHOUT ANY WARRANTY; without even the implied warranty of
047 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
048 *          Lesser General Public License for more details. <br>
049 * <br>
050 *          You should have received a copy of the GNU Lesser General Public
051 *          License along with this library; if not see
052 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
053 * @param <V> Variable
054 * @param <T> Value
055 */
056public abstract class AbstractCriterion<V extends Variable<V, T>, T extends Value<V, T>> implements Criterion<V, T>, HasAssignmentContext<V, T, AbstractCriterion<V,T>.ValueContext>, CanHoldContext {
057    private Model<V, T> iModel;
058    protected double iBest = 0.0, iWeight = 0.0;
059    protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.##",
060            new java.text.DecimalFormatSymbols(Locale.US));
061    protected static java.text.DecimalFormat sPercentFormat = new java.text.DecimalFormat("0.##",
062            new java.text.DecimalFormatSymbols(Locale.US));
063    protected boolean iDebug = false;
064    
065    private AssignmentContextReference<V, T, ValueContext> iContextReference = null;
066    private AssignmentContext[] iContext = new AssignmentContext[CanHoldContext.sMaxSize];
067    private int iLastCacheId = 0;
068
069    
070    /**
071     * Defines how the overall value of the criterion should be automatically updated (using {@link Criterion#getValue(Value, Set)}).
072     */
073    protected static enum ValueUpdateType {
074        /** Update is done before an unassignment (decrement) and before an assignment (increment). */
075        BeforeUnassignedBeforeAssigned,
076        /** Update is done after an unassignment (decrement) and before an assignment (increment). */
077        AfterUnassignedBeforeAssigned,
078        /** Update is done before an unassignment (decrement) and after an assignment (increment). */
079        BeforeUnassignedAfterAssigned,
080        /** Update is done after an unassignment (decrement) and after an assignment (increment). This is the default. */
081        AfterUnassignedAfterAssigned,
082        /** Criterion is to be updated manually (e.g., using {@link Criterion#inc(Assignment, double)}). */
083        NoUpdate
084    }
085    private ValueUpdateType iValueUpdateType = ValueUpdateType.BeforeUnassignedBeforeAssigned;
086
087    /** Defines weight name (to be used to get the criterion weight from the configuration). 
088     * @return name of the weight associated with this criterion
089     **/
090    public String getWeightName() {
091        return "Weight." + getClass().getName().substring(1 + getClass().getName().lastIndexOf('.'));
092    }
093    
094    /** Defines default weight (when {@link AbstractCriterion#getWeightName()} parameter is not present in the criterion).
095     * @param config solver configuration
096     * @return default criterion weight value
097     **/
098    public double getWeightDefault(DataProperties config) {
099        return 0.0;
100    }
101    
102    @Override
103    public void setModel(Model<V,T> model) {
104        iModel = model;
105        if (model != null)
106            iContextReference = model.createReference(this);
107    }
108
109    @Override
110    public boolean init(Solver<V, T> solver) {
111        iWeight = solver.getProperties().getPropertyDouble(getWeightName(), getWeightDefault(solver.getProperties()));
112        iDebug = solver.getProperties().getPropertyBoolean(
113                "Debug." + getClass().getName().substring(1 + getClass().getName().lastIndexOf('.')),
114                solver.getProperties().getPropertyBoolean("Debug.Criterion", false));
115        return true;
116    }
117    
118    /**
119     * Returns current model
120     * @return problem model
121     **/
122    public Model<V, T> getModel() { return iModel; }
123    
124    /**
125     * Returns an assignment context associated with this criterion. If there is no 
126     * assignment context associated with this criterion yet, one is created using the
127     * {@link ConstraintWithContext#createAssignmentContext(Assignment)} method. From that time on,
128     * this context is kept with the assignment and automatically updated by calling the
129     * {@link AssignmentConstraintContext#assigned(Assignment, Value)} and {@link AssignmentConstraintContext#unassigned(Assignment, Value)}
130     * whenever a variable is changed as given by the {@link ValueUpdateType}.
131     * @param assignment given assignment
132     * @return assignment context associated with this constraint and the given assignment
133     */
134    @Override
135    public ValueContext getContext(Assignment<V, T> assignment) {
136        return AssignmentContextHelper.getContext(this, assignment);
137    }
138    
139    @Override
140    public ValueContext createAssignmentContext(Assignment<V,T> assignment) {
141        return new ValueContext(assignment);
142    }
143
144    @Override
145    public AssignmentContextReference<V, T, ValueContext> getAssignmentContextReference() { return iContextReference; }
146
147    @Override
148    public void setAssignmentContextReference(AssignmentContextReference<V, T, ValueContext> reference) { iContextReference = reference; }
149
150    @Override
151    public AssignmentContext[] getContext() {
152        return iContext;
153    }
154    
155    @Override
156    public double getValue(Assignment<V, T> assignment) {
157        return getContext(assignment).getTotal();
158    }
159    
160    @Override
161    public double getBest() {
162        return iBest;
163    }
164    
165    @Override
166    public double getValue(Assignment<V, T> assignment, Collection<V> variables) {
167        double ret = 0;
168        for (V v: variables) {
169            T t = assignment.getValue(v);
170            if (t != null) ret += getValue(assignment, t, null);
171        }
172        return ret;
173    }
174
175    
176    @Override
177    public double getWeight() {
178        return iWeight;
179    }
180    
181    @Override
182    public double getWeightedBest() {
183        return getWeight() == 0.0 ? 0.0 : getWeight() * getBest();
184    }
185    
186    @Override
187    public double getWeightedValue(Assignment<V, T> assignment) {
188        return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment));
189    }
190    
191    @Override
192    public double getWeightedValue(Assignment<V, T> assignment, T value, Set<T> conflicts) {
193        return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment, value, conflicts));
194    }
195    
196    @Override
197    public double getWeightedValue(Assignment<V, T> assignment, Collection<V> variables) {
198        return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment, variables));
199    }
200
201    /** Compute bounds (bounds are being cached by default). 
202     * @param assignment current assignment
203     * @return minimum and maximum of this criterion's value
204     **/
205    protected double[] computeBounds(Assignment<V, T> assignment) {
206        return getBounds(assignment, new ArrayList<V>(getModel().variables()));
207    }
208
209    @Override
210    public double[] getBounds(Assignment<V, T> assignment) {
211        return getContext(assignment).getBounds(assignment);
212    }
213
214    @Override
215    public double[] getBounds(Assignment<V, T> assignment, Collection<V> variables) {
216        double[] bounds = new double[] { 0.0, 0.0 };
217        for (V v: variables) {
218            Double min = null, max = null;
219            for (T t: v.values(assignment)) {
220                double value = getValue(assignment, t, null);
221                if (min == null) { min = value; max = value; continue; }
222                min = Math.min(min, value);
223                max = Math.max(max, value);
224            }
225            if (min != null) {
226                bounds[0] += min;
227                bounds[1] += max;
228            }
229        }
230        return bounds;
231    }
232
233    @Override
234    public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) {
235        switch (getValueUpdateType()) {
236            case AfterUnassignedBeforeAssigned:
237            case BeforeUnassignedBeforeAssigned:
238                getContext(assignment).assigned(assignment, value);
239        }
240    }
241
242    @Override
243    public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) {
244        switch (getValueUpdateType()) {
245            case AfterUnassignedAfterAssigned:
246            case BeforeUnassignedAfterAssigned:
247                getContext(assignment).assigned(assignment, value);
248        }
249    }
250
251    @Override
252    public void beforeUnassigned(Assignment<V, T> assignment, long iteration, T value) {
253        switch (getValueUpdateType()) {
254            case BeforeUnassignedAfterAssigned:
255            case BeforeUnassignedBeforeAssigned:
256                getContext(assignment).unassigned(assignment, value);
257        }
258    }
259
260    @Override
261    public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) {
262        switch (getValueUpdateType()) {
263            case AfterUnassignedAfterAssigned:
264            case AfterUnassignedBeforeAssigned:
265                getContext(assignment).unassigned(assignment, value);
266        }
267    }
268
269    @Override
270    public void bestSaved(Assignment<V, T> assignment) {
271        iBest = getContext(assignment).getTotal();
272    }
273
274    @Override
275    public void bestRestored(Assignment<V, T> assignment) {
276        getContext(assignment).setTotal(iBest);
277    }
278    
279    @Override
280    public void inc(Assignment<V, T> assignment, double value) {
281        getContext(assignment).inc(value);
282    }   
283
284    @Override
285    public String getName() {
286        return getClass().getName().substring(1 + getClass().getName().lastIndexOf('.')).replaceAll("(?<=[^A-Z])([A-Z])"," $1");
287    }
288    
289    /** Clear bounds cache */
290    protected void clearCache() {
291        iLastCacheId++;
292    }
293    
294    @Override
295    public void variableAdded(V variable) {
296        clearCache();
297    }
298    
299    @Override
300    public void variableRemoved(V variable) {
301        clearCache();
302    }
303    
304    @Override
305    public void constraintAdded(Constraint<V, T> constraint) {
306        clearCache();
307    }
308    
309    @Override
310    public void constraintRemoved(Constraint<V, T> constraint) {
311        clearCache();
312    }
313    
314    protected String getPerc(double value, double min, double max) {
315        if (max == min)
316            return sPercentFormat.format(100.0);
317        return sPercentFormat.format(100.0 - 100.0 * (value - min) / (max - min));
318    }
319
320    protected String getPercRev(double value, double min, double max) {
321        if (max == min)
322            return sPercentFormat.format(0.0);
323        return sPercentFormat.format(100.0 * (value - min) / (max - min));
324    }
325
326    @Override
327    public void getInfo(Assignment<V, T> assignment, Map<String, String> info) {
328    }
329    
330    @Override
331    public void getInfo(Assignment<V, T> assignment, Map<String, String> info, Collection<V> variables) {
332    }
333    
334    @Override
335    public void getExtendedInfo(Assignment<V, T> assignment, Map<String, String> info) {
336        if (iDebug) {
337            double val = getValue(assignment), w = getWeightedValue(assignment), prec = getValue(assignment, getModel().variables());
338            double[] bounds = getBounds(assignment);
339            if (bounds[0] <= val && val <= bounds[1] && bounds[0] < bounds[1])
340                info.put("[C] " + getName(),
341                        getPerc(val, bounds[0], bounds[1]) + "% (value: " + sDoubleFormat.format(val) +
342                        (Math.abs(prec - val) > 0.0001 ? ", precise:" + sDoubleFormat.format(prec) : "") +
343                        ", weighted:" + sDoubleFormat.format(w) +
344                        ", bounds: " + sDoubleFormat.format(bounds[0]) + ".." + sDoubleFormat.format(bounds[1]) + ")");
345            else if (bounds[1] <= val && val <= bounds[0] && bounds[1] < bounds[0])
346                info.put("[C] " + getName(),
347                        getPercRev(val, bounds[1], bounds[0]) + "% (value: " + sDoubleFormat.format(val) +
348                        (Math.abs(prec - val) > 0.0001 ? ", precise:" + sDoubleFormat.format(prec) : "") +
349                        ", weighted:" + sDoubleFormat.format(w) +
350                        ", bounds: " + sDoubleFormat.format(bounds[1]) + ".." + sDoubleFormat.format(bounds[0]) + ")");
351            else if (bounds[0] != val || val != bounds[1])
352                info.put("[C] " + getName(),
353                        sDoubleFormat.format(val) + " (" +
354                        (Math.abs(prec - val) > 0.0001 ? "precise:" + sDoubleFormat.format(prec) + ", ": "") +
355                        "weighted:" + sDoubleFormat.format(w) +
356                        (bounds[0] != bounds[1] ? ", bounds: " + sDoubleFormat.format(bounds[0]) + ".." + sDoubleFormat.format(bounds[1]) : "") +
357                        ")");
358        }        
359    }
360    
361    /**
362     * Assignment context holding current value and the cached bounds.
363     */
364    public class ValueContext implements AssignmentContext {
365        protected double iTotal = 0.0;
366        private double[] iBounds = null;
367        private int iCacheId = -1;
368
369        /** Create from an assignment 
370         * @param assignment current assignment
371         **/
372        protected ValueContext(Assignment<V, T> assignment) {
373            if (getValueUpdateType() != ValueUpdateType.NoUpdate)
374                iTotal = AbstractCriterion.this.getValue(assignment, getModel().variables());
375        }
376        
377        protected ValueContext() {}
378        
379        /** Update value when unassigned
380         * @param assignment current assignment
381         * @param value recently unassigned value
382         **/
383        protected void unassigned(Assignment<V, T> assignment, T value) {
384            iTotal -= getValue(assignment, value, null);
385        }
386        
387        /** Update value when assigned 
388         * @param assignment current assignment
389         * @param value recently assigned value
390         **/
391        protected void assigned(Assignment<V, T> assignment, T value) {
392            iTotal += getValue(assignment, value, null);
393        }
394
395        /** Return value 
396         * @return current value of the criterion
397         **/
398        public double getTotal() { return iTotal; }
399        
400        /** Set value
401         * @param value current value of the criterion
402         **/
403        public void setTotal(double value) { iTotal = value; }
404        
405        /** Increment value
406         * @param value increment
407         **/
408        public void inc(double value) { iTotal += value; }
409        
410        /** Return bounds 
411         * @param assignment current assignment 
412         * @return minimum and maximum of this criterion's value
413         **/
414        protected double[] getBounds(Assignment<V, T> assignment) {
415            if (iBounds == null || iCacheId < iLastCacheId) {
416                iCacheId = iLastCacheId;
417                iBounds = computeBounds(assignment);
418            }
419            return (iBounds == null ? new double[] {0.0, 0.0} : iBounds);
420        }
421        
422        /** Set bounds 
423         * @param bounds bounds to cache
424         **/
425        protected void setBounds(double[] bounds) {
426            iBounds = bounds;
427        }
428    }
429
430    @Override
431    @Deprecated
432    public double getWeightedValue() {
433        return getWeightedValue(getModel().getDefaultAssignment());
434    }
435
436    @Override
437    @Deprecated
438    public double[] getBounds() {
439        return getBounds(getModel().getDefaultAssignment());
440    }
441
442    @Override
443    @Deprecated
444    public double getWeightedValue(T value, Set<T> conflicts) {
445        return getWeightedValue(getModel().getDefaultAssignment(), value, conflicts);
446    }
447    
448    @Override
449    @Deprecated
450    public double getValue(T value, Set<T> conflicts) {
451        return getValue(getModel().getDefaultAssignment(), value, conflicts);
452    }
453
454    @Override
455    @Deprecated
456    public double getWeightedValue(Collection<V> variables) {
457        return getWeightedValue(getModel().getDefaultAssignment(), variables);
458    }
459
460    @Override
461    @Deprecated
462    public double getValue(Collection<V> variables) {
463        return getValue(getModel().getDefaultAssignment(), variables);
464    }
465
466    @Override
467    @Deprecated
468    public double[] getBounds(Collection<V> variables) {
469        return getBounds(getModel().getDefaultAssignment(), variables);
470    }
471    
472    @Override
473    @Deprecated
474    public void inc(double value) {
475        inc(getModel().getDefaultAssignment(), value);
476    }
477    
478    /** Abbreviated name of the criterion for {@link TimetablingCriterion#toString()}. 
479     * @return abbreviated name of the criterion
480     **/
481    public String getAbbreviation() {
482        return getName().replaceAll("[a-z ]","");
483    }
484    
485    /**
486     * Simple text representation of the criterion and its value. E.g., X:x where X is the {@link AbstractCriterion#getAbbreviation()} 
487     * and x is the current value {@link AbstractCriterion#getValue(Assignment)}.
488     * @param assignment current assignment
489     * @return short string representation (e.g., PP:95% for period preference)
490     */
491    @Override
492    public String toString(Assignment<V, T> assignment) {
493        double val = getValue(assignment);
494        if (Math.abs(getWeightedValue(assignment)) < 0.005) return "";
495        double[] bounds = getBounds(assignment);
496        if (bounds[0] <= val && val <= bounds[1] && bounds[0] < bounds[1] && getName().endsWith(" Preferences"))
497            return getAbbreviation() + ":" + getPerc(val, bounds[0], bounds[1]) + "%";
498        else if (bounds[1] <= val && val <= bounds[0] && bounds[1] < bounds[0] && getName().endsWith(" Preferences"))
499            return getAbbreviation() + ":" + getPercRev(val, bounds[1], bounds[0]) + "%";
500        else if (bounds[0] != val || val != bounds[1])
501            return getAbbreviation() + ":" + sDoubleFormat.format(getValue(assignment));
502        else
503            return "";
504    }
505
506    public ValueUpdateType getValueUpdateType() {
507        return iValueUpdateType;
508    }
509
510    public void setValueUpdateType(ValueUpdateType iValueUpdateType) {
511        this.iValueUpdateType = iValueUpdateType;
512    }
513}