    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.logging.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 = org.apache.logging.log4j.LogManager.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}