trie

%-*-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-2018 Michael Truog <mjtruog at protonmail dot com>
%%%
%%% 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 <mjtruog at protonmail dot com>
%%% @copyright 2010-2018 Michael Truog
%%% @version 1.7.5 {@date} {@time}
%%%------------------------------------------------------------------------

-module(trie).
-author('mjtruog at protonmail 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_match2/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_pattern2/1,
         is_prefix/2,
         is_prefixed/2,
         is_prefixed/3,
         iter/2,
         itera/3,
         map/2,
         merge/3,
         new/0,
         new/1,
         pattern_fill/2,
         pattern_fill/4,
         pattern_parse/2,
         pattern_parse/3,
         pattern_suffix/2,
         pattern2_fill/2,
         pattern2_fill/4,
         pattern2_parse/2,
         pattern2_parse/3,
         pattern2_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 a badarg exit
%% exception will occur.  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([], _, _) ->
    error;

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_pattern_1(Match, Key, Node);
        true ->
            Result
    end.

find_match_pattern_1([_ | T] = Match, Key, {I0, I1, Data})
    when $* >= I0, $* =< I1 ->
    {ChildNode, Value} = erlang:element($* - I0 + 1, Data),
    if
        is_tuple(ChildNode) ->
            find_match_pattern_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_pattern_1(_, _, _) ->
    error.

find_match_pattern_N([], _, error, _) ->
    error;

find_match_pattern_N([], Key, WildValue, _) ->
    {ok, lists:reverse(Key), WildValue};

find_match_pattern_N([$* | _], _, _, _) ->
    erlang:exit(badarg);

find_match_pattern_N([H | T], Key, WildValue, {I0, I1, _} = Node)
    when H < I0; H > I1 ->
    find_match_pattern_N(T, Key, WildValue, Node);

find_match_pattern_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_pattern_N(T, Key, WildValue, Node);
                Result ->
                    Result
            end;
        Value =:= error ->
            find_match_pattern_N(T, Key, WildValue, Node);
        true ->
            case wildcard_match_lists(ChildNode, T) of
                true ->
                    {ok, lists:reverse([H | Key], ChildNode), Value};
                false ->
                    find_match_pattern_N(T, Key, WildValue, Node)
            end
    end.

%%-------------------------------------------------------------------------
%% @doc
%% ===Find a match with patterns (using 2 wildcard characters) held within a trie.===
%% All patterns held within the trie use the wildcard character "*" or "?"
%% to represent a regex of ".+".  "**", "??", "*?", or "?*" 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 a badarg exit exception will occur.
%% The "?" wildcard character consumes the shortest match to the next
%% character and must not be the the last character in the string
%% (the pattern would be malformed).
%% @end
%%-------------------------------------------------------------------------

-spec find_match2(string(), trie()) -> {ok, any(), any()} | 'error'.

find_match2(_, []) ->
    error;

find_match2(Match, Node) ->
    find_match2_node(Match, [], Node).

find_match2_node([], _, _) ->
    error;

find_match2_node([H | _], _, _)
    when H == $*; H == $? ->
    erlang:exit(badarg);

find_match2_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_match2_node(T, [H | Key], ChildNode);
                        Value =:= error ->
                            error;
                        true ->
                            case wildcard_match2_lists(ChildNode, T) of
                                true ->
                                    {ok, lists:reverse([H | Key],
                                                       ChildNode), Value};
                                false ->
                                    error
                            end
                    end
            end
    end,
    if
        Result =:= error ->
            ResultPattern0 = find_match2_pattern0_0(Match, Key, Node),
            if
                ResultPattern0 =:= error ->
                    find_match2_pattern1_1(Match, Key, Node);
                true ->
                    ResultPattern0
            end;
        true ->
            Result
    end.

find_match2_pattern0_0([H | T] = Match, Key, {I0, I1, Data})
    when $? >= I0, $? =< I1 ->
    {ChildNode, Value} = erlang:element($? - I0 + 1, Data),
    if
        is_tuple(ChildNode) ->
            find_match2_pattern0_1(T, H, [$? | Key], ChildNode);
        Value =:= error; ChildNode =:= [] ->
            error;
        true ->
            Suffix = [$? | ChildNode],
            case wildcard_match2_lists(Suffix, Match) of
                true ->
                    {ok, lists:reverse(Key, Suffix), Value};
                false ->
                    error
            end
    end;

find_match2_pattern0_0(_, _, _) ->
    error.

find_match2_pattern0_1(T, H, Key, {I0, I1, _} = Node)
    when H < I0; H > I1 ->
    find_match2_pattern0_N(T, undefined, Key, Node);

find_match2_pattern0_1(T, H, Key, {I0, _, Data} = Node) ->
    {_, Value} = erlang:element(H - I0 + 1, Data),
    if
        Value =:= error ->
            find_match2_pattern0_N(T, undefined, Key, Node);
        true ->
            find_match2_pattern0_N(T, H, Key, Node)
    end.

find_match2_pattern0_N([], _, _, _) ->
    error;

find_match2_pattern0_N([$? | _], _, _, _) ->
    erlang:exit(badarg);

find_match2_pattern0_N([H | T], H, Key, Node) ->
    find_match2_pattern0_N(T, H, Key, Node);

find_match2_pattern0_N([H | T], Ignore, Key, {I0, I1, _} = Node)
    when H < I0; H > I1 ->
    find_match2_pattern0_N(T, Ignore, Key, Node);

find_match2_pattern0_N([H | T], Ignore, Key, {I0, _, Data} = Node) ->
    {ChildNode, Value} = erlang:element(H - I0 + 1, Data),
    if
        is_tuple(ChildNode) ->
            find_match2_node(T, [H | Key], ChildNode);
        Value =:= error ->
            find_match2_pattern0_N(T, Ignore, Key, Node);
        true ->
            case wildcard_match2_lists(ChildNode, T) of
                true ->
                    {ok, lists:reverse([H | Key], ChildNode), Value};
                false ->
                    find_match2_pattern0_N(T, Ignore, Key, Node)
            end
    end.

find_match2_pattern1_1([_ | T] = Match, Key, {I0, I1, Data})
    when $* >= I0, $* =< I1 ->
    {ChildNode, Value} = erlang:element($* - I0 + 1, Data),
    if
        is_tuple(ChildNode) ->
            find_match2_pattern1_N(T, [$* | Key], Value, ChildNode);
        Value =:= error ->
            error;
        true ->
            Suffix = [$* | ChildNode],
            case wildcard_match2_lists(Suffix, Match) of
                true ->
                    {ok, lists:reverse(Key, Suffix), Value};
                false ->
                    error
            end
    end;

find_match2_pattern1_1(_, _, _) ->
    error.

find_match2_pattern1_N([], _, error, _) ->
    error;

find_match2_pattern1_N([], Key, WildValue, _) ->
    {ok, lists:reverse(Key), WildValue};

find_match2_pattern1_N([$* | _], _, _, _) ->
    erlang:exit(badarg);

find_match2_pattern1_N([H | T], Key, WildValue, {I0, I1, _} = Node)
    when H < I0; H > I1 ->
    find_match2_pattern1_N(T, Key, WildValue, Node);

find_match2_pattern1_N([H | T], Key, WildValue, {I0, _, Data} = Node) ->
    {ChildNode, Value} = erlang:element(H - I0 + 1, Data),
    if
        is_tuple(ChildNode) ->
            case find_match2_node(T, [H | Key], ChildNode) of
                error ->
                    find_match2_pattern1_N(T, Key, WildValue, Node);
                Result ->
                    Result
            end;
        Value =:= error ->
            find_match2_pattern1_N(T, Key, WildValue, Node);
        true ->
            case wildcard_match2_lists(ChildNode, T) of
                true ->
                    {ok, lists:reverse([H | Key], ChildNode), Value};
                false ->
                    find_match2_pattern1_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 a badarg
%% exit exception will occur. 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).
%% "**" 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
%% ===Test to determine if a string is a pattern (using 2 wildcard characters).===
%% "*" and "?" are wildcard characters (equivalent to the ".+" regex).
%% "**", "??", "*?" and "?*" are forbidden.  "?" must not be the last
%% character in the pattern.
%% @end
%%-------------------------------------------------------------------------

-spec is_pattern2(Pattern :: string()) -> 'true' | 'false'.

is_pattern2(Pattern) ->
    is_pattern2(Pattern, false).

is_pattern2([], Result) ->
    Result;

is_pattern2([$?], _) ->
    erlang:exit(badarg);

is_pattern2([C0, C1 | _], _)
    when C0 == $* orelse C0 == $?,
         C1 == $* orelse C1 == $? ->
    erlang:exit(badarg);

is_pattern2([H | Pattern], _)
    when H == $*; H == $? ->
    is_pattern2(Pattern, true);

is_pattern2([_ | Pattern], Result) ->
    is_pattern2(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
%% ===Fill wildcard characters in a string.===
%% The "*" wildcard character may be used consecutively by this function
%% to have parameters concatenated.
%% @end
%%-------------------------------------------------------------------------

-spec pattern_fill(FillPattern :: string(),
                   Parameters :: list(string())) ->
    {ok, string()} |
    {error, parameters_ignored | parameter_missing}.

pattern_fill(FillPattern, Parameters) ->
    pattern_fill_insert(FillPattern, Parameters, true).

%%-------------------------------------------------------------------------
%% @doc
%% ===Fill wildcard characters in a string.===
%% The "*" wildcard character may be used consecutively by this function
%% to have parameters concatenated.
%% @end
%%-------------------------------------------------------------------------

-spec pattern_fill(FillPattern :: string(),
                   Parameters :: list(string()),
                   ParametersSelected :: list(pos_integer()),
                   ParametersStrictMatching :: boolean()) ->
    {ok, string()} |
    {error,
     parameters_ignored | parameter_missing | parameters_selected_empty |
     {parameters_selected_ignored, list(pos_integer())} |
     {parameters_selected_missing, pos_integer()}}.

pattern_fill(FillPattern, Parameters, [], ParametersStrictMatching) ->
    pattern_fill_insert(FillPattern, Parameters, ParametersStrictMatching);
pattern_fill(FillPattern, Parameters, ParametersSelected,
             ParametersStrictMatching) ->
    pattern_fill_select(FillPattern, Parameters, ParametersSelected,
                        ParametersStrictMatching).

pattern_fill_strip([], NameOut) ->
    {ok, lists:reverse(NameOut)};
pattern_fill_strip([$* | FillPatternIn], NameOut) ->
    pattern_fill_strip(FillPatternIn, NameOut);
pattern_fill_strip([C | FillPatternIn], NameOut) ->
    pattern_fill_strip(FillPatternIn, [C | NameOut]).

pattern_fill_insert([], NameOut,
                    [], _) ->
    {ok, lists:reverse(NameOut)};
pattern_fill_insert([], NameOut,
                    [_ | _], ParametersStrictMatching) ->
    if
        ParametersStrictMatching =:= true ->
            {error, parameters_ignored};
        true ->
            {ok, lists:reverse(NameOut)}
    end;
pattern_fill_insert([$* | FillPatternIn], NameOut,
                    [], ParametersStrictMatching) ->
    if
        ParametersStrictMatching =:= true ->
            {error, parameter_missing};
        true ->
            pattern_fill_strip(FillPatternIn, NameOut)
    end;
pattern_fill_insert([$* | FillPatternIn], NameOut,
                    [Parameter | Parameters], ParametersStrictMatching) ->
    pattern_fill_insert(FillPatternIn, lists:reverse(Parameter) ++ NameOut,
                        Parameters, ParametersStrictMatching);
pattern_fill_insert([C | FillPatternIn], NameOut,
                    Parameters, ParametersStrictMatching) ->
    pattern_fill_insert(FillPatternIn, [C | NameOut],
                        Parameters, ParametersStrictMatching).

pattern_fill_insert(FillPatternIn, Parameters, ParametersStrictMatching) ->
    pattern_fill_insert(FillPatternIn, [],
                        Parameters, ParametersStrictMatching).

pattern_fill_select([], NameOut, _,
                    ParametersSelected, ParametersStrictMatching) ->
    if
        ParametersStrictMatching =:= true, ParametersSelected /= [] ->
            {error, {parameters_selected_ignored, ParametersSelected}};
        true ->
            {ok, lists:reverse(NameOut)}
    end;
pattern_fill_select([$* | FillPatternIn], NameOut, _,
                    [], ParametersStrictMatching) ->
    if
        ParametersStrictMatching =:= true ->
            {error, parameters_selected_empty};
        true ->
            pattern_fill_strip(FillPatternIn, NameOut)
    end;
pattern_fill_select([$* | FillPatternIn], NameOut, Parameters,
                    [I | ParametersSelected],
                    ParametersStrictMatching) ->
    try lists:nth(I, Parameters) of
        Parameter ->
            pattern_fill_select(FillPatternIn,
                                lists:reverse(Parameter) ++ NameOut,
                                Parameters, ParametersSelected,
                                ParametersStrictMatching)
    catch
        error:_ ->
            if
                ParametersStrictMatching =:= true ->
                    {error, {parameters_selected_missing, I}};
                true ->
                    pattern_fill_strip(FillPatternIn, NameOut)
            end
    end;
pattern_fill_select([C | FillPatternIn], NameOut, Parameters,
                    ParametersSelected, ParametersStrictMatching) ->
    pattern_fill_select(FillPatternIn, [C | NameOut], Parameters,
                        ParametersSelected, ParametersStrictMatching).

pattern_fill_select(FillPatternIn, Parameters,
                    ParametersSelected, ParametersStrictMatching) ->
    pattern_fill_select(FillPatternIn, [], Parameters,
                        ParametersSelected, ParametersStrictMatching).

%%-------------------------------------------------------------------------
%% @doc
%% ===Parse a string based on the supplied wildcard pattern.===
%% "*" is the wildcard character (equivalent to the ".+" regex).
%% "**" 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).
%% "**" 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).
%% "**" 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.

%%-------------------------------------------------------------------------
%% @doc
%% ===Fill wildcard characters in a string.===
%% The "*" and "?" wildcard characters may be used consecutively by this
%% function to have parameters concatenated (both are processed the same
%% way by this function).
%% @end
%%-------------------------------------------------------------------------

-spec pattern2_fill(FillPattern :: string(),
                    Parameters :: list(string())) ->
    {ok, string()} |
    {error, parameters_ignored | parameter_missing}.

pattern2_fill(FillPattern, Parameters) ->
    pattern2_fill_insert(FillPattern, Parameters, true).

%%-------------------------------------------------------------------------
%% @doc
%% ===Fill wildcard characters in a string.===
%% The "*" and "?" wildcard characters may be used consecutively by this
%% function to have parameters concatenated (both are processed the same
%% way by this function).
%% @end
%%-------------------------------------------------------------------------

-spec pattern2_fill(FillPattern :: string(),
                    Parameters :: list(string()),
                    ParametersSelected :: list(pos_integer()),
                    ParametersStrictMatching :: boolean()) ->
    {ok, string()} |
    {error,
     parameters_ignored | parameter_missing | parameters_selected_empty |
     {parameters_selected_ignored, list(pos_integer())} |
     {parameters_selected_missing, pos_integer()}}.

pattern2_fill(FillPattern, Parameters, [], ParametersStrictMatching) ->
    pattern2_fill_insert(FillPattern, Parameters, ParametersStrictMatching);
pattern2_fill(FillPattern, Parameters, ParametersSelected,
              ParametersStrictMatching) ->
    pattern2_fill_select(FillPattern, Parameters, ParametersSelected,
                         ParametersStrictMatching).

pattern2_fill_strip([], NameOut) ->
    {ok, lists:reverse(NameOut)};
pattern2_fill_strip([C | FillPatternIn], NameOut)
    when C == $*; C == $? ->
    pattern2_fill_strip(FillPatternIn, NameOut);
pattern2_fill_strip([C | FillPatternIn], NameOut) ->
    pattern2_fill_strip(FillPatternIn, [C | NameOut]).

pattern2_fill_insert([], NameOut,
                     [], _) ->
    {ok, lists:reverse(NameOut)};
pattern2_fill_insert([], NameOut,
                     [_ | _], ParametersStrictMatching) ->
    if
        ParametersStrictMatching =:= true ->
            {error, parameters_ignored};
        true ->
            {ok, lists:reverse(NameOut)}
    end;
pattern2_fill_insert([C | FillPatternIn], NameOut,
                     [], ParametersStrictMatching)
    when C == $*; C == $? ->
    if
        ParametersStrictMatching =:= true ->
            {error, parameter_missing};
        true ->
            pattern2_fill_strip(FillPatternIn, NameOut)
    end;
pattern2_fill_insert([C | FillPatternIn], NameOut,
                     [Parameter | Parameters], ParametersStrictMatching)
    when C == $*; C == $? ->
    pattern2_fill_insert(FillPatternIn, lists:reverse(Parameter) ++ NameOut,
                         Parameters, ParametersStrictMatching);
pattern2_fill_insert([C | FillPatternIn], NameOut,
                     Parameters, ParametersStrictMatching) ->
    pattern2_fill_insert(FillPatternIn, [C | NameOut],
                         Parameters, ParametersStrictMatching).

pattern2_fill_insert(FillPatternIn, Parameters, ParametersStrictMatching) ->
    pattern2_fill_insert(FillPatternIn, [],
                         Parameters, ParametersStrictMatching).

pattern2_fill_select([], NameOut, _,
                     ParametersSelected, ParametersStrictMatching) ->
    if
        ParametersStrictMatching =:= true, ParametersSelected /= [] ->
            {error, {parameters_selected_ignored, ParametersSelected}};
        true ->
            {ok, lists:reverse(NameOut)}
    end;
pattern2_fill_select([C | FillPatternIn], NameOut, _,
                     [], ParametersStrictMatching)
    when C == $*; C == $? ->
    if
        ParametersStrictMatching =:= true ->
            {error, parameters_selected_empty};
        true ->
            pattern2_fill_strip(FillPatternIn, NameOut)
    end;
pattern2_fill_select([C | FillPatternIn], NameOut, Parameters,
                     [I | ParametersSelected],
                     ParametersStrictMatching)
    when C == $*; C == $? ->
    try lists:nth(I, Parameters) of
        Parameter ->
            pattern2_fill_select(FillPatternIn,
                                 lists:reverse(Parameter) ++ NameOut,
                                 Parameters, ParametersSelected,
                                 ParametersStrictMatching)
    catch
        error:_ ->
            if
                ParametersStrictMatching =:= true ->
                    {error, {parameters_selected_missing, I}};
                true ->
                    pattern2_fill_strip(FillPatternIn, NameOut)
            end
    end;
pattern2_fill_select([C | FillPatternIn], NameOut, Parameters,
                     ParametersSelected, ParametersStrictMatching) ->
    pattern2_fill_select(FillPatternIn, [C | NameOut], Parameters,
                         ParametersSelected, ParametersStrictMatching).

pattern2_fill_select(FillPatternIn, Parameters,
                     ParametersSelected, ParametersStrictMatching) ->
    pattern2_fill_select(FillPatternIn, [], Parameters,
                         ParametersSelected, ParametersStrictMatching).

%%-------------------------------------------------------------------------
%% @doc
%% ===Parse a string based on the supplied wildcard pattern (using 2 wildcard characters).===
%% "*" and "?" are wildcard characters (equivalent to the ".+" regex).
%% "**", "??", "*?" and "?*" are forbidden.  "?" must not be the last
%% character in the pattern.
%% @end
%%-------------------------------------------------------------------------

-spec pattern2_parse(Pattern :: string(),
                    L :: string()) -> list(string()) | 'error'.

pattern2_parse(Pattern, L) ->
    pattern2_parse(Pattern, L, default).

%%-------------------------------------------------------------------------
%% @doc
%% ===Parse a string based on the supplied wildcard pattern (using 2 wildcard characters).===
%% "*" and "?" are wildcard characters (equivalent to the ".+" regex).
%% "**", "??", "*?" and "?*" are forbidden.  "?" must not be the last
%% character in the pattern.
%% @end
%%-------------------------------------------------------------------------

-spec pattern2_parse(Pattern :: string(),
                    L :: string(),
                    Option :: default | with_suffix | expanded) ->
    list(string()) |                       % default
    {list(string()), string()} |           % with_suffix
    list(string() | {exact, string()}) |   % expanded
    'error'.

pattern2_parse(Pattern, L, Option)
    when (Option =:= default) orelse
         (Option =:= with_suffix) orelse
         (Option =:= expanded) ->
    pattern2_parse(Pattern, L, [], [], Option).

pattern2_parse_result(default, Parameters, _) ->
    lists:reverse(Parameters);

pattern2_parse_result(with_suffix, Parameters, Suffix) ->
    {lists:reverse(Parameters), lists:reverse(Suffix)};

pattern2_parse_result(expanded, Parameters, Suffix) ->
    NewParameters = if
        Suffix /= [] ->
            [{exact, lists:reverse(Suffix)} | Parameters];
        true ->
            Parameters
    end,
    lists:reverse(NewParameters).

pattern2_parse_element(_, [], _) ->
    error;

pattern2_parse_element(C, [C | T], Segment) ->
    {ok, T, lists:reverse(Segment)};

pattern2_parse_element(_, [H | _], _)
    when H == $*; H == $? ->
    erlang:exit(badarg);

pattern2_parse_element(C, [H | T], L) ->
    pattern2_parse_element(C, T, [H | L]).

pattern2_parse_pattern0(Pattern, C, L, Segment, Parsed, Option) ->
    case pattern2_parse_element(C, L, Segment) of
        {ok, NewL, NewSegment} ->
            pattern2_parse(Pattern, NewL,
                           [NewSegment | Parsed], [C], Option);
        error ->
            error
    end.

pattern2_parse_pattern1(Pattern, C, L, Segment, Parsed, Option) ->
    case pattern2_parse_element(C, L, Segment) of
        {ok, NewL, NewSegment} ->
            case pattern2_parse(Pattern, NewL,
                               [NewSegment | Parsed], [C], Option) of
                error ->
                    pattern2_parse_pattern1(Pattern, C, NewL,
                                            [C | lists:reverse(NewSegment)],
                                            Parsed, Option);
                Success ->
                    Success
            end;
        error ->
            error
    end.

pattern2_parse([], [], Parsed, Suffix, Option) ->
    pattern2_parse_result(Option, Parsed, Suffix);

pattern2_parse([], [_ | _], _, _, _) ->
    error;

pattern2_parse([_ | _], [H | _], _, _, _)
    when H == $*; H == $? ->
    erlang:exit(badarg);

pattern2_parse([$*], [_ | _] = L, Parsed, Suffix, Option) ->
    NewParsed = if
        Option =:= expanded, Suffix /= [] ->
            [{exact, lists:reverse(Suffix)} | Parsed];
        true ->
            Parsed
    end,
    pattern2_parse_result(Option, [L | NewParsed], []);

pattern2_parse([$?], _, _, _, _) ->
    erlang:exit(badarg);

pattern2_parse([C0, C1 | _], [_ | _], _, _, _)
    when C0 == $* orelse C0 == $?,
         C1 == $* orelse C1 == $? ->
    erlang:exit(badarg);

pattern2_parse([$?, C | Pattern], [H | T], Parsed, Suffix, Option) ->
    if
        C == H ->
            error;
        true ->
            NewParsed = if
                Option =:= expanded, Suffix /= [] ->
                    [{exact, lists:reverse(Suffix)} | Parsed];
                true ->
                    Parsed
            end,
            pattern2_parse_pattern0(Pattern, C, T, [H], NewParsed, Option)
    end;

pattern2_parse([$*, C | Pattern], [H | T], Parsed, Suffix, Option) ->
    NewParsed = if
        Option =:= expanded, Suffix /= [] ->
            [{exact, lists:reverse(Suffix)} | Parsed];
        true ->
            Parsed
    end,
    pattern2_parse_pattern1(Pattern, C, T, [H], NewParsed, Option);

pattern2_parse([C | Pattern], [C | L], Parsed, Suffix, Option) ->
    pattern2_parse(Pattern, L, Parsed, [C | Suffix], Option);

pattern2_parse(_, _, _, _, _) ->
    error.

%%-------------------------------------------------------------------------
%% @doc
%% ===Parse a string based on the supplied wildcard pattern (using 2 wildcard characters) to return only the suffix after the pattern.===
%% "*" and "?" are wildcard characters (equivalent to the ".+" regex).
%% "**", "??", "*?" and "?*" are forbidden.  "?" must not be the last
%% character in the pattern.
%% @end
%%-------------------------------------------------------------------------

-spec pattern2_suffix(Pattern :: string(),
                      L :: string()) ->
    string() | 'error'.

pattern2_suffix([], []) ->
    [];

pattern2_suffix([], [_ | _] = L) ->
    L;

pattern2_suffix([_ | _], [H | _])
    when H == $*; H == $? ->
    erlang:exit(badarg);

pattern2_suffix([$*], [_ | _]) ->
    [];

pattern2_suffix([$?], _) ->
    erlang:exit(badarg);

pattern2_suffix([C0, C1 | _], [_ | _])
    when C0 == $* orelse C0 == $?,
         C1 == $* orelse C1 == $? ->
    erlang:exit(badarg);

pattern2_suffix([$?, C | Pattern], [H | T]) ->
    if
        C == H ->
            error;
        true ->
            pattern2_suffix_pattern0(Pattern, C, T)
    end;

pattern2_suffix([$*, C | Pattern], [_ | T]) ->
    pattern2_suffix_pattern1(Pattern, C, T);

pattern2_suffix([C | Pattern], [C | L]) ->
    pattern2_suffix(Pattern, L);

pattern2_suffix(_, _) ->
    error.

pattern2_suffix_element(_, []) ->
    error;

pattern2_suffix_element(C, [C | T]) ->
    {ok, T};

pattern2_suffix_element(_, [H | _])
    when H == $*; H == $? ->
    erlang:exit(badarg);

pattern2_suffix_element(C, [_ | T]) ->
    pattern2_suffix_element(C, T).

pattern2_suffix_pattern0(Pattern, C, L) ->
    case pattern2_suffix_element(C, L) of
        {ok, NewL} ->
            pattern2_suffix(Pattern, NewL);
        error ->
            error
    end.

pattern2_suffix_pattern1(Pattern, C, L) ->
    case pattern2_suffix_element(C, L) of
        {ok, NewL} ->
            case pattern2_suffix(Pattern, NewL) of
                error ->
                    pattern2_suffix_pattern1(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),
    {ok,"aa*",2} = trie:find_match2("aaaa", RootNode6),
    {ok,"aaaaa",5} = trie:find_match2("aaaaa", RootNode6),
    {ok,"*",1} = trie:find_match2("aa", RootNode6),
    {ok,"aa*",2} = trie:find_match2("aab", RootNode6),
    {ok,"aa*b",3} = trie:find_match2("aabb", RootNode6),
    {ok,"aa*a*",4} = trie:find_match2("aabab", RootNode6),
    {ok,"aa*a*",4} = trie:find_match2("aababb", RootNode6),
    {ok,"aa*a*",4} = trie:find_match2("aabbab", RootNode6),
    {ok,"aa*a*",4} = trie:find_match2("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)),
    {'EXIT',badarg} = (catch trie:find_match2("aa*", RootNode6)),
    {'EXIT',badarg} = (catch trie:find_match2("aaaa*", RootNode6)),
    {'EXIT',badarg} = (catch trie:find_match2("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"),
    ["aa"] = trie:pattern2_parse("aa*", "aaaa"),
    ["b"] = trie:pattern2_parse("aa*", "aab"),
    ["b"] = trie:pattern2_parse("aa*b", "aabb"),
    {["b"], "b"} = trie:pattern2_parse("aa*b", "aabb", with_suffix),
    ["b", "b"] = trie:pattern2_parse("aa*a*", "aabab"),
    {["b", "b"], ""} = trie:pattern2_parse("aa*a*", "aabab", with_suffix),
    ["b", "bb"] = trie:pattern2_parse("aa*a*", "aababb"),
    ["b", "bb"] = trie:pattern2_parse("aa?a*", "aababb"),
    ["bb", "b"] = trie:pattern2_parse("aa*a*", "aabbab"),
    ["bb", "b"] = trie:pattern2_parse("aa?a*", "aabbab"),
    ["bb", "bb"] = trie:pattern2_parse("aa*a*", "aabbabb"),
    ["bb", "bb"] = trie:pattern2_parse("aa?a*", "aabbabb"),
    error = trie:pattern2_parse("aa*a*", "aaabb"),
    ["file.name"] = trie:pattern2_parse("*.txt", "file.name.txt"),
    ["//"] = trie:pattern2_parse("*/", "///"),
    "/get" = trie:pattern2_suffix("*.txt", "file.name.txt/get"),
    error = trie:pattern2_suffix("?.txt", "file.name.txt/get"),
    "/get" = trie:pattern2_suffix("?.txt", "file_name.txt/get"),
    "/get" = trie:pattern2_suffix("*/", "///get"),
    error = trie:pattern2_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),
    [] = trie:pattern2_parse("aaabb", "aaabb"),
    {[], "aaabb"} = trie:pattern2_parse("aaabb", "aaabb", with_suffix),
    [{exact, "a"},
     "ddi",
     {exact, "t"},
     "io",
     {exact, "n"}] = trie:pattern2_parse("a*t*n", "addition", expanded),
    [{exact, "a"},
     "ddi",
     {exact, "t"},
     "io",
     {exact, "n"}] = trie:pattern2_parse("a?t?n", "addition", expanded),
    ["w",{exact,"atch"}] = trie:pattern2_parse("*atch", "watch", expanded),
    ["w",{exact,"atch"}] = trie:pattern2_parse("?atch", "watch", expanded),
    error = trie:pattern2_parse("?atch", "aatch", expanded),
    [{exact,"is"},"t"] = trie:pattern2_parse("is*", "ist", expanded),
    false = trie:is_pattern("abcdef"),
    false = trie:is_pattern("abcde?f"),
    true = trie:is_pattern("abc*d*ef"),
    {'EXIT',badarg} = (catch trie:is_pattern("abc**ef")),
    false = trie:is_pattern2("abcdef"),
    true = trie:is_pattern2("abc?def"),
    true = trie:is_pattern2("abc?d*ef"),
    true = trie:is_pattern2("abcd*ef"),
    {'EXIT',badarg} = (catch trie:is_pattern2("abc**ef")),
    {'EXIT',badarg} = (catch trie:is_pattern2("abc??ef")),
    {'EXIT',badarg} = (catch trie:is_pattern2("abc?*ef")),
    {'EXIT',badarg} = (catch trie:is_pattern2("abc*?ef")),
    {'EXIT',badarg} = (catch trie:is_pattern2("abcef?")),
    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),
    RootNode12 = trie:new([
        {"*",      1},
        {"/?a",    2},
        {"/?/a",   3},
        {"/?/b" ,  4},
        {"/*/a",   5}]),
    {ok,"*",1} = trie:find_match2("/alba", RootNode12),
    {ok,"*",1} = trie:find_match2("/aa", RootNode12),
    {ok,"*",1} = trie:find_match2("/a", RootNode12),
    {ok,"/?a",2} = trie:find_match2("/ba", RootNode12),
    {ok,"/?a",2} = trie:find_match2("/bcdefghijklmno___a", RootNode12),
    {ok,"/?/a",3} = trie:find_match2("/aaaaaaaa/a", RootNode12),
    {ok,"/?/b",4} = trie:find_match2("/a/b", RootNode12),
    {ok,"/?/b",4} = trie:find_match2("/aa/b", RootNode12),
    {ok,"/?/b",4} = trie:find_match2("/ab/b", RootNode12),
    {'EXIT',badarg} = (catch trie:find_match2("/?a", RootNode12)),
    {'EXIT',badarg} = (catch trie:find_match2("/?b", RootNode12)),
    {'EXIT',badarg} = (catch trie:find_match2("/?a", RootNode12)),
    {ok,"/?/a",3} = trie:find_match2("/alba-white/a", RootNode12),
    {ok,"/*/a",5} = trie:find_match2("/alba/white/a", RootNode12),
    RootNode13 = trie:new([
        {"/?a",    1},
        {"/?bbb",  2},
        {"/?c",    3}]),
    {ok,"/?bbb",2} = trie:find_match2("/abbb", RootNode13),
    error = trie:find_match2("/abba", RootNode13),
    {ok,"/?c",3} = trie:find_match2("/abbc", RootNode13),
    RootNode14 = trie:new([
        {"*bc",   1},
        {"*bd",   2}]),
    error = trie:find_match("bb", RootNode14),
    error = trie:find_match2("bb", RootNode14),
    FillPattern0 = "/**/*",
    Parameters0 = ["a/", "b", "c"],
    Parameters1 = ["ignore1", "a/", "ignore2", "b", "c"],
    FillError0 = parameters_selected_empty,
    FillError1 = parameters_selected_ignored,
    FillError2 = parameters_selected_missing,
    {ok, "/a/b/c"} = trie:pattern_fill(FillPattern0, Parameters0),
    {ok, "/a/b/c"} = trie:pattern_fill(FillPattern0, Parameters1,
                                       [2, 4, 5], false),
    {ok, "/a/b/"} = trie:pattern_fill(FillPattern0, Parameters1,
                                       [2, 4], false),
    {ok, "/a/b/c"} = trie:pattern_fill(FillPattern0, Parameters1,
                                       [2, 4, 5], true),
    {error, FillError0} = trie:pattern_fill(FillPattern0, Parameters1,
                                            [2, 4], true),
    {error, {FillError1, [1]}} = trie:pattern_fill(FillPattern0, Parameters1,
                                                   [2, 4, 5, 1], true),
    {error, {FillError2, 6}} = trie:pattern_fill(FillPattern0, Parameters1,
                                                 [2, 4, 6], true),
    FillPattern1 = "/??/?",
    {ok, "/a/b/c"} = trie:pattern2_fill(FillPattern1, Parameters0),
    {ok, "/a/b/c"} = trie:pattern2_fill(FillPattern1, Parameters1,
                                        [2, 4, 5], false),
    {ok, "/a/b/"} = trie:pattern2_fill(FillPattern1, Parameters1,
                                        [2, 4], false),
    {ok, "/a/b/c"} = trie:pattern2_fill(FillPattern1, Parameters1,
                                        [2, 4, 5], true),
    {error, FillError0} = trie:pattern2_fill(FillPattern1, Parameters1,
                                             [2, 4], true),
    {error, {FillError1, [1]}} = trie:pattern2_fill(FillPattern1, Parameters1,
                                                    [2, 4, 5, 1], true),
    {error, {FillError2, 6}} = trie:pattern2_fill(FillPattern1, Parameters1,
                                                  [2, 4, 6], true),
    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).

wildcard_match2_lists_element(_, []) ->
    error;

wildcard_match2_lists_element(_, [C | _])
    when C == $*; C == $? ->
    erlang:exit(badarg);

wildcard_match2_lists_element(C, [C | L]) ->
    {ok, L};

wildcard_match2_lists_element(C, [_ | L]) ->
    wildcard_match2_lists_element(C, L).

wildcard_match2_lists_valid([], Result) ->
    Result;

wildcard_match2_lists_valid([C | _], _)
    when C == $*; C == $? ->
    erlang:exit(badarg);

wildcard_match2_lists_valid([_ | L], Result) ->
    wildcard_match2_lists_valid(L, Result).

wildcard_match2_lists_pattern0(Pattern, C, L) ->
    case wildcard_match2_lists_element(C, L) of
        {ok, NewL} ->
            wildcard_match2_lists(Pattern, NewL);
        error ->
            wildcard_match2_lists_valid(L, false)
    end.

wildcard_match2_lists_pattern1(Pattern, C, L) ->
    case wildcard_match2_lists_element(C, L) of
        {ok, NewL} ->
            case wildcard_match2_lists(Pattern, NewL) of
                true ->
                    true;
                false ->
                    wildcard_match2_lists_pattern1(Pattern, C, NewL)
            end;
        error ->
            wildcard_match2_lists_valid(L, false)
    end.

wildcard_match2_lists([], []) ->
    true;

wildcard_match2_lists([], [_ | _] = L) ->
    wildcard_match2_lists_valid(L, false);

wildcard_match2_lists([_ | _], [C | _])
    when C == $*; C == $? ->
    erlang:exit(badarg);

wildcard_match2_lists([$?], [_ | _]) ->
    erlang:exit(badarg);

wildcard_match2_lists([$?, C | Pattern], [_ | L]) ->
    true = (C =/= $*) andalso (C =/= $?),
    wildcard_match2_lists_pattern0(Pattern, C, L);

wildcard_match2_lists([$*], [_ | L]) ->
    wildcard_match2_lists_valid(L, true);

wildcard_match2_lists([$*, C | Pattern], [_ | L]) ->
    true = (C =/= $*) andalso (C =/= $?),
    wildcard_match2_lists_pattern1(Pattern, C, L);

wildcard_match2_lists([C | Pattern], [C | L]) ->
    wildcard_match2_lists(Pattern, L);

wildcard_match2_lists(_, L) ->
    wildcard_match2_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.