// XLOOKUP subset: vector lookup_array / return_array (row or column), match
// modes 0 (exact), -1 (exact or next smaller), 1 (exact or next larger),
// 2 (wildcard, text only); search modes 1 (first-to-last), -1 (last-to-first),
// 2 (binary ascending) and -2 (binary descending).
//
// Binary search is a standard lower_bound over the vector in the declared sort
// direction. It assumes the data really is sorted; unsorted data may return a
// not-found fallback (adjudicated by corpus lookup-xlookup-0027..0030). Binary
// search and wildcard matching are not combined (#VALUE!). Duplicate keys are
// not specified by Excel's documentation; our descending path returns the
// duplicate nearest the small end of the descending order, which is what the
// 2024 probe showed.

fn xlookup_vector(v : Value) -> Result[Array[Value], XlError] {
  match v {
    Range(r) =>
      if r.rows == 1 || r.cols == 1 {
        Ok(r.cells)
      } else {
        Err(XlError::Value)
      }
    Err(e) => Err(e)
    _ => Err(XlError::Value)
  }
}

fn xlookup_mode_arg(args : Array[Thunk], i : Int, fallback : Int) -> Result[Int, XlError] {
  if i >= args.length() {
    return Ok(fallback)
  }
  match args[i]() {
    Err(e) => Err(e)
    v =>
      match to_number(scalarize(v)) {
        Err(e) => Err(e)
        Ok(d) =>
          // Real Excel rejects a non-integral match_mode/search_mode with
          // #VALUE! (corpus lookup-xlookup-0036: match_mode -1.9).
          if !d.is_finite() || d.abs() > 1000.0 || d != d.trunc() {
            Err(XlError::Value)
          } else {
            Ok(d.to_int())
          }
      }
  }
}

fn xlookup_exact(
  cells : Array[Value],
  lookup : Value,
  forward : Bool,
  wildcard : Bool
) -> Int {
  let n = cells.length()
  let pattern = match lookup {
    Text(s) => Some(s)
    _ => None
  }
  let mut k = 0
  while k < n {
    let idx = if forward { k } else { n - 1 - k }
    let hit = if wildcard {
      match (pattern, cells[idx]) {
        (Some(p), Text(s)) => wildcard_match(p, s)
        (None, cell) => cell_eq(cell, lookup)
        _ => false
      }
    } else {
      match cells[idx] {
        // Error cells inside the lookup vector can be compared: unknown is
        // "no match" for exact search rather than a hard failure.
        Err(_) => false
        cell => cell_eq(cell, lookup)
      }
    }
    if hit {
      return idx
    }
    k += 1
  }
  -1
}

// Approximate modes scan linearly and pick the closest comparable candidate:
// mode -1 keeps the largest value <= lookup, mode 1 the smallest >= lookup.
// An exact hit wins immediately in the requested search direction.
fn xlookup_approx(
  cells : Array[Value],
  lookup : Value,
  want_smaller : Bool,
  forward : Bool
) -> Int {
  let n = cells.length()
  let exact = xlookup_exact(cells, lookup, forward, false)
  if exact >= 0 {
    return exact
  }
  let mut best = -1
  let mut k = 0
  while k < n {
    let idx = if forward { k } else { n - 1 - k }
    match cells[idx] {
      Err(_) => ()
      cell =>
        match compare_values(cell, lookup) {
          Err(_) => ()
          Ok(ord) => {
            let candidate = if want_smaller { ord < 0 } else { ord > 0 }
            if candidate {
              let better = if best < 0 {
                true
              } else {
                match compare_values(cell, cells[best]) {
                  Ok(cmp) => if want_smaller { cmp > 0 } else { cmp < 0 }
                  Err(_) => false
                }
              }
              if better {
                best = idx
              }
            }
          }
        }
    }
    k += 1
  }
  best
}

// Binary search over a vector assumed sorted in the declared direction.
// `ascending` reinterprets the array as its reverse, which keeps the
// lower_bound logic identical for both directions and reproduces the duplicate
// position observed in the 2024 probe (descending duplicate keys resolve to
// the last appearance in the original array).
fn xlookup_binary(
  cells : Array[Value],
  lookup : Value,
  match_mode : Int,
  ascending : Bool
) -> Result[Int, XlError] {
  let n = cells.length()
  if n == 0 {
    return Ok(-1)
  }
  let at = (i : Int) => if ascending { cells[i] } else { cells[n - 1 - i] }
  let mut lo = 0
  let mut hi = n
  while lo < hi {
    let mid = (lo + hi) / 2
    let ord = match compare_values(at(mid), lookup) {
      Ok(v) => v
      Err(e) => return Err(e)
    }
    if ord < 0 {
      lo = mid + 1
    } else {
      hi = mid
    }
  }
  let pos = lo
  let exact = if pos < n {
    match compare_values(at(pos), lookup) {
      Ok(0) => true
      _ => false
    }
  } else {
    false
  }
  let view_idx = if match_mode == 0 {
    if exact {
      pos
    } else {
      return Ok(-1)
    }
  } else if match_mode == -1 {
    if exact {
      pos
    } else if pos > 0 {
      pos - 1
    } else {
      return Ok(-1)
    }
  } else if exact {
    pos
  } else if pos < n {
    pos
  } else {
    return Ok(-1)
  }
  Ok(if ascending { view_idx } else { n - 1 - view_idx })
}

fn fn_xlookup(_ctx : Ctx, args : Array[Thunk]) -> Value {
  // 1. lookup_value (scalar; >1-cell range has no implicit intersection here).
  let lookup = match args[0]() {
    Err(e) => return Value::Err(e)
    v =>
      match scalarize(v) {
        Err(e) => return Value::Err(e)
        s => s
      }
  }
  if lookup is Range(_) {
    return Value::Err(XlError::Value)
  }
  // 2. lookup_array and 3. return_array: same-shape vectors.
  let lookup_cells = match xlookup_vector(args[1]()) {
    Ok(a) => a
    Err(e) => return Value::Err(e)
  }
  let return_cells = match xlookup_vector(args[2]()) {
    Ok(a) => a
    Err(e) => return Value::Err(e)
  }
  if lookup_cells.length() != return_cells.length() {
    return Value::Err(XlError::Value)
  }
  // 5. match_mode / 6. search_mode are eager numeric arguments.
  let match_mode = match xlookup_mode_arg(args, 4, 0) {
    Ok(m) => m
    Err(e) => return Value::Err(e)
  }
  let search_mode = match xlookup_mode_arg(args, 5, 1) {
    Ok(s) => s
    Err(e) => return Value::Err(e)
  }
  if match_mode != 0 && match_mode != -1 && match_mode != 1 && match_mode != 2 {
    return Value::Err(XlError::Value)
  }
  let (forward, binary) = match search_mode {
    1 => (true, None)
    -1 => (false, None)
    2 => (true, Some(true))
    -2 => (false, Some(false))
    _ => return Value::Err(XlError::Value)
  }
  let found = match binary {
    Some(ascending) => {
      if match_mode == 2 {
        // Wildcard matching cannot be combined with binary search.
        return Value::Err(XlError::Value)
      }
      match xlookup_binary(lookup_cells, lookup, match_mode, ascending) {
        Ok(i) => i
        Err(e) => return Value::Err(e)
      }
    }
    None => {
      if match_mode == 0 {
        xlookup_exact(lookup_cells, lookup, forward, false)
      } else if match_mode == 2 {
        xlookup_exact(lookup_cells, lookup, forward, true)
      } else if match_mode == -1 {
        xlookup_approx(lookup_cells, lookup, true, forward)
      } else {
        xlookup_approx(lookup_cells, lookup, false, forward)
      }
    }
  }
  if found < 0 {
    // 4. if_not_found is only evaluated on a miss.
    return if args.length() >= 4 { args[3]() } else { Value::Err(XlError::NA) }
  }
  match return_cells[found] {
    Blank => Value::Num(0.0)
    v => v
  }
}