///|
pub(open) trait Shrink {
  shrink(Self) -> Iter[Self] = _
}

///|
impl Shrink with shrink(_a) {
  Iter::empty()
}

///|
pub impl Shrink for Int with shrink(x) {
  @utils.apply_while_list(x, fn(z) { z / 2 }, fn(z) { (x - z).abs() < x.abs() })
  .map(fn(i) { x - i })
  .iter()
  .concat(Iter::singleton(0))
  .filter(fn(u) { u != x })
}

///|
test "shrink int" {
  json_inspect(Shrink::shrink(100), content=[99, 97, 94, 88, 75, 50, 0])
  json_inspect(Shrink::shrink(0), content=[])
}

///|
pub impl Shrink for Int64 with shrink(x) {
  @utils.apply_while_list(x, fn(z) { z / 2 }, fn(z) { (x - z).abs() < x.abs() })
  .map(fn(i) { x - i })
  .iter()
  .concat(Iter::singleton(0))
  .filter(fn(u) { u != x })
}

///|
test "shrink int64" {
  json_inspect(Shrink::shrink(10000L), content=[
    "9999", "9998", "9996", "9991", "9981", "9961", "9922", "9844", "9688", "9375",
    "8750", "7500", "5000", "0",
  ])
}

///|
pub impl Shrink for UInt with shrink(x) {
  @utils.apply_while_list(x, fn(z) { z / 2 }, fn(z) { z > 0 })
  .map(fn(i) { x - i })
  .iter()
  .concat(Iter::singleton(0))
  .filter(fn(u) { u != x })
}

///|
test "shrink uint" {
  json_inspect(Shrink::shrink(37000U), content=[
    36999, 36998, 36996, 36991, 36982, 36964, 36928, 36856, 36711, 36422, 35844,
    34688, 32375, 27750, 18500, 0,
  ])
}

///|
pub impl Shrink for UInt64 with shrink(x) {
  @utils.apply_while_list(x, fn(z) { z / 2 }, fn(z) { z > 0 })
  .map(fn(i) { x - i })
  .iter()
  .concat(Iter::singleton(0))
  .filter(fn(u) { u != x })
}

///|
test "shrink uint64" {
  json_inspect(Shrink::shrink((42000 : UInt64)), content=[
    "41999", "41998", "41995", "41990", "41980", "41959", "41918", "41836", "41672",
    "41344", "40688", "39375", "36750", "31500", "21000", "0",
  ])
}

///|
pub impl Shrink for Bool with shrink(b) {
  if !b {
    Iter::empty()
  } else {
    Iter::singleton(false)
  }
}

///|
test "shrink boolean" {
  json_inspect(Shrink::shrink(true), content=[false])
  json_inspect(Shrink::shrink(false), content=[])
}

///|
pub impl Shrink for Char with shrink(c) {
  let ci = c.to_int()
  if ci == 0 {
    return Iter::empty()
  } else {
    let (cl, ch) = (Int::unsafe_to_char(ci - 1), Int::unsafe_to_char(ci + 1))
    [cl, ch, 'a', 'A', '1', '\n', '\t', '\b', '\\', '\'', '\r', ' '].iter()
  }
}

///|
test "shrink char" {
  json_inspect(Shrink::shrink('测'), content=[
    "浊", "浌", "a", "A", "1", "\n", "\t", "\b", "\\", "'", "\r", " ",
  ])
}

///|
pub impl Shrink for Double

///|
pub impl Shrink for Float

///|
pub impl Shrink for String

///|
pub impl Shrink for Bytes

///|
pub impl[T : Shrink] Shrink for T? with shrink(x) {
  match x {
    None => Iter::empty()
    Some(v) =>
      Shrink::shrink(v).map(Option::Some(_)).concat(Iter::singleton(None))
  }
}

///|

///|
pub impl Shrink for Unit

///|
test "shrink option" {
  json_inspect(Shrink::shrink((None : Unit?)), content=[])
  json_inspect(Shrink::shrink(Some(1000)), content=[
    [999],
    [997],
    [993],
    [985],
    [969],
    [938],
    [875],
    [750],
    [500],
    [0],
    null,
  ])
}

///|
pub impl[T : Shrink, E : Shrink] Shrink for Result[T, E] with shrink(x) {
  match x {
    Ok(v) => Shrink::shrink(v).map(Result::Ok(_))
    Err(e) => Shrink::shrink(e).map(Result::Err(_))
  }
}

///|
test "shrink result" {
  let b : Result[Bool, Int] = Err(100)
  let x : Result[Bool, Int] = Ok(true)
  json_inspect(Shrink::shrink(b), content=[
    { "Err": 99 },
    { "Err": 97 },
    { "Err": 94 },
    { "Err": 88 },
    { "Err": 75 },
    { "Err": 50 },
    { "Err": 0 },
  ])
  json_inspect(Shrink::shrink(x), content=[{ "Ok": false }])
}

///|
pub impl[A : Shrink, B : Shrink] Shrink for (A, B) with shrink(x) {
  let (a, b) = x
  Shrink::shrink(a)
  .map(fn(a1) { (a1, b) })
  .concat(Shrink::shrink(b).map(fn(b1) { (a, b1) }))
}

///|
test "shrink tuple" {
  let x = (120, true)
  json_inspect(Shrink::shrink(x), content=[
    [119, true],
    [117, true],
    [113, true],
    [105, true],
    [90, true],
    [60, true],
    [0, true],
    [120, false],
  ])
}

///|
pub impl[A : Shrink, B : Shrink, C : Shrink] Shrink for (A, B, C) with shrink(x) {
  let (a, b, c) = x
  Shrink::shrink((a, (b, c))).map(fn(y) {
    let (a1, (b1, c1)) = y
    (a1, b1, c1)
  })
}

///|
pub impl[A : Shrink, B : Shrink, C : Shrink, D : Shrink] Shrink for (A, B, C, D) with shrink(
  x,
) {
  let (a, b, c, d) = x
  Shrink::shrink((a, (b, c, d))).map(fn(y) {
    let (a1, (b1, c1, d1)) = y
    (a1, b1, c1, d1)
  })
}

///|
pub impl[A : Shrink, B : Shrink, C : Shrink, D : Shrink, E : Shrink] Shrink for (
  A,
  B,
  C,
  D,
  E,
) with shrink(x) {
  let (a, b, c, d, e) = x
  Shrink::shrink((a, (b, c, d, e))).map(fn(y) {
    let (a1, (b1, c1, d1, e1)) = y
    (a1, b1, c1, d1, e1)
  })
}

///|
pub impl[A : Shrink, B : Shrink, C : Shrink, D : Shrink, E : Shrink, F : Shrink] Shrink for (
  A,
  B,
  C,
  D,
  E,
  F,
) with shrink(x) {
  let (a, b, c, d, e, f) = x
  Shrink::shrink((a, (b, c, d, e, f))).map(fn(y) {
    let (a1, (b1, c1, d1, e1, f1)) = y
    (a1, b1, c1, d1, e1, f1)
  })
}

///|
test "shrink 6-tuple" {
  let x = (20, 'A', 30U, true, true, true)
  json_inspect(Shrink::shrink(x), content=[
    [19, "A", 30, true, true, true],
    [18, "A", 30, true, true, true],
    [15, "A", 30, true, true, true],
    [10, "A", 30, true, true, true],
    [0, "A", 30, true, true, true],
    [20, "@", 30, true, true, true],
    [20, "B", 30, true, true, true],
    [20, "a", 30, true, true, true],
    [20, "A", 30, true, true, true],
    [20, "1", 30, true, true, true],
    [20, "\n", 30, true, true, true],
    [20, "\t", 30, true, true, true],
    [20, "\b", 30, true, true, true],
    [20, "\\", 30, true, true, true],
    [20, "'", 30, true, true, true],
    [20, "\r", 30, true, true, true],
    [20, " ", 30, true, true, true],
    [20, "A", 29, true, true, true],
    [20, "A", 27, true, true, true],
    [20, "A", 23, true, true, true],
    [20, "A", 15, true, true, true],
    [20, "A", 0, true, true, true],
    [20, "A", 30, false, true, true],
    [20, "A", 30, true, false, true],
    [20, "A", 30, true, true, false],
  ])
}

///|
pub impl[T : Shrink] Shrink for List[T] with shrink(xs) {
  let n = xs.length()
  fn shr_sub_terms(lst : List[T]) {
    match lst {
      Empty => Iter::empty()
      More(x, tail=xs) =>
        T::shrink(x)
        .map(fn(x_) { xs.add(x_) })
        .concat(shr_sub_terms(xs).map(fn(xs_) { xs_.add(x) }))
    }
  }

  @utils.apply_while_list(n, fn(x) { x / 2 }, fn(x) { x > 0 })
  .map(fn(k) { @utils.removes_list(k, n, xs) })
  .flatten()
  .iter()
  .concat(shr_sub_terms(xs))
}

///|
test "shrink int list" {
  let il : List[Int] = @list.from_array([1, 2, 3, 4, 5, 6])
  let s = Shrink::shrink(il)
  json_inspect(s, content=[
    [2, 3, 4, 5, 6],
    [1, 3, 4, 5, 6],
    [1, 2, 4, 5, 6],
    [1, 2, 3, 5, 6],
    [1, 2, 3, 4, 6],
    [4, 5, 6],
    [0, 2, 3, 4, 5, 6],
    [1, 1, 3, 4, 5, 6],
    [1, 0, 3, 4, 5, 6],
    [1, 2, 2, 4, 5, 6],
    [1, 2, 0, 4, 5, 6],
    [1, 2, 3, 3, 5, 6],
    [1, 2, 3, 2, 5, 6],
    [1, 2, 3, 0, 5, 6],
    [1, 2, 3, 4, 4, 6],
    [1, 2, 3, 4, 3, 6],
    [1, 2, 3, 4, 0, 6],
    [1, 2, 3, 4, 5, 5],
    [1, 2, 3, 4, 5, 3],
    [1, 2, 3, 4, 5, 0],
  ])
}

///|
pub impl[X : Shrink] Shrink for Array[X] with shrink(xs) {
  let view = xs[:]
  let n = view.length()
  fn shr_sub_terms(arr : ArrayView[X]) {
    match arr {
      [] => Iter::empty()
      [x, .. xs] =>
        X::shrink(x)
        .map(fn(x_) { [x_, ..xs] })
        .concat(shr_sub_terms(xs).map(fn(xs_) { [x, ..xs_] }))
    }
  }

  @utils.apply_while_array(n, fn(x) { x / 2 }, fn(x) { x > 0 })
  .map(fn(k) { @utils.removes_array(k, n, xs) })
  .flatten()
  .iter()
  .concat(shr_sub_terms(view))
}

///|
test "shrink array" {
  let ar = [1, 2, 3, 4, 5, 6]
  let s = Shrink::shrink(ar)
  json_inspect(s, content=[
    [2, 3, 4, 5, 6],
    [1, 3, 4, 5, 6],
    [1, 2, 4, 5, 6],
    [1, 2, 3, 5, 6],
    [1, 2, 3, 4, 6],
    [4, 5, 6],
    [0, 2, 3, 4, 5, 6],
    [1, 1, 3, 4, 5, 6],
    [1, 0, 3, 4, 5, 6],
    [1, 2, 2, 4, 5, 6],
    [1, 2, 0, 4, 5, 6],
    [1, 2, 3, 3, 5, 6],
    [1, 2, 3, 2, 5, 6],
    [1, 2, 3, 0, 5, 6],
    [1, 2, 3, 4, 4, 6],
    [1, 2, 3, 4, 3, 6],
    [1, 2, 3, 4, 0, 6],
    [1, 2, 3, 4, 5, 5],
    [1, 2, 3, 4, 5, 3],
    [1, 2, 3, 4, 5, 0],
  ])
}

///|
pub impl[X : Shrink] Shrink for Iter[X] with shrink(xs) {
  let arr = xs.to_array()
  let its : Array[_] = Array::makei(arr.length(), fn(x) {
    X::shrink(arr[x])
    .map(fn(y) {
      let cp = arr.copy()
      cp[x] = y
      cp.iter()
    })
    .to_array()
  }).flatten()
  let rms : Array[Iter[X]] = arr.mapi(fn(i, _) {
    let a = arr.copy()
    a.remove(i) |> ignore
    a.iter()
  })
  rms.iter().concat(its.iter())
}

///|
test "shrink iter" {
  let it = [1, 2, 3, 4, 5, 6].iter()
  json_inspect(Shrink::shrink(it), content=[
    [2, 3, 4, 5, 6],
    [1, 3, 4, 5, 6],
    [1, 2, 4, 5, 6],
    [1, 2, 3, 5, 6],
    [1, 2, 3, 4, 6],
    [1, 2, 3, 4, 5],
    [0, 2, 3, 4, 5, 6],
    [1, 1, 3, 4, 5, 6],
    [1, 0, 3, 4, 5, 6],
    [1, 2, 2, 4, 5, 6],
    [1, 2, 0, 4, 5, 6],
    [1, 2, 3, 3, 5, 6],
    [1, 2, 3, 2, 5, 6],
    [1, 2, 3, 0, 5, 6],
    [1, 2, 3, 4, 4, 6],
    [1, 2, 3, 4, 3, 6],
    [1, 2, 3, 4, 0, 6],
    [1, 2, 3, 4, 5, 5],
    [1, 2, 3, 4, 5, 3],
    [1, 2, 3, 4, 5, 0],
  ])
}