omarelb Posts - Answer Overflow

omarelb

•Created by omarelb on 10/29/2024 in #questions

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]

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[]))

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()))

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?

3 replies

Gaming

Programming