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