001package net.sf.cpsolver.coursett.constraint; 002 003import java.util.Collection; 004import java.util.Comparator; 005import java.util.List; 006import java.util.Set; 007import java.util.TreeSet; 008 009import net.sf.cpsolver.coursett.model.Lecture; 010import net.sf.cpsolver.coursett.model.Placement; 011import net.sf.cpsolver.ifs.model.Constraint; 012 013/** 014 * Class limit constraint. 015 * 016 * @version CourseTT 1.2 (University Course Timetabling)<br> 017 * Copyright (C) 2006 - 2010 Tomáš Müller<br> 018 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 019 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 020 * <br> 021 * This library is free software; you can redistribute it and/or modify 022 * it under the terms of the GNU Lesser General Public License as 023 * published by the Free Software Foundation; either version 3 of the 024 * License, or (at your option) any later version. <br> 025 * <br> 026 * This library is distributed in the hope that it will be useful, but 027 * WITHOUT ANY WARRANTY; without even the implied warranty of 028 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 029 * Lesser General Public License for more details. <br> 030 * <br> 031 * You should have received a copy of the GNU Lesser General Public 032 * License along with this library; if not see 033 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 034 */ 035 036public class ClassLimitConstraint extends Constraint<Lecture, Placement> { 037 private int iClassLimit = 0; 038 private Lecture iParent = null; 039 private String iName = null; 040 boolean iEnabled = true; 041 042 private int iClassLimitDelta = 0; 043 044 public ClassLimitConstraint(int classLimit, String name) { 045 iClassLimit = classLimit; 046 iName = name; 047 } 048 049 public ClassLimitConstraint(Lecture parent, String name) { 050 iParent = parent; 051 iName = name; 052 } 053 054 public int getClassLimitDelta() { 055 return iClassLimitDelta; 056 } 057 058 public void setClassLimitDelta(int classLimitDelta) { 059 iClassLimitDelta = classLimitDelta; 060 } 061 062 public int classLimit() { 063 return (iParent == null ? iClassLimit + iClassLimitDelta : iParent.minClassLimit() + iClassLimitDelta); 064 } 065 066 public Lecture getParentLecture() { 067 return iParent; 068 } 069 070 public int currentClassLimit(Placement value, Set<Placement> conflicts) { 071 int limit = 0; 072 for (Lecture lecture : variables()) { 073 limit += lecture.classLimit(value, conflicts); 074 } 075 return limit; 076 } 077 078 @Override 079 public void computeConflicts(Placement value, Set<Placement> conflicts) { 080 if (!iEnabled) 081 return; 082 int currentLimit = currentClassLimit(value, conflicts); 083 int classLimit = classLimit(); 084 if (currentLimit < classLimit) { 085 // System.out.println(getName()+"> "+currentLimit+"<"+classLimit+" ("+value+")"); 086 TreeSet<Placement> adepts = new TreeSet<Placement>(new ClassLimitComparator()); 087 computeAdepts(adepts, variables(), value, conflicts); 088 addParentAdepts(adepts, iParent, value, conflicts); 089 // System.out.println(" -- found "+adepts.size()+" adepts"); 090 for (Placement adept : adepts) { 091 // System.out.println(" -- selected "+adept); 092 conflicts.add(adept); 093 currentLimit = currentClassLimit(value, conflicts); 094 // System.out.println(" -- new current limit "+currentLimit); 095 if (currentLimit >= classLimit) 096 break; 097 } 098 // System.out.println(" -- done (currentLimit="+currentLimit+", classLimit="+classLimit+")"); 099 } 100 101 if (currentLimit < classLimit) 102 conflicts.add(value); 103 104 if (iParent != null && iParent.getClassLimitConstraint() != null) 105 iParent.getClassLimitConstraint().computeConflicts(value, conflicts); 106 } 107 108 public void computeAdepts(Collection<Placement> adepts, List<Lecture> variables, Placement value, 109 Set<Placement> conflicts) { 110 for (Lecture lecture : variables) { 111 if (lecture.isCommitted()) continue; 112 Placement placement = lecture.getAssignment(); 113 if (placement != null && !placement.equals(value) && !conflicts.contains(placement)) { 114 adepts.add(placement); 115 } 116 if (lecture.hasAnyChildren()) { 117 for (Long subpartId: lecture.getChildrenSubpartIds()) { 118 computeAdepts(adepts, lecture.getChildren(subpartId), value, conflicts); 119 } 120 } 121 122 } 123 } 124 125 public void addParentAdepts(Collection<Placement> adepts, Lecture parent, Placement value, Set<Placement> conflicts) { 126 if (parent == null || parent.isCommitted() || parent.minClassLimit() == parent.maxClassLimit()) 127 return; 128 Placement placement = parent.getAssignment(); 129 if (placement != null && !placement.equals(value) && !conflicts.contains(placement)) { 130 adepts.add(placement); 131 } 132 addParentAdepts(adepts, parent.getParent(), value, conflicts); 133 } 134 135 @Override 136 public boolean inConflict(Placement value) { 137 if (!iEnabled) 138 return false; 139 int currentLimit = currentClassLimit(value, null); 140 int classLimit = classLimit(); 141 if (currentLimit < classLimit) 142 return true; 143 144 if (iParent != null && iParent.getClassLimitConstraint() != null) 145 return iParent.getClassLimitConstraint().inConflict(value); 146 147 return false; 148 } 149 150 @Override 151 public String getName() { 152 return iName; 153 } 154 155 private static class ClassLimitComparator implements Comparator<Placement> { 156 @Override 157 public int compare(Placement p1, Placement p2) { 158 Lecture l1 = p1.variable(); 159 Lecture l2 = p2.variable(); 160 int cl1 = Math.min(l1.maxClassLimit(), (int) Math.floor(p1.getRoomSize() / l1.roomToLimitRatio())); 161 int cl2 = Math.min(l2.maxClassLimit(), (int) Math.floor(p2.getRoomSize() / l2.roomToLimitRatio())); 162 int cmp = -Double.compare(l1.maxAchievableClassLimit() - cl1, l2.maxAchievableClassLimit() - cl2); 163 if (cmp != 0) 164 return cmp; 165 return l1.getClassId().compareTo(l2.getClassId()); 166 } 167 } 168 169 public void setEnabled(boolean enabled) { 170 iEnabled = enabled; 171 } 172 173 public boolean isEnabled() { 174 return iEnabled; 175 } 176 177 @Override 178 public String toString() { 179 return "Class-limit " + getName(); 180 } 181 182}