001    package net.sf.cpsolver.coursett.constraint;
002    
003    import java.util.Collection;
004    import java.util.Comparator;
005    import java.util.List;
006    import java.util.Set;
007    import java.util.TreeSet;
008    
009    import net.sf.cpsolver.coursett.model.Lecture;
010    import net.sf.cpsolver.coursett.model.Placement;
011    import 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 Tomas Muller<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    
036    public 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    }