///|
/// Return the number of levels below a spatial node.  IFC aggregation is a
/// graph in the file, but applications consume it as a bounded tree.
pub fn SpatialNode::depth(self : SpatialNode) -> Int {
  self.children.fold(init=0, (current, child) => {
    let candidate = child.depth() + 1
    if candidate > current {
      candidate
    } else {
      current
    }
  })
}

///|
pub fn SpatialNode::is_leaf(self : SpatialNode) -> Bool {
  self.children.length() == 0
}

///|
pub fn SpatialNode::node_count(self : SpatialNode) -> Int {
  1 + self.children.fold(init=0, (count, child) => count + child.node_count())
}

///|
pub fn SpatialNode::leaf_count(self : SpatialNode) -> Int {
  if self.is_leaf() {
    1
  } else {
    self.children.fold(init=0, (count, child) => count + child.leaf_count())
  }
}

///|
pub fn SpatialNode::product_count(self : SpatialNode) -> Int {
  self.products.length() +
  self.children.fold(init=0, (count, child) => count + child.product_count())
}

///|
pub fn SpatialNode::all_product_ids(self : SpatialNode) -> Array[Int] {
  let result = self.products.copy()
  for child in self.children {
    result.append(child.all_product_ids())
  }
  result
}

///|
fn unique_ints(values : Array[Int]) -> Array[Int] {
  let seen : Map[Int, Bool] = Map([])
  let result : Array[Int] = []
  for value in values {
    if !seen.contains(value) {
      seen[value] = true
      result.push(value)
    }
  }
  result
}

///|
pub fn SpatialNode::unique_product_ids(self : SpatialNode) -> Array[Int] {
  unique_ints(self.all_product_ids())
}

///|
pub fn SpatialNode::contains(self : SpatialNode, id : Int) -> Bool {
  self.id == id || self.children.any(child => child.contains(id))
}

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

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

///|
pub fn SpatialNode::path_to(self : SpatialNode, target : Int) -> Array[Int]? {
  path_to_node(self, target, [])
}

///|
pub fn SpatialNode::nodes_at_depth(
  self : SpatialNode,
  wanted : Int,
) -> Array[SpatialNode] {
  fn visit(
    node : SpatialNode,
    depth : Int,
    wanted : Int,
    output : Array[SpatialNode],
  ) -> Unit {
    if depth == wanted {
      output.push(node)
    } else if depth < wanted {
      for child in node.children {
        visit(child, depth + 1, wanted, output)
      }
    }
  }
  let output : Array[SpatialNode] = []
  if wanted >= 0 {
    visit(self, 0, wanted, output)
  }
  output
}

///|
pub fn SpatialNode::leaves(self : SpatialNode) -> Array[SpatialNode] {
  if self.is_leaf() {
    [self]
  } else {
    self.children.fold(init=Array::new(), (output, child) => {
      output.append(child.leaves())
      output
    })
  }
}

///|
pub fn SpatialNode::type_histogram(self : SpatialNode) -> Map[String, Int] {
  let result : Map[String, Int] = Map([])
  fn visit(node : SpatialNode, output : Map[String, Int]) -> Unit {
    output.update_or_default(node.ifc_type.to_upper(), 1, count => count + 1)
    for child in node.children {
      visit(child, output)
    }
  }
  visit(self, result)
  result
}

///|
fn product_geometry_bounds(
  index : ModelIndex,
  product : Product,
) -> BoundingBox {
  let transform = product_transform(index, product)
  geometries_for_product(index, product).fold(init=BoundingBox::empty(), (
    bounds,
    geometry,
  ) => {
    let transformed = geometry.points.map(point => transform.apply(point))
    merge_bounds(bounds, BoundingBox::from_points(transformed))
  })
}

///|
fn spatial_bounds_for_node(
  index : ModelIndex,
  products : Map[Int, Product],
  node : SpatialNode,
) -> BoundingBox {
  let own = node.products.fold(init=BoundingBox::empty(), (bounds, id) => {
    match products.get(id) {
      Some(product) =>
        merge_bounds(bounds, product_geometry_bounds(index, product))
      None => bounds
    }
  })
  node.children.fold(init=own, (bounds, child) => {
    merge_bounds(bounds, spatial_bounds_for_node(index, products, child))
  })
}

///|
pub fn spatial_metrics(
  index : ModelIndex,
  root : SpatialNode,
) -> SpatialMetrics {
  let products = extract_products(index)
  let by_id : Map[Int, Product] = Map([])
  for product in products {
    by_id[product.id] = product
  }
  {
    node_count: root.node_count(),
    leaf_count: root.leaf_count(),
    product_count: root.unique_product_ids().length(),
    max_depth: root.depth(),
    occupied_volume: spatial_bounds_for_node(index, by_id, root).volume(),
    bounds: spatial_bounds_for_node(index, by_id, root),
  }
}

///|
pub fn spatial_model_metrics(model : Model) -> SpatialMetrics {
  let index = model.index()
  let roots = spatial_roots(index)
  roots.fold(
    init={
      node_count: 0,
      leaf_count: 0,
      product_count: 0,
      max_depth: 0,
      occupied_volume: 0.0,
      bounds: BoundingBox::empty(),
    },
    (result, root) => {
      let current = spatial_metrics(index, root)
      {
        node_count: result.node_count + current.node_count,
        leaf_count: result.leaf_count + current.leaf_count,
        product_count: result.product_count + current.product_count,
        max_depth: if result.max_depth > current.max_depth {
          result.max_depth
        } else {
          current.max_depth
        },
        occupied_volume: result.occupied_volume + current.occupied_volume,
        bounds: merge_bounds(result.bounds, current.bounds),
      }
    },
  )
}

///|
pub fn spatial_depth_histogram(root : SpatialNode) -> Map[Int, Int] {
  let result : Map[Int, Int] = Map([])
  fn visit(node : SpatialNode, depth : Int, output : Map[Int, Int]) -> Unit {
    output.update_or_default(depth, 1, count => count + 1)
    for child in node.children {
      visit(child, depth + 1, output)
    }
  }
  visit(root, 0, result)
  result
}

///|
pub fn spatial_product_containers(index : ModelIndex) -> Map[Int, Int] {
  let result : Map[Int, Int] = Map([])
  for relation in index.all() {
    if relation.name.to_upper() == "IFCRELCONTAINEDINSPATIALSTRUCTURE" {
      match optional_reference_argument(relation, 5) {
        Some(container) =>
          for product in relation_objects(relation, 4) {
            result[product] = container
          }
        None => ()
      }
    }
  }
  result
}

///|
pub fn spatial_nodes_by_type(
  root : SpatialNode,
  ifc_type : String,
) -> Array[SpatialNode] {
  let wanted = ifc_type.to_upper()
  flatten_spatial(root).filter(node => node.ifc_type.to_upper() == wanted)
}

///|
pub fn spatial_named_nodes(
  root : SpatialNode,
  fragment : String,
) -> Array[SpatialNode] {
  let wanted = fragment.to_lower()
  flatten_spatial(root).filter(node => {
    match node.name {
      Some(name) => name.to_lower().contains(wanted)
      None => false
    }
  })
}

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

///|
pub fn spatial_duplicate_product_ids(root : SpatialNode) -> Array[Int] {
  let counts : Map[Int, Int] = Map([])
  for id in root.all_product_ids() {
    counts.update_or_default(id, 1, count => count + 1)
  }
  let result : Array[Int] = []
  for id, count in counts {
    if count > 1 {
      result.push(id)
    }
  }
  result
}

///|
pub fn spatial_report(index : ModelIndex, root : SpatialNode) -> String {
  let metrics = spatial_metrics(index, root)
  "root #" +
  root.id.to_string() +
  " " +
  root.ifc_type +
  " nodes=" +
  metrics.node_count.to_string() +
  " leaves=" +
  metrics.leaf_count.to_string() +
  " products=" +
  metrics.product_count.to_string() +
  " depth=" +
  metrics.max_depth.to_string() +
  " bounds=" +
  metrics.bounds.width().to_string() +
  "x" +
  metrics.bounds.height().to_string() +
  "x" +
  metrics.bounds.depth().to_string()
}

///|
pub fn spatial_report_all(model : Model) -> Array[String] {
  let index = model.index()
  spatial_roots(index).map(root => spatial_report(index, root))
}

///|
pub fn spatial_tree_is_acyclic(root : SpatialNode) -> Bool {
  fn visit(node : SpatialNode, path : Array[Int]) -> Bool {
    if path.contains(node.id) {
      return false
    }
    let next = path.copy()
    next.push(node.id)
    for child in node.children {
      if !visit(child, next) {
        return false
      }
    }
    true
  }
  visit(root, [])
}

///|
pub fn spatial_tree_ids(root : SpatialNode) -> Array[Int] {
  flatten_spatial(root).map(node => node.id)
}

///|
pub fn spatial_root_summary(model : Model) -> String {
  let roots = spatial_roots(model.index())
  if roots.length() == 0 {
    "no spatial roots"
  } else {
    roots.map(root => root.ifc_type + " #" + root.id.to_string()).join(", ")
  }
}