001 package net.sf.cpsolver.coursett.constraint;
002
003 import java.util.ArrayList;
004 import java.util.BitSet;
005 import java.util.Comparator;
006 import java.util.HashMap;
007 import java.util.HashSet;
008 import java.util.List;
009 import java.util.Set;
010
011 import net.sf.cpsolver.coursett.Constants;
012 import net.sf.cpsolver.coursett.criteria.FlexibleConstraintCriterion;
013 import net.sf.cpsolver.coursett.model.Lecture;
014 import net.sf.cpsolver.coursett.model.Placement;
015 import net.sf.cpsolver.coursett.model.TimeLocation;
016 import net.sf.cpsolver.coursett.model.TimetableModel;
017 import net.sf.cpsolver.ifs.model.Constraint;
018
019 /**
020 * Flexible constraint. <br>
021 * This constraint expresses relations between several classes. Provides similar
022 * functions as Group constraint. Unlike group constraint, Flexible constraint
023 * is able to parse some of its parameters from its reference field<br>
024 *
025 * @version CourseTT 1.2 (University Course Timetabling)<br>
026 * Copyright (C) 2013 Matej Lukac<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 */
042 public abstract class FlexibleConstraint extends Constraint<Lecture, Placement> {
043
044 private int iPreference;
045 private boolean iIsRequired;
046 private double iLastPreference;
047 private String iOwner;
048
049 // Constraint type
050 protected FlexibleConstraintType iConstraintType = null;
051
052 // A pattern the constraint was created from
053 protected String iReference = "";
054
055 // Determines whether the constraint is checked for every week in the semester
056 protected List<BitSet> iWeeks = null;
057
058 /**
059 * Flexible constraint types
060 *
061 */
062 public static enum FlexibleConstraintType {
063 /**
064 * Given classes must be taught in a way there is a break between two blocks of classes.
065 */
066 MAXBLOCK_BACKTOBACK("_(MaxBlock):([0-9]+):([0-9]+)_", MaxBlockFlexibleConstraint.class, "Block"),
067 /**
068 * There must be a break of a given length in a given time interval.
069 */
070 BREAK("_(Break):([0-9]+):([0-9]+):([0-9]+)_", BreakFlexibleConstraint.class, "Break"),
071 ;
072
073 private String iPattern;
074 private Class<? extends FlexibleConstraint> iImplementation;
075 private String iName;
076 FlexibleConstraintType(String pattern, Class<? extends FlexibleConstraint> implementation, String name) {
077 iPattern = pattern; iImplementation = implementation; iName = name;
078 }
079
080 public String getPattern() { return iPattern; }
081
082 public String getName() { return iName; }
083
084 public FlexibleConstraint create(Long id, String owner, String preference, String reference) throws IllegalArgumentException {
085 try {
086 return iImplementation.getConstructor(Long.class, String.class, String.class, String.class).newInstance(id, owner, preference, reference);
087 } catch (IllegalArgumentException e) {
088 throw e;
089 } catch (Exception e) {
090 throw new IllegalArgumentException(e.getMessage(), e);
091 }
092 }
093 }
094
095 @Override
096 public abstract void computeConflicts(Placement value, Set<Placement> conflicts);
097
098 /**
099 *
100 * @param conflicts conflicting placements to be unassigned
101 * @param assignments assigned placements
102 * @return the number of violations of the constraint during days and all weeks of the semester
103 */
104 public abstract double getNrViolations(Set<Placement> conflicts, HashMap<Lecture, Placement> assignments);
105
106 /**
107 *
108 * @param owner identifier of distribution preference the constraint was created for
109 * @param preference time preference ("R" for required, "P" for prohibited, "-2",
110 * "-1", "1", "2" for soft preference)
111 * @param reference parameters of the constraint in String form
112 */
113 public FlexibleConstraint(Long id, String owner, String preference, String reference){
114 super();
115 iId = id;
116 iReference = reference;
117 iPreference = Constants.preference2preferenceLevel(preference);
118 iIsRequired = preference.equals(Constants.sPreferenceRequired);
119 iOwner = owner;
120 }
121
122 /**
123 *
124 * @return i list of bitsets representing datePatterns or null if semester is whole semester is considered
125 */
126 public List<BitSet> getWeeks(){
127 if (iWeeks == null){
128 TimetableModel model = (TimetableModel) getModel();
129 iWeeks = new ArrayList<BitSet>();
130
131 boolean checkWeeks = model.getProperties().getPropertyBoolean("FlexibleConstraint.CheckWeeks", false);
132
133 if (checkWeeks) {
134 // get weeks method returns bitsets representing weeks during semester
135 iWeeks = model.getWeeks();
136 } else {
137 // weeks are not considered, all placements are taken into consideration
138 iWeeks.add(null);
139 }
140 }
141
142 return iWeeks;
143 }
144
145 @Override
146 public boolean isConsistent(Placement value1, Placement value2) {
147 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
148 if (value1 != null)
149 assignments.put(value1.variable(), value1);
150 if (value2 != null)
151 assignments.put(value2.variable(), value2);
152
153 if (getNrViolations(null, assignments) != 0) return false;
154
155 return super.isConsistent(value1, value2);
156 }
157
158 /**
159 * Returns placements of variables assigned to this constraint with assignment which satisfy following conditions:
160 * They must be taught in the day included in dayCode.
161 * They cannot be included in conflicts
162 * Their date pattern intersects with week
163 *
164 * @param dayCode representation of days in week combination
165 * @param conflicts placements to be unassigned
166 * @param value placement to be assigned
167 * @param assignments placements of variables
168 * @param week bitset representing a date pattern
169 * @return placements of variables assigned to this constraint with assignment which satisfy conditions above
170 */
171 protected Set<Placement> getRelevantPlacements(int dayCode, Set<Placement> conflicts, Placement value,
172 HashMap<Lecture, Placement> assignments, BitSet week) {
173 Set<Placement> placements = new HashSet<Placement>();
174
175 for (Lecture lecture : variables()) {
176 // lecture of the value is already assigned
177 if(value != null && lecture.equals(value.variable()))continue;
178
179 // lecture might not have assignment if it is present in assignments
180 if (assignments != null && assignments.containsKey(lecture)) {
181 TimeLocation t = assignments.get(lecture).getTimeLocation();
182 if (shareWeeksAndDay(t, week, dayCode))
183 placements.add(assignments.get(lecture));
184 continue;
185 }
186 if (lecture.getAssignment() == null || lecture.getAssignment().getTimeLocation() == null)
187 continue;
188 if (conflicts != null && conflicts.contains(lecture.getAssignment()))
189 continue;
190
191 TimeLocation t = lecture.getAssignment().getTimeLocation();
192 if (t == null || !shareWeeksAndDay(t, week, dayCode))
193 continue;
194
195 placements.add(lecture.getAssignment());
196 }
197
198 if (value == null || (conflicts != null && conflicts.contains(value))) {
199 return placements;
200 }
201
202 if (shareWeeksAndDay(value.getTimeLocation(), week, dayCode)) placements.add(value);
203
204 return placements;
205 }
206
207 /**
208 * Used to determine the daycode and week of a timelocation
209 *
210 * @param t timelocation
211 * @param week date pattern compared to timelocation
212 * @param dayCode days compared to timelocation
213 * @return true if TimeLocation matches the date pattern and days
214 */
215 private boolean shareWeeksAndDay(TimeLocation t, BitSet week, int dayCode){
216 boolean matchDay = (t.getDayCode() & dayCode) != 0;
217 boolean matchWeek = (week == null || t.shareWeeks(week));
218
219 return matchDay && matchWeek;
220 }
221
222 /**
223 * Creates a list of blocks from a placements sorted by startSlot
224 *
225 * @param sorted list of placements sorted by startSlot
226 * @param maxBreakBetweenBTB maximum number of free slots between BTB placements
227 * @return groups of BTB placements as a list of blocks
228 */
229 protected List<Block> mergeToBlocks(List<Placement> sorted, int maxBreakBetweenBTB){
230 List<Block> blocks = new ArrayList<Block>();
231 // add placements to blocks
232 for (int i = 0; i < sorted.size(); i++) {
233 Placement placement = sorted.get(i);
234 boolean added = false;
235 // add placement to a suitable block
236 for (int j = 0; j < blocks.size(); j++) {
237 if (blocks.get(j).addPlacement(placement)) {
238 added = true;
239 }
240 }
241 // create a new block if a lecture does not fit into any block
242 if (!added) {
243 Block block = new Block(maxBreakBetweenBTB);
244 block.addPlacement(placement);
245 blocks.add(block);
246 }
247 }
248 return blocks;
249 }
250
251 @Override
252 public boolean isHard() {
253 return iIsRequired;
254 }
255
256 @Override
257 public String getName() {
258 return iOwner + ": " + iConstraintType.getName();
259 }
260
261 public FlexibleConstraintType getType(){
262 return iConstraintType;
263 }
264
265 @Override
266 public void assigned(long iteration, Placement value) {
267 super.assigned(iteration, value);
268 updateCriterion();
269 }
270
271 public String getReference() {
272 return iReference;
273 }
274
275 public String getOwner() {
276 return iOwner;
277 }
278
279 /**
280 * Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for
281 * preference
282 */
283 public String getPrologPreference() {
284 return Constants.preferenceLevel2preference(iPreference);
285 }
286
287 /**
288 * Update value of FlexibleConstraintCriterion and number of violated FlexibleConstraints
289 */
290 private void updateCriterion() {
291 FlexibleConstraintCriterion pc = (FlexibleConstraintCriterion)getModel().getCriterion(FlexibleConstraintCriterion.class);
292 if (pc != null) {
293 if (!isHard()){
294 pc.inc(-iLastPreference);
295 iLastPreference = getCurrentPreference(null, null);
296 pc.inc(iLastPreference);
297 }
298 }
299 }
300
301 /**
302 * Return the current preference of the flexible constraint, considering conflicts and new assignments.
303 * Used to compute value for flexible constraint criterion.
304 *
305 * @param conflicts
306 * @param assignments
307 * @return the current preference of the flexible constraint
308 */
309 public double getCurrentPreference(Set<Placement> conflicts, HashMap<Lecture, Placement> assignments){
310 double pref = getNrViolations(conflicts, assignments);
311 if(pref == 0){
312 return - Math.abs(iPreference);
313 }
314 return Math.abs(iPreference) * pref;
315 }
316
317 @Override
318 public void unassigned(long iteration, Placement value) {
319 super.unassigned(iteration, value);
320 updateCriterion();
321 }
322
323 /**
324 * A block is a list of placements sorted by startSlot, which are BTB.
325 * maxSlotsBetweenBackToBack determines the number of free slots between two BTB placements
326 *
327 */
328 public class Block {
329
330 // start slot of the block
331 private int startSlotCurrentBlock = -1;
332 // end slot of the block
333 private int endSlotCurrentBlock = -1;
334 // max number of slots between classes to be considered Back-To-Back; 4 slots default
335 private int maxSlotsBetweenBackToBack = 4;
336 // the list of placements of this block
337 private List<Placement> placements = new ArrayList<Placement>();
338
339 public Block(int maxSlotsBetweenBTB){
340 this.maxSlotsBetweenBackToBack = maxSlotsBetweenBTB;
341 }
342
343 /**
344 * Adds placement to the block and updates block's attributes.
345 *
346 * @param placement placement to be added to the block
347 * @return true if the placement was successfully added to the block
348 */
349 public boolean addPlacement(Placement placement){
350 if (placement == null){
351 return false;
352 }
353
354 TimeLocation t = placement.getTimeLocation();
355
356 if (t == null){
357 return false;
358 }
359
360 // if placements is empty, the block only contains currently added placement -> set start and end
361 if (placements.isEmpty()){
362 placements.add(placement);
363 startSlotCurrentBlock = t.getStartSlot();
364 endSlotCurrentBlock = t.getStartSlot() + t.getLength();
365 return true;
366 }
367
368 // if startSlotCurrentBlock equals placement's start slot, add placement and adjust endSlotCurrentBlock
369 if (t.getStartSlot() == startSlotCurrentBlock){
370 placements.add(placement);
371 int tEnd = t.getStartSlot() + t.getLength();
372 if (tEnd > endSlotCurrentBlock){
373 endSlotCurrentBlock = tEnd;
374 }
375 return true;
376 }
377
378 // if placement starts among endSlotCurrentBlock + modifier and startSlotCurrentBlock, add the placement
379 if (endSlotCurrentBlock + maxSlotsBetweenBackToBack >= t.getStartSlot() && t.getStartSlot() >= startSlotCurrentBlock ){
380 placements.add(placement);
381 int tEnd = t.getStartSlot() + t.getLength();
382 if (tEnd > endSlotCurrentBlock){
383 endSlotCurrentBlock = tEnd;
384 }
385 return true;
386 }
387
388 return false;
389 }
390
391 public boolean haveSameStartTime() {
392 if (!placements.isEmpty()) {
393 int startSlot = placements.get(0).getTimeLocation().getStartSlot();
394 for (Placement p : getPlacements()) {
395 if (p.getTimeLocation().getStartSlot() != startSlot)
396 return false;
397 }
398 }
399 return true;
400 }
401
402 public int getStartSlotCurrentBlock(){
403 return startSlotCurrentBlock;
404 }
405
406 public int getEndSlotCurrentBlock(){
407 return endSlotCurrentBlock;
408 }
409
410 public int getNbrPlacements(){
411 return placements.size();
412 }
413
414 public List<Placement> getPlacements(){
415 return placements;
416 }
417
418 public int getLengthInSlots(){
419 return endSlotCurrentBlock - startSlotCurrentBlock;
420 }
421
422 @Override
423 public String toString(){
424 return "[" + startSlotCurrentBlock + ", " + endSlotCurrentBlock + "]" + " PlacementsNbr: "+ getNbrPlacements();
425 }
426 }
427
428 /**
429 * Placement comparator: earlier placement first, shorter placement first if both start at the same time.
430 */
431 protected static class PlacementTimeComparator implements Comparator<Placement> {
432 @Override
433 public int compare(Placement p1, Placement p2) {
434 TimeLocation t1 = p1.getTimeLocation(), t2 = p2.getTimeLocation();
435 // compare by start time (earlier first)
436 if (t1.getStartSlot() < t2.getStartSlot())
437 return -1;
438 if (t1.getStartSlot() > t2.getStartSlot())
439 return 1;
440 // same start -> compare by length (shorter first)
441 if (t1.getLength() < t2.getLength())
442 return -1;
443 if (t1.getLength() > t2.getLength())
444 return 1;
445 // fallback
446 return 0;
447 }
448 }
449
450 @Override
451 public String toString() {
452 return getName();
453 }
454 }