///|
/// A service-level target for an open M/M/c center.
pub(all) struct SlaStaffing {
  servers : Int
  utilization : Double
  delay_probability : Double
  probability_within_threshold : Double
  mean_wait : Double
} derive(Debug, ToJson)

///|
/// Find the smallest server count satisfying both an M/M/c waiting target and
/// a utilization ceiling. The threshold is measured in the same time unit as
/// service and arrival rates.
pub fn sla_staffing(
  arrival : Double,
  service : Double,
  target_probability : Double,
  wait_threshold : Double,
  maximum_utilization? : Double = 0.95,
  maximum_servers? : Int = 10000,
) -> SlaStaffing raise QueueError {
  rate(arrival, "arrival")
  positive(service, "service")
  rate(service, "service")
  probability(target_probability, "target probability")
  nonnegative(wait_threshold, "wait threshold")
  probability(maximum_utilization, "maximum utilization")
  if maximum_utilization >= 1.0 {
    raise Invalid("maximum utilization must be below one")
  }
  if maximum_servers < 1 || maximum_servers > 10000 {
    raise Limit("maximum staffing servers must be 1..10000")
  }
  for servers in 1..<=maximum_servers {
    let q : Mmc = { arrival, service, servers, }
    if arrival >= service * servers.to_double() {
      continue
    }
    let metrics = q.analyze()
    let within = 1.0 - q.wait_survival(wait_threshold)
    let utilization_ok = metrics.utilization <= maximum_utilization + 1.0e-12
    let service_ok = within + 1.0e-12 >= target_probability
    if utilization_ok && service_ok {
      return {
        servers,
        utilization: metrics.utilization,
        delay_probability: metrics.delay_probability,
        probability_within_threshold: within,
        mean_wait: metrics.mean_wait,
      }
    }
  }
  raise Infeasible("SLA target unattainable within server bound")
}

///|
/// A fixed open-network node used by exact server-budget allocation.
pub(all) struct ServerBudgetNode {
  arrival : Double
  service : Double
  minimum_servers : Int
  maximum_servers : Int
} derive(Debug, ToJson)

///|
/// Exact allocation result. The selected counts consume the requested budget
/// exactly; objective is the recomputed sum of node mean queue lengths.
pub(all) struct ServerAllocation {
  servers : Array[Int]
  total_mean_queue : Double
  node_mean_queues : Array[Double]
  consumed_budget : Int
} derive(Debug, ToJson)

///|
fn ServerBudgetNode::validate(self : ServerBudgetNode) -> Unit raise QueueError {
  rate(self.arrival, "allocation arrival")
  positive(self.service, "allocation service")
  rate(self.service, "allocation service")
  servers(self.minimum_servers)
  servers(self.maximum_servers)
  if self.minimum_servers > self.maximum_servers {
    raise Invalid("minimum servers must not exceed maximum servers")
  }
}

///|
/// Exact separable dynamic programming over integer server counts. Unstable
/// node/count combinations are excluded instead of assigned an artificial
/// finite penalty.
pub fn allocate_server_budget(
  nodes : Array[ServerBudgetNode],
  budget : Int,
) -> ServerAllocation raise QueueError {
  let node_count = nodes.length()
  if node_count == 0 || node_count > 64 {
    raise Limit("allocation needs 1..64 nodes")
  }
  if budget < 1 || budget > 10000 {
    raise Limit("allocation budget must be 1..10000")
  }
  let mut minimum_total = 0
  let mut maximum_total = 0
  for node in nodes {
    node.validate()
    minimum_total += node.minimum_servers
    maximum_total += node.maximum_servers
  }
  if budget < minimum_total || budget > maximum_total {
    raise Infeasible("allocation budget is outside node bounds")
  }
  let mut prefix_minimum = 0
  let mut prefix_maximum = 0
  let mut estimated_transitions = 0.0
  for node in nodes {
    let first_state = prefix_minimum
    let last_state = if prefix_maximum < budget {
      prefix_maximum
    } else {
      budget
    }
    let state_count = if last_state < first_state {
      0
    } else {
      last_state - first_state + 1
    }
    let choice_count = node.maximum_servers - node.minimum_servers + 1
    estimated_transitions += state_count.to_double() * choice_count.to_double()
    if estimated_transitions > 2.0e7 {
      raise Limit("exact allocation exceeds 20 million bounded transitions")
    }
    prefix_minimum += node.minimum_servers
    prefix_maximum += node.maximum_servers
  }
  let infinity = 1.0e300
  let mut costs = Array::make(budget + 1, infinity)
  costs[0] = 0.0
  let choices : Array[Array[Int]] = []
  for _ in 0..= node.minimum_servers &&
        node.arrival < node.service * count.to_double() {
        let rho = offered / count.to_double()
        let delay = loss / (1.0 - rho + rho * loss)
        let cost = node.arrival *
          (delay / (node.service * count.to_double() - node.arrival))
        finite(cost, "allocation queue cost")
        if cost >= infinity {
          raise Numerical("allocation objective exceeds supported range")
        }
        node_cost[count] = cost
      }
    }
    for spent in 0..<=budget {
      if costs[spent] >= infinity {
        continue
      }
      for count in node.minimum_servers..<=node.maximum_servers {
        if spent + count > budget {
          break
        }
        if node_cost[count] >= infinity {
          continue
        }
        let candidate = costs[spent] + node_cost[count]
        if candidate < next[spent + count] {
          next[spent + count] = candidate
          choices[i][spent + count] = count
        }
      }
    }
    costs = next
  }
  if costs[budget] >= infinity {
    raise Infeasible("no stable allocation consumes the exact budget")
  }
  let selected = Array::make(node_count, 0)
  let mut remaining = budget
  for offset in 0..