zipper.exs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
defmodule BinTree do
  @moduledoc """
  A node in a binary tree.

  `value` is the value of a node.
  `left` is the left subtree (nil if no subtree).
  `right` is the right subtree (nil if no subtree).
  """
  @type t :: %BinTree{ value: any, left: BinTree.t | nil, right: BinTree.t | nil }
  defstruct value: nil, left: nil, right: nil
end

defmodule Zipper do
  @type t :: %Zipper{ focus: BinTree.t, path: Zipper.p }
  defstruct focus: nil, path: nil

  @type p :: [ { :left, BinTree.t } | { :right, BinTree.t } ]

  @doc """
  Get a zipper focused on the root node.
  """
  @spec from_tree(BT.t) :: Z.t
  def from_tree(bt), do: %Zipper{ focus: bt, path: [] }

  @doc """
  Get the complete tree from a zipper.
  """
  @spec to_tree(Z.t) :: BT.t
  def to_tree(%Zipper{ path: [], focus: focus }), do: focus

  def to_tree(%Zipper{ path: path }) do
    { _, tree } = List.last(path)
    tree
  end

  @doc """
  Get the value of the focus node.
  """
  @spec value(Z.t) :: any
  def value(%Zipper{ focus: focus }), do: focus.value

  @doc """
  Get the left child of the focus node, if any.
  """
  @spec left(Z.t) :: Z.t | nil
  def left(%Zipper{ focus: focus, path: path }) do
    cond do
      focus.left != nil -> %Zipper{ focus: focus.left, path: [{ :left, focus }|path] }
      true -> nil
    end
  end

  @doc """
  Get the right child of the focus node, if any.
  """
  @spec right(Z.t) :: Z.t | nil
  def right(%Zipper{ focus: focus, path: path }) do
    cond do
      focus.right != nil -> %Zipper{ focus: focus.right, path: [{ :right, focus }|path] }
      true -> nil
    end
  end

  @doc """
  Get the parent of the focus node, if any.
  """
  @spec up(Z.t) :: Z.t
  def up(%Zipper{ path: [{ _, parent }|tail] }), do: %Zipper{ path: tail, focus: parent }

  @doc """
  Set the value of the focus node.
  """
  @spec set_value(Z.t, any) :: Z.t
  def set_value(%Zipper{ focus: focus, path: path }, value) do
    insert(%BinTree{ right: focus.right, left: focus.left, value: value }, path)
    |> from_tree()
  end

  @doc """
  Replace the left child tree of the focus node.
  """
  @spec set_left(Z.t, BT.t) :: Z.t
  def set_left(%Zipper{ focus: focus, path: path }, left) do
    insert(%BinTree{ left: left, right: focus.right, value: focus.value }, path)
    |> from_tree()
  end

  @doc """
  Replace the right child tree of the focus node.
  """
  @spec set_right(Z.t, BT.t) :: Z.t
  def set_right(%Zipper{ focus: focus, path: path }, right) do
    insert(%BinTree{ value: focus.value, left: focus.left, right: right }, path)
    |> from_tree()
  end

  defp insert(node, [head|tail]) do
    case head do
      {:left, parent}  -> insert(%BinTree{ left: node,        right: parent.right, value: parent.value }, tail)
      {:right, parent} -> insert(%BinTree{ left: parent.left, right: node,         value: parent.value }, tail)
    end
  end

  defp insert(node, []), do: node
end

Comments


You're not logged in right now. Please login via GitHub to comment