%%%%
%%%% MANY THANKS to Zeynep Kiziltan <zeykiz@csd.uu.se> for fixing a number of
%%%% problems with my original code for SICStus Prolog Chapter 8
%%%%
%%%%                                          Peter Stuckey (September 1999)
%%%%
% compiler directive to load finite domain library and cumulative
:- use_module(library(clpfd)).
:- use_module(library('clpfd/cumul')). %% not required for SICStus 3.7

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                       8.1 Domains and Labelling                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% simple relation likes p252.
% SICStus does not support arbitrary domains mimicked with integers
likes(1, maria). 
likes(1, nicole). 
likes(1, erika). 
likes(2, maria). 
likes(3, nicole). 
likes(3, maria).
likes(3, erika). 
 
% goal for the marriage problem p252.
% SICStus does not support arbitrary domains mimicked with integers
gp252a(N,M,E) :-
    domain([N,M,E], 1,3), N #\= M, N #\= E, M #\= E, 
             likes(N, nicole), likes(M, maria), likes(E, erika).

% smugglers knapsack goal p252. 
gp252b(W,P,C) :-
     domain([W,P,C],0,9), 4*W + 3*P + 2*C #=< 9, 
        15*W + 10*P + 7*C #>= 30.

% smugglers knapsack goal with labelling p253. 
gp253a(W,P,C) :-
        domain([W,P,C],0,9), 4*W + 3*P + 2*C #=< 9, 
        15*W + 10*P + 7*C #>= 30, labeling([],[W,P,C]).

% minimization version of smugglers knapsack p253.
gp253b(W,P,C) :-
        L #= -15*W - 10*P - 7*C,
        minimize((domain([W,P,C],0,9), 4*W + 3*P + 2*C #=< 9, 
        15*W + 10*P + 7*C #>= 30, labeling([],[W,P,C])), L).

% send more money program p254. 
smm(S,E,N,D,M,O,R,Y)  :-  
     domain([S,E,N,D,M,O,R,Y],0,9),
     constrain([S,E,N,D,M,O,R,Y]),
     labeling([],[S,E,N,D,M,O,R,Y]).
 
constrain([S,E,N,D,M,O,R,Y])  :-  
     S #\= 0,M #\= 0, 
     alldifferent_neq([S,E,N,D,M,O,R,Y]), 
         1000*S +     100*E +     10*N +     D 
     +    1000*M +     100*O +     10*R +     E 
     #= 10000*M +     1000*O +     100*N +     10*E +     Y.

% alldifferent program Ex 6.3 p190.
alldifferent_neq([]). 
alldifferent_neq([Y|Ys]) :- not_member(Y, Ys), alldifferent_neq(Ys). 
 
not_member(_X, []). 
not_member(X, [Y|Ys]) :-        
        X #\= Y, %% beware not_member will only work correctly
                %% when both arguments are finite domain,
        not_member(X, Ys).

% goal for send more money p254.
gp254(S,E,N,D,M,O,R,Y) :- smm(S,E,N,D,M,O,R,Y).

% send more money generate and test version p256. 
smm_gt(S,E,N,D,M,O,R,Y)   :-   
     domain([S,E,N,D,M,O,R,Y],0,9),
     labeling([],[S,E,N,D,M,O,R,Y]),
     constrain([S,E,N,D,M,O,R,Y]).

% goal for send more money generate and test version p256.
gp256(S,E,N,D,M,O,R,Y) :- smm_gt(S,E,N,D,M,O,R,Y).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                       8.2 Complex Constraints                       %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% old fashion marriage problem with complex constraint p257.
gp257a(N,M,E) :-
     domain([N,M,E], 1,3), all_different([N,M,E]), 
     likes(N, nicole), likes(M, maria), likes(E, erika). 
 
% apart constraint progra p257.
apart(X, Y, N) :- X #>= Y + N. 
apart(X, Y, N) :- Y #>= X + N. 
 
% seesaw problem goal p257.
gp257b(L, F, S) :-
     domain([L,F,S],-5,5),  9 * L + 8 * F + 4 * S #= 0,
     apart(L,F,3), apart(L,S,3), apart(F,S,3),  
     labeling([],[L,F,S]).

% seesaw problem goal with cumulative constraint p258.
gp258(L, F, S) :-
     domain([L,F,S] ,-5,5),  9 * L + 8 * F + 4 * S #= 0,
     cumulative([L,F,S],[3,3,3],[1,1,1],1), 
     labeling([],[L,F,S]).
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                           8.3 Labelling                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% building the basic domain enquiry functions for SICStus
dom(V,D) :- fd_dom(V,D1), my_fdset_to_list(D1,D).
my_fdset_to_list(S,L) :- my_fdset_to_list(S,L,[]).
my_fdset_to_list({N},D,D0) :-  D = [N|D0].
my_fdset_to_list(A..B,D,D0) :- range(A,B,D,D0).
my_fdset_to_list(A\/B,D,D0) :- my_fdset_to_list(A,D,D1),my_fdset_to_list(B,D1,D0).
range(A,B,D,D0) :- 
        (A > B -> D = D0 ; D = [A|D1], A1 is A + 1, range(A1,B,D1,D0)).
mindomain(V,M) :- fd_min(V,M).
maxdomain(V,M) :- fd_max(V,M).

% labelling program defn from p259.
labeling259([]). 
labeling259([V|Vs]) :- 
     indomain259(V), 
     labeling259(Vs).

indomain259(V) :- 
     dom(V,D),
     member(V,D).

member(X,[X|_]).
member(X,[_|R]) :- member(X,R).

% copy of send more money goal using user labeling (not in text). 
gp259(S,E,N,D,M,O,R,Y)  :-  
     domain([S,E,N,D,M,O,R,Y] ,0,9),
     constrain([S,E,N,D,M,O,R,Y]),
     labeling259([S,E,N,D,M,O,R,Y]).
 
% labelling using first fail strategy of choosing the min domain size p260. 
labelingff260([]). 
labelingff260(Vs) :- 
     deleteff260(Vs, V, Rest), %choose the variable with the smallest domain
     indomain259(V),      %assign the first value in the domain
     labelingff260(Rest). %continue with the rest of the list

deleteff260([V0|Vs], V, Rest) :- 
     get_domain_size(V0, S0), 
     min_size(Vs, S0, V0, V, Rest). 

min_size([], _, V, V, []). 
min_size([V1|Vs], S0, V0, V, [V0|Rest]) :-
     get_domain_size(V1, S1), 
     S1 #< S0, % could be < since the sizes are fixed 
     min_size(Vs, S1, V1, V, Rest). 
min_size([V1|Vs], S0, V0, V, [V1|Rest]) :-
     get_domain_size(V1, S1), 
     S1 #>= S0, 
     min_size(Vs, S0, V0, V, Rest). 

get_domain_size(V, S) :- dom(V, D), mylength(D, S).

mylength([],0).
mylength([_|L],N):-N#=N1+1, mylength(L,N1).

% copy of send more money goal using user labelingff (not in text). 
gp260(S,E,N,D,M,O,R,Y)  :-  
     domain([S,E,N,D,M,O,R,Y] ,0,9),
     constrain([S,E,N,D,M,O,R,Y]),
     labelingff260([S,E,N,D,M,O,R,Y]).

% alternate defn of get_domain_size for range domains 
get_domain_size261(V, S) :-  
     mindomain(V, Min), maxdomain(V, Max), S #= Max - Min + 1. 
 
% N-queens program p262.
goal(N, Queens) :-
        length(Queens, N),
        domain(Queens,1,N),
        queens(Queens),
        labeling([],Queens). 

queens([]). 
queens([X|Y]) :-
       safe(X,Y,1),
       queens(Y).

safe(_,[],_).
safe(X,[F|T],Nb) :-
       noattack(X,F,Nb),
       Newnb #= Nb + 1,
       safe(X,T,Newnb).

noattack(X,Y,Nb) :- 
     Y + Nb #\= X, X + Nb #\= Y, X #\= Y.

% goal for 8 queens
gp262(Queens) :- goal(8, Queens).

% middle out labelling strategy p262--263. 
indomain_middle(Var) :- 
     make_list_of_values(Var, List), 
     member(Var, List).
 
make_list_of_values(Var, List) :- 
     dom(Var, Domain), 
     length(Domain, Size), 
     B in 0..1, 2*N + B #= Size, % translation of N = Size div 2.
                                  % since Size is fixed a better translation
                                  % is N is Size // 2.
     halve_list(N, Domain, [], RFirst, Second),
     merge(Second, RFirst, List). 

halve_list(0, L2, L1, L1, L2).
halve_list(N, [H|R], Li, L1, L2) :-
        N #>= 1,
        N1 #= N-1,
        halve_list(N1, R, [H|Li], L1, L2).

merge([], L, L). 
merge([X|L1], L2, [X|L3]) :- merge(L2, L1, L3). 

% goal illustrating part of indomain_middle p263. 
gp263a(RFirst,Second) :-
     halve_list(3, [1,2,5,6,8,9,10], [], RFirst, Second).
 
% copy of labeling using indomain_middle (not in text).
labeling_middle([]). 
labeling_middle([V|Vs]) :- 
     indomain_middle(V), %choose the middle element of the variable
     labeling_middle(Vs).

% copy of 8-queens goal using middle labelling (not in text).
gp263b(Queens) :-
        length(Queens, 8),
        domain(Queens,1,8),
        queens(Queens),
        labeling_middle(Queens). 

% domain splitting approach to labelling program p264.
labelingsplit([]). 
labelingsplit([V|Vs]) :- 
        mindomain(V, Min), 
        maxdomain(V, Max), 
        (Min #= Max -> 
                        labelingsplit(Vs) 
        ; 
                        B in 0..1, 2*Mid + B #= Min+Max, % translation of
                                % Mid = (Min + Max) div 2 but because
                                % Min and Max are fixed better is
                                % Mid is (Min + Max) // 2.
                        labelsplit(V, Mid, Vs)
        ).
 
labelsplit(V, M, Vs):- 
        V #=< M, 
        append(Vs, [V], NVs), 
        labelingsplit(NVs).
labelsplit(V, M, Vs):- 
        V #>= M+1, 
        append(Vs, [V], NVs), 
        labelingsplit(NVs).
 
append([],L,L).
append([H|T],L,[H|T1]):-append(T,L,T1).

% domain splitting version of seesaw goal p265.
gp265(L, F, S) :-
     domain([L,F,S] ,-5,5),
     9 * L + 8 * F + 4 * S #= 0, 
     cumulative([L,F,S],[3,3,3],[1,1,1],1), 
     labelingsplit([L,F,S]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                   8.4 Different Problem Modellings                  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% simple assigment problem Boolean model Ex 8.5 p267.  
gp267([B11,B12,B13,B14,B21,B22,B23,B24,B31,B32,
          B33,B34,B41,B42,B43,B44]) :-
     domain([B11,B12,B13,B14,B21,B22,B23,B24,B31,B32,
      B33,B34,B41,B42,B43,B44],0,1), 
        B11 + B12 + B13 + B14 #= 1,
        B21 + B22 + B23 + B24 #= 1,
        B31 + B32 + B33 + B34 #= 1,
        B41 + B42 + B43 + B44 #= 1,
        B11 + B21 + B31 + B41 #= 1,
        B12 + B22 + B32 + B42 #= 1,
        B13 + B23 + B33 + B43 #= 1,
        B14 + B24 + B34 + B44 #= 1,
        P #=          7 * B11 + B12 + 3 * B13 + 4 * B14
                        + 8 * B21 + 2 * B22 + 5 * B23 +     B24
                        + 4 * B31 + 3 * B32 + 7 * B33 + 2 * B34
                        + 3 * B41 +     B42 + 6 * B43 + 3 * B44,
        P #>= 19,
        labeling([],[B11,B12,B13,B14,B21,B22,B23,B24,B31,B32,
          B33,B34,B41,B42,B43,B44]).

% simple assigment problem element model Ex 8.6 p268.
gp268([W1,W2,W3,W4]) :-
        domain([W1,W2,W3,W4],1,4), 
        all_different([W1,W2,W3,W4]), 
        element(W1,[7,1,3,4],WP1), 
        element(W2,[8,2,5,1],WP2), 
        element(W3,[4,3,7,2],WP3), 
        element(W4,[3,1,6,3],WP4), 
        P #= WP1 + WP2 + WP3 + WP4, 
        P #>= 19, 
        labeling([],[W1,W2,W3,W4]).
 
% simple assigment problem alternate element model Ex 8.7 p269.  
gp269([T1,T2,T3,T4]) :-
        domain([T1,T2,T3,T4],1,4), 
        all_different([T1,T2,T3,T4]), 
        element(T1,[7,8,4,3],TP1), 
        element(T2,[1,2,3,1],TP2), 
        element(T3,[3,5,7,6],TP3), 
        element(T4,[4,1,2,3],TP4), 
        P #= TP1 + TP2 + TP3 + TP4, 
        P #>= 19, 
        labeling([],[T1,T2,T3,T4]).
 
% simple assignment problem element model with additional constraint p270.
gp270([W1,W2,W3,W4]) :-
        domain([B11,B44],0,1), 
        element(W1,[1,0,0,0],B11), 
        element(W4,[0,0,0,1],B44), 
        B11 + B44 #=< 1,
        gp268([W1,W2,W3,W4]).
 
% simple assignment problem combined goal p271.
gp271([W1,W2,W3,W4],[T1,T2,T3,T4]) :-
        domain([W1,W2,W3,W4],1,4), 
        all_different([W1,W2,W3,W4]), 
        element(W1,[7,1,3,4],WP1), 
        element(W2,[8,2,5,1],WP2), 
        element(W3,[4,3,7,2],WP3), 
        element(W4,[3,1,6,3],WP4), 
        P #= WP1 + WP2 + WP3 + WP4, 
        domain([T1,T2,T3,T4],1,4), 
        all_different([T1,T2,T3,T4]), 
        element(T1,[7,8,4,3],TP1), 
        element(T2,[1,2,3,1],TP2), 
        element(T3,[3,5,7,6],TP3), 
        element(T4,[4,1,2,3],TP4), 
        P #= TP1 + TP2 + TP3 + TP4, 
        P #>= 19, 
        iff(W1,1,T1,1), iff(W1,2,T2,1), iff(W1,3,T3,1), iff(W1,4,T4,1), 
        iff(W2,1,T1,2), iff(W2,2,T2,2), iff(W2,3,T3,2), iff(W2,4,T4,2), 
        iff(W3,1,T1,3), iff(W3,2,T2,3), iff(W3,3,T3,3), iff(W3,4,T4,3), 
        iff(W4,1,T1,4), iff(W4,2,T2,4), iff(W4,3,T3,4), iff(W4,4,T4,4), 
        labeling([],[W1,W2,W3,W4]).
 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                 8.5 An Extended Example Scheduling                  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% problem data as predicate p273.
problem([task(j1,3,[],m1), task(j2,8,[],m1), task(j3,8,[j4,j5],m1),
         task(j4,6,[],m2), task(j5,3,[j1],m2), task(j6,4,[j1],m2)]).

once(G) :- call(G), !.

% schedule program p273--274.
schedule(Data, End, Joblist)   :-    
         makejoblist(Data, Joblist, End), 
         precedences(Data, Joblist),
         machines(Data, Joblist),
         labeltasks(Joblist).   
% 
makejoblist([],[],_). 
makejoblist([task(N,D,_,_)|Ts], [job(N,D,TS)|Js], End)  :-  
        TS in 0..1000, 
        TS + D #=< End,
        makejoblist(Ts, Js, End).       

getjob(JL, N, D, TS)  :- once(member(job(N,D,TS), JL)). 
 
precedences([],_). 
precedences([task(N,_,Pre,_)|Ts], Joblist)  :- 
        getjob(Joblist, N, _, TS),
            prectask(Pre, TS, Joblist),
            precedences(Ts, Joblist).   
 
prectask([],  _, _).
prectask([Name|Names], PostStart, Joblist)  :-
        getjob(Joblist, Name, D, TS),
            TS + D #=< PostStart,
            prectask(Names, PostStart, Joblist).        
 
machines([], _).
machines([task(N,_,_,M)|Ts], Joblist)  :-
        getjob(Joblist, N, D, TS),
            machtask(Ts, M, D, TS, Joblist),
            machines(Ts, Joblist).      
 
machtask([], _, _, _, _).
machtask([task(SN,_,_,M0)|Ts], M, D, TS, Joblist)  :- 
             (M = M0 -> 
                 getjob(Joblist, SN, SD, STS),
                 exclude(D, TS, SD, STS)
             ; true ),
            machtask(Ts, M, D, TS, Joblist).    
 
exclude(_D, TS, SD, STS)  :-  STS + SD #=< TS. 
exclude(D, TS, _SD, STS)  :-  TS + D #=< STS. 
 
labeltasks([]). 
labeltasks([job(_,_,TS)|Js])   :-   
     indomain(TS), 
     labeltasks(Js).
 
% goal for finding a schedule p274.
gp274(Joblist) :-
     End = 20, problem(Problem), schedule(Problem, End, Joblist).
 
 
% minimization goal for finding a minimum schedule p276.
gp276(End, Joblist) :-
   End in 0..1000, problem(Problem),  
   minimize((schedule(Problem, End, Joblist), indomain(End)), End).
 
% schedule program with redundant constraints p277.
schedule277(Data, End, Machinelist, Joblist)  :-  
          makejoblist(Data, Joblist, End), 
          precedences(Data, Joblist),
          makeemptylists(Machinelist, Emptys),
          extrainfo(Data,Joblist,Machinelist,Emptys,Joblist), 
          machines(Data, Joblist),
          labeltasks(Joblist).
 
makeemptylists([],[]). 
makeemptylists([_|L],[[]|R]) :- makeemptylists(L,R).
 
extrainfo(_, [], _, _, _).
extrainfo(Data, [job(N,_,TS)|Js], Machinelist, Emptys, Joblist) :-
        predecessors(N, Data, [], Pre), 
        splittasks(Pre, Data, Machinelist, Emptys, Split), 
        list_redundant(Split, Joblist, TS), 
        extrainfo(Data, Js, Machinelist, Emptys, Joblist).
 
splittasks([], _, _, Split, Split). 
splittasks([N|Ns], Data, Machines, Split0, Split) :-
     gettask(Data, N, task(_,_,_,M)), 
     insert(Machines, M, N, Split0, Split1), 
     splittasks(Ns, Data, Machines, Split1, Split).
 
insert([M|_], M, T, [L|Ls], [[T|L]|Ls]).
insert([M0|Ms], M, T, [L|Ls0], [L|Ls]) :- 
     M0 \== M,
     insert(Ms, M, T, Ls0, Ls).
 
list_redundant([], _, _). 
list_redundant([L|Ls], Joblist, TS) :- 
     redundant(L, Joblist, TS, 0, []), 
     list_redundant(Ls, Joblist, TS).
 
redundant([], _, TS, TotalD, ListTS) :- 
     TS #>= MinTs + TotalD, % translation of TS #>= minimum(ListTS) + TotalD.
     minimum(ListTS,MinTs). % using new constraint minimum 
redundant([N|Ns], Joblist, TS, TotalD0, ListTS) :- 
     getjob(Joblist, N, DN, TSN), 
     TotalD #= TotalD0 + DN, 
     redundant(Ns, Joblist, TS, TotalD, [TSN|ListTS]).
 
gettask(Data, N, T)  :- 
     T = task(N, _, _, _), 
     once(member(T, Data)).
 
lookup(Data, N, P) :- member(task(N,_,P,_), Data).

% Improved predecessors program from p197.
predecessors(N, List, Pre0, Pre) :- 
     lookup(List, N, NImPre), 
     cumul_predecessors(NImPre, List, Pre0, Pre).
 
cumul_predecessors([], _, Pre, Pre). 
cumul_predecessors([N|Ns], List, Pre0, Pre) :- 
     member(N, Pre0),  
     cumul_predecessors(Ns, List, Pre0, Pre). 
cumul_predecessors([N|Ns], List, Pre0, Pre) :- 
     not_member2(N, Pre0), 
     predecessors(N, List, [N|Pre0], Pre1), 
     cumul_predecessors(Ns, List, Pre1, Pre). 

%a different not_member because the domains dont allow arbitrary constants
%wont work unless arguments are ground
not_member2(_,[]).
not_member2(X,[Y|Ys]) :- X \== Y, not_member2(X,Ys).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% minimum constraint defined using indexicals
minimum([],0).    % special case for above program
minimum([X|Xs],M) :-
        minimum(Xs, X, M).
minimum([], M, M).
minimum([X|Xs], M0, M) :-
        min2(X,M0,M1),
        minimum(Xs,M1,M).

% minimum propagation indexical see p102.
% X = minimum{Y,Z}
min2(Y,Z,X) +: 
        Y in min(X)..sup,                       % Y >= min(X)
        Z in min(X)..sup,                       % Z >= min(Z)
        X in ((min(Y)..sup) \/ (min(Z)..sup))   % X >= minimum(min(Y),min(Z))
             /\ (inf..max(Y)) /\ (inf..max(Z)). % X <= minimum(max(Y),max(Z))
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

        
% minimization goal with redundancy p278.
gp278(End, Joblist) :-
   End in 0..1000, problem(Problem), 
   minimize((schedule277(Problem, End, [m1,m2], Joblist), indomain(End)), End).


% scheduling program using cumulative constraints p279. 
schedule279(Data, End, Machinelist, Joblist)  :-  
         makejoblist(Data, Joblist, End), 
          precedences(Data, Joblist),
          makeemptylists(Machinelist, Emptys),
          extrainfo(Data,Joblist,Machinelist,Emptys,Joblist), 
          cumulative_machines(Data,Joblist,Machinelist,Emptys),
          labeltasks(Joblist).
 
cumulative_machines(Data, Joblist, Machinelist, Emptys) :- 
     datatolist(Data, Names), 
     splittasks(Names, Data, Machinelist, Emptys, Split), 
     makecumulatives(Split, Joblist).
 
datatolist([],[]). 
datatolist([task(N,_,_,_)|Ts],[N|Ns]) :- 
     datatolist(Ts,Ns).
 
makecumulatives([], _). 
makecumulatives([L|Ls], Joblist) :- 
     makecumulative(L, Joblist, [], [], []), 
     makecumulatives(Ls, Joblist). 
 
makecumulative([], _, Ts, Ds, Rs) :- 
     cumulative(Ts, Ds, Rs, 1). 
makecumulative([N|Ns], Joblist, Ts, Ds, Rs) :- 
     getjob(Joblist, N, DN, TSN), 
     makecumulative(Ns, Joblist, [TSN|Ts], [DN|Ds], [1|Rs]). 

% minimization goal with cumulative p279.
gp279(End, Joblist) :-
   End in 0..1000, problem(Problem), 
   minimize((schedule279(Problem, End, [m1,m2], Joblist), indomain(End)), End).

% labelling predicate that labels the earliest job first p280--281. 
labeltasks280([]). 
labeltasks280(Js)   :-   
     gettimes(Js, Ts), 
     label_earliest(Ts).
 
gettimes([],[]). 
gettimes([job(_,_,TS)|Js], [TS|Ts]) :- gettimes(Js, Ts). 
 
label_earliest([]).  
label_earliest([TS0|Ts]) :- 
     mindomain(TS0, M0),
     find_min_start(Ts, TS0, M0, TS, M, RTs), 
     rest_earliest(TS, M, [TS0|Ts], RTs). 
 
rest_earliest(TS, M, _Ts, RTs) :- 
     TS #= M, 
     label_earliest(RTs). 
rest_earliest(TS, M, Ts, _RTs) :- 
     TS #\= M, 
     label_earliest(Ts).  
 
find_min_start([], TS, M, TS, M, []). 
find_min_start([TS1|Ts], TS0, M0, TS, M, RTs) :- 
     mindomain(TS1, M1), 
     (M1 #< M0 -> 
          RTs = [TS0|RTs1], 
          find_min_start(Ts, TS1, M1, TS, M, RTs1) 
     ; 
          RTs = [TS1|RTs1], 
          find_min_start(Ts, TS0, M0, TS, M, RTs1) 
     ). 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                         8.6 Arc Consistency                         %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% op declaration for consistent and dirty implmentation
% using the global constraint features of SICStus
% Oh oh my sictus doesnt include this facility? so not debugged
% fd_global does not appear to exist in SICStus 3.7 !!!
:- op(100, xf, consistent). 
:- use_module(library(terms)).
:- use_module(library(ordsets)).
consistent(Goal) :-
        term_variables(Goal,Vars),
        dom_suspensions(Vars,Susp),
        fd_global(consistent(Goal),erk,Susp).

dom_suspensions([], []).
dom_suspensions([X|Xs], [dom(X)|Susp]) :- 
        dom_suspensions(Xs, Susp).

dispatch_global(consistent(Goal),_,_,Actions) :-
        term_variables(Goal,Vars),
        findall(Vars,Goal,Ans),
        makeemptylists(Vars,Es),
        build_domains(Ans,Es,Ds),
        Actions = [setdomains(Vars,Ds)].

build_domains([], Ds, Ds).
build_domains([A|As], Ds0, Ds) :-
        addels(A,Ds0,Ds1),
        build_domains(As,Ds1,Ds).

addel([],[],[]).
addel([E|Es],[D|Ds],[ND|NDs]) :-
        ord_add_element(E,D,ND),
        addel(Es,Ds,NDs).

setdomains([],[]).
setdomains([V|Vs],[L|Ls]) :-
        (L = [] ->
            fail
        ;
            my_list_to_fdset(L,D),
            fd_dom(V,D)
        ),
        setdomains(Vs,Ls).

my_list_to_fdset([F|R],D) :- my_list_to_fdset(R,{F},D).
my_list_to_fdset([],D,D).
my_list_to_fdset([X|Xs],D0,D) :- my_list_to_fdset(Xs,{X}\/D0,D).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  
% goal using arc consistency p283.
gp283(N,M,E) :-
     domain([N,M,E],1,3), N #\= M,N #\= E,M #\= E, 
             likes(N, nicole) consistent, 
             likes(M, maria) consistent, 
             likes(E, erika) consistent, 
             labeling([N,M,E]).
 
% profit program p284. 
profit_1(1,7).
profit_1(2,1).
profit_1(3,3).
profit_1(4,4).

% goal for profit p284. %% same problem as above
gp284(W1,WP1) :- profit_1(W1,WP1) consistent.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                       8.6 Reified Constraints                       %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% either program either X1 = X or X2 = X p285
either(X,X1,X2) :- 
     domain([B1,B2],0,1), 
     (X #= X1 #<=> B1), (X #= X2 #<=> B2),
     1 #=< B1+B2.

% goal for either p285.
gp285(A,C,E) :- 
        domain([A,C,E],0,4), 
        either(A,C,E), 
        A in 1..2, C in 3..4, E in 2..3. 

% program for iff in terms of reified constraints p285. 
iff(X1,V1,X2,V2) :- 
     B in 0..1,
     (X1 #= V1 #<=> B),
     (X2 #= V2 #<=> B).
 






