///|
/// A normalized half-open interval used by coordinate set operations.
pub struct CoordinateInterval {
  start : Int
  end : Int
} derive(Debug, Eq)

///|
/// Summary of interval union/intersection calculations.
pub struct IntervalCoverage {
  intervals : Array[CoordinateInterval]
  covered_bases : Int
  minimum : Int
  maximum : Int
  gaps : Int
} derive(Debug, Eq)

///|
/// Convert a location into sorted, valid inclusive coordinate intervals.
pub fn location_intervals(location : Location) -> Array[CoordinateInterval] {
  let result : Array[CoordinateInterval] = []
  for range in location.ranges {
    if range.start <= range.end {
      result.push({ start: range.start, end: range.end })
    }
  }
  result.sort_by(fn(left, right) { left.start - right.start })
  result
}

///|
/// Merge touching and overlapping intervals into a minimal union.
pub fn merge_coordinate_intervals(
  intervals : Array[CoordinateInterval],
) -> Array[CoordinateInterval] {
  let sorted = intervals.copy()
  sorted.sort_by(fn(left, right) {
    if left.start == right.start {
      left.end - right.end
    } else {
      left.start - right.start
    }
  })
  let result : Array[CoordinateInterval] = []
  for current in sorted {
    match result.get(result.length() - 1) {
      None => result.push(current)
      Some(previous) if current.start <= previous.end + 1 =>
        result[result.length() - 1] = {
          start: previous.start,
          end: Int::max(previous.end, current.end),
        }
      Some(_) => result.push(current)
    }
  }
  result
}

///|
/// Calculate the intersection of two coordinate sets.
pub fn intersect_coordinate_intervals(
  left : Array[CoordinateInterval],
  right : Array[CoordinateInterval],
) -> Array[CoordinateInterval] {
  let result : Array[CoordinateInterval] = []
  for a in left {
    for b in right {
      let start = Int::max(a.start, b.start)
      let end = Int::min(a.end, b.end)
      if start <= end {
        result.push({ start, end })
      }
    }
  }
  merge_coordinate_intervals(result)
}

///|
/// Calculate the number of bases covered by a coordinate set.
pub fn coordinate_coverage(intervals : Array[CoordinateInterval]) -> Int {
  merge_coordinate_intervals(intervals).fold(init=0, fn(total, item) {
    total + item.end - item.start + 1
  })
}

///|
/// Calculate the number of shared bases between two locations.
pub fn location_overlap_length(left : Location, right : Location) -> Int {
  coordinate_coverage(
    intersect_coordinate_intervals(
      location_intervals(left),
      location_intervals(right),
    ),
  )
}

///|
/// Build a coverage report including unannotated gaps in the enclosing span.
pub fn interval_coverage(
  intervals : Array[CoordinateInterval],
) -> IntervalCoverage {
  let merged = merge_coordinate_intervals(intervals)
  if merged.length() == 0 {
    return {
      intervals: merged,
      covered_bases: 0,
      minimum: 0,
      maximum: 0,
      gaps: 0,
    }
  }
  let minimum = merged[0].start
  let maximum = merged[merged.length() - 1].end
  let mut gaps = 0
  for index in 1.. Array[Bool] {
  let mask = Array::make(Int::max(0, sequence_length), false)
  for interval in merge_coordinate_intervals(intervals) {
    let start = Int::max(1, interval.start)
    let end = Int::min(sequence_length, interval.end)
    if start <= end {
      for position in start..<=end {
        mask[position - 1] = true
      }
    }
  }
  mask
}

///|
/// Convert a mask back into maximal inclusive intervals.
pub fn mask_to_intervals(mask : Array[Bool]) -> Array[CoordinateInterval] {
  let result : Array[CoordinateInterval] = []
  let mut start = -1
  for index in 0..<=mask.length() {
    let covered = index < mask.length() && mask[index]
    if covered && start < 0 {
      start = index + 1
    } else if !covered && start >= 0 {
      result.push({ start, end: index })
      start = -1
    }
  }
  result
}

///|
/// Count bases in a record covered by features of a selected key.
pub fn record_key_coverage(record : Record, key : String) -> IntervalCoverage {
  let intervals : Array[CoordinateInterval] = []
  for feature in record.features {
    if feature.key == key && !location_is_remote(feature.location) {
      intervals.append(location_intervals(feature.location))
    }
  }
  interval_coverage(intervals)
}

///|
/// Determine whether an interval is wholly contained in another interval.
pub fn interval_contains(
  outer : CoordinateInterval,
  inner : CoordinateInterval,
) -> Bool {
  outer.start <= inner.start && inner.end <= outer.end
}

///|
/// Render interval sets as `start..end` values for logs and reports.
pub fn intervals_to_text(intervals : Array[CoordinateInterval]) -> String {
  merge_coordinate_intervals(intervals)
  .map(fn(item) { item.start.to_string() + ".." + item.end.to_string() })
  .join(",")
}

///|
pub fn CoordinateInterval::to_json_string(self : CoordinateInterval) -> String {
  "{\"start\":" +
  self.start.to_string() +
  ",\"end\":" +
  self.end.to_string() +
  "}"
}

///|
pub fn IntervalCoverage::to_json_string(self : IntervalCoverage) -> String {
  "{\"intervals\":[" +
  self.intervals.map(fn(item) { item.to_json_string() }).join(",") +
  "],\"covered_bases\":" +
  self.covered_bases.to_string() +
  ",\"minimum\":" +
  self.minimum.to_string() +
  ",\"maximum\":" +
  self.maximum.to_string() +
  ",\"gaps\":" +
  self.gaps.to_string() +
  "}"
}