% lista rĂłĹźnicowa to lista postaci X = [1,2,3 | V] gdzie V to zmienna ktĂłrÄ niezaleĹźnie "znamy"


% 1) dokĹadanie na poczÄtek to konstrukcja typu [0 | X]
% 2) dokĹadanie na koniec to konstrukcja typu V = [4 | L1]

% tak naprawdÄ taka lista to para [... | V] oraz V. MoĹźemy to pisaÄ tak:
% [1,2,3 | V] - V

/*
            -

         /      \

    [ ... | V]   V
*/

% test(X) :- X = tree(Y, 2, nil) - Y, X = _ - apple.

% lista rĂłĹźnicowa: [1,2,3,4 | Y] - Y


% asList(D, X) gdy X to uzyskana w czasie staĹym "zamkniÄta" dana lista rĂłĹźnicowa D (jako zwykĹa lista)

asList(L - V, X) :- X - [] = L - V.


% head(L, X) gdy X to gĹowa listy rĂłĹźnicowej L

head([X|_] - _V, X).

% tail(L, L1) gdy L1 to lista rĂłĹźnicowa po odciÄciu gĹowy

tail([_|L] - V, L - V).

% putlast(L1, X, L2) gdy L2 to lista rĂłĹźnicowa L1 z doklejonym X na koĹcu

/*
gdy wywoĹamy (gdzie V to zmienna!):
  putlast(L - V, X, L - V1)
to prolog stwierdzi, Ĺźe trzeba wykonaÄ uzgodnienie:
  V = [X | V1].
np. przy wywoĹaniu
  putlast([1,2,3,4 | V] - V, 5, Y).
uzgadniamy, Ĺźe V = [5 | V1]
i zwracamy
  Y = [1,2,3,4,5 | V1] - V1
*/

putlast(L - [X | V1], X, L - V1).

% sklej(L1, L2, L3) gdy L3 to lista rĂłĹźnicowa powstaĹa ze sklejenia L1 i L2

sklej( L1 - L2, L2 - V2, L1 - V2).


test(D2) :- D1 = V - V, head(D1, 6), putlast(D1, 6, D2).

% moĹźna uĹźywaÄ var(...) co wymaga by dana wartoĹÄ byĹa ciÄgle nieustalonÄ zmiennÄ

% implementacja kolejki:

init(Kolejka - Kolejka). % tworzy kolejkÄ = jednÄ, pustÄ listÄ rĂłĹźnicowÄ

% put(E, K1, K2) gdy K2 powstaje przez wstawienie elementu E na koniec kolejki K1
% === putlast

put(E, K1 - [E | K2], K1 - K2).

/*
przeĹledĹşmy wywoĹanie put(7, [1,2|V] - V, L1 - V1):
0) V = V, L1 = L1, V1 = V1
1) okazuje siÄ, Ĺźe:
   V  = [7 | K2], bo tak wygląda drugi argument put
   K1 = [1,2|V] = [1,2,7 | K2] // tutaj ostatnia rĂłwnoĹÄ jest kluczowa: 7 wskakuje na koniec K1
2) więc:
   L1 = K1 = [1,2,7 | K2]
   V1 = K2 = K2
3) więc L1 - V1 = [1,2,7 | K2] - K2
*/

% get(E, K1, K2) gdy K2 powstaje przez wyjÄcie z kolejki K1 elementu E (z poczÄtku)
% === head + tail

get(E, [E | K1] - K2, K1 - K2).

% empty(K) gdy kolejka K jest pusta

% empty(L1 - V1) :- L1 = V1. % (Ĺşle, powstajÄ nieskoĹczone listy / kolejki)

empty(L1 - _V1) :- var(L1).


% PLAN : wszerz drzewa binarnego (czyli BFS) w oparciu o zaimplementowane powyĹźej kolejki


% wszerz(T, L) gdy L jest listÄ wierzchoĹkĂłw drzewa T przy przejĹciu BFS

wszerz(T, L) :-
	wszerzFIFO([T | V] - V, L). % kolejka jedno-elementowa zawierajÄca T

% wszerzFIFO(K, L) gdy L to lista wierzchoĹkĂłw BFS drzew z kolejki K

wszerzFIFO(K - _V, []) :-
	var(K),  % var(K) sprawdza, Ĺźe kolejka jest pusta
	!.       % ! odcina kolejne moĹźliwoĹci, by nie pobieraÄ z pustej kolejki

wszerzFIFO([leaf | K] - V, L) :-
	wszerzFIFO(K - V, L). % na poczÄtku kolejki jest leaf i go olewamy

wszerzFIFO([tree(TL, D, TR) | K] - [TL, TR | V], [D | L]) :-
	wszerzFIFO(K - V, L).

% na początku kolejki jest tree(TL, D, TR), wstawiamy TL, TR na koniec kolejki i wykonujemy się rekurencyjnie wszerzFIFO(K - V, L), na koniec dostawiamy D na początek listy L


% alternatywnie, ten sam kod, ale z operacjami na kolejkach

wszerz2(T, L) :-
	init(K1),
	put(T, K1, K2),
	wszerzFIFO2(K2, L).

wszerzFIFO2(K, []) :-
	empty(K),
	!.		% znowu tutaj jest CZERWONE odciÄcie, by nie pobieraĹ z pustej kolejki

wszerzFIFO2(K1, L) :-
	get(leaf, K1, K2),
	wszerzFIFO2(K2, L).

wszerzFIFO2(K1, [D | L]) :-
	get(tree(TL, D, TR), K1, K2),
	put(TL, K2, K3),
	put(TR, K3, K4),
	wszerzFIFO2(K4, L).

% zielone odciÄcia:

max(X1, X2, X2) :- X1 =< X2, !. % moĹźemy dostawiÄ ZIELONE odciÄcie

max(X1, X2, X1) :- X1 > X2.