    001package org.cpsolver.coursett.constraint;
    002
    003import java.util.ArrayList;
    004import java.util.BitSet;
    005import java.util.Collections;
    006import java.util.HashMap;
    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.model.Lecture;
    015import org.cpsolver.coursett.model.Placement;
    016import org.cpsolver.ifs.assignment.Assignment;
    017import org.cpsolver.ifs.model.WeakeningConstraint;
    018import org.cpsolver.ifs.util.ToolBox;
    019
    020
    021/**
    022 *
    023 * The MaxBreaks constraint limits the number of blocks of non back-to-back classes of an instructor on a day.<br>
    024 * It has two parameters: a maximal number of breaks and a minimal length of a break between two classes not to be considered in the same block.<br>
    025 * Reference _MaxBreaks:1:30_ translates to a maximum number of one break (two blocks) on a day of classes not more than 30 minutes a part.<br>
    026 *
    027 * @author  Tomáš Müller
    028 * @version CourseTT 1.3 (University Course Timetabling)<br>
    029 *          Copyright (C) 2013 - 2014 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 MaxBreaksFlexibleConstraint extends FlexibleConstraint implements WeakeningConstraint<Lecture, Placement> {
    046    private int iMaxBreakBetweenBTB;
    047    protected int iMaxBlocksOnADay;
    048
    049    public MaxBreaksFlexibleConstraint(Long id, String owner, String preference, String reference) {
    050        super(id, owner, preference, reference);
    051
    052        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_BREAKS.getPattern()).matcher(reference);
    053        if (matcher.find()) {
    054            iMaxBlocksOnADay = 1 + Integer.parseInt(matcher.group(2));
    055            iMaxBreakBetweenBTB = Integer.parseInt(matcher.group(3)) / Constants.SLOT_LENGTH_MIN;
    056            iConstraintType = FlexibleConstraintType.MAX_BREAKS;
    057        }
    058    }
    059
    060    public List<Block> getBlocks(Assignment<Lecture, Placement> assignment, int dayCode, Set<Placement> conflicts, Placement value, HashMap<Lecture, Placement> assignments, BitSet week) {
    061        List<Placement> toBeSorted = new ArrayList<Placement>(getRelevantPlacements(assignment, dayCode, conflicts, value, assignments, week));
    062        Collections.sort(toBeSorted, new PlacementTimeComparator());
    063
    064        return mergeToBlocks(toBeSorted, iMaxBreakBetweenBTB);
    065    }
    066
    067    @Override
    068    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
    069        int penalty = 0;
    070        // constraint is checked for every day in week
    071        for (int dayCode : Constants.DAY_CODES) {
    072            // constraint is checked for every week in semester (or for the whole semester)
    073            for (BitSet week : getWeeks()) {
    074                // each blocks contains placements which are BTB
    075                List<Block> blocks = getBlocks(assignment, dayCode, null, null, assignments, week);
    076                // too many blocks -> increase penalty
    077                if (blocks.size() > iMaxBlocksOnADay)
    078                    penalty += (blocks.size() - iMaxBlocksOnADay) * (blocks.size() - iMaxBlocksOnADay);
    079            }
    080        }
    081        return penalty;
    082    }
    083
    084    @Override
    085    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    086        if (!isHard()) return;
    087
    088        if (((MaxBreaksFlexibleConstraintContext)getContext(assignment)).isWeak(value)) {
    089            for (Lecture v: variables())
    090                if (assignment.getValue(v) == null && !v.equals(value.variable())) {
    091                    // incomplete and week -- do not check for conflicts just yet
    092                    return;
    093                }
    094        }
    095
    096        // constraint is checked for every day in week
    097        for (int dayCode : Constants.DAY_CODES) {
    098            if ((value.getTimeLocation().getDayCode() & dayCode) == 0) continue; // ignore other days
    099            // constraint is checked for every week in semester (or for the whole semester)
    100            for (BitSet week : getWeeks()) {
    101                if (isPreciseDateComputation()) {
    102                    if (!value.getTimeLocation().overlaps(dayCode, week, getDayOfWeekOffset())) continue;
    103                } else {
    104                    if (week != null && !week.intersects(value.getTimeLocation().getWeekCode())) continue; // ignore other weeks
    105                }
    106                // each blocks contains placements which are BTB
    107                List<Block> blocks = getBlocks(assignment, dayCode, conflicts, value, null, week);
    108                while (blocks.size() > iMaxBlocksOnADay) {
    109                    // too many blocks -> identify adepts for unassignment
    110                    List<Block> adepts = new ArrayList<Block>(); int size = 0;
    111                    for (Block block: blocks) {
    112                        if (block.getPlacements().contains(value)) continue; // skip block containing given value
    113                        // select adepts of the smallest size
    114                        if (adepts.isEmpty() || size > block.getPlacements().size()) {
    115                            adepts.clear();
    116                            adepts.add(block);
    117                            size = block.getPlacements().size();
    118                        } else if (size == block.getPlacements().size()) {
    119                            adepts.add(block);
    120                        }
    121                    }
    122
    123                    // pick one randomly
    124                    Block block = ToolBox.random(adepts);
    125                    blocks.remove(block);
    126                    for (Placement conflict: block.getPlacements())
    127                        if (conflict.equals(assignment.getValue(conflict.variable())))
    128                            conflicts.add(conflict);
    129                }
    130            }
    131        }
    132    }
    133
    134    @Override
    135    public void weaken(Assignment<Lecture, Placement> assignment) {
    136    }
    137
    138    @Override
    139    public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
    140        if (isHard())
    141            ((MaxBreaksFlexibleConstraintContext)getContext(assignment)).weaken(value);
    142    }
    143
    144    @Override
    145    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    146        return new MaxBreaksFlexibleConstraintContext(assignment);
    147    }
    148
    149    public class MaxBreaksFlexibleConstraintContext extends FlexibleConstraintContext {
    150        private Map<Lecture, Placement> iWeakAssignment = new HashMap<Lecture, Placement>();
    151
    152        public MaxBreaksFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
    153            super(assignment);
    154        }
    155
    156        @Override
    157        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
    158            super.assigned(assignment, value);
    159            if (isHard())
    160                iWeakAssignment.remove(value.variable());
    161        }
    162
    163        public void weaken(Placement value) {
    164            if (isHard())
    165                iWeakAssignment.put(value.variable(), value);
    166        }
    167
    168        public boolean isWeak(Placement value) {
    169            return value.equals(iWeakAssignment.get(value.variable()));
    170        }
    171    }
    172
    173}