import type { SAdd } from "./Add";
import type { Inc } from "./Inc";
import type { _CompareStrLength } from "./internals/_CompareStrLength";
import type { _RemoveStrPaddingZeroes } from "./internals/_RemoveStrPaddingZeroes";
import type { Digit, GT, Nat } from "../aliases";
import type { _ReverseString } from "../internals/_ReverseString";
import type { _StrToNum } from "../internals/_StrToNum";

type MulMatDigit = [
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
  [0, 2, 4, 6, 8, 0, 2, 4, 6, 8],
  [0, 3, 6, 9, 2, 5, 8, 1, 4, 7],
  [0, 4, 8, 2, 6, 0, 4, 8, 2, 6],
  [0, 5, 0, 5, 0, 5, 0, 5, 0, 5],
  [0, 6, 2, 8, 4, 0, 6, 2, 8, 4],
  [0, 7, 4, 1, 8, 5, 2, 9, 6, 3],
  [0, 8, 6, 4, 2, 0, 8, 6, 4, 2],
  [0, 9, 8, 7, 6, 5, 4, 3, 2, 1],
];
type MulMatCarry = [
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
  [0, 0, 0, 0, 1, 1, 1, 2, 2, 2],
  [0, 0, 0, 1, 1, 2, 2, 2, 3, 3],
  [0, 0, 1, 1, 2, 2, 3, 3, 4, 4],
  [0, 0, 1, 1, 2, 3, 3, 4, 4, 5],
  [0, 0, 1, 2, 2, 3, 4, 4, 5, 6],
  [0, 0, 1, 2, 3, 4, 4, 5, 6, 7],
  [0, 0, 1, 2, 3, 4, 5, 6, 7, 8],
];

/**
 * Multiply two {@link Nat}s.
 *
 * Sig: `(n: Nat, m: Nat) => Nat`
 */
export type Mul<N extends Nat, M extends Nat> =
  N extends N ?
    M extends M ?
      Nat extends N | M ?
        Nat
      : _StrToNum<SMul<`${N}`, `${M}`>>
    : never
  : never;

/**
 * Multiply two string representations of {@link Nat}s.
 * @private
 */
export type SMul<N extends string, M extends string> =
  _CompareStrLength<N, M> extends GT ? _SMul<N, _ReverseString<M>> : _SMul<M, _ReverseString<N>>;
type _SMul<N extends string, M extends string> =
  M extends `${infer F extends Digit}${infer R}` ?
    _RemoveStrPaddingZeroes<SAdd<`${_SMul<N, R>}0`, _ReverseString<__SMul<_ReverseString<N>, F>>>>
  : "";
type __SMul<
  N extends string,
  M extends Digit,
  Carry extends Digit = 0,
  Result extends string = "",
> =
  N extends `${infer F extends Digit}${infer R}` ?
    SAdd<`${MulMatDigit[F][M]}`, `${Carry}`> extends `${infer NextDigitRaw extends number}` ?
      `${NextDigitRaw}` extends `1${infer NextDigit extends Digit}` ?
        __SMul<R, M, Inc<MulMatCarry[F][M]>, `${Result}${NextDigit}`>
      : __SMul<R, M, MulMatCarry[F][M], `${Result}${NextDigitRaw}`>
    : never
  : `${Result}${Carry extends 0 ? "" : Carry}`;