001 package net.sf.cpsolver.coursett.constraint;
002
003 import java.util.ArrayList;
004 import java.util.BitSet;
005 import java.util.Collections;
006 import java.util.HashMap;
007 import java.util.HashSet;
008 import java.util.List;
009 import java.util.Set;
010 import java.util.regex.Matcher;
011 import java.util.regex.Pattern;
012
013 import net.sf.cpsolver.coursett.Constants;
014 import net.sf.cpsolver.coursett.model.Lecture;
015 import net.sf.cpsolver.coursett.model.Placement;
016 import net.sf.cpsolver.ifs.util.ToolBox;
017
018 /**
019 *
020 * The MaxBlock constraint checks for too big blocks of back-to-back classes of an instructor.<br>
021 * It has two parameters: a maximal length of a back-to-back block that is allowed and a minimal length of a break between two classes not to be considered in the same block.<br>
022 * Reference _MaxBlock:120:30_ translates to a maximal block of at most 2 hours (120 minutes) with classes not more than 30 minutes a part.<br>
023 *
024 * @version CourseTT 1.2 (University Course Timetabling)<br>
025 * Copyright (C) 2013 Matej Lukac<br>
026 * <br>
027 * This library is free software; you can redistribute it and/or modify
028 * it under the terms of the GNU Lesser General Public License as
029 * published by the Free Software Foundation; either version 3 of the
030 * License, or (at your option) any later version. <br>
031 * <br>
032 * This library is distributed in the hope that it will be useful, but
033 * WITHOUT ANY WARRANTY; without even the implied warranty of
034 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
035 * Lesser General Public License for more details. <br>
036 * <br>
037 * You should have received a copy of the GNU Lesser General Public
038 * License along with this library; if not see
039 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
040 */
041 public class MaxBlockFlexibleConstraint extends FlexibleConstraint {
042
043 // max number of slots between to classes to be considered Back-To-Back
044 private int iMaxBreakBetweenBTB;
045 // max length of a block of classes taught Back-To-Back
046 private int iMaxBlockSlotsBTB;
047
048 /**
049 *
050 * @param owner identifier of distribution preference the constraint was created for
051 * @param preference time preference ("R" for required, "P" for prohibited, "-2",
052 * "-1", "1", "2" for soft preference)
053 * @param reference parameters of the constraint in String form
054 */
055 public MaxBlockFlexibleConstraint(Long id, String owner, String preference, String reference) {
056 super(id, owner, preference, reference);
057
058 Pattern pattern = null;
059 Matcher matcher = null;
060
061 // recognize Break constraint
062 String patternString = "_(MaxBlock):([0-9]+):([0-9]+)_";
063 pattern = Pattern.compile(patternString);
064 matcher = pattern.matcher(reference);
065 if (matcher.find()) {
066 iMaxBlockSlotsBTB = Integer.parseInt(matcher.group(2))/Constants.SLOT_LENGTH_MIN;
067 iMaxBreakBetweenBTB = Integer.parseInt(matcher.group(3))/Constants.SLOT_LENGTH_MIN;
068 iConstraintType = FlexibleConstraint.FlexibleConstraintType.MAXBLOCK_BACKTOBACK;
069 }
070
071 }
072
073 @Override
074 public void computeConflicts(Placement value, Set<Placement> conflicts) {
075 if (!isHard())
076 return;
077
078 List<BitSet> weeks = getWeeks();
079
080 // constraint is checked for every day in week
081 for (int dayCode : Constants.DAY_CODES) {
082 // constraint is checked for every week in semester (or for the whole semester)
083 for (BitSet week : weeks) {
084 boolean isProblem = false;
085 do {
086 isProblem = false;
087 // each blocks contains placements which are BTB
088 List<Block> blocks = getBlocks(dayCode, conflicts, value, null, week);
089 for (Block block : blocks) {
090 // if the block is not affected by the current placement, continue
091 if (!block.getPlacements().contains(value)){
092 continue;
093 }
094 Set<Placement> adepts = new HashSet<Placement>();
095 // if there is only 1 placement in block, the block cannot be shortened
096 // if placements of a block start at the same time, they intersect
097 // this solves problem when between 2 classes is required MEET_TOGETHER
098 if (block.getNbrPlacements() == 1 || block.haveSameStartTime())
099 continue;
100 // if block is longer than maximum size, some of its placements are conflicts
101 if (block.getLengthInSlots() > iMaxBlockSlotsBTB) {
102 // classes from block are potential conflicts
103 adepts.addAll(block.getPlacements());
104 // do not set currently assigned value as conflict
105 adepts.remove(value);
106 isProblem = true;
107 // pick random placement
108 Placement conflict = ToolBox.random(adepts);
109 if (conflict != null) {
110 conflicts.add(conflict);
111 }
112 }
113 }
114 } while (isProblem);
115 }
116 }
117 }
118
119 public List<Block> getBlocks(int dayCode, Set<Placement> conflicts, Placement value, HashMap<Lecture, Placement> assignments, BitSet week) {
120 List<Placement> toBeSorted = new ArrayList<Placement>(getRelevantPlacements(dayCode, conflicts, value, assignments, week));
121 Collections.sort(toBeSorted, new PlacementTimeComparator());
122
123 return mergeToBlocks(toBeSorted, iMaxBreakBetweenBTB);
124 }
125
126 @Override
127 public double getNrViolations(Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
128 List<BitSet> weeks = getWeeks();
129
130 int violatedBlocks = 0;
131 for (int dayCode : Constants.DAY_CODES) {
132 for (BitSet week : weeks) {
133 List<Block> blocks = getBlocks(dayCode, null, null, assignments, week);
134 for (Block block : blocks) {
135 if (block.getNbrPlacements() == 1 || block.haveSameStartTime())
136 continue;
137 // violated if there is a block containing more than one
138 // class longer than iMaxBlockSlotsBTB
139 if (block.getLengthInSlots() > iMaxBlockSlotsBTB) {
140 int blockLengthPenalty = block.getLengthInSlots() / iMaxBlockSlotsBTB;
141 violatedBlocks += blockLengthPenalty;
142 }
143 }
144 }
145 }
146 return violatedBlocks;
147 }
148
149 }