///|
/// Palette policy used by the size planner.
pub(all) enum PaletteStrategy {
  LocalPerFrame
  GlobalFirstFrame
  Adaptive
} derive(Eq, Debug)

///|
pub(all) struct OptimizationOptions {
  max_colors : Int
  difference_threshold : Int
  merge_equal_frames : Bool
  crop_delta_frames : Bool
  palette_strategy : PaletteStrategy
  default_delay_cs : Int
} derive(Debug)

///|
pub fn OptimizationOptions::default() -> OptimizationOptions {
  {
    max_colors: 256,
    difference_threshold: 0,
    merge_equal_frames: true,
    crop_delta_frames: true,
    palette_strategy: Adaptive,
    default_delay_cs: 1,
  }
}

///|
pub fn OptimizationOptions::colors(
  self : OptimizationOptions,
  value : Int,
) -> OptimizationOptions {
  {
    ..self,
    max_colors: if value < 2 {
      2
    } else if value > 256 {
      256
    } else {
      value
    },
  }
}

///|
pub fn OptimizationOptions::threshold(
  self : OptimizationOptions,
  value : Int,
) -> OptimizationOptions {
  { ..self, difference_threshold: if value < 0 { 0 } else { value } }
}

///|
pub fn OptimizationOptions::merge_equal(
  self : OptimizationOptions,
  enabled : Bool,
) -> OptimizationOptions {
  { ..self, merge_equal_frames: enabled }
}

///|
pub fn OptimizationOptions::crop_deltas(
  self : OptimizationOptions,
  enabled : Bool,
) -> OptimizationOptions {
  { ..self, crop_delta_frames: enabled }
}

///|
pub fn OptimizationOptions::palette(
  self : OptimizationOptions,
  strategy : PaletteStrategy,
) -> OptimizationOptions {
  { ..self, palette_strategy: strategy }
}

///|
pub(all) struct OptimizationFrame {
  index : Int
  source_pixels : Int
  encoded_pixels : Int
  palette_colors : Int
  compressed_bytes : Int
  estimated_bytes : Int
  changed : Bool
} derive(Debug)

///|
pub fn OptimizationFrame::index(self : OptimizationFrame) -> Int {
  self.index
}

///|
pub fn OptimizationFrame::source_pixels(self : OptimizationFrame) -> Int {
  self.source_pixels
}

///|
pub fn OptimizationFrame::encoded_pixels(self : OptimizationFrame) -> Int {
  self.encoded_pixels
}

///|
pub fn OptimizationFrame::palette_colors(self : OptimizationFrame) -> Int {
  self.palette_colors
}

///|
pub fn OptimizationFrame::compressed_bytes(self : OptimizationFrame) -> Int {
  self.compressed_bytes
}

///|
pub fn OptimizationFrame::estimated_bytes(self : OptimizationFrame) -> Int {
  self.estimated_bytes
}

///|
pub fn OptimizationFrame::changed(self : OptimizationFrame) -> Bool {
  self.changed
}

///|
pub(all) struct OptimizationReport {
  input_frames : Int
  output_frames : Int
  input_pixels : Int
  output_pixels : Int
  palette_bytes : Int
  compressed_bytes : Int
  estimated_bytes : Int
  changed_frames : Int
  frames : Array[OptimizationFrame]
} derive(Debug)

///|
pub fn OptimizationReport::input_frames(self : OptimizationReport) -> Int {
  self.input_frames
}

///|
pub fn OptimizationReport::output_frames(self : OptimizationReport) -> Int {
  self.output_frames
}

///|
pub fn OptimizationReport::input_pixels(self : OptimizationReport) -> Int {
  self.input_pixels
}

///|
pub fn OptimizationReport::output_pixels(self : OptimizationReport) -> Int {
  self.output_pixels
}

///|
pub fn OptimizationReport::palette_bytes(self : OptimizationReport) -> Int {
  self.palette_bytes
}

///|
pub fn OptimizationReport::compressed_bytes(self : OptimizationReport) -> Int {
  self.compressed_bytes
}

///|
pub fn OptimizationReport::estimated_bytes(self : OptimizationReport) -> Int {
  self.estimated_bytes
}

///|
pub fn OptimizationReport::changed_frames(self : OptimizationReport) -> Int {
  self.changed_frames
}

///|
pub fn OptimizationReport::frames(
  self : OptimizationReport,
) -> ArrayView[OptimizationFrame] {
  self.frames[:]
}

///|
pub fn OptimizationReport::saving_per_mille(self : OptimizationReport) -> Int {
  if self.input_pixels <= 0 {
    0
  } else {
    (self.input_pixels - self.output_pixels) * 1000 / self.input_pixels
  }
}

///|
fn palette_cost(colors : Int) -> Int {
  let safe = if colors < 2 { 2 } else if colors > 256 { 256 } else { colors }
  let mut size = 2
  while size < safe {
    size *= 2
  }
  size * 3
}

///|
fn estimate_optimization_frame(
  index : Int,
  frame : Frame,
  options : OptimizationOptions,
  changed : Bool,
) -> OptimizationFrame raise GifError {
  let quantized = match frame.transparent {
    None => quantize(frame.canvas(), max_colors=options.max_colors)
    Some(color) =>
      quantize(frame.canvas(), max_colors=options.max_colors, transparent=color)
  }
  let palette = quantized.palette()
  let min_code_size = if palette.len() <= 2 {
    2
  } else if palette.len() > 128 {
    8
  } else if palette.len() > 64 {
    7
  } else if palette.len() > 32 {
    6
  } else if palette.len() > 16 {
    5
  } else if palette.len() > 8 {
    4
  } else if palette.len() > 4 {
    3
  } else {
    2
  }
  let compressed = lzw_encode_sub_blocks(quantized.indices(), min_code_size).length()
  let palette_bytes = palette_cost(palette.len())
  OptimizationFrame::{
    index,
    source_pixels: frame.canvas().width * frame.canvas().height,
    encoded_pixels: quantized.indices().length(),
    palette_colors: palette.len(),
    compressed_bytes: compressed,
    estimated_bytes: compressed + palette_bytes + 24,
    changed,
  }
}

///|
/// Estimate GIF payload cost after palette quantization and delta analysis.
pub fn Animation::optimization_report(
  self : Animation,
  options : OptimizationOptions,
) -> OptimizationReport raise GifError {
  let planned = if options.crop_delta_frames {
    self.delta_encode(threshold=options.difference_threshold)
  } else {
    self
  }
  let input_pixels = self.width * self.height * self.frames.length()
  let frames : Array[OptimizationFrame] = []
  let mut output_pixels = 0
  let mut palette_bytes = 0
  let mut compressed_bytes = 0
  let mut changed_frames = 0
  let mut previous = self.background_canvas()
  for i, frame in planned.frames {
    let changed = changed_rect(
        previous,
        frame.canvas(),
        options.difference_threshold,
      )
      is Some(_)
    if changed {
      changed_frames += 1
    }
    let estimate = estimate_optimization_frame(i, frame, options, changed)
    output_pixels += estimate.encoded_pixels()
    palette_bytes += palette_cost(estimate.palette_colors())
    compressed_bytes += estimate.compressed_bytes()
    frames.push(estimate)
    previous = frame.canvas()
  }
  OptimizationReport::{
    input_frames: self.frames.length(),
    output_frames: planned.frames.length(),
    input_pixels,
    output_pixels,
    palette_bytes,
    compressed_bytes,
    estimated_bytes: compressed_bytes +
    palette_bytes +
    planned.frames.length() * 24 +
    14,
    changed_frames,
    frames,
  }
}

///|
/// Run safe size optimizations while preserving logical dimensions and delay.
pub fn Animation::optimize_for_size(
  self : Animation,
  options : OptimizationOptions,
) -> Animation {
  let mut result = self
  if options.merge_equal_frames {
    result = result.merge_equal_frames()
  }
  if options.crop_delta_frames {
    result = result.delta_encode(threshold=options.difference_threshold)
  }
  result.normalize_delays(default_delay_cs=options.default_delay_cs)
}

///|
/// Choose a palette budget that fits an estimated byte budget.
pub fn choose_palette_budget(
  animation : Animation,
  budget_bytes : Int,
  options : OptimizationOptions,
) -> Int raise GifError {
  let mut best = 2
  let mut colors = options.max_colors
  while colors >= 2 {
    let candidate = animation.optimization_report(options.colors(colors))
    if candidate.estimated_bytes() <= budget_bytes {
      best = colors
      break
    }
    colors /= 2
  }
  best
}

///|
/// Optimize an animation for a byte budget and return the chosen report.
pub fn Animation::optimize_to_budget(
  self : Animation,
  budget_bytes : Int,
  options : OptimizationOptions,
) -> (Animation, OptimizationReport) raise GifError {
  let safe_budget = if budget_bytes < 0 { 0 } else { budget_bytes }
  let budget = choose_palette_budget(self, safe_budget, options)
  let tuned = options.colors(budget)
  let optimized = self.optimize_for_size(tuned)
  (optimized, optimized.optimization_report(tuned))
}

///|
/// Select a conservative encoding option from a quality target in per mille.
pub fn options_for_quality(target_per_mille : Int) -> OptimizationOptions {
  let target = if target_per_mille < 0 {
    0
  } else if target_per_mille > 1000 {
    1000
  } else {
    target_per_mille
  }
  let colors = if target >= 950 {
    256
  } else if target >= 800 {
    128
  } else if target >= 600 {
    64
  } else if target >= 400 {
    32
  } else {
    16
  }
  OptimizationOptions::default().colors(colors)
}

///|
/// Return the ratio of frame pixels retained after delta cropping.
pub fn Animation::retained_pixel_ratio(
  self : Animation,
  threshold : Int,
) -> Int {
  let stats = self.delta_stats(threshold~)
  if stats.full_pixels() <= 0 {
    0
  } else {
    stats.delta_pixels() * 1000 / stats.full_pixels()
  }
}

///|
/// Verify that a planned animation still has valid GIF frame rectangles.
pub fn Animation::optimization_warnings(
  self : Animation,
  options : OptimizationOptions,
) -> Array[String] {
  let optimized = self.optimize_for_size(options)
  let warnings : Array[String] = []
  for issue in optimized.validate() {
    warnings.push(issue)
  }
  if optimized.frame_count() > 0 &&
    optimized.retained_pixel_ratio(options.difference_threshold) == 0 {
    warnings.push("optimization removed all visible frame pixels")
  }
  warnings
}