// Arc-length parameterised Bézier paths: a port of @davepagurek/bezier-path
// 0.0.7 (MIT), which p5.js uses for `textToPoints` / `textToContours`.

///|
/// A 2D point.
#derive(Debug, Eq)
pub(all) struct Pt {
  x : Double
  y : Double
}

///|
/// A cubic Bézier segment.
pub struct BezierSegment {
  a : Pt
  b : Pt
  c : Pt
  d : Pt
  priv mut total : Double?
}

///|
pub fn BezierSegment::new(a : Pt, b : Pt, c : Pt, d : Pt) -> BezierSegment {
  { a, b, c, d, total: None, }
}

///|
fn normalize(x : Double, y : Double) -> Pt {
  let h = hypot(x, y)
  if h.abs() > 1.0e-4 {
    { x: x / h, y: y / h, }
  } else {
    { x, y, }
  }
}

///|
/// Unit tangent at parameter `t` (clamped to [0, 1]).
pub fn BezierSegment::tangent_at(
  self : BezierSegment,
  parameter : Double,
) -> Pt {
  let t = parameter.clamp(min=0, max=1)
  let { a, b, c, d, .. } = self
  if t == 0 {
    if a.x == b.x && a.y == b.y {
      normalize(c.x - a.x, c.y - a.y)
    } else {
      normalize(b.x - a.x, b.y - a.y)
    }
  } else if t == 1 {
    if d.x == c.x && d.y == c.y {
      normalize(d.x - b.x, d.y - b.y)
    } else {
      normalize(d.x - c.x, d.y - c.y)
    }
  } else {
    let u = 1.0 - t
    let x = 3.0 * d.x * pow(t, 2) -
      3.0 * c.x * pow(t, 2) +
      6.0 * c.x * u * t -
      6.0 * b.x * u * t +
      3.0 * b.x * pow(u, 2) -
      3.0 * a.x * pow(u, 2)
    let y = 3.0 * d.y * pow(t, 2) -
      3.0 * c.y * pow(t, 2) +
      6.0 * c.y * u * t -
      6.0 * b.y * u * t +
      3.0 * b.y * pow(u, 2) -
      3.0 * a.y * pow(u, 2)
    normalize(x, y)
  }
}

///|
fn BezierSegment::is_linear(self : BezierSegment) -> Bool {
  self.a.x == self.b.x &&
  self.a.y == self.b.y &&
  self.c.x == self.d.x &&
  self.c.y == self.d.y
}

///|
/// The point at parameter `t` (clamped to [0, 1]).
pub fn BezierSegment::point_at(self : BezierSegment, parameter : Double) -> Pt {
  let t = parameter.clamp(min=0, max=1)
  let { a, b, c, d, .. } = self
  {
    x: pow(1.0 - t, 3) * a.x +
    3.0 * pow(1.0 - t, 2) * t * b.x +
    3.0 * (1.0 - t) * pow(t, 2) * c.x +
    pow(t, 3) * d.x,
    y: pow(1.0 - t, 3) * a.y +
    3.0 * pow(1.0 - t, 2) * t * b.y +
    3.0 * (1.0 - t) * pow(t, 2) * c.y +
    pow(t, 3) * d.y,
  }
}

///|
/// Approximate arc length.
pub fn BezierSegment::total_length(self : BezierSegment) -> Double {
  match self.total {
    Some(l) => l
    None => {
      let l = if self.is_linear() {
        hypot(self.d.x - self.a.x, self.d.y - self.a.y)
      } else {
        let hull = hypot(self.b.x - self.a.x, self.b.y - self.a.y) +
          hypot(self.c.x - self.b.x, self.c.y - self.b.y) +
          hypot(self.d.x - self.c.x, self.d.y - self.c.y)
        let n = @cmath.ceil(hull / 2).to_int().max(10)
        let pts = [
          for i in 0.. self.point_at(i.to_double() / (n - 1).to_double())
        ]
        let mut total = 0.0
        for i in 1.. BezierPath {
  let samples : Array[Sample] = []
  if segments.is_empty() {
    return { segments, samples, total: @double.not_a_number, }
  }
  let lengths = segments.map(s => s.total_length())
  let offsets = [0.0]
  for i in 1.. {
    @cmath.ceil(s.total_length() / 2).to_int().max(4)
  })
  let num_samples = seg_samples.fold(init=0, (a, b) => a + b)
  let step = 1.0 / num_samples.to_double() / 10
  let avg = total / num_samples.to_double()
  samples.push({
    dist: 0,
    pt: segments[0].a,
    tan: segments[0].tangent_at(0),
    seg: 0,
    t: 0,
  })
  for si, seg in segments {
    let n = seg_samples[si]
    let ts = [ for i in 0..<=n => i.to_double() / n.to_double() ]
    let pts = ts.map(t => seg.point_at(t))
    let mut dists : Array[Double] = []
    for _ in 0..<4 {
      dists = [
        for i in 0.. {
          hypot(pts[i + 1].x - pts[i].x, pts[i + 1].y - pts[i].y)
        }
      ]
      let mut offset = 0.0
      for i in 1..<(ts.length() - 1) {
        offset += dists[i - 1] - avg
        ts[i] -= step * offset
        pts[i] = seg.point_at(ts[i])
      }
    }
    let mut last = 0.0
    for i in 0.. BezierPath {
  let segments : Array[BezierSegment] = []
  let mut k = 0
  let mut last : Pt = { x: 0, y: 0, }
  let mut first = last
  for cmd in cmds {
    match cmd {
      M => {
        first = { x: crds[k], y: crds[k + 1], }
        last = first
        k += 2
      }
      L => {
        let p = { x: crds[k], y: crds[k + 1], }
        if p.x != last.x || p.y != last.y {
          segments.push(BezierSegment::new(last, last, p, p))
        }
        last = p
        k += 2
      }
      Q => {
        let x1 = crds[k]
        let y1 = crds[k + 1]
        let p = { x: crds[k + 2], y: crds[k + 3], }
        segments.push(
          BezierSegment::new(
            last,
            {
              x: last.x + 2.0 / 3.0 * (x1 - last.x),
              y: last.y + 2.0 / 3.0 * (y1 - last.y),
            },
            {
              x: p.x + 2.0 / 3.0 * (x1 - p.x),
              y: p.y + 2.0 / 3.0 * (y1 - p.y),
            },
            p,
          ),
        )
        last = p
        k += 4
      }
      C => {
        let p = { x: crds[k + 4], y: crds[k + 5], }
        segments.push(
          BezierSegment::new(
            last,
            { x: crds[k], y: crds[k + 1], },
            { x: crds[k + 2], y: crds[k + 3], },
            p,
          ),
        )
        last = p
        k += 6
      }
      Z =>
        if hypot(last.x - first.x, last.y - first.y) > 0 {
          segments.push(BezierSegment::new(last, last, first, first))
        }
    }
  }
  BezierPath::new(segments)
}

///|
/// Total arc length (NaN for an empty path, as in JS).
pub fn BezierPath::total_length(self : BezierPath) -> Double {
  self.total
}

///|
fn BezierPath::closest_sample(self : BezierPath, dist : Double) -> Int32 {
  let s = self.samples
  let mut lo = 0
  let mut hi = s.length() - 1
  while lo < hi {
    let mid = (lo + hi) / 2
    if s[mid].dist > dist {
      hi = mid - 1
    } else if s[mid].dist < dist {
      lo = mid + 1
    } else {
      return mid
    }
  }
  ((lo + hi) / 2).clamp(min=0, max=s.length() - 1)
}

///|
fn BezierPath::pair(self : BezierPath, length : Double) -> (Sample, Sample) {
  let ia = self.closest_sample(length)
  let ib = if self.samples[ia].dist < length {
    (ia + 1).min(self.samples.length() - 1)
  } else {
    (ia - 1).max(0)
  }
  (self.samples[ia], self.samples[ib])
}

///|
/// The point `length` along the path.
pub fn BezierPath::point_at_length(self : BezierPath, length : Double) -> Pt {
  if length <= 0 {
    return self.samples[0].pt
  }
  if length >= self.total {
    return self.samples[self.samples.length() - 1].pt
  }
  let (a, b) = self.pair(length)
  let mix = if (b.dist - a.dist).abs() < 1.0e-6 {
    0.0
  } else {
    (length - a.dist) / (b.dist - a.dist)
  }
  if a.seg > b.seg {
    {
      x: (1.0 - mix) * a.pt.x + mix * b.pt.x,
      y: (1.0 - mix) * a.pt.y + mix * b.pt.y,
    }
  } else if a.seg != b.seg {
    let t_diff = 1.0 - a.t + b.t
    let mix_mid = if t_diff > 0 { (1.0 - a.t) / t_diff } else { 0.5 }
    if mix < mix_mid {
      let ma = mix / mix_mid
      self.segments[a.seg].point_at((1.0 - ma) * a.t + ma)
    } else {
      let mb = (mix - mix_mid) / (1.0 - mix_mid)
      self.segments[b.seg].point_at(mb * b.t)
    }
  } else {
    self.segments[a.seg].point_at((1.0 - mix) * a.t + mix * b.t)
  }
}

///|
/// The unit tangent `length` along the path.
pub fn BezierPath::tangent_at_length(self : BezierPath, length : Double) -> Pt {
  if length <= 0 {
    return self.samples[0].tan
  }
  if length >= self.total {
    return self.samples[self.samples.length() - 1].tan
  }
  let (a, b) = self.pair(length)
  let mix = (length - a.dist) / (b.dist - a.dist)
  if a.seg > b.seg {
    let x = (1.0 - mix) * a.tan.x + mix * b.tan.x
    let y = (1.0 - mix) * a.tan.y + mix * b.tan.y
    let h = hypot(x, y).max(1.0e-4)
    { x: x / h, y: y / h, }
  } else if a.seg != b.seg {
    if mix < 0.5 {
      let ma = 2.0 * mix
      self.segments[a.seg].tangent_at((1.0 - ma) * a.t + ma)
    } else {
      let mb = 2.0 * (mix - 0.5)
      self.segments[b.seg].tangent_at(mb * b.t)
    }
  } else {
    self.segments[a.seg].tangent_at((1.0 - mix) * a.t + mix * b.t)
  }
}

///|
/// The tangent angle (radians) `length` along the path.
pub fn BezierPath::angle_at_length(
  self : BezierPath,
  length : Double,
) -> Double {
  let t = self.tangent_at_length(length)
  atan2(t.y, t.x)
}