%
% ECLiPSe SAMPLE CODE
%
% Copyright (c)	1999  IC-Parc, Imperial College, London
% All Rights Reserved
%
% IDENTIFICATION:	roster.ecl
%
% AUTHOR:		Joachim Schimpf, IC-Parc
%			Imperial College, London
%

%:- nodbgcomp.
:- lib(fd_global).

:- local struct(post(r,m,e,j,k)).

go(Name, Cost) :-

	% Data -----------------
	data(Name, NWeeks, Data),
	dim(Data, [NLabels,NDays]),

	% Model -----------------
	dim(Roster, [NWeeks,NDays]),		% Make both a matrix and ...
	Rows is Roster[1..NWeeks,1..NDays],
	flatten(Rows, Vars),			% a flat list of the variables
	length(Vars, NVars),
	Vars :: 1..NLabels,			% They range over the labels

	% Debugging support
%	( current_predicate(make_display_matrix/2) ->
%	    make_display_matrix(Roster, roster) ; true ),

	% Constraints for the required number of labels on each day
	( for(Label,1,NLabels), param(Data,Roster,NDays,NWeeks) do
	    ( for(Day, 1, NDays), param(Data,Roster,Label,NWeeks) do
		Required is Data[Label,Day],
		Days is Roster[1..NWeeks,Day],
		occurrences(Label, Days, Required)
	    )
	),

	% Append the variables-list to a copy of itself
	% to make it easier to set up the cyclic constraints
	append(Vars, Vars, VarsWithOverlap),

	% Set up constraints on sub-sequences of days
	(
	    for(I,1,NVars),
	    fromto(VarsWithOverlap, RestVars, RestVars1, _),
	    fromto(AllViolations, [Viol1,Viol2|Violations], Violations, [])

	do
	    RestVars = [_|RestVars1],

	    % In every 7 days there must be at least 1 day off
	    first_n(7, RestVars, Consec7),
	    occurrences(r of post, Consec7, DaysOffIn7),
	    DaysOffIn7 :: 1..6,

	    % No more than 3 consecutive days off
	    first_n(4, RestVars, Consec4),
	    occurrences(r of post, Consec4, DaysOffIn4),
	    DaysOffIn4 :: 0..3,

	    % SOFT: No m after e
	    RestVars = [SomeDay,NextDay|_],
	    Viol1  isd  SomeDay #= e of post  #/\  NextDay #= m of post,

	    % SOFT: No isolated day off
	    RestVars = [Before,Off,After|_],
	    Viol2  isd  Off #= r of post
	    	#/\ Before #\= r of post
		#/\  After #\= r of post
	),
	Cost #= sum(AllViolations),

	% Search -----------------
	min_max((
	    ic_col_labeling(Data, Roster),
	    labeling_ff(Vars)
	    ),
	    Cost).

    try_day_off(X) :- X #= r of post.
    try_day_off(X) :- X #\= r of post.


% IC-Parc Search strategy

   ic_col_labeling(Data, Roster) :-
	dim(Roster, [NWeeks,NDays]),
	% find the column with the smallest number of Days off
	(
	    for(I,1,NDays),
	    fromto(1,OldMinCol,NewMinCol,MinCol),
	    param(Data)
	do
	    ( Data[r of post, I] < Data[r of post, OldMinCol] ->
	    	NewMinCol = I
	    ;
		NewMinCol = OldMinCol
	    )
	),
	DailyShift is NWeeks//NDays,
	(
	    for(I,MinCol,MinCol+NDays-1),
	    fromto(0, Offset1, Offset2, _),
	    param(DailyShift,Roster,NWeeks,NDays)
	do
	    Offset2 is Offset1+DailyShift,
	    (
	    	for(J,Offset1,Offset1+NWeeks-1), param(Roster,I,NWeeks,NDays)
	    do
	    	try_day_off(Roster[J mod NWeeks + 1, (I-1) mod NDays + 1])
	    )
	).


% Some general-purpose utilities

    % get the first N elements of a list
    first_n(N, List, FirstN) :-
    	length(FirstN, N),
	append(FirstN, _, List).


    % labeling using deleteff variable selection
    labeling_ff(AllVars) :-
    	( fromto(AllVars, Vars, Rest, []) do
	    deleteff(X, Vars, Rest),
	    indomain(X)
	).


% Data sets

data(i5, 5, post with [
	    r: week(3,2,1,0,1,1,5),	% Day-off
	    m: week(1,0,1,0,1,2,0),	% Morning
	    e: week(1,2,0,1,1,1,0),	% Evening
	    j: week(0,1,2,2,2,1,0),	% Mid-day
	    k: week(0,0,1,2,0,0,0)	% Joker
	]).