You could also draw inspiration from erlang’s :gb_trees implementation where each node is a {key, value, left_subtree, right_subtree} tuple which looks quite cheap/easy to update and probably cost less memory to keep around than a struct or map
bottlenecked
1
Dusty
So I have been working a bit on the struct for each node in the tree. Each node needs to hold a pointer to its parent, as well as a list of children. What is the best way for the two nodes to point to each other in memory? I am coding in circles a bit. For example, if I start with this abbreviated module:
defmodule SuffixTree.Node do
alias __MODULE__
use Puid
@enforce_keys [:id, :children]
defstruct id: nil,
parent: nil,
label: nil,
leaves: [],
children: [],
link: nil
@type t :: %Node{
id: String.t(),
parent: Node.t(),
label: {String.t(), Range.t()},
leaves: [{String.t(), integer()}],
children: [Node.t()],
link: Node.t()
}
def new_node() do
%Node{
id: generate(),
parent: nil,
label: nil,
leaves: [],
children: [],
link: nil
}
end
def add_child(%{children: children} = parent, child) do
{:ok, child} = add_parent(parent, child)
children = [child | children] |> Enum.sort(Node)
{:ok, %{parent | children: children}}
end
def add_parent(parent, child) do
{:ok, %{child | parent: parent}}
end
end
And then in IEx I load the module, and do something like:
node1 = new_node()
node2 = new_node()
{:ok, node1} = add_child(node1, node2)
node1
I get back something like this:
%SuffixTree.Node{
children: [
%SuffixTree.Node{
children: [],
id: "NJ_fgObmA_gBgU9GB7iy-Q",
label: nil,
leaves: [],
link: nil,
parent: %SuffixTree.Node{
children: [],
id: "rd2Y7laSMSDmaeT9JbLFeA",
label: nil,
leaves: [],
link: nil,
parent: nil
}
}
],
id: "rd2Y7laSMSDmaeT9JbLFeA",
label: nil,
leaves: [],
link: nil,
parent: nil
}
I see that node1’s id matches in both places (in itself, and in the parent field of its child). But the Node listed in the parent field has no children, and we know that node1 now has a child. It doesn’t take much thought for me to realize that there’s no way to display this kind of referential circle, because you would infinitely print the child inside the parent inside the child inside the parent…
So my question is: Am I pointing at 2 different memory locations? Are these actually 2 different node1’s?
The obvious answer seems to be to point only to the id of the node, rather than the node itself, but that means I need a lookup table/map containing every node by id.
Am I thinking about this wrong? How would you approach it?
0
NobbZ
You can’t have circular references in immutable data structures.
You can of course simulate them using a flat datastructure and mentioning IDs.
3