001package org.cpsolver.studentsct.online.selection;
002
003import java.util.ArrayList;
004import java.util.Hashtable;
005import java.util.List;
006import java.util.Map;
007import java.util.Set;
008
009import org.cpsolver.ifs.assignment.Assignment;
010import org.cpsolver.ifs.util.DataProperties;
011import org.cpsolver.studentsct.extension.DistanceConflict;
012import org.cpsolver.studentsct.extension.TimeOverlapsCounter;
013import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection;
014import org.cpsolver.studentsct.model.Config;
015import org.cpsolver.studentsct.model.CourseRequest;
016import org.cpsolver.studentsct.model.Enrollment;
017import org.cpsolver.studentsct.model.FreeTimeRequest;
018import org.cpsolver.studentsct.model.Request;
019import org.cpsolver.studentsct.model.Section;
020import org.cpsolver.studentsct.model.Student;
021import org.cpsolver.studentsct.model.Subpart;
022import org.cpsolver.studentsct.online.OnlineSectioningModel;
023
024/**
025 * Online student sectioning algorithm based on the {@link BranchBoundSelection} of the batch solver. The 
026 * selections adds the ability to provide required free times and sections and to prefer certain sections.
027 * If a course request has preferred sections, StudentWeights.PreferenceFactor parameter is used
028 * to penalize selection of a non-preferred section.
029 * 
030 * @author  Tomáš Müller
031 * @version StudentSct 1.3 (Student Sectioning)<br>
032 *          Copyright (C) 2014 Tomáš Müller<br>
033 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
034 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
035 * <br>
036 *          This library is free software; you can redistribute it and/or modify
037 *          it under the terms of the GNU Lesser General Public License as
038 *          published by the Free Software Foundation; either version 3 of the
039 *          License, or (at your option) any later version. <br>
040 * <br>
041 *          This library is distributed in the hope that it will be useful, but
042 *          WITHOUT ANY WARRANTY; without even the implied warranty of
043 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
044 *          Lesser General Public License for more details. <br>
045 * <br>
046 *          You should have received a copy of the GNU Lesser General Public
047 *          License along with this library; if not see <a
048 *          href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
049 * 
050 */
051public class SuggestionSelection extends BranchBoundSelection implements OnlineSectioningSelection {
052    protected Set<FreeTimeRequest> iRequiredFreeTimes;
053    protected Hashtable<CourseRequest, Config> iRequiredConfig = null;
054    protected Hashtable<CourseRequest, Hashtable<Subpart, Section>> iRequiredSection = null;
055    protected Hashtable<CourseRequest, Set<Section>> iPreferredSections = null;
056    protected Set<CourseRequest> iRequiredUnassinged = null;
057    /** add up to 50% for preferred sections */
058    private double iPreferenceFactor = 0.500;
059    private double iMaxOverExpected = -1.0;
060
061    public SuggestionSelection(DataProperties properties) {
062        super(properties);
063        iPreferenceFactor = properties.getPropertyDouble("StudentWeights.PreferenceFactor", iPreferenceFactor);
064    }
065
066    @Override
067    public void setPreferredSections(Hashtable<CourseRequest, Set<Section>> preferredSections) {
068        iPreferredSections = preferredSections;
069    }
070
071    @Override
072    public void setRequiredSections(Hashtable<CourseRequest, Set<Section>> requiredSections) {
073        iRequiredConfig = new Hashtable<CourseRequest, Config>();
074        iRequiredSection = new Hashtable<CourseRequest, Hashtable<Subpart, Section>>();
075        if (requiredSections != null) {
076            for (Map.Entry<CourseRequest, Set<Section>> entry : requiredSections.entrySet()) {
077                Hashtable<Subpart, Section> subSection = new Hashtable<Subpart, Section>();
078                iRequiredSection.put(entry.getKey(), subSection);
079                for (Section section : entry.getValue()) {
080                    if (subSection.isEmpty())
081                        iRequiredConfig.put(entry.getKey(), section.getSubpart().getConfig());
082                    subSection.put(section.getSubpart(), section);
083                }
084            }
085        }
086    }
087
088    @Override
089    public void setRequiredFreeTimes(Set<FreeTimeRequest> requiredFreeTimes) {
090        iRequiredFreeTimes = requiredFreeTimes;
091    }
092
093    @Override
094    public BranchBoundNeighbour select(Assignment<Request, Enrollment> assignment, Student student) {
095        return new Selection(student, assignment).select();
096    }
097
098    @Override
099    public void setModel(OnlineSectioningModel model) {
100        super.setModel(model);
101    }
102
103    /**
104     * Extension of {@link org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection.Selection} including checking of
105     * required free times and sections.
106     *
107     */
108    public class Selection extends BranchBoundSelection.Selection {
109        public Selection(Student student, Assignment<Request, Enrollment> assignment) {
110            super(student, assignment);
111        }
112
113        /**
114         * Check if the given enrollment is allowed
115         * @param idx enrollment index
116         * @param enrollment enrollment
117         * @return true if allowed (there is no conflict with required sections or free times)
118         */
119        public boolean isAllowed(int idx, Enrollment enrollment) {
120            if (enrollment.isCourseRequest()) {
121                CourseRequest request = (CourseRequest) enrollment.getRequest();
122                if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request)) return false;
123                Config reqConfig = iRequiredConfig.get(request);
124                if (reqConfig != null) {
125                    if (!reqConfig.equals(enrollment.getConfig()))
126                        return false;
127                    Hashtable<Subpart, Section> reqSections = iRequiredSection.get(request);
128                    for (Section section : enrollment.getSections()) {
129                        Section reqSection = reqSections.get(section.getSubpart());
130                        if (reqSection == null)
131                            continue;
132                        if (!section.equals(reqSection))
133                            return false;
134                    }
135                }
136            } else if (iRequiredFreeTimes.contains(enrollment.getRequest())) {
137                if (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty())
138                    return false;
139            }
140            return true;
141        }
142
143        @Override
144        public boolean inConflict(int idx, Enrollment enrollment) {
145            if (iMaxOverExpected >= 0.0 && iModel instanceof OnlineSectioningModel) {
146                double penalty = 0.0;
147                for (int i = 0; i < idx; i++) {
148                    if (iAssignment[i] != null && iAssignment[i].getAssignments() != null && iAssignment[i].isCourseRequest())
149                        for (Section section: iAssignment[i].getSections())
150                            penalty += ((OnlineSectioningModel)iModel).getOverExpected(iCurrentAssignment, iAssignment, i, section, iAssignment[i].getRequest());
151                }
152                if (enrollment.isCourseRequest())
153                    for (Section section: enrollment.getSections())
154                        penalty += ((OnlineSectioningModel)iModel).getOverExpected(iCurrentAssignment, iAssignment, idx, section, enrollment.getRequest());
155                if (penalty > iMaxOverExpected) return true;
156            }
157            return super.inConflict(idx, enrollment) || !isAllowed(idx, enrollment);
158        }
159
160        @Override
161        public Enrollment firstConflict(int idx, Enrollment enrollment) {
162            Enrollment conflict = super.firstConflict(idx, enrollment);
163            if (conflict != null)
164                return conflict;
165            return (isAllowed(idx, enrollment) ? null : enrollment);
166        }
167
168        @Override
169        protected boolean canLeaveUnassigned(Request request) {
170            if (request instanceof CourseRequest) {
171                if (iRequiredConfig.get(request) != null)
172                    return false;
173            } else if (iRequiredFreeTimes.contains(request))
174                return false;
175            return true;
176        }
177
178        @Override
179        protected List<Enrollment> values(final CourseRequest request) {
180            if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request))
181                return new ArrayList<Enrollment>();
182            return super.values(request);
183        }
184
185        @Override
186        @Deprecated
187        protected double getWeight(Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts,
188                Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
189            double weight = super.getWeight(enrollment, distanceConflicts, timeOverlappingConflicts);
190            if (enrollment.isCourseRequest() && iPreferredSections != null) {
191                Set<Section> preferred = iPreferredSections.get(enrollment.getRequest());
192                if (preferred != null && !preferred.isEmpty()) {
193                    double nrPreferred = 0;
194                    for (Section section : enrollment.getSections())
195                        if (preferred.contains(section))
196                            nrPreferred++;
197                    double preferredFraction = nrPreferred / preferred.size();
198                    weight *= 1.0 + iPreferenceFactor * preferredFraction;
199                }
200            }
201            return weight;
202        }
203
204        @Override
205        protected double getBound(Request r) {
206            double bound = super.getBound(r);
207            if (r instanceof CourseRequest) {
208                Set<Section> preferred = iPreferredSections.get(r);
209                if (preferred != null && !preferred.isEmpty())
210                    bound *= (1.0 + iPreferenceFactor);
211            }
212            return bound;
213        }
214
215    }
216
217    @Override
218    public void setRequiredUnassinged(Set<CourseRequest> requiredUnassignedRequests) {
219        iRequiredUnassinged = requiredUnassignedRequests;
220    }
221    
222    @Override
223    public void setMaxOverExpected(double maxOverExpected) {
224        iMaxOverExpected = maxOverExpected;
225    }
226}