

% 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.






















