-module(assoc).

-export([new/0, from_list/1, to_list/1, store/3, erase/2, fold/3, map/2, find/2, size/1, is_key/2, deletesp/1]).

%Бинарное дерево - дерево. Кортеж {Ключ, Значение, Меньшее_поддерево, Большее_поддерево}.
%В левом поддереве все ключи меньше Ключа, в правом — больше.
%Пустое дерево - {}.

%Новый пустой массив:
new() -> {};

%Список -> ассоциативный массив

from_list (Xs) ->
    from_list(Xs, new()).
from_list([], Btree) ->
    Btree;
from_list( [{K, V}| S], Btree) ->
    from_list (S, store (K, V, Btree).

%Ассоциативный массив -> список

to_list (Btree) ->
    to_list (Btree, []).
to_list (_, Xs) ->
    Xs;
to_list ({K, V, S, B}, Xs) ->
    to_list(S, to_list(B, [{K, V|Xs}]).

%Запись нового узла дерева

store(K, V, {}) ->
    {K, V, new(), new()};
store(Key, Value, {Key, _, S, B}) ->
    {K, Value, S, B};
store(Key, Value, {K, V, S, B}) when Key < K ->
    store(K, V, store(Key, Value, S), B);
store(Key, Value, {K, _, S, B}) when Key > K ->
    store(K, S, store(Key, Value, B)).

%Поиск узла по ключу
find(_, {}) ->
    error;
find(Key, {Key, V, _, _}) ->
    {ok, V};
find(Key, {Key1, _, S, B}) ->
    if
        Key < Key1 -> find(Key, S);
        Key > Key1 -> find(Key, B)
    end.

%Удаление узла
erase(Key, {}) ->
    new();
erase(Key, {Key, _, {}, {}}) ->
    new();
erase(Key, {Key, _, S, {}}) ->
    S;
erase(Key, {Key, _, {}, Bigger}) ->
    Bigger;
erase(Key, {Key, _, S, B}) ->
    {K2, V2, S2} = deletesp(S),
    {K2, V2, S2, B};
erase(Key, {K,V,S,B}) when Key < K ->
    {K, V, assoc:erase(Key, S), B};
erase(Key, {K,V,S,B}) when Key > K ->
    {K, V, S, assoc:erase(Key, B)}.

%При удалении узла в середине дерева возникает брешь, которую надо прикрыть
deletesp({K, V, {}, {}) ->
    {K, V, {}};
deletesp({K,V,S,{}}) ->
    {K, V, S};
deletesp({K, V, S, B}) ->
    {K2, V2, B2} = deletesp(B),
    {K2, V2, {K, V, S, B2}}.

%Размер ассоциативного массива
size({}) ->
    0;
size({_, _, S, B}) ->
    1 + assoc:size(B) + assoc:size(S).


%Проверка наличия элемента с указанным ключем в массиве
is_key(_, {}) ->
    false;
is_key(Key, {Key, _, _, _}) ->
    true;
is_key(Key, {K, _, S, _}) when Key < K ->
    is_key(Key, S);
is_key(Key, {_, _, _, B}) -> is_key(Key, B).

%Свертка
fold(_Fun, Z, []) -> Z;
fold(Fun, Z, {K, V, S, B}) ->
    fold(Fun, Z, to_list({K, V, S, B}));
fold(Fun, Z, [{S, B}|S])->
    Fun(K, V, fold(Fun, Z, S)).

%Функтор
map(_Fun, {}) -> {};
map(Fun, {K, V, S, B}) ->
    {K, Fun(K, V), map(Fun, S), map(Fun, B)}.