

% zdanie(Zdanie, Reszta) gdy Zdanie = Slowo * Reszta, Slowo - jw.
% (np. zdanie([a,a,b,b,c,d], [c,d]) - sukces)

zdanie(Z, R) :- append(S, R, Z), slowo(S).


% flagaPolska(Lista, Flaga) wtw, gdy Flaga jest posortowaną listą Lista, złożoną ze stałych b,c
% (np. flagaPolska([b,c,b,c], [b,b,c,c]) - sukces)

% opcja 1: przez arytmetyke, takie sortowanie kubelkowe

% opcja 2: dwa akumulatory i na koniec append

% opcja 3: dwa przejscia:

flagaPolska(L, F) :-
	collect(L, c, [], C),
	collect(L, b, C, F).

% collect(L, E, A, R) dorzuca do akumulatora A wszystkie wystąpienia elementu E na liście L
% i zwraca wszystko jako wynik R


% leciutkie oszustwo bo uzywamy \= / 2 ale robimy to dla termow całkowicie ustalonych, więc nie jest to aż tak bolesne
% w rozwiązaniach domowych NIE można tego używać (!!!)
% tutaj moglibyśmy rozważyć wszystkie przypadki: osobne predykaty collectC, collect B, ...

collect([], _, R, R).

collect([X|L], X, A, R) :- collect(L, X, [X|A], R).

collect([Y|L], X, A, R) :- X \= Y, collect(L, X, A, R).


%. flagaHolenderska(ListaRWB, RWB) (flaga: red-white-blue)

flagaHolenderska(L, RWB) :-
	collect(L, b, [],   B),
	collect(L, w,  B,  WB),
	collect(L, r, WB, RWB).


% quickSort(L, S) wtw, gdy S jest wynikiem sortowania L (algorytm QuickSort)


quickSort([], []).

quickSort([X|L], R) :-
	split(L, X, LA, LB),    % LA to lista mniejszych rownych zas LB to lista wiekszych
	quickSort(LA, SA),      % SA to posortowana lista mniejszych
	quickSort(LB, SB),      % SB to posortowana lista wiekszych
	append(SA, [X|SB], R).  % czas kwadratowy - do sprawdzenia !!! (?)

% split(L, X, LA, LB) rozdziela liste L na elementy mniejsze (w liscie LA) i wieksze (w liscie LB) od X

split(L, X, LA, LB) :- split(L, X, [], [], LA, LB).

% split(L, X, AA, AB, LA, LB) - wersja z akumulatorami AA i AB

split([], _, AA, AB, AA, AB).

split([E|L], X, AA, AB, LA, LB) :-
	E =< X,
	split(L, X, [E|AA], AB, LA, LB).

split([E|L], X, AA, AB, LA, LB) :-
	E > X,
	split(L, X, AA, [E|AB], LA, LB).


% flatten(L, F) wtw, gdy L jest zagnieżdżoną listą list, których elementami są liczby całkowite, a F jest spłaszczoną listą L (np. flatten([1,[[[[2,[3]]], 4], 5]], [1,2,3,4,5]) - sukces)






