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

new()->{null}.

from_list(L) ->
    foldlist(fun ({K,V}, D) -> store(K, V, D) end, new(), L).
foldlist(F, Accu, [Hd|Tail]) -> foldlist(F, F(Hd, Accu), Tail);
foldlist(_, Accu, []) -> Accu.

to_list(D) -> to_list_fold(D,[]).
to_list_fold({null},List)-> List;
to_list_fold({{K,V},Left,Right},List) -> List++[{K,V}]++to_list(Left)++to_list(Right).

fold(F, Acc, D) -> fold_assoc(F, Acc, to_list(D)).
fold_assoc(_,Acc,[])->Acc;
fold_assoc(F,Acc,[{Hd,Tail}|T])-> fold_assoc(F,F(Hd,Tail,Acc),T).

filter(F, D) -> filter_assoc(F,to_list(D),[]).
filter_assoc(_,[],Acc)->from_list(Acc);
filter_assoc(F,[{K,V}|Tail],Acc) ->
    case F(K, V) of
    true -> filter_assoc(F, Tail, [{K,V}|Acc]);
    false -> filter_assoc(F, Tail, Acc)
    end.

map(F,D) -> map_assoc(F,to_list(D),[]).
map_assoc(_,[],Acc)->from_list(Acc);
map_assoc(F,[{K,V}|Tail],Acc)->map_assoc(F,Tail,[{K,F(K,V)}|Acc]).

erase(Key,D)->from_list(erase_assoc(Key,to_list(D))).
erase_assoc(Key, [{Key,_}|Tail]) -> Tail;
erase_assoc(Key, [Hd|Tail]) -> ([Hd|erase_assoc(Key, Tail)]);
erase_assoc(_, []) -> [].

find(_,{null})->error;
find(Key,{{K,V},_,_}) when Key==K ->{ok,V};
find(Key,{{K,_},_,Right}) when Key>K -> find(Key,Right);
find(Key,{{K,_},Left,_}) when Key<K -> find(Key,Left).

store(K,V,{null})-> {{K,V},{null},{null}};
store(K,V,{{Hd,Tail},Left,Right}) ->
    if K>Hd -> {{Hd,Tail},Left,store(K,V,Right)};
    K<Hd -> {{Hd,Tail},store(K,V,Left),Right};
    K==Hd -> {{Hd,V},Left,Right}
    end.

size(D) -> fold(fun (_,_,L) -> L+1 end,0,D).

is_key(Key,D) -> find(Key,D)/=error.