// Ports ClipperBase of Clipper2 2.0.1 src/clipper.engine.cpp (commit 642390d),
// Boost Software License 1.0, Copyright (c) Angus Johnson 2010-2026. See NOTICE.

///|
/// Clipper2's sweep-line engine (`ClipperBase` and `Clipper64`): add subject
/// and clip paths, then `execute` a boolean operation.
pub struct Clipper64 {
  priv mut cliptype : ClipType
  priv mut fillrule : FillRule
  priv mut bot_y : Int64
  priv mut minima_list_sorted : Bool
  priv mut using_polytree : Bool
  priv mut actives : Active?
  priv mut sel : Active?
  priv minima_list : Array[LocalMinima]
  priv mut current_locmin : Int32
  priv scanlines : Array[Int64]
  priv intersect_nodes : Array[IntersectNode]
  priv horz_seg_list : Array[HorzSegment]
  priv horz_join_list : Array[HorzJoin]
  priv mut preserve_collinear : Bool
  priv mut reverse_solution : Bool
  priv mut has_open_paths : Bool
  priv mut succeeded : Bool
  priv outrec_list : Array[OutRec]
}

///|
pub fn Clipper64::new() -> Clipper64 {
  {
    cliptype: NoClip,
    fillrule: EvenOdd,
    bot_y: 0L,
    minima_list_sorted: false,
    using_polytree: false,
    actives: None,
    sel: None,
    minima_list: [],
    current_locmin: 0,
    scanlines: [],
    intersect_nodes: [],
    horz_seg_list: [],
    horz_join_list: [],
    preserve_collinear: true,
    reverse_solution: false,
    has_open_paths: false,
    succeeded: true,
    outrec_list: [],
  }
}

///|
/// Whether collinear edges are kept in solutions (default true; 180° spikes
/// are always removed).
pub fn Clipper64::set_preserve_collinear(self : Clipper64, v : Bool) -> Unit {
  self.preserve_collinear = v
}

///|
/// Whether solutions are wound the other way round.
pub fn Clipper64::set_reverse_solution(self : Clipper64, v : Bool) -> Unit {
  self.reverse_solution = v
}

///|
fn Clipper64::clean_up(self : Clipper64) -> Unit {
  self.actives = None
  self.scanlines.clear()
  self.intersect_nodes.clear()
  self.outrec_list.clear()
  self.horz_seg_list.clear()
  self.horz_join_list.clear()
}

///|
/// Forgets every added path.
pub fn Clipper64::clear(self : Clipper64) -> Unit {
  self.clean_up()
  self.minima_list.clear()
  self.current_locmin = 0
  self.minima_list_sorted = false
  self.has_open_paths = false
}

///|
fn Clipper64::reset(self : Clipper64) -> Unit {
  if !self.minima_list_sorted {
    stable_sort(self.minima_list, (a, b) => {
      if b.vertex.pt.y != a.vertex.pt.y {
        b.vertex.pt.y < a.vertex.pt.y
      } else {
        b.vertex.pt.x > a.vertex.pt.x
      }
    })
    self.minima_list_sorted = true
  }
  for i = self.minima_list.length() - 1; i >= 0; i = i - 1 {
    self.insert_scanline(self.minima_list[i].vertex.pt.y)
  }
  self.current_locmin = 0
  self.actives = None
  self.sel = None
  self.succeeded = true
}

///|
/// Adds `v` to the scanline max-heap (`std::priority_queue`).
fn Clipper64::insert_scanline(self : Clipper64, y : Int64) -> Unit {
  let h = self.scanlines
  h.push(y)
  let mut i = h.length() - 1
  while i > 0 {
    let parent = (i - 1) / 2
    if h[parent] >= h[i] {
      break
    }
    let t = h[parent]
    h[parent] = h[i]
    h[i] = t
    i = parent
  }
}

///|
fn Clipper64::pop_heap(self : Clipper64) -> Int64 {
  let h = self.scanlines
  let top = h[0]
  let last = h.pop().unwrap()
  if h.length() > 0 {
    h[0] = last
    let n = h.length()
    let mut i = 0
    while true {
      let l = i * 2 + 1
      let r = l + 1
      let mut m = i
      if l < n && h[l] > h[m] {
        m = l
      }
      if r < n && h[r] > h[m] {
        m = r
      }
      if m == i {
        break
      }
      let t = h[m]
      h[m] = h[i]
      h[i] = t
      i = m
    }
  }
  top
}

///|
fn Clipper64::pop_scanline(self : Clipper64) -> Int64? {
  if self.scanlines.is_empty() {
    return None
  }
  let y = self.pop_heap()
  while !self.scanlines.is_empty() && self.scanlines[0] == y {
    self.pop_heap() |> ignore
  }
  Some(y)
}

///|
fn Clipper64::pop_local_minima(self : Clipper64, y : Int64) -> LocalMinima? {
  if self.current_locmin == self.minima_list.length() ||
    self.minima_list[self.current_locmin].vertex.pt.y != y {
    return None
  }
  let m = self.minima_list[self.current_locmin]
  self.current_locmin += 1
  Some(m)
}

///|
fn add_loc_min(
  list : Array[LocalMinima],
  vert : Vertex,
  polytype : PathType,
  is_open : Bool,
) -> Unit {
  if (vert.flags & VERTEX_LOCAL_MIN) != 0 {
    return
  }
  vert.flags = vert.flags | VERTEX_LOCAL_MIN
  list.push({ vertex: vert, polytype, is_open, })
}

///|
/// Links each path's points into a ring of vertices (duplicates dropped) and
/// records its local minima (`AddPaths_`).
fn add_paths_(
  paths : Array[Array[Point64]],
  polytype : PathType,
  is_open : Bool,
  loc_min_list : Array[LocalMinima],
) -> Unit {
  for path in paths {
    if path.is_empty() {
      continue
    }
    let mut v0 : Vertex? = None
    let mut prev_v : Vertex? = None
    let mut cnt = 0
    for pt in path {
      if prev_v is Some(p) && p.pt == pt {
        continue
      }
      let curr_v = { pt, next: None, prev: prev_v, flags: 0, }
      if prev_v is Some(p) {
        p.next = Some(curr_v)
      }
      if v0 is None {
        v0 = Some(curr_v)
      }
      prev_v = Some(curr_v)
      cnt += 1
    }
    guard prev_v is Some(last) && last.prev is Some(_) else { continue }
    let v0 = v0.unwrap()
    let mut last = last
    if !is_open && last.pt == v0.pt {
      last = last.p()
    }
    last.next = Some(v0)
    v0.prev = Some(last)
    if cnt < 2 || (cnt == 2 && !is_open) {
      continue
    }
    let mut going_up = false
    if is_open {
      let mut curr_v = v0.n()
      while !physical_equal(curr_v, v0) && curr_v.pt.y == v0.pt.y {
        curr_v = curr_v.n()
      }
      going_up = curr_v.pt.y <= v0.pt.y
      if going_up {
        v0.flags = VERTEX_OPEN_START
        add_loc_min(loc_min_list, v0, polytype, true)
      } else {
        v0.flags = VERTEX_OPEN_START | VERTEX_LOCAL_MAX
      }
    } else {
      let mut p = v0.p()
      while !physical_equal(p, v0) && p.pt.y == v0.pt.y {
        p = p.p()
      }
      if physical_equal(p, v0) {
        continue
      }
      going_up = p.pt.y > v0.pt.y
    }
    let going_up0 = going_up
    let mut prev = v0
    let mut curr = v0.n()
    while !physical_equal(curr, v0) {
      if curr.pt.y > prev.pt.y && going_up {
        prev.flags = prev.flags | VERTEX_LOCAL_MAX
        going_up = false
      } else if curr.pt.y < prev.pt.y && !going_up {
        going_up = true
        add_loc_min(loc_min_list, prev, polytype, is_open)
      }
      prev = curr
      curr = curr.n()
    }
    if is_open {
      prev.flags = prev.flags | VERTEX_OPEN_END
      if going_up {
        prev.flags = prev.flags | VERTEX_LOCAL_MAX
      } else {
        add_loc_min(loc_min_list, prev, polytype, is_open)
      }
    } else if going_up != going_up0 {
      if going_up0 {
        add_loc_min(loc_min_list, prev, polytype, false)
      } else {
        prev.flags = prev.flags | VERTEX_LOCAL_MAX
      }
    }
  }
}

///|
fn Clipper64::add_paths_of(
  self : Clipper64,
  paths : Array[Array[Point64]],
  polytype : PathType,
  is_open : Bool,
) -> Unit {
  if is_open {
    self.has_open_paths = true
  }
  self.minima_list_sorted = false
  add_paths_(paths, polytype, is_open, self.minima_list)
}

///|
/// Adds closed subject paths.
pub fn Clipper64::add_subject(
  self : Clipper64,
  paths : Array[Array[Point64]],
) -> Unit {
  self.add_paths_of(paths, Subject, false)
}

///|
/// Adds open subject paths (polylines).
pub fn Clipper64::add_open_subject(
  self : Clipper64,
  paths : Array[Array[Point64]],
) -> Unit {
  self.add_paths_of(paths, Subject, true)
}

///|
/// Adds clip paths (always closed).
pub fn Clipper64::add_clip(
  self : Clipper64,
  paths : Array[Array[Point64]],
) -> Unit {
  self.add_paths_of(paths, Clip, false)
}

///|
fn Clipper64::is_contributing_closed(self : Clipper64, e : Active) -> Bool {
  match self.fillrule {
    EvenOdd => ()
    NonZero => if e.wind_cnt.abs() != 1 { return false }
    Positive => if e.wind_cnt != 1 { return false }
    Negative => if e.wind_cnt != -1 { return false }
  }
  match self.cliptype {
    NoClip => false
    Intersection =>
      match self.fillrule {
        Positive => e.wind_cnt2 > 0
        Negative => e.wind_cnt2 < 0
        _ => e.wind_cnt2 != 0
      }
    Union =>
      match self.fillrule {
        Positive => e.wind_cnt2 <= 0
        Negative => e.wind_cnt2 >= 0
        _ => e.wind_cnt2 == 0
      }
    Difference => {
      let result = match self.fillrule {
        Positive => e.wind_cnt2 <= 0
        Negative => e.wind_cnt2 >= 0
        _ => e.wind_cnt2 == 0
      }
      if get_poly_type(e) == Subject {
        result
      } else {
        !result
      }
    }
    Xor => true
  }
}

///|
fn Clipper64::is_contributing_open(self : Clipper64, e : Active) -> Bool {
  let (is_in_clip, is_in_subj) = match self.fillrule {
    Positive => (e.wind_cnt2 > 0, e.wind_cnt > 0)
    Negative => (e.wind_cnt2 < 0, e.wind_cnt < 0)
    _ => (e.wind_cnt2 != 0, e.wind_cnt != 0)
  }
  match self.cliptype {
    Intersection => is_in_clip
    Union => !is_in_subj && !is_in_clip
    _ => !is_in_clip
  }
}

///|
/// Sets `e`'s winding counts: its own polytype's (the higher of the two
/// regions it borders) and the other polytype's.
fn Clipper64::set_wind_count_for_closed_path_edge(
  self : Clipper64,
  e : Active,
) -> Unit {
  let mut e2 = e.prev_in_ael
  let pt = get_poly_type(e)
  while e2 is Some(a) && (get_poly_type(a) != pt || is_open(a)) {
    e2 = a.prev_in_ael
  }
  match e2 {
    None => {
      e.wind_cnt = e.wind_dx
      e2 = self.actives
    }
    Some(a) if self.fillrule == EvenOdd => {
      e.wind_cnt = e.wind_dx
      e.wind_cnt2 = a.wind_cnt2
      e2 = a.next_in_ael
    }
    Some(a) => {
      if a.wind_cnt * a.wind_dx < 0 {
        if a.wind_cnt.abs() > 1 {
          if a.wind_dx * e.wind_dx < 0 {
            e.wind_cnt = a.wind_cnt
          } else {
            e.wind_cnt = a.wind_cnt + e.wind_dx
          }
        } else {
          e.wind_cnt = if is_open(e) { 1 } else { e.wind_dx }
        }
      } else if a.wind_dx * e.wind_dx < 0 {
        e.wind_cnt = a.wind_cnt
      } else {
        e.wind_cnt = a.wind_cnt + e.wind_dx
      }
      e.wind_cnt2 = a.wind_cnt2
      e2 = a.next_in_ael
    }
  }
  if self.fillrule == EvenOdd {
    while e2 is Some(a) && !physical_equal(a, e) {
      if get_poly_type(a) != pt && !is_open(a) {
        e.wind_cnt2 = if e.wind_cnt2 == 0 { 1 } else { 0 }
      }
      e2 = a.next_in_ael
    }
  } else {
    while e2 is Some(a) && !physical_equal(a, e) {
      if get_poly_type(a) != pt && !is_open(a) {
        e.wind_cnt2 += a.wind_dx
      }
      e2 = a.next_in_ael
    }
  }
}

///|
fn Clipper64::set_wind_count_for_open_path_edge(
  self : Clipper64,
  e : Active,
) -> Unit {
  let mut e2 = self.actives
  if self.fillrule == EvenOdd {
    let mut cnt1 = 0
    let mut cnt2 = 0
    while e2 is Some(a) && !physical_equal(a, e) {
      if get_poly_type(a) == Clip {
        cnt2 += 1
      } else if !is_open(a) {
        cnt1 += 1
      }
      e2 = a.next_in_ael
    }
    e.wind_cnt = if cnt1 % 2 != 0 { 1 } else { 0 }
    e.wind_cnt2 = if cnt2 % 2 != 0 { 1 } else { 0 }
  } else {
    while e2 is Some(a) && !physical_equal(a, e) {
      if get_poly_type(a) == Clip {
        e.wind_cnt2 += a.wind_dx
      } else if !is_open(a) {
        e.wind_cnt += a.wind_dx
      }
      e2 = a.next_in_ael
    }
  }
}

///|
/// Whether `newcomer` belongs to the right of `resident` in the AEL.
fn is_valid_ael_order(resident : Active, newcomer : Active) -> Bool {
  if newcomer.curr_x != resident.curr_x {
    return newcomer.curr_x > resident.curr_x
  }
  let i = cross_product_sign(resident.top, newcomer.bot, newcomer.top)
  if i != 0 {
    return i < 0
  }
  if !is_maxima(resident) && resident.top.y > newcomer.top.y {
    return cross_product_sign(
        newcomer.bot,
        resident.top,
        next_vertex(resident).pt,
      ) <=
      0
  } else if !is_maxima(newcomer) && newcomer.top.y > resident.top.y {
    return cross_product_sign(
        newcomer.bot,
        newcomer.top,
        next_vertex(newcomer).pt,
      ) >=
      0
  }
  let y = newcomer.bot.y
  let newcomer_is_left = newcomer.is_left_bound
  if resident.bot.y != y || resident.local_min.vertex.pt.y != y {
    newcomer.is_left_bound
  } else if resident.is_left_bound != newcomer_is_left {
    newcomer_is_left
  } else if is_collinear(
      prev_prev_vertex(resident).pt,
      resident.bot,
      resident.top,
    ) {
    true
  } else {
    (
      cross_product_sign(
        prev_prev_vertex(resident).pt,
        newcomer.bot,
        prev_prev_vertex(newcomer).pt,
      ) >
      0
    ) ==
    newcomer_is_left
  }
}

///|
fn Clipper64::insert_left_edge(self : Clipper64, e : Active) -> Unit {
  match self.actives {
    None => {
      e.prev_in_ael = None
      e.next_in_ael = None
      self.actives = Some(e)
    }
    Some(first) if !is_valid_ael_order(first, e) => {
      e.prev_in_ael = None
      e.next_in_ael = Some(first)
      first.prev_in_ael = Some(e)
      self.actives = Some(e)
    }
    Some(first) => {
      let mut e2 = first
      while e2.next_in_ael is Some(n) && is_valid_ael_order(n, e) {
        e2 = n
      }
      if e2.join_with == Right {
        guard e2.next_in_ael is Some(n) else { return }
        e2 = n
      }
      e.next_in_ael = e2.next_in_ael
      if e2.next_in_ael is Some(n) {
        n.prev_in_ael = Some(e)
      }
      e.prev_in_ael = Some(e2)
      e2.next_in_ael = Some(e)
    }
  }
}

///|
fn insert_right_edge(e : Active, e2 : Active) -> Unit {
  e2.next_in_ael = e.next_in_ael
  if e.next_in_ael is Some(n) {
    n.prev_in_ael = Some(e2)
  }
  e2.prev_in_ael = Some(e)
  e.next_in_ael = Some(e2)
}

///|
fn new_bound(
  local_minima : LocalMinima,
  wind_dx : Int32,
  vertex_top : Vertex,
) -> Active {
  let a : Active = {
    bot: local_minima.vertex.pt,
    top: vertex_top.pt,
    curr_x: local_minima.vertex.pt.x,
    dx: 0.0,
    wind_dx,
    wind_cnt: 0,
    wind_cnt2: 0,
    outrec: None,
    prev_in_ael: None,
    next_in_ael: None,
    prev_in_sel: None,
    next_in_sel: None,
    jump: None,
    vertex_top,
    local_min: local_minima,
    is_left_bound: false,
    join_with: NoJoin,
  }
  set_dx(a)
  a
}

///|
fn Clipper64::insert_local_minima_into_ael(
  self : Clipper64,
  bot_y : Int64,
) -> Unit {
  while self.pop_local_minima(bot_y) is Some(local_minima) {
    let mut left_bound = if (local_minima.vertex.flags & VERTEX_OPEN_START) != 0 {
      None
    } else {
      Some(new_bound(local_minima, -1, local_minima.vertex.p()))
    }
    let mut right_bound = if (local_minima.vertex.flags & VERTEX_OPEN_END) != 0 {
      None
    } else {
      Some(new_bound(local_minima, 1, local_minima.vertex.n()))
    }
    match (left_bound, right_bound) {
      (Some(l), Some(r)) =>
        if is_horizontal(l) {
          if is_heading_right_horz(l) {
            left_bound = Some(r)
            right_bound = Some(l)
          }
        } else if is_horizontal(r) {
          if is_heading_left_horz(r) {
            left_bound = Some(r)
            right_bound = Some(l)
          }
        } else if l.dx < r.dx {
          left_bound = Some(r)
          right_bound = Some(l)
        }
      (None, _) => {
        left_bound = right_bound
        right_bound = None
      }
      _ => ()
    }
    let left = left_bound.unwrap()
    left.is_left_bound = true
    self.insert_left_edge(left)
    let contributing = if is_open(left) {
      self.set_wind_count_for_open_path_edge(left)
      self.is_contributing_open(left)
    } else {
      self.set_wind_count_for_closed_path_edge(left)
      self.is_contributing_closed(left)
    }
    match right_bound {
      Some(right) => {
        right.is_left_bound = false
        right.wind_cnt = left.wind_cnt
        right.wind_cnt2 = left.wind_cnt2
        insert_right_edge(left, right)
        if contributing {
          self.add_local_min_poly(left, right, left.bot, is_new=true) |> ignore
          if !is_horizontal(left) {
            self.check_join_left(left, left.bot)
          }
        }
        while right.next_in_ael is Some(n) && is_valid_ael_order(n, right) {
          self.intersect_edges(right, n, right.bot)
          self.swap_positions_in_ael(right, n)
        }
        if is_horizontal(right) {
          self.push_horz(right)
        } else {
          self.check_join_right(right, right.bot)
          self.insert_scanline(right.top.y)
        }
      }
      None => if contributing { self.start_open_path(left, left.bot) |> ignore }
    }
    if is_horizontal(left) {
      self.push_horz(left)
    } else {
      self.insert_scanline(left.top.y)
    }
  }
}

///|
fn Clipper64::push_horz(self : Clipper64, e : Active) -> Unit {
  e.next_in_sel = self.sel
  self.sel = Some(e)
}

///|
fn Clipper64::pop_horz(self : Clipper64) -> Active? {
  let e = self.sel
  if e is Some(a) {
    self.sel = a.next_in_sel
  }
  e
}