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