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 private String iPattern; 085 private Class<? extends FlexibleConstraint> iImplementation; 086 private String iName; 087 FlexibleConstraintType(String pattern, Class<? extends FlexibleConstraint> implementation, String name) { 088 iPattern = pattern; iImplementation = implementation; iName = name; 089 } 090 091 public String getPattern() { return iPattern; } 092 093 public String getName() { return iName; } 094 095 public FlexibleConstraint create(Long id, String owner, String preference, String reference) throws IllegalArgumentException { 096 try { 097 return iImplementation.getConstructor(Long.class, String.class, String.class, String.class).newInstance(id, owner, preference, reference); 098 } catch (IllegalArgumentException e) { 099 throw e; 100 } catch (Exception e) { 101 throw new IllegalArgumentException(e.getMessage(), e); 102 } 103 } 104 } 105 106 /** 107 * Constructor 108 * @param id unique id 109 * @param owner identifier of distribution preference the constraint was created for 110 * @param preference time preference ("R" for required, "P" for prohibited, "-2", 111 * "-1", "1", "2" for soft preference) 112 * @param reference parameters of the constraint in String form 113 */ 114 public FlexibleConstraint(Long id, String owner, String preference, String reference){ 115 super(); 116 iId = id; 117 iReference = reference; 118 iPreference = Constants.preference2preferenceLevel(preference); 119 iIsRequired = preference.equals(Constants.sPreferenceRequired); 120 iOwner = owner; 121 } 122 123 124 /** 125 * Return current number of violations. 126 * @param assignment current assignment 127 * @param conflicts conflicting placements to be unassigned 128 * @param assignments assigned placements 129 * @return the number of violations of the constraint during days and all weeks of the semester 130 */ 131 public abstract double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments); 132 133 134 /** 135 * Return weeks of the term. 136 * @return a list of bitsets (one for each week of the term) representing datePatterns or null if semester is whole semester is considered 137 */ 138 public List<BitSet> getWeeks(){ 139 if (iWeeks == null){ 140 TimetableModel model = (TimetableModel) getModel(); 141 iWeeks = new ArrayList<BitSet>(); 142 143 boolean checkWeeks = model.getProperties().getPropertyBoolean("FlexibleConstraint.CheckWeeks", false); 144 145 if (checkWeeks) { 146 // get weeks method returns bitsets representing weeks during semester 147 iWeeks = model.getWeeks(); 148 } else { 149 // weeks are not considered, all placements are taken into consideration 150 iWeeks.add(null); 151 } 152 } 153 154 return iWeeks; 155 } 156 157 @Override 158 public boolean isConsistent(Placement value1, Placement value2) { 159 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 160 if (value1 != null) 161 assignments.put(value1.variable(), value1); 162 if (value2 != null) 163 assignments.put(value2.variable(), value2); 164 165 if (getNrViolations(null, null, assignments) != 0) return false; 166 167 return super.isConsistent(value1, value2); 168 } 169 170 /** 171 * Returns placements of variables assigned to this constraint with assignment which satisfy following conditions: 172 * They must be taught in the day included in dayCode. 173 * They cannot be included in conflicts 174 * Their date pattern intersects with week 175 * 176 * @param assignment current assignment 177 * @param dayCode representation of days in week combination 178 * @param conflicts placements to be unassigned 179 * @param value placement to be assigned 180 * @param assignments placements of variables 181 * @param week bitset representing a date pattern 182 * @return placements of variables assigned to this constraint with assignment which satisfy conditions above 183 */ 184 protected Set<Placement> getRelevantPlacements(Assignment<Lecture, Placement> assignment, int dayCode, Set<Placement> conflicts, Placement value, 185 HashMap<Lecture, Placement> assignments, BitSet week) { 186 Set<Placement> placements = new HashSet<Placement>(); 187 188 for (Lecture lecture : variables()) { 189 // lecture of the value is already assigned 190 if(value != null && lecture.equals(value.variable()))continue; 191 192 // lecture might not have assignment if it is present in assignments 193 if (assignments != null && assignments.containsKey(lecture)) { 194 Placement placement = assignments.get(lecture); 195 if (placement != null && shareWeeksAndDay(placement.getTimeLocation(), week, dayCode)) 196 placements.add(placement); 197 } else if (assignment != null) { 198 Placement placement = assignment.getValue(lecture); 199 if (placement != null && (conflicts == null || !conflicts.contains(placement)) && shareWeeksAndDay(placement.getTimeLocation(), week, dayCode)) 200 placements.add(placement); 201 } 202 } 203 204 if (value == null || (conflicts != null && conflicts.contains(value))) { 205 return placements; 206 } 207 208 if (shareWeeksAndDay(value.getTimeLocation(), week, dayCode)) placements.add(value); 209 210 return placements; 211 } 212 213 /** 214 * Used to determine the daycode and week of a timelocation 215 * 216 * @param t timelocation 217 * @param week date pattern compared to timelocation 218 * @param dayCode days compared to timelocation 219 * @return true if TimeLocation matches the date pattern and days 220 */ 221 private boolean shareWeeksAndDay(TimeLocation t, BitSet week, int dayCode){ 222 boolean matchDay = (t.getDayCode() & dayCode) != 0; 223 boolean matchWeek = (week == null || t.shareWeeks(week)); 224 225 return matchDay && matchWeek; 226 } 227 228 /** 229 * Creates a list of blocks from a placements sorted by startSlot 230 * 231 * @param sorted list of placements sorted by startSlot 232 * @param maxBreakBetweenBTB maximum number of free slots between BTB placements 233 * @return groups of BTB placements as a list of blocks 234 */ 235 protected List<Block> mergeToBlocks(List<Placement> sorted, int maxBreakBetweenBTB){ 236 List<Block> blocks = new ArrayList<Block>(); 237 // add placements to blocks 238 for (int i = 0; i < sorted.size(); i++) { 239 Placement placement = sorted.get(i); 240 boolean added = false; 241 // add placement to a suitable block 242 for (int j = 0; j < blocks.size(); j++) { 243 if (blocks.get(j).addPlacement(placement)) { 244 added = true; 245 } 246 } 247 // create a new block if a lecture does not fit into any block 248 if (!added) { 249 Block block = new Block(maxBreakBetweenBTB); 250 block.addPlacement(placement); 251 blocks.add(block); 252 } 253 } 254 return blocks; 255 } 256 257 @Override 258 public boolean isHard() { 259 return iIsRequired; 260 } 261 262 @Override 263 public String getName() { 264 return iOwner + ": " + iConstraintType.getName(); 265 } 266 267 public FlexibleConstraintType getType(){ 268 return iConstraintType; 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 * @return prolog preference 283 */ 284 public String getPrologPreference() { 285 return Constants.preferenceLevel2preference(iPreference); 286 } 287 288 /** 289 * Return the current preference of the flexible constraint, considering conflicts and new assignments. 290 * Used to compute value for flexible constraint criterion. 291 * @param assignment current assignment 292 * @param conflicts conflicting assignment 293 * @param assignments proposed assignments 294 * @return the current preference of the flexible constraint 295 */ 296 public double getCurrentPreference(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments){ 297 if (isHard()) return 0; 298 double pref = getNrViolations(assignment, conflicts, assignments); 299 if(pref == 0){ 300 return - Math.abs(iPreference); 301 } 302 return Math.abs(iPreference) * pref; 303 } 304 305 /** 306 * A block is a list of placements sorted by startSlot, which are BTB. 307 * maxSlotsBetweenBackToBack determines the number of free slots between two BTB placements 308 * 309 */ 310 public class Block { 311 312 // start slot of the block 313 private int startSlotCurrentBlock = -1; 314 // end slot of the block 315 private int endSlotCurrentBlock = -1; 316 // max number of slots between classes to be considered Back-To-Back; 4 slots default 317 private int maxSlotsBetweenBackToBack = 4; 318 // the list of placements of this block 319 private List<Placement> placements = new ArrayList<Placement>(); 320 321 public Block(int maxSlotsBetweenBTB){ 322 this.maxSlotsBetweenBackToBack = maxSlotsBetweenBTB; 323 } 324 325 /** 326 * Adds placement to the block and updates block's attributes. 327 * 328 * @param placement placement to be added to the block 329 * @return true if the placement was successfully added to the block 330 */ 331 public boolean addPlacement(Placement placement){ 332 if (placement == null){ 333 return false; 334 } 335 336 TimeLocation t = placement.getTimeLocation(); 337 338 if (t == null){ 339 return false; 340 } 341 342 // if placements is empty, the block only contains currently added placement -> set start and end 343 if (placements.isEmpty()){ 344 placements.add(placement); 345 startSlotCurrentBlock = t.getStartSlot(); 346 endSlotCurrentBlock = t.getStartSlot() + t.getLength(); 347 return true; 348 } 349 350 // if startSlotCurrentBlock equals placement's start slot, add placement and adjust endSlotCurrentBlock 351 if (t.getStartSlot() == startSlotCurrentBlock){ 352 placements.add(placement); 353 int tEnd = t.getStartSlot() + t.getLength(); 354 if (tEnd > endSlotCurrentBlock){ 355 endSlotCurrentBlock = tEnd; 356 } 357 return true; 358 } 359 360 // if placement starts among endSlotCurrentBlock + modifier and startSlotCurrentBlock, add the placement 361 if (endSlotCurrentBlock + maxSlotsBetweenBackToBack >= t.getStartSlot() && t.getStartSlot() >= startSlotCurrentBlock ){ 362 placements.add(placement); 363 int tEnd = t.getStartSlot() + t.getLength(); 364 if (tEnd > endSlotCurrentBlock){ 365 endSlotCurrentBlock = tEnd; 366 } 367 return true; 368 } 369 370 return false; 371 } 372 373 public boolean haveSameStartTime() { 374 if (!placements.isEmpty()) { 375 int startSlot = placements.get(0).getTimeLocation().getStartSlot(); 376 for (Placement p : getPlacements()) { 377 if (p.getTimeLocation().getStartSlot() != startSlot) 378 return false; 379 } 380 } 381 return true; 382 } 383 384 public int getStartSlotCurrentBlock(){ 385 return startSlotCurrentBlock; 386 } 387 388 public int getEndSlotCurrentBlock(){ 389 return endSlotCurrentBlock; 390 } 391 392 public int getNbrPlacements(){ 393 return placements.size(); 394 } 395 396 public List<Placement> getPlacements(){ 397 return placements; 398 } 399 400 public int getLengthInSlots(){ 401 return endSlotCurrentBlock - startSlotCurrentBlock; 402 } 403 404 @Override 405 public String toString(){ 406 return "[" + startSlotCurrentBlock + ", " + endSlotCurrentBlock + "]" + " PlacementsNbr: "+ getNbrPlacements(); 407 } 408 } 409 410 /** 411 * Placement comparator: earlier placement first, shorter placement first if both start at the same time. 412 */ 413 protected static class PlacementTimeComparator implements Comparator<Placement> { 414 @Override 415 public int compare(Placement p1, Placement p2) { 416 TimeLocation t1 = p1.getTimeLocation(), t2 = p2.getTimeLocation(); 417 // compare by start time (earlier first) 418 if (t1.getStartSlot() < t2.getStartSlot()) 419 return -1; 420 if (t1.getStartSlot() > t2.getStartSlot()) 421 return 1; 422 // same start -> compare by length (shorter first) 423 if (t1.getLength() < t2.getLength()) 424 return -1; 425 if (t1.getLength() > t2.getLength()) 426 return 1; 427 // fallback 428 return 0; 429 } 430 } 431 432 @Override 433 public String toString() { 434 return getName(); 435 } 436 437 @Override 438 public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 439 return new FlexibleConstraintContext(assignment); 440 } 441 442 public class FlexibleConstraintContext implements AssignmentConstraintContext<Lecture, Placement> { 443 protected double iLastPreference = 0; 444 445 FlexibleConstraintContext() {} 446 447 FlexibleConstraintContext(Assignment<Lecture, Placement> assignment) { 448 updateCriterion(assignment); 449 } 450 451 @Override 452 public void assigned(Assignment<Lecture, Placement> assignment, Placement value) { 453 updateCriterion(assignment); 454 } 455 456 @Override 457 public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) { 458 updateCriterion(assignment); 459 } 460 461 /** 462 * Update value of FlexibleConstraintCriterion and number of violated FlexibleConstraints 463 */ 464 protected void updateCriterion(Assignment<Lecture, Placement> assignment) { 465 if (!isHard()) { 466 Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class); 467 if (criterion != null) { 468 criterion.inc(assignment, -iLastPreference); 469 iLastPreference = getCurrentPreference(assignment, null, null); 470 criterion.inc(assignment, iLastPreference); 471 } 472 } 473 } 474 475 public double getPreference() { 476 return iLastPreference; 477 } 478 } 479}