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 Break constraint checks for instructor lunch break or a break in general in between the given classes.<br>
021 * It has three parameters: a start and an end time of a window in which the break is required / preferred, and a minimal length of a break that is needed.<br>
022 * Reference _Break:132:162:30_ translates to a break of at least 30 minutes between 11 am (slot 132) and 1:30 pm (slot 162).<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 BreakFlexibleConstraint extends FlexibleConstraint {
042
043 // LunchBreak constraint parameters
044 private int iBreakStart;
045 private int iBreakEnd;
046 private int iBreakLength;
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 BreakFlexibleConstraint(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 = "_(Break):([0-9]+):([0-9]+):([0-9]+)_";
063 pattern = Pattern.compile(patternString);
064 matcher = pattern.matcher(reference);
065 if (matcher.find()) {
066 iBreakStart = Integer.parseInt(matcher.group(2));
067 iBreakEnd = Integer.parseInt(matcher.group(3));
068 iBreakLength = Integer.parseInt(matcher.group(4))/Constants.SLOT_LENGTH_MIN;
069 iConstraintType = FlexibleConstraintType.BREAK;
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 // checks only placements in the break time
081 if (value.getTimeLocation().getStartSlot() <= iBreakEnd
082 && value.getTimeLocation().getStartSlot() + value.getTimeLocation().getLength() > iBreakStart) {
083
084 for (int dayCode : Constants.DAY_CODES) {
085 // checks only days affected by the placement
086 if ((value.getTimeLocation().getDayCode() & dayCode) != 0) {
087 // constraint is checked for every week in semester (or for the whole semester)
088 for (BitSet week : weeks) {
089 boolean isProblem = false;
090 do {
091 Set<Placement> adepts = new HashSet<Placement>();
092 // each blocks contains placements which are BTB
093 // placements are BTB if there is less time between them than the minimal break length
094 List<Block> blocks = getBreakBlocks(dayCode, conflicts, value, null, week);
095 // determine possible conflicts from blocks' placements
096 getAdeptsLunchBreak(blocks, adepts);
097 if (adepts.isEmpty())
098 isProblem = false;
099 // currently assigned value shouldn't be added to conflicts if possible
100 if (adepts.size() >= 2)
101 adepts.remove(value);
102 // pick random placement
103 Placement conflict = ToolBox.random(adepts);
104 if (conflict != null) {
105 conflicts.add(conflict);
106 }
107 } while (isProblem);
108 }
109 }
110 }
111 }
112 }
113
114 /**
115 * Creates a list of consecutive blocks with back-to-back classes.
116 */
117 public List<Block> getBreakBlocks(int dayCode, Set<Placement> conflicts, Placement value, HashMap<Lecture, Placement> assignments, BitSet week) {
118
119 List<Placement> toBeSorted = new ArrayList<Placement>(getRelevantPlacements(dayCode, conflicts, value, assignments, week));
120 Collections.sort(toBeSorted, new PlacementTimeComparator());
121
122 return mergeToBlocks(toBeSorted, iBreakLength);
123 }
124
125
126
127 /**
128 * Method adds Placements from blocks to adepts if there is a possibility, that the placement caused constraint violation
129 *
130 * @param blocks placements in
131 * @param adepts
132 */
133 private void getAdeptsLunchBreak(List<Block> blocks, Set<Placement> adepts) {
134 List<Block> matchingBlocks = new ArrayList<Block>();
135 for(Block block: blocks){
136 // if block intersects with break interval, it will be used in conflict selection
137 if (block.getStartSlotCurrentBlock() <= iBreakEnd && block.getEndSlotCurrentBlock() >= iBreakStart) matchingBlocks.add(block);
138 }
139 int size = matchingBlocks.size();
140 // if there is none block intersecting with break interval, the constraint is satisfied
141 // if there are at least 2 blocks intersecting with break interval, the constraint is satisfied,
142 // because there must be a space between them, otherwise they would be in one block
143 // if there is only one block intersecting with break interval, constraint might not be satisfied
144 if (size == 1) {
145 Block block = matchingBlocks.get(0);
146 // check whether the block leaves enough space for break
147 if (block.getStartSlotCurrentBlock() - iBreakStart >= iBreakLength || iBreakEnd - block.getEndSlotCurrentBlock() >= iBreakLength){
148 return;
149 // if it doesn't
150 }else{
151 // every placement intersecting with break interval might be potential conflict
152 for (Placement p: block.getPlacements()){
153 if ( p.getTimeLocation().getStartSlot() <= iBreakEnd && p.getTimeLocation().getStartSlot()+ p.getTimeLocation().getLength() >= iBreakStart){
154 adepts.add(p);
155 }
156 }
157 }
158 }
159 }
160
161 @Override
162 public double getNrViolations(Set<Placement> conflicts, HashMap<Lecture, Placement> assignments){
163 List<BitSet> weeks = getWeeks();
164
165 int violatedDays = 0;
166 for (int dayCode : Constants.DAY_CODES) {
167 weekIteration: for (BitSet week : weeks) {
168 Set<Placement> adepts = new HashSet<Placement>();
169 List<Block> blocks = getBreakBlocks(dayCode, null, null, assignments, week);
170 getAdeptsLunchBreak(blocks, adepts);
171 if (!adepts.isEmpty())
172 violatedDays++;
173 break weekIteration;
174 }
175 }
176 return violatedDays;
177 }
178
179 }