///|
pub struct SolverConfig {
  max_iterations : Int
  candidate_limit : Int
  allow_partial : Bool
  improve : Bool
  seed : Int
} derive(Eq, Show, ToJson)

///|
pub fn SolverConfig::default() -> SolverConfig {
  {
    max_iterations: 250,
    candidate_limit: 64,
    allow_partial: true,
    improve: true,
    seed: 1,
  }
}

///|
pub fn SolverConfig::with_iterations(
  self : SolverConfig,
  max_iterations : Int,
) -> SolverConfig {
  { ..self, max_iterations, }
}

///|
pub fn SolverConfig::with_seed(self : SolverConfig, seed : Int) -> SolverConfig {
  { ..self, seed, }
}

///|
pub struct Candidate {
  worker_id : String
  shift_id : String
  delta : Int
  tie_breaker : Int
} derive(Eq, Show, ToJson)

///|
fn candidate_before(left : Candidate, right : Candidate) -> Bool {
  if left.delta != right.delta {
    left.delta < right.delta
  } else if left.tie_breaker != right.tie_breaker {
    left.tie_breaker < right.tie_breaker
  } else if left.worker_id != right.worker_id {
    left.worker_id < right.worker_id
  } else {
    left.shift_id < right.shift_id
  }
}

///|
fn sort_candidates(values : Array[Candidate]) -> Array[Candidate] {
  let result = values.copy()
  for i = 1; i < result.length(); i = i + 1 {
    let current = result[i]
    let mut j = i
    while j > 0 && candidate_before(current, result[j - 1]) {
      result[j] = result[j - 1]
      j = j - 1
    }
    result[j] = current
  }
  result
}

///|
struct DeterministicRandom {
  mut state : UInt
}

///|
fn DeterministicRandom::new(seed : Int) -> DeterministicRandom {
  let initial = if seed == 0 { 2463534242U } else { seed.to_uint() }
  { state: initial }
}

///|
fn DeterministicRandom::next(self : DeterministicRandom) -> UInt {
  let mut value = self.state
  value = value ^ (value << 13)
  value = value ^ (value >> 17)
  value = value ^ (value << 5)
  self.state = value
  value
}

///|
fn DeterministicRandom::below(self : DeterministicRandom, limit : Int) -> Int {
  if limit <= 0 {
    0
  } else {
    (self.next() % limit.to_uint()).to_int()
  }
}

///|
fn shift_difficulty(problem : PlanningProblem, shift : Shift) -> Int {
  let mut eligible = 0
  for worker in problem.workers {
    if worker.is_available(shift.range) {
      let mut qualified = true
      for requirement in shift.requirements {
        if !worker.has_skill(requirement.skill_id, requirement.minimum_level) {
          qualified = false
        }
      }
      if qualified {
        eligible = eligible + 1
      }
    }
  }
  let scarcity = if eligible == 0 { 10000 } else { 1000 / eligible }
  scarcity + shift.requirements.length() * 100 + shift.required_workers * 10
}

///|
fn ordered_shifts(problem : PlanningProblem) -> Array[Shift] {
  let result = problem.shifts.copy()
  for i = 1; i < result.length(); i = i + 1 {
    let current = result[i]
    let current_difficulty = shift_difficulty(problem, current)
    let mut j = i
    while j > 0 {
      let previous_difficulty = shift_difficulty(problem, result[j - 1])
      let should_move = current_difficulty > previous_difficulty ||
        (
          current_difficulty == previous_difficulty &&
          current.id < result[j - 1].id
        )
      if !should_move {
        break
      }
      result[j] = result[j - 1]
      j = j - 1
    }
    result[j] = current
  }
  result
}

///|
fn worker_tie_breaker(worker_id : String, shift_id : String, seed : Int) -> Int {
  let mut hash = seed
  for ch in worker_id {
    hash = (hash * 31 + ch.to_int()) & 0x7fffffff
  }
  for ch in shift_id {
    hash = (hash * 33 + ch.to_int()) & 0x7fffffff
  }
  hash
}

///|
fn candidate_list(
  problem : PlanningProblem,
  schedule : Schedule,
  shift : Shift,
  config : SolverConfig,
) -> Array[Candidate] {
  let candidates : Array[Candidate] = []
  for worker_id in eligible_workers(problem, schedule, shift.id) {
    candidates.push({
      worker_id,
      shift_id: shift.id,
      delta: assignment_delta(problem, schedule, worker_id, shift.id),
      tie_breaker: worker_tie_breaker(worker_id, shift.id, config.seed),
    })
  }
  let sorted = sort_candidates(candidates)
  if sorted.length() <= config.candidate_limit {
    return sorted
  }
  let limited : Array[Candidate] = []
  for i = 0; i < config.candidate_limit; i = i + 1 {
    limited.push(sorted[i])
  }
  limited
}

///|
fn append_locked_assignments(
  problem : PlanningProblem,
  schedule : Schedule,
) -> (Schedule, Array[Diagnostic]) {
  let mut result = schedule
  let diagnostics : Array[Diagnostic] = []
  for assignment in problem.locked_assignments {
    let report = check_candidate(
      problem,
      result,
      assignment.worker_id,
      assignment.shift_id,
    )
    if report.feasible() {
      result = result.add(assignment)
    } else {
      diagnostics.push(
        Diagnostic::new(
          "invalid_locked_assignment",
          Error,
          "locked assignment violates one or more hard constraints",
        )
        .for_worker(assignment.worker_id)
        .for_shift(assignment.shift_id),
      )
    }
  }
  (result, diagnostics)
}

///|
fn requirement_missing(
  problem : PlanningProblem,
  schedule : Schedule,
  shift : Shift,
  requirement : SkillRequirement,
) -> Int {
  let mut qualified = 0
  for worker_id in schedule.workers_for(shift.id) {
    match problem.worker(worker_id) {
      Some(worker) =>
        if worker.has_skill(requirement.skill_id, requirement.minimum_level) {
          qualified = qualified + 1
        }
      None => ()
    }
  }
  if qualified < requirement.count {
    requirement.count - qualified
  } else {
    0
  }
}

///|
fn skill_candidate_list(
  problem : PlanningProblem,
  schedule : Schedule,
  shift : Shift,
  requirement : SkillRequirement,
  config : SolverConfig,
) -> Array[Candidate] {
  let candidates : Array[Candidate] = []
  for worker in problem.workers {
    if worker.has_skill(requirement.skill_id, requirement.minimum_level) &&
      check_candidate(problem, schedule, worker.id, shift.id).feasible() {
      candidates.push({
        worker_id: worker.id,
        shift_id: shift.id,
        delta: assignment_delta(problem, schedule, worker.id, shift.id),
        tie_breaker: worker_tie_breaker(worker.id, shift.id, config.seed),
      })
    }
  }
  sort_candidates(candidates)
}

///|
fn fill_skill_requirements(
  problem : PlanningProblem,
  initial : Schedule,
  shift : Shift,
  config : SolverConfig,
) -> (Schedule, Int) {
  let mut schedule = initial
  let mut explored = 0
  for requirement in shift.requirements {
    let mut missing = requirement_missing(problem, schedule, shift, requirement)
    while missing > 0 {
      let candidates = skill_candidate_list(
        problem, schedule, shift, requirement, config,
      )
      explored = explored + candidates.length()
      if candidates.length() == 0 {
        break
      }
      schedule = schedule.add(
        Assignment::new(candidates[0].worker_id, candidates[0].shift_id),
      )
      missing = requirement_missing(problem, schedule, shift, requirement)
    }
  }
  (schedule, explored)
}

///|
fn fill_headcount(
  problem : PlanningProblem,
  initial : Schedule,
  shift : Shift,
  config : SolverConfig,
) -> (Schedule, Int) {
  let mut schedule = initial
  let mut explored = 0
  while assignment_count_for_shift(schedule, shift.id) < shift.required_workers {
    let candidates = candidate_list(problem, schedule, shift, config)
    explored = explored + candidates.length()
    if candidates.length() == 0 {
      break
    }
    schedule = schedule.add(
      Assignment::new(candidates[0].worker_id, candidates[0].shift_id),
    )
  }
  (schedule, explored)
}

///|
fn construct_schedule(
  problem : PlanningProblem,
  config : SolverConfig,
) -> (Schedule, Array[Diagnostic], Int) {
  let (locked, diagnostics) = append_locked_assignments(
    problem,
    Schedule::empty(),
  )
  let mut schedule = locked
  let mut explored = 0
  for shift in ordered_shifts(problem) {
    let (with_skills, skill_explored) = fill_skill_requirements(
      problem, schedule, shift, config,
    )
    schedule = with_skills
    explored = explored + skill_explored
    let (with_headcount, headcount_explored) = fill_headcount(
      problem, schedule, shift, config,
    )
    schedule = with_headcount
    explored = explored + headcount_explored
  }
  (schedule, diagnostics, explored)
}

///|
fn assignment_is_locked(
  problem : PlanningProblem,
  assignment : Assignment,
) -> Bool {
  for locked in problem.locked_assignments {
    if locked.worker_id == assignment.worker_id &&
      locked.shift_id == assignment.shift_id {
      return true
    }
  }
  false
}

///|
fn try_move(
  problem : PlanningProblem,
  schedule : Schedule,
  index : Int,
  replacement_worker : String,
) -> Schedule? {
  let original = schedule.assignments[index]
  if assignment_is_locked(problem, original) ||
    original.worker_id == replacement_worker {
    return None
  }
  let removed = schedule.remove(original.worker_id, original.shift_id)
  if !check_candidate(problem, removed, replacement_worker, original.shift_id).feasible() {
    return None
  }
  let candidate = removed.add(
    Assignment::new(replacement_worker, original.shift_id),
  )
  if evaluate_constraints(problem, candidate).feasible() {
    Some(candidate)
  } else {
    None
  }
}

///|
fn improve_by_moves(
  problem : PlanningProblem,
  initial : Schedule,
  config : SolverConfig,
) -> (Schedule, Int, Int, Int) {
  let random = DeterministicRandom::new(config.seed)
  let mut schedule = initial
  let mut best_score = score_schedule(problem, schedule).total
  let mut explored = 0
  let mut pruned = 0
  let mut improvements = 0
  if schedule.assignments.length() == 0 || problem.workers.length() == 0 {
    return (schedule, explored, pruned, improvements)
  }
  for iteration = 0
      iteration < config.max_iterations
      iteration = iteration + 1 {
    let index = (iteration + random.below(schedule.assignments.length())) %
      schedule.assignments.length()
    let worker_index = (iteration * 7 + random.below(problem.workers.length())) %
      problem.workers.length()
    let replacement = problem.workers[worker_index].id
    explored = explored + 1
    match try_move(problem, schedule, index, replacement) {
      None => pruned = pruned + 1
      Some(candidate) => {
        let candidate_score = score_schedule(problem, candidate).total
        if candidate_score < best_score {
          schedule = candidate
          best_score = candidate_score
          improvements = improvements + 1
        } else {
          pruned = pruned + 1
        }
      }
    }
  }
  (schedule, explored, pruned, improvements)
}

///|
fn violations_to_diagnostics(report : ConstraintReport) -> Array[Diagnostic] {
  let diagnostics : Array[Diagnostic] = []
  for violation in report.violations {
    let severity = if violation.hard { Error } else { Warning }
    let mut diagnostic = Diagnostic::new(
      "constraint_violation",
      severity,
      violation.message,
    )
    match violation.worker_id {
      Some(worker_id) => diagnostic = diagnostic.for_worker(worker_id)
      None => ()
    }
    match violation.shift_id {
      Some(shift_id) => diagnostic = diagnostic.for_shift(shift_id)
      None => ()
    }
    diagnostics.push(diagnostic)
  }
  diagnostics
}

///|
pub fn solve_with_config(
  problem : PlanningProblem,
  config : SolverConfig,
) -> Solution {
  let validation = problem.validate()
  if diagnostics_have_errors(validation) {
    return {
      schedule: Schedule::empty(),
      score: ScoreBreakdown::zero(),
      diagnostics: validation,
      feasible: false,
      stats: {
        explored_nodes: 0,
        pruned_nodes: 0,
        improvements: 0,
        elapsed_steps: 0,
      },
    }
  }
  let (constructed, initial_diagnostics, construct_explored) = construct_schedule(
    problem, config,
  )
  let (schedule, move_explored, pruned, improvements) = if config.improve {
    improve_by_moves(problem, constructed, config)
  } else {
    (constructed, 0, 0, 0)
  }
  let report = evaluate_constraints(problem, schedule)
  let diagnostics = initial_diagnostics.copy()
  diagnostics.append(violations_to_diagnostics(report))
  {
    schedule,
    score: score_schedule(problem, schedule),
    diagnostics,
    feasible: report.feasible(),
    stats: {
      explored_nodes: construct_explored + move_explored,
      pruned_nodes: pruned,
      improvements,
      elapsed_steps: construct_explored + config.max_iterations,
    },
  }
}

///|
pub fn solve(problem : PlanningProblem) -> Solution {
  solve_with_config(problem, SolverConfig::default().with_seed(problem.seed))
}

///|
pub fn repair_schedule(
  problem : PlanningProblem,
  existing : Schedule,
  config : SolverConfig,
) -> Solution {
  let mut repaired = Schedule::empty()
  let diagnostics : Array[Diagnostic] = []
  for assignment in existing.assignments {
    let report = check_candidate(
      problem,
      repaired,
      assignment.worker_id,
      assignment.shift_id,
    )
    if report.feasible() {
      repaired = repaired.add(assignment)
    } else {
      diagnostics.push(
        Diagnostic::new(
          "removed_invalid_assignment",
          Warning,
          "repair removed an assignment that violates current constraints",
        )
        .for_worker(assignment.worker_id)
        .for_shift(assignment.shift_id),
      )
    }
  }
  let augmented_problem = {
    ..problem,
    locked_assignments: repaired.assignments.copy(),
  }
  let solved = solve_with_config(augmented_problem, config)
  let all_diagnostics = diagnostics.copy()
  all_diagnostics.append(solved.diagnostics)
  {
    schedule: solved.schedule,
    score: solved.score,
    diagnostics: all_diagnostics,
    feasible: solved.feasible,
    stats: solved.stats,
  }
}