% ukol(Id,Doba,MinStart,MaxKonec)
ukol(1,4,8,70).
ukol(2,2,7,60).
ukol(3,1,2,25).
ukol(4,6,5,55).
ukol(5,4,1,45).
ukol(6,2,4,35).
ukol(7,8,2,25).
ukol(8,5,0,20).
ukol(9,1,8,40).
ukol(10,7,4,50).
ukol(11,5,2,50).
ukol(12,2,0,35).
ukol(13,3,30,60).
ukol(14,5,15,70).
ukol(15,4,10,40).

% prec(A,B)
prec(8,7).
prec(6,12).
prec(2,1).

% clovek(Id,Kapacita,Ukoly)
clovek(1,2,[1,2,3,4,5]).
clovek(2,1,[6,7,8,9,10]).
clovek(3,2,[11,12,13,14,15]).

:- use_module(library(clpfd)).
:- use_module(library(lists)).

ukoly(Zacatky) :-
	domeny(Ukoly,Zacatky,Tasks),
	precedence(Tasks),
	lide(Tasks),
	labeling([ff],Zacatky),
	tiskni(Ukoly,Zacatky).

ukoly_lide(Zacatky) :-
	domeny(Ukoly,Zacatky,Tasks),
	precedence(Tasks),
	lide(Tasks,Lide),
	labeling([ff],Zacatky),
	tiskni_lide(Lide,Ukoly,Zacatky).

domeny(Ukoly,Zacatky,Tasks) :-
	findall(ukol(Id,Doba,MinStart,MaxKonec),
                ukol(Id,Doba,MinStart,MaxKonec), Ukoly),
        nastav_domeny(Ukoly,Zacatky,Tasks).

nastav_domeny([],[],[]).
nastav_domeny([ukol(Id,Doba,MinStart,MaxKonec)|Ukoly],[Z|Zacatky],
              [task(Z,Doba,K,1,Id)|Tasks]) :-
	MaxStart is MaxKonec-Doba, 
	Z in MinStart..MaxStart,
        K #= Z + Doba,
	nastav_domeny(Ukoly,Zacatky,Tasks).	

precedence(Tasks) :-	
	findall(prec(A,B),prec(A,B),P),
	omezeni_precedence(P,Tasks).

omezeni_precedence([],_Tasks).
omezeni_precedence([prec(A,B)|Prec],Tasks) :-
	nth1(A,Tasks,task(ZA,DA,_KA,1,A)),
	nth1(B,Tasks,task(ZB,_DB,_KB,1,B)),
	ZA + DA #=< ZB,
	omezeni_precedence(Prec,Tasks).

lide(Tasks) :- cumulative(Tasks).

lide(Tasks,Lide) :- 
	findall(clovek(Kdo,Kapacita,Ukoly),clovek(Kdo,Kapacita,Ukoly), Lide),
        omezeni_lide(Lide,Tasks).

omezeni_lide([],_Tasks).
omezeni_lide([clovek(_Id,Kapacita,UkolyClovek)|Lide],Tasks) :-
	omezeni_clovek(UkolyClovek,Kapacita,Tasks),
	omezeni_lide(Lide,Tasks).

omezeni_clovek(Ukoly,Kapacita,Tasks) :- 
	omezeni_clovek(Ukoly,Kapacita,Tasks,[]).

% omezeni_clovek(IdUkoly,Kapacita,Tasks,TasksC)
omezeni_clovek([],Kapacita,_Tasks,TasksC) :-
	cumulative(TasksC,[limit(Kapacita)]).
omezeni_clovek([U|Ukoly],Kapacita,Tasks,TasksC) :-
	nth1(U,Tasks,TU),
	omezeni_clovek(Ukoly,Kapacita,Tasks,[TU|TasksC]).

tiskni_lide([],_Ukoly,_Zacatky).
tiskni_lide([Clovek|Lide],Ukoly,Zacatky) :-
	Clovek=clovek(Id,Kapacita,IdUkoly),
	priprav_lide(IdUkoly,Ukoly,Zacatky,ClovekUkoly,ClovekZacatky),
	format("Clovek ~d (~d):",[Id,Kapacita]),
	tiskni(ClovekUkoly,ClovekZacatky),
	tiskni_lide(Lide,Ukoly,Zacatky).

priprav_lide([],_Ukoly,_Zacatky,[],[]).
priprav_lide([Id|Ids],Ukoly,Zacatky,[U|ClovekUkoly],[Z|ClovekZacatky]) :-
	nth1(Id,Ukoly,U),
	nth1(Id,Zacatky,Z),
	priprav_lide(Ids,Ukoly,Zacatky,ClovekUkoly,ClovekZacatky).

tiskni(Ukoly,Zacatky) :- 
	priprav(Ukoly,Zacatky,Vstup),
	quicksort(Vstup,Vystup),
	nl, tiskni(Vystup).

priprav([],[],[]).
priprav([ukol(Id,Doba,MinStart,MaxKonec)|Ukoly], [Z|Zacatky],
        [ukol(Id,Doba,MinStart,MaxKonec,Z)|Vstup]) :-
	priprav(Ukoly,Zacatky,Vstup).
	
tiskni([]) :- nl.
tiskni([V|Vystup]) :-
	V=ukol(Id,Doba,MinStart,MaxKonec,Z),
	K is Z+Doba,
	format('   ~d: \t~d..~d \t(~d: ~d..~d)\n',
               [Id,Z,K,Doba,MinStart,MaxKonec] ),
	tiskni(Vystup).

quicksort(S, Sorted) :- quicksort1(S,Sorted-[]).

quicksort1([],Z-Z).
quicksort1([X|Tail], A1-Z2) :- 
        split(X, Tail, Small, Big),
        quicksort1(Small, A1-[X|A2]),
        quicksort1(Big, A2-Z2). 

split(_X, [], [], []).
split(X, [Y|T], [Y|Small], Big) :- greater(X,Y), !, split(X, T, Small, Big).
split(X, [Y|T], Small, [Y|Big]) :- split(X, T, Small, Big).

greater(ukol(_,_,_,_,Z1),ukol(_,_,_,_,Z2)) :- Z1>Z2.