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