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