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 MaxBlock constraint checks for too big blocks of back-to-back classes of an instructor.<br> 021 * It has two parameters: a maximal length of a back-to-back block that is allowed and a minimal length of a break between two classes not to be considered in the same block.<br> 022 * Reference _MaxBlock:120:30_ translates to a maximal block of at most 2 hours (120 minutes) with classes not more than 30 minutes a part.<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 MaxBlockFlexibleConstraint extends FlexibleConstraint { 042 043 // max number of slots between to classes to be considered Back-To-Back 044 private int iMaxBreakBetweenBTB; 045 // max length of a block of classes taught Back-To-Back 046 private int iMaxBlockSlotsBTB; 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 MaxBlockFlexibleConstraint(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 = "_(MaxBlock):([0-9]+):([0-9]+)_"; 063 pattern = Pattern.compile(patternString); 064 matcher = pattern.matcher(reference); 065 if (matcher.find()) { 066 iMaxBlockSlotsBTB = Integer.parseInt(matcher.group(2))/Constants.SLOT_LENGTH_MIN; 067 iMaxBreakBetweenBTB = Integer.parseInt(matcher.group(3))/Constants.SLOT_LENGTH_MIN; 068 iConstraintType = FlexibleConstraint.FlexibleConstraintType.MAXBLOCK_BACKTOBACK; 069 } 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 // constraint is checked for every day in week 081 for (int dayCode : Constants.DAY_CODES) { 082 // constraint is checked for every week in semester (or for the whole semester) 083 for (BitSet week : weeks) { 084 boolean isProblem = false; 085 do { 086 isProblem = false; 087 // each blocks contains placements which are BTB 088 List<Block> blocks = getBlocks(dayCode, conflicts, value, null, week); 089 for (Block block : blocks) { 090 // if the block is not affected by the current placement, continue 091 if (!block.getPlacements().contains(value)){ 092 continue; 093 } 094 Set<Placement> adepts = new HashSet<Placement>(); 095 // if there is only 1 placement in block, the block cannot be shortened 096 // if placements of a block start at the same time, they intersect 097 // this solves problem when between 2 classes is required MEET_TOGETHER 098 if (block.getNbrPlacements() == 1 || block.haveSameStartTime()) 099 continue; 100 // if block is longer than maximum size, some of its placements are conflicts 101 if (block.getLengthInSlots() > iMaxBlockSlotsBTB) { 102 // classes from block are potential conflicts 103 adepts.addAll(block.getPlacements()); 104 // do not set currently assigned value as conflict 105 adepts.remove(value); 106 isProblem = true; 107 // pick random placement 108 Placement conflict = ToolBox.random(adepts); 109 if (conflict != null) { 110 conflicts.add(conflict); 111 } 112 } 113 } 114 } while (isProblem); 115 } 116 } 117 } 118 119 public List<Block> getBlocks(int dayCode, Set<Placement> conflicts, Placement value, HashMap<Lecture, Placement> assignments, BitSet week) { 120 List<Placement> toBeSorted = new ArrayList<Placement>(getRelevantPlacements(dayCode, conflicts, value, assignments, week)); 121 Collections.sort(toBeSorted, new PlacementTimeComparator()); 122 123 return mergeToBlocks(toBeSorted, iMaxBreakBetweenBTB); 124 } 125 126 @Override 127 public double getNrViolations(Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) { 128 List<BitSet> weeks = getWeeks(); 129 130 int violatedBlocks = 0; 131 for (int dayCode : Constants.DAY_CODES) { 132 for (BitSet week : weeks) { 133 List<Block> blocks = getBlocks(dayCode, null, null, assignments, week); 134 for (Block block : blocks) { 135 if (block.getNbrPlacements() == 1 || block.haveSameStartTime()) 136 continue; 137 // violated if there is a block containing more than one 138 // class longer than iMaxBlockSlotsBTB 139 if (block.getLengthInSlots() > iMaxBlockSlotsBTB) { 140 int blockLengthPenalty = block.getLengthInSlots() / iMaxBlockSlotsBTB; 141 violatedBlocks += blockLengthPenalty; 142 } 143 } 144 } 145 } 146 return violatedBlocks; 147 } 148 149}