001package org.cpsolver.instructor.model;
002
003import java.text.DecimalFormat;
004import java.util.ArrayList;
005import java.util.BitSet;
006import java.util.Collection;
007import java.util.Date;
008import java.util.HashMap;
009import java.util.HashSet;
010import java.util.Iterator;
011import java.util.List;
012import java.util.Map;
013import java.util.Set;
014import java.util.TreeSet;
015
016import org.apache.log4j.Logger;
017import org.cpsolver.coursett.Constants;
018import org.cpsolver.coursett.model.TimeLocation;
019import org.cpsolver.ifs.assignment.Assignment;
020import org.cpsolver.ifs.criteria.Criterion;
021import org.cpsolver.ifs.model.Constraint;
022import org.cpsolver.ifs.model.Model;
023import org.cpsolver.ifs.util.DataProperties;
024import org.cpsolver.ifs.util.ToolBox;
025import org.cpsolver.instructor.constraints.InstructorConstraint;
026import org.cpsolver.instructor.constraints.SameInstructorConstraint;
027import org.cpsolver.instructor.constraints.SameLinkConstraint;
028import org.cpsolver.instructor.criteria.UnusedInstructorLoad;
029import org.cpsolver.instructor.criteria.AttributePreferences;
030import org.cpsolver.instructor.criteria.BackToBack;
031import org.cpsolver.instructor.criteria.CoursePreferences;
032import org.cpsolver.instructor.criteria.InstructorPreferences;
033import org.cpsolver.instructor.criteria.SameInstructor;
034import org.cpsolver.instructor.criteria.DifferentLecture;
035import org.cpsolver.instructor.criteria.OriginalInstructor;
036import org.cpsolver.instructor.criteria.SameCommon;
037import org.cpsolver.instructor.criteria.SameCourse;
038import org.cpsolver.instructor.criteria.SameDays;
039import org.cpsolver.instructor.criteria.SameLink;
040import org.cpsolver.instructor.criteria.SameRoom;
041import org.cpsolver.instructor.criteria.TeachingPreferences;
042import org.cpsolver.instructor.criteria.TimeOverlaps;
043import org.cpsolver.instructor.criteria.TimePreferences;
044import org.dom4j.Document;
045import org.dom4j.DocumentHelper;
046import org.dom4j.Element;
047
048/**
049 * Instructor Scheduling Model. Variables are {@link org.cpsolver.instructor.model.TeachingRequest}, values are {@link org.cpsolver.instructor.model.TeachingAssignment}.
050 * Each teaching request has a course (see {@link org.cpsolver.instructor.model.Course}) and one or more sections (see {link {@link org.cpsolver.instructor.model.Section}}).
051 * Each assignment assigns one instructor (see {@link org.cpsolver.instructor.model.Instructor}) to a single teaching request.
052 * 
053 * @version IFS 1.3 (Instructor Sectioning)<br>
054 *          Copyright (C) 2016 Tomáš Müller<br>
055 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
056 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
057 * <br>
058 *          This library is free software; you can redistribute it and/or modify
059 *          it under the terms of the GNU Lesser General Public License as
060 *          published by the Free Software Foundation; either version 3 of the
061 *          License, or (at your option) any later version. <br>
062 * <br>
063 *          This library is distributed in the hope that it will be useful, but
064 *          WITHOUT ANY WARRANTY; without even the implied warranty of
065 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
066 *          Lesser General Public License for more details. <br>
067 * <br>
068 *          You should have received a copy of the GNU Lesser General Public
069 *          License along with this library; if not see
070 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
071 */
072public class InstructorSchedulingModel extends Model<TeachingRequest.Variable, TeachingAssignment> {
073    private static Logger sLog = Logger.getLogger(InstructorSchedulingModel.class);
074    private DataProperties iProperties;
075    private Set<Attribute.Type> iTypes = new HashSet<Attribute.Type>();
076    private List<Instructor> iInstructors = new ArrayList<Instructor>();
077    private List<TeachingRequest> iRequests = new ArrayList<TeachingRequest>();
078
079    /**
080     * Constructor
081     * @param properties data properties
082     */
083    public InstructorSchedulingModel(DataProperties properties) {
084        super();
085        iProperties = properties;
086        addCriterion(new AttributePreferences());
087        addCriterion(new InstructorPreferences());
088        addCriterion(new TeachingPreferences());
089        addCriterion(new TimePreferences());
090        addCriterion(new CoursePreferences());
091        addCriterion(new BackToBack());
092        addCriterion(new SameInstructor());
093        addCriterion(new TimeOverlaps());
094        addCriterion(new DifferentLecture());
095        addCriterion(new SameLink());
096        addCriterion(new OriginalInstructor());
097        addCriterion(new UnusedInstructorLoad());
098        addCriterion(new SameCourse());
099        addCriterion(new SameCommon());
100        addCriterion(new SameDays());
101        addCriterion(new SameRoom());
102        addGlobalConstraint(new InstructorConstraint());
103    }
104    
105    /**
106     * Return solver configuration
107     * @return data properties given in the constructor
108     */
109    public DataProperties getProperties() {
110        return iProperties;
111    }
112    
113    /**
114     * Add instructor
115     * @param instructor
116     */
117    public void addInstructor(Instructor instructor) {
118        instructor.setModel(this);
119        iInstructors.add(instructor);
120        for (Attribute attribute: instructor.getAttributes())
121            addAttributeType(attribute.getType());
122    }
123    
124    /**
125     * All instructors
126     * @return all instructors in the model
127     */
128    public List<Instructor> getInstructors() {
129        return iInstructors;
130    }
131
132    /**
133     * Add teaching request and the related variables
134     * @param request teaching request
135     */
136    public void addRequest(TeachingRequest request) {
137        iRequests.add(request);
138        for (TeachingRequest.Variable variable: request.getVariables())
139            addVariable(variable);
140    }
141    
142    /**
143     * All teaching requests
144     * @return all teaching requests in the model
145     */
146    public List<TeachingRequest> getRequests() {
147        return iRequests;
148    }
149
150    
151    /**
152     * Return registered attribute types
153     * @return attribute types in the problem
154     */
155    public Set<Attribute.Type> getAttributeTypes() { return iTypes; }
156    
157    /**
158     * Register an attribute type
159     * @param type attribute type
160     */
161    public void addAttributeType(Attribute.Type type) { iTypes.add(type); }
162
163    @Override
164    public Map<String, String> getInfo(Assignment<TeachingRequest.Variable, TeachingAssignment> assignment) {
165        Map<String, String> info = super.getInfo(assignment);
166
167        double totalLoad = 0.0;
168        double assignedLoad = 0.0;
169        for (TeachingRequest.Variable clazz : variables()) {
170            totalLoad += clazz.getRequest().getLoad();
171            if (assignment.getValue(clazz) != null)
172                assignedLoad += clazz.getRequest().getLoad();
173        }
174        info.put("Assigned Load", getPerc(assignedLoad, totalLoad, 0) + "% (" + sDoubleFormat.format(assignedLoad) + " / " + sDoubleFormat.format(totalLoad) + ")");
175
176        return info;
177    }
178
179    @Override
180    public double getTotalValue(Assignment<TeachingRequest.Variable, TeachingAssignment> assignment) {
181        double ret = 0;
182        for (Criterion<TeachingRequest.Variable, TeachingAssignment> criterion : getCriteria())
183            ret += criterion.getWeightedValue(assignment);
184        return ret;
185    }
186
187    @Override
188    public double getTotalValue(Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Collection<TeachingRequest.Variable> variables) {
189        double ret = 0;
190        for (Criterion<TeachingRequest.Variable, TeachingAssignment> criterion : getCriteria())
191            ret += criterion.getWeightedValue(assignment, variables);
192        return ret;
193    }
194    
195    /**
196     * Store the problem (together with its solution) in an XML format
197     * @param assignment current assignment
198     * @return XML document with the problem
199     */
200    public Document save(Assignment<TeachingRequest.Variable, TeachingAssignment> assignment) {
201        DecimalFormat sDF7 = new DecimalFormat("0000000");
202        boolean saveInitial = getProperties().getPropertyBoolean("Xml.SaveInitial", false);
203        boolean saveBest = getProperties().getPropertyBoolean("Xml.SaveBest", false);
204        boolean saveSolution = getProperties().getPropertyBoolean("Xml.SaveSolution", true);
205        Document document = DocumentHelper.createDocument();
206        if (assignment != null && assignment.nrAssignedVariables() > 0) {
207            StringBuffer comments = new StringBuffer("Solution Info:\n");
208            Map<String, String> solutionInfo = (getProperties().getPropertyBoolean("Xml.ExtendedInfo", true) ? getExtendedInfo(assignment) : getInfo(assignment));
209            for (String key : new TreeSet<String>(solutionInfo.keySet())) {
210                String value = solutionInfo.get(key);
211                comments.append("    " + key + ": " + value + "\n");
212            }
213            document.addComment(comments.toString());
214        }
215        Element root = document.addElement("instructor-schedule");
216        root.addAttribute("version", "1.0");
217        root.addAttribute("created", String.valueOf(new Date()));
218        Element typesEl = root.addElement("attributes");
219        for (Attribute.Type type: getAttributeTypes()) {
220            Element typeEl = typesEl.addElement("type");
221            if (type.getTypeId() != null)
222                typeEl.addAttribute("id", String.valueOf(type.getTypeId()));
223            typeEl.addAttribute("name", type.getTypeName());
224            typeEl.addAttribute("conjunctive", type.isConjunctive() ? "true" : "false");
225            typeEl.addAttribute("required", type.isRequired() ? "true": "false");
226            Set<Attribute> attributes = new HashSet<Attribute>();
227            for (TeachingRequest request: getRequests()) {
228                for (Preference<Attribute> pref: request.getAttributePreferences()) {
229                    Attribute attribute = pref.getTarget();
230                    if (type.equals(attribute.getType()) && attributes.add(attribute)) {
231                        Element attributeEl = typeEl.addElement("attribute");
232                        if (attribute.getAttributeId() != null)
233                            attributeEl.addAttribute("id", String.valueOf(attribute.getAttributeId()));
234                        attributeEl.addAttribute("name", attribute.getAttributeName());
235                        if (attribute.getParentAttribute() != null && attribute.getParentAttribute().getAttributeId() != null)
236                            attributeEl.addAttribute("parent", String.valueOf(attribute.getParentAttribute().getAttributeId()));
237                    }
238                }
239                for (Instructor instructor: getInstructors()) {
240                    for (Attribute attribute: instructor.getAttributes()) {
241                        if (type.equals(attribute.getType()) && attributes.add(attribute)) {
242                            Element attributeEl = typeEl.addElement("attribute");
243                            if (attribute.getAttributeId() != null)
244                                attributeEl.addAttribute("id", String.valueOf(attribute.getAttributeId()));
245                            attributeEl.addAttribute("name", attribute.getAttributeName());
246                            if (attribute.getParentAttribute() != null && attribute.getParentAttribute().getAttributeId() != null)
247                                attributeEl.addAttribute("parent", String.valueOf(attribute.getParentAttribute().getAttributeId()));
248                        }
249                    }
250                }
251            }
252        }
253        Element requestsEl = root.addElement("teaching-requests");
254        for (TeachingRequest request: getRequests()) {
255            Element requestEl = requestsEl.addElement("request");
256            requestEl.addAttribute("id", String.valueOf(request.getRequestId()));
257            if (request.getNrInstructors() != 1)
258                requestEl.addAttribute("nrInstructors", String.valueOf(request.getNrInstructors()));
259            Course course = request.getCourse();
260            Element courseEl = requestEl.addElement("course");
261            if (course.getCourseId() != null)
262                courseEl.addAttribute("id", String.valueOf(course.getCourseId()));
263            if (course.getCourseName() != null)
264                courseEl.addAttribute("name", String.valueOf(course.getCourseName()));
265            for (Section section: request.getSections()) {
266                Element sectionEl = requestEl.addElement("section");
267                sectionEl.addAttribute("id", String.valueOf(section.getSectionId()));
268                if (section.getExternalId() != null && !section.getExternalId().isEmpty()) sectionEl.addAttribute("externalId", section.getExternalId());
269                if (section.getSectionType() != null && !section.getSectionType().isEmpty()) sectionEl.addAttribute("type", section.getSectionType());
270                if (section.getSectionName() != null && !section.getSectionName().isEmpty()) sectionEl.addAttribute("name", section.getSectionName());
271                if (section.hasTime()) {
272                    TimeLocation tl = section.getTime();
273                    Element timeEl = sectionEl.addElement("time");
274                    timeEl.addAttribute("days", sDF7.format(Long.parseLong(Integer.toBinaryString(tl.getDayCode()))));
275                    timeEl.addAttribute("start", String.valueOf(tl.getStartSlot()));
276                    timeEl.addAttribute("length", String.valueOf(tl.getLength()));
277                    if (tl.getBreakTime() != 0)
278                        timeEl.addAttribute("breakTime", String.valueOf(tl.getBreakTime()));
279                    if (tl.getTimePatternId() != null)
280                        timeEl.addAttribute("pattern", tl.getTimePatternId().toString());
281                    if (tl.getDatePatternId() != null)
282                        timeEl.addAttribute("datePattern", tl.getDatePatternId().toString());
283                    if (tl.getDatePatternName() != null && !tl.getDatePatternName().isEmpty())
284                        timeEl.addAttribute("datePatternName", tl.getDatePatternName());
285                    if (tl.getWeekCode() != null)
286                        timeEl.addAttribute("dates", bitset2string(tl.getWeekCode()));
287                    timeEl.setText(tl.getLongName(false));
288                }
289                if (section.hasRoom()) sectionEl.addAttribute("room", section.getRoom());
290                if (section.isAllowOverlap()) sectionEl.addAttribute("canOverlap", "true");
291                if (section.isCommon()) sectionEl.addAttribute("common", "true");
292            }
293            requestEl.addAttribute("load", sDoubleFormat.format(request.getLoad()));
294            requestEl.addAttribute("sameCourse", Constants.preferenceLevel2preference(request.getSameCoursePreference()));
295            requestEl.addAttribute("sameCommon", Constants.preferenceLevel2preference(request.getSameCommonPreference()));
296            for (Preference<Attribute> pref: request.getAttributePreferences()) {
297                Element attributeEl = requestEl.addElement("attribute");
298                if (pref.getTarget().getAttributeId() != null)
299                    attributeEl.addAttribute("id", String.valueOf(pref.getTarget().getAttributeId()));
300                attributeEl.addAttribute("name", pref.getTarget().getAttributeName());
301                attributeEl.addAttribute("type", pref.getTarget().getType().getTypeName());
302                attributeEl.addAttribute("preference", (pref.isRequired() ? "R" : pref.isProhibited() ? "P" : String.valueOf(pref.getPreference())));
303                if (pref.getTarget().getParentAttribute() != null && pref.getTarget().getParentAttribute().getAttributeId() != null)
304                    attributeEl.addAttribute("parent", String.valueOf(pref.getTarget().getParentAttribute().getAttributeId()));
305            }
306            for (Preference<Instructor> pref: request.getInstructorPreferences()) {
307                Element instructorEl = requestEl.addElement("instructor");
308                instructorEl.addAttribute("id", String.valueOf(pref.getTarget().getInstructorId()));
309                if (pref.getTarget().hasExternalId())
310                    instructorEl.addAttribute("externalId", pref.getTarget().getExternalId());
311                if (pref.getTarget().hasName())
312                    instructorEl.addAttribute("name", pref.getTarget().getName());
313                instructorEl.addAttribute("preference", (pref.isRequired() ? "R" : pref.isProhibited() ? "P" : String.valueOf(pref.getPreference())));
314            }
315            if (saveBest)
316                for (TeachingRequest.Variable variable: request.getVariables()) {
317                    if (variable.getBestAssignment() != null) {
318                        Instructor instructor = variable.getBestAssignment().getInstructor();
319                        Element instructorEl = requestEl.addElement("best-instructor");
320                        instructorEl.addAttribute("id", String.valueOf(instructor.getInstructorId()));
321                        if (request.getNrInstructors() != 1)
322                            instructorEl.addAttribute("index", String.valueOf(variable.getInstructorIndex()));
323                        if (instructor.hasExternalId())
324                            instructorEl.addAttribute("externalId", instructor.getExternalId());
325                        if (instructor.hasName())
326                            instructorEl.addAttribute("name", instructor.getName());
327                    }                    
328                }
329            if (saveInitial)
330                for (TeachingRequest.Variable variable: request.getVariables()) {
331                    if (variable.getInitialAssignment() != null) {
332                        Instructor instructor = variable.getInitialAssignment().getInstructor();
333                        Element instructorEl = requestEl.addElement("initial-instructor");
334                        instructorEl.addAttribute("id", String.valueOf(instructor.getInstructorId()));
335                        if (request.getNrInstructors() != 1)
336                            instructorEl.addAttribute("index", String.valueOf(variable.getInstructorIndex()));
337                        if (instructor.hasExternalId())
338                            instructorEl.addAttribute("externalId", instructor.getExternalId());
339                        if (instructor.hasName())
340                            instructorEl.addAttribute("name", instructor.getName());
341                    }
342                }
343            if (saveSolution)
344                for (TeachingRequest.Variable variable: request.getVariables()) {
345                    TeachingAssignment ta = assignment.getValue(variable);
346                    if (ta != null) {
347                        Instructor instructor = ta.getInstructor();
348                        Element instructorEl = requestEl.addElement("assigned-instructor");
349                        instructorEl.addAttribute("id", String.valueOf(instructor.getInstructorId()));
350                        if (request.getNrInstructors() != 1)
351                            instructorEl.addAttribute("index", String.valueOf(variable.getInstructorIndex()));
352                        if (instructor.hasExternalId())
353                            instructorEl.addAttribute("externalId", instructor.getExternalId());
354                        if (instructor.hasName())
355                            instructorEl.addAttribute("name", instructor.getName());
356                    }
357                }
358        }
359        Element instructorsEl = root.addElement("instructors");
360        for (Instructor instructor: getInstructors()) {
361            Element instructorEl = instructorsEl.addElement("instructor");
362            instructorEl.addAttribute("id", String.valueOf(instructor.getInstructorId()));
363            if (instructor.hasExternalId())
364                instructorEl.addAttribute("externalId", instructor.getExternalId());
365            if (instructor.hasName())
366                instructorEl.addAttribute("name", instructor.getName());
367            if (instructor.getPreference() != 0)
368                instructorEl.addAttribute("preference", String.valueOf(instructor.getPreference()));
369            if (instructor.getBackToBackPreference() != 0)
370                instructorEl.addAttribute("btb", String.valueOf(instructor.getBackToBackPreference()));
371            if (instructor.getSameDaysPreference() != 0)
372                instructorEl.addAttribute("same-days", String.valueOf(instructor.getSameDaysPreference()));
373            if (instructor.getSameRoomPreference() != 0)
374                instructorEl.addAttribute("same-room", String.valueOf(instructor.getSameRoomPreference()));
375            for (Attribute attribute: instructor.getAttributes()) {
376                Element attributeEl = instructorEl.addElement("attribute");
377                if (attribute.getAttributeId() != null)
378                    attributeEl.addAttribute("id", String.valueOf(attribute.getAttributeId()));
379                attributeEl.addAttribute("name", attribute.getAttributeName());
380                attributeEl.addAttribute("type", attribute.getType().getTypeName());
381                if (attribute.getParentAttribute() != null && attribute.getParentAttribute().getAttributeId() != null)
382                    attributeEl.addAttribute("parent", String.valueOf(attribute.getParentAttribute().getAttributeId()));
383            }
384            instructorEl.addAttribute("maxLoad", sDoubleFormat.format(instructor.getMaxLoad()));
385            for (Preference<TimeLocation> tp: instructor.getTimePreferences()) {
386                
387                Element timeEl = instructorEl.addElement("time");
388                TimeLocation tl = tp.getTarget();
389                timeEl.addAttribute("days", sDF7.format(Long.parseLong(Integer.toBinaryString(tl.getDayCode()))));
390                timeEl.addAttribute("start", String.valueOf(tl.getStartSlot()));
391                timeEl.addAttribute("length", String.valueOf(tl.getLength()));
392                if (tl.getBreakTime() != 0)
393                    timeEl.addAttribute("breakTime", String.valueOf(tl.getBreakTime()));
394                if (tl.getTimePatternId() != null)
395                    timeEl.addAttribute("pattern", tl.getTimePatternId().toString());
396                if (tl.getDatePatternId() != null)
397                    timeEl.addAttribute("datePattern", tl.getDatePatternId().toString());
398                if (tl.getDatePatternName() != null && !tl.getDatePatternName().isEmpty())
399                    timeEl.addAttribute("datePatternName", tl.getDatePatternName());
400                if (tl.getWeekCode() != null)
401                    timeEl.addAttribute("dates", bitset2string(tl.getWeekCode()));
402                timeEl.addAttribute("preference", tp.isProhibited() ? "P" : tp.isRequired() ? "R" : String.valueOf(tp.getPreference()));
403                if (tp.getTarget() instanceof EnrolledClass) {
404                    Element classEl = timeEl.addElement("section");
405                    Element courseEl = null;
406                    EnrolledClass ec = (EnrolledClass)tp.getTarget();
407                    if (ec.getCourseId() != null || ec.getCourse() != null) {
408                        courseEl = timeEl.addElement("course");
409                        if (ec.getCourseId() != null) courseEl.addAttribute("id", String.valueOf(ec.getCourseId()));
410                        if (ec.getCourse() != null) courseEl.addAttribute("name", ec.getCourse());
411                    }
412                    if (ec.getClassId() != null) classEl.addAttribute("id", String.valueOf(ec.getClassId()));
413                    if (ec.getType() != null) classEl.addAttribute("type", ec.getType());
414                    if (ec.getSection() != null) classEl.addAttribute("name", ec.getSection());
415                    if (ec.getExternalId() != null) classEl.addAttribute("externalId", ec.getExternalId());
416                    if (ec.getRoom() != null) classEl.addAttribute("room", ec.getRoom());
417                    classEl.addAttribute("role", ec.isInstructor() ? "instructor" : "student");
418                } else {
419                    timeEl.setText(tl.getLongName(false));
420                }
421            }
422            for (Preference<Course> cp: instructor.getCoursePreferences()) {
423                Element courseEl = instructorEl.addElement("course");
424                Course course = cp.getTarget();
425                if (course.getCourseId() != null)
426                    courseEl.addAttribute("id", String.valueOf(course.getCourseId()));
427                if (course.getCourseName() != null)
428                    courseEl.addAttribute("name", String.valueOf(course.getCourseName()));
429                courseEl.addAttribute("preference", cp.isProhibited() ? "P" : cp.isRequired() ? "R" : String.valueOf(cp.getPreference()));
430            }
431        }
432        Element constraintsEl = root.addElement("constraints");
433        for (Constraint<TeachingRequest.Variable, TeachingAssignment> c: constraints()) {
434            if (c instanceof SameInstructorConstraint) {
435                SameInstructorConstraint si = (SameInstructorConstraint) c;
436                Element sameInstEl = constraintsEl.addElement("same-instructor");
437                if (si.getConstraintId() != null)
438                    sameInstEl.addAttribute("id", String.valueOf(si.getConstraintId()));
439                if (si.getName() != null)
440                    sameInstEl.addAttribute("name", si.getName());
441                sameInstEl.addAttribute("preference", Constants.preferenceLevel2preference(si.getPreference()));
442                for (TeachingRequest.Variable request: c.variables()) {
443                    Element assignmentEl = sameInstEl.addElement("request");
444                    assignmentEl.addAttribute("id", String.valueOf(request.getRequest().getRequestId()));
445                    if (request.getRequest().getNrInstructors() != 1)
446                        assignmentEl.addAttribute("index", String.valueOf(request.getInstructorIndex()));
447                }
448            } else if (c instanceof SameLinkConstraint) {
449                SameLinkConstraint si = (SameLinkConstraint) c;
450                Element sameInstEl = constraintsEl.addElement("same-link");
451                if (si.getConstraintId() != null)
452                    sameInstEl.addAttribute("id", String.valueOf(si.getConstraintId()));
453                if (si.getName() != null)
454                    sameInstEl.addAttribute("name", si.getName());
455                sameInstEl.addAttribute("preference", Constants.preferenceLevel2preference(si.getPreference()));
456                for (TeachingRequest.Variable request: c.variables()) {
457                    Element assignmentEl = sameInstEl.addElement("request");
458                    assignmentEl.addAttribute("id", String.valueOf(request.getRequest().getRequestId()));
459                    if (request.getRequest().getNrInstructors() != 1)
460                        assignmentEl.addAttribute("index", String.valueOf(request.getInstructorIndex()));
461                }
462            }
463        }
464        return document;
465    }
466    
467    /**
468     * Load the problem (and its solution) from an XML format
469     * @param document XML document
470     * @param assignment current assignment
471     * @return true, if the problem was successfully loaded in
472     */
473    public boolean load(Document document, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment) {
474        boolean loadInitial = getProperties().getPropertyBoolean("Xml.LoadInitial", true);
475        boolean loadBest = getProperties().getPropertyBoolean("Xml.LoadBest", true);
476        boolean loadSolution = getProperties().getPropertyBoolean("Xml.LoadSolution", true);
477        String defaultBtb = getProperties().getProperty("Defaults.BackToBack", "0");
478        String defaultSameDays = getProperties().getProperty("Defaults.SameDays", "0");
479        String defaultSameRoom = getProperties().getProperty("Defaults.SameRoom", "0");
480        String defaultConjunctive = getProperties().getProperty("Defaults.Conjunctive", "false");
481        String defaultRequired = getProperties().getProperty("Defaults.Required", "false");
482        String defaultSameCourse = getProperties().getProperty("Defaults.SameCourse", "R");
483        String defaultSameCommon = getProperties().getProperty("Defaults.SameCommon", "R");
484        Element root = document.getRootElement();
485        if (!"instructor-schedule".equals(root.getName()))
486            return false;
487        Map<String, Attribute.Type> types = new HashMap<String, Attribute.Type>();
488        Map<Long, Attribute> attributes = new HashMap<Long, Attribute>();
489        Map<Long, Long> parents = new HashMap<Long, Long>();
490        if (root.element("attributes") != null) {
491            for (Iterator<?> i = root.element("attributes").elementIterator("type"); i.hasNext();) {
492                Element typeEl = (Element) i.next();
493                Attribute.Type type = new Attribute.Type(
494                        Long.parseLong(typeEl.attributeValue("id")),
495                        typeEl.attributeValue("name"),
496                        "true".equalsIgnoreCase(typeEl.attributeValue("conjunctive", defaultConjunctive)),
497                        "true".equalsIgnoreCase(typeEl.attributeValue("required", defaultRequired)));
498                addAttributeType(type);
499                if (type.getTypeName() != null)
500                    types.put(type.getTypeName(), type);
501                for (Iterator<?> j = typeEl.elementIterator("attribute"); j.hasNext();) {
502                    Element attributeEl = (Element) j.next();
503                    Attribute attribute = new Attribute(
504                            Long.parseLong(attributeEl.attributeValue("id")),
505                            attributeEl.attributeValue("name"),
506                            type);
507                    attributes.put(attribute.getAttributeId(), attribute);
508                    if (attributeEl.attributeValue("parent") != null)
509                        parents.put(attribute.getAttributeId(), Long.parseLong(attributeEl.attributeValue("parent")));
510                }
511            }
512        }
513        Map<Long, Course> courses = new HashMap<Long, Course>();
514        if (root.element("courses") != null) {
515            for (Iterator<?> i = root.element("courses").elementIterator("course"); i.hasNext();) {
516                Element courseEl = (Element) i.next();
517                Course course = new Course(
518                        Long.parseLong(courseEl.attributeValue("id")),
519                        courseEl.attributeValue("name"));
520                courses.put(course.getCourseId(), course);
521            }
522        }
523        Map<Long, Instructor> instructors = new HashMap<Long, Instructor>();
524        for (Iterator<?> i = root.element("instructors").elementIterator("instructor"); i.hasNext();) {
525            Element instructorEl = (Element) i.next();
526            Instructor instructor = new Instructor(
527                    Long.parseLong(instructorEl.attributeValue("id")),
528                    instructorEl.attributeValue("externalId"),
529                    instructorEl.attributeValue("name"),
530                    string2preference(instructorEl.attributeValue("preference")),
531                    Float.parseFloat(instructorEl.attributeValue("maxLoad", "0")));
532            instructor.setBackToBackPreference(Integer.valueOf(instructorEl.attributeValue("btb", defaultBtb)));
533            instructor.setSameDaysPreference(Integer.valueOf(instructorEl.attributeValue("same-days", defaultSameDays)));
534            instructor.setSameRoomPreference(Integer.valueOf(instructorEl.attributeValue("same-room", defaultSameRoom)));
535            for (Iterator<?> j = instructorEl.elementIterator("attribute"); j.hasNext();) {
536                Element f = (Element) j.next();
537                Long attributeId = Long.valueOf(f.attributeValue("id"));
538                Attribute attribute = attributes.get(attributeId);
539                if (attribute == null) {
540                    Attribute.Type type = types.get(f.attributeValue("type"));
541                    if (type == null) {
542                        type = new Attribute.Type(types.size(), f.attributeValue("type"),
543                                "true".equalsIgnoreCase(f.attributeValue("conjunctive", defaultConjunctive)),
544                                "true".equalsIgnoreCase(f.attributeValue("required", defaultRequired)));
545                        types.put(type.getTypeName(), type);
546                    }
547                    attribute = new Attribute(attributeId, f.attributeValue("name"), type);
548                    attributes.put(attributeId, attribute);
549                    if (f.attributeValue("parent") != null)
550                        parents.put(attribute.getAttributeId(), Long.parseLong(f.attributeValue("parent")));
551                }
552                instructor.addAttribute(attribute);
553            }
554            for (Iterator<?> j = instructorEl.elementIterator("time"); j.hasNext();) {
555                Element f = (Element) j.next();
556                Element classEl = f.element("section");
557                Element courseEl = f.element("course");
558                TimeLocation time = null;
559                if (classEl != null) {
560                    time = new EnrolledClass(
561                            courseEl == null || courseEl.attributeValue("id") == null ? null : Long.valueOf(courseEl.attributeValue("id")),
562                            classEl.attributeValue("id") == null ? null : Long.valueOf(classEl.attributeValue("id")),
563                            courseEl == null ? null : courseEl.attributeValue("name"),
564                            classEl.attributeValue("type"),
565                            classEl.attributeValue("name"),
566                            classEl.attributeValue("externalId"),
567                            Integer.parseInt(f.attributeValue("days"), 2),
568                            Integer.parseInt(f.attributeValue("start")),
569                            Integer.parseInt(f.attributeValue("length")),
570                            f.attributeValue("datePattern") == null ? null : Long.valueOf(f.attributeValue("datePattern")),
571                            f.attributeValue("datePatternName", ""),
572                            createBitSet(f.attributeValue("dates")),
573                            Integer.parseInt(f.attributeValue("breakTime", "0")),
574                            classEl.attributeValue("room"),
575                            "instructor".equalsIgnoreCase(classEl.attributeValue("role", "instructor")));
576                } else {
577                    time = new TimeLocation(
578                            Integer.parseInt(f.attributeValue("days"), 2),
579                            Integer.parseInt(f.attributeValue("start")),
580                            Integer.parseInt(f.attributeValue("length")), 0, 0,
581                            f.attributeValue("datePattern") == null ? null : Long.valueOf(f.attributeValue("datePattern")),
582                            f.attributeValue("datePatternName", ""),
583                            createBitSet(f.attributeValue("dates")),
584                            Integer.parseInt(f.attributeValue("breakTime", "0")));
585                }
586                if (f.attributeValue("pattern") != null)
587                    time.setTimePatternId(Long.valueOf(f.attributeValue("pattern")));
588                instructor.addTimePreference(new Preference<TimeLocation>(time, string2preference(f.attributeValue("preference"))));
589            }
590            for (Iterator<?> j = instructorEl.elementIterator("course"); j.hasNext();) {
591                Element f = (Element) j.next();
592                instructor.addCoursePreference(new Preference<Course>(new Course(Long.parseLong(f.attributeValue("id")), f.attributeValue("name")), string2preference(f.attributeValue("preference"))));
593            }
594            addInstructor(instructor);
595            instructors.put(instructor.getInstructorId(), instructor);
596        }
597        Map<Long, TeachingRequest> requests = new HashMap<Long, TeachingRequest>();
598        Map<TeachingRequest, Map<Integer, Instructor>> current = new HashMap<TeachingRequest, Map<Integer, Instructor>>();
599        Map<TeachingRequest, Map<Integer, Instructor>> best = new HashMap<TeachingRequest, Map<Integer, Instructor>>();
600        Map<TeachingRequest, Map<Integer, Instructor>> initial = new HashMap<TeachingRequest, Map<Integer, Instructor>>();
601        for (Iterator<?> i = root.element("teaching-requests").elementIterator("request"); i.hasNext();) {
602            Element requestEl = (Element) i.next();
603            Element courseEl = requestEl.element("course");
604            Course course = null;
605            if (courseEl != null) {
606                Long courseId = Long.valueOf(courseEl.attributeValue("id"));
607                course = courses.get(courseId);
608                if (course == null) {
609                    course = new Course(courseId, courseEl.attributeValue("name"));
610                }
611            } else {
612                course = courses.get(Long.valueOf(requestEl.attributeValue("course")));
613            }
614            List<Section> sections = new ArrayList<Section>();
615            for (Iterator<?> j = requestEl.elementIterator("section"); j.hasNext();) {
616                Element f = (Element) j.next();
617                TimeLocation time = null;
618                Element timeEl = f.element("time");
619                if (timeEl != null) {
620                    time = new TimeLocation(
621                            Integer.parseInt(timeEl.attributeValue("days"), 2),
622                            Integer.parseInt(timeEl.attributeValue("start")),
623                            Integer.parseInt(timeEl.attributeValue("length")), 0, 0,
624                            timeEl.attributeValue("datePattern") == null ? null : Long.valueOf(timeEl.attributeValue("datePattern")),
625                            timeEl.attributeValue("datePatternName", ""),
626                            createBitSet(timeEl.attributeValue("dates")),
627                            Integer.parseInt(timeEl.attributeValue("breakTime", "0")));
628                    if (timeEl.attributeValue("pattern") != null)
629                        time.setTimePatternId(Long.valueOf(timeEl.attributeValue("pattern")));
630                }
631                Section section = new Section(
632                        Long.valueOf(f.attributeValue("id")),
633                        f.attributeValue("externalId"),
634                        f.attributeValue("type"),
635                        f.attributeValue("name"),
636                        time,
637                        f.attributeValue("room"),
638                        "true".equalsIgnoreCase(f.attributeValue("canOverlap", "false")),
639                        "true".equalsIgnoreCase(f.attributeValue("common", "false")));
640                sections.add(section);
641            }
642            TeachingRequest request = new TeachingRequest(
643                    Long.parseLong(requestEl.attributeValue("id")),
644                    Integer.parseInt(requestEl.attributeValue("nrInstructors", "1")),
645                    course,
646                    Float.valueOf(requestEl.attributeValue("load", "0")),
647                    sections,
648                    Constants.preference2preferenceLevel(requestEl.attributeValue("sameCourse", defaultSameCourse)),
649                    Constants.preference2preferenceLevel(requestEl.attributeValue("sameCommon", defaultSameCommon)));
650            requests.put(request.getRequestId(), request);
651            for (Iterator<?> j = requestEl.elementIterator("attribute"); j.hasNext();) {
652                Element f = (Element) j.next();
653                Long attributeId = Long.valueOf(f.attributeValue("id"));
654                Attribute attribute = attributes.get(attributeId);
655                if (attribute == null) {
656                    Attribute.Type type = types.get(f.attributeValue("type"));
657                    if (type == null) {
658                        type = new Attribute.Type(types.size(), f.attributeValue("type"),
659                                "true".equalsIgnoreCase(f.attributeValue("conjunctive", defaultConjunctive)),
660                                "true".equalsIgnoreCase(f.attributeValue("required", defaultRequired)));
661                        types.put(type.getTypeName(), type);
662                    }
663                    attribute = new Attribute(attributeId, f.attributeValue("name"), type);
664                    attributes.put(attributeId, attribute);
665                    if (f.attributeValue("parent") != null)
666                        parents.put(attribute.getAttributeId(), Long.parseLong(f.attributeValue("parent")));
667                }
668                request.addAttributePreference(new Preference<Attribute>(attribute, string2preference(f.attributeValue("preference"))));
669            }
670            for (Iterator<?> j = requestEl.elementIterator("instructor"); j.hasNext();) {
671                Element f = (Element) j.next();
672                Long instructorId = Long.valueOf(f.attributeValue("id"));
673                Instructor instructor = instructors.get(instructorId);
674                if (instructor != null)
675                    request.addInstructorPreference(new Preference<Instructor>(instructor, string2preference(f.attributeValue("preference"))));
676            }
677            if (loadBest) {
678                for (Iterator<?> j = requestEl.elementIterator("best-instructor"); j.hasNext();) {
679                    Element f = (Element) j.next();
680                    Map<Integer, Instructor> idx2inst = best.get(request);
681                    if (idx2inst == null) {
682                        idx2inst = new HashMap<Integer, Instructor>();
683                        best.put(request, idx2inst);
684                    }
685                    int index = 1 + Integer.parseInt(f.attributeValue("index", String.valueOf(idx2inst.size())));
686                    Instructor instructor = instructors.get(Long.valueOf(f.attributeValue("id")));
687                    if (instructor != null)
688                        idx2inst.put(index, instructor);
689                }
690            }
691            if (loadInitial) {
692                for (Iterator<?> j = requestEl.elementIterator("initial-instructor"); j.hasNext();) {
693                    Element f = (Element) j.next();
694                    Map<Integer, Instructor> idx2inst = initial.get(request);
695                    if (idx2inst == null) {
696                        idx2inst = new HashMap<Integer, Instructor>();
697                        initial.put(request, idx2inst);
698                    }
699                    int index = 1 + Integer.parseInt(f.attributeValue("index", String.valueOf(idx2inst.size())));
700                    Instructor instructor = instructors.get(Long.valueOf(f.attributeValue("id")));
701                    if (instructor != null)
702                        idx2inst.put(index, instructor);
703                }
704            }
705            if (loadSolution) {
706                for (Iterator<?> j = requestEl.elementIterator("assigned-instructor"); j.hasNext();) {
707                    Element f = (Element) j.next();
708                    Map<Integer, Instructor> idx2inst = current.get(request);
709                    if (idx2inst == null) {
710                        idx2inst = new HashMap<Integer, Instructor>();
711                        current.put(request, idx2inst);
712                    }
713                    int index = Integer.parseInt(f.attributeValue("index", String.valueOf(idx2inst.size())));
714                    Instructor instructor = instructors.get(Long.valueOf(f.attributeValue("id")));
715                    if (instructor != null)
716                        idx2inst.put(index, instructor);
717                }
718            }
719            addRequest(request);
720        }
721        if (root.element("constraints") != null) {
722            for (Iterator<?> i = root.element("constraints").elementIterator(); i.hasNext();) {
723                Element constraintEl = (Element) i.next();
724                Constraint<TeachingRequest.Variable, TeachingAssignment> constraint = null;
725                if ("same-link".equals(constraintEl.getName())) {
726                    constraint = new SameLinkConstraint(
727                            (constraintEl.attributeValue("id") == null ? null : Long.valueOf(constraintEl.attributeValue("id"))),
728                            constraintEl.attributeValue("name"),
729                            constraintEl.attributeValue("preference"));
730                } else if ("same-instructor".equals(constraintEl.getName())) {
731                    constraint = new SameInstructorConstraint(
732                            (constraintEl.attributeValue("id") == null ? null : Long.valueOf(constraintEl.attributeValue("id"))),
733                            constraintEl.attributeValue("name"),
734                            constraintEl.attributeValue("preference"));
735                }
736                if (constraint != null) {
737                    for (Iterator<?> j = constraintEl.elementIterator("request"); j.hasNext();) {
738                        Element f = (Element) j.next();
739                        TeachingRequest request = requests.get(Long.valueOf(f.attributeValue("id")));
740                        if (request != null) {
741                            int index = Integer.valueOf(f.attributeValue("index", "0"));
742                            if (index >= 0 && index < request.getNrInstructors())
743                                constraint.addVariable(request.getVariables()[index]);
744                        }
745                    }
746                    addConstraint(constraint);
747                }
748            }            
749        }
750        for (Map.Entry<Long, Long> e: parents.entrySet())
751            attributes.get(e.getKey()).setParentAttribute(attributes.get(e.getValue()));
752        for (Map.Entry<TeachingRequest, Map<Integer, Instructor>> e1: best.entrySet())
753            for (Map.Entry<Integer, Instructor> e2: e1.getValue().entrySet())
754                if (e2.getKey() >= 0 && e2.getKey() < e1.getKey().getNrInstructors()) {
755                    TeachingRequest.Variable variable = e1.getKey().getVariables()[e2.getKey()];
756                    variable.setBestAssignment(new TeachingAssignment(variable, e2.getValue()), 0l);
757                }
758
759        for (Map.Entry<TeachingRequest, Map<Integer, Instructor>> e1: initial.entrySet())
760            for (Map.Entry<Integer, Instructor> e2: e1.getValue().entrySet())
761                if (e2.getKey() >= 0 && e2.getKey() < e1.getKey().getNrInstructors()) {
762                    TeachingRequest.Variable variable = e1.getKey().getVariables()[e2.getKey()];
763                    variable.setInitialAssignment(new TeachingAssignment(variable, e2.getValue()));
764                }
765        
766        if (!current.isEmpty()) {
767            for (Map.Entry<TeachingRequest, Map<Integer, Instructor>> e1: current.entrySet())
768                for (Map.Entry<Integer, Instructor> e2: e1.getValue().entrySet())
769                    if (e2.getKey() >= 0 && e2.getKey() < e1.getKey().getNrInstructors()) {
770                        TeachingRequest.Variable variable = e1.getKey().getVariables()[e2.getKey()];
771                        TeachingAssignment ta = new TeachingAssignment(variable, e2.getValue());
772                        Set<TeachingAssignment> conf = conflictValues(assignment, ta);
773                        if (conf.isEmpty()) {
774                            assignment.assign(0, ta);
775                        } else {
776                            sLog.error("Unable to assign " + ta.getName() + " to " + variable.getName());
777                            sLog.error("Conflicts:" + ToolBox.dict2string(conflictConstraints(assignment, ta), 2));
778                        }
779                    }
780        }
781        
782        return true;
783    }
784    
785    /** Convert bitset to a bit string */
786    protected static String bitset2string(BitSet b) {
787        StringBuffer sb = new StringBuffer();
788        for (int i = 0; i < b.length(); i++)
789            sb.append(b.get(i) ? "1" : "0");
790        return sb.toString();
791    }
792
793    /** Create BitSet from a bit string */
794    protected static BitSet createBitSet(String bitString) {
795        if (bitString == null) return null;
796        BitSet ret = new BitSet(bitString.length());
797        for (int i = 0; i < bitString.length(); i++)
798            if (bitString.charAt(i) == '1')
799                ret.set(i);
800        return ret;
801    }
802    
803    /** Convert preference string to a preference value */
804    protected static int string2preference(String pref) {
805        if (pref == null || pref.isEmpty()) return 0;
806        if (Constants.sPreferenceRequired.equals(pref))
807            return Constants.sPreferenceLevelRequired;
808        if (Constants.sPreferenceProhibited.equals(pref))
809            return Constants.sPreferenceLevelProhibited;
810        return Integer.valueOf(pref);
811    }
812}