% 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,Doby),
	precedence(Zacatky,Doby),
	lide(Zacatky,Doby),
	labeling([ff],Zacatky),
	tiskni(Ukoly,Zacatky).

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

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

nastav_domeny([],[],[]).
nastav_domeny([U|Ukoly],[Z|Zacatky],[Doba|Doby]) :-
	U=ukol(_Id,Doba,MinStart,MaxKonec),
	MaxStart #= MaxKonec-Doba, 
	Z in MinStart..MaxStart,
	nastav_domeny(Ukoly,Zacatky,Doby).	

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

omezeni_precedence([],_Zacatky,_Doby).
omezeni_precedence([prec(A,B)|Prec],Zacatky,Doby) :-
	nth(A,Zacatky,ZA),
	nth(B,Zacatky,ZB),
	nth(A,Doby,DA),
	ZA + DA #< ZB,
	omezeni_precedence(Prec,Zacatky,Doby).

lide(Zacatky,Doby) :- serialized(Zacatky,Doby).

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

omezeni_lide([],_Zacatky,_Doby).
omezeni_lide([Clovek|Lide],Zacatky,Doby) :-
	Clovek=clovek(_Id,Kapacita,Ukoly),
	omezeni_clovek(Ukoly,Kapacita,Zacatky,Doby),
	omezeni_lide(Lide,Zacatky,Doby).

omezeni_clovek(Ukoly,Kapacita,Zacatky,Doby) :- 
	omezeni_clovek(Ukoly,Kapacita,Zacatky,Doby,[],[]).

% omezeni_clovek(Ukoly,Zacatky,Doby,ClovekZ,ClovekD)
omezeni_clovek([],Kapacita,_Zacatky,_Doby,ClovekZ,ClovekD) :-
	% serialized(ClovekZ,ClovekD).
	length(ClovekZ,Delka),
	listOf1(Delka,ListOf1),
	cumulative(ClovekZ,ClovekD,ListOf1,Kapacita).
omezeni_clovek([U|Ukoly],Kapacita,Zacatky,Doby,ClovekZ,ClovekD) :-
	nth(U,Zacatky,Z),
	nth(U,Doby,D),
	omezeni_clovek(Ukoly,Kapacita,Zacatky,Doby,[Z|ClovekZ],[D|ClovekD]).

listOf1(0,[]) :- !.
listOf1(D,[1|L]) :-
	D1 is D-1,
	listOf1(D1,L).

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]) :-
	nth(Id,Ukoly,U),
	nth(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.
