ModularM
Modular•15mo ago•
2 replies
omarelb

What pointer lifetime to use when iterating through a tree?

I've created a tree data structure:
struct BKTree:
    var root: Optional[BKTreeNode]

struct BKTreeNode(TestableCollectionElement):
    var text: String
    var parent_distance: Int
    var children: List[BKTreeNode]

which I've added nodes to. I now want to search for a node by iterating over its children:
nodes_to_process = List[UnsafePointer[BKTreeNode]](
    UnsafePointer.address_of(self.root.value())
)

while len(nodes_to_process) > 0:
  current_node_ref = nodes_to_process.pop()
  current_node_distance_to_query = levenshtein_distance(
      current_node_ref[].text, query
  )

  for child in current_node_ref[].children:
      if (within_distance):
          nodes_to_process.append(UnsafePointer.address_of(child[]))


As you can see, I'm using UnsafePointer here which I don't really like. I tried to use Pointer, but I can't figure out how to get the lifetime right. If I use:
nodes_to_process = List(Pointer.address_of(self.root.value()))


I get an error at the append call: invalid call to 'append': method argument #0 cannot be converted from 'Pointer[0, BKTreeNode, self.root._value.children, 0]' to 'Pointer[0, BKTreeNode, self.root._value, 0]'.

Is there an idiomatic way to do this correctly? I've tried Arc but this seems to slow the search down by a lot. I'm using Pointers to avoid copying nodes. Is this the right way to go about this in the first place?
Was this page helpful?