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