///|
/// Independent per-variable integer intervals. This cheap layer is what the
/// octagon domain improves on; conversion helpers make the precision gap
/// measurable. All operations return fresh states.
pub struct Box {
  dimensions : Int32
  lower : Array[Int64?]
  upper : Array[Int64?]
  empty : Bool
}

///|
fn box_compatible(a : Box, b : Box) -> Unit raise OctagonError {
  if a.dimensions != b.dimensions {
    raise Invalid("box dimensions differ: \{a.dimensions} vs \{b.dimensions}")
  }
}

///|
fn lower_min(a : Int64?, b : Int64?) -> Int64? {
  match (a, b) {
    (None, _) | (_, None) => None
    (Some(x), Some(y)) => Some(if x < y { x } else { y })
  }
}

///|
fn upper_max(a : Int64?, b : Int64?) -> Int64? {
  match (a, b) {
    (None, _) | (_, None) => None
    (Some(x), Some(y)) => Some(if x > y { x } else { y })
  }
}

///|
fn add_low(a : Int64?, b : Int64?) -> Int64? {
  match (a, b) {
    (Some(x), Some(y)) => Some(x + y)
    _ => None
  }
}

///|
fn add_high(a : Int64?, b : Int64?) -> Int64? {
  match (a, b) {
    (Some(x), Some(y)) => Some(x + y)
    _ => None
  }
}

///|
fn negate(v : Int64?) -> Int64? {
  match v {
    None => None
    Some(x) => Some(-x)
  }
}

///|
pub fn box_top(n : Int32) -> Box raise OctagonError {
  validate_dimensions(n)
  let lower : Array[Int64?] = Array::makei(n, _ => None)
  let upper : Array[Int64?] = Array::makei(n, _ => None)
  { dimensions: n, lower, upper, empty: false, }
}

///|
pub fn box_bottom(n : Int32) -> Box raise OctagonError {
  let b = box_top(n)
  { ..b, empty: true, }
}

///|
pub fn Box::size(self : Box) -> Int32 {
  self.dimensions
}

///|
pub fn Box::is_bottom(self : Box) -> Bool {
  self.empty
}

///|
pub fn Box::is_top(self : Box) -> Bool {
  if self.empty {
    return false
  }
  for i in 0.. Interval? raise OctagonError {
  variable(self.dimensions, i)
  if self.empty {
    None
  } else {
    Some({ lower: self.lower[i], upper: self.upper[i], })
  }
}

///|
pub fn Box::contains(
  self : Box,
  values : Array[Int64],
) -> Bool raise OctagonError {
  if values.length() != self.dimensions {
    raise Invalid("box witness dimension mismatch")
  }
  if self.empty {
    return false
  }
  for i in 0.. if v < lo { return false }
      None => ()
    }
    match self.upper[i] {
      Some(hi) => if v > hi { return false }
      None => ()
    }
  }
  true
}

///|
pub fn Box::meet(self : Box, other : Box) -> Box raise OctagonError {
  box_compatible(self, other)
  if self.empty || other.empty {
    return box_bottom(self.dimensions)
  }
  let lower : Array[Int64?] = []
  let upper : Array[Int64?] = []
  for i in 0.. x
      (x, None) => x
      (Some(a), Some(b)) => Some(if a > b { a } else { b })
    }
    let hi = match (self.upper[i], other.upper[i]) {
      (None, x) => x
      (x, None) => x
      (Some(a), Some(b)) => Some(if a < b { a } else { b })
    }
    match (lo, hi) {
      (Some(a), Some(b)) => if a > b { return box_bottom(self.dimensions) }
      _ => ()
    }
    lower.push(lo)
    upper.push(hi)
  }
  { dimensions: self.dimensions, lower, upper, empty: false, }
}

///|
pub fn Box::join(self : Box, other : Box) -> Box raise OctagonError {
  box_compatible(self, other)
  if self.empty {
    return other
  }
  if other.empty {
    return self
  }
  let lower : Array[Int64?] = []
  let upper : Array[Int64?] = []
  for i in 0.. Box raise OctagonError {
  box_compatible(self, next)
  if self.empty {
    return next
  }
  if next.empty {
    return self
  }
  let lower : Array[Int64?] = []
  let upper : Array[Int64?] = []
  for i in 0.. Bool raise OctagonError {
  box_compatible(self, other)
  if self.empty {
    return true
  }
  if other.empty {
    return false
  }
  for i in 0.. if a < b { return false }
      (None, Some(_)) => return false
      _ => ()
    }
    match (self.upper[i], other.upper[i]) {
      (Some(a), Some(b)) => if a > b { return false }
      (None, Some(_)) => return false
      _ => ()
    }
  }
  true
}

///|
pub fn Box::equivalent(self : Box, other : Box) -> Bool raise OctagonError {
  self.subset_of(other) && other.subset_of(self)
}

///|
fn box_term_range(b : Box, t : Term) -> (Int64?, Int64?) {
  let lo = b.lower[t.variable]
  let hi = b.upper[t.variable]
  if t.sign == 1 {
    (lo, hi)
  } else {
    (negate(hi), negate(lo))
  }
}

///|
fn box_expr_range(b : Box, c : Constraint) -> (Int64?, Int64?) {
  let (lo, hi) = box_term_range(b, c.left)
  match c.right {
    None => (lo, hi)
    Some(t) => {
      let (rlo, rhi) = box_term_range(b, t)
      (add_low(lo, rlo), add_high(hi, rhi))
    }
  }
}

///|
pub fn Box::entails(self : Box, c : Constraint) -> Bool raise OctagonError {
  validate_constraint(self.dimensions, c)
  if self.empty {
    return true
  }
  let (_, hi) = box_expr_range(self, c)
  match hi {
    Some(v) => v <= c.bound
    None => false
  }
}

///|
pub fn Box::assign(
  self : Box,
  target : Int32,
  source : Term,
  offset : Int64,
) -> Box raise OctagonError {
  variable(self.dimensions, target)
  ignore(term_index(self.dimensions, source))
  validate_bound(offset)
  if self.empty {
    return self
  }
  let (lo, hi) = box_term_range(self, source)
  let new_low = add_low(lo, Some(offset))
  let new_high = add_high(hi, Some(offset))
  let lower = self.lower.copy()
  let upper = self.upper.copy()
  lower[target] = new_low
  upper[target] = new_high
  { dimensions: self.dimensions, lower, upper, empty: false, }
}

///|
pub fn Box::forget(self : Box, target : Int32) -> Box raise OctagonError {
  variable(self.dimensions, target)
  if self.empty {
    return self
  }
  let lower = self.lower.copy()
  let upper = self.upper.copy()
  lower[target] = None
  upper[target] = None
  { dimensions: self.dimensions, lower, upper, empty: false, }
}

///|
pub fn Box::set_constant(
  self : Box,
  target : Int32,
  value : Int64,
) -> Box raise OctagonError {
  variable(self.dimensions, target)
  validate_bound(value)
  if self.empty {
    return self
  }
  let lower = self.lower.copy()
  let upper = self.upper.copy()
  lower[target] = Some(value)
  upper[target] = Some(value)
  { dimensions: self.dimensions, lower, upper, empty: false, }
}

///|
/// Choose a concrete point inside the box, or `None` for the empty box.
pub fn Box::witness(self : Box) -> Array[Int64]? raise OctagonError {
  if self.empty {
    return None
  }
  let values : Array[Int64] = []
  for i in 0.. if value < lo { value = lo }
      None => ()
    }
    match self.upper[i] {
      Some(hi) => if value > hi { value = hi }
      None => ()
    }
    values.push(value)
  }
  if !self.contains(values) {
    raise Arithmetic("box witness failed membership check")
  }
  Some(values)
}

///|
/// Forget every relation and keep only the independent intervals.
pub fn Octagon::to_box(self : Octagon) -> Box raise OctagonError {
  if self.empty {
    return box_bottom(self.dimensions)
  }
  let ranges = self.intervals()
  let lower : Array[Int64?] = []
  let upper : Array[Int64?] = []
  for i in 0.. {
        lower.push(r.lower)
        upper.push(r.upper)
      }
      None => {
        lower.push(None)
        upper.push(None)
      }
    }
  }
  { dimensions: self.dimensions, lower, upper, empty: false, }
}

///|
/// Build the weakest octagon containing this box; all relations are dropped.
pub fn Box::to_octagon(self : Box) -> Octagon raise OctagonError {
  if self.empty {
    return bottom(self.dimensions)
  }
  let constraints : Array[Constraint] = []
  for i in 0.. constraints.push(lower(i, lo))
      None => ()
    }
    match self.upper[i] {
      Some(hi) => constraints.push(upper(i, hi))
      None => ()
    }
  }
  from_constraints(self.dimensions, constraints)
}

///|
/// Serialise the box as constraint text accepted by `parse_constraints`.
pub fn Box::to_text(self : Box) -> String raise OctagonError {
  if self.empty {
    raise Invalid("empty box has no finite text form")
  }
  if self.is_top() {
    return ""
  }
  let sb = StringBuilder()
  let mut first = true
  for i in 0.. Some("x\{i} in [\{lo}, \{hi}]")
      (Some(lo), None) => Some("x\{i} >= \{lo}")
      (None, Some(hi)) => Some("x\{i} <= \{hi}")
      (None, None) => None
    }
    match line {
      Some(text) => {
        if !first {
          sb.write("\n")
        }
        first = false
        sb.write(text)
      }
      None => ()
    }
  }
  sb.to_string()
}

///|
/// Least box containing every state in a non-empty compatible family.
pub fn box_join_all(states : Array[Box]) -> Box raise OctagonError {
  if states.length() == 0 {
    raise Invalid("box_join_all needs at least one state")
  }
  let mut acc = states[0]
  for i in 1.. Box raise OctagonError {
  if states.length() == 0 {
    raise Invalid("box_meet_all needs at least one state")
  }
  let mut acc = states[0]
  for i in 1.. String {
  if self.empty {
    return "bottom(\{self.dimensions})"
  }
  if self.is_top() {
    return "top(\{self.dimensions})"
  }
  let sb = StringBuilder()
  for i in 0.. 0 {
      sb.write("; ")
    }
    sb.write("x\{i} in ")
    sb.write(interval_text({ lower: self.lower[i], upper: self.upper[i], }))
  }
  sb.to_string()
}