    001package org.cpsolver.coursett.constraint;
    002
    003import java.util.ArrayList;
    004import java.util.HashMap;
    005import java.util.HashSet;
    006import java.util.List;
    007import java.util.Map;
    008import java.util.Set;
    009import java.util.regex.Matcher;
    010import java.util.regex.Pattern;
    011
    012import org.cpsolver.coursett.Constants;
    013import org.cpsolver.coursett.criteria.FlexibleConstraintCriterion;
    014import org.cpsolver.coursett.model.Lecture;
    015import org.cpsolver.coursett.model.Placement;
    016import org.cpsolver.ifs.assignment.Assignment;
    017import org.cpsolver.ifs.criteria.Criterion;
    018import org.cpsolver.ifs.util.ToolBox;
    019
    020/**
    021 *
    022 * The MaxDays constraint limits the number of days of week during which the given set of classes are taught.<br>
    023 * It has one parameter: a maximal number of week days during which the given set of classes can be placed.<br>
    024 * Reference _MaxDays:2_ translates to a maximum number of 2 days a week<br>
    025 *
    026 * @version CourseTT 1.3 (University Course Timetabling)<br>
    027 *          Copyright (C) 2015 Tomáš Müller<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 MaxDaysFlexibleConstraint extends FlexibleConstraint {
    044    private int iMaxDays;
    045
    046    public MaxDaysFlexibleConstraint(Long id, String owner, String preference, String reference) {
    047        super(id, owner, preference, reference);
    048
    049        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_DAYS.getPattern()).matcher(reference);
    050        if (matcher.find()) {
    051            iMaxDays = Integer.parseInt(matcher.group(2));
    052            iConstraintType = FlexibleConstraintType.MAX_DAYS;
    053        }
    054    }
    055
    056    @Override
    057    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
    058        return ((MaxDaysFlexibleConstraintContext)getContext(assignment)).nrViolations(assignments, conflicts);
    059    }
    060
    061    @Override
    062    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    063        if (!isHard()) return;
    064
    065        MaxDaysFlexibleConstraintContext context = (MaxDaysFlexibleConstraintContext)getContext(assignment);
    066        while (context.nrDays(value, conflicts) > iMaxDays) {
    067            Set<Lecture> candidates = context.candidates(value, conflicts);
    068            if (candidates == null) return;
    069            for (Lecture candidate: candidates) {
    070                Placement conflict = assignment.getValue(candidate);
    071                if (conflict != null)
    072                    conflicts.add(conflict);
    073            }
    074        }
    075    }
    076
    077    @Override
    078    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
    079        if (!isHard()) return false;
    080        return ((MaxDaysFlexibleConstraintContext)getContext(assignment)).nrDays(value, null) > iMaxDays;
    081    }
    082
    083    @Override
    084    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    085        return new MaxDaysFlexibleConstraintContext(assignment);
    086    }
    087
    088    public class MaxDaysFlexibleConstraintContext extends FlexibleConstraintContext {
    089        private Set<Lecture> iDayAssignments[] = null;
    090
    091        @SuppressWarnings("unchecked")
    092        public MaxDaysFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
    093            super();
    094            iDayAssignments = new Set[Constants.NR_DAYS];
    095            for (int i = 0; i < iDayAssignments.length; i++)
    096                iDayAssignments[i] = new HashSet<Lecture>();
    097
    098            for (Lecture variable: variables()) {
    099                Placement value = assignment.getValue(variable);
    100                if (value != null) {
    101                    for (int i = 0; i < iDayAssignments.length; i++)
    102                        if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0)
    103                            iDayAssignments[i].add(value.variable());
    104                }
    105            }
    106
    107            if (!isHard()) {
    108                Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class);
    109                if (criterion != null) {
    110                    double pref = nrViolations(null, null);
    111                    if (pref == 0)
    112                        iLastPreference = -Math.abs(iPreference);
    113                    else
    114                        iLastPreference = Math.abs(iPreference) * pref;
    115                    criterion.inc(assignment, iLastPreference);
    116                }
    117            }
    118        }
    119
    120        @Override
    121        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
    122            for (int i = 0; i < iDayAssignments.length; i++)
    123                if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0)
    124                    iDayAssignments[i].add(value.variable());
    125            updateCriterion(assignment);
    126        }
    127
    128        @Override
    129        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
    130            for (int i = 0; i < iDayAssignments.length; i++)
    131                if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0)
    132                    iDayAssignments[i].remove(value.variable());
    133            updateCriterion(assignment);
    134        }
    135
    136        public int nrDays(Placement value, Set<Placement> conflicts) {
    137            int ret = 0;
    138            for (int i = 0; i < iDayAssignments.length; i++) {
    139                int cnt = iDayAssignments[i].size();
    140                if (value != null) {
    141                    if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) cnt ++;
    142                    if (iDayAssignments[i].contains(value.variable())) cnt --;
    143                }
    144                if (conflicts != null) {
    145                    for (Placement conflict: conflicts) {
    146                        if (value != null && conflict.variable().equals(value.variable())) continue;
    147                        if (iDayAssignments[i].contains(conflict.variable())) cnt --;
    148                    }
    149                }
    150                if (cnt > 0) ret++;
    151            }
    152            return ret;
    153        }
    154
    155        public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) {
    156            int bestCnt = 0;
    157            List<Integer> bestWeeks = new ArrayList<Integer>();
    158            for (int i = 0; i < iDayAssignments.length; i++) {
    159                if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) continue;
    160                int cnt = iDayAssignments[i].size();
    161                if (iDayAssignments[i].contains(value.variable())) cnt --;
    162                for (Placement conflict: conflicts) {
    163                    if (conflict.variable().equals(value.variable())) continue;
    164                    if (iDayAssignments[i].contains(conflict.variable())) cnt --;
    165                }
    166                if (cnt <= 0) continue;
    167                if (bestWeeks.isEmpty() || bestCnt > cnt) {
    168                    bestWeeks.clear(); bestWeeks.add(i); bestCnt = cnt;
    169                } else if (bestCnt == cnt) {
    170                    bestWeeks.add(i);
    171                }
    172            }
    173            return bestWeeks.isEmpty() ? null : iDayAssignments[ToolBox.random(bestWeeks)];
    174        }
    175
    176        public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
    177            int days = 0;
    178            for (int i = 0; i < iDayAssignments.length; i++) {
    179                int cnt = iDayAssignments[i].size();
    180                if (assignments != null) {
    181                    for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) {
    182                        Placement assignment = entry.getValue();
    183                        if (assignment != null && (assignment.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) cnt ++;
    184                    }
    185                }
    186                if (conflicts != null)
    187                    for (Placement conflict: conflicts) {
    188                        if (assignments != null && assignments.containsKey(conflict.variable())) continue;
    189                        if (iDayAssignments[i].contains(conflict.variable())) cnt --;
    190                    }
    191                if (cnt > 0) days ++;
    192            }
    193            return (days <= iMaxDays ? 0 : days - iMaxDays);
    194        }
    195
    196    }
    197}