list_trie.ex

defmodule Hjf.ListTrie do
  import Logger

  def new() do
    nil
  end

  def insert(tnode, str, value) when is_binary(str) do
    insert(tnode, String.codepoints(str), value)
  end

  def insert(nil, [], value) do
    %{values: [value]}
  end

  def insert(tnode, [], value) do
    ori_values = Map.get(tnode, :values, [])
    Map.put(tnode, :values, [value | ori_values])
  end

  def insert(nil, [h | t], value) do
    %{h => insert(nil, t, value)}
  end

  def insert(tnode, [h | t], value) do
    child = Map.get(tnode, h, nil)
    Map.put(tnode, h, insert(child, t, value))
  end

  def lookup(tnode, str) when is_binary(str) do
    lookup(tnode, String.codepoints(str))
  end

  def lookup(nil, _) do
    []
  end

  def lookup(%{values: values}, []) do
    values
  end

  def lookup(_, []) do
    []
  end

  def lookup(tnode, [h | t]) do
    case Map.get(tnode, h, nil) do
      nil -> []
      child -> lookup(child, t)
    end
  end

  def match(tnode, str) when is_binary(str) do
    match(tnode, String.codepoints(str))
  end

  def match(nil, _) do
    []
  end

  def match(tnode, []) do
    get_values(tnode)
  end

  def match(tnode, [h | t]) do
    case Map.get(tnode, h, nil) do
      nil -> []
      child -> match(child, t)
    end
  end

  def get_values(nil) do
    []
  end

  def get_values(tnode) do
    :maps.fold(
      fn
        :values, values, acc ->
          values ++ acc

        _, child, acc ->
          get_values(child) ++ acc
      end,
      [],
      tnode
    )
  end
end

toy_trie.erl

-module(toy_trie).
-export([new/0
         , insert/3
         , delete/2
         , lookup/2
         , match/2 ]).


new() ->
    nil.


insert([], Value, nil) ->
    #{value => Value};
insert([], Value, Node) ->
    Node#{value => Value};
insert([H | T], Value, nil) ->
    #{H => insert(T, Value, nil)};
insert([H | T], Value, Node) ->
    Child = maps:get(H, Node, nil),
    Node#{H => insert(T, Value, Child)}.


delete(_, nil) ->
    nil;
delete([], Node) ->
    Node2 = maps:remove(value, Node),
    case maps:size(Node2) =:= 0 of
        true ->
            nil;
        false ->
            Node2
    end;
delete([H | T], Node) ->
    Child = maps:get(H, Node, nil),
    Child2 = delete(T, Child),
    Node2 = case Child2 =:= nil orelse Child2 =:= #{} of
                true ->
                    maps:remove(H, Node);
                false ->
                    Node#{H => Child2}
            end,
    case maps:size(Node2) =:= 0 of
        true ->
            nil;
        false ->
            Node2
    end.


lookup(_, nil) ->
    [];
lookup([], #{value := Value}) ->
    [Value];
lookup([], _) ->
    [];
lookup([H | T], Node) ->
    case Node of
        #{H := Child} ->
            lookup(T, Child);
        _ ->
            []
    end.

match(_, nil) ->
    [];
match([], Node) ->
    values(Node);
match([H | T], Node) ->
    case Node of
        #{H := Child} ->
            match(T, Child);
        _ ->
            []
    end.

values(nil) ->
    [];
values(Node) ->
    maps:fold(fun(value, Value, Acc) ->
                      [Value | Acc];
                 (_, Child, Acc) ->
                      values(Child) ++ Acc
              end, [], Node
             ).

trie.ex

defmodule Hjf.Trie do
  import Logger

  def new() do
    nil
  end

  def insert(tnode, str, value) when is_binary(str) do
    insert(tnode, String.codepoints(str), value)
  end

  def insert(nil, [], value) do
    %{value: value}
  end

  def insert(tnode, [], value) do
    Map.put(tnode, :value, value)
  end

  def insert(nil, [h | t], value) do
    %{h => insert(nil, t, value)}
  end

  def insert(tnode, [h | t], value) do
    child = Map.get(tnode, h, nil)
    Map.put(tnode, h, insert(child, t, value))
  end

  def lookup(tnode, str) when is_binary(str) do
    lookup(tnode, String.codepoints(str))
  end

  def lookup(nil, _) do
    nil
  end

  def lookup(%{value: value}, []) do
    value
  end

  def lookup(_, []) do
    nil
  end

  def lookup(tnode, [h | t]) do
    case Map.get(tnode, h, nil) do
      nil -> nil
      child -> lookup(child, t)
    end
  end

  def match(tnode, str) when is_binary(str) do
    match(tnode, String.codepoints(str))
  end

  def match(nil, _) do
    []
  end

  def match(tnode, []) do
    values(tnode)
  end

  def match(tnode, [h | t]) do
    case Map.get(tnode, h, nil) do
      nil -> []
      child -> match(child, t)
    end
  end

  def values(nil) do
    []
  end

  def values(tnode) do
    :maps.fold(
      fn
        :value, value, acc ->
          [value | acc]

        _, child, acc ->
          values(child) ++ acc
      end,
      [],
      tnode
    )
  end
end