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