001package net.sf.cpsolver.coursett.constraint; 002 003import java.util.ArrayList; 004import java.util.BitSet; 005import java.util.Collections; 006import java.util.HashMap; 007import java.util.HashSet; 008import java.util.List; 009import java.util.Set; 010import java.util.regex.Matcher; 011import java.util.regex.Pattern; 012 013import net.sf.cpsolver.coursett.Constants; 014import net.sf.cpsolver.coursett.model.Lecture; 015import net.sf.cpsolver.coursett.model.Placement; 016import net.sf.cpsolver.ifs.util.ToolBox; 017 018/** 019 * 020 * The Break constraint checks for instructor lunch break or a break in general in between the given classes.<br> 021 * It has three parameters: a start and an end time of a window in which the break is required / preferred, and a minimal length of a break that is needed.<br> 022 * Reference _Break:132:162:30_ translates to a break of at least 30 minutes between 11 am (slot 132) and 1:30 pm (slot 162).<br> 023 * 024 * @version CourseTT 1.2 (University Course Timetabling)<br> 025 * Copyright (C) 2013 Matej Lukac<br> 026 * <br> 027 * This library is free software; you can redistribute it and/or modify 028 * it under the terms of the GNU Lesser General Public License as 029 * published by the Free Software Foundation; either version 3 of the 030 * License, or (at your option) any later version. <br> 031 * <br> 032 * This library is distributed in the hope that it will be useful, but 033 * WITHOUT ANY WARRANTY; without even the implied warranty of 034 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 035 * Lesser General Public License for more details. <br> 036 * <br> 037 * You should have received a copy of the GNU Lesser General Public 038 * License along with this library; if not see 039 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 040 */ 041public class BreakFlexibleConstraint extends FlexibleConstraint { 042 043 // LunchBreak constraint parameters 044 private int iBreakStart; 045 private int iBreakEnd; 046 private int iBreakLength; 047 048 /** 049 * 050 * @param owner identifier of distribution preference the constraint was created for 051 * @param preference time preference ("R" for required, "P" for prohibited, "-2", 052 * "-1", "1", "2" for soft preference) 053 * @param reference parameters of the constraint in String form 054 */ 055 public BreakFlexibleConstraint(Long id, String owner, String preference, String reference) { 056 super(id, owner, preference, reference); 057 058 Pattern pattern = null; 059 Matcher matcher = null; 060 061 // recognize Break constraint 062 String patternString = "_(Break):([0-9]+):([0-9]+):([0-9]+)_"; 063 pattern = Pattern.compile(patternString); 064 matcher = pattern.matcher(reference); 065 if (matcher.find()) { 066 iBreakStart = Integer.parseInt(matcher.group(2)); 067 iBreakEnd = Integer.parseInt(matcher.group(3)); 068 iBreakLength = Integer.parseInt(matcher.group(4))/Constants.SLOT_LENGTH_MIN; 069 iConstraintType = FlexibleConstraintType.BREAK; 070 } 071 } 072 073 @Override 074 public void computeConflicts(Placement value, Set<Placement> conflicts) { 075 if (!isHard()) 076 return; 077 078 List<BitSet> weeks = getWeeks(); 079 080 // checks only placements in the break time 081 if (value.getTimeLocation().getStartSlot() <= iBreakEnd 082 && value.getTimeLocation().getStartSlot() + value.getTimeLocation().getLength() > iBreakStart) { 083 084 for (int dayCode : Constants.DAY_CODES) { 085 // checks only days affected by the placement 086 if ((value.getTimeLocation().getDayCode() & dayCode) != 0) { 087 // constraint is checked for every week in semester (or for the whole semester) 088 for (BitSet week : weeks) { 089 boolean isProblem = false; 090 do { 091 Set<Placement> adepts = new HashSet<Placement>(); 092 // each blocks contains placements which are BTB 093 // placements are BTB if there is less time between them than the minimal break length 094 List<Block> blocks = getBreakBlocks(dayCode, conflicts, value, null, week); 095 // determine possible conflicts from blocks' placements 096 getAdeptsLunchBreak(blocks, adepts); 097 if (adepts.isEmpty()) 098 isProblem = false; 099 // currently assigned value shouldn't be added to conflicts if possible 100 if (adepts.size() >= 2) 101 adepts.remove(value); 102 // pick random placement 103 Placement conflict = ToolBox.random(adepts); 104 if (conflict != null) { 105 conflicts.add(conflict); 106 } 107 } while (isProblem); 108 } 109 } 110 } 111 } 112 } 113 114 /** 115 * Creates a list of consecutive blocks with back-to-back classes. 116 */ 117 public List<Block> getBreakBlocks(int dayCode, Set<Placement> conflicts, Placement value, HashMap<Lecture, Placement> assignments, BitSet week) { 118 119 List<Placement> toBeSorted = new ArrayList<Placement>(getRelevantPlacements(dayCode, conflicts, value, assignments, week)); 120 Collections.sort(toBeSorted, new PlacementTimeComparator()); 121 122 return mergeToBlocks(toBeSorted, iBreakLength); 123 } 124 125 126 127 /** 128 * Method adds Placements from blocks to adepts if there is a possibility, that the placement caused constraint violation 129 * 130 * @param blocks placements in 131 * @param adepts 132 */ 133 private void getAdeptsLunchBreak(List<Block> blocks, Set<Placement> adepts) { 134 List<Block> matchingBlocks = new ArrayList<Block>(); 135 for(Block block: blocks){ 136 // if block intersects with break interval, it will be used in conflict selection 137 if (block.getStartSlotCurrentBlock() <= iBreakEnd && block.getEndSlotCurrentBlock() >= iBreakStart) matchingBlocks.add(block); 138 } 139 int size = matchingBlocks.size(); 140 // if there is none block intersecting with break interval, the constraint is satisfied 141 // if there are at least 2 blocks intersecting with break interval, the constraint is satisfied, 142 // because there must be a space between them, otherwise they would be in one block 143 // if there is only one block intersecting with break interval, constraint might not be satisfied 144 if (size == 1) { 145 Block block = matchingBlocks.get(0); 146 // check whether the block leaves enough space for break 147 if (block.getStartSlotCurrentBlock() - iBreakStart >= iBreakLength || iBreakEnd - block.getEndSlotCurrentBlock() >= iBreakLength){ 148 return; 149 // if it doesn't 150 }else{ 151 // every placement intersecting with break interval might be potential conflict 152 for (Placement p: block.getPlacements()){ 153 if ( p.getTimeLocation().getStartSlot() <= iBreakEnd && p.getTimeLocation().getStartSlot()+ p.getTimeLocation().getLength() >= iBreakStart){ 154 adepts.add(p); 155 } 156 } 157 } 158 } 159 } 160 161 @Override 162 public double getNrViolations(Set<Placement> conflicts, HashMap<Lecture, Placement> assignments){ 163 List<BitSet> weeks = getWeeks(); 164 165 int violatedDays = 0; 166 for (int dayCode : Constants.DAY_CODES) { 167 weekIteration: for (BitSet week : weeks) { 168 Set<Placement> adepts = new HashSet<Placement>(); 169 List<Block> blocks = getBreakBlocks(dayCode, null, null, assignments, week); 170 getAdeptsLunchBreak(blocks, adepts); 171 if (!adepts.isEmpty()) 172 violatedDays++; 173 break weekIteration; 174 } 175 } 176 return violatedDays; 177 } 178 179}