Hey, I read a &String.myers_difference/2 code and modified it, so it’s possible to use List (also char list) and Keyword types instead of String type.
Here is an example module:
defmodule Example do
def myers_difference(list1, list2) do
len1 = Enum.count(list1)
len2 = Enum.count(list2)
path = {0, 0, list1, list2, []}
find_script(0, len1 + len2, [path])
end
defp find_script(envelope, max, _paths) when envelope > max do
nil
end
defp find_script(envelope, max, paths) do
case each_diagonal(-envelope, envelope, paths, []) do
{:done, edits} -> compact_reverse(edits, [], false)
{:next, paths} -> find_script(envelope + 1, max, paths)
end
end
defp compact_reverse([], acc, _), do: acc
defp compact_reverse([{kind, el} | rest], [{kind, next_elem} | acc], false) do
compact_reverse(rest, [{kind, [el, next_elem]} | acc], true)
end
defp compact_reverse([{kind, el} | rest], [{kind, next_elements} | acc], true) do
compact_reverse(rest, [{kind, [el | next_elements]} | acc], true)
end
defp compact_reverse([elem | rest], acc, _) do
compact_reverse(rest, [elem | acc], false)
end
defp each_diagonal(diag, limit, _paths, next_paths) when diag > limit do
{:next, Enum.reverse(next_paths)}
end
defp each_diagonal(diag, limit, paths, next_paths) do
{path, rest} = proceed_path(diag, limit, paths)
with {:cont, path} <- follow_snake(path) do
each_diagonal(diag + 2, limit, rest, [path | next_paths])
end
end
defp proceed_path(0, 0, [path]), do: {path, []}
defp proceed_path(diag, limit, [path | _] = paths) when diag == -limit do
{move_down(path), paths}
end
defp proceed_path(diag, limit, [path]) when diag == limit do
{move_right(path), []}
end
defp proceed_path(_diag, _limit, [path1, path2 | rest]) do
if elem(path1, 1) > elem(path2, 1) do
{move_right(path1), [path2 | rest]}
else
{move_down(path2), [path2 | rest]}
end
end
defp move_right({x, y, list1, [elem | rest], edits}) do
{x + 1, y, list1, rest, [{:ins, elem} | edits]}
end
defp move_right({x, y, list1, [], edits}) do
{x + 1, y, list1, [], edits}
end
defp move_down({x, y, [elem | rest], list2, edits}) do
{x, y + 1, rest, list2, [{:del, elem} | edits]}
end
defp move_down({x, y, [], list2, edits}) do
{x, y + 1, [], list2, edits}
end
defp follow_snake({x, y, [elem | rest1], [elem | rest2], edits}) do
follow_snake({x + 1, y + 1, rest1, rest2, [{:eq, elem} | edits]})
end
defp follow_snake({_x, _y, [], [], edits}) do
{:done, edits}
end
defp follow_snake(path) do
{:cont, path}
end
end
As you can see I modified only some things:
- variable names - now we don’'t have a string and chars (graphemes) - instead we have list and elements
-
compact_reversemethod has one more (boolean) parameter and case - it’s for create/join a list of changes (no conflict with nested list) -
myers_differencemain method is modified to support list (len1 and len2 variables)
Here is the link for source of original implementation.
If someone is interested in Map implementation I can try modify the code.
What do you think about my changes?
. Maybe in this month I post my differ package, but there are a lot of things I want to implement to it. I have done it for String, Atom (also boolean), Integer and Float types. Now I’m working on List and Map (also structs).
