// Ported from topojson-client src/merge.js, ISC. Shared-arc dissolve, not geometric union.

///|
fn polygons(g : Json, out : Array[Json]) -> Unit {
  match kind(g) {
    "Polygon" => out.push(field(g, "arcs"))
    "MultiPolygon" =>
      for p in array(field(g, "arcs")) {
        out.push(p)
      }
    "GeometryCollection" =>
      for c in array(field(g, "geometries")) {
        polygons(c, out)
      }
    _ => ()
  }
}

///|
fn ring_area(points : Array[Array[Double]]) -> Double {
  if points.is_empty() {
    return 0.0
  }
  let mut area = 0.0
  let mut prev = points[points.length() - 1]
  for p in points {
    area += prev[0] * p[1] - prev[1] * p[0]
    prev = p
  }
  area.abs()
}

///|
/// Dissolve polygon boundaries shared by the selected objects, retaining holes.
pub fn Topology::merge_arcs(
  self : Topology,
  names : Array[String],
) -> Json raise TopoError {
  let ps : Array[Json] = []
  for g in self.selected(names) {
    polygons(g, ps)
  }
  let by_arc : Map[Int, Array[Int]] = Map([])
  for k = 0; k < ps.length(); k = k + 1 {
    let refs = []
    refs_flat(ps[k], refs)
    for r in refs {
      let id = arc_id(r)
      let a = by_arc.get(id).unwrap_or([])
      a.push(k)
      by_arc[id] = a
    }
  }
  let seen = Array::make(ps.length(), false)
  let groups : Array[Array[Int]] = []
  for k = 0; k < ps.length(); k = k + 1 {
    if seen[k] {
      continue
    }
    let stack = [k]
    seen[k] = true
    let group = []
    while stack.length() > 0 {
      let i = stack.pop().unwrap()
      group.push(i)
      let refs = []
      refs_flat(ps[i], refs)
      for r in refs {
        for j in by_arc[arc_id(r)] {
          if !seen[j] {
            seen[j] = true
            stack.push(j)
          }
        }
      }
    }
    groups.push(group)
  }
  let output : Array[Array[Array[Int]]] = []
  for group in groups {
    let exterior = []
    for p in group {
      let refs = []
      refs_flat(ps[p], refs)
      for r in refs {
        if by_arc[arc_id(r)].length() < 2 {
          exterior.push(r)
        }
      }
    }
    let rings = self.stitch_refs(exterior)
    if rings.length() == 0 {
      continue
    }
    let mut largest = ring_area(self.line(rings[0].to_json(), 4))
    for i = 1; i < rings.length(); i = i + 1 {
      let area = ring_area(self.line(rings[i].to_json(), 4))
      if area > largest {
        let tmp = rings[0]
        rings[0] = rings[i]
        rings[i] = tmp
        largest = area
      }
    }
    output.push(rings)
  }
  { "type": "MultiPolygon", "arcs": output.to_json() }
}

///|
pub fn Topology::merge(
  self : Topology,
  names : Array[String],
) -> Json raise TopoError {
  self.geometry(self.merge_arcs(names))
}