%zadanie 1

%stos

put(E, S, [E|S]).
get([H|T], H, T).
empty([]).

addall(Element, Goal, Stack, Rest):-
  findall(Element, Goal, List),
  putall(List, Stack, Rest).

putall([],Rest,Rest).
putall([Head|Tail],Stack,Rest):-
  put(Head,Stack,NewStack),
  putall(Tail,NewStack,Rest).


%kolejka

putk(E, S-Wsk, S-Wsk1) :-
  Wsk = [E|Wsk1].
getk([H|T]-Wsk, H, T-Wsk) :-
  nonvar(H).
emptyk(X - X).

addall(Element, Goal, Stack, Rest):-
  findall(Element, Goal, List),
  putall(List, Stack, Rest).

putall([],Rest,Rest).
putall([Head|Tail],Stack,Rest):-
  put(Head,Stack,NewStack),
  putall(Tail,NewStack,Rest).



  %zadanie 3
  insert(leaf, Elem, node(leaf, Elem, leaf)).

  insert(node(L, V, R), Elem, node(L, V, R)) :-
    Elem=V,!.

  insert(node(L, V, R), Elem, InsertedTree) :-
    Elem>V,!,
    insert(R, Elem, InsertedSubTree),
    InsertedTree = node(L, V, InsertedSubTree).

  insert(node(L, V, R), Elem, InsertedTree) :-
    insert(L, Elem, InsertedSubTree),
    InsertedTree = node(InsertedSubTree, V, R).

    find(node(_, Val, _), Elem) :-
      Elem = Val.
    find(node(Left, _, _), Elem) :-
      find(Left, Elem).
    find(node(_, _, Right), Elem) :-
      find(Right, Elem).

    findMax(node(_, V, leaf), V) :-!.
    findMax(node(_, _, Right), Max) :-
      find(Right, Max).

    delMax(node(L, Val, leaf), Val, L).
    delMax(node(Left, Value, node(L, Val, leaf)), Val, node(Left, Value, L)).
    delMax(node(Left, Val, R), Val, FTree) :-
      delMax(R, Val, PFTree),
      FTree = node(Left, Val, PFTree).


      del(leaf,_,leaf):-!.
      del(node(Left,Val,Right),V2Del,Wynik):-
        V2Del>Val,!,
        del(Right,V2Del,PrawyWynik),
        Wynik = node(Left,Val,PrawyWynik).

      del(node(Left,Val,Right),V2Del,Wynik):-
        V2Del<Val,!,
        del(Left,V2Del,LewyWynik),
        Wynik = node(LewyWynik,Val,Right).

      del(node(Left,Val,Right),Val,Wynik):-
        insertTree(Right,Left,Wynik).

      insertTree(leaf,X,X):-!.
      insertTree(node(leaf,Val,Wynik),X,node(X,Val,Wynik)):-!.
      insertTree(node(Left,V,Right),X,node(InsertedLeft,V,Right)):-
        insertTree(Left,X,InsertedLeft).