///|
/// Shared candidate-visit budget for topology, intersections and gap checks.
pub(all) struct GeometryBudget {
  max_candidates : Int
}

///|
pub fn GeometryBudget::default() -> GeometryBudget {
  { max_candidates: 1000000, }
}

///|
priv struct CheckWork {
  mut remaining : Int
  mut stopped : Bool
}

///|
fn CheckWork::spend(self : CheckWork) -> Bool {
  if self.remaining <= 0 {
    self.stopped = true
    return false
  }
  self.remaining -= 1
  true
}

///|
/// Expansion still uses its independent defaults; a partial check is explicit.
pub fn Drawing::check_with_budget(
  self : Drawing,
  opt : CheckOptions,
  budget : GeometryBudget,
) -> Report {
  self.check_expansion(opt, self.expand(opt.tol), budget~)
}

///|
fn topology_root(parent : Array[Int], i : Int) -> Int {
  let mut root = i
  while parent[root] != root {
    root = parent[root]
  }
  let mut n = i
  while parent[n] != n {
    let next = parent[n]
    parent[n] = root
    n = next
  }
  root
}

///|
fn topology_union(parent : Array[Int], a : Int, b : Int) -> Unit {
  let x = topology_root(parent, a)
  let y = topology_root(parent, b)
  if x != y {
    parent[x] = y
  }
}

///|
/// Endpoint equivalence graph, then connected edge components. Branches are
/// diagnosed, never resolved by an input-order-dependent greedy choice.
fn endpoint_topology(
  edges : Array[(Vec2, Vec2)],
  tol : Double,
  work : CheckWork,
) -> (Int, Double, Vec2, Bool) {
  let points : Array[Vec2] = []
  for edge in edges {
    points.push(edge.0)
    points.push(edge.1)
  }
  let parent = Array::makei(points.length(), i => i)
  let order = Array::makei(points.length(), i => i)
  // A vertical column would otherwise visit every pair, even when the
  // vertical separation makes a contact impossible.
  let vertical = points.length() > 0 && points.all(p => p.x == points[0].x)
  let key = (i : Int) => if vertical { points[i].y } else { points[i].x }
  order.sort_by((a, b) => {
    if key(a) < key(b) {
      -1
    } else if key(a) > key(b) {
      1
    } else {
      0
    }
  })
  for at = 0; at < order.length(); at = at + 1 {
    let i = order[at]
    let mut next = at + 1
    while next < order.length() && key(order[next]) - key(i) <= tol {
      if !work.spend() {
        return (0, 0.0, Vec2::zero(), false)
      }
      let j = order[next]
      if points[i].distance(points[j]) <= tol {
        topology_union(parent, i, j)
      }
      next += 1
    }
  }
  let degree = Array::make(points.length(), 0)
  for i = 0; i < points.length(); i = i + 1 {
    degree[topology_root(parent, i)] += 1
  }
  let components = Array::makei(points.length(), i => i)
  for i = 0; i < edges.length(); i = i + 1 {
    topology_union(
      components,
      topology_root(parent, i * 2),
      topology_root(parent, i * 2 + 1),
    )
  }
  let ends : Map[Int, Array[Vec2]] = Map([])
  let mut branched = false
  for i = 0; i < points.length(); i = i + 1 {
    if degree[i] > 0 && degree[i] != 2 {
      if degree[i] > 2 {
        branched = true
      }
      let component = topology_root(components, i)
      match ends.get(component) {
        Some(group) => group.push(points[i])
        None => ends[component] = [points[i]]
      }
    }
  }
  let mut worst = 0.0
  let mut at = Vec2::zero()
  for group in ends.values() {
    if group.length() >= 2 {
      let gap = group[0].distance(group[1])
      if gap > worst {
        worst = gap
        at = group[0]
      }
    }
  }
  (ends.length(), worst, at, branched)
}