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