    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.coursett.model.TimeLocation;
    017import org.cpsolver.coursett.model.TimetableModel;
    018import org.cpsolver.ifs.assignment.Assignment;
    019import org.cpsolver.ifs.criteria.Criterion;
    020import org.cpsolver.ifs.model.Model;
    021import org.cpsolver.ifs.util.ToolBox;
    022
    023/**
    024 *
    025 * The MaxHalfDays constraint limits the number of half-days of week during which the given set of classes are taught.<br>
    026 * It has one parameter: a maximal number of week half-days during which the given set of classes can be placed.<br>
    027 * A day is split by noon (which can be changed using General.HalfDaySlot parameter). A class starting before noon is considered
    028 * a morning class (despite of its end), a class starting at noon or later is considered an afternoon class.<br>
    029 * Reference _MaxHalfDays:4_ translates to a maximum number of 4 half-days a week<br>
    030 *
    031 * @version CourseTT 1.3 (University Course Timetabling)<br>
    032 *          Copyright (C) 2017 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 MaxHalfDaysFlexibleConstraint extends FlexibleConstraint {
    049    private int iMaxHalfDays;
    050    private int iNoonSlot = 144;
    051
    052    public MaxHalfDaysFlexibleConstraint(Long id, String owner, String preference, String reference) {
    053        super(id, owner, preference, reference);
    054
    055        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_HALF_DAYS.getPattern()).matcher(reference);
    056        if (matcher.find()) {
    057            iMaxHalfDays = Integer.parseInt(matcher.group(2));
    058            iConstraintType = FlexibleConstraintType.MAX_HALF_DAYS;
    059        }
    060    }
    061
    062    @Override
    063    public void setModel(Model<Lecture, Placement> model) {
    064        super.setModel(model);
    065        iNoonSlot = ((TimetableModel)model).getProperties().getPropertyInt("General.HalfDaySlot", iNoonSlot);
    066    }
    067
    068    /**
    069     * Returns number of half-days in a day
    070     */
    071    protected int getNrHalfDays() {
    072        return 2;
    073    }
    074
    075    /**
    076     * Returns index of the half day
    077     * @param time given time
    078     * @return 0 for morning, 1 for evening
    079     */
    080    protected int getHalfDay(TimeLocation time) {
    081        return (time.getStartSlot() < iNoonSlot ? 0 : 1);
    082    }
    083
    084    @Override
    085    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
    086        return ((MaxHalfDaysFlexibleConstraintContext)getContext(assignment)).nrViolations(assignments, conflicts);
    087    }
    088
    089    @Override
    090    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    091        if (!isHard()) return;
    092
    093        MaxHalfDaysFlexibleConstraintContext context = (MaxHalfDaysFlexibleConstraintContext)getContext(assignment);
    094        while (context.nrHalfDays(value, conflicts) > iMaxHalfDays) {
    095            Set<Lecture> candidates = context.candidates(value, conflicts);
    096            if (candidates == null) return;
    097            for (Lecture candidate: candidates) {
    098                Placement conflict = assignment.getValue(candidate);
    099                if (conflict != null)
    100                    conflicts.add(conflict);
    101            }
    102        }
    103    }
    104
    105    @Override
    106    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
    107        if (!isHard()) return false;
    108        return ((MaxHalfDaysFlexibleConstraintContext)getContext(assignment)).nrHalfDays(value, null) > iMaxHalfDays;
    109    }
    110
    111    @Override
    112    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    113        return new MaxHalfDaysFlexibleConstraintContext(assignment);
    114    }
    115
    116    public class MaxHalfDaysFlexibleConstraintContext extends FlexibleConstraintContext {
    117        private Set<Lecture> iHalfDayAssignments[] = null;
    118
    119        @SuppressWarnings("unchecked")
    120        public MaxHalfDaysFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
    121            super();
    122            iHalfDayAssignments = new Set[getNrHalfDays() * Constants.NR_DAYS];
    123            for (int i = 0; i < iHalfDayAssignments.length; i++)
    124                iHalfDayAssignments[i] = new HashSet<Lecture>();
    125
    126            for (Lecture variable: variables()) {
    127                Placement value = assignment.getValue(variable);
    128                if (value != null) {
    129                    for (int i = 0; i < Constants.DAY_CODES.length; i++)
    130                        if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0)
    131                            iHalfDayAssignments[i * getNrHalfDays() + getHalfDay(value.getTimeLocation())].add(value.variable());
    132                }
    133            }
    134
    135            if (!isHard()) {
    136                Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class);
    137                if (criterion != null) {
    138                    double pref = nrViolations(null, null);
    139                    if (pref == 0)
    140                        iLastPreference = -Math.abs(iPreference);
    141                    else
    142                        iLastPreference = Math.abs(iPreference) * pref;
    143                    criterion.inc(assignment, iLastPreference);
    144                }
    145            }
    146        }
    147
    148        @Override
    149        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
    150            for (int i = 0; i < Constants.DAY_CODES.length; i++)
    151                if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0)
    152                    iHalfDayAssignments[i * getNrHalfDays() + getHalfDay(value.getTimeLocation())].add(value.variable());
    153            updateCriterion(assignment);
    154        }
    155
    156        @Override
    157        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
    158            for (int i = 0; i < Constants.DAY_CODES.length; i++)
    159                if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0)
    160                    iHalfDayAssignments[i * getNrHalfDays() + getHalfDay(value.getTimeLocation())].remove(value.variable());
    161            updateCriterion(assignment);
    162        }
    163
    164        public int nrHalfDays(Placement value, Set<Placement> conflicts) {
    165            int ret = 0;
    166            for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    167                for (int j = 0; j < getNrHalfDays(); j++) {
    168                    int idx = i * getNrHalfDays() + j;
    169                    int cnt = iHalfDayAssignments[idx].size();
    170                    if (value != null) {
    171                        if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0 && j == getHalfDay(value.getTimeLocation())) cnt ++;
    172                        if (iHalfDayAssignments[idx].contains(value.variable())) cnt --;
    173                    }
    174                    if (conflicts != null) {
    175                        for (Placement conflict: conflicts) {
    176                            if (value != null && conflict.variable().equals(value.variable())) continue;
    177                            if (iHalfDayAssignments[idx].contains(conflict.variable())) cnt --;
    178                        }
    179                    }
    180                    if (cnt > 0) ret++;
    181                }
    182            }
    183            return ret;
    184        }
    185
    186        public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) {
    187            int bestCnt = 0;
    188            List<Integer> bestHalfDays = new ArrayList<Integer>();
    189            for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    190                for (int j = 0; j < getNrHalfDays(); j++) {
    191                    int idx = i * getNrHalfDays() + j;
    192                    if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0 && j == getHalfDay(value.getTimeLocation())) continue;
    193                    int cnt = iHalfDayAssignments[idx].size();
    194                    if (iHalfDayAssignments[idx].contains(value.variable())) cnt --;
    195                    for (Placement conflict: conflicts) {
    196                        if (conflict.variable().equals(value.variable())) continue;
    197                        if (iHalfDayAssignments[idx].contains(conflict.variable())) cnt --;
    198                    }
    199                    if (cnt <= 0) continue;
    200                    if (bestHalfDays.isEmpty() || bestCnt > cnt) {
    201                        bestHalfDays.clear(); bestHalfDays.add(idx); bestCnt = cnt;
    202                    } else if (bestCnt == cnt) {
    203                        bestHalfDays.add(idx);
    204                    }
    205                }
    206            }
    207            return bestHalfDays.isEmpty() ? null : iHalfDayAssignments[ToolBox.random(bestHalfDays)];
    208        }
    209
    210        public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
    211            int halfDays = 0;
    212            for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    213                for (int j = 0; j < getNrHalfDays(); j++) {
    214                    int idx = i * getNrHalfDays() + j;
    215                    int cnt = iHalfDayAssignments[idx].size();
    216                    if (assignments != null) {
    217                        for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) {
    218                            Placement assignment = entry.getValue();
    219                            if (assignment != null && (assignment.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0 && j == getHalfDay(assignment.getTimeLocation())) cnt ++;
    220                        }
    221                    }
    222                    if (conflicts != null)
    223                        for (Placement conflict: conflicts) {
    224                            if (assignments != null && assignments.containsKey(conflict.variable())) continue;
    225                            if (iHalfDayAssignments[idx].contains(conflict.variable())) cnt --;
    226                        }
    227                    if (cnt > 0) halfDays ++;
    228                }
    229            }
    230            return (halfDays <= iMaxHalfDays ? 0 : halfDays - iMaxHalfDays);
    231        }
    232
    233    }
    234}