Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- -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)}.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement