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 void configure(DataProperties properties) {
111        iWeight = properties.getPropertyDouble(getWeightName(), getWeightDefault(properties));
112        iDebug = properties.getPropertyBoolean("Debug." + getClass().getName().substring(1 + getClass().getName().lastIndexOf('.')), properties.getPropertyBoolean("Debug.Criterion", false));
113    }
114
115    @Override
116    public boolean init(Solver<V, T> solver) {
117        configure(solver.getProperties());
118        return true;
119    }
120    
121    /**
122     * Returns current model
123     * @return problem model
124     **/
125    public Model<V, T> getModel() { return iModel; }
126    
127    /**
128     * Returns an assignment context associated with this criterion. If there is no 
129     * assignment context associated with this criterion yet, one is created using the
130     * {@link ConstraintWithContext#createAssignmentContext(Assignment)} method. From that time on,
131     * this context is kept with the assignment and automatically updated by calling the
132     * {@link AssignmentConstraintContext#assigned(Assignment, Value)} and {@link AssignmentConstraintContext#unassigned(Assignment, Value)}
133     * whenever a variable is changed as given by the {@link ValueUpdateType}.
134     * @param assignment given assignment
135     * @return assignment context associated with this constraint and the given assignment
136     */
137    @Override
138    public ValueContext getContext(Assignment<V, T> assignment) {
139        return AssignmentContextHelper.getContext(this, assignment);
140    }
141    
142    @Override
143    public ValueContext createAssignmentContext(Assignment<V,T> assignment) {
144        return new ValueContext(assignment);
145    }
146
147    @Override
148    public AssignmentContextReference<V, T, ValueContext> getAssignmentContextReference() { return iContextReference; }
149
150    @Override
151    public void setAssignmentContextReference(AssignmentContextReference<V, T, ValueContext> reference) { iContextReference = reference; }
152
153    @Override
154    public AssignmentContext[] getContext() {
155        return iContext;
156    }
157    
158    @Override
159    public double getValue(Assignment<V, T> assignment) {
160        return getContext(assignment).getTotal();
161    }
162    
163    @Override
164    public double getBest() {
165        return iBest;
166    }
167    
168    @Override
169    public double getValue(Assignment<V, T> assignment, Collection<V> variables) {
170        double ret = 0;
171        for (V v: variables) {
172            T t = assignment.getValue(v);
173            if (t != null) ret += getValue(assignment, t, null);
174        }
175        return ret;
176    }
177
178    
179    @Override
180    public double getWeight() {
181        return iWeight;
182    }
183    
184    @Override
185    public double getWeightedBest() {
186        return getWeight() == 0.0 ? 0.0 : getWeight() * getBest();
187    }
188    
189    @Override
190    public double getWeightedValue(Assignment<V, T> assignment) {
191        return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment));
192    }
193    
194    @Override
195    public double getWeightedValue(Assignment<V, T> assignment, T value, Set<T> conflicts) {
196        return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment, value, conflicts));
197    }
198    
199    @Override
200    public double getWeightedValue(Assignment<V, T> assignment, Collection<V> variables) {
201        return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment, variables));
202    }
203
204    /** Compute bounds (bounds are being cached by default). 
205     * @param assignment current assignment
206     * @return minimum and maximum of this criterion's value
207     **/
208    protected double[] computeBounds(Assignment<V, T> assignment) {
209        return getBounds(assignment, new ArrayList<V>(getModel().variables()));
210    }
211
212    @Override
213    public double[] getBounds(Assignment<V, T> assignment) {
214        return getContext(assignment).getBounds(assignment);
215    }
216
217    @Override
218    public double[] getBounds(Assignment<V, T> assignment, Collection<V> variables) {
219        double[] bounds = new double[] { 0.0, 0.0 };
220        for (V v: variables) {
221            Double min = null, max = null;
222            for (T t: v.values(assignment)) {
223                double value = getValue(assignment, t, null);
224                if (min == null) { min = value; max = value; continue; }
225                min = Math.min(min, value);
226                max = Math.max(max, value);
227            }
228            if (min != null) {
229                bounds[0] += min;
230                bounds[1] += max;
231            }
232        }
233        return bounds;
234    }
235
236    @Override
237    public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) {
238        switch (getValueUpdateType()) {
239            case AfterUnassignedBeforeAssigned:
240            case BeforeUnassignedBeforeAssigned:
241                getContext(assignment).assigned(assignment, value);
242        }
243    }
244
245    @Override
246    public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) {
247        switch (getValueUpdateType()) {
248            case AfterUnassignedAfterAssigned:
249            case BeforeUnassignedAfterAssigned:
250                getContext(assignment).assigned(assignment, value);
251        }
252    }
253
254    @Override
255    public void beforeUnassigned(Assignment<V, T> assignment, long iteration, T value) {
256        switch (getValueUpdateType()) {
257            case BeforeUnassignedAfterAssigned:
258            case BeforeUnassignedBeforeAssigned:
259                getContext(assignment).unassigned(assignment, value);
260        }
261    }
262
263    @Override
264    public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) {
265        switch (getValueUpdateType()) {
266            case AfterUnassignedAfterAssigned:
267            case AfterUnassignedBeforeAssigned:
268                getContext(assignment).unassigned(assignment, value);
269        }
270    }
271
272    @Override
273    public void bestSaved(Assignment<V, T> assignment) {
274        iBest = getContext(assignment).getTotal();
275    }
276
277    @Override
278    public void bestRestored(Assignment<V, T> assignment) {
279        getContext(assignment).setTotal(iBest);
280    }
281    
282    @Override
283    public void inc(Assignment<V, T> assignment, double value) {
284        getContext(assignment).inc(value);
285    }   
286
287    @Override
288    public String getName() {
289        return getClass().getName().substring(1 + getClass().getName().lastIndexOf('.')).replaceAll("(?<=[^A-Z])([A-Z])"," $1");
290    }
291    
292    /** Clear bounds cache */
293    protected void clearCache() {
294        iLastCacheId++;
295    }
296    
297    @Override
298    public void variableAdded(V variable) {
299        clearCache();
300    }
301    
302    @Override
303    public void variableRemoved(V variable) {
304        clearCache();
305    }
306    
307    @Override
308    public void constraintAdded(Constraint<V, T> constraint) {
309        clearCache();
310    }
311    
312    @Override
313    public void constraintRemoved(Constraint<V, T> constraint) {
314        clearCache();
315    }
316    
317    protected String getPerc(double value, double min, double max) {
318        if (max == min)
319            return sPercentFormat.format(100.0);
320        return sPercentFormat.format(100.0 - 100.0 * (value - min) / (max - min));
321    }
322
323    protected String getPercRev(double value, double min, double max) {
324        if (max == min)
325            return sPercentFormat.format(0.0);
326        return sPercentFormat.format(100.0 * (value - min) / (max - min));
327    }
328
329    @Override
330    public void getInfo(Assignment<V, T> assignment, Map<String, String> info) {
331    }
332    
333    @Override
334    public void getInfo(Assignment<V, T> assignment, Map<String, String> info, Collection<V> variables) {
335    }
336    
337    @Override
338    public void getExtendedInfo(Assignment<V, T> assignment, Map<String, String> info) {
339        if (iDebug) {
340            double val = getValue(assignment), w = getWeightedValue(assignment), prec = getValue(assignment, getModel().variables());
341            double[] bounds = getBounds(assignment);
342            if (bounds[0] <= val && val <= bounds[1] && bounds[0] < bounds[1])
343                info.put("[C] " + getName(),
344                        getPerc(val, bounds[0], bounds[1]) + "% (value: " + sDoubleFormat.format(val) +
345                        (Math.abs(prec - val) > 0.0001 ? ", precise:" + sDoubleFormat.format(prec) : "") +
346                        ", weighted:" + sDoubleFormat.format(w) +
347                        ", bounds: " + sDoubleFormat.format(bounds[0]) + ".." + sDoubleFormat.format(bounds[1]) + ")");
348            else if (bounds[1] <= val && val <= bounds[0] && bounds[1] < bounds[0])
349                info.put("[C] " + getName(),
350                        getPercRev(val, bounds[1], bounds[0]) + "% (value: " + sDoubleFormat.format(val) +
351                        (Math.abs(prec - val) > 0.0001 ? ", precise:" + sDoubleFormat.format(prec) : "") +
352                        ", weighted:" + sDoubleFormat.format(w) +
353                        ", bounds: " + sDoubleFormat.format(bounds[1]) + ".." + sDoubleFormat.format(bounds[0]) + ")");
354            else if (bounds[0] != val || val != bounds[1])
355                info.put("[C] " + getName(),
356                        sDoubleFormat.format(val) + " (" +
357                        (Math.abs(prec - val) > 0.0001 ? "precise:" + sDoubleFormat.format(prec) + ", ": "") +
358                        "weighted:" + sDoubleFormat.format(w) +
359                        (bounds[0] != bounds[1] ? ", bounds: " + sDoubleFormat.format(bounds[0]) + ".." + sDoubleFormat.format(bounds[1]) : "") +
360                        ")");
361        }        
362    }
363    
364    /**
365     * Assignment context holding current value and the cached bounds.
366     */
367    public class ValueContext implements AssignmentContext {
368        protected double iTotal = 0.0;
369        private double[] iBounds = null;
370        private int iCacheId = -1;
371
372        /** Create from an assignment 
373         * @param assignment current assignment
374         **/
375        protected ValueContext(Assignment<V, T> assignment) {
376            if (getValueUpdateType() != ValueUpdateType.NoUpdate)
377                iTotal = AbstractCriterion.this.getValue(assignment, getModel().variables());
378        }
379        
380        protected ValueContext() {}
381        
382        /** Update value when unassigned
383         * @param assignment current assignment
384         * @param value recently unassigned value
385         **/
386        protected void unassigned(Assignment<V, T> assignment, T value) {
387            iTotal -= getValue(assignment, value, null);
388        }
389        
390        /** Update value when assigned 
391         * @param assignment current assignment
392         * @param value recently assigned value
393         **/
394        protected void assigned(Assignment<V, T> assignment, T value) {
395            iTotal += getValue(assignment, value, null);
396        }
397
398        /** Return value 
399         * @return current value of the criterion
400         **/
401        public double getTotal() { return iTotal; }
402        
403        /** Set value
404         * @param value current value of the criterion
405         **/
406        public void setTotal(double value) { iTotal = value; }
407        
408        /** Increment value
409         * @param value increment
410         **/
411        public void inc(double value) { iTotal += value; }
412        
413        /** Return bounds 
414         * @param assignment current assignment 
415         * @return minimum and maximum of this criterion's value
416         **/
417        protected double[] getBounds(Assignment<V, T> assignment) {
418            if (iBounds == null || iCacheId < iLastCacheId) {
419                iCacheId = iLastCacheId;
420                iBounds = computeBounds(assignment);
421            }
422            return (iBounds == null ? new double[] {0.0, 0.0} : iBounds);
423        }
424        
425        /** Set bounds 
426         * @param bounds bounds to cache
427         **/
428        protected void setBounds(double[] bounds) {
429            iBounds = bounds;
430        }
431    }
432
433    @Override
434    @Deprecated
435    public double getWeightedValue() {
436        return getWeightedValue(getModel().getDefaultAssignment());
437    }
438
439    @Override
440    @Deprecated
441    public double[] getBounds() {
442        return getBounds(getModel().getDefaultAssignment());
443    }
444
445    @Override
446    @Deprecated
447    public double getWeightedValue(T value, Set<T> conflicts) {
448        return getWeightedValue(getModel().getDefaultAssignment(), value, conflicts);
449    }
450    
451    @Override
452    @Deprecated
453    public double getValue(T value, Set<T> conflicts) {
454        return getValue(getModel().getDefaultAssignment(), value, conflicts);
455    }
456
457    @Override
458    @Deprecated
459    public double getWeightedValue(Collection<V> variables) {
460        return getWeightedValue(getModel().getDefaultAssignment(), variables);
461    }
462
463    @Override
464    @Deprecated
465    public double getValue(Collection<V> variables) {
466        return getValue(getModel().getDefaultAssignment(), variables);
467    }
468
469    @Override
470    @Deprecated
471    public double[] getBounds(Collection<V> variables) {
472        return getBounds(getModel().getDefaultAssignment(), variables);
473    }
474    
475    @Override
476    @Deprecated
477    public void inc(double value) {
478        inc(getModel().getDefaultAssignment(), value);
479    }
480    
481    /** Abbreviated name of the criterion for {@link TimetablingCriterion#toString()}. 
482     * @return abbreviated name of the criterion
483     **/
484    public String getAbbreviation() {
485        return getName().replaceAll("[a-z ]","");
486    }
487    
488    /**
489     * Simple text representation of the criterion and its value. E.g., X:x where X is the {@link AbstractCriterion#getAbbreviation()} 
490     * and x is the current value {@link AbstractCriterion#getValue(Assignment)}.
491     * @param assignment current assignment
492     * @return short string representation (e.g., PP:95% for period preference)
493     */
494    @Override
495    public String toString(Assignment<V, T> assignment) {
496        double val = getValue(assignment);
497        if (Math.abs(getWeightedValue(assignment)) < 0.005) return "";
498        double[] bounds = getBounds(assignment);
499        if (bounds[0] <= val && val <= bounds[1] && bounds[0] < bounds[1] && getName().endsWith(" Preferences"))
500            return getAbbreviation() + ":" + getPerc(val, bounds[0], bounds[1]) + "%";
501        else if (bounds[1] <= val && val <= bounds[0] && bounds[1] < bounds[0] && getName().endsWith(" Preferences"))
502            return getAbbreviation() + ":" + getPercRev(val, bounds[1], bounds[0]) + "%";
503        else if (bounds[0] != val || val != bounds[1])
504            return getAbbreviation() + ":" + sDoubleFormat.format(getValue(assignment));
505        else
506            return "";
507    }
508
509    public ValueUpdateType getValueUpdateType() {
510        return iValueUpdateType;
511    }
512
513    public void setValueUpdateType(ValueUpdateType iValueUpdateType) {
514        this.iValueUpdateType = iValueUpdateType;
515    }
516}