001package net.sf.cpsolver.exam.model;
002
003import java.util.HashSet;
004import java.util.Iterator;
005import java.util.Set;
006
007import net.sf.cpsolver.exam.criteria.DistributionPenalty;
008import net.sf.cpsolver.ifs.model.Constraint;
009
010/**
011 * Distribution binary constraint. <br>
012 * <br>
013 * The following binary distribution constraints are implemented
014 * <ul>
015 * <li>Same room
016 * <li>Different room
017 * <li>Same period
018 * <li>Different period
019 * <li>Precedence
020 * </ul>
021 * <br>
022 * <br>
023 * 
024 * @version ExamTT 1.2 (Examination Timetabling)<br>
025 *          Copyright (C) 2008 - 2010 Tomáš Müller<br>
026 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
027 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
028 * <br>
029 *          This library is free software; you can redistribute it and/or modify
030 *          it under the terms of the GNU Lesser General Public License as
031 *          published by the Free Software Foundation; either version 3 of the
032 *          License, or (at your option) any later version. <br>
033 * <br>
034 *          This library is distributed in the hope that it will be useful, but
035 *          WITHOUT ANY WARRANTY; without even the implied warranty of
036 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
037 *          Lesser General Public License for more details. <br>
038 * <br>
039 *          You should have received a copy of the GNU Lesser General Public
040 *          License along with this library; if not see
041 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
042 */
043public class ExamDistributionConstraint extends Constraint<Exam, ExamPlacement> {
044    /** Same room constraint type */
045    public static final int sDistSameRoom = 0;
046    /** Different room constraint type */
047    public static final int sDistDifferentRoom = 1;
048    /** Same period constraint type */
049    public static final int sDistSamePeriod = 2;
050    /** Different period constraint type */
051    public static final int sDistDifferentPeriod = 3;
052    /** Precedence constraint type */
053    public static final int sDistPrecedence = 4;
054    /** Precedence constraint type (reverse order) */
055    public static final int sDistPrecedenceRev = 5;
056    /** Distribution type name */
057    public static final String[] sDistType = new String[] { "same-room", "different-room", "same-period",
058            "different-period", "precedence", "precedence-rev" };
059
060    private int iType = -1;
061    private boolean iHard = true;
062    private int iWeight = 0;
063
064    /**
065     * Constructor
066     * 
067     * @param id
068     *            constraint unique id
069     * @param type
070     *            constraint type
071     * @param hard
072     *            true if the constraint is hard (cannot be violated)
073     * @param weight
074     *            if not hard, penalty for violation
075     */
076    public ExamDistributionConstraint(long id, int type, boolean hard, int weight) {
077        iId = id;
078        iType = type;
079        iHard = hard;
080        iWeight = weight;
081    }
082
083    /**
084     * Constructor
085     * 
086     * @param id
087     *            constraint unique id
088     * @param type
089     *            constraint type (EX_SAME_PREF, EX_SAME_ROOM, or EX_PRECEDENCE)
090     * @param pref
091     *            preference (R/P for required/prohibited, or -2, -1, 0, 1, 2
092     *            for preference (from preferred to discouraged))
093     */
094    public ExamDistributionConstraint(long id, String type, String pref) {
095        iId = id;
096        boolean neg = "P".equals(pref) || "2".equals(pref) || "1".equals(pref);
097        if ("EX_SAME_PER".equals(type)) {
098            iType = (neg ? sDistDifferentPeriod : sDistSamePeriod);
099        } else if ("EX_SAME_ROOM".equals(type)) {
100            iType = (neg ? sDistDifferentRoom : sDistSameRoom);
101        } else if ("EX_PRECEDENCE".equals(type)) {
102            iType = (neg ? sDistPrecedenceRev : sDistPrecedence);
103        } else
104            throw new RuntimeException("Unkown type " + type);
105        if ("P".equals(pref) || "R".equals(pref))
106            iHard = true;
107        else {
108            iHard = false;
109            iWeight = Integer.parseInt(pref) * Integer.parseInt(pref);
110        }
111    }
112
113    /**
114     * Constructor
115     * 
116     * @param id
117     *            constraint unique id
118     * @param type
119     *            constraint type name
120     */
121    public ExamDistributionConstraint(long id, String type, boolean hard, int weight) {
122        iId = id;
123        for (int i = 0; i < sDistType.length; i++)
124            if (sDistType[i].equals(type))
125                iType = i;
126        if (iType < 0)
127            throw new RuntimeException("Unknown type '" + type + "'.");
128        iHard = hard;
129        iWeight = weight;
130    }
131
132    /**
133     * True if hard (must be satisfied), false for soft (should be satisfied)
134     */
135    @Override
136    public boolean isHard() {
137        return iHard;
138    }
139
140    /**
141     * If not hard, penalty for violation
142     */
143    public int getWeight() {
144        return iWeight;
145    }
146
147    /**
148     * Constraint type
149     */
150    public int getType() {
151        return iType;
152    }
153
154    /**
155     * Constraint type name
156     */
157    public String getTypeString() {
158        return sDistType[iType];
159    }
160
161    /**
162     * String representation -- constraint type name (exam 1, exam 2)
163     */
164    @Override
165    public String toString() {
166        return getTypeString() + " (" + variables() + ")";
167    }
168
169    /**
170     * Compute conflicts -- there is a conflict if the other variable is
171     * assigned and
172     * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is
173     * false
174     */
175    @Override
176    public void computeConflicts(ExamPlacement givenPlacement, Set<ExamPlacement> conflicts) {
177        boolean before = true;
178        for (Exam exam : variables()) {
179            if (exam.equals(givenPlacement.variable())) {
180                before = false;
181                continue;
182            }
183            ExamPlacement placement = exam.getAssignment();
184            if (placement == null)
185                continue;
186            if (!check(before ? placement : givenPlacement, before ? givenPlacement : placement))
187                conflicts.add(placement);
188        }
189    }
190
191    /**
192     * Check for conflict -- there is a conflict if the other variable is
193     * assigned and
194     * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is
195     * false
196     */
197    @Override
198    public boolean inConflict(ExamPlacement givenPlacement) {
199        boolean before = true;
200        for (Exam exam : variables()) {
201            if (exam.equals(givenPlacement.variable())) {
202                before = false;
203                continue;
204            }
205            ExamPlacement placement = exam.getAssignment();
206            if (placement == null)
207                continue;
208            if (!check(before ? placement : givenPlacement, before ? givenPlacement : placement))
209                return true;
210        }
211        return false;
212    }
213
214    /**
215     * Consistency check --
216     * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is
217     * called
218     */
219    @Override
220    public boolean isConsistent(ExamPlacement first, ExamPlacement second) {
221        boolean before = (variables().indexOf(first.variable()) < variables().indexOf(second.variable()));
222        return check(before ? first : second, before ? second : first);
223    }
224
225    /**
226     * Check assignments of the given exams
227     * 
228     * @param first
229     *            assignment of the first exam
230     * @param second
231     *            assignment of the second exam
232     * @return true, if the constraint is satisfied
233     */
234    public boolean check(ExamPlacement first, ExamPlacement second) {
235        switch (getType()) {
236            case sDistPrecedence:
237                return first.getPeriod().getIndex() < second.getPeriod().getIndex();
238            case sDistPrecedenceRev:
239                return first.getPeriod().getIndex() > second.getPeriod().getIndex();
240            case sDistSamePeriod:
241                return first.getPeriod().getIndex() == second.getPeriod().getIndex();
242            case sDistDifferentPeriod:
243                return first.getPeriod().getIndex() != second.getPeriod().getIndex();
244            case sDistSameRoom:
245                return first.getRoomPlacements().containsAll(second.getRoomPlacements())
246                        || second.getRoomPlacements().containsAll(first.getRoomPlacements());
247            case sDistDifferentRoom:
248                for (Iterator<ExamRoomPlacement> i = first.getRoomPlacements().iterator(); i.hasNext();)
249                    if (second.getRoomPlacements().contains(i.next()))
250                        return false;
251                return true;
252            default:
253                return false;
254        }
255    }
256
257    /**
258     * Compare with other constraint for equality
259     */
260    @Override
261    public boolean equals(Object o) {
262        if (o == null || !(o instanceof ExamDistributionConstraint))
263            return false;
264        ExamDistributionConstraint c = (ExamDistributionConstraint) o;
265        return getType() == c.getType() && getId() == c.getId();
266    }
267
268    /**
269     * Return true if this is hard constraint or this is a soft constraint
270     * without any violation
271     */
272    public boolean isSatisfied() {
273        return isSatisfied(null);
274    }
275
276    /**
277     * Return true if this is hard constraint or this is a soft constraint
278     * without any violation
279     * 
280     * @param p
281     *            exam assignment to be made
282     */
283    public boolean isSatisfied(ExamPlacement p) {
284        if (isHard())
285            return true;
286        switch (getType()) {
287            case sDistPrecedence:
288                ExamPeriod last = null;
289                for (Exam exam : variables()) {
290                    ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
291                    if (placement == null)
292                        continue;
293                    if (last == null || last.getIndex() < placement.getPeriod().getIndex())
294                        last = placement.getPeriod();
295                    else
296                        return false;
297                }
298                return true;
299            case sDistPrecedenceRev:
300                last = null;
301                for (Exam exam : variables()) {
302                    ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
303                    if (placement == null)
304                        continue;
305                    if (last == null || last.getIndex() > placement.getPeriod().getIndex())
306                        last = placement.getPeriod();
307                    else
308                        return false;
309                }
310                return true;
311            case sDistSamePeriod:
312                ExamPeriod period = null;
313                for (Exam exam : variables()) {
314                    ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
315                    if (placement == null)
316                        continue;
317                    if (period == null)
318                        period = placement.getPeriod();
319                    else if (period.getIndex() != placement.getPeriod().getIndex())
320                        return false;
321                }
322                return true;
323            case sDistDifferentPeriod:
324                HashSet<ExamPeriod> periods = new HashSet<ExamPeriod>();
325                for (Exam exam : variables()) {
326                    ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
327                    if (placement == null)
328                        continue;
329                    if (!periods.add(placement.getPeriod()))
330                        return false;
331                }
332                return true;
333            case sDistSameRoom:
334                Set<ExamRoomPlacement> rooms = null;
335                for (Exam exam : variables()) {
336                    ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
337                    if (placement == null)
338                        continue;
339                    if (rooms == null)
340                        rooms = placement.getRoomPlacements();
341                    else if (!rooms.containsAll(placement.getRoomPlacements())
342                            || !placement.getRoomPlacements().containsAll(rooms))
343                        return false;
344                }
345                return true;
346            case sDistDifferentRoom:
347                HashSet<ExamRoomPlacement> allRooms = new HashSet<ExamRoomPlacement>();
348                for (Exam exam : variables()) {
349                    ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
350                    if (placement == null)
351                        continue;
352                    for (ExamRoomPlacement room : placement.getRoomPlacements()) {
353                        if (!allRooms.add(room))
354                            return false;
355                    }
356                }
357                return true;
358            default:
359                return false;
360        }
361    }
362
363    boolean iIsSatisfied = true;
364
365    @Override
366    public void assigned(long iteration, ExamPlacement value) {
367        super.assigned(iteration, value);
368        if (!isHard() && iIsSatisfied != isSatisfied()) {
369            iIsSatisfied = !iIsSatisfied;
370            ((DistributionPenalty)getModel().getCriterion(DistributionPenalty.class)).inc(iIsSatisfied ? -getWeight() : getWeight());
371        }
372    }
373
374    @Override
375    public void unassigned(long iteration, ExamPlacement value) {
376        super.unassigned(iteration, value);
377        if (!isHard() && iIsSatisfied != isSatisfied()) {
378            iIsSatisfied = !iIsSatisfied;
379            ((DistributionPenalty)getModel().getCriterion(DistributionPenalty.class)).inc(iIsSatisfied ? -getWeight() : getWeight());
380        }
381    }
382
383    /** True if the constraint is related to rooms */
384    public boolean isRoomRelated() {
385        return iType == sDistSameRoom || iType == sDistDifferentRoom;
386    }
387
388    /** True if the constraint is related to periods */
389    public boolean isPeriodRelated() {
390        return !isRoomRelated();
391    }
392}