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 }