%% @copyright 2013 Takeru Ohta %% %% @doc Splay Tree %% %% == Note == %% %% The keys of the entries in a tree are compared using the `==' operator %% (e.g., `1' and `1.0' are regarded as the same keys). %% %% == References == %% %% -module(splay_tree). -compile(inline). %%-------------------------------------------------------------------------------- %% Exported API %%-------------------------------------------------------------------------------- -export([new/0, store/3, find/2, find_largest/1, find_smallest/1, take_largest/1, take_smallest/1, find_lower_bound/2, find_upper_bound/2, lookup/2, get_value/3, erase/2, size/1, is_empty/1, update/4, update/3, filter/2, map/2, keys/1, values/1, foldl/3, foldr/3, foldl_while/3, foldr_while/3, from_list/1, to_list/1, split/2]). -export_type([tree/0, tree/2, key/0, value/0, update_fn/0, map_fn/0, fold_fn/0, fold_while_fn/0, pred_fn/0]). %%-------------------------------------------------------------------------------- %% Exported Types %%-------------------------------------------------------------------------------- -opaque tree() :: maybe_tree_node(). %% A splay tree. -opaque tree(_Key, _Vlaue) :: maybe_tree_node(). %% A splay tree. -type key() :: any(). %% The key of an entry in a splay tree. %% %% == Note == %% %% The keys are compared using the `==' operator %% (e.g., `1' and `1.0' are regarded as the same keys). -type value() :: any(). %% The value of an entry in a splay tree. -type update_fn() :: fun((value()) -> value()). %% A function for updating the value of an entry in a splay tree. -type map_fn() :: fun((key(), value()) -> value()). %% A function for mapping a splay tree to another one. -type pred_fn() :: fun((key(), value()) -> boolean()). %% A predicate function that returns `true' %% if the input entry (key and value) satisfies the expected condition. -type fold_fn() :: fun((key(), value(), AccIn :: term()) -> AccOut :: term()). %% A function that folds the entries in a splay tree. -type fold_while_fn() :: fun ((key(), value(), AccIn :: term()) -> {Continue :: boolean(), AccOut :: term()}). %% A function that folds the entries in a splay tree. %% %% If the value of `Continue' is `true', the folding will be broken and `AccOut' will be returned as the resulting value. %%-------------------------------------------------------------------------------- %% Internal Types %%-------------------------------------------------------------------------------- -type maybe_tree_node() :: tree_node() | nil. -type tree_node() :: inner_node() | leaf_node(). -type inner_node() :: {key(), value(), maybe_tree_node(), maybe_tree_node()}. -type leaf_node() :: {key(), value()}. -type direction() :: lft | rgt. % left | right %%-------------------------------------------------------------------------------- %% Exported Functions %%-------------------------------------------------------------------------------- %% @doc Makes an empty tree. %% %% == Example == %% %% ``` %% Tree = splay_tree:new(). %% true = splay_tree:is_empty(Tree). %% ''' -spec new() -> tree(). new() -> nil. %% @doc Returns the number of entries in the tree. %% %% Note that this function takes `N' steps (where `N' is the number of entries). %% %% == Example == %% %% ``` %% Tree0 = splay_tree:new(). %% 0 = splay_tree:size(Tree0). %% %% Tree1 = splay_tree:store(foo, bar, Tree1). %% 1 = splay_tree:size(Tree1). %% ''' -spec size(tree()) -> non_neg_integer(). size(Tree) -> foldl(fun (_, _, Count) -> Count+1 end, 0, Tree). %% @doc Returns `true' if the tree is empty, otherwise `false'. %% %% == Example == %% %% ``` %% Tree = splay_tree:new(). %% true = splay_tree:is_empty(Tree). %% ''' -spec is_empty(tree()) -> boolean(). is_empty(nil) -> true; is_empty(_) -> false. %% @doc Stores the entry in `Tree'. %% %% If there is an entry whose key is equal to `Key', its value will be replaced by `Value'. %% %% == Example == %% %% ``` %% Tree0 = splay_tree:new(). %% Tree1 = splay_tree:store(foo, bar, Tree0). %% Tree2 = splay_tree:store(111, 222, Tree1). %% %% [{111, 222}, {foo, bar}] = splay_tree:to_list(Tree2). %% ''' -spec store(key(), value(), tree()) -> tree(). store(Key, Value, Tree) -> case path_to_node(Key, Tree) of {nil, Path} -> splay(leaf(Key,Value), Path); {Node, Path} -> splay(val(Node,Value), Path) end. %% @doc Updates the value of an entry in the tree. %% %% If there is an entry whose key is equal to `Key', %% its value will be updated to `Fun(Key, CurrentValue)'. %% Otherwise a new entry whose value is `Initial' will be inserted to the tree. %% %% == Example == %% %% ``` %% Tree0 = splay_tree:from_list([{foo, bar}]). %% %% %% `foo' exists. %% Tree1 = splay_tree:update(foo, fun (bar) -> baz end, qux, Tree0). %% {{ok, baz}, _} = splay_tree:find(foo, Tree1). %% %% %% `111' does not exist. %% Tree2 = splay_tree:update(111, fun (_) -> 222 end, 333, Tree1). %% {{ok, 333}, _} = splay_tree:find(111, Tree2). %% ''' -spec update(key(), update_fn(), value(), tree()) -> tree(). update(Key, Fun, Initial, Tree) -> case path_to_node(Key, Tree) of {nil, Path} -> splay(leaf(Key,Initial), Path); {Node, Path} -> splay(val(Node,Fun(val(Node))), Path) end. %% @doc Updates the value of an entry in the tree. %% %% If there is an entry whose key is equal to `Key', %% its value will be updated to `Fun(Key, CurrentValue)'. %% Otherwise this function will return `error'. %% %% == Example == %% %% ``` %% Tree0 = splay_tree:from_list([{foo, bar}]). %% %% %% `foo' exists. %% {ok, Tree1} = splay_tree:update(foo, fun (bar) -> baz end, Tree0). %% {{ok, baz}, _} = splay_tree:find(foo, Tree1). %% %% %% `111' does not exist. %% error = splay_tree:update(111, fun (_) -> 222 end, Tree1). %% ''' -spec update(key(), update_fn(), tree()) -> {ok, tree()} | error. update(Key, Fun, Tree) -> case path_to_node(Key, Tree) of {nil, _Path} -> error; {Node, Path} -> {ok, splay(val(Node,Fun(val(Node))), Path)} end. %% @doc Finds the value of the entry whose key is equal to `Key' in the tree. %% %% Because splay tree is an amortized data structure, %% this function partially rebalance `Tree' and returns the updated tree. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{foo, bar}]). %% %% {{ok, bar}, _} = splay_tree:find(foo, Tree). %% {error, _} = splay_tree:find(baz, Tree). %% ''' -spec find(key(), tree()) -> {error, tree()} | {{ok, value()}, tree()}. find(Key, Tree) -> case path_to_node(Key, Tree) of {nil, Path} -> {error, splay(Path)}; {Node, Path} -> {{ok,val(Node)}, splay(Node,Path)} end. %% @doc Finds the entry which has the largest key in the tree. %% %% If `Tree' is empty, `{error, Tree}' will be returned. %% %% Because splay tree is an amortized data structure, %% this function partially rebalance `Tree' and returns the updated tree. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{333, 444}, {111, 222}]). %% {{ok, 333, 444}, _} = splay_tree:find_largest(Tree). %% ''' -spec find_largest(tree()) -> {error, tree()} | {{ok, key(), value()}, tree()}. find_largest(Tree) -> case move_largest_node_to_front(Tree) of nil -> {error, nil}; Node -> {{ok, key(Node), val(Node)}, Node} end. %% @doc Finds the entry which has the smallest key in the tree. %% %% If `Tree' is empty, `{error, Tree}' will be returned. %% %% Because splay tree is an amortized data structure, %% this function partially rebalance `Tree' and returns the updated tree. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{333, 444}, {111, 222}]). %% {{ok, 111, 222}, _} = splay_tree:find_smallest(Tree). %% ''' -spec find_smallest(tree()) -> {error, tree()} | {{ok, key(), value()}, tree()}. find_smallest(Tree) -> case move_smallest_node_to_front(Tree) of nil -> {error, nil}; Node -> {{ok, key(Node), val(Node)}, Node} end. %% @doc Takes the entry which has the largest key out from the tree. %% %% If `Tree' is empty, `{error, Tree}' will be returned. %% %% == Example == %% %% ``` %% Tree0 = splay_tree:from_list([{333, 444}, {111, 222}]). %% {{ok, 333, 444}, Tree1} = splay_tree:take_largest(Tree0). %% {{ok, 111, 222}, Tree2} = splay_tree:take_largest(Tree1). %% {error, Tree2} = splay_tree:take_largest(Tree2). %% ''' -spec take_largest(tree()) -> {error, tree()} | {{ok, key(), value()}, tree()}. take_largest(Tree) -> case move_largest_node_to_front(Tree) of nil -> {error, nil}; Node -> {{ok, key(Node), val(Node)}, lft(Node)} end. %% @doc Takes the entry which has the smallest key out from the tree. %% %% If `Tree' is empty, `{error, Tree}' will be returned. %% %% == Example == %% %% ``` %% Tree0 = splay_tree:from_list([{333, 444}, {111, 222}]). %% {{ok, 111, 222}, Tree1} = splay_tree:take_smallest(Tree0). %% {{ok, 333, 444}, Tree2} = splay_tree:take_smallest(Tree1). %% {error, Tree2} = splay_tree:take_smallest(Tree2). %% ''' -spec take_smallest(tree()) -> {error, tree()} | {{ok, key(), value()}, tree()}. take_smallest(Tree) -> case move_smallest_node_to_front(Tree) of nil -> {error, nil}; Node -> {{ok, key(Node), val(Node)}, rgt(Node)} end. %% @doc Lookups the value of the entry whose key is equal to `Key' in the tree. %% %% == Caution == %% %% Unlike {@link find/2}, this function does not rebalance `Tree'. %% So use of this function may cause performance degradation. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{foo, bar}]). %% %% {ok, bar} = splay_tree:lookup(foo, Tree). %% error = splay_tree:lookup(baz, Tree). %% ''' -spec lookup(key(), tree()) -> error | {ok, value()}. lookup(Key, Tree) -> case lookup_node(Key, Tree) of nil -> error; Node -> {ok, val(Node)} end. %% @doc Gets the value of the entry whose key is equal to `Key' in the tree. %% %% If there is no entry which has the key, %% this function will return `DefaultValue' instead. %% %% == Caution == %% %% Unlike {@link find/2}, this function does not rebalance `Tree'. %% So use of this function may cause performance degradation. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{foo, bar}]). %% %% bar = splay_tree:get_value(foo, Tree, qux). %% qux = splay_tree:get_value(baz, Tree, qux). %% ''' -spec get_value(key(), tree(), value()) -> value(). get_value(Key, Tree, DefaultValue) -> case lookup_node(Key, Tree) of nil -> DefaultValue; Node -> val(Node) end. %% @doc Erases the entry whose key is equal to `Key' from the tree. %% %% == Example == %% %% ``` %% Tree0 = splay_tree:from_list([{foo, bar}]). %% %% Tree1 = splay_tree:erase(foo, Tree0). %% error = splay_tree:lookup(foo, Tree1). %% %% Tree1 = splay_tree:erase(foo, Tree1). %% ''' -spec erase(key(), tree()) -> tree(). erase(Key, Tree) -> case path_to_node(Key, Tree) of {nil, Path} -> splay(Path); {Node, []} -> pop_front(Node); {Node, Path} -> case {pop_front(Node), hd(Path)} of {C, {lft,P}} -> splay(lft(P, C), tl(Path)); {C, {rgt,P}} -> splay(rgt(P, C), tl(Path)) end end. %% @doc Splits `Tree' at the position specified by `BorderKey'. %% %% `LeftTree' contains the entries whose key is smaller than `BorderKey'. %% `RightTree' contains the entries whose key is equal to or greater than `BorderKey'. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{1, a}, {2, b}, {3, c}]). %% {Left, Right} = splay_tree:split(2, Tree). %% %% [1] = splay_tree:keys(Left). %% [2, 3] = splay_tree:keys(Right). %% ''' -spec split(key(), tree()) -> {LeftTree :: tree(), RightTree :: tree()}. split(BorderKey, Tree) -> {_, Tree2} = find(BorderKey, Tree), case Tree2 of nil -> {nil, nil}; _ -> case key(Tree2) < BorderKey of true -> {rgt(Tree2, nil), rgt(Tree2)}; false -> {lft(Tree2), lft(Tree2, nil)} end end. %% @doc Finds the smallest entry among those whose key is equal to or greater than `Key'. %% %% Because splay tree is an amortized data structure, %% this function partially rebalance `Tree' and returns the updated tree. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{1, a}, {2, b}, {3, c}]). %% {{ok, 2, b}, _} = splay_tree:find_lower_bound(2, Tree). %% {{ok, 3, c}, _} = splay_tree:find_lower_bound(2.5, Tree). %% {error, _} = splay_tree:find_lower_bound(3.1, Tree). %% ''' -spec find_lower_bound(key(), tree()) -> {error, tree()} | {{ok, key(), value()}, tree()}. find_lower_bound(Key, Tree) -> {Left, Right} = split(Key, Tree), case Right of nil -> {error, Left}; {K, V, nil, _} -> {{ok, K, V}, lft(Right, Left)}; {K, V} -> {{ok, K, V}, lft(Right, Left)} end. %% @doc Finds the smallest entry among those whose key is greater than `Key'. %% %% Because splay tree is an amortized data structure, %% this function partially rebalance `Tree' and returns the updated tree. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{1, a}, {2, b}, {3, c}]). %% {{ok, 3, c}, _} = splay_tree:find_upper_bound(2, Tree). %% {{ok, 3, c}, _} = splay_tree:find_upper_bound(2.5, Tree). %% {error, _} = splay_tree:find_upper_bound(3.1, Tree). %% ''' -spec find_upper_bound(key(), tree()) -> {error, tree()} | {{ok, key(), value()}, tree()}. find_upper_bound(Key, Tree) -> {Left, Right} = split(Key, Tree), case Right of nil -> {error, Left}; {Key, Value} -> {error, store(Key, Value, Left)}; {Key, Value, nil, Right2} -> Left2 = store(Key, Value, Left), case find_smallest(Right2) of {error, _} -> {error, Left2}; {Ok, Right3} -> {Ok, lft(Right3, Left2)} end; {K, V, nil, _} -> {{ok, K, V}, lft(Right, Left)}; {K, V} -> {{ok, K, V}, lft(Right, Left)} end. %% @doc Converts `Tree` to an associated list. %% %% The resulting list is ordered by the key of the entries. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{2, b}, {3, c}, {1, a}]). %% [{1, a}, {2, b}, {3, c}] = splay_tree:to_list(Tree). %% ''' -spec to_list(tree()) -> [{key(), value()}]. to_list(Tree) -> foldr(fun (K, V, Acc) -> [{K,V}|Acc] end, [], Tree). %% @doc Returns the keys of the entries in `Tree'. %% %% The resulting list is in ascending order. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{2, b}, {3, c}, {1, a}]). %% [1, 2, 3] = splay_tree:keys(Tree). %% ''' -spec keys(tree()) -> [key()]. keys(Tree) -> foldr(fun (K, _, Acc) -> [K|Acc] end, [], Tree). %% @doc Returns the values of the entries in `Tree'. %% %% The resulting values are ordered by the associated keys. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{2, a}, {3, b}, {1, c}]). %% [c, a, b] = splay_tree:values(Tree). %% ''' -spec values(tree()) -> [value()]. values(Tree) -> foldr(fun (_, V, Acc) -> [V|Acc] end, [], Tree). %% @doc Makes a splay tree from the given associated list. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{2, b}, {1, a}]). %% {{ok, a}, _} = splay_tree:find(1, Tree). %% ''' -spec from_list([{key(), value()}]) -> tree(). from_list(List) -> lists:foldl(fun ({K, V}, Tree) -> store(K, V, Tree) end, new(), List). %% @doc Maps `Tree' to another splay tree. %% %% == Example == %% %% ``` %% Tree0 = splay_tree:from_list([{1, 2}, {3, 4}]). %% Tree1 = splay_tree:map(fun (K, V) -> K + V end, Tree0). %% [{1, 3}, {3, 7}] = splay_tree:to_list(Tree1). %% ''' -spec map(map_fn(), tree()) -> tree(). map(Fun, Tree) -> map_node(Fun, Tree). %% @doc Folds the entries in `Tree' by ascending order. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{a, 1}, {b, 2}]). %% [2, 1] = splay_tree:foldl(fun (_, V, Acc) -> [V | Acc] end, [], Tree). %% ''' -spec foldl(fold_fn(), term(), tree()) -> Result :: term(). foldl(Fun, Initial, Tree) -> foldl_node(Fun, Tree, Initial). %% @doc Folds the entries in `Tree' by descending order. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{a, 1}, {b, 2}]). %% [1, 2] = splay_tree:foldr(fun (_, V, Acc) -> [V | Acc] end, [], Tree). %% ''' -spec foldr(fold_fn(), term(), tree()) -> Result :: term(). foldr(Fun, Initial, Tree) -> foldr_node(Fun, Tree, Initial). %% @doc Folds the entries in `Tree' by ascending order. %% %% If `Fun' returns `{false, Result}', the folding will be broken immediately and %% `Result` will be returned as the resulting value. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{a, 1}, {b, 2}]). %% [1] = splay_tree:foldl_while(fun (_, V, Acc) -> {false, [V | Acc]} end, [], Tree). %% ''' -spec foldl_while(fold_while_fn(), term(), tree()) -> Result :: term(). foldl_while(Fun, Initial, Tree) -> try foldl_while_node(Fun, Tree, Initial) catch throw:{?MODULE, break, AccFinal} -> AccFinal end. %% @doc Folds the entries in `Tree' by descending order. %% %% If `Fun' returns `{false, Result}', the folding will be broken immediately and %% `Result` will be returned as the resulting value. %% %% == Example == %% %% ``` %% Tree = splay_tree:from_list([{a, 1}, {b, 2}]). %% [2] = splay_tree:foldr_while(fun (_, V, Acc) -> {false, [V | Acc]} end, [], Tree). %% ''' -spec foldr_while(fold_while_fn(), term(), tree()) -> term(). foldr_while(Fun, Initial, Tree) -> try foldr_while_node(Fun, Tree, Initial) catch throw:{?MODULE, break, AccFinal} -> AccFinal end. %% @doc Makes a splay tree that contains entries in `Tree' for which the invocation of `Pred' returns `true'. %% %% == Example == %% %% ``` %% Tree0 = splay_tree:from_list([{aaa, bbb}, {111, 222}]). %% Tree1 = splay_tree:filter(fun (K, _) -> is_atom(K) end, Tree0). %% [{aaa, bbb}] = splay_tree:to_list(Tree1). %% ''' -spec filter(pred_fn(), tree()) -> tree(). filter(Pred, Tree) -> foldl(fun (Key, Value, AccTree) -> case Pred(Key, Value) of false -> AccTree; true -> store(Key, Value, AccTree) end end, new(), Tree). %%-------------------------------------------------------------------------------- %% Internal Functions %%-------------------------------------------------------------------------------- -spec key(tree_node()) -> key(). key(Node) -> element(1, Node). -spec val(tree_node()) -> value(). val(Node) -> element(2, Node). -spec val(tree_node(), value()) -> tree_node(). val(Node, Value) -> setelement(2, Node, Value). -spec lft(tree_node()) -> maybe_tree_node(). lft({_, _, Lft, _}) -> Lft; lft({_, _}) -> nil. -spec lft(tree_node(), maybe_tree_node()) -> tree_node(). lft({Key, Val, _, nil}, nil) -> {Key, Val}; lft({Key, Val, _, Rgt}, Lft) -> {Key, Val, Lft, Rgt}; lft({Key, Val}, nil) -> {Key, Val}; lft({Key, Val}, Lft) -> {Key, Val, Lft, nil}. -spec rgt(tree_node()) -> maybe_tree_node(). rgt({_, _, _, Rgt}) -> Rgt; rgt({_, _}) -> nil. -spec rgt(tree_node(), maybe_tree_node()) -> tree_node(). rgt({Key, Val, nil, _}, nil) -> {Key, Val}; rgt({Key, Val, Lft, _}, Rgt) -> {Key, Val, Lft, Rgt}; rgt({Key, Val}, nil) -> {Key, Val}; rgt({Key, Val}, Rgt) -> {Key, Val, nil, Rgt}. -spec lft_rgt(tree_node(), maybe_tree_node(), maybe_tree_node()) -> tree_node(). lft_rgt(Node, Lft, Rgt) -> {key(Node), val(Node), Lft, Rgt}. -spec rgt_lft(tree_node(), maybe_tree_node(), maybe_tree_node()) -> tree_node(). rgt_lft(Node, Rgt, Lft) -> {key(Node), val(Node), Lft, Rgt}. -spec leaf(key(), value()) -> tree_node(). leaf(Key, Value) -> {Key, Value}. -spec pop_front(tree_node()) -> maybe_tree_node(). pop_front(Node) -> case move_largest_node_to_front(lft(Node)) of nil -> rgt(Node); Front -> rgt(Front, rgt(Node)) end. -spec move_largest_node_to_front(maybe_tree_node()) -> maybe_tree_node(). move_largest_node_to_front(nil) -> nil; move_largest_node_to_front(Node) -> move_largest_node_to_front(Node, []). -spec move_largest_node_to_front(tree_node(), [tree_node()]) -> tree_node(). move_largest_node_to_front(Node, Path) -> case rgt(Node) of nil -> splay(Node, Path); Rgt -> move_largest_node_to_front(Rgt, [{rgt, Node}|Path]) end. -spec move_smallest_node_to_front(maybe_tree_node()) -> maybe_tree_node(). move_smallest_node_to_front(nil) -> nil; move_smallest_node_to_front(Node) -> move_smallest_node_to_front(Node, []). -spec move_smallest_node_to_front(tree_node(), [tree_node()]) -> tree_node(). move_smallest_node_to_front(Node, Path) -> case lft(Node) of nil -> splay(Node, Path); Lft -> move_smallest_node_to_front(Lft, [{lft, Node}|Path]) end. -spec path_to_node(key(), maybe_tree_node()) -> {maybe_tree_node(), [{direction(),tree_node()}]}. path_to_node(Key, Root) -> path_to_node(Key, Root, []). -spec path_to_node(key(), maybe_tree_node(), [{direction(),tree_node()}]) -> {maybe_tree_node(), [{direction(),tree_node()}]}. path_to_node(_Key, nil, Path) -> {nil, Path}; path_to_node(Key, Node, Path) -> case key(Node) of K when Key < K -> path_to_node(Key, lft(Node), [{lft,Node}|Path]); K when Key > K -> path_to_node(Key, rgt(Node), [{rgt,Node}|Path]); _ -> {Node, Path} end. -spec lookup_node(key(), maybe_tree_node()) -> maybe_tree_node(). lookup_node(_Key, nil) -> nil; lookup_node(Key, Node) -> case key(Node) of K when Key < K -> lookup_node(Key, lft(Node)); K when Key > K -> lookup_node(Key, rgt(Node)); _ -> Node end. -spec splay([{direction(),tree_node()}]) -> maybe_tree_node(). splay([]) -> nil; splay([{_,Node}|Path]) -> splay(Node, Path). -spec splay(tree_node(), [{direction(),tree_node()}]) -> tree_node(). splay(X, []) -> X; splay(X, [{Dir, P}]) -> % zig case Dir of lft -> rgt(X, lft(P, rgt(X))); rgt -> lft(X, rgt(P, lft(X))) end; splay(X, [{Dir,P}, {Dir,G} | Path]) -> % zig-zig splay(case Dir of lft -> rgt(X, rgt_lft(P, lft(G, rgt(P)), rgt(X))); rgt -> lft(X, lft_rgt(P, rgt(G, lft(P)), lft(X))) end, Path); splay(X, [{Dir,P}, {_,G} | Path]) -> % zig-zag splay(case Dir of lft -> rgt_lft(X, lft(P, rgt(X)), rgt(G, lft(X))); rgt -> lft_rgt(X, rgt(P, lft(X)), lft(G, rgt(X))) end, Path). -spec map_node(map_fn(), maybe_tree_node()) -> maybe_tree_node(). map_node(_Fun, nil) -> nil; map_node(Fun, {Key, Val}) -> {Key, Fun(Key, Val)}; map_node(Fun, {Key, Val, Lft, Rgt}) -> {Key, Fun(Key, Val), map_node(Fun, Lft), map_node(Fun, Rgt)}. -spec foldl_node(fold_fn(), maybe_tree_node(), term()) -> term(). foldl_node(_Fun, nil, Acc) -> Acc; foldl_node(Fun, {Key, Val}, Acc) -> Fun(Key, Val, Acc); foldl_node(Fun, {Key, Val, Lft, Rgt}, Acc) -> foldl_node(Fun, Rgt, Fun(Key, Val, foldl_node(Fun, Lft, Acc))). -spec foldr_node(fold_fn(), maybe_tree_node(), term()) -> term(). foldr_node(_Fun, nil, Acc) -> Acc; foldr_node(Fun, {Key, Val}, Acc) -> Fun(Key, Val, Acc); foldr_node(Fun, {Key, Val, Lft, Rgt}, Acc) -> foldr_node(Fun, Lft, Fun(Key, Val, foldr_node(Fun, Rgt, Acc))). -define(MAYBE_BREAK(Result), case Result of {false, Value} -> throw({?MODULE, break, Value}); {true, Value} -> Value end). -spec foldl_while_node(fold_while_fn(), maybe_tree_node(), term()) -> term(). foldl_while_node(_Fun, nil, Acc) -> Acc; foldl_while_node(Fun, {Key, Val}, Acc) -> ?MAYBE_BREAK(Fun(Key, Val, Acc)); foldl_while_node(Fun, {Key, Val, Lft, Rgt}, Acc) -> foldl_while_node(Fun, Rgt, ?MAYBE_BREAK(Fun(Key, Val, foldl_while_node(Fun, Lft, Acc)))). -spec foldr_while_node(fold_while_fn(), maybe_tree_node(), term()) -> term(). foldr_while_node(_Fun, nil, Acc) -> Acc; foldr_while_node(Fun, {Key, Val}, Acc) -> ?MAYBE_BREAK(Fun(Key, Val, Acc)); foldr_while_node(Fun, {Key, Val, Lft, Rgt}, Acc) -> foldr_while_node(Fun, Lft, ?MAYBE_BREAK(Fun(Key, Val, foldr_while_node(Fun, Rgt, Acc)))).