GenTree (gen_tree v0.2.1)
Tree data structure for BEAM in BEAM-way. Each node is a process that contains data and children_pids. The pid is used as pointers.
Tree implementation becomes straight forwards with pointers that can point to a node and a shared state that helps in while performing operations on different nodes, say traversals.
A work around this would be using Agents.
Agents are a simple abstraction around state.
Often in Elixir there is a need to share or store state that must be accessed
from different processes or by the same process at different points in time.
The Agent module provides a basic server implementation that allows state to be
retrieved and updated via a simple API.Thus a node in tree can be described as
{:ok, node_pid} = Agent.start(fn -> %{data: "some_data"} end)This provides us with a pid which can be used to point to the node and a state that can be manipulated.
Link to this section Summary
Functions
Traverses a tree using BFS.
Counts the number of children of the node
Traverses a binary tree using DFS.
Builds a tree from a datalist in level-order. Data can have nil to skip sub-tree.
Get the children list of the node
Get the node data value.
Get the left child of node in case of binary tree [:nary, 2]
Get the node details.
Updates the parent pid of node.
Get the right child of node in case of binary tree [:nary, 2]
Return if data has a left child in case of binary tree [:nary, 2]
Return if data has a right child in case of binary tree [:nary, 2]
Inserts child to the node and returns the child pid. child_type can be :left, :right or omitted.
New node of GenTree
Invokes reducer_function for each node_pid in the tree with the accumulator.
Updates the parent pid of node.
Updates the data value of the node
Updates complete node value
Link to this section Functions
bfs(parent_pid)
Specs
Traverses a tree using BFS.
Examples
iex> root = GenTree.from_list([1,2,3,4,5,6])
iex> GenTree.Traversal.bfs(root)
[1, 2, 3, 4, 5, 6]count_children(node_pid)
Specs
Counts the number of children of the node
Examples
iex> root = GenTree.new(5)
iex> GenTree.count_children(root)
0
iex> GenTree.insert_child(root, "b", :left)
iex> GenTree.insert_child(root, "a", :right)
iex> GenTree.count_children(root)
2dfs(parent_pid, traversal_type)
Specs
Traverses a binary tree using DFS.
Traversal types
- :inorder
- :preorder
- :postorder
Examples
iex> root = GenTree.from_list([1,2,3,4,5,6])
iex> GenTree.Traversal.dfs(root, :inorder)
[4, 2, 5, 1, 6, 3]
iex> GenTree.Traversal.dfs(root, :preorder)
[1, 2, 4, 5, 3, 6]
iex> GenTree.Traversal.dfs(root, :postorder)
[4, 5, 2, 6, 3, 1]from_list(data_list, opts \\ [nary: 2])
Builds a tree from a datalist in level-order. Data can have nil to skip sub-tree.
get_children(node_pid)
Specs
Get the children list of the node
get_data(node_pid)
Specs
Get the node data value.
Examples
iex> root = GenTree.new(5)
iex> root |> GenTree.get_data()
5get_left(node_pid)
Specs
Get the left child of node in case of binary tree [:nary, 2]
Examples
iex> root = GenTree.new(5)
iex> GenTree.get_left(root)get_node(node_pid)
Specs
get_node(pid()) :: GenTree.Node.t()
Get the node details.
Examples
iex> root = GenTree.new(5)
iex> root |> GenTree.get_node()
%GenTree.Node{children: [], data: 5, left: nil, right: nil, parent: nil}get_parent(self_pid)
Specs
Updates the parent pid of node.
get_right(node_pid)
Specs
Get the right child of node in case of binary tree [:nary, 2]
Examples
iex> root = GenTree.new(5)
iex> GenTree.get_right(root)has_left?(node_pid)
Specs
Return if data has a left child in case of binary tree [:nary, 2]
## Examples
iex> root = GenTree.new(5)
iex> GenTree.has_left?(root)
falsehas_right?(node_pid)
Specs
Return if data has a right child in case of binary tree [:nary, 2]
## Examples
iex> root = GenTree.new(5)
iex> GenTree.has_right?(root)
falseinsert_child(node_pid, data, child_type \\ nil)
Inserts child to the node and returns the child pid. child_type can be :left, :right or omitted.
Examples
iex(21)> root = GenTree.new("a")
iex(23)> left_child = GenTree.insert_child(root, "b", :left)
iex(25)> GenTree.get_parent(left_child) === root
truenew(data)
Specs
New node of GenTree
Examples
iex> root = GenTree.new(5)
iex> is_pid(root) === truereduce(root_pid, initial_value, reducer_function, traverse_opts \\ [search: :bfs])
Specs
Invokes reducer_function for each node_pid in the tree with the accumulator.
Default tree traversal method is Breadth-First-Search and default order of Depth First Search is postorder. Traversal options can be passed as Keyword list as
[
search: :bfs | :dfs,
order: :postorder, :preorder, :inorder
]Examples
iex> root = GenTree.from_list([1,2,3,nil,4,5,7,nil,nil,8,9])
iex> GenTree.reduce(root, 0, fn node_pid, acc -> acc + GenTree.get_data(node_pid) end)
39
iex> GenTree.reduce(root, [], fn node_pid, acc -> acc ++ [GenTree.get_data(node_pid)] end, [search: :dfs, order: :postorder])
[4, 2, 8, 9, 5, 7, 3, 1]
iex> GenTree.dfs(root, :postorder)
[4, 2, 8, 9, 5, 7, 3, 1]
iex> GenTree.reduce(root, [], fn node_pid, acc -> acc ++ [node_pid] end, [search: :dfs, order: :postorder]) |>
...> Enum.map(fn node_pid -> GenTree.get_data(node_pid) end)
[4, 2, 8, 9, 5, 7, 3, 1]set_parent(self_pid, parent_pid)
Specs
Updates the parent pid of node.
update_data(node_pid, data)
Specs
Updates the data value of the node
update_node(node_pid, data)
Specs
Updates complete node value