///|
pub fn spatial_find(root : SpatialNode, id : Int) -> SpatialNode? {
  if root.id == id {
    return Some(root)
  }
  for child in root.children {
    match spatial_find(child, id) {
      Some(found) => return Some(found)
      None => ()
    }
  }
  None
}

///|
pub fn spatial_find_named(
  root : SpatialNode,
  fragment : String,
) -> Array[SpatialNode] {
  let result : Array[SpatialNode] = []
  match root.name {
    Some(name) if name.to_lower().contains(fragment.to_lower()) =>
      result.push(root)
    _ => ()
  }
  for child in root.children {
    for found in spatial_find_named(child, fragment) {
      result.push(found)
    }
  }
  result
}

///|
fn spatial_path_inner(
  root : SpatialNode,
  target : Int,
  path : Array[Int],
) -> Array[Int]? {
  let next = path.copy()
  next.push(root.id)
  if root.id == target {
    return Some(next)
  }
  for child in root.children {
    match spatial_path_inner(child, target, next) {
      Some(found) => return Some(found)
      None => ()
    }
  }
  None
}

///|
pub fn spatial_path(root : SpatialNode, target : Int) -> Array[Int]? {
  spatial_path_inner(root, target, [])
}

///|
pub fn spatial_depth(root : SpatialNode) -> Int {
  root.children.fold(init=0, (maximum, child) => {
    let depth = spatial_depth(child) + 1
    if depth > maximum {
      depth
    } else {
      maximum
    }
  })
}

///|
pub fn spatial_leaf_nodes(root : SpatialNode) -> Array[SpatialNode] {
  if root.children.length() == 0 {
    return [root]
  }
  root.children.fold(init=Array::new(), (result, child) => {
    for leaf in spatial_leaf_nodes(child) {
      result.push(leaf)
    }
    result
  })
}

///|
pub fn spatial_products_named(
  root : SpatialNode,
  fragment : String,
) -> Array[Int] {
  spatial_find_named(root, fragment).fold(init=Array::new(), (result, node) => {
    for product in node.products {
      result.push(product)
    }
    result
  })
}