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