package ttsolver.constraint;

import ifs.model.*;
import ttsolver.model.*;
import ifs.util.*;
import java.util.*;
import edu.purdue.smas.timetable.util.Constants;

/**
 * Departmental ballancing constraint.
 * <br><br>
 * The new implementation of the balancing times for departments works as follows: Initially, there is a histogram for 
 * each department computed. For each time slot, it says how many placements of all classes (of the department) include 
 * this time slot. Each such placement has the weight of 1 / number of placements of the class, so the total sum of all 
 * values in the histogram (i.e., for all time slots) is equal to the total sum of half-hours required by the given set 
 * of classes.
 * <br><br>
 * On the other hand, each class splits its number of half-hours (e.g., 2x50 has 4 half-hours, "4 points") into the 
 * time slots which it can occupy, according to the frequencies of the utilization of each time slots (i.e., number of 
 * placements containing the time slots divided by the number of all placements of the class).
 * <br><br>
 * For example, a histogram for department 1286:<code><br>
 * 1: [0.10,0.00,0.10,0.00,0.10] <- 7:30 [Mon, Tue, Wed, Thu, Fri]<br>
 * 2: [0.10,0.00,0.10,0.00,0.10] <- 8:00 [Mon, Tue, Wed, Thu, Fri]<br>
 * 3: [0.35,0.62,0.48,0.62,0.10] ... and so on<br>
 * 4: [0.35,0.62,0.48,0.62,0.10]<br>
 * 5: [1.35,1.12,1.48,0.12,1.10]<br>
 * 6: [1.35,1.12,1.48,0.12,1.10]<br>
 * 7: [0.35,0.62,0.48,1.63,0.10]<br>
 * 8: [0.35,0.62,0.48,1.63,0.10]<br>
 * 9: [0.35,0.12,0.48,0.12,0.10]<br>
 * 10:[0.35,0.12,0.48,0.12,0.10]<br>
 * 11:[0.35,0.12,0.48,0.12,0.10]<br>
 * 12:[0.35,0.12,0.48,0.12,0.10]<br>
 * 13:[0.35,0.12,0.48,1.12,0.10]<br>
 * 14:[0.35,0.12,0.48,1.12,0.10]<br>
 * 15:[0.35,0.12,0.48,0.12,0.10]<br>
 * 16:[0.35,0.12,0.48,0.12,0.10]<br>
 * 17:[0.35,0.12,0.48,0.12,0.10]<br>
 * 18:[0.35,0.12,0.48,0.12,0.10]<br>
 * 19:[0.10,0.00,0.10,0.00,0.10]<br>
 * 20:[0.10,0.00,0.10,0.00,0.10]<br>
 * 21:[0.00,0.00,0.00,0.00,0.00]<br>
 * </code><br>
 * You can easily see, that the time slots which are prohibited for all of the classes of the department have zero 
 * values, also some time slots are used much often than the others. Note that there are no preferences involved in 
 * this computation, only prohibited / not used times are less involved.
 * <br><br>
 * The idea is to setup the initial limits for each of the time slots according to the above values. The reason for doing 
 * so is to take the requirements (time patterns, required/prohibited times) of all classes of the department into 
 * account. For instance, take two classes A and B of type MWF 2x100 with two available locations starting from 7:30 
 * and 8:30. Note that the time slot Monday 8:30-9:00 will be always used by both of the classes and for instance the 
 * time slot Monday 7:30-8:00 (or Friday 9:30-10:00) can be used by none of them, only one of them or both of them. 
 * From the balancing point of the view, I believe it should be preferred to have one class starting from 7:30 and the 
 * other one from 8:30.
 * <br><br>
 * So, after the histogram is computed, its values are increased by the given percentage (same reason as before, to 
 * allow some space between the actual value and the limit, also not to make the limits for a department with 21 time 
 * slots less strict than a department with 20 time slots etc.). The initial limits are than computed as these values 
 * rounded upwards (1.90 results in 2).
 * <br><br>
 * Moreover, the value is increased only when the histogram value of a time slot is below the following value: 
 * spread factor * (number of used time slots / number of all time slots). Is assures a department of at least the 
 * given percentage more time slots than required, but does not provide an additional reward for above average 
 * use of time slots based on 'required' times.
 * <br><br>
 * For example, the department 1286 will have the following limits (histogram increased by 20% (i.e., each value is 20% 
 * higher) and rounded upwards):
 * <code><br>
 * 1: [1,0,1,0,1]<br>
 * 2: [1,0,1,0,1]<br>
 * 3: [1,1,1,1,1]<br>
 * 4: [1,1,1,1,1]<br>
 * 5: [2,2,2,1,2]<br>
 * 6: [2,2,2,1,2]<br>
 * 7: [1,1,1,2,1]<br>
 * 8: [1,1,1,2,1]<br>
 * 9: [1,1,1,1,1]<br>
 * 10:[1,1,1,1,1]<br>
 * 11:[1,1,1,1,1]<br>
 * 12:[1,1,1,1,1]<br>
 * 13:[1,1,1,2,1]<br>
 * 14:[1,1,1,2,1]<br>
 * 15:[1,1,1,1,1]<br>
 * 16:[1,1,1,1,1]<br>
 * 17:[1,1,1,1,1]<br>
 * 18:[1,1,1,1,1]<br>
 * 19:[1,0,1,0,1]<br>
 * 20:[1,0,1,0,1]<br>
 * 21:[0,0,0,0,0]<br>
 * </code><br>
 * The maximal penalty (i.e., the maximal number of half-hours which can be used above the pre-computed limits by a 
 * department) of a constraint is used. Initially, the maximal penalty is set to zero. It is increased by one after 
 * each time when the constraint causes the given number (e.g., 100) of un-assignments.
 * <br><br>
 * Also, the balancing penalty (the total number of half-hours over the initial limits) is computed and it can be 
 * minimized during the search (soft constraint).
 * <br><br>
 * Parameters:
 * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
 * <tr><td>DepartmentSpread.SpreadFactor</td><td>{@link Double}</td><td>Initial allowance of the slots for a particular time (factor)<br>Allowed slots = ROUND(SpreadFactor * (number of requested slots / number of slots per day))</td></tr>
 * <tr><td>DepartmentSpread.Unassignments2Weaken</td><td>{@link Integer}</td><td>Increase the initial allowance when it causes the given number of unassignments</td></tr>
 * </table>
 *
 * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomas Muller</a>
 * @version 1.0
 */

public class DepartmentSpreadConstraint extends Constraint {
    private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(DepartmentSpreadConstraint.class);
    private static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00",new java.text.DecimalFormatSymbols(Locale.US));
    private static java.text.DecimalFormat sIntFormat = new java.text.DecimalFormat("0",new java.text.DecimalFormatSymbols(Locale.US));
    private int iMaxCourses[][] = null;
    private int iCurrentPenalty = 0;
    private int iMaxAllowedPenalty = 0;
    
    private String iDepartment = null;
    private boolean iInitialized = false;
    private int[][] iNrCourses = null;
    private Vector [][] iCourses = null;
    private double iSpreadFactor = 1.20;
    private int iUnassignmentsToWeaken = 250;
    private long iUnassignment = 0;
    
    public DepartmentSpreadConstraint(DataProperties config, String department) {
        iDepartment = department;
        iSpreadFactor = config.getPropertyDouble("DepartmentSpread.SpreadFactor",iSpreadFactor);
        iUnassignmentsToWeaken = config.getPropertyInt("DepartmentSpread.Unassignments2Weaken", iUnassignmentsToWeaken);
        iNrCourses = new int[Constants.SLOTS_PER_DAY_NO_EVENINGS][Constants.DAY_CODES.length];
        iCourses = new Vector[Constants.SLOTS_PER_DAY_NO_EVENINGS][Constants.DAY_CODES.length];
        for (int i=0;i<iNrCourses.length;i++) {
            for (int j=0;j<Constants.DAY_CODES.length;j++) {
                iNrCourses[i][j] = 0;
                iCourses[i][j]=new Vector(10,5);
            }
        }
    }
    
    /** Initialize constraint (to be called after all variables are added to this constraint) */
    public void init() {
        if (iInitialized) return;
        double histogramPerDay[][] = new double[Constants.SLOTS_PER_DAY_NO_EVENINGS][Constants.DAY_CODES.length];
        iMaxCourses = new int[Constants.SLOTS_PER_DAY_NO_EVENINGS][Constants.DAY_CODES.length];
        for (int i=0;i<Constants.SLOTS_PER_DAY_NO_EVENINGS;i++)
            for (int j=0;j<Constants.DAY_CODES.length;j++)
                histogramPerDay[i][j]=0.0;
        int totalUsedSlots = 0;
        for (Enumeration e=variables().elements();e.hasMoreElements();) {
            Lecture lecture = (Lecture)e.nextElement();
            Placement firstPlacement = (Placement)lecture.values().firstElement();
            if (firstPlacement!=null) {
                totalUsedSlots += firstPlacement.getTimeLocation().getNrHalfHoursPerMeeting()*firstPlacement.getTimeLocation().getNrMeetings();
            }
            for (Enumeration e2=lecture.values().elements();e2.hasMoreElements();) {
                Placement p = (Placement)e2.nextElement();
                int firstSlot = p.getTimeLocation().getStartSlot();
                if (firstSlot>=Constants.SLOTS_PER_DAY_NO_EVENINGS) continue;
                int endSlot = firstSlot+p.getTimeLocation().getNrHalfHoursPerMeeting()-1;
                for (int i=firstSlot;i<=Math.min(endSlot,Constants.SLOTS_PER_DAY_NO_EVENINGS-1);i++) {
                    int dayCode = p.getTimeLocation().getDayCode();
                    for (int j=0;j<Constants.DAY_CODES.length;j++) {
                        if ((dayCode & Constants.DAY_CODES[j])!=0) {
                            histogramPerDay[i][j] += 1.0 / lecture.values().size();
                        }
                    }
                }
            }
        }
        //System.out.println("Histogram for department "+iDepartment+":");
        double threshold = iSpreadFactor*((double)totalUsedSlots/(5.0*Constants.SLOTS_PER_DAY_NO_EVENINGS));
        //System.out.println("Threshold["+iDepartment+"] = "+threshold);
        int totalAvailableSlots = 0;
        for (int i=0;i<Constants.SLOTS_PER_DAY_NO_EVENINGS;i++) {
            //System.out.println("  "+fmt(i+1)+": "+fmt(histogramPerDay[i]));
            for (int j=0;j<Constants.DAY_CODES.length;j++) {
                iMaxCourses[i][j]=(int)(0.999+(histogramPerDay[i][j]<=threshold?iSpreadFactor*histogramPerDay[i][j]:histogramPerDay[i][j]));
                totalAvailableSlots += iMaxCourses[i][j];
            }
        }
        iCurrentPenalty = 0;
        for (Enumeration e=variables().elements();e.hasMoreElements();) {
            Lecture lecture = (Lecture)e.nextElement();
            Placement placement = (Placement)lecture.getAssignment();
            if (placement==null) continue;
            int firstSlot = placement.getTimeLocation().getStartSlot();
            if (firstSlot>=Constants.SLOTS_PER_DAY_NO_EVENINGS) continue;
            int endSlot = firstSlot+placement.getTimeLocation().getNrHalfHoursPerMeeting()-1;
            for (int i=firstSlot;i<=Math.min(endSlot,Constants.SLOTS_PER_DAY_NO_EVENINGS-1);i++) {
                for (int j=0;j<Constants.DAY_CODES.length;j++) {
                    int dayCode = Constants.DAY_CODES[j];
                    if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
                        iNrCourses[i][j]++;
                        iCourses[i][j].addElement(placement);
                        iCurrentPenalty += Math.max(0,iNrCourses[i][j]-iMaxCourses[i][j]);
                    }
                }
            }
        }
        iMaxAllowedPenalty = iCurrentPenalty;
        //System.out.println("Initial penalty = "+fmt(iMaxAllowedPenalty));
        iInitialized = true;
    }
    
    private Lecture getAdept(Placement placement, int[][] nrCourses, Set conflicts) {
        //sLogger.debug("  -- looking for an adept");
        Lecture adept = null;
        int improvement = 0;
        for (Enumeration e=variables().elements();e.hasMoreElements();) {
            Lecture lect = (Lecture)e.nextElement();
            if (lect.getAssignment()==null || lect.equals(placement.variable())) continue;
            if (conflicts.contains(lect.getAssignment())) continue;
            int imp = getPenaltyIfUnassigned((Placement)lect.getAssignment(),nrCourses);
            if (imp==0) continue;
            //sLogger.debug("    -- "+lect+" can decrease penalty by "+imp);
            if (adept==null || imp>improvement) {
                adept = lect;
                improvement = imp;
            }
        }
        //sLogger.debug("  -- adept "+adept+" selected, penalty will be decreased by "+improvement);
        return adept;
    }
    
    private int getPenaltyIfUnassigned(Placement placement, int[][] nrCourses)  {
        int firstSlot = placement.getTimeLocation().getStartSlot();
        if (firstSlot>=Constants.SLOTS_PER_DAY_NO_EVENINGS) return 0;
        int endSlot = firstSlot+placement.getTimeLocation().getNrHalfHoursPerMeeting()-1;
        int penalty = 0;
        for (int i=firstSlot;i<=Math.min(endSlot,Constants.SLOTS_PER_DAY_NO_EVENINGS-1);i++) {
            for (int j=0;j<Constants.DAY_CODES.length;j++) {
                int dayCode = Constants.DAY_CODES[j];
                if ((dayCode & placement.getTimeLocation().getDayCode()) != 0 &&
                    nrCourses[i][j]>iMaxCourses[i][j]) penalty ++;
            }
        }
        return penalty;
    }

    private int tryUnassign(Placement placement, int[][] nrCourses) {
        //sLogger.debug("  -- trying to unassign "+placement);
        int firstSlot = placement.getTimeLocation().getStartSlot();
        if (firstSlot>=Constants.SLOTS_PER_DAY_NO_EVENINGS) return 0;
        int endSlot = firstSlot+placement.getTimeLocation().getNrHalfHoursPerMeeting()-1;
        int improvement = 0;
        for (int i=firstSlot;i<=Math.min(endSlot,Constants.SLOTS_PER_DAY_NO_EVENINGS-1);i++) {
            for (int j=0;j<Constants.DAY_CODES.length;j++) {
                int dayCode = Constants.DAY_CODES[j];
                if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
                    if (nrCourses[i][j]>iMaxCourses[i][j]) improvement++;
                    nrCourses[i][j]--;
                }
            }
        }
        //sLogger.debug("  -- penalty is decreased by "+improvement);
        return improvement;
    }

    private int tryAssign(Placement placement, int[][] nrCourses) {
        //sLogger.debug("  -- trying to assign "+placement);
        int firstSlot = placement.getTimeLocation().getStartSlot();
        if (firstSlot>=Constants.SLOTS_PER_DAY_NO_EVENINGS) return 0;
        int endSlot = firstSlot+placement.getTimeLocation().getNrHalfHoursPerMeeting()-1;
        int penalty = 0;
        for (int i=firstSlot;i<=Math.min(endSlot,Constants.SLOTS_PER_DAY_NO_EVENINGS-1);i++) {
            for (int j=0;j<Constants.DAY_CODES.length;j++) {
                int dayCode = Constants.DAY_CODES[j];
                if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
                    nrCourses[i][j]++;
                    if (nrCourses[i][j]>iMaxCourses[i][j]) penalty++;
                }
            }
        }
        //sLogger.debug("  -- penalty is incremented by "+penalty);
        return penalty;
    }

    public void computeConflicts(Value value, Set conflicts) {
        if (!iInitialized || iUnassignmentsToWeaken==0) return;
        Placement placement = (Placement)value;
        int penalty = iCurrentPenalty + getPenalty(placement);
        if (penalty<=iMaxAllowedPenalty) return;
        int firstSlot = placement.getTimeLocation().getStartSlot();
        if (firstSlot>=Constants.SLOTS_PER_DAY_NO_EVENINGS) return;
        int endSlot = firstSlot+placement.getTimeLocation().getNrHalfHoursPerMeeting()-1;
            //sLogger.debug("-- computing conflict for value "+value+" ... (penalty="+iCurrentPenalty+", penalty with the value="+penalty+", max="+iMaxAllowedPenalty+")");
            int[][] nrCourses = new int[iNrCourses.length][Constants.DAY_CODES.length];
            for (int i=0;i<iNrCourses.length;i++)
                for (int j=0;j<Constants.DAY_CODES.length;j++)
                    nrCourses[i][j] = iNrCourses[i][j];
            tryAssign(placement, nrCourses);
            //sLogger.debug("  -- nrCurses="+fmt(nrCourses));
            for (Enumeration e=variables().elements();e.hasMoreElements();) {
                Lecture lect = (Lecture)e.nextElement();
                if (conflicts.contains(lect)) {
                    penalty -= tryUnassign((Placement)lect.getAssignment(), nrCourses);
                }
                if (penalty<=iMaxAllowedPenalty) return;
            }
            while (penalty>iMaxAllowedPenalty) {
                Lecture lect = getAdept(placement, nrCourses, conflicts);
                if (lect==null) break;
                conflicts.add(lect.getAssignment());
                //sLogger.debug("  -- conflict "+lect.getAssignment()+" added");
                penalty -= tryUnassign((Placement)lect.getAssignment(), nrCourses);
            }
    }
    
    public boolean inConflict(Value value) {
        if (!iInitialized || iUnassignmentsToWeaken==0) return false;
        Placement placement = (Placement)value;
            return getPenalty(placement)+iCurrentPenalty>iMaxAllowedPenalty;
    }
    
    public boolean isConsistent(Value value1, Value value2) {
        if (!iInitialized || iUnassignmentsToWeaken==0) return true;
        Placement p1 = (Placement)value1;
        Placement p2 = (Placement)value2;
        if (!p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) return true;
        int firstSlot = Math.max(p1.getTimeLocation().getStartSlot(),p2.getTimeLocation().getStartSlot());
        if (firstSlot>=Constants.SLOTS_PER_DAY_NO_EVENINGS) return true;
        int endSlot = Math.min(p1.getTimeLocation().getStartSlot()+p1.getTimeLocation().getNrHalfHoursPerMeeting()-1,p2.getTimeLocation().getStartSlot()+p2.getTimeLocation().getNrHalfHoursPerMeeting()-1);
            int penalty = 0;
            for (int i=firstSlot;i<=Math.min(endSlot,Constants.SLOTS_PER_DAY_NO_EVENINGS-1);i++) {
                for (int j=0;j<Constants.DAY_CODES.length;j++) {
                    int dayCode = Constants.DAY_CODES[j];
                    if ((dayCode & p1.getTimeLocation().getDayCode()) != 0 && (dayCode & p2.getTimeLocation().getDayCode()) != 0) {
                        penalty += Math.max(0,2-iMaxCourses[i][j]);
                    }
                }
            }
            return (penalty<iMaxAllowedPenalty);
    }
    
    private void weaken() {
        if (!iInitialized) return;
        if (iUnassignmentsToWeaken==0) return;
            iMaxAllowedPenalty ++;
    }
    
    public void assigned(long iteration, Value value) {
        super.assigned(iteration, value);
        if (!iInitialized) return;
        Placement placement = (Placement)value;
        int firstSlot = placement.getTimeLocation().getStartSlot();
        if (firstSlot>=Constants.SLOTS_PER_DAY_NO_EVENINGS) return;
        int endSlot = firstSlot+placement.getTimeLocation().getNrHalfHoursPerMeeting()-1;
        for (int i=firstSlot;i<=Math.min(endSlot,Constants.SLOTS_PER_DAY_NO_EVENINGS-1);i++) {
            for (int j=0;j<Constants.DAY_CODES.length;j++) {
                int dayCode = Constants.DAY_CODES[j];
                if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
                    iNrCourses[i][j]++;
                    if (iNrCourses[i][j]>iMaxCourses[i][j]) iCurrentPenalty++;
                    iCourses[i][j].addElement(value);
                }
            }
        }
    }
    
    public void unassigned(long iteration, Value value) {
        super.unassigned(iteration, value);
        if (!iInitialized) return;
        Placement placement = (Placement)value;
        int firstSlot = placement.getTimeLocation().getStartSlot();
        if (firstSlot>=Constants.SLOTS_PER_DAY_NO_EVENINGS) return;
        int endSlot = firstSlot+placement.getTimeLocation().getNrHalfHoursPerMeeting()-1;
        for (int i=firstSlot;i<=Math.min(endSlot,Constants.SLOTS_PER_DAY_NO_EVENINGS-1);i++) {
            for (int j=0;j<Constants.DAY_CODES.length;j++) {
                int dayCode = Constants.DAY_CODES[j];
                if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
                    if (iNrCourses[i][j]>iMaxCourses[i][j]) iCurrentPenalty--;
                    iNrCourses[i][j]--;
                    iCourses[i][j].removeElement(value);
                }
            }
        }
    }
    
    /** Increment unassignment counter */
    public void incUnassignmentCounter(Value value) {
        iUnassignment ++;
        if (iUnassignment%iUnassignmentsToWeaken==0)
            weaken();
    }
    
    public String toString() {
        if (!iInitialized) return iDepartment+" (not initialized)";
        return iDepartment+" (p="+fmt(getPenalty())+", mx="+fmt(iMaxCourses)+", mp="+fmt(iMaxAllowedPenalty)+"): "+fmt(iNrCourses);
    }

    /** Department balancing penalty for this department */
    public int getPenalty() {
        if (!iInitialized) return 0;
        return iCurrentPenalty;
    }
    
    /** Department balancing penalty of the given placement */
    public int getPenalty(Placement placement) {
        if (!iInitialized) return 0;
        int firstSlot = placement.getTimeLocation().getStartSlot();
        if (firstSlot>=Constants.SLOTS_PER_DAY_NO_EVENINGS) return 0;
        int endSlot = firstSlot+placement.getTimeLocation().getNrHalfHoursPerMeeting()-1;
        int penalty = 0;
        for (int i=firstSlot;i<=Math.min(endSlot,Constants.SLOTS_PER_DAY_NO_EVENINGS-1);i++) {
            for (int j=0;j<Constants.DAY_CODES.length;j++) {
                int dayCode = Constants.DAY_CODES[j];
                if ((dayCode & placement.getTimeLocation().getDayCode()) != 0 &&
                    iNrCourses[i][j]>=iMaxCourses[i][j]) penalty ++;
            }
        }
        return penalty;
    }
        
    private String fmt(double value) {
        return sDoubleFormat.format(value);
    }
    
    private String fmt(double[] values) {
        if (values==null) return null;
        StringBuffer sb = new StringBuffer("[");
        for (int i=0;i<Math.min(5,values.length);i++)
            sb.append(i==0?"":",").append(sDoubleFormat.format(values[i]));
            sb.append("]");
            return sb.toString();
    }
    
    private String fmt(double[][] values) {
        if (values==null) return null;
        StringBuffer sb = new StringBuffer("[");
        for (int i=0;i<values.length;i++) {
            /*double total = 0;
            for (int j=0;j<values[i].length;j++)
                total += values[i][j];
            sb.append(i==0?"":",").append(fmt(total));*/
            sb.append(i==0?"":",").append(fmt(values[i]));
        }
        sb.append("]");
        return sb.toString();
    }
    
    private String fmt(int value) {
        return sIntFormat.format(value);
    }
    
    private String fmt(int[] values) {
        if (values==null) return null;
        StringBuffer sb = new StringBuffer("[");
        for (int i=0;i<Math.min(5,values.length);i++)
            sb.append(i==0?"":",").append(sIntFormat.format(values[i]));
            sb.append("]");
            return sb.toString();
    }
    
    private String fmt(int[][] values) {
        if (values==null) return null;
        StringBuffer sb = new StringBuffer("[");
        for (int i=0;i<values.length;i++) {
            /*int total = 0;
            for (int j=0;j<values[i].length;j++)
                total += values[i][j];
            sb.append(i==0?"":",").append(fmt(total));*/
            sb.append(i==0?"":",").append(fmt(values[i]));
        }
        sb.append("]");
        return sb.toString();
    }
}