// Adapted from topojson-client src/stitch.js (ISC). Map flush order is canonicalized.

///|
priv struct Fragment {
  ids : Array[Int]
  start : String
  end : String
}

///|
fn Topology::ends(self : Topology, i : Int) -> (String, String) {
  let ps = array(array(field(self.data, "arcs"))[arc_id(i)])
  let p0 = array(ps[0]).map(number)
  let p1 = if field(self.data, "transform") == Json::null() {
    array(ps[ps.length() - 1]).map(number)
  } else {
    let end = [0.0, 0.0]
    for p in ps {
      let v = array(p)
      end[0] += number(v[0])
      end[1] += number(v[1])
    }
    end
  }
  let a = [p0[0], p0[1]].to_json().stringify()
  let b = [p1[0], p1[1]].to_json().stringify()
  if i < 0 {
    (b, a)
  } else {
    (a, b)
  }
}

///|
fn Topology::stitch_refs(
  self : Topology,
  input : Array[Int],
) -> Array[Array[Int]] {
  let ids = input.copy()
  let mut empty = -1
  let arcs = array(field(self.data, "arcs"))
  for j = 0; j < ids.length(); j = j + 1 {
    let a = array(arcs[arc_id(ids[j])])
    let p = array(a[1])
    if a.length() < 3 && number(p[0]) == 0.0 && number(p[1]) == 0.0 {
      empty += 1
      let tmp = ids[empty]
      ids[empty] = ids[j]
      ids[j] = tmp
    }
  }
  let starts : Map[String, Int] = Map([])
  let ends : Map[String, Int] = Map([])
  let fragments : Array[Fragment] = []
  for i in ids {
    let (start, end) = self.ends(i)
    let next = match ends.get(start) {
      Some(fi) => {
        let f = fragments[fi]
        ends.remove(f.end)
        let joined = f.ids.copy()
        joined.push(i)
        match starts.get(end) {
          Some(gi) => {
            let g = fragments[gi]
            starts.remove(g.start)
            if gi != fi {
              for x in g.ids {
                joined.push(x)
              }
            }
            {
              ids: joined,
              start: f.start,
              end: if gi == fi {
                end
              } else {
                g.end
              },
            }
          }
          None => { ids: joined, start: f.start, end, }
        }
      }
      None =>
        match starts.get(end) {
          Some(fi) => {
            let f = fragments[fi]
            starts.remove(f.start)
            let joined = [i]
            for x in f.ids {
              joined.push(x)
            }
            match ends.get(start) {
              Some(gi) => {
                let g = fragments[gi]
                ends.remove(g.end)
                let combined = if gi == fi {
                  joined
                } else {
                  let a = g.ids.copy()
                  for x in joined {
                    a.push(x)
                  }
                  a
                }
                {
                  ids: combined,
                  start: if gi == fi {
                    start
                  } else {
                    g.start
                  },
                  end: f.end,
                }
              }
              None => { ids: joined, start, end: f.end, }
            }
          }
          None => { ids: [i], start, end, }
        }
    }
    let n = fragments.length()
    fragments.push(next)
    starts[next.start] = n
    ends[next.end] = n
  }
  let out : Array[Array[Int]] = []
  let stitched : Map[Int, Bool] = Map([])
  let keys = ends.keys().collect()
  keys.sort()
  for k in keys {
    let f = fragments[ends[k]]
    starts.remove(f.start)
    for i in f.ids {
      stitched[arc_id(i)] = true
    }
    out.push(f.ids)
  }
  let remaining = starts.keys().collect()
  remaining.sort()
  for k in remaining {
    let f = fragments[starts[k]]
    for i in f.ids {
      stitched[arc_id(i)] = true
    }
    out.push(f.ids)
  }
  for i in ids {
    if !stitched.contains(arc_id(i)) {
      out.push([i])
    }
  }
  out
}

///|
/// Stitch selected signed arcs into connected chains. Arc IDs must be unique ignoring direction.
pub fn Topology::stitch(
  self : Topology,
  ids : Array[Int],
) -> Array[Array[Int]] raise TopoError {
  let n = array(field(self.data, "arcs")).length()
  let seen : Map[Int, Bool] = Map([])
  for i in ids {
    if i < -n || i >= n {
      raise Invalid("arc.index")
    }
    if seen.contains(arc_id(i)) {
      raise Invalid("arc.duplicate")
    }
    seen[arc_id(i)] = true
  }
  self.stitch_refs(ids)
}