/// Analysis helpers used by the CLI, examples, and benchmark reports.

pub(all) struct ChunkProfile {
  total_bytes : Int
  chunk_count : Int
  mean_size : Int
  median_size : Int
  min_size : Int
  max_size : Int
  unique_count : Int
  duplicate_count : Int
  histogram : Array[Int]
} derive(Show)

pub fn ChunkProfile::bytes(self : ChunkProfile) -> Int { self.total_bytes }
pub fn ChunkProfile::count(self : ChunkProfile) -> Int { self.chunk_count }
pub fn ChunkProfile::mean(self : ChunkProfile) -> Int { self.mean_size }
pub fn ChunkProfile::median(self : ChunkProfile) -> Int { self.median_size }
pub fn ChunkProfile::minimum(self : ChunkProfile) -> Int { self.min_size }
pub fn ChunkProfile::maximum(self : ChunkProfile) -> Int { self.max_size }
pub fn ChunkProfile::unique(self : ChunkProfile) -> Int { self.unique_count }
pub fn ChunkProfile::duplicates(self : ChunkProfile) -> Int { self.duplicate_count }
pub fn ChunkProfile::distribution(self : ChunkProfile) -> Array[Int] { self.histogram.copy() }

fn insertion_sort(values : Array[Int]) -> Array[Int] {
  let result = values.copy()
  for i in 1.. 0 && result[j - 1] > value {
      result[j] = result[j - 1]
      j = j - 1
    }
    result[j] = value
  }
  result
}

fn sorted_chunk_sizes(chunks : Array[Chunk]) -> Array[Int] {
  insertion_sort(chunks.map(c => c.size()))
}

fn count_digest(digests : Array[String], digest : String) -> Int {
  let mut result = 0
  for item in digests { if digest_equal(item, digest) { result = result + 1 } }
  result
}

fn unique_digests(digests : Array[String]) -> Array[String] {
  let result = []
  for digest in digests {
    if count_digest(result, digest) == 0 { result.push(digest) }
  }
  result
}

fn bucket_for_size(size : Int, maximum : Int, buckets : Int) -> Int {
  if buckets <= 1 || maximum <= 0 { return 0 }
  let slot = size * buckets / (maximum + 1)
  if slot >= buckets { buckets - 1 } else if slot < 0 { 0 } else { slot }
}

pub fn profile_chunks(chunks : Array[Chunk], buckets? : Int = 10) -> ChunkProfile {
  if chunks.length() == 0 {
    return { total_bytes: 0, chunk_count: 0, mean_size: 0, median_size: 0, min_size: 0, max_size: 0, unique_count: 0, duplicate_count: 0, histogram: Array::make(if buckets <= 0 { 1 } else { buckets }, 0) }
  }
  let sizes = sorted_chunk_sizes(chunks)
  let digests = chunks.map(c => c.id())
  let unique = unique_digests(digests)
  let total = chunk_total_size(chunks)
  let min_size = sizes[0]
  let max_size = sizes[sizes.length() - 1]
  let median = sizes[sizes.length() / 2]
  let count = if buckets <= 0 { 1 } else { buckets }
  let histogram = Array::make(count, 0)
  for size in sizes { histogram[bucket_for_size(size, max_size, count)] = histogram[bucket_for_size(size, max_size, count)] + 1 }
  { total_bytes: total, chunk_count: chunks.length(), mean_size: total / chunks.length(), median_size: median, min_size, max_size, unique_count: unique.length(), duplicate_count: chunks.length() - unique.length(), histogram }
}

pub fn profile_strings(chunks : Array[Chunk], buckets : Int) -> String {
  let p = profile_chunks(chunks, buckets~)
  "chunks=\{p.count()} bytes=\{p.bytes()} mean=\{p.mean()} median=\{p.median()} unique=\{p.unique()} duplicate=\{p.duplicates()}"
}

pub fn duplicate_ratio(chunks : Array[Chunk]) -> Double {
  if chunks.length() == 0 { return 0.0 }
  let profile = profile_chunks(chunks)
  profile.duplicates().to_double() / chunks.length().to_double()
}

pub fn estimated_storage(chunks : Array[Chunk]) -> Int {
  let unique = unique_digests(chunks.map(c => c.id()))
  let mut total = 0
  for digest in unique {
    for chunk in chunks {
      if digest_equal(chunk.id(), digest) { total = total + chunk.size(); break }
    }
  }
  total
}

pub fn estimated_savings(chunks : Array[Chunk]) -> Int {
  chunk_total_size(chunks) - estimated_storage(chunks)
}

pub fn size_percentile(chunks : Array[Chunk], percentile : Int) -> Int {
  if chunks.length() == 0 { return 0 }
  let values = sorted_chunk_sizes(chunks)
  let p = if percentile < 0 { 0 } else if percentile > 100 { 100 } else { percentile }
  values[(values.length() - 1) * p / 100]
}

pub fn boundary_gaps(chunks : Array[Chunk]) -> Array[Int] {
  let gaps = []
  let mut previous = 0
  for chunk in chunks {
    gaps.push(chunk.range().end - previous)
    previous = chunk.range().end
  }
  gaps
}

pub fn boundary_jitter(chunks : Array[Chunk]) -> Int {
  let gaps = boundary_gaps(chunks)
  if gaps.length() < 2 { return 0 }
  let mut total = 0
  for i in 1.. Int { self.old_bytes }
pub fn VersionComparison::new_size(self : VersionComparison) -> Int { self.new_bytes }
pub fn VersionComparison::reused(self : VersionComparison) -> Int { self.reused_bytes }
pub fn VersionComparison::uploaded(self : VersionComparison) -> Int { self.uploaded_bytes }
pub fn VersionComparison::removed(self : VersionComparison) -> Int { self.removed_chunks }
pub fn VersionComparison::reuse_fraction(self : VersionComparison) -> Double { self.reuse_ratio }
pub fn VersionComparison::upload_fraction(self : VersionComparison) -> Double { self.upload_ratio }

pub fn compare_versions(old : Manifest, next : Manifest) -> VersionComparison {
  let plan = diff_manifests(old, next)
  let old_size = old.size()
  let new_size = next.size()
  { old_bytes: old_size, new_bytes: new_size, reused_bytes: plan.reused(), uploaded_bytes: plan.uploaded(), removed_chunks: plan.removed(), reuse_ratio: if new_size == 0 { 0.0 } else { plan.reused().to_double() / new_size.to_double() }, upload_ratio: if new_size == 0 { 0.0 } else { plan.uploaded().to_double() / new_size.to_double() } }
}

pub fn comparison_summary(comparison : VersionComparison) -> String {
  "old={comparison.old_size()} new={comparison.new_size()} reused={comparison.reused()} uploaded={comparison.uploaded()} removed={comparison.removed()}"
}

pub fn digest_frequency(chunks : Array[Chunk]) -> Array[(String, Int)] {
  let result = []
  for digest in unique_digests(chunks.map(c => c.id())) {
    result.push((digest, count_digest(chunks.map(c => c.id()), digest)))
  }
  result
}

pub fn most_repeated(chunks : Array[Chunk]) -> (String, Int)? {
  let frequencies = digest_frequency(chunks)
  if frequencies.length() == 0 { return None }
  let mut best = frequencies[0]
  for item in frequencies {
    if item.1 > best.1 { best = item }
  }
  Some(best)
}

pub fn profile_is_reasonable(profile : ChunkProfile, config : ChunkerConfig) -> Bool {
  if profile.count() == 0 { return true }
  profile.minimum() >= config.minimum() && profile.maximum() <= config.maximum()
}

pub fn compare_boundaries(left : Array[Chunk], right : Array[Chunk]) -> Int {
  let left_boundaries = chunk_boundaries(left)
  let right_boundaries = chunk_boundaries(right)
  let shared = if left_boundaries.length() < right_boundaries.length() { left_boundaries.length() } else { right_boundaries.length() }
  let mut matches = 0
  for i in 0.. Array[(Int, String)] {
  chunks.map(c => (c.range().start, c.id()))
}

pub fn content_overlap(left : Array[Chunk], right : Array[Chunk]) -> Int {
  let left_ids = left.map(c => c.id())
  let mut total = 0
  for chunk in right {
    if index_of_digest(left_ids, chunk.id()) is Some(_) { total = total + chunk.size() }
  }
  total
}

pub fn format_histogram(histogram : Array[Int]) -> String {
  let out = StringBuilder::new()
  for i, count in histogram {
    if i > 0 { out.write_string(",") }
    out.write_string(i.to_string() + ":" + count.to_string())
  }
  out.to_string()
}