    001package org.cpsolver.coursett.constraint;
    002
    003import java.util.BitSet;
    004import java.util.HashMap;
    005import java.util.HashSet;
    006import java.util.Map;
    007import java.util.Set;
    008import java.util.regex.Matcher;
    009import java.util.regex.Pattern;
    010
    011import org.cpsolver.coursett.Constants;
    012import org.cpsolver.coursett.criteria.FlexibleConstraintCriterion;
    013import org.cpsolver.coursett.model.Lecture;
    014import org.cpsolver.coursett.model.Placement;
    015import org.cpsolver.ifs.assignment.Assignment;
    016import org.cpsolver.ifs.criteria.Criterion;
    017import org.cpsolver.ifs.util.ToolBox;
    018
    019/**
    020 *
    021 * The MaxConsecutiveDays constraint limits the number of consecutive days of week during which the given set of classes are taught.<br>
    022 * It has one parameter: a maximal number of consecutive days during which the given set of classes can be placed.<br>
    023 * Reference _MaxConsDays:2_ translates to a maximum number of 2 consecutive days a week (so for instance, Monday &amp; Tuesday,
    024 * Tuesday &amp; Wednesday, Wednesday &amp; Thursday, ...)<br>
    025 *
    026 * @author  Tomáš Müller
    027 * @version CourseTT 1.3 (University Course Timetabling)<br>
    028 *          Copyright (C) 2022 Tomáš Müller<br>
    029 * <br>
    030 *          This library is free software; you can redistribute it and/or modify
    031 *          it under the terms of the GNU Lesser General Public License as
    032 *          published by the Free Software Foundation; either version 3 of the
    033 *          License, or (at your option) any later version. <br>
    034 * <br>
    035 *          This library is distributed in the hope that it will be useful, but
    036 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    037 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    038 *          Lesser General Public License for more details. <br>
    039 * <br>
    040 *          You should have received a copy of the GNU Lesser General Public
    041 *          License along with this library; if not see
    042 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    043 */
    044public class MaxConsecutiveDaysFlexibleConstraint extends FlexibleConstraint {
    045private int iMaxDays;
    046
    047    public MaxConsecutiveDaysFlexibleConstraint(Long id, String owner, String preference, String reference) {
    048        super(id, owner, preference, reference);
    049
    050        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_CONSECUTIVE_DAYS.getPattern()).matcher(reference);
    051        if (matcher.find()) {
    052            iMaxDays = Integer.parseInt(matcher.group(2));
    053            iConstraintType = FlexibleConstraintType.MAX_CONSECUTIVE_DAYS;
    054        }
    055    }
    056
    057    @Override
    058    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
    059        return ((MaxConsecutiveDaysFlexibleConstraintContext)getContext(assignment)).nrViolations(assignments, conflicts);
    060    }
    061
    062    @Override
    063    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    064        if (!isHard()) return;
    065
    066        MaxConsecutiveDaysFlexibleConstraintContext context = (MaxConsecutiveDaysFlexibleConstraintContext)getContext(assignment);
    067        while (context.nrDays(value, conflicts) > iMaxDays && !conflicts.contains(value)) {
    068            Set<Lecture> candidates = context.candidates(value, conflicts);
    069            if (candidates == null) {
    070                conflicts.add(value);
    071                return;
    072            }
    073            for (Lecture candidate: candidates) {
    074                Placement conflict = assignment.getValue(candidate);
    075                if (conflict != null)
    076                    conflicts.add(conflict);
    077            }
    078        }
    079    }
    080
    081    @Override
    082    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
    083        if (!isHard()) return false;
    084        return ((MaxConsecutiveDaysFlexibleConstraintContext)getContext(assignment)).nrDays(value, null) > iMaxDays;
    085    }
    086
    087    @Override
    088    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    089        return new MaxConsecutiveDaysFlexibleConstraintContext(assignment);
    090    }
    091
    092    public class MaxConsecutiveDaysFlexibleConstraintContext extends FlexibleConstraintContext {
    093        private Map<BitSet, Set<Lecture>[]> iWeekDayAssignments = null;
    094        private Set<Lecture> iDayAssignments[] = null;
    095
    096        public MaxConsecutiveDaysFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
    097            super();
    098            for (BitSet week: getWeeks()) {
    099                Set<Lecture>[] dayAssignments = getDayAssignments(week);
    100                for (Lecture variable: variables()) {
    101                    Placement value = assignment.getValue(variable);
    102                    if (value != null) {
    103                        for (int i = 0; i < dayAssignments.length; i++)
    104                            if (overlaps(week, i, value))
    105                                dayAssignments[i].add(value.variable());
    106                    }
    107                }
    108            }
    109            if (!isHard()) {
    110                Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class);
    111                if (criterion != null) {
    112                    double pref = nrViolations(null, null);
    113                    if (pref == 0)
    114                        iLastPreference = -Math.abs(iPreference);
    115                    else
    116                        iLastPreference = Math.abs(iPreference) * pref;
    117                    criterion.inc(assignment, iLastPreference);
    118                }
    119            }
    120        }
    121
    122        protected boolean overlaps(BitSet week, int dayOfWeek, Placement value) {
    123            if (value == null || value.getTimeLocation() == null) return false;
    124            if (isPreciseDateComputation())
    125                return value.getTimeLocation().hasDate(dayOfWeek, week, getDayOfWeekOffset());
    126            if (week != null && !value.getTimeLocation().getWeekCode().intersects(week)) return false;
    127            return (value.getTimeLocation().getDayCode() & Constants.DAY_CODES[dayOfWeek]) != 0;
    128        }
    129
    130        @SuppressWarnings("unchecked")
    131        protected Set<Lecture>[] getDayAssignments(BitSet week) {
    132            if (week == null) {
    133                if (iDayAssignments == null) {
    134                    iDayAssignments = new Set[Constants.NR_DAYS];
    135                    for (int i = 0; i < iDayAssignments.length; i++)
    136                        iDayAssignments[i] = new HashSet<Lecture>();
    137                }
    138                return iDayAssignments;
    139            } else {
    140                if (iWeekDayAssignments == null)
    141                    iWeekDayAssignments = new HashMap<BitSet, Set<Lecture>[]>();
    142                Set<Lecture>[] dayAssignments = iWeekDayAssignments.get(week);
    143                if (dayAssignments == null) {
    144                    dayAssignments = new Set[Constants.NR_DAYS];
    145                    for (int i = 0; i < dayAssignments.length; i++)
    146                        dayAssignments[i] = new HashSet<Lecture>();
    147                    iWeekDayAssignments.put(week, dayAssignments);
    148                }
    149                return dayAssignments;
    150            }
    151        }
    152
    153        @Override
    154        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
    155            for (BitSet week: getWeeks()) {
    156                Set<Lecture>[] dayAssignments = getDayAssignments(week);
    157                for (int i = 0; i < dayAssignments.length; i++)
    158                    if (overlaps(week, i, value))
    159                        dayAssignments[i].add(value.variable());
    160            }
    161            updateCriterion(assignment);
    162        }
    163
    164        @Override
    165        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
    166            for (BitSet week: getWeeks()) {
    167                Set<Lecture>[] dayAssignments = getDayAssignments(week);
    168                for (int i = 0; i < dayAssignments.length; i++)
    169                    if (overlaps(week, i, value))
    170                        dayAssignments[i].remove(value.variable());
    171            }
    172            updateCriterion(assignment);
    173        }
    174
    175        public int nrDays(BitSet week, Placement value, Set<Placement> conflicts) {
    176            Set<Lecture>[] dayAssignments = getDayAssignments(week);
    177            Integer min = null, max = null;
    178            for (int i = 0; i < dayAssignments.length; i++) {
    179                int cnt = dayAssignments[i].size();
    180                if (value != null) {
    181                    if (overlaps(week, i, value)) cnt ++;
    182                    if (dayAssignments[i].contains(value.variable())) cnt --;
    183                }
    184                if (conflicts != null) {
    185                    for (Placement conflict: conflicts) {
    186                        if (value != null && conflict.variable().equals(value.variable())) continue;
    187                        if (dayAssignments[i].contains(conflict.variable())) cnt --;
    188                    }
    189                }
    190                if (cnt > 0) {
    191                    if (min == null) min = i;
    192                    max = i;
    193                }
    194            }
    195            if (min == null) return 0;
    196            return max - min + 1;
    197        }
    198
    199        public int nrDays(Placement value, Set<Placement> conflicts) {
    200            int ret = 0;
    201            for (BitSet week: getWeeks()) {
    202                int days = nrDays(week, value, conflicts);
    203                if (days > ret) ret = days;
    204            }
    205            return ret;
    206        }
    207
    208        public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) {
    209            for (BitSet week: getWeeks()) {
    210                Set<Lecture>[] dayAssignments = getDayAssignments(week);
    211                Integer min = null, max = null;
    212                Integer minThisPl = null, maxThisPl = null;
    213                for (int i = 0; i < dayAssignments.length; i++) {
    214                    int cnt = dayAssignments[i].size();
    215                    if (overlaps(week, i, value)) {
    216                        if (minThisPl == null) minThisPl = i;
    217                        maxThisPl = i;
    218                        cnt ++;
    219                    }
    220                    if (dayAssignments[i].contains(value.variable())) cnt --;
    221                    for (Placement conflict: conflicts) {
    222                        if (conflict.variable().equals(value.variable())) continue;
    223                        if (dayAssignments[i].contains(conflict.variable())) cnt --;
    224                    }
    225                    if (cnt > 0) {
    226                        if (min == null) min = i;
    227                        max = i;
    228                    }
    229                }
    230                if (min == null || max - min + 1 <= iMaxDays) continue;
    231                if ((minThisPl == null || min < minThisPl) && (maxThisPl == null || maxThisPl < max)) {
    232                    if (ToolBox.random() <= 0.5)
    233                        return dayAssignments[min];
    234                    else
    235                        return dayAssignments[max];
    236                }
    237                if (minThisPl == null || min < minThisPl)
    238                    return dayAssignments[min];
    239                if (maxThisPl == null || maxThisPl < max)
    240                    return dayAssignments[max];
    241            }
    242            return null;
    243        }
    244
    245        public int nrViolations(BitSet week, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
    246            Set<Lecture>[] dayAssignments = getDayAssignments(week);
    247            Integer min = null, max = null;
    248            for (int i = 0; i < dayAssignments.length; i++) {
    249                int cnt = dayAssignments[i].size();
    250                if (assignments != null) {
    251                    for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) {
    252                        Placement assignment = entry.getValue();
    253                        if (assignment != null && overlaps(week, i, assignment)) cnt ++;
    254                    }
    255                }
    256                if (conflicts != null) {
    257                    for (Placement conflict: conflicts) {
    258                        if (assignments != null && assignments.containsKey(conflict.variable())) continue;
    259                        if (dayAssignments[i].contains(conflict.variable())) cnt --;
    260                    }
    261                }
    262                if (cnt > 0) {
    263                    if (min == null) min = i;
    264                    max = i;
    265                }
    266            }
    267            if (min == null) return 0;
    268            return (max - min + 1 <= iMaxDays ? 0 : max - min + 1 - iMaxDays);
    269        }
    270
    271        public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
    272            int ret = 0;
    273            for (BitSet week: getWeeks()) {
    274                ret += nrViolations(week, assignments, conflicts);
    275            }
    276            return ret;
    277        }
    278
    279    }
    280}