% Реализация описанного в тестах типа данных — отображения (Ассоциативного массива).

-module(assoc_tests).
-include_lib("eunit/include/eunit.hrl").
-export([new/0, insert/3, from_list/1, to_list/1, fold/3, map/2, find/2, store/3, size/1, is_key/2, filter/2, erase/2]).
new() -> {nil,nil,nil,nil}.


% Добавление нового элемента в ассоциативный массив
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}.


% Функции from_list() to_list() (преобразование)
from_list([]) -> new();
from_list(X) -> from_list(X, new()).

from_list([], Three) -> Three;
from_list([{Xa,Xb}|Xs], Three) ->   T = insert(Xa, Xb, Three),
from_list(Xs, T).

to_list({nil, nil, nil, nil}) -> [];
to_list(Three) -> to_list(Three, []).

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


% Функция fold (свертка)
fold(_F, Z, {nil, nil, nil, nil}) -> Z;
fold(F, Z, {Key, Value, {nil, nil, nil, nil}, B}) -> F(Key, Value, fold(F, Z, B));
fold(F, Z, {Key, Value, S, _}) -> F(Key, Value, fold(F, Z, S)).


% Функция Filter
filter(_F, {nil, nil, nil, nil}) -> {nil, nil, nil, nil};
filter(F, Three) -> filter(F, Three, new()).
filter(_F,{nil, nil, nil, nil}, FThree) -> FThree;
filter(F, {Key, Value, {nil, nil, nil, nil}, B}, FThree) -> case F(Key, Value) of
true-> FT = insert(Key, Value, FThree),
filter(F, B, FT);
_ -> filter(F, B, FThree)
end;

filter(F, {Key, Value, S, _}, FThree) -> case F(Key, Value) of
true-> FT = insert(Key, Value, FThree),
filter(F, S, FT);
_ -> filter(F, S, FThree)
end.


% Функция map
map(_F, {nil, nil, nil, nil}) -> {nil, nil, nil, nil};
map(F, Three) -> map(F, Three, new()).
map(_F, {nil, nil, nil, nil}, MThree) -> MThree;
map(F, {Key, Value, {nil, nil, nil, nil}, B}, MThree) -> MT = insert(Key, F(Key, Value), MThree),
map(F, B, MT);
map(F, {Key, Value, S, _}, MThree) -> MT = insert(Key, F(Key, Value), MThree),
map(F, S, MT).


% Функция erase (удаление)
erase(Key, Three) -> filter(fun(K, _) when Key == K -> false;
(_, _) -> true end, Three).


% Функция find (поиск)
find(_Key, {nil, nil, nil, nil}) -> error;
find(Key, {Key, V, _, _}) -> {ok, V};
find(Key, {K, _, S, _}) when Key < K -> find(Key, S);
find(Key, {K, _, _, B}) when Key > K -> find(Key, B).


% Функция store (восстановление)
store(Key, Value, Three) -> insert(Key, Value, Three).


% Функция size (размер АМ)
size({nil, nil, nil, nil}) -> 0;
size(Three) -> size(Three, 0).
size({nil, nil, nil, nil}, Acc) -> Acc;
size({_, _, {nil, nil, nil, nil}, B}, Acc) -> size(B, Acc+1);
size({_, _, S, _}, Acc) -> size(S, Acc+1).


% Функция is_key() (проверка элемента)
is_key(_Key, {nil, nil, nil, nil}) -> false;
is_key(Key, {Key, _, _, _}) -> true;
is_key(Key, {K, _, S, _}) when Key < K ->   is_key(Key, S);
is_key(Key, {K, _, _, B}) when Key > K ->   is_key(Key, B).