From 5a9cdd3cc89507d4d74f8bded56ce5e037b3b56e Mon Sep 17 00:00:00 2001 From: Trygve Laugstøl Date: Fri, 23 Feb 2024 07:08:18 +0100 Subject: wip --- learn-you-some-erlang/tree.erl | 43 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+) create mode 100644 learn-you-some-erlang/tree.erl (limited to 'learn-you-some-erlang/tree.erl') diff --git a/learn-you-some-erlang/tree.erl b/learn-you-some-erlang/tree.erl new file mode 100644 index 0000000..3cda7c3 --- /dev/null +++ b/learn-you-some-erlang/tree.erl @@ -0,0 +1,43 @@ +-module(tree). +-export([empty/0, insert/3, lookup/2, has_value/2]). + +empty() -> {node, 'nil'}. + +insert(Key, Val, {node, 'nil'}) -> + {node, {Key, Val, {node, 'nil'}, {node, 'nil'}}}; +insert(NewKey, NewVal, {node, {Key, Val, Smaller, Larger}}) when NewKey < Key -> + {node, {Key, Val, insert(NewKey, NewVal, Smaller), Larger}}; +insert(NewKey, NewVal, {node, {Key, Val, Smaller, Larger}}) when NewKey > Key -> + {node, {Key, Val, Smaller, insert(NewKey, NewVal, Larger)}}; +insert(Key, Val, {node, {Key, _, Smaller, Larger}}) -> + {node, {Key, Val, Smaller, Larger}}. + +lookup(_, {node, 'nil'}) -> + undefined; +lookup(Key, {node, {Key, Val, _, _}}) -> + {ok, Val}; +lookup(Key, {node, {NodeKey, _, Smaller, _}}) when Key < NodeKey -> + lookup(Key, Smaller); +lookup(Key, {node, {_, _, _, Larger}}) -> + lookup(Key, Larger). + +%%--------------------------------------------------------- +%% The code after this comment is added in the errors and +%% exceptions chapter. Ignore it if you're still reading +%% the chapter about recursion. +%%--------------------------------------------------------- + +has_value(Val, Tree) -> + try has_value1(Val, Tree) of + _ -> false + catch + true -> true + end. + +has_value1(_, {node, 'nil'}) -> + false; +has_value1(Val, {node, {_, Val, _, _}}) -> + throw(true); +has_value1(Val, {node, {_, _, Left, Right}}) -> + has_value1(Val, Left), + has_value1(Val, Right). -- cgit v1.2.3