    001package net.sf.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 net.sf.cpsolver.coursett.Constants;
    014import net.sf.cpsolver.coursett.model.Lecture;
    015import net.sf.cpsolver.coursett.model.Placement;
    016import net.sf.cpsolver.ifs.model.WeakeningConstraint;
    017import net.sf.cpsolver.ifs.util.ToolBox;
    018
    019/**
    020 *
    021 * The MaxBreaks constraint limits the number of blocks of non back-to-back classes of an instructor on a day.<br>
    022 * 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>
    023 * 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>
    024 *
    025 * @version CourseTT 1.2 (University Course Timetabling)<br>
    026 *          Copyright (C) 2013 Tomáš Müller<br>
    027 * <br>
    028 *          This library is free software; you can redistribute it and/or modify
    029 *          it under the terms of the GNU Lesser General Public License as
    030 *          published by the Free Software Foundation; either version 3 of the
    031 *          License, or (at your option) any later version. <br>
    032 * <br>
    033 *          This library is distributed in the hope that it will be useful, but
    034 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    035 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    036 *          Lesser General Public License for more details. <br>
    037 * <br>
    038 *          You should have received a copy of the GNU Lesser General Public
    039 *          License along with this library; if not see
    040 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    041 */
    042public class MaxBreaksFlexibleConstraint extends FlexibleConstraint implements WeakeningConstraint<Lecture, Placement> {
    043    private int iMaxBreakBetweenBTB;
    044    private int iMaxBlocksOnADay;
    045    private Map<Lecture, Placement> iWeakAssignment = new HashMap<Lecture, Placement>();
    046
    047    public MaxBreaksFlexibleConstraint(Long id, String owner, String preference, String reference) {
    048        super(id, owner, preference, reference);
    049
    050        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_BREAKS.getPattern()).matcher(reference);
    051        if (matcher.find()) {
    052            iMaxBlocksOnADay = 1 + Integer.parseInt(matcher.group(2));
    053            iMaxBreakBetweenBTB = Integer.parseInt(matcher.group(3)) / Constants.SLOT_LENGTH_MIN;
    054            iConstraintType = FlexibleConstraintType.MAX_BREAKS;
    055        }
    056    }
    057
    058    public List<Block> getBlocks(int dayCode, Set<Placement> conflicts, Placement value, HashMap<Lecture, Placement> assignments, BitSet week) {
    059        List<Placement> toBeSorted = new ArrayList<Placement>(getRelevantPlacements(dayCode, conflicts, value, assignments, week));
    060        Collections.sort(toBeSorted, new PlacementTimeComparator());
    061
    062        return mergeToBlocks(toBeSorted, iMaxBreakBetweenBTB);
    063    }
    064
    065    @Override
    066    public double getNrViolations(Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
    067        int penalty = 0;
    068        // constraint is checked for every day in week
    069        for (int dayCode : Constants.DAY_CODES) {
    070            // constraint is checked for every week in semester (or for the whole semester)
    071            for (BitSet week : getWeeks()) {
    072                // each blocks contains placements which are BTB
    073                List<Block> blocks = getBlocks(dayCode, null, null, assignments, week);
    074                // too many blocks -> increase penalty
    075                if (blocks.size() > iMaxBlocksOnADay)
    076                    penalty += (blocks.size() - iMaxBlocksOnADay) * (blocks.size() - iMaxBlocksOnADay);
    077            }
    078        }
    079        return penalty;
    080    }
    081
    082    @Override
    083    public void computeConflicts(Placement value, Set<Placement> conflicts) {
    084        if (!isHard()) return;
    085
    086        if (value.equals(iWeakAssignment.get(value.variable()))) {
    087            for (Lecture v: variables())
    088                if (v.getAssignment() == null && !v.equals(value.variable())) {
    089                    // incomplete and week -- do not check for conflicts just yet
    090                    return;
    091                }
    092        }
    093
    094        // constraint is checked for every day in week
    095        for (int dayCode : Constants.DAY_CODES) {
    096            if ((value.getTimeLocation().getDayCode() & dayCode) == 0) continue; // ignore other days
    097            // constraint is checked for every week in semester (or for the whole semester)
    098            for (BitSet week : getWeeks()) {
    099                if (week != null && !week.intersects(value.getTimeLocation().getWeekCode())) continue; // ignore other weeks
    100                // each blocks contains placements which are BTB
    101                List<Block> blocks = getBlocks(dayCode, conflicts, value, null, week);
    102                while (blocks.size() > iMaxBlocksOnADay) {
    103                    // too many blocks -> identify adepts for unassignment
    104                    List<Block> adepts = new ArrayList<Block>(); int size = 0;
    105                    for (Block block: blocks) {
    106                        if (block.getPlacements().contains(value)) continue; // skip block containing given value
    107                        // select adepts of the smallest size
    108                        if (adepts.isEmpty() || size > block.getPlacements().size()) {
    109                            adepts.clear();
    110                            adepts.add(block);
    111                            size = block.getPlacements().size();
    112                        } else if (size == block.getPlacements().size()) {
    113                            adepts.add(block);
    114                        }
    115                    }
    116
    117                    // pick one randomly
    118                    Block block = ToolBox.random(adepts);
    119                    blocks.remove(block);
    120                    for (Placement conflict: block.getPlacements())
    121                        if (conflict.equals(conflict.variable().getAssignment()))
    122                            conflicts.add(conflict);
    123                }
    124            }
    125        }
    126    }
    127
    128    @Override
    129    public void weaken() {
    130    }
    131
    132    @Override
    133    public void weaken(Placement value) {
    134        if (isHard())
    135            iWeakAssignment.put(value.variable(), value);
    136    }
    137
    138    @Override
    139    public void assigned(long iteration, Placement value) {
    140        super.assigned(iteration, value);
    141        if (isHard())
    142            iWeakAssignment.remove(value.variable());
    143    }
    144}