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