///|
fn scene_chunk_from_entries(
  entries : Array[SpatialEntry],
  index : Int,
) -> SceneChunk {
  {
    index,
    product_ids: entries.map(entry => entry.product_id),
    bounds: entries.fold(init=BoundingBox::empty(), (result, entry) => {
      merge_bounds(result, entry.bounds)
    }),
    point_count: entries.fold(init=0, (result, entry) => {
      result + entry.point_count
    }),
    triangle_count: entries.fold(init=0, (result, entry) => {
      result + entry.triangle_count
    }),
  }
}

///|
fn scene_partition_chunks(
  entries : Array[SpatialEntry],
  chunk_size : Int,
) -> Array[SceneChunk] {
  let chunks : Array[SceneChunk] = []
  let safe_size = if chunk_size <= 0 { 128 } else { chunk_size }
  let mut offset = 0
  let mut index = 0
  while offset < entries.length() {
    let end = if offset + safe_size > entries.length() {
      entries.length()
    } else {
      offset + safe_size
    }
    chunks.push(scene_chunk_from_entries(entries[offset:end].to_owned(), index))
    offset = end
    index += 1
  }
  chunks
}

///|
/// Partition the indexed product space into bounded render chunks.
pub fn scene_partition(
  model : Model,
  chunk_size? : Int = 128,
) -> ScenePartition raise ParseError {
  let spatial = SpatialIndex::new(model)
  let chunks = scene_partition_chunks(spatial.entries(), chunk_size)
  {
    chunks,
    bounds: spatial.bounds(),
    chunk_size: if chunk_size <= 0 {
      128
    } else {
      chunk_size
    },
    product_count: spatial.entries().length(),
  }
}

///|
pub fn SceneChunk::is_empty(self : SceneChunk) -> Bool {
  self.product_ids.length() == 0
}

///|
pub fn SceneChunk::product_count(self : SceneChunk) -> Int {
  self.product_ids.length()
}

///|
pub fn SceneChunk::contains_product(self : SceneChunk, id : Int) -> Bool {
  self.product_ids.contains(id)
}

///|
pub fn SceneChunk::intersects(
  self : SceneChunk,
  bounds : BoundingBox,
  tolerance? : Double = 0.0,
) -> Bool {
  box_relation(self.bounds, bounds, tolerance) != Disjoint
}

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

///|
pub fn SceneChunk::headline(self : SceneChunk) -> String {
  "chunk=" +
  self.index.to_string() +
  " products=" +
  self.product_ids.length().to_string() +
  " triangles=" +
  self.triangle_count.to_string() +
  " volume=" +
  self.bounds.volume().to_string()
}

///|
pub fn ScenePartition::chunk(self : ScenePartition, index : Int) -> SceneChunk? {
  self.chunks.get(index)
}

///|
pub fn ScenePartition::chunk_for_product(
  self : ScenePartition,
  id : Int,
) -> SceneChunk? {
  for chunk in self.chunks {
    if chunk.contains_product(id) {
      return Some(chunk)
    }
  }
  None
}

///|
pub fn ScenePartition::chunks_intersecting(
  self : ScenePartition,
  bounds : BoundingBox,
  tolerance? : Double = 0.0,
) -> Array[SceneChunk] {
  self.chunks.filter(chunk => chunk.intersects(bounds, tolerance~))
}

///|
pub fn ScenePartition::chunks_at_point(
  self : ScenePartition,
  point : Point3,
  tolerance? : Double = 0.0,
) -> Array[SceneChunk] {
  self.chunks_intersecting({ min: point, max: point, empty: false }, tolerance~)
}

///|
pub fn ScenePartition::largest_chunk(self : ScenePartition) -> SceneChunk? {
  let mut result : SceneChunk? = None
  for chunk in self.chunks {
    match result {
      Some(current) if current.product_ids.length() >=
        chunk.product_ids.length() => ()
      _ => result = Some(chunk)
    }
  }
  result
}

///|
pub fn ScenePartition::chunk_count(self : ScenePartition) -> Int {
  self.chunks.length()
}

///|
pub fn ScenePartition::average_products_per_chunk(
  self : ScenePartition,
) -> Double {
  if self.chunks.length() == 0 {
    0.0
  } else {
    self.product_count.to_double() / self.chunks.length().to_double()
  }
}

///|
pub fn ScenePartition::product_ids(self : ScenePartition) -> Array[Int] {
  self.chunks.fold(init=Array::new(), (result, chunk) => {
    result.append(chunk.product_ids)
    result
  })
}

///|
pub fn ScenePartition::headline(self : ScenePartition) -> String {
  "chunks=" +
  self.chunks.length().to_string() +
  " products=" +
  self.product_count.to_string() +
  " chunk_size=" +
  self.chunk_size.to_string() +
  " bounds_volume=" +
  self.bounds.volume().to_string()
}

///|
pub fn ScenePartition::to_json(self : ScenePartition) -> String {
  let chunks = self.chunks
    .map(chunk => {
      "{\"index\":" +
      chunk.index.to_string() +
      ",\"product_ids\":[" +
      chunk.product_ids.map(id => id.to_string()).join(",") +
      "],\"triangle_count\":" +
      chunk.triangle_count.to_string() +
      ",\"bounds\":" +
      mesh_bounds_json({
        points: [chunk.bounds.min, chunk.bounds.max],
        triangles: [],
      }) +
      "}"
    })
    .join(",")
  "{\"chunk_size\":" +
  self.chunk_size.to_string() +
  ",\"product_count\":" +
  self.product_count.to_string() +
  ",\"chunks\":[" +
  chunks +
  "]}"
}

///|
pub fn ScenePartition::to_markdown(self : ScenePartition) -> String {
  let builder = StringBuilder()
  builder <+ "# Scene partition\n\n"
  builder <+ "- Chunks: \{self.chunks.length()}\n"
  builder <+ "- Products: \{self.product_count}\n"
  builder <+ "- Chunk size: \{self.chunk_size}\n"
  builder <+ "- Average products: \{self.average_products_per_chunk()}\n\n"
  builder <+ "| Chunk | Products | Triangles | Volume |\n"
  builder <+ "| ---: | ---: | ---: | ---: |\n"
  for chunk in self.chunks {
    builder <+
      "| \{chunk.index} | \{chunk.product_ids.length()} | \{chunk.triangle_count} | \{chunk.bounds.volume()} |\n"
  }
  builder.to_string()
}

///|
pub fn scene_partition_for_products(
  spatial : SpatialIndex,
  product_ids : Array[Int],
  chunk_size? : Int = 128,
) -> ScenePartition {
  let entries = spatial
    .entries()
    .filter(entry => product_ids.contains(entry.product_id))
  let chunks = scene_partition_chunks(entries, chunk_size)
  {
    chunks,
    bounds: entries.fold(init=BoundingBox::empty(), (result, entry) => {
      merge_bounds(result, entry.bounds)
    }),
    chunk_size: if chunk_size <= 0 {
      128
    } else {
      chunk_size
    },
    product_count: entries.length(),
  }
}

///|
pub fn scene_partition_product_chunk_counts(
  partition : ScenePartition,
) -> Map[Int, Int] {
  partition.chunks.fold(init=Map([]), (result, chunk) => {
    for id in chunk.product_ids {
      result[id] = chunk.index
    }
    result
  })
}

///|
pub fn scene_partition_bounds(
  partition : ScenePartition,
  indices : Array[Int],
) -> BoundingBox {
  indices.fold(init=BoundingBox::empty(), (result, index) => {
    match partition.chunk(index) {
      Some(chunk) => merge_bounds(result, chunk.bounds)
      None => result
    }
  })
}