// HELPERS
import { DateTime, isDateTime, numberToJsDate, parseDateTime } from "../helpers/dates";
import { memoize } from "../helpers/misc";
import { isNumber, parseNumber } from "../helpers/numbers";
import { _t } from "../translation";
import { CellValue } from "../types/cells";
import { CellErrorType, ErrorValue, EvaluationError, errorTypes } from "../types/errors";
import { LookupCaches } from "../types/functions";
import { Locale } from "../types/locale";
import {
  Arg,
  FunctionResultNumber,
  FunctionResultObject,
  Matrix,
  Maybe,
  SortDirection,
  isMatrix,
} from "../types/misc";

const SORT_TYPES_ORDER = ["number", "string", "boolean", "undefined"];

export function inferFormat(data: Arg | undefined): string | undefined {
  if (data === undefined) {
    return undefined;
  }

  if (isMatrix(data)) {
    return data[0][0]?.format;
  }
  return data.format;
}

export function isEvaluationError(error: Maybe<CellValue>): error is ErrorValue {
  return typeof error === "string" && errorTypes.has(error);
}

export function valueNotAvailable(searchKey: Maybe<FunctionResultObject>): FunctionResultObject {
  return {
    value: CellErrorType.NotAvailable,
    message: _t("Did not find value '%s' in [[FUNCTION_NAME]] evaluation.", toString(searchKey)),
  };
}

// -----------------------------------------------------------------------------
// FORMAT FUNCTIONS
// -----------------------------------------------------------------------------

const expectNumberValueError = (value: string) =>
  _t(
    "The function [[FUNCTION_NAME]] expects a number value, but '%s' is a string, and cannot be coerced to a number.",
    value
  );

export const expectReferenceError = _t(
  "The function [[FUNCTION_NAME]] expects a reference to a cell or range."
);

export const expectNumberRangeError = (lowerBound: number, upperBound: number, value: number) =>
  _t(
    "The function [[FUNCTION_NAME]] expects a number value between %s and %s inclusive, but receives %s.",
    lowerBound.toString(),
    upperBound.toString(),
    value.toString()
  );

export const expectStringSetError = (stringSet: string[], value: string) => {
  const stringSetString = stringSet.map((str) => `'${str}'`).join(", ");
  return _t(
    "The function [[FUNCTION_NAME]] has an argument with value '%s'. It should be one of: %s.",
    value,
    stringSetString
  );
};

export function toNumber(
  data: FunctionResultObject | CellValue | undefined,
  locale: Locale
): number {
  const value = toValue(data);
  switch (typeof value) {
    case "number":
      return value;
    case "boolean":
      return value ? 1 : 0;
    case "string":
      if (isNumber(value, locale) || value === "") {
        return parseNumber(value, locale);
      }
      const internalDate = parseDateTime(value, locale);
      if (internalDate) {
        return internalDate.value;
      }
      throw new EvaluationError(expectNumberValueError(value));
    default:
      return 0;
  }
}

export function tryToNumber(
  value: string | number | boolean | null | undefined,
  locale: Locale
): number | undefined {
  try {
    return toNumber(value, locale);
  } catch (e) {
    return undefined;
  }
}

export function toNumberMatrix(data: Arg, argName: string): Matrix<number> {
  return toMatrix(data).map((row) => {
    return row.map((cell) => {
      if (typeof cell.value !== "number") {
        let message = "";
        if (typeof cell === "object") {
          message = _t(
            "Function [[FUNCTION_NAME]] expects number values for %s, but got an empty value.",
            argName
          );
        } else if (typeof cell === "string") {
          message = _t(
            "Function [[FUNCTION_NAME]] expects number values for %s, but got a string.",
            argName
          );
        } else if (typeof cell === "boolean") {
          message = _t(
            "Function [[FUNCTION_NAME]] expects number values for %s, but got a boolean.",
            argName
          );
        }
        throw new EvaluationError(message);
      }
      return cell.value;
    });
  });
}

export function strictToNumber(
  data: FunctionResultObject | CellValue | undefined,
  locale: Locale
): number {
  const value = toValue(data);
  if (value === "") {
    throw new EvaluationError(expectNumberValueError(value));
  }
  return toNumber(value, locale);
}

export function toInteger(value: FunctionResultObject | CellValue | undefined, locale: Locale) {
  return Math.trunc(toNumber(value, locale));
}

export function strictToInteger(
  value: FunctionResultObject | CellValue | undefined,
  locale: Locale
) {
  return Math.trunc(strictToNumber(value, locale));
}

export function toString(data: FunctionResultObject | CellValue | undefined): string {
  const value = toValue(data);
  switch (typeof value) {
    case "string":
      return value;
    case "number":
      return value.toString();
    case "boolean":
      return value ? "TRUE" : "FALSE";
    default:
      return "";
  }
}

/**
 * Only converts the decimal separator, ignore number format such as % or dates
 */
export function toLocaleString(
  data: FunctionResultObject | CellValue | undefined,
  locale: Locale
): string {
  const value = toValue(data);
  switch (typeof value) {
    case "string":
      return value;
    case "number":
      return value.toString().replace(".", locale.decimalSeparator);
    case "boolean":
      return value ? "TRUE" : "FALSE";
    default:
      return "";
  }
}

/**
 * Normalize range by setting all the string in the range to lowercase and replacing
 * accent letters with plain letters
 */
export function normalizeRange<T>(range: T[]) {
  return range.map((item) => (typeof item === "string" ? normalizeString(item) : item));
}

/** Normalize string by setting it to lowercase and replacing accent letters with plain letters */
const normalizeString = memoize(function normalizeString(str: string) {
  return str
    .toLowerCase()
    .normalize("NFD")
    .replace(/[\u0300-\u036f]/g, "");
});

const expectBooleanValueError = (value: string) =>
  _t(
    "The function [[FUNCTION_NAME]] expects a boolean value, but '%s' is a text, and cannot be coerced to a boolean.",
    value
  );

export function toBoolean(data: FunctionResultObject | CellValue | undefined): boolean {
  const value = toValue(data);
  switch (typeof value) {
    case "boolean":
      return value;
    case "string":
      if (value) {
        const uppercaseVal = value.toUpperCase();
        if (uppercaseVal === "TRUE") {
          return true;
        }
        if (uppercaseVal === "FALSE") {
          return false;
        }
        throw new EvaluationError(expectBooleanValueError(value));
      } else {
        return false;
      }
    case "number":
      return value ? true : false;
    default:
      return false;
  }
}

function strictToBoolean(data: FunctionResultObject | CellValue | undefined): boolean {
  const value = toValue(data);
  if (value === "") {
    throw new EvaluationError(expectBooleanValueError(value));
  }
  return toBoolean(value);
}

export function toJsDate(
  data: FunctionResultObject | CellValue | undefined,
  locale: Locale
): DateTime {
  const value = toValue(data);
  return numberToJsDate(toNumber(value, locale));
}

export function toValue(data: FunctionResultObject | CellValue | undefined): CellValue | undefined {
  if (typeof data === "object" && data !== null && "value" in data) {
    if (isEvaluationError(data.value)) {
      throw data;
    }
    return data.value;
  }
  if (isEvaluationError(data)) {
    throw new EvaluationError("", data as string);
  }
  return data;
}
// -----------------------------------------------------------------------------
// VISIT FUNCTIONS
// -----------------------------------------------------------------------------
function visitArgs<T extends FunctionResultObject | CellValue>(
  args: (T | Matrix<T> | undefined)[],
  cellCb: (a: T) => void,
  dataCb: (a: T | undefined) => void
): void {
  for (const arg of args) {
    if (isMatrix(arg)) {
      // arg is ref to a Cell/Range
      const lenRow = arg.length;
      const lenCol = arg[0].length;
      for (let y = 0; y < lenCol; y++) {
        for (let x = 0; x < lenRow; x++) {
          cellCb(arg[x][y]);
        }
      }
    } else {
      // arg is set directly in the formula function
      dataCb(arg);
    }
  }
}

export function visitAny(args: Arg[], cb: (a: Maybe<FunctionResultObject>) => void): void {
  visitArgs(
    args,
    (cell) => {
      if (isEvaluationError(cell.value)) {
        throw cell;
      }
      cb(cell);
    },
    (arg) => {
      if (isEvaluationError(arg?.value)) {
        throw arg;
      }
      cb(arg);
    }
  );
}

export function visitNumbers(
  args: Arg[],
  cb: (arg: FunctionResultNumber) => void,
  locale: Locale
): void {
  visitArgs(
    args,
    (cell) => {
      if (typeof cell?.value === "number") {
        cb(cell as FunctionResultNumber);
      }
      if (isEvaluationError(cell?.value)) {
        throw cell;
      }
    },
    (arg) => {
      cb({ value: strictToNumber(arg, locale), format: arg?.format });
    }
  );
}

// -----------------------------------------------------------------------------
// REDUCE FUNCTIONS
// -----------------------------------------------------------------------------

function reduceArgs<T, M>(
  args: (T | Matrix<T>)[],
  cellCb: (acc: M, a: T) => M,
  dataCb: (acc: M, a: T) => M,
  initialValue: M,
  dir: "rowFirst" | "colFirst" = "rowFirst"
): M {
  let val = initialValue;
  for (const arg of args) {
    if (isMatrix(arg)) {
      // arg is ref to a Cell/Range
      const numberOfCols = arg.length;
      const numberOfRows = arg[0].length;

      if (dir === "rowFirst") {
        for (let row = 0; row < numberOfRows; row++) {
          for (let col = 0; col < numberOfCols; col++) {
            val = cellCb(val, arg[col][row]);
          }
        }
      } else {
        for (let col = 0; col < numberOfCols; col++) {
          for (let row = 0; row < numberOfRows; row++) {
            val = cellCb(val, arg[col][row]);
          }
        }
      }
    } else {
      // arg is set directly in the formula function
      val = dataCb(val, arg);
    }
  }
  return val;
}

export function reduceAny<T, M>(
  args: (T | Matrix<T>)[],
  cb: (acc: M, a: T) => M,
  initialValue: M,
  dir: "rowFirst" | "colFirst" = "rowFirst"
): M {
  return reduceArgs(args, cb, cb, initialValue, dir);
}

export function reduceNumbers(
  args: Arg[],
  cb: (acc: number, a: number) => number,
  initialValue: number,
  locale: Locale
): number {
  return reduceArgs(
    args,
    (acc, arg) => {
      const argValue = arg?.value;
      if (typeof argValue === "number") {
        return cb(acc, argValue);
      } else if (isEvaluationError(argValue)) {
        throw arg;
      }
      return acc;
    },
    (acc, arg) => {
      return cb(acc, strictToNumber(arg, locale));
    },
    initialValue
  );
}

export function reduceNumbersTextAs0(
  args: Arg[],
  cb: (acc: number, a: number) => number,
  initialValue: number,
  locale: Locale
): number {
  return reduceArgs(
    args,
    (acc, arg) => {
      const argValue = arg?.value;
      if (argValue !== undefined && argValue !== null) {
        if (typeof argValue === "number") {
          return cb(acc, argValue);
        } else if (typeof argValue === "boolean") {
          return cb(acc, toNumber(argValue, locale));
        } else if (isEvaluationError(argValue)) {
          throw arg;
        } else {
          return cb(acc, 0);
        }
      }
      return acc;
    },
    (acc, arg) => {
      return cb(acc, toNumber(arg, locale));
    },
    initialValue
  );
}

// -----------------------------------------------------------------------------
// MATRIX FUNCTIONS
// -----------------------------------------------------------------------------

/**
 * Generate a matrix of size nColumns x nRows and apply a callback on each position
 */
export function generateMatrix<T>(
  nColumns: number,
  nRows: number,
  callback: (col: number, row: number) => T
): Matrix<T> {
  const returned = Array(nColumns);
  for (let col = 0; col < nColumns; col++) {
    returned[col] = Array(nRows);
    for (let row = 0; row < nRows; row++) {
      returned[col][row] = callback(col, row);
    }
  }
  return returned;
}

export function matrixMap<T, M>(matrix: Matrix<T>, callback: (value: T) => M): Matrix<M> {
  if (matrix.length === 0) {
    return [];
  }
  return generateMatrix(matrix.length, matrix[0].length, (col, row) => callback(matrix[col][row]));
}

export function matrixForEach<T>(matrix: Matrix<T>, fn: (value: T) => void): void {
  const numberOfCols = matrix.length;
  const numberOfRows = matrix[0]?.length ?? 0;
  for (let col = 0; col < numberOfCols; col++) {
    for (let row = 0; row < numberOfRows; row++) {
      fn(matrix[col][row]);
    }
  }
}

export function transposeMatrix<T>(matrix: Matrix<T>): Matrix<T> {
  if (!matrix.length) {
    return [];
  }
  return generateMatrix(matrix[0].length, matrix.length, (i, j) => matrix[j][i]);
}

// -----------------------------------------------------------------------------
// CONDITIONAL EXPLORE FUNCTIONS
// -----------------------------------------------------------------------------

/**
 * This function allows to visit arguments and stop the visit if necessary.
 * It is mainly used to bypass argument evaluation for functions like OR or AND.
 */
function conditionalVisitArgs(
  args: Arg[],
  cellCb: (a: FunctionResultObject | undefined) => boolean,
  dataCb: (a: Maybe<FunctionResultObject>) => boolean
): void {
  for (const arg of args) {
    if (isMatrix(arg)) {
      // arg is ref to a Cell/Range
      const lenRow = arg.length;
      const lenCol = arg[0].length;
      for (let y = 0; y < lenCol; y++) {
        for (let x = 0; x < lenRow; x++) {
          if (!cellCb(arg[x][y] ?? undefined)) {
            return;
          }
        }
      }
    } else {
      // arg is set directly in the formula function
      if (!dataCb(arg)) {
        return;
      }
    }
  }
}

export function conditionalVisitBoolean(args: Arg[], cb: (a: boolean) => boolean): void {
  return conditionalVisitArgs(
    args,
    (arg) => {
      const argValue = arg?.value;
      if (typeof argValue === "boolean") {
        return cb(argValue);
      }
      if (typeof argValue === "number") {
        return cb(argValue ? true : false);
      }
      if (isEvaluationError(argValue)) {
        throw arg;
      }
      return true;
    },
    (arg) => {
      if (arg !== undefined && arg.value !== null) {
        return cb(strictToBoolean(arg));
      }
      return true;
    }
  );
}

// -----------------------------------------------------------------------------
// CRITERION FUNCTIONS
// -----------------------------------------------------------------------------

type Operator = ">" | ">=" | "<" | "<=" | "<>" | "=";
interface Predicate {
  operator: Operator;
  operand: number | string | boolean;
}

function getPredicate(descr: string, locale: Locale): Predicate {
  let operator: Operator;
  let operand: Maybe<CellValue>;

  let subString = descr.substring(0, 2);

  if (subString === "<=" || subString === ">=" || subString === "<>") {
    operator = subString;
    operand = descr.substring(2);
  } else {
    subString = descr.substring(0, 1);
    if (subString === "<" || subString === ">" || subString === "=") {
      operator = subString;
      operand = descr.substring(1);
    } else {
      operator = "=";
      operand = descr;
    }
  }

  if (isNumber(operand, locale) || isDateTime(operand, locale)) {
    operand = toNumber(operand, locale);
  } else if (operand === "TRUE" || operand === "FALSE") {
    operand = toBoolean(operand);
  }

  return { operator, operand };
}

/**
 * Converts a search string containing wildcard characters to a regular expression.
 *
 * The function iterates over each character in the input string. If the character is a wildcard
 * character ("?" or "*") and is not preceded by a "~", it is replaced by the corresponding regular
 * expression.
 * If the character is a special regular expression character, it is escaped with "\\".
 */
const wildcardToRegExp = memoize(function wildcardToRegExp(operand: string): RegExp {
  if (operand === "*") {
    return /.+/;
  }
  let exp = "";
  let predecessor = "";
  for (const char of operand) {
    if (char === "?" && predecessor !== "~") {
      exp += ".";
    } else if (char === "*" && predecessor !== "~") {
      exp += ".*";
    } else {
      if (char === "*" || char === "?") {
        //remove "~"
        exp = exp.slice(0, -1);
      }
      if (["^", ".", "[", "]", "$", "(", ")", "*", "+", "?", "|", "{", "}", "\\"].includes(char)) {
        exp += "\\";
      }
      exp += char;
    }
    predecessor = char;
  }
  return new RegExp("^" + exp + "$", "i");
});

function evaluatePredicate(
  value: CellValue | undefined = "",
  criterion: Predicate,
  locale: Locale
): boolean {
  const { operator, operand } = criterion;

  if (operand === undefined || value === null || operand === null) {
    return false;
  }
  if (typeof operand === "number" && operator === "=") {
    if (typeof value === "string" && (isNumber(value, locale) || isDateTime(value, locale))) {
      return toNumber(value, locale) === operand;
    }
    return value === operand;
  }

  if (operator === "<>" || operator === "=") {
    let result: boolean;
    if (typeof value === typeof operand) {
      if (value === "" && operand === "") {
        // fast path to avoid regex evaluation
        result = true;
      } else if (typeof value === "string" && typeof operand === "string") {
        result = wildcardToRegExp(operand).test(value);
      } else {
        result = value === operand;
      }
    } else {
      result = false;
    }
    return operator === "=" ? result : !result;
  }

  if (typeof value === typeof operand) {
    switch (operator) {
      case "<":
        return value < operand;
      case ">":
        return value > operand;
      case "<=":
        return value <= operand;
      case ">=":
        return value >= operand;
    }
  }
  return false;
}

/**
 * Functions used especially for predicate evaluation on ranges.
 *
 * Take ranges with same dimensions and take predicates, one for each range.
 * For (i, j) coordinates, if all elements with coordinates (i, j) of each
 * range correspond to the associated predicate, then the function uses a callback
 * function with the parameters "i" and "j".
 *
 * Syntax:
 * visitMatchingRanges([range1, predicate1, range2, predicate2, ...], cb(i,j), likeSelection)
 *
 * - range1 (range): The range to check against predicate1.
 * - predicate1 (string): The pattern or test to apply to range1.
 * - range2: (range, repeatable) ranges to check.
 * - predicate2 (string, repeatable): Additional pattern or test to apply to range2.
 *
 * - cb(i: number, j: number) => void: the callback function.
 *
 * - isQuery (boolean) indicates if the comparison with a string should be done as a SQL-like query.
 * (Ex1 isQuery = true, predicate = "abc", element = "abcde": predicate match the element),
 * (Ex2 isQuery = false, predicate = "abc", element = "abcde": predicate not match the element).
 * (Ex3 isQuery = true, predicate = "abc", element = "abc": predicate match the element),
 * (Ex4 isQuery = false, predicate = "abc", element = "abc": predicate match the element).
 */
export function visitMatchingRanges(
  args: Arg[],
  cb: (i: number, j: number) => void,
  locale: Locale,
  isQuery: boolean = false
): void {
  const countArg = args.length;

  if (countArg % 2 === 1) {
    throw new EvaluationError(
      _t("Function [[FUNCTION_NAME]] expects criteria_range and criterion to be in pairs.")
    );
  }

  const firstArg = toMatrix(args[0]);
  const dimRow = firstArg.length;
  const dimCol = firstArg[0].length;

  const predicates: Predicate[] = [];

  for (let i = 0; i < countArg - 1; i += 2) {
    const criteriaRange = toMatrix(args[i]);

    if (criteriaRange.length !== dimRow || criteriaRange[0].length !== dimCol) {
      throw new EvaluationError(
        _t("Function [[FUNCTION_NAME]] expects criteria_range to have the same dimension")
      );
    }

    const description = toLocaleString(args[i + 1] as Maybe<FunctionResultObject>, locale);
    const predicate = getPredicate(description, locale);
    if (isQuery && typeof predicate.operand === "string") {
      predicate.operand += "*";
    }
    predicates.push(predicate);
  }

  for (let i = 0; i < dimRow; i++) {
    for (let j = 0; j < dimCol; j++) {
      let validatedPredicates = true;
      for (let k = 0; k < countArg - 1; k += 2) {
        const criteriaValue = toMatrix(args[k])[i][j].value;
        const criterion = predicates[k / 2];
        validatedPredicates = evaluatePredicate(criteriaValue ?? undefined, criterion, locale);
        if (!validatedPredicates) {
          break;
        }
      }
      if (validatedPredicates) {
        cb(i, j);
      }
    }
  }
}

// -----------------------------------------------------------------------------
// COMMON FUNCTIONS
// -----------------------------------------------------------------------------

/**
 * Perform a dichotomic search on an array and return the index of the nearest match.
 *
 * The array should be sorted, if not an incorrect value might be returned. In the case where multiple
 * element of the array match the target, the method will return the first match if the array is sorted
 * in descending order, and the last match if the array is in ascending order.
 *
 *
 * @param data the array in which to search.
 * @param target the value to search.
 * @param mode "nextGreater/nextSmaller" : return next greater/smaller value if no exact match is found.
 * @param sortOrder whether the array is sorted in ascending or descending order.
 * @param rangeLength the number of elements to consider in the search array.
 * @param getValueInData function returning the element at index i in the search array.
 */
export function dichotomicSearch<T>(
  data: T,
  target: Maybe<FunctionResultObject>,
  mode: "nextGreater" | "nextSmaller" | "strict",
  sortOrder: SortDirection,
  rangeLength: number,
  getValueInData: (range: T, index: number) => CellValue | undefined
): number {
  if (target === undefined || target.value === null) {
    return -1;
  }
  if (isEvaluationError(target.value)) {
    throw target;
  }
  const _target = normalizeValue(target.value);
  const targetType = typeof _target;

  let matchVal: CellValue | undefined = undefined;
  let matchValIndex: number | undefined = undefined;

  let indexLeft = 0;
  let indexRight = rangeLength - 1;

  let indexMedian: number;
  let currentIndex: number;
  let currentVal: CellValue | undefined;
  let currentType: string;

  const getValue =
    sortOrder === "desc"
      ? (i: number) => normalizeValue(getValueInData(data, rangeLength - i - 1))
      : (i: number) => normalizeValue(getValueInData(data, i));

  while (indexRight - indexLeft >= 0) {
    indexMedian = Math.floor((indexLeft + indexRight) / 2);

    currentIndex = indexMedian;
    currentVal = getValue(currentIndex);
    currentType = typeof currentVal;

    // 1 - linear search to find value with the same type
    while (indexLeft < currentIndex && targetType !== currentType) {
      currentIndex--;
      currentVal = getValue(currentIndex);
      currentType = typeof currentVal;
    }
    if (currentType !== targetType || currentVal === undefined || currentVal === null) {
      indexLeft = indexMedian + 1;
      continue;
    }

    // 2 - check if value match
    if (mode === "strict" && currentVal === _target) {
      matchVal = currentVal;
      matchValIndex = currentIndex;
    } else if (mode === "nextSmaller" && currentVal <= _target) {
      if (
        matchVal === undefined ||
        matchVal === null ||
        matchVal < currentVal ||
        (matchVal === currentVal && matchValIndex! < currentIndex)
      ) {
        matchVal = currentVal;
        matchValIndex = currentIndex;
      }
    } else if (mode === "nextGreater" && currentVal >= _target) {
      if (
        matchVal === undefined ||
        matchVal > currentVal ||
        (matchVal === currentVal && matchValIndex! < currentIndex)
      ) {
        matchVal = currentVal;
        matchValIndex = currentIndex;
      }
    }

    // 3 - give new indexes for the Binary search
    if (currentVal > _target || (mode === "strict" && currentVal === _target)) {
      indexRight = currentIndex - 1;
    } else {
      indexLeft = indexMedian + 1;
    }
  }

  // note that valMinIndex could be 0
  if (matchValIndex === undefined) {
    return -1;
  }
  return sortOrder === "desc" ? rangeLength - matchValIndex - 1 : matchValIndex;
}

export type LinearSearchMode = "nextSmaller" | "nextGreater" | "strict" | "wildcard";

/**
 * Perform a linear search and return the index of the match.
 * -1 is returned if no value is found.
 *
 * Example:
 * - [3, 6, 10], 3 => 0
 * - [3, 6, 10], 6 => 1
 * - [3, 6, 10], 9 => -1
 * - [3, 6, 10], 2 => -1
 *
 * @param data the array to search in.
 * @param target the value to search in the array.
 * @param mode if "strict" return exact match index. "nextGreater" returns the next greater
 * element from the target and "nextSmaller" the next smaller
 * @param numberOfValues the number of elements to consider in the search array.
 * @param getValueInData function returning the element at index i in the search array.
 * @param reverseSearch if true, search in the array starting from the end.

 */
export function linearSearch<T>(
  data: T,
  target: Maybe<FunctionResultObject> | undefined,
  mode: LinearSearchMode,
  numberOfValues: number,
  getValueInData: (data: T, index: number) => CellValue | undefined,
  lookupCaches?: LookupCaches,
  reverseSearch = false
): number {
  if (target === undefined || target.value === null) {
    return -1;
  }
  if (isEvaluationError(target.value)) {
    throw target;
  }

  const _target = normalizeValue(target.value);
  const getValue = reverseSearch
    ? (data: T, i: number) => normalizeValue(getValueInData(data, numberOfValues - i - 1))
    : (data: T, i: number) => normalizeValue(getValueInData(data, i));

  // first check if the target is in the cache

  const isNotWildcardTarget =
    mode !== "wildcard" ||
    typeof _target !== "string" ||
    !(_target.includes("*") || _target.includes("?"));

  if (lookupCaches && isNotWildcardTarget) {
    const searchMode = reverseSearch ? "reverseSearch" : "forwardSearch";
    let cache = lookupCaches[searchMode].get(data);
    if (cache === undefined) {
      // build the cache for all the values
      cache = new Map<CellValue, number>();
      for (let i = 0; i < numberOfValues; i++) {
        const value = getValue(data, i) ?? null;
        if (!cache.has(value)) {
          cache.set(value, i);
        }
      }
      lookupCaches[searchMode].set(data, cache);
    }

    if (cache.has(_target)) {
      const resultIndex = cache.get(_target)!;
      return reverseSearch ? numberOfValues - resultIndex - 1 : resultIndex;
    }

    if (mode === "strict" || mode === "wildcard") {
      return -1;
    }
  }

  // else perform the linear search

  const resultIndex = _linearSearch(data, _target, mode, numberOfValues, getValue);
  return reverseSearch && resultIndex !== -1 ? numberOfValues - resultIndex - 1 : resultIndex;
}

function _linearSearch<T>(
  data: T,
  _target: Exclude<CellValue, null>,
  mode: LinearSearchMode,
  numberOfValues: number,
  getNormalizeValue: (data: T, index: number) => CellValue | undefined
): number {
  let indexMatchTarget: (index: number) => boolean = (i) => {
    return getNormalizeValue(data, i) === _target;
  };

  if (
    mode === "wildcard" &&
    typeof _target === "string" &&
    (_target.includes("*") || _target.includes("?"))
  ) {
    const regExp = wildcardToRegExp(_target);
    indexMatchTarget = (i) => {
      const value = getNormalizeValue(data, i);
      if (typeof value === "string") {
        return regExp.test(value);
      }
      return false;
    };
  }

  let closestMatch: CellValue | undefined = undefined;
  let closestMatchIndex = -1;

  if (mode === "nextSmaller") {
    indexMatchTarget = (i) => {
      const value = getNormalizeValue(data, i);
      if (
        (!closestMatch && compareCellValues(_target, value) >= 0) ||
        (compareCellValues(_target, value) >= 0 && compareCellValues(value, closestMatch) > 0)
      ) {
        closestMatch = value;
        closestMatchIndex = i;
      }
      return value === _target;
    };
  }

  if (mode === "nextGreater") {
    indexMatchTarget = (i) => {
      const value = getNormalizeValue(data, i);
      if (
        (!closestMatch && compareCellValues(_target, value) <= 0) ||
        (compareCellValues(_target, value) <= 0 && compareCellValues(value, closestMatch) < 0)
      ) {
        closestMatch = value;
        closestMatchIndex = i;
      }
      return value === _target;
    };
  }

  for (let i = 0; i < numberOfValues; i++) {
    if (indexMatchTarget(i)) {
      return i;
    }
  }

  return closestMatchIndex;
}

/**
 * Normalize a value.
 * If the cell value is a string, this will set it to lowercase and replacing accent letters with plain letters
 */
function normalizeValue<T>(value: T): T | string {
  return typeof value === "string" ? normalizeString(value) : value;
}

function compareCellValues(left: CellValue | undefined, right: CellValue | undefined): number {
  let typeOrder = SORT_TYPES_ORDER.indexOf(typeof left) - SORT_TYPES_ORDER.indexOf(typeof right);
  if (typeOrder === 0) {
    if (typeof left === "string" && typeof right === "string") {
      typeOrder = left.localeCompare(right);
    } else if (typeof left === "number" && typeof right === "number") {
      typeOrder = left - right;
    } else if (typeof left === "boolean" && typeof right === "boolean") {
      typeOrder = Number(left) - Number(right);
    }
  }
  return typeOrder;
}

export function toMatrix<T>(data: T | Matrix<T> | undefined): Matrix<T> {
  if (data === undefined) {
    return [[]];
  }
  return isMatrix(data) ? data : [[data]];
}

/**
 * Flatten an array of items, where each item can be a single value or a 2D array, and apply the
 * callback to each element.
 *
 * The 2D array are flattened row first.
 */
export function flattenRowFirst<T, K>(items: Array<T | Matrix<T>>, callback: (val: T) => K): K[] {
  /**/
  return reduceAny(
    items,
    (array: K[], val: T) => {
      array.push(callback(val));
      return array;
    },
    [],
    "rowFirst"
  );
}

export function isDataNonEmpty(data: FunctionResultObject | undefined): boolean {
  if (data === undefined) {
    return false;
  }
  const { value } = data;
  if (value === null || value === "") {
    return false;
  }
  return true;
}

export const noValidInputErrorMessage = _t("[[FUNCTION_NAME]] has no valid input data.");

export function emptyDataErrorMessage(argName: string): string {
  return _t(
    "[[FUNCTION_NAME]] expects the provided values of %(argName)s to be a non-empty matrix.",
    { argName }
  );
}