%-*-Mode:erlang;coding:utf-8;tab-width:4;c-basic-offset:4;indent-tabs-mode:()-*- % ex: set ft=erlang fenc=utf-8 sts=4 ts=4 sw=4 et nomod: %%% %%%------------------------------------------------------------------------ %%% @doc %%% ==A trie data structure implementation.== %%% The trie (i.e., from "retrieval") data structure was invented by %%% Edward Fredkin (it is a form of radix sort). The implementation stores %%% string suffixes as a list because it is a PATRICIA trie %%% (PATRICIA - Practical Algorithm to Retrieve Information %%% Coded in Alphanumeric, D.R.Morrison (1968)). %%% %%% This Erlang trie implementation uses string (list of integers) keys and %%% is able to get performance close to the process dictionary when doing key %%% lookups (find or fetch, see [http://okeuday.livejournal.com/16941.html]). %%% Utilizing this trie, it is possible to avoid generating dynamic atoms %%% in various contexts. Also, an added benefit to using this trie is that %%% the traversals preserve alphabetical ordering. %%% @end %%% %%% MIT License %%% %%% Copyright (c) 2010-2017 Michael Truog %%% %%% Permission is hereby granted, free of charge, to any person obtaining a %%% copy of this software and associated documentation files (the "Software"), %%% to deal in the Software without restriction, including without limitation %%% the rights to use, copy, modify, merge, publish, distribute, sublicense, %%% and/or sell copies of the Software, and to permit persons to whom the %%% Software is furnished to do so, subject to the following conditions: %%% %%% The above copyright notice and this permission notice shall be included in %%% all copies or substantial portions of the Software. %%% %%% THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR %%% IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, %%% FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE %%% AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER %%% LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING %%% FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER %%% DEALINGS IN THE SOFTWARE. %%% %%% @author Michael Truog %%% @copyright 2010-2017 Michael Truog %%% @version 1.7.1 {@date} {@time} %%%------------------------------------------------------------------------ -module(trie). -author('mjtruog [at] gmail (dot) com'). %% external interface -export([append/3, append_list/3, erase/2, erase_similar/2, fetch/2, fetch_keys/1, fetch_keys_similar/2, filter/2, find/2, find_match/2, find_prefix/2, find_prefixes/2, find_prefix_longest/2, find_similar/2, fold/3, foldl/3, foldr/3, fold_match/4, fold_similar/4, foldl_similar/4, foldr_similar/4, foreach/2, from_list/1, is_key/2, is_pattern/1, is_prefix/2, is_prefixed/2, is_prefixed/3, iter/2, itera/3, map/2, merge/3, new/0, new/1, pattern_parse/2, pattern_parse/3, pattern_suffix/2, prefix/3, size/1, store/2, store/3, take/2, to_list/1, to_list_similar/2, update/3, update/4, update_counter/3, test/0]). -define(MODE_LIST, true). -include("trie.hrl"). %%%------------------------------------------------------------------------ %%% External interface functions %%%------------------------------------------------------------------------ %%------------------------------------------------------------------------- %% @doc %% ===Find a match with patterns held within a trie.=== %% All patterns held within the trie use a wildcard character "*" to represent %% a regex of ".+". "**" within the trie will result in undefined behavior %% (the pattern is malformed). The function will search for the most specific %% match possible, given the input string and the trie contents. The input %% string must not contain wildcard characters, otherwise badarg is thrown. %% If you instead want to supply a pattern string to match the contents of %% the trie, see fold_match/4. %% @end %%------------------------------------------------------------------------- -spec find_match(string(), trie()) -> {ok, any(), any()} | 'error'. find_match(_, []) -> error; find_match(Match, Node) -> find_match_node(Match, [], Node). find_match_node([$* | _], _, _) -> erlang:exit(badarg); find_match_node([H | T] = Match, Key, {I0, I1, Data} = Node) when is_integer(H) -> Result = if H < I0; H > I1 -> error; true -> {ChildNode, Value} = erlang:element(H - I0 + 1, Data), if T =:= [] -> if is_tuple(ChildNode); ChildNode =:= [] -> if Value =:= error -> error; true -> {ok, lists:reverse([H | Key]), Value} end; true -> error end; true -> if is_tuple(ChildNode) -> find_match_node(T, [H | Key], ChildNode); Value =:= error -> error; true -> case wildcard_match_lists(ChildNode, T) of true -> {ok, lists:reverse([H | Key], ChildNode), Value}; false -> error end end end end, if Result =:= error -> find_match_element_1(Match, Key, Node); true -> Result end. find_match_element_1([_ | T] = Match, Key, {I0, I1, Data}) when $* >= I0, $* =< I1 -> {ChildNode, Value} = erlang:element($* - I0 + 1, Data), if is_tuple(ChildNode) -> find_match_element_N(T, [$* | Key], Value, ChildNode); Value =:= error -> error; true -> Suffix = [$* | ChildNode], case wildcard_match_lists(Suffix, Match) of true -> {ok, lists:reverse(Key, Suffix), Value}; false -> error end end; find_match_element_1(_, _, _) -> error. find_match_element_N([], _, error, _) -> error; find_match_element_N([], Key, WildValue, _) -> {ok, lists:reverse(Key), WildValue}; find_match_element_N([$* | _], _, _, _) -> erlang:exit(badarg); find_match_element_N([H | T], Key, WildValue, {I0, I1, _} = Node) when H < I0; H > I1 -> find_match_element_N(T, Key, WildValue, Node); find_match_element_N([H | T], Key, WildValue, {I0, _, Data} = Node) -> {ChildNode, Value} = erlang:element(H - I0 + 1, Data), if is_tuple(ChildNode) -> case find_match_node(T, [H | Key], ChildNode) of error -> find_match_element_N(T, Key, WildValue, Node); Result -> Result end; Value =:= error -> find_match_element_N(T, Key, WildValue, Node); true -> case wildcard_match_lists(ChildNode, T) of true -> {ok, lists:reverse([H | Key], ChildNode), Value}; false -> find_match_element_N(T, Key, WildValue, Node) end end. %%------------------------------------------------------------------------- %% @doc %% ===Find the first key/value pair in a trie where the key shares a common prefix.=== %% The first match is found based on alphabetical order. %% @end %%------------------------------------------------------------------------- -spec find_similar(Similar :: string(), Node :: trie()) -> {ok, string(), any()} | 'error'. find_similar([H | _], {I0, I1, _}) when H < I0; H > I1 -> error; find_similar(_, []) -> error; find_similar(Similar, Node) -> find_similar_entry(Similar, [], error, Node). find_similar_entry([H | _], Key, LastValue, {I0, I1, _} = Node) when H < I0; H > I1 -> if LastValue =:= error -> find_similar_element(Key, Node); true -> {ok, Key, LastValue} end; find_similar_entry([H] = Suffix, Key, _, {I0, _, Data} = Node) when is_integer(H) -> {ChildNode, Value} = erlang:element(H - I0 + 1, Data), if is_tuple(ChildNode) -> NewKey = Key ++ Suffix, if Value =:= error -> find_similar_element(NewKey, ChildNode); true -> {ok, NewKey, Value} end; Value =/= error, ChildNode =:= [] -> {ok, Key ++ Suffix, Value}; true -> find_similar_element(Key, Node) end; find_similar_entry([H | T] = Suffix, Key, _, {I0, _, Data} = Node) when is_integer(H) -> {ChildNode, Value} = erlang:element(H - I0 + 1, Data), if is_tuple(ChildNode) -> find_similar_entry(T, Key ++ [H], Value, ChildNode); Value =/= error, ChildNode == T -> {ok, Key ++ Suffix, Value}; true -> find_similar_element(Key, Node) end. find_similar_element(Key, Node) -> {trie_itera_done, Result} = itera(fun(NewKey, Value, _, _) -> {ok, NewKey, Value} end, {trie_itera_done, error}, Key, Node), Result. %%------------------------------------------------------------------------- %% @doc %% ===Fold a function over the keys within a trie that matches a pattern.=== %% Traverses in alphabetical order. Uses "*" as a wildcard character %% within the pattern (it acts like a ".+" regex, and "**" is forbidden). %% The trie keys must not contain wildcard characters, otherwise badarg %% is thrown. If you want to match a specific string without wildcards %% on trie values that contain wildcard characters, see find_match/2. %% @end %%------------------------------------------------------------------------- -spec fold_match(Match :: string(), F :: fun((string(), any(), any()) -> any()), A :: any(), Node :: trie()) -> any(). fold_match(_, _, A, []) -> A; fold_match(Match, F, A, Node) -> fold_match_node_1(Match, F, A, [], Node). fold_match_node_1([$*, $* | _], _, _, _, _) -> erlang:exit(badarg); fold_match_node_1([$* | _] = Match, F, A, Prefix, {I0, I1, Data}) -> fold_match_element_1(Match, F, A, 1, I1 - I0 + 2, I0 - 1, Prefix, [], Data); fold_match_node_1([H | _], _, A, _, {I0, I1, _}) when H < I0; H > I1 -> A; fold_match_node_1([H], F, A, Prefix, {I0, _, Data}) when is_integer(H) -> {ChildNode, Value} = erlang:element(H - I0 + 1, Data), if Value =/= error -> if is_tuple(ChildNode); ChildNode =:= [] -> F(lists:reverse([H | Prefix]), Value, A); true -> A end; true -> A end; fold_match_node_1([H | T], F, A, Prefix, {I0, _, Data}) when is_integer(H) -> {ChildNode, Value} = erlang:element(H - I0 + 1, Data), NewPrefix = [H | Prefix], if is_tuple(ChildNode) -> fold_match_node_1(T, F, A, NewPrefix, ChildNode); Value =/= error -> case wildcard_match_lists(T, ChildNode) of true -> F(lists:reverse(NewPrefix, ChildNode), Value, A); false -> A end; true -> A end. fold_match_element_1(_, _, A, N, N, _, _, _, _) -> A; fold_match_element_1(Match, F, A, I, N, Offset, Prefix, Mid, Data) when I + Offset =:= $* -> case erlang:element(I, Data) of {[], error} -> fold_match_element_1(Match, F, A, I + 1, N, Offset, Prefix, Mid, Data); _ -> erlang:exit(badarg) end; fold_match_element_1([$* | T] = Match, F, A, I, N, Offset, Prefix, Mid, Data) -> {Node, Value} = erlang:element(I, Data), case Node of {I0, I1, NextData} -> NewMid = [(Offset + I) | Mid], NewA = if T =:= [], Value =/= error -> F(lists:reverse(NewMid ++ Prefix), Value, A); true -> A end, fold_match_element_1(Match, F, fold_match_element_N(Match, F, NewA, 1, I1 - I0 + 2, I0 - 1, Prefix, NewMid, NextData), I + 1, N, Offset, Prefix, Mid, Data); _ -> NewA = if Value =/= error -> Suffix = lists:reverse([(Offset + I) | Mid], Node), case wildcard_match_lists(Match, Suffix) of true -> F(lists:reverse(Prefix, Suffix), Value, A); false -> A end; true -> A end, fold_match_element_1(Match, F, NewA, I + 1, N, Offset, Prefix, Mid, Data) end. fold_match_element_N(_, _, A, N, N, _, _, _, _) -> A; fold_match_element_N(Match, F, A, I, N, Offset, Prefix, Mid, Data) when I + Offset =:= $* -> case erlang:element(I, Data) of {[], error} -> fold_match_element_N(Match, F, A, I + 1, N, Offset, Prefix, Mid, Data); _ -> erlang:exit(badarg) end; fold_match_element_N([$*] = Match, F, A, I, N, Offset, Prefix, Mid, Data) -> {Node, Value} = erlang:element(I, Data), case Node of {I0, I1, NextData} -> NewMid = [(Offset + I) | Mid], NewA = if Value =/= error -> F(lists:reverse(NewMid ++ Prefix), Value, A); true -> A end, fold_match_element_N(Match, F, fold_match_element_N(Match, F, NewA, 1, I1 - I0 + 2, I0 - 1, Prefix, NewMid, NextData), I + 1, N, Offset, Prefix, Mid, Data); _ -> NewA = if Value =/= error -> F(lists:reverse([(Offset + I) | Mid] ++ Prefix, Node), Value, A); true -> A end, fold_match_element_N(Match, F, NewA, I + 1, N, Offset, Prefix, Mid, Data) end; fold_match_element_N([$* | T] = Match, F, A, I, N, Offset, Prefix, Mid, Data) -> {Node, Value} = erlang:element(I, Data), case T of [C | NewMatch] when C =:= Offset + I -> NewPrefix = [(Offset + I) | Mid] ++ Prefix, case NewMatch of [_ | _] when is_tuple(Node) -> fold_match_node_1(NewMatch, F, A, NewPrefix, Node); [_ | _] -> if Value =/= error -> case wildcard_match_lists(NewMatch, Node) of true -> F(lists:reverse(NewPrefix, Node), Value, A); false -> A end; true -> A end; [] -> case Node of [_ | _] -> A; _ when Value =/= error -> F(lists:reverse(NewPrefix), Value, A); _ -> A end end; _ -> case Node of {I0, I1, NextData} -> fold_match_element_N(Match, F, fold_match_element_N(Match, F, A, 1, I1 - I0 + 2, I0 - 1, Prefix, [(Offset + I) | Mid], NextData), I + 1, N, Offset, Prefix, Mid, Data); _ -> NewA = if Value =/= error -> Suffix = lists:reverse([(Offset + I) | Mid], Node), case wildcard_match_lists(Match, Suffix) of true -> F(lists:reverse(Prefix, Suffix), Value, A); false -> A end; true -> A end, fold_match_element_N(Match, F, NewA, I + 1, N, Offset, Prefix, Mid, Data) end end. %%------------------------------------------------------------------------- %% @doc %% ===Test to determine if a string is a pattern.=== %% "*" is the wildcard character (equivalent to the ".+" regex) and %% "**" is forbidden. %% @end %%------------------------------------------------------------------------- -spec is_pattern(Pattern :: string()) -> 'true' | 'false'. is_pattern(Pattern) -> is_pattern(Pattern, false). is_pattern([], Result) -> Result; is_pattern([$*, $* | _], _) -> erlang:exit(badarg); is_pattern([$* | Pattern], _) -> is_pattern(Pattern, true); is_pattern([_ | Pattern], Result) -> is_pattern(Pattern, Result). %%------------------------------------------------------------------------- %% @doc %% ===Determine if the prefix provided has existed within a trie.=== %% The function returns true if the string supplied is a prefix %% for a key that has previously been stored within the trie. %% If no values with the prefix matching key(s) were removed from the trie, %% then the prefix currently exists within the trie. %% @end %%------------------------------------------------------------------------- -spec is_prefix(string(), trie()) -> 'true' | 'false'. is_prefix([H | _], {I0, I1, _}) when H < I0; H > I1 -> false; is_prefix([H], {I0, _, Data}) when is_integer(H) -> case erlang:element(H - I0 + 1, Data) of {{_, _, _}, _} -> true; {_, error} -> false; {_, _} -> true end; is_prefix([H | T], {I0, _, Data}) when is_integer(H) -> case erlang:element(H - I0 + 1, Data) of {{_, _, _} = Node, _} -> is_prefix(T, Node); {_, error} -> false; {T, _} -> true; {L, _} -> lists:prefix(T, L) end; is_prefix(_, []) -> false. %%------------------------------------------------------------------------- %% @doc %% ===Determine if the provided string has a prefix within a trie.=== %% @end %%------------------------------------------------------------------------- -spec is_prefixed(string(), trie()) -> 'true' | 'false'. is_prefixed([H | _], {I0, I1, _}) when H < I0; H > I1 -> false; is_prefixed([H], {I0, _, Data}) when is_integer(H) -> case erlang:element(H - I0 + 1, Data) of {_, error} -> false; {{_, _, _}, _} -> true; {[], _} -> true; {[_ | _], _} -> false end; is_prefixed([H | T], {I0, _, Data}) when is_integer(H) -> case erlang:element(H - I0 + 1, Data) of {{_, _, _} = Node, error} -> is_prefixed(T, Node); {{_, _, _}, _} -> true; {_, error} -> false; {T, _} -> true; {L, _} -> lists:prefix(L, T) end; is_prefixed(_, []) -> false. %%------------------------------------------------------------------------- %% @doc %% ===Determine if the provided string has an acceptable prefix within a trie.=== %% The prefix within the trie must match at least 1 character that is not %% within the excluded list of characters. %% @end %%------------------------------------------------------------------------- -spec is_prefixed(string(), string(), trie()) -> 'true' | 'false'. is_prefixed(Key, Exclude, Node) -> is_prefixed_match(Key, false, Exclude, Node). is_prefixed_match([H | _], _, _, {I0, I1, _}) when H < I0; H > I1 -> false; is_prefixed_match([H], Matched, Exclude, {I0, _, Data}) when is_integer(H) -> case erlang:element(H - I0 + 1, Data) of {_, error} -> false; {{_, _, _}, _} -> Matched orelse (not lists:member(H, Exclude)); {[], _} -> Matched orelse (not lists:member(H, Exclude)); {[_ | _], _} -> false end; is_prefixed_match([H | T], Matched, Exclude, {I0, _, Data}) when is_integer(H) -> case erlang:element(H - I0 + 1, Data) of {{_, _, _} = Node, error} -> is_prefixed_match(T, Matched orelse (not lists:member(H, Exclude)), Exclude, Node); {{_, _, _} = Node, _} -> case (Matched orelse (not lists:member(H, Exclude))) of true -> true; false -> is_prefixed_match(T, false, Exclude, Node) end; {_, error} -> false; {L, _} -> is_prefixed_match_check(L, T, Matched orelse (not lists:member(H, Exclude)), Exclude) end; is_prefixed_match(_, _, _, []) -> false. is_prefixed_match_check([], _, Matched, _) -> Matched; is_prefixed_match_check([H | T1], [H | T2], Matched, Exclude) -> is_prefixed_match_check(T1, T2, Matched orelse (not lists:member(H, Exclude)), Exclude); is_prefixed_match_check(_, _, _, _) -> false. %%------------------------------------------------------------------------- %% @doc %% ===Iterate over a trie.=== %% Traverses in alphabetical order. %% @end %%------------------------------------------------------------------------- -spec iter(F :: fun((string(), any(), fun(() -> any())) -> any()), Node :: trie()) -> ok. iter(F, []) when is_function(F, 3) -> ok; iter(F, Node) when is_function(F, 3) -> iter(F, [], Node), ok. iter(F, Key, {I0, I1, Data}) -> iter_element(F, 1, I1 - I0 + 2, I0 - 1, Key, Data). iter_element(_, N, N, _, _, _) -> trie_iter_done; iter_element(F, I, N, Offset, Key, Data) -> {Node, Value} = erlang:element(I, Data), if is_list(Node) =:= false -> if Value =:= error -> iter(F, Key ++ [Offset + I], Node), iter_element(F, I + 1, N, Offset, Key, Data); true -> NewKey = Key ++ [Offset + I], Iter = fun() -> iter(F, NewKey, Node) end, case F(NewKey, Value, Iter) of trie_iter_done -> iter_element(F, I + 1, N, Offset, Key, Data); _ -> ok end end; true -> if Value =:= error -> iter_element(F, I + 1, N, Offset, Key, Data); true -> Iter = fun() -> iter_element(F, I + 1, N, Offset, Key, Data) end, F((Key ++ [Offset + I]) ++ Node, Value, Iter) end end. %%------------------------------------------------------------------------- %% @doc %% ===Iterate over a trie with an accumulator.=== %% Traverses in alphabetical order. %% @end %%------------------------------------------------------------------------- -spec itera(F :: fun((string(), any(), any(), fun((any()) -> any())) -> any()), A :: any(), Node :: trie()) -> any(). itera(F, A, []) when is_function(F, 4) -> A; itera(F, A, Node) when is_function(F, 4) -> {trie_itera_done, NewA} = itera(F, {trie_itera_done, A}, [], Node), NewA. itera(F, ReturnValue, Key, {I0, I1, Data}) -> itera_element(F, ReturnValue, 1, I1 - I0 + 2, I0 - 1, Key, Data). itera_element(_, {trie_itera_done, _} = ReturnValue, N, N, _, _, _) -> ReturnValue; itera_element(F, {trie_itera_done, A} = ReturnValue, I, N, Offset, Key, Data) -> {Node, Value} = erlang:element(I, Data), if is_list(Node) =:= false -> if Value =:= error -> itera_element(F, itera(F, ReturnValue, Key ++ [Offset + I], Node), I + 1, N, Offset, Key, Data); true -> NewKey = Key ++ [Offset + I], Iter = fun(NewA) -> itera(F, {trie_itera_done, NewA}, NewKey, Node) end, case F(NewKey, Value, A, Iter) of {trie_itera_done, _} = NewReturnValue -> itera_element(F, NewReturnValue, I + 1, N, Offset, Key, Data); Result -> {trie_itera_done, Result} end end; true -> if Value =:= error -> itera_element(F, ReturnValue, I + 1, N, Offset, Key, Data); true -> Iter = fun(NewA) -> itera_element(F, {trie_itera_done, NewA}, I + 1, N, Offset, Key, Data) end, case F((Key ++ [Offset + I]) ++ Node, Value, A, Iter) of {trie_itera_done, _} = NewReturnValue -> NewReturnValue; Result -> {trie_itera_done, Result} end end end. %%------------------------------------------------------------------------- %% @doc %% ===Parse a string based on the supplied wildcard pattern.=== %% "*" is the wildcard character (equivalent to the ".+" regex) and %% "**" is forbidden. %% @end %%------------------------------------------------------------------------- -spec pattern_parse(Pattern :: string(), L :: string()) -> list(string()) | 'error'. pattern_parse(Pattern, L) -> pattern_parse(Pattern, L, default). %%------------------------------------------------------------------------- %% @doc %% ===Parse a string based on the supplied wildcard pattern.=== %% "*" is the wildcard character (equivalent to the ".+" regex) and %% "**" is forbidden. %% @end %%------------------------------------------------------------------------- -spec pattern_parse(Pattern :: string(), L :: string(), Option :: default | with_suffix | expanded) -> list(string()) | % default {list(string()), string()} | % with_suffix list(string() | {exact, string()}) | % expanded 'error'. pattern_parse(Pattern, L, Option) when (Option =:= default) orelse (Option =:= with_suffix) orelse (Option =:= expanded) -> pattern_parse(Pattern, L, [], [], Option). pattern_parse_result(default, Parameters, _) -> lists:reverse(Parameters); pattern_parse_result(with_suffix, Parameters, Suffix) -> {lists:reverse(Parameters), lists:reverse(Suffix)}; pattern_parse_result(expanded, Parameters, Suffix) -> NewParameters = if Suffix /= [] -> [{exact, lists:reverse(Suffix)} | Parameters]; true -> Parameters end, lists:reverse(NewParameters). pattern_parse_element(_, [], _) -> error; pattern_parse_element(C, [C | T], Segment) -> {ok, T, lists:reverse(Segment)}; pattern_parse_element(_, [$* | _], _) -> erlang:exit(badarg); pattern_parse_element(C, [H | T], L) -> pattern_parse_element(C, T, [H | L]). pattern_parse_pattern(Pattern, C, L, Segment, Parsed, Option) -> case pattern_parse_element(C, L, Segment) of {ok, NewL, NewSegment} -> case pattern_parse(Pattern, NewL, [NewSegment | Parsed], [C], Option) of error -> pattern_parse_pattern(Pattern, C, NewL, [C | lists:reverse(NewSegment)], Parsed, Option); Success -> Success end; error -> error end. pattern_parse([], [], Parsed, Suffix, Option) -> pattern_parse_result(Option, Parsed, Suffix); pattern_parse([], [_ | _], _, _, _) -> error; pattern_parse([_ | _], [$* | _], _, _, _) -> erlang:exit(badarg); pattern_parse([$*], [_ | _] = L, Parsed, Suffix, Option) -> NewParsed = if Option =:= expanded, Suffix /= [] -> [{exact, lists:reverse(Suffix)} | Parsed]; true -> Parsed end, pattern_parse_result(Option, [L | NewParsed], []); pattern_parse([$*, $* | _], [_ | _], _, _, _) -> erlang:exit(badarg); pattern_parse([$*, C | Pattern], [H | T], Parsed, Suffix, Option) -> NewParsed = if Option =:= expanded, Suffix /= [] -> [{exact, lists:reverse(Suffix)} | Parsed]; true -> Parsed end, pattern_parse_pattern(Pattern, C, T, [H], NewParsed, Option); pattern_parse([C | Pattern], [C | L], Parsed, Suffix, Option) -> pattern_parse(Pattern, L, Parsed, [C | Suffix], Option); pattern_parse(_, _, _, _, _) -> error. %%------------------------------------------------------------------------- %% @doc %% ===Parse a string based on the supplied wildcard pattern to return only the suffix after the pattern.=== %% "*" is the wildcard character (equivalent to the ".+" regex) and %% "**" is forbidden. %% @end %%------------------------------------------------------------------------- -spec pattern_suffix(Pattern :: string(), L :: string()) -> string() | 'error'. pattern_suffix([], []) -> []; pattern_suffix([], [_ | _] = L) -> L; pattern_suffix([_ | _], [$* | _]) -> erlang:exit(badarg); pattern_suffix([$*], [_ | _]) -> []; pattern_suffix([$*, $* | _], [_ | _]) -> erlang:exit(badarg); pattern_suffix([$*, C | Pattern], [_ | T]) -> pattern_suffix_pattern(Pattern, C, T); pattern_suffix([C | Pattern], [C | L]) -> pattern_suffix(Pattern, L); pattern_suffix(_, _) -> error. pattern_suffix_element(_, []) -> error; pattern_suffix_element(C, [C | T]) -> {ok, T}; pattern_suffix_element(_, [$* | _]) -> erlang:exit(badarg); pattern_suffix_element(C, [_ | T]) -> pattern_suffix_element(C, T). pattern_suffix_pattern(Pattern, C, L) -> case pattern_suffix_element(C, L) of {ok, NewL} -> case pattern_suffix(Pattern, NewL) of error -> pattern_suffix_pattern(Pattern, C, NewL); Success -> Success end; error -> error end. %%------------------------------------------------------------------------- %% @private %% @doc %% ===Regression test.=== %% @end %%------------------------------------------------------------------------- test() -> {97,97,{{[],empty}}} = trie:new(["a"]), {97,97,{{"b",empty}}} = trie:new(["ab"]), {97,97,{{"bc",empty}}} = trie:new(["abc"]), {97,97,{{"b",empty}}} = trie:new(["ab"]), {97,97,{{{97,98,{{[],empty},{[],empty}}},error}}} = trie:new(["ab","aa"]), {97,97,{{{97,98,{{"c",empty},{"c",empty}}},error}}} = trie:new(["abc","aac"]), {97,97,{{{97,98,{{"c",2},{"c",1}}},error}}} = trie:new([{"abc", 1},{"aac", 2}]), {97,97,{{{97,98,{{"c",2},{"cdefghijklmnopqrstuvwxyz",1}}},error}}} = RootNode0 = trie:new([{"abcdefghijklmnopqrstuvwxyz", 1},{"aac", 2}]), {ok, 1} = trie:find("abcdefghijklmnopqrstuvwxyz", RootNode0), error = trie:find("abcdefghijklmnopqrstuvwxy", RootNode0), {ok, 1} = trie:find_prefix("abcdefghijklmnopqrstuvwxyz", RootNode0), prefix = trie:find_prefix("abcdefghijklmnopqrstuvwxy", RootNode0), error = trie:find_prefix("abcdefghijklmnopqrstuvwxyzX", RootNode0), prefix = trie:find_prefix("a", RootNode0), prefix = trie:find_prefix("aa", RootNode0), {ok, 2} = trie:find_prefix("aac", RootNode0), error = trie:find_prefix("aacX", RootNode0), {97,97,{{{97,98,{{{98,99,{{"cde",3},{[],2}}},error}, {"cdefghijklmnopqrstuvwxyz",1}}},error}}} = RootNode1 = trie:store("aabcde", 3, RootNode0), {97,97,{{{97,98,{{{98,99,{{"cde",13},{[],12}}},error}, {"cdefghijklmnopqrstuvwxyz",11}}},error}}} = map(fun(_, V) -> V + 10 end, RootNode1), {97,97,{{{97,98,{{{98,99,{{[],error},{[],error}}},error}, {"cdefghijklmnopqrstuvwxyz",1}}},error}}} = filter(fun(_, V) -> V =< 1 end, RootNode1), {97,97,{{{97,98,{{{98,99,{{[],error},{[],2}}},error}, {"cdefghijklmnopqrstuvwxyz",1}}},error}}} = filter(fun(_, V) -> V =< 2 end, RootNode1), ["aabcde", "aac", "abcdefghijklmnopqrstuvwxyz"] = trie:fetch_keys(RootNode1), [{"aabcde", 3}, {"aac", 2}, {"abcdefghijklmnopqrstuvwxyz", 1}] = trie:to_list(RootNode1), [{"aabcde", 3}, {"aac", 12}, {"abcdefghijklmnopqrstuvwxyz", 1}] = trie:to_list(trie:update("aac", fun(I) -> I + 10 end, RootNode1)), [{"aaa", 4}, {"aabcde", 3}, {"aac", 2}, {"abcdefghijklmnopqrstuvwxyz", 1}] = trie:to_list(trie:update("aaa", fun(I) -> I + 10 end, 4, RootNode1)), 6 = foldl(fun(_, I, A) -> I + A end, 0, RootNode1), [{"aabcde", 3},{"aac", 2},{"abcdefghijklmnopqrstuvwxyz", 1}] = foldr(fun(K, V, A) -> [{K,V} | A] end, [], RootNode1), [{"abcdefghijklmnopqrstuvwxyz", 1}, {"aac", 2}, {"aabcde", 3}] = foldl(fun(K, V, A) -> [{K,V} | A] end, [], RootNode1), error = trie:find("aabcde", RootNode0), {ok, 3} = trie:find("aabcde", RootNode1), RootNode2 = trie:erase("aac", RootNode0), {ok, 1} = trie:find("abcdefghijklmnopqrstuvwxyz", RootNode2), {97,98,{{{98,98,{{[],[2]}}},[1]},{"c",[3]}}} = RootNode3 = trie:new([{"a", [1]},{"ab", [2]},{"bc", [3]}]), {97,98,{{{98,98,{{[],[2]}}},[1,2]},{"c",[3]}}} = trie:append("a", 2, RootNode3), RootNode4 = trie:new([ {"ammmmmmm", 7}, {"aaaaaaaaaaa", 4}, {"aaa", 2}, {"ab", 0}, {"ab", 5}, {"aa", 1}, {"aba", 6}, {"aaaaaaaa", 3}]), {97,97, {{{97,109, {{{97,97, {{{97,97, {{{97,97, {{{97,97, {{{97,97, {{{97,97, {{{97,97, {{"aa",4}}}, 3}}}, error}}}, error}}}, error}}}, error}}}, 2}}}, 1}, {{97,97,{{[],6}}},5}, {[],error}, {[],error}, {[],error}, {[],error}, {[],error}, {[],error}, {[],error}, {[],error}, {[],error}, {[],error}, {"mmmmmm",7}}}, error}}} = RootNode4, [{"aa",1}, {"aaa",2}, {"aaaaaaaa",3}, {"aaaaaaaaaaa",4}, {"ab",5}, {"aba",6}, {"ammmmmmm",7}] = trie:to_list(trie:from_list(trie:to_list(RootNode4))), Liter = ["aa", "aaa", "aaaaaaaa", "aaaaaaaaaaa", "ab", "aba"], Fiter = fun(Key, _, Iter) -> case lists:member(Key, Liter) of true -> Iter(); false -> done end end, Fitera = fun (_, _, [], _) -> done; (Key, _, [Key | T], Iter) -> Iter(T) end, ok = trie:iter(Fiter, RootNode4), done = trie:itera(Fitera, Liter, RootNode4), % trie:map happens to go through in reverse order ["aa", "aaa", "aaaaaaaa", "aaaaaaaaaaa", "ab", "aba", "ammmmmmm"] = trie:fetch_keys(RootNode4), ["aa", "aaa", "aaaaaaaa", "aaaaaaaaaaa", "ab", "aba", "ammmmmmm"] = trie:foldr(fun(Key, _, L) -> [Key | L] end, [], RootNode4), ["ammmmmmm", "aba", "ab", "aaaaaaaaaaa", "aaaaaaaa", "aaa", "aa"] = trie:foldl(fun(Key, _, L) -> [Key | L] end, [], RootNode4), RootNode5 = trie:store("a", 0, trie:store("aaaa", 2.5, RootNode4)), {ok, 2.5} = trie:find("aaaa", RootNode5), error = trie:find("aaaa", RootNode4), {ok, 2.5} = trie:find_prefix("aaaa", RootNode5), prefix = trie:find_prefix("aaaa", RootNode4), [] = trie:find_prefixes("z", RootNode4), [{"aa", 1}] = trie:find_prefixes("aa", RootNode4), [{"aa", 1}, {"aaa",2}] = trie:find_prefixes("aaaa", RootNode4), [{"ab",5}] = trie:find_prefixes("absolut", RootNode4), [{"ab",5}, {"aba", 6}] = trie:find_prefixes("aba", RootNode4), [] = trie:find_prefixes("bar", RootNode4), [{"aa",1}, {"aaa",2}, {"aaaaaaaa",3}, {"aaaaaaaaaaa",4} ] = trie:find_prefixes("aaaaaaaaaaaaaaaaaaaaaddddddaa", RootNode4), error = trie:find_prefix_longest("a", RootNode4), {ok, "aa", 1} = trie:find_prefix_longest("aa", RootNode4), {ok, "aaa", 2} = trie:find_prefix_longest("aaaa", RootNode4), {ok, "ab", 5} = trie:find_prefix_longest("absolut", RootNode4), {ok, "aba", 6} = trie:find_prefix_longest("aba", RootNode4), {ok, "aaaaaaaa", 3} = trie:find_prefix_longest("aaaaaaaaa", RootNode4), error = trie:find_prefix_longest("bar", RootNode4), {ok, "aaaaaaaaaaa", 4} = trie:find_prefix_longest("aaaaaaaaaaaaaaaaaaaaaddddddaa", RootNode4), 2.5 = trie:fetch("aaaa", RootNode5), {'EXIT', {if_clause, _}} = (catch trie:fetch("aaaa", RootNode4)), RootNode4 = trie:erase("a", trie:erase("aaaa", RootNode5)), {2.5, RootNodePre4} = trie:take("aaaa", RootNode5), {0, RootNode4} = trie:take("a", RootNodePre4), error = trie:take("a", RootNode4), true = trie:is_key("aaaa", RootNode5), false = trie:is_key("aaaa", RootNode4), ["aa", "aaa", "aaaaaaaa", "aaaaaaaaaaa"] = trie:fetch_keys_similar("aa", RootNode4), ["aaa", "aaaaaaaa", "aaaaaaaaaaa"] = trie:fetch_keys_similar("aaac", RootNode4), ["ab", "aba"] = trie:fetch_keys_similar("abba", RootNode4), ["aa", "aaa", "aaaaaaaa", "aaaaaaaaaaa", "ab", "aba", "ammmmmmm"] = trie:fetch_keys_similar("a", RootNode4), [] = trie:fetch_keys_similar("b", RootNode4), {ok, "aa", 1} = trie:find_similar("aa", RootNode4), {ok, "aaa", 2} = trie:find_similar("aaac", RootNode4), {ok, "aaaaaaaa", 3} = trie:find_similar("aaaa", RootNode4), {ok, "ab", 5} = trie:find_similar("abba", RootNode4), {ok, "aa", 1} = trie:find_similar("a", RootNode4), true = trie:is_prefixed("abacus", RootNode4), false = trie:is_prefixed("ac", RootNode4), false = trie:is_prefixed("abacus", "ab", RootNode4), true = trie:foldl(fun(K, _, L) -> [K | L] end, [], RootNode4) == trie:fold_match("*", fun(K, _, L) -> [K | L] end, [], RootNode4), ["aaa" ] = trie:fold_match("*aa", fun(K, _, L) -> [K | L] end, [], RootNode4), ["aaaaaaaaaaa", "aaaaaaaa", "aaa" ] = trie:fold_match("aa*", fun(K, _, L) -> [K | L] end, [], RootNode4), ["aba" ] = trie:fold_match("ab*", fun(K, _, L) -> [K | L] end, [], RootNode4), ["ammmmmmm" ] = trie:fold_match("am*", fun(K, _, L) -> [K | L] end, [], RootNode4), ["aba", "aaa" ] = trie:fold_match("a*a", fun(K, _, L) -> [K | L] end, [], RootNode4), {'EXIT', badarg} = (catch trie:fold_match("a**a", fun(K, _, L) -> [K | L] end, [], RootNode4)), RootNode6 = trie:new([ {"*", 1}, {"aa*", 2}, {"aa*b", 3}, {"aa*a*", 4}, {"aaaaa", 5}]), {ok,"aa*",2} = trie:find_match("aaaa", RootNode6), {ok,"aaaaa",5} = trie:find_match("aaaaa", RootNode6), {ok,"*",1} = trie:find_match("aa", RootNode6), {ok,"aa*",2} = trie:find_match("aab", RootNode6), {ok,"aa*b",3} = trie:find_match("aabb", RootNode6), {ok,"aa*a*",4} = trie:find_match("aabab", RootNode6), {ok,"aa*a*",4} = trie:find_match("aababb", RootNode6), {ok,"aa*a*",4} = trie:find_match("aabbab", RootNode6), {ok,"aa*a*",4} = trie:find_match("aabbabb", RootNode6), {'EXIT',badarg} = (catch trie:find_match("aa*", RootNode6)), {'EXIT',badarg} = (catch trie:find_match("aaaa*", RootNode6)), {'EXIT',badarg} = (catch trie:find_match("aaaaa*", RootNode6)), ["aa"] = trie:pattern_parse("aa*", "aaaa"), ["b"] = trie:pattern_parse("aa*", "aab"), ["b"] = trie:pattern_parse("aa*b", "aabb"), {["b"], "b"} = trie:pattern_parse("aa*b", "aabb", with_suffix), ["b", "b"] = trie:pattern_parse("aa*a*", "aabab"), {["b", "b"], ""} = trie:pattern_parse("aa*a*", "aabab", with_suffix), ["b", "bb"] = trie:pattern_parse("aa*a*", "aababb"), ["bb", "b"] = trie:pattern_parse("aa*a*", "aabbab"), ["bb", "bb"] = trie:pattern_parse("aa*a*", "aabbabb"), error = trie:pattern_parse("aa*a*", "aaabb"), ["file.name"] = trie:pattern_parse("*.txt", "file.name.txt"), ["//"] = trie:pattern_parse("*/", "///"), "/get" = trie:pattern_suffix("*.txt", "file.name.txt/get"), "/get" = trie:pattern_suffix("*/", "///get"), {ok, "/accounting/balances/fred", empty} = trie:find_match("/accounting/balances/fred", trie:new(["/accounting/balances/*", "/accounting/balances/fred"])), {ok, "/permissions/fred/accounts/*", empty} = trie:find_match("/permissions/fred/accounts/add", trie:new(["/permissions/*/accounts/*", "/permissions/fred/accounts/*", "/permissions/*/accounts/add", "/permissions/fred/accounts/remove"])), {ok,"*//get",empty} = trie:find_match("///get", trie:new(["*//get"])), {ok,"*/",empty} = trie:find_match("///", trie:new(["*/"])), [] = trie:pattern_parse("aaabb", "aaabb"), {[], "aaabb"} = trie:pattern_parse("aaabb", "aaabb", with_suffix), [{exact, "a"}, "ddi", {exact, "t"}, "io", {exact, "n"}] = trie:pattern_parse("a*t*n", "addition", expanded), ["w",{exact,"atch"}] = trie:pattern_parse("*atch", "watch", expanded), [{exact,"is"},"t"] = trie:pattern_parse("is*", "ist", expanded), false = trie:is_pattern("abcdef"), true = trie:is_pattern("abc*d*ef"), {'EXIT',badarg} = (catch trie:is_pattern("abc**ef")), RootNode7 = trie:from_list([{"00", zeros}, {"11", ones}]), RootNode8 = trie:from_list([{"0", zero}, {"1", one}]), ["00"] = trie:fetch_keys_similar("02", RootNode7), [] = trie:fetch_keys_similar("2", RootNode7), ["11"] = trie:fetch_keys_similar("1", RootNode7), ["1"] = trie:fetch_keys_similar("1", RootNode8), ["0"] = trie:fetch_keys_similar("0", RootNode8), ["00"] = trie:fetch_keys_similar("0", RootNode7), RootNode9 = trie:new([{"abc", 123}]), {97,97,{{"bc",456}}} = trie:store("abc", 456, RootNode9), RootNode10 = trie:store("abc", value, trie:new()), RootNode11 = trie:store("abcd", value, RootNode10), true = trie:is_prefixed("abcdefghijk", RootNode10), true = trie:is_prefixed("abcdefghijk", RootNode11), true = trie:is_prefix("a", RootNode10), true = trie:is_prefix("a", RootNode11), true = trie:is_prefix("ab", RootNode10), true = trie:is_prefix("ab", RootNode11), true = trie:is_prefixed("abcdefghijk", "", RootNode10), true = trie:is_prefixed("abcdefghijk", "", RootNode11), false = trie:is_prefixed("abcdefghijk", "abc", RootNode10), true = trie:is_prefixed("abcdefghijk", "abc", RootNode11), true = trie:is_prefixed("abcdefghijk", "ac", RootNode10), true = trie:is_prefixed("abcdefghijk", "bc", RootNode10), true = trie:is_prefixed("abcdefghijk", "ab", RootNode10), ok. %%%------------------------------------------------------------------------ %%% Private functions %%%------------------------------------------------------------------------ %% make a new tuple with arity N and default D, then %% move tuple T into the new tuple at index I tuple_move(I, N, T, D) when is_integer(I), is_integer(N), is_tuple(T), (N - I + 1) >= tuple_size(T) -> tuple_move_i(I, 1, I + tuple_size(T), erlang:make_tuple(N, D), T). tuple_move_i(N1, _, N1, T1, _) -> T1; tuple_move_i(I1, I0, N1, T1, T0) -> tuple_move_i(I1 + 1, I0 + 1, N1, erlang:setelement(I1, T1, erlang:element(I0, T0)), T0). wildcard_match_lists_element(_, []) -> error; wildcard_match_lists_element(_, [$* | _]) -> erlang:exit(badarg); wildcard_match_lists_element(C, [C | L]) -> {ok, L}; wildcard_match_lists_element(C, [_ | L]) -> wildcard_match_lists_element(C, L). wildcard_match_lists_valid([], Result) -> Result; wildcard_match_lists_valid([$* | _], _) -> erlang:exit(badarg); wildcard_match_lists_valid([_ | L], Result) -> wildcard_match_lists_valid(L, Result). wildcard_match_lists_pattern(Pattern, C, L) -> case wildcard_match_lists_element(C, L) of {ok, NewL} -> case wildcard_match_lists(Pattern, NewL) of true -> true; false -> wildcard_match_lists_pattern(Pattern, C, NewL) end; error -> wildcard_match_lists_valid(L, false) end. wildcard_match_lists([], []) -> true; wildcard_match_lists([], [_ | _] = L) -> wildcard_match_lists_valid(L, false); wildcard_match_lists([_ | _], [$* | _]) -> erlang:exit(badarg); wildcard_match_lists([$*], [_ | L]) -> wildcard_match_lists_valid(L, true); wildcard_match_lists([$*, C | Pattern], [_ | L]) -> true = C =/= $*, wildcard_match_lists_pattern(Pattern, C, L); wildcard_match_lists([C | Pattern], [C | L]) -> wildcard_match_lists(Pattern, L); wildcard_match_lists(_, L) -> wildcard_match_lists_valid(L, false). -ifdef(TEST). -include_lib("eunit/include/eunit.hrl"). internal_test_() -> [ {"internal tests", ?_assertEqual(ok, test())} ]. %proper_test_() -> % {timeout, 600, [ % {"proper tests", ?_assert(trie_proper:qc_run(?MODULE))} % ]}. -endif.