///|
/// `impossible` marks a proved failure of a necessary feasibility condition.
/// `search_exhausted` describes the bounded search only.
#derive(Debug, Eq, ToJson)
pub(all) struct SolveError {
  kind : String
  message : String
}

///|
pub extend SolveError with @debug.Debug::{to_repr}

///|
pub extend SolveError with Eq::{equal, not_equal}

///|
pub extend SolveError with @json.ToJson::{to_json}

///|
#derive(Debug)
pub struct InitialResult {
  assignment : Array[Int32]
  metrics : @metrics.Metrics
  starts_tried : Int32
  search_nodes : Int32
}

///|
pub extend InitialResult with @debug.Debug::{to_repr}

///|
priv struct Rng {
  mut state : UInt32
}

///|
fn Rng::next(self : Rng) -> UInt32 {
  let mut x = self.state
  x = x ^ (x << 13)
  x = x ^ (x >> 17)
  x = x ^ (x << 5)
  self.state = x
  x
}

///|
fn greedy(
  graph : @model.Hypergraph,
  order : Array[Int32],
  capacities : Array[Int64],
) -> Array[Int32]? {
  let assignment = Array::make(order.length(), -1)
  let loads = [0L, 0L]
  let sizes = [0, 0]
  for i in 0.. capacities[side] - loads[side] {
        return None
      }
    } else if weight > capacities[side] - loads[side] {
      side = 1 - side
      if weight > capacities[side] - loads[side] {
        return None
      }
    }
    assignment[v] = side
    loads[side] += weight
    sizes[side] += 1
  }
  Some(assignment)
}

///|
// Iterative backtracking keeps stack use independent of the vertex count.
fn repair(
  graph : @model.Hypergraph,
  order : Array[Int32],
  capacities : Array[Int64],
  budget : Int32,
) -> (Array[Int32]?, Int32) {
  let n = order.length()
  let assignment = Array::make(n, -1)
  let choices = Array::make(n, 0)
  let loads = [0L, 0L]
  let sizes = [0, 0]
  let mut depth = 0
  let mut used = 0
  while depth >= 0 {
    if depth == n {
      if sizes[0] > 0 && sizes[1] > 0 {
        return (Some(assignment), used)
      }
      depth -= 1
      let v = order[depth]
      let side = assignment[v]
      loads[side] -= graph.vertex_weight(v)
      sizes[side] -= 1
      assignment[v] = -1
      continue
    }
    if choices[depth] == 2 {
      choices[depth] = 0
      depth -= 1
      if depth >= 0 {
        let v = order[depth]
        let side = assignment[v]
        loads[side] -= graph.vertex_weight(v)
        sizes[side] -= 1
        assignment[v] = -1
      }
      continue
    }
    if used >= budget {
      return (None, used)
    }
    used += 1
    let side = choices[depth]
    choices[depth] += 1
    let v = order[depth]
    let weight = graph.vertex_weight(v)
    if weight > capacities[side] - loads[side] {
      continue
    }
    assignment[v] = side
    loads[side] += weight
    sizes[side] += 1
    depth += 1
    if depth < n {
      choices[depth] = 0
    }
  }
  (None, used)
}

///|
/// Multi-start greedy packing followed by bounded repair when all starts fail.
/// Start zero uses decreasing vertex weight and increasing ID for ties.
pub fn construct(
  graph : @model.Hypergraph,
  capacities : Array[Int64],
  seed~ : UInt32,
  starts~ : Int32,
  search_nodes~ : Int32,
) -> Result[InitialResult, SolveError] {
  if capacities.length() != 2 ||
    starts < 1 ||
    starts > 64 ||
    search_nodes < 0 ||
    search_nodes > 10000000 {
    return Err({
      kind: "options",
      message: "two capacities, 1..64 starts and 0..10000000 search nodes required",
    })
  }
  if capacities[0] <= 0L || capacities[1] <= 0L {
    return Err({ kind: "options", message: "capacities must be positive", })
  }
  let total = graph.total_vertex_weight()
  if graph.vertex_count() < 2 ||
    (capacities[0] < total && capacities[1] < total - capacities[0]) {
    return Err({
      kind: "impossible",
      message: "two nonempty parts require two vertices and sufficient total capacity",
    })
  }
  for v in 0.. capacities[0] && weight > capacities[1] {
      return Err({
        kind: "impossible",
        message: "a vertex exceeds both capacities",
      })
    }
  }
  let order = Array::makei(graph.vertex_count(), fn(i) { i })
  order.sort_by(fn(a, b) {
    let wa = graph.vertex_weight(a)
    let wb = graph.vertex_weight(b)
    if wa > wb {
      -1
    } else if wa < wb {
      1
    } else {
      a.compare(b)
    }
  })
  let rng : Rng = { state: if seed == 0U { 2463534242U } else { seed }, }
  let mut best : InitialResult? = None
  for start in 0.. 0 {
      let mut i = current.length() - 1
      while i > 0 {
        let j = (rng.next() % (i + 1).reinterpret_as_uint()).reinterpret_as_int()
        let temporary = current[i]
        current[i] = current[j]
        current[j] = temporary
        i -= 1
      }
    }
    if greedy(graph, current, capacities) is Some(assignment) {
      if @metrics.verify(graph, assignment, capacities) is Ok(metrics) {
        let improve = match best {
          None => true
          Some(previous) => metrics.cut_net < previous.metrics.cut_net
        }
        if improve {
          best = Some({
            assignment,
            metrics,
            starts_tried: starts,
            search_nodes: 0,
          })
        }
      }
    }
  }
  if best is Some(result) {
    return Ok(result)
  }
  let (candidate, used) = repair(graph, order, capacities, search_nodes)
  if candidate is Some(assignment) {
    if @metrics.verify(graph, assignment, capacities) is Ok(metrics) {
      return Ok({
        assignment,
        metrics,
        starts_tried: starts,
        search_nodes: used,
      })
    }
  }
  Err({
    kind: "search_exhausted",
    message: "no feasible bipartition found within the construction budget",
  })
}