    001package org.cpsolver.coursett.constraint;
    002
    003import java.util.ArrayList;
    004import java.util.BitSet;
    005import java.util.HashMap;
    006import java.util.HashSet;
    007import java.util.List;
    008import java.util.Map;
    009import java.util.Set;
    010import java.util.regex.Matcher;
    011import java.util.regex.Pattern;
    012
    013import org.cpsolver.coursett.criteria.FlexibleConstraintCriterion;
    014import org.cpsolver.coursett.model.Lecture;
    015import org.cpsolver.coursett.model.Placement;
    016import org.cpsolver.coursett.model.TimetableModel;
    017import org.cpsolver.ifs.assignment.Assignment;
    018import org.cpsolver.ifs.criteria.Criterion;
    019import org.cpsolver.ifs.util.ToolBox;
    020
    021/**
    022 *
    023 * The MaxWeeks constraint limits the number of weeks during which the given set of classes are taught.<br>
    024 * It has two parameters: a maximal number of weeks during which the given set of classes can be placed
    025 * and a day code indicating what days of week are considered.<br>
    026 * Reference _MaxWeeks:3:6_ translates to a maximum number of 3 weeks, but only for classes that are placed on Fridays and Saturdays
    027 * (64 for Monday, 32 for Tuesday, 16 for Wednesday, 8 for Thursday, 4 for Friday, 2 for Saturday, and 1 for Sunday).
    028 * If the second parameter is zero, all days of week are considered.<br>
    029 *
    030 * @author  Tomáš Müller
    031 * @version CourseTT 1.3 (University Course Timetabling)<br>
    032 *          Copyright (C) 2013 - 2014 Tomáš Müller<br>
    033 * <br>
    034 *          This library is free software; you can redistribute it and/or modify
    035 *          it under the terms of the GNU Lesser General Public License as
    036 *          published by the Free Software Foundation; either version 3 of the
    037 *          License, or (at your option) any later version. <br>
    038 * <br>
    039 *          This library is distributed in the hope that it will be useful, but
    040 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    041 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    042 *          Lesser General Public License for more details. <br>
    043 * <br>
    044 *          You should have received a copy of the GNU Lesser General Public
    045 *          License along with this library; if not see
    046 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    047 */
    048public class MaxWeeksFlexibleConstraint extends FlexibleConstraint {
    049    private int iMaxWeeks;
    050    private int iDayCode;
    051
    052    public MaxWeeksFlexibleConstraint(Long id, String owner, String preference, String reference) {
    053        super(id, owner, preference, reference);
    054
    055        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_WEEKS.getPattern()).matcher(reference);
    056        if (matcher.find()) {
    057            iMaxWeeks = Integer.parseInt(matcher.group(2));
    058            iDayCode = Integer.parseInt(matcher.group(3));
    059            iConstraintType = FlexibleConstraintType.MAX_WEEKS;
    060        }
    061    }
    062
    063    public boolean isCorectDayOfWeek(Placement value) {
    064        return value != null && value.getTimeLocation() != null && (iDayCode == 0 || (iDayCode & value.getTimeLocation().getDayCode()) != 0);
    065    }
    066
    067    @Override
    068    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
    069        return ((MaxWeeksFlexibleConstraintContext)getContext(assignment)).nrViolations(assignments, conflicts);
    070    }
    071
    072    @Override
    073    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    074        if (!isHard() || !isCorectDayOfWeek(value)) return;
    075
    076        MaxWeeksFlexibleConstraintContext context = (MaxWeeksFlexibleConstraintContext)getContext(assignment);
    077        while (context.nrWeeks(value, conflicts) > iMaxWeeks) {
    078            Set<Lecture> candidates = context.candidates(value, conflicts);
    079            if (candidates == null) return;
    080            for (Lecture candidate: candidates) {
    081                Placement conflict = assignment.getValue(candidate);
    082                if (conflict != null)
    083                    conflicts.add(conflict);
    084            }
    085        }
    086    }
    087
    088    @Override
    089    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
    090        if (!isHard() || !isCorectDayOfWeek(value)) return false;
    091        return ((MaxWeeksFlexibleConstraintContext)getContext(assignment)).nrWeeks(value, null) > iMaxWeeks;
    092    }
    093
    094    @Override
    095    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    096        return new MaxWeeksFlexibleConstraintContext(assignment);
    097    }
    098
    099    public class MaxWeeksFlexibleConstraintContext extends FlexibleConstraintContext {
    100        private List<BitSet> iWeeks = null;
    101        private Set<Lecture> iWeekAssignments[] = null;
    102
    103        @SuppressWarnings("unchecked")
    104        public MaxWeeksFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
    105            super();
    106            iWeeks = ((TimetableModel)getModel()).getWeeks();
    107            iWeekAssignments = new Set[iWeeks.size()];
    108            for (int i = 0; i < iWeekAssignments.length; i++)
    109                iWeekAssignments[i] = new HashSet<Lecture>();
    110
    111            for (Lecture variable: variables()) {
    112                Placement value = assignment.getValue(variable);
    113                if (value != null && isCorectDayOfWeek(value)) {
    114                    for (int i = 0; i < iWeeks.size(); i++)
    115                        if (value.getTimeLocation().shareWeeks(iWeeks.get(i)))
    116                            iWeekAssignments[i].add(value.variable());
    117                }
    118            }
    119
    120            if (!isHard()) {
    121                Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class);
    122                if (criterion != null) {
    123                    double pref = nrViolations(null, null);
    124                    if (pref == 0)
    125                        iLastPreference = -Math.abs(iPreference);
    126                    else
    127                        iLastPreference = Math.abs(iPreference) * pref;
    128                    criterion.inc(assignment, iLastPreference);
    129                }
    130            }
    131        }
    132
    133        @Override
    134        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
    135            if (isCorectDayOfWeek(value)) {
    136                for (int i = 0; i < iWeeks.size(); i++)
    137                    if (value.getTimeLocation().shareWeeks(iWeeks.get(i)))
    138                        iWeekAssignments[i].add(value.variable());
    139                updateCriterion(assignment);
    140            }
    141        }
    142
    143        @Override
    144        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
    145            if (isCorectDayOfWeek(value)) {
    146                for (int i = 0; i < iWeeks.size(); i++)
    147                    if (value.getTimeLocation().shareWeeks(iWeeks.get(i)))
    148                        iWeekAssignments[i].remove(value.variable());
    149                updateCriterion(assignment);
    150            }
    151        }
    152
    153        public int nrWeeks(Placement value, Set<Placement> conflicts) {
    154            int ret = 0;
    155            for (int i = 0; i < iWeeks.size(); i++) {
    156                BitSet w = iWeeks.get(i);
    157                int cnt = iWeekAssignments[i].size();
    158                if (value != null) {
    159                    if (value.getTimeLocation().shareWeeks(w)) cnt ++;
    160                    if (iWeekAssignments[i].contains(value.variable())) cnt --;
    161                }
    162                if (conflicts != null) {
    163                    for (Placement conflict: conflicts) {
    164                        if (value != null && conflict.variable().equals(value.variable())) continue;
    165                        if (iWeekAssignments[i].contains(conflict.variable())) cnt --;
    166                    }
    167                }
    168                if (cnt > 0) ret++;
    169            }
    170            return ret;
    171        }
    172
    173        public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) {
    174            int bestCnt = 0;
    175            List<Integer> bestWeeks = new ArrayList<Integer>();
    176            for (int i = 0; i < iWeeks.size(); i++) {
    177                BitSet w = iWeeks.get(i);
    178                if (value.getTimeLocation().shareWeeks(w)) continue;
    179                int cnt = iWeekAssignments[i].size();
    180                if (iWeekAssignments[i].contains(value.variable())) cnt --;
    181                for (Placement conflict: conflicts) {
    182                    if (conflict.variable().equals(value.variable())) continue;
    183                    if (iWeekAssignments[i].contains(conflict.variable())) cnt --;
    184                }
    185                if (cnt <= 0) continue;
    186                if (bestWeeks.isEmpty() || bestCnt > cnt) {
    187                    bestWeeks.clear(); bestWeeks.add(i); bestCnt = cnt;
    188                } else if (bestCnt == cnt) {
    189                    bestWeeks.add(i);
    190                }
    191            }
    192            return bestWeeks.isEmpty() ? null : iWeekAssignments[ToolBox.random(bestWeeks)];
    193        }
    194
    195        public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
    196            int weeks = 0;
    197            for (int i = 0; i < iWeeks.size(); i++) {
    198                BitSet w = iWeeks.get(i);
    199                int cnt = iWeekAssignments[i].size();
    200                if (assignments != null) {
    201                    for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) {
    202                        if (isCorectDayOfWeek(entry.getValue()) && entry.getValue().getTimeLocation().shareWeeks(w)) cnt ++;
    203                        if (iWeekAssignments[i].contains(entry.getKey())) cnt --;
    204                    }
    205                }
    206                if (conflicts != null)
    207                    for (Placement conflict: conflicts) {
    208                        if (assignments != null && assignments.containsKey(conflict.variable())) continue;
    209                        if (iWeekAssignments[i].contains(conflict.variable())) cnt --;
    210                    }
    211                if (cnt > 0) weeks ++;
    212            }
    213            return (weeks <= iMaxWeeks ? 0 : weeks - iMaxWeeks);
    214        }
    215
    216    }
    217}