%zad 1
appn1(L,X):-
  appn(L,[X]-X).
appn([],_-[]).
appn([[]|T],Acc):-!,
  appn(T,Acc).
appn([[H|H1]|T],L-End):-
  End=[H|End1],
  appn([H1|T],L-End1).

%zad 2
flatten(Lista_zlozona,Lista_splaszczona_rev):-
  flatten(Lista_zlozona,[],Lista_splaszczona),
  reverse(Lista_splaszczona,Lista_splaszczona_rev).
flatten([],Acc,Acc):-!.
flatten([H|T],Acc,Lista_splaszczona):-
  atomic(H),
  Acc1=[H|Acc],
  flatten(T,Acc1,Lista_splaszczona),!.
flatten([H|T],Acc,Lista_splaszczona):-
  flatten(H,Acc,Lista_splaszczona2),
  flatten(T,Lista_splaszczona2,Lista_splaszczona).

%zad 3
halve(Lista,P,Druga_polowa):-
  halve(Lista,[P]-P,Lista,Druga_polowa).
halve(Acc1,_-[],[],Acc1):-!.
halve(Acc1,_-[],[_],Acc1):-!.
halve(Lista,L-End,Acc1,Druga_polowa):-
  Lista=[H|T],
  Acc1=[_|[_|T1]],
  End=[H|End2],
  halve(T,L-End2,T1,Druga_polowa).

%zad 4
merge1(L1,L2,X):-
  merge(L1,L2,[X]-X).
merge([],B,_-B):-!.
merge(A,[],_-A):-!.
merge([H1|T1],[H2|T2],L-End):-
  H1<H2,!,
  End=[H1|End1],
  merge(T1,[H2|T2],L-End1).
merge(L1,[H2|T2],L-End):-
  End=[H2|End1],
  merge(L1,T2,L-End1).

merge_sort([],[]):-!.
merge_sort([A],[A]):-!.
merge_sort(Lista,Lista_sort):-
  halve(Lista,L,R),
  merge_sort(L,L_sort),
  merge_sort(R,R_sort),
  merge1(L_sort,R_sort,Lista_sort).

%zad 5
dalsze(X,0,X):-!.
dalsze([_|X],N,Y):-
    NN is N-1,
    dalsze(X,NN,Y).



merge_sort_5(_,0,[]):-!.
merge_sort_5([H|_],1,[H]):-!.
merge_sort_5([A],_,[A]).
merge_sort_5(X,N,Y):-
    N1 is N div 2,
    N2 is N-N1,
    merge_sort_5(X,N1,YY),
    dalsze(X,N1,Z),
    merge_sort_5(Z,N2,ZZ),
    merge1(YY,ZZ,Y).

%zad 6
merge_sort2(Lista,Lista_sort):-
  na_singletony(Lista,[Lista_poj]-Lista_poj),
  merge_sort_straszna(Lista_poj,[Lista_sort]-Lista_sort).

merge_sort_straszna([A],[A]-A):-!.
merge_sort_straszna(Lista_poj,[Lista_sort]-Lista_sort):-
  merge_sort3(Lista_poj,[Lista_sort]-Lista_sort_straszna),
  merge_sort_straszna(Lista_sort_straszna,[Lista_sort]-Lista_sort).

na_singletony([],_-[]).
na_singletony([H|T],L-End):-
  End=[[H]|End1],
  na_singletony(T,L-End1).

merge_sort3([],_-[]):-!.
merge_sort3([A],_-[A]):-!.
merge_sort3([H1|[H2|T]],L-End):-
  merge1(H1,H2,Wyn),
  End=[Wyn|End1],
  merge_sort3(T,L-End1).

  %zad 7
split(List,Med,S,B):-
  split1(List,Med,[S]-S,[B]-B).
split1([],_,_-[],_-[]).
split1([H|T],Med,S-EndS,B-EndB):-
  H<Med,!,
  EndS=[H|EndS1],
  split1(T,Med,S-EndS1,B-EndB).
split1([H|T],Med,S-EndS,B-EndB):-
  EndB=[H|EndB1],
  split1(T,Med,S-EndS,B-EndB1).

qsort(List, Sorted):-
  qsort(List, Sorted, []).

qsort([], Sorted, Sorted).

qsort([H|T], S1, Acc):-
  split(T, H, S, B),
  qsort(B, B1, Acc),
  qsort(S, S1, [H|B1]).

%zad 9
sum(X,Y,Z):-
    nonvar(X),
    nonvar(Y),!,
    Z is X + Y.
sum(X,Y,Z):-
    nonvar(Z),
    nonvar(Y),!,
    X is Z - Y.
sum(X,Y,Z):-
    nonvar(Z),
    nonvar(X),!,
    Y is Z - X.
sum(X,Y,Z):-
    nonvar(X),!,
    itr(0,Y),
    Z is Y + X.
sum(X,Y,Z):-
    nonvar(Y),!,
    itr(0,X),
    Z is Y + X.
sum(X,Y,Z):-
    nonvar(Z),!,
    itrm(0,X),
    Y is Z - X.
sum(X,Y,Z):-
    itr(0,Y),
    itr(0,X),
    Z is X + Y.

itr(X,X).
itr(X,Y):-
    Z is X + 1,
    itr(Z,Y).

itrm(X,X).
itrm(X,Y):-X\=0,Y is -X.
itrm(X,Y):-
    Z is X + 1,
    itrm(Z,Y).