///|
/// Policy for selecting between full-frame and delta-frame encoding.
pub(all) enum DeltaPolicy {
  AlwaysFull
  AlwaysDelta
  Threshold(per_mille~ : Int)
  Budget(max_pixels~ : Int)
} derive(Eq, Debug)

///|
pub(all) struct DeltaPlanItem {
  frame_index : Int
  changed : Bool
  rect : GifRect?
  source_pixels : Int
  encoded_pixels : Int
  saving_per_mille : Int
} derive(Debug)

///|
pub fn DeltaPlanItem::frame_index(self : DeltaPlanItem) -> Int {
  self.frame_index
}

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

///|
pub fn DeltaPlanItem::rect(self : DeltaPlanItem) -> GifRect? {
  self.rect
}

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

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

///|
pub fn DeltaPlanItem::saving_per_mille(self : DeltaPlanItem) -> Int {
  self.saving_per_mille
}

///|
pub(all) struct DeltaPlan {
  policy : DeltaPolicy
  items : Array[DeltaPlanItem]
  full_pixels : Int
  selected_pixels : Int
} derive(Debug)

///|
pub fn DeltaPlan::policy(self : DeltaPlan) -> DeltaPolicy {
  self.policy
}

///|
pub fn DeltaPlan::items(self : DeltaPlan) -> ArrayView[DeltaPlanItem] {
  self.items[:]
}

///|
pub fn DeltaPlan::full_pixels(self : DeltaPlan) -> Int {
  self.full_pixels
}

///|
pub fn DeltaPlan::selected_pixels(self : DeltaPlan) -> Int {
  self.selected_pixels
}

///|
pub fn DeltaPlan::saving_per_mille(self : DeltaPlan) -> Int {
  if self.full_pixels <= 0 {
    0
  } else {
    (self.full_pixels - self.selected_pixels) * 1000 / self.full_pixels
  }
}

///|
fn choose_delta(policy : DeltaPolicy, full : Int, delta : Int) -> Bool {
  match policy {
    AlwaysFull => false
    AlwaysDelta => true
    Threshold(per_mille~) => {
      let required = if per_mille < 0 {
        0
      } else if per_mille > 1000 {
        1000
      } else {
        per_mille
      }
      delta * 1000 <= full * (1000 - required)
    }
    Budget(max_pixels~) => delta <= max_pixels
  }
}

///|
/// Build a per-frame plan from changed rectangles and a policy.
pub fn Animation::plan_delta(
  self : Animation,
  policy : DeltaPolicy,
  threshold? : Int = 0,
) -> DeltaPlan {
  let items : Array[DeltaPlanItem] = []
  let mut previous = Canvas::new(
    width=self.width,
    height=self.height,
    fill=self.background,
  )
  let full_pixels = self.width * self.height * self.frames.length()
  let mut selected_pixels = 0
  for index, frame in self.frames {
    let source_pixels = frame.canvas().len()
    let rectangle = changed_rect(previous, frame.canvas(), threshold)
    let delta_pixels = match rectangle {
      None => 1
      Some(rect) => rect.area()
    }
    let selected = choose_delta(policy, source_pixels, delta_pixels)
    let encoded_pixels = if selected { delta_pixels } else { source_pixels }
    selected_pixels += encoded_pixels
    let saving = if source_pixels <= 0 {
      0
    } else {
      (source_pixels - encoded_pixels) * 1000 / source_pixels
    }
    items.push(DeltaPlanItem::{
      frame_index: index,
      changed: rectangle is Some(_),
      rect: if selected {
        rectangle
      } else {
        None
      },
      source_pixels,
      encoded_pixels,
      saving_per_mille: saving,
    })
    previous = frame.canvas()
  }
  DeltaPlan::{ policy, items, full_pixels, selected_pixels }
}

///|
/// Apply a delta plan without changing frame timing or logical screen size.
pub fn Animation::apply_delta_plan(
  self : Animation,
  plan : DeltaPlan,
) -> Animation {
  let result = Animation::new(width=self.width, height=self.height)
    .with_loop_count(loop_count=self.loop_count)
    .with_background(background=self.background)
  for item in plan.items {
    let frame = self.frames[item.frame_index]
    match item.rect {
      None => {
        let empty = Canvas::new(width=1, height=1, fill=rgba(0, 0, 0, 0))
        ignore(
          result.add_frame(
            frame
            .with_canvas(empty)
            .with_offset(left=0, top=0)
            .with_transparent(color=rgba(0, 0, 0, 0)),
          ),
        )
      }
      Some(rect) => {
        let cropped = frame
          .canvas()
          .crop(
            x=rect.left(),
            y=rect.top(),
            width=rect.width(),
            height=rect.height(),
          )
        ignore(
          result.add_frame(
            frame
            .with_canvas(cropped)
            .with_offset(left=rect.left(), top=rect.top()),
          ),
        )
      }
    }
  }
  result
}

///|
/// Return changed rectangles for visual diff overlays.
pub fn Animation::delta_rectangles(
  self : Animation,
  threshold? : Int = 0,
) -> Array[GifRect?] {
  let result : Array[GifRect?] = []
  let mut previous = Canvas::new(
    width=self.width,
    height=self.height,
    fill=self.background,
  )
  for frame in self.frames {
    result.push(changed_rect(previous, frame.canvas(), threshold))
    previous = frame.canvas()
  }
  result
}

///|
/// Estimate whether delta encoding is likely to improve the final GIF size.
pub fn DeltaPlan::is_worthwhile(
  self : DeltaPlan,
  minimum_saving_per_mille : Int,
) -> Bool {
  self.saving_per_mille() >= minimum_saving_per_mille
}

///|
/// Find the highest activity frames in a delta plan.
pub fn DeltaPlan::largest_changes(
  self : DeltaPlan,
  count : Int,
) -> Array[DeltaPlanItem] {
  let result : Array[DeltaPlanItem] = []
  let limit = if count < 0 { 0 } else { count }
  for item in self.items {
    if item.changed() {
      result.push(item)
    }
  }
  while result.length() > limit {
    let mut smallest = 0
    for i in 1..