%%Горохова Юлия
%%5081/12
%%Программа, написанная по предоставленным модульным тестам
%%Часть 2.Деревья

  -module(assoc2).
  -export([new/0,lookup/3, insert/3,delete/2, from_list/1, to_list/1, fold/3, filter/2]).

new() -> {nil,nil,nil,nil}.

%Поиск заданного ключа в дереве
lookup(_, _, {nil, 0, nil, nil}) -> [];
lookup(Key, _, {Key, H, S, B}) -> {Key, H, S, B};
lookup(Key,Value, {Key1, _, Smaller, Bigger}) ->
    if
        Key < Key1 -> lookup(Key,Value,Smaller);
        Key > Key1 -> lookup(Key,Value,Bigger)
    end.

%Вставка ключа в дерево
insert(Key, Value, {nil, nil, nil, nil}) ->
     E = new(),
     {Key, Value, E, E};
insert(Key, Value, {K, _, S, B}) when Key == K -> {Key, Value, S, B};
insert(Key, Value, {K, V, S, B}) when Key < K ->
     T = insert(Key, Value, S),
     {K, V, T, B};
insert(Key, Value, {K, V, S, B}) when Key > K ->
     T = insert(Key, Value, B),
     {K, V, S, T}.

%Удаление элемента из дерева
delete(_,{nil, 0, nil, nil}) -> {nil, 0, nil, nil};
delete(Key, {Key, 1, {nil, 0, nil, nil}, {nil, 0, nil, nil}}) -> {nil, 0, nil, nil};
delete(Key,{Key, _, {nil, 0, nil, nil}, B}) -> B;
delete(Key, {Key, _, S, {nil, 0, nil, nil}}) -> S.

%реализация функций теста
from_list([]) -> new();
from_list(Arg) -> list(Arg, new()).
list([], Tree) -> Tree;
list([{Arg1,Arg2}|Xs], Tree) ->
    T = insert(Arg1, Arg2, Tree),
    list(Xs, T).

to_list({nil, nil, nil, nil}) -> [];
to_list(Tree) -> list2(Tree, []).
list2({nil, nil, nil, nil}, Arg) -> Arg;
list2({Key, Value, {nil, nil, nil, nil}, B}, Arg) -> list2(B, [{Key, Value}|Arg]);
list2({Key, Value, S, _}, Arg) -> list2(S, [{Key, Value}|Arg]).

fold(_Fun, Q, {nil, nil, nil, nil}) -> Q;
fold(Fun, Q, {Key, Value, {nil, nil, nil, nil}, B}) -> Fun(Key, Value, fold(Fun, Q, B));
fold(Fun, Q, {Key, Value, S, _}) -> Fun(Key, Value, fold(Fun, Q, S)).

filter(_, {nil, nil, nil, nil}) -> {nil, nil, nil, nil};
filter(Fun, Tree) -> filter(Fun, Tree, new()).
filter(_Fun,{nil, nil, nil, nil}, Tree2) -> Tree2;
filter(Fun, {Key, Value, {nil, nil, nil, nil}, B}, Tree2) ->
                case Fun(Key, Value) of
                   true-> T = insert(Key, Value, Tree2),filter(Fun, B, T);
                   false -> filter(Fun, B, Tree2)
                end;
filter(Fun, {Key, Value, S, _}, Tree2) ->
                case Fun(Key, Value) of
                   true-> T = insert(Key, Value, Tree2),filter(Fun, S, T);
                   false -> filter(Fun, S, Tree2)
                end.