///|
fn spatial_safe_cell_size(value : Double) -> Double {
  if value <= 0.0 {
    10.0
  } else {
    value
  }
}

///|
fn spatial_safe_limit(value : Int) -> Int {
  if value <= 0 {
    2147483647
  } else {
    value
  }
}

///|
/// Return conservative construction defaults for a building-scale model.
pub fn default_spatial_index_options() -> SpatialIndexOptions {
  { cell_size: 10.0, include_empty: false, maximum_entries: 0 }
}

///|
pub fn SpatialIndexOptions::with_cell_size(
  self : SpatialIndexOptions,
  cell_size : Double,
) -> SpatialIndexOptions {
  { ..self, cell_size: spatial_safe_cell_size(cell_size) }
}

///|
pub fn SpatialIndexOptions::including_empty(
  self : SpatialIndexOptions,
  include_empty : Bool,
) -> SpatialIndexOptions {
  { ..self, include_empty, }
}

///|
pub fn SpatialIndexOptions::with_maximum_entries(
  self : SpatialIndexOptions,
  maximum_entries : Int,
) -> SpatialIndexOptions {
  {
    ..self,
    maximum_entries: if maximum_entries < 0 {
      0
    } else {
      maximum_entries
    },
  }
}

///|
fn spatial_axis_distance(
  left_min : Double,
  left_max : Double,
  right_min : Double,
  right_max : Double,
) -> Double {
  if left_max < right_min {
    right_min - left_max
  } else if right_max < left_min {
    left_min - right_max
  } else {
    0.0
  }
}

///|
pub fn box_distance(left : BoundingBox, right : BoundingBox) -> Double {
  if left.empty || right.empty {
    return 0.0
  }
  let x = spatial_axis_distance(
    left.min.x,
    left.max.x,
    right.min.x,
    right.max.x,
  )
  let y = spatial_axis_distance(
    left.min.y,
    left.max.y,
    right.min.y,
    right.max.y,
  )
  let z = spatial_axis_distance(
    left.min.z,
    left.max.z,
    right.min.z,
    right.max.z,
  )
  (x * x + y * y + z * z).sqrt()
}

///|
pub fn box_intersection(left : BoundingBox, right : BoundingBox) -> BoundingBox {
  if left.empty || right.empty {
    return BoundingBox::empty()
  }
  let min_x = if left.min.x > right.min.x { left.min.x } else { right.min.x }
  let min_y = if left.min.y > right.min.y { left.min.y } else { right.min.y }
  let min_z = if left.min.z > right.min.z { left.min.z } else { right.min.z }
  let max_x = if left.max.x < right.max.x { left.max.x } else { right.max.x }
  let max_y = if left.max.y < right.max.y { left.max.y } else { right.max.y }
  let max_z = if left.max.z < right.max.z { left.max.z } else { right.max.z }
  if min_x > max_x || min_y > max_y || min_z > max_z {
    BoundingBox::empty()
  } else {
    {
      min: { x: min_x, y: min_y, z: min_z },
      max: { x: max_x, y: max_y, z: max_z },
      empty: false,
    }
  }
}

///|
pub fn box_relation(
  left : BoundingBox,
  right : BoundingBox,
  tolerance : Double,
) -> BoxRelation {
  if left.empty || right.empty {
    return Disjoint
  }
  let margin = if tolerance < 0.0 { 0.0 } else { tolerance }
  let separated = left.max.x < right.min.x - margin ||
    right.max.x < left.min.x - margin ||
    left.max.y < right.min.y - margin ||
    right.max.y < left.min.y - margin ||
    left.max.z < right.min.z - margin ||
    right.max.z < left.min.z - margin
  if separated {
    return Disjoint
  }
  let overlap = box_intersection(left, right)
  let touching = overlap.empty ||
    overlap.width() <= margin ||
    overlap.height() <= margin ||
    overlap.depth() <= margin
  let left_contains = left.min.x <= right.min.x + margin &&
    left.min.y <= right.min.y + margin &&
    left.min.z <= right.min.z + margin &&
    left.max.x >= right.max.x - margin &&
    left.max.y >= right.max.y - margin &&
    left.max.z >= right.max.z - margin
  let right_contains = right.min.x <= left.min.x + margin &&
    right.min.y <= left.min.y + margin &&
    right.min.z <= left.min.z + margin &&
    right.max.x >= left.max.x - margin &&
    right.max.y >= left.max.y - margin &&
    right.max.z >= left.max.z - margin
  if touching {
    Touching
  } else if left_contains && right_contains {
    Equal
  } else if left_contains {
    Contains
  } else if right_contains {
    Within
  } else {
    Overlapping
  }
}

///|
fn spatial_world_bounds(
  index : ModelIndex,
  product : Product,
) -> BoundingBox raise ParseError {
  let mesh = mesh_for_product_advanced(index, product)
  if mesh.points.length() > 0 {
    bounds_of_mesh(mesh)
  } else {
    geometries_for_product(index, product).fold(init=BoundingBox::empty(), (
      result,
      geometry,
    ) => {
      let transformed = transform_points(index, product, geometry.points)
      merge_bounds(result, BoundingBox::from_points(transformed))
    })
  }
}

///|
fn spatial_entry_for_product(
  index : ModelIndex,
  product : Product,
) -> SpatialEntry raise ParseError {
  let geometries = geometries_for_product(index, product)
  let mesh = mesh_for_product_advanced(index, product)
  {
    product_id: product.id,
    entity_id: product.id,
    ifc_type: product.ifc_type,
    name: product.name,
    container: product.container,
    bounds: if mesh.points.length() > 0 {
      bounds_of_mesh(mesh)
    } else {
      spatial_world_bounds(index, product)
    },
    geometry_count: geometries.length(),
    point_count: mesh.points.length(),
    triangle_count: mesh.triangles.length(),
  }
}

///|
fn spatial_cell_coordinate(value : Double, cell_size : Double) -> Int {
  @math.floor(value / cell_size).to_int()
}

///|
fn spatial_cell_key(x : Int, y : Int, z : Int) -> String {
  x.to_string() + ":" + y.to_string() + ":" + z.to_string()
}

///|
fn spatial_cell_range(
  bounds : BoundingBox,
  cell_size : Double,
) -> (Int, Int, Int, Int, Int, Int) {
  (
    spatial_cell_coordinate(bounds.min.x, cell_size),
    spatial_cell_coordinate(bounds.max.x, cell_size),
    spatial_cell_coordinate(bounds.min.y, cell_size),
    spatial_cell_coordinate(bounds.max.y, cell_size),
    spatial_cell_coordinate(bounds.min.z, cell_size),
    spatial_cell_coordinate(bounds.max.z, cell_size),
  )
}

///|
fn spatial_add_entry_to_cells(
  cells : Map[String, Array[Int]],
  entry_index : Int,
  bounds : BoundingBox,
  cell_size : Double,
) -> Unit {
  if bounds.empty {
    return
  }
  let (min_x, max_x, min_y, max_y, min_z, max_z) = spatial_cell_range(
    bounds, cell_size,
  )
  for x in min_x..<=max_x {
    for y in min_y..<=max_y {
      for z in min_z..<=max_z {
        let key = spatial_cell_key(x, y, z)
        cells.update_or_default(key, [entry_index], values => {
          if !values.contains(entry_index) {
            values.push(entry_index)
          }
          values
        })
      }
    }
  }
}

///|
/// Build a broad-phase spatial index from transformed product meshes.
pub fn SpatialIndex::new(
  model : Model,
  options? : SpatialIndexOptions = default_spatial_index_options(),
) -> SpatialIndex raise ParseError {
  let index = model.index()
  let products = model.products()
  let entries : Array[SpatialEntry] = []
  let cell_size = spatial_safe_cell_size(options.cell_size)
  let maximum_entries = spatial_safe_limit(options.maximum_entries)
  let mut bounds = BoundingBox::empty()
  for product in products {
    if entries.length() >= maximum_entries {
      break
    }
    let entry = spatial_entry_for_product(index, product)
    if options.include_empty || !entry.bounds.empty {
      let position = entries.length()
      entries.push(entry)
      bounds = merge_bounds(bounds, entry.bounds)
      ignore(position)
    }
  }
  let cells : Map[String, Array[Int]] = Map([])
  for position, entry in entries {
    spatial_add_entry_to_cells(cells, position, entry.bounds, cell_size)
  }
  { entries, cells, bounds, cell_size }
}

///|
pub fn spatial_index(
  model : Model,
  options? : SpatialIndexOptions = default_spatial_index_options(),
) -> SpatialIndex raise ParseError {
  SpatialIndex::new(model, options~)
}

///|
pub fn SpatialIndex::entry(
  self : SpatialIndex,
  product_id : Int,
) -> SpatialEntry? {
  for item in self.entries {
    if item.product_id == product_id {
      return Some(item)
    }
  }
  None
}

///|
pub fn SpatialIndex::entries(self : SpatialIndex) -> Array[SpatialEntry] {
  self.entries.copy()
}

///|
pub fn SpatialIndex::bounds(self : SpatialIndex) -> BoundingBox {
  self.bounds
}

///|
pub fn SpatialIndex::cell_count(self : SpatialIndex) -> Int {
  self.cells.length()
}

///|
pub fn SpatialIndex::cell_size(self : SpatialIndex) -> Double {
  self.cell_size
}

///|
pub fn SpatialIndex::product_ids(self : SpatialIndex) -> Array[Int] {
  self.entries.map(entry => entry.product_id)
}

///|
fn SpatialIndex::candidate_positions(
  self : SpatialIndex,
  bounds : BoundingBox,
) -> Array[Int] {
  if bounds.empty {
    return []
  }
  let (min_x, max_x, min_y, max_y, min_z, max_z) = spatial_cell_range(
    bounds,
    self.cell_size,
  )
  let result : Array[Int] = []
  for x in min_x..<=max_x {
    for y in min_y..<=max_y {
      for z in min_z..<=max_z {
        match self.cells.get(spatial_cell_key(x, y, z)) {
          Some(values) =>
            for value in values {
              if !result.contains(value) {
                result.push(value)
              }
            }
          None => ()
        }
      }
    }
  }
  result
}

///|
fn spatial_hit(
  entry : SpatialEntry,
  query : BoundingBox,
  tolerance : Double,
) -> SpatialHit {
  let overlap = box_intersection(entry.bounds, query)
  {
    product_id: entry.product_id,
    entity_id: entry.entity_id,
    bounds: entry.bounds,
    relation: box_relation(entry.bounds, query, tolerance),
    distance: box_distance(entry.bounds, query),
    overlap_volume: overlap.volume(),
  }
}

///|
pub fn SpatialIndex::query_box(
  self : SpatialIndex,
  query : BoundingBox,
  tolerance? : Double = 0.0,
) -> Array[SpatialHit] {
  let result : Array[SpatialHit] = []
  for position in self.candidate_positions(query) {
    match self.entries.get(position) {
      Some(entry) =>
        match box_relation(entry.bounds, query, tolerance) {
          Disjoint => ()
          _ => result.push(spatial_hit(entry, query, tolerance))
        }
      None => ()
    }
  }
  result
}

///|
pub fn SpatialIndex::query_point(
  self : SpatialIndex,
  point : Point3,
  tolerance? : Double = 0.0,
) -> Array[SpatialHit] {
  let margin = if tolerance < 0.0 { 0.0 } else { tolerance }
  self.query_box(
    {
      min: { x: point.x - margin, y: point.y - margin, z: point.z - margin },
      max: { x: point.x + margin, y: point.y + margin, z: point.z + margin },
      empty: false,
    },
    tolerance=margin,
  )
}

///|
pub fn SpatialIndex::query_range(
  self : SpatialIndex,
  minimum : Point3,
  maximum : Point3,
  tolerance? : Double = 0.0,
) -> Array[SpatialHit] {
  self.query_box(BoundingBox::from_points([minimum, maximum]), tolerance~)
}

///|
pub fn SpatialIndex::nearest(
  self : SpatialIndex,
  point : Point3,
  maximum_distance? : Double = 0.0,
) -> SpatialHit? {
  let mut best : SpatialHit? = None
  let limit = if maximum_distance <= 0.0 { 1.0e300 } else { maximum_distance }
  for entry in self.entries {
    let distance = box_distance(entry.bounds, {
      min: point,
      max: point,
      empty: false,
    })
    if distance <= limit {
      match best {
        Some(current) if current.distance <= distance => ()
        _ =>
          best = Some({
            product_id: entry.product_id,
            entity_id: entry.entity_id,
            bounds: entry.bounds,
            relation: box_relation(
              entry.bounds,
              { min: point, max: point, empty: false },
              0.0,
            ),
            distance,
            overlap_volume: box_intersection(entry.bounds, {
              min: point,
              max: point,
              empty: false,
            }).volume(),
          })
      }
    }
  }
  best
}

///|
pub fn SpatialIndex::within(
  self : SpatialIndex,
  container : BoundingBox,
  tolerance? : Double = 0.0,
) -> Array[SpatialEntry] {
  self.entries.filter(entry => {
    match box_relation(entry.bounds, container, tolerance) {
      Within | Equal => true
      _ => false
    }
  })
}

///|
pub fn SpatialIndex::intersections(
  self : SpatialIndex,
  query : BoundingBox,
  tolerance? : Double = 0.0,
) -> Array[SpatialEntry] {
  self
  .query_box(query, tolerance~)
  .map(hit => self.entry(hit.product_id).unwrap())
}

///|
pub fn SpatialIndex::products_in_container(
  self : SpatialIndex,
  container_id : Int,
) -> Array[SpatialEntry] {
  self.entries.filter(entry => entry.container == Some(container_id))
}

///|
pub fn SpatialIndex::type_histogram(self : SpatialIndex) -> Map[String, Int] {
  self.entries.fold(init=Map([]), (result, entry) => {
    result.update_or_default(entry.ifc_type.to_upper(), 1, count => count + 1)
    result
  })
}

///|
pub fn SpatialIndex::total_triangles(self : SpatialIndex) -> Int {
  self.entries.fold(init=0, (result, entry) => result + entry.triangle_count)
}

///|
pub fn SpatialIndex::total_geometry_count(self : SpatialIndex) -> Int {
  self.entries.fold(init=0, (result, entry) => result + entry.geometry_count)
}

///|
pub fn SpatialIndex::contains_product(
  self : SpatialIndex,
  product_id : Int,
) -> Bool {
  self.entry(product_id) is Some(_)
}

///|
pub fn SpatialIndex::distance_between(
  self : SpatialIndex,
  left_id : Int,
  right_id : Int,
) -> Double? {
  match (self.entry(left_id), self.entry(right_id)) {
    (Some(left), Some(right)) => Some(box_distance(left.bounds, right.bounds))
    _ => None
  }
}

///|
pub fn SpatialIndex::relation_between(
  self : SpatialIndex,
  left_id : Int,
  right_id : Int,
  tolerance? : Double = 0.0,
) -> BoxRelation? {
  match (self.entry(left_id), self.entry(right_id)) {
    (Some(left), Some(right)) =>
      Some(box_relation(left.bounds, right.bounds, tolerance))
    _ => None
  }
}

///|
pub fn SpatialHit::headline(self : SpatialHit) -> String {
  "#" +
  self.product_id.to_string() +
  " distance=" +
  self.distance.to_string() +
  " overlap=" +
  self.overlap_volume.to_string()
}

///|
fn box_relation_name(relation : BoxRelation) -> String {
  match relation {
    Disjoint => "disjoint"
    Touching => "touching"
    Overlapping => "overlapping"
    Contains => "contains"
    Within => "within"
    Equal => "equal"
  }
}

///|
pub fn box_relation_text(relation : BoxRelation) -> String {
  box_relation_name(relation)
}

///|
pub fn SpatialEntry::headline(self : SpatialEntry) -> String {
  let name = self.name.unwrap_or(self.ifc_type)
  name +
  " #" +
  self.product_id.to_string() +
  " " +
  self.bounds.width().to_string() +
  "x" +
  self.bounds.height().to_string() +
  "x" +
  self.bounds.depth().to_string()
}

///|
pub fn SpatialEntry::center(self : SpatialEntry) -> Point3 {
  self.bounds.center()
}

///|
pub fn SpatialEntry::is_empty(self : SpatialEntry) -> Bool {
  self.bounds.empty
}

///|
pub fn SpatialEntry::volume(self : SpatialEntry) -> Double {
  self.bounds.volume()
}

///|
pub fn SpatialIndex::raycast(
  self : SpatialIndex,
  origin : Point3,
  direction : Vector3,
  maximum_distance? : Double = 0.0,
) -> Array[SpatialHit] {
  let length = direction.length()
  if length == 0.0 {
    return []
  }
  let normalized = direction.scale(1.0 / length)
  let limit = if maximum_distance <= 0.0 { 1.0e300 } else { maximum_distance }
  let hits : Array[SpatialHit] = []
  for entry in self.entries {
    match spatial_ray_box_distance(origin, normalized, entry.bounds) {
      Some(distance) if distance <= limit =>
        hits.push({
          product_id: entry.product_id,
          entity_id: entry.entity_id,
          bounds: entry.bounds,
          relation: Overlapping,
          distance,
          overlap_volume: 0.0,
        })
      _ => ()
    }
  }
  spatial_sort_hits(hits)
}

///|
fn spatial_inverse_or_infinity(value : Double) -> Double {
  if value == 0.0 {
    1.0e300
  } else {
    1.0 / value
  }
}

///|
fn spatial_ray_axis(
  origin : Double,
  inverse : Double,
  minimum : Double,
  maximum : Double,
  near : Double,
  far : Double,
) -> (Double, Double) {
  if inverse >= 1.0e299 {
    if origin < minimum || origin > maximum {
      (1.0, 0.0)
    } else {
      (near, far)
    }
  } else {
    let left = (minimum - origin) * inverse
    let right = (maximum - origin) * inverse
    let axis_near = if left < right { left } else { right }
    let axis_far = if left > right { left } else { right }
    (
      if axis_near > near {
        axis_near
      } else {
        near
      },
      if axis_far < far {
        axis_far
      } else {
        far
      },
    )
  }
}

///|
fn spatial_ray_box_distance(
  origin : Point3,
  direction : Vector3,
  bounds : BoundingBox,
) -> Double? {
  if bounds.empty {
    return None
  }
  let inverse_x = spatial_inverse_or_infinity(direction.x)
  let inverse_y = spatial_inverse_or_infinity(direction.y)
  let inverse_z = spatial_inverse_or_infinity(direction.z)
  let (x_near, x_far) = spatial_ray_axis(
    origin.x,
    inverse_x,
    bounds.min.x,
    bounds.max.x,
    0.0,
    1.0e300,
  )
  let (y_near, y_far) = spatial_ray_axis(
    origin.y,
    inverse_y,
    bounds.min.y,
    bounds.max.y,
    x_near,
    x_far,
  )
  let (z_near, z_far) = spatial_ray_axis(
    origin.z,
    inverse_z,
    bounds.min.z,
    bounds.max.z,
    y_near,
    y_far,
  )
  if z_far < z_near || z_far < 0.0 {
    None
  } else if z_near < 0.0 {
    Some(0.0)
  } else {
    Some(z_near)
  }
}

///|
fn spatial_sort_hits(hits : Array[SpatialHit]) -> Array[SpatialHit] {
  let result = hits.copy()
  for i in 0.. SpatialHit? {
  self.raycast(origin, direction, maximum_distance~).get(0)
}

///|
pub fn SpatialIndex::query_sphere(
  self : SpatialIndex,
  center : Point3,
  radius : Double,
) -> Array[SpatialHit] {
  let safe_radius = if radius < 0.0 { 0.0 } else { radius }
  self.entries.fold(init=Array::new(), (result, entry) => {
    let distance = box_distance(entry.bounds, {
      min: center,
      max: center,
      empty: false,
    })
    if distance <= safe_radius {
      result.push({
        product_id: entry.product_id,
        entity_id: entry.entity_id,
        bounds: entry.bounds,
        relation: if distance == 0.0 {
          Overlapping
        } else {
          Touching
        },
        distance,
        overlap_volume: 0.0,
      })
    }
    result
  })
}

///|
pub fn SpatialIndex::bounds_for_products(
  self : SpatialIndex,
  product_ids : Array[Int],
) -> BoundingBox {
  product_ids.fold(init=BoundingBox::empty(), (result, id) => {
    match self.entry(id) {
      Some(entry) => merge_bounds(result, entry.bounds)
      None => result
    }
  })
}

///|
pub fn SpatialIndex::to_json(self : SpatialIndex) -> String {
  let rows = self.entries.map(entry => {
    "{\"product_id\":" +
    entry.product_id.to_string() +
    ",\"type\":\"" +
    entry.ifc_type +
    "\"" +
    ",\"min\":[" +
    entry.bounds.min.x.to_string() +
    "," +
    entry.bounds.min.y.to_string() +
    "," +
    entry.bounds.min.z.to_string() +
    "]" +
    ",\"max\":[" +
    entry.bounds.max.x.to_string() +
    "," +
    entry.bounds.max.y.to_string() +
    "," +
    entry.bounds.max.z.to_string() +
    "]}"
  })
  "{\"cell_size\":" +
  self.cell_size.to_string() +
  ",\"cell_count\":" +
  self.cell_count().to_string() +
  ",\"entries\":[" +
  rows.join(",") +
  "]}"
}