% Dijkstras Dutch Flag Problem
% ============================
% Eine Liste mit rot, weiss oder blau gefaerbten Objekten 
% soll so umsortiert werden, dass zunaechst alle roten,
% dann alle weissen und schliesslich alle blauen Objekte
% auftreten. Dabei soll die relative Ordnung der gleichfarbigen
% Objekte untereinander erhalten bleiben.
%


dutch(Xs,RWB) :- distribute(Xs,R,W,B),
                 append(W,B,WB), 
                 append(R,WB,RWB).

distribute([red(X)|Xs],[red(X)|Rs],Ws,Bs)     :- distribute(Xs,Rs,Ws,Bs).
distribute([white(X)|Xs],Rs,[white(X)|Ws],Bs) :- distribute(Xs,Rs,Ws,Bs).
distribute([blue(X)|Xs],Rs,Ws,[blue(X)|Bs])   :- distribute(Xs,Rs,Ws,Bs).
distribute([],[],[],[]).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Version mit Differenzlisten  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

dutchDL(Xs,RWB) :- distribute_dls(Xs,RWB,WB,WB,B,B,[]).

distribute_dls([red(X)|Xs],[red(X)|Rs],Rs1,Ws,Ws1,Bs,Bs1)  
                :- distribute_dls(Xs,Rs,Rs1,Ws,Ws1,Bs,Bs1).
distribute_dls([white(X)|Xs],Rs,Rs1,[white(X)|Ws],Ws1,Bs,Bs1) 
                :- distribute_dls(Xs,Rs,Rs1,Ws,Ws1,Bs,Bs1). 
distribute_dls([blue(X)|Xs],Rs,Rs1,Ws,Ws1,[blue(X)|Bs],Bs1) 
                :- distribute_dls(Xs,Rs,Rs1,Ws,Ws1,Bs,Bs1). 
distribute_dls([],Rs,Rs,Ws,Ws,Bs,Bs).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% erzeuge Liste mit 3N Eintraegen
genList(0,[]).
genList(N,[blue(N),red(N),white(N)|L]) :- N1 is N-1, genList(N1,L).
 
% Testaufrufe
test(N,T) :- genList(N,L), statistics(cputime,S1), dutch(L,_), 
             statistics(cputime,S2), T is S2-S1.
testDL(N,T) :- genList(N,L), statistics(cputime,S1), dutchDL(L,_), 
             statistics(cputime,S2), T is S2-S1.