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

new()->[].

% Получение списка пар {Key,List} из хэш-дерева
to_list([])->[];
to_list(HTree)->to_list_elem(HTree, []).
to_list_elem([], List)->List;
to_list_elem({Key,Value,Left,Right,_}, List)->to_list_elem(Left, to_list_elem(Right, [{Key,Value}|List])).


% Получения хэш-дерева из списка пар {Key,Value}
from_list(List)->from_list(List,[]).
from_list([],HTree)->HTree;
from_list([{Key, Value} | Tl],HTree)->from_list(Tl,store(Key,Value,HTree)).


% Собирает все результаты применения F к каждой паре {Key,Value} в список
fold(_Fun, Z, []) -> Z;
fold(Fun, Z, {Key, Value, Left, Right, Hash}) -> fold(Fun, Z, to_list({Key, Value, Left, Right,Hash}));
fold(Fun, Z, [{Key, Value}|List])->Fun(Key, Value, fold(Fun, Z, List)).


% Проверяет, есть ли в хэш-дереве элемент с данным ключом
is_key(Key,HTree)->
    case find(Key,HTree) of
        {ok,_} -> true;
        _ -> false
    end.


% Собирает удаляет элементы не удовлетворяющие функции F
filter(_, [])-> [];
filter(F, {Key, Value, Left, Right, Hash})->
    case F(Key,Value) of
        true -> {Key, Value, filter(F,Left), filter(F, Right), Hash};
        _ -> filter(F,erase(Key,{Key, Value, Left, Right, Hash}))
    end.


% Производит отображение функции дерева по функции F
map(_,[])->[];
map(F,{Key, Value, Left, Right, Hash})->
    {Key, F(Key, Value),map(F, Left),map(F,Right),Hash}.


% Интерфейс для size, возвращает размерность хэш-дерева
size(Htree)->
    sizeof(to_list(Htree),0).

sizeof([],I)->I;
sizeof([{_,_}|Tl],I)->
    sizeof(Tl, incr(I,1)).

incr(X,Y)->X+Y.


% Интерфейс для get_elem, возвращает значение по ключу
find(Key,HTree)->
    get_elem(HTree,{Key,hash(Key)}).

get_elem([],_)->error;
get_elem({Key,Value, _,_,Hash},{Key,Hash})->
    {ok,Value};
get_elem({_,_, Left,_,Hash1},{_,Hash}=KH) when Hash1>=Hash->
    get_elem(Left,KH);
get_elem({_,_,_,Right,Hash1},{_,Hash}=KH) when Hash1<Hash->
    get_elem(Right,KH).


% Интерфейс для put_elem, вставляет в словарь элемент {Key, Value}
store(Key, Value, HTree)->
    put_elem(HTree, {Key, hash(Key), Value}).

put_elem({Key,_, Left,Right,Hash},{Key,Hash,NewValue})->
    {Key,NewValue, Left,Right,Hash};
put_elem({Key,Value, Left,Right,Hash1},{_,Hash,_}=KHV) when Hash1>=Hash->
    {Key,Value, put_elem(Left,KHV),Right,Hash1};
put_elem({Key,Value, Left,Right,Hash1},{_,Hash,_}=KHV) when Hash1<Hash->
    {Key,Value,Left,put_elem(Right,KHV),Hash1};
put_elem([],{Key,Hash,NewValue})->
    {Key,NewValue,[],[],Hash}.


% Интерфейс для del_h, удаляет элемент с указанным ключом
erase(Key,HTree)->
    del_h(HTree,{Key,hash(Key)}).

del_h([],_)->[];
del_h({Key,_, [],Right,Hash},{Key,Hash})->
    Right;
del_h({Key,_, Left,[],Hash},{Key,Hash})->
    Left;
del_h({Key,_, Left,Right,Hash},{Key,Hash})->
    {LKey,LValue, _,_,LHash} = rightest(Left),
    NLeft = del_h(Left,{LKey,LHash}),
    {LKey,LValue, NLeft,Right,LHash};
del_h({Key,Value, Left,Right,Hash1},{_,Hash}=KH) when Hash1>=Hash->
    {Key,Value,del_h(Left,KH),Right,Hash1};
del_h({Key,Value, Left,Right,Hash1},{_,Hash}=KH) when Hash1<Hash->
    {Key,Value,Left,del_h(Right,KH),Hash1}.


% Самый правый элемент поддерева
rightest([])->[];
rightest({_,_,_,[],_}=S)->S;
rightest({_,_,_,Right,_})->rightest(Right).


% Вычисляет хэш ключа
hash(S)->erlang:phash(S,10000).