import type { CombinatorialDimensions, CombinatorialPlan, OmittedCombination } from "./types.js";

type Dimension = {
  name: string;
  values: string[];
};

function compareUnicodeScalars(left: string, right: string): number {
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    const leftCode = left.codePointAt(leftIndex);
    const rightCode = right.codePointAt(rightIndex);
    if (leftCode === undefined || rightCode === undefined) {
      break;
    }
    if (leftCode !== rightCode) {
      return leftCode < rightCode ? -1 : 1;
    }
    leftIndex += leftCode > 0xffff ? 2 : 1;
    rightIndex += rightCode > 0xffff ? 2 : 1;
  }

  return left.length - right.length;
}

function assertNonEmptyString(value: string, field: string): void {
  if (value.trim().length === 0) {
    throw new Error(`${field} must be a non-empty string`);
  }
}

function assertPositiveInteger(value: number, field: string): void {
  if (!Number.isInteger(value) || value <= 0) {
    throw new Error(`${field} must be a positive integer`);
  }
}

function normalizeDimensions(dimensions: CombinatorialDimensions): Dimension[] {
  const names = Object.keys(dimensions).sort(compareUnicodeScalars);
  if (names.length === 0) {
    throw new Error("dimensions must contain at least one dimension");
  }

  const normalized: Dimension[] = [];
  for (const name of names) {
    assertNonEmptyString(name, "dimensions key");
    const values = dimensions[name];
    if (!Array.isArray(values) || values.length === 0) {
      throw new Error(`dimensions.${name} must contain at least one value`);
    }
    const uniqueValues: string[] = [];
    for (const value of values) {
      if (typeof value !== "string") {
        throw new Error(`dimensions.${name}[] must contain strings`);
      }
      if (!uniqueValues.includes(value)) {
        uniqueValues.push(value);
      }
    }
    uniqueValues.sort(compareUnicodeScalars);
    for (const value of uniqueValues) {
      assertNonEmptyString(value, `dimensions.${name}[]`);
    }
    normalized.push({ name, values: uniqueValues });
  }

  return normalized;
}

function serializeAssignment(assignment: Record<string, string>): string {
  return Object.keys(assignment)
    .sort(compareUnicodeScalars)
    .map((name) => `${name}=${assignment[name] ?? ""}`)
    .join("|");
}

function cartesianAssignments(dimensions: Dimension[]): Array<Record<string, string>> {
  if (dimensions.length === 0) {
    return [{}];
  }

  let assignments: Array<Record<string, string>> = [{}];
  for (const dimension of dimensions) {
    const next: Array<Record<string, string>> = [];
    for (const assignment of assignments) {
      for (const value of dimension.values) {
        next.push({ ...assignment, [dimension.name]: value });
      }
    }
    assignments = next;
  }

  return assignments.sort((left, right) =>
    compareUnicodeScalars(serializeAssignment(left), serializeAssignment(right)),
  );
}

function combinations<T>(items: readonly T[], size: number): T[][] {
  if (size <= 0) {
    return [];
  }
  if (size > items.length) {
    return [];
  }
  if (size === 1) {
    return items.map((item) => [item]);
  }

  const result: T[][] = [];
  for (let index = 0; index < items.length; index += 1) {
    const head = items[index];
    if (head === undefined) {
      continue;
    }
    for (const tail of combinations(items.slice(index + 1), size - 1)) {
      result.push([head, ...tail]);
    }
  }
  return result;
}

function tupleKey(
  selectedDimensionNames: string[],
  valuesByDimension: Record<string, string>,
): string {
  return selectedDimensionNames
    .sort(compareUnicodeScalars)
    .map((name) => `${name}=${valuesByDimension[name] ?? ""}`)
    .join("|");
}

function buildRequiredTuples(dimensions: Dimension[], t: number): Set<string> {
  const required = new Set<string>();
  const dimensionCombinations = combinations(dimensions, t);

  for (const subset of dimensionCombinations) {
    let assignments: Array<Record<string, string>> = [{}];
    for (const dimension of subset) {
      const next: Array<Record<string, string>> = [];
      for (const assignment of assignments) {
        for (const value of dimension.values) {
          next.push({ ...assignment, [dimension.name]: value });
        }
      }
      assignments = next;
    }

    const names = subset.map((dimension) => dimension.name);
    for (const assignment of assignments) {
      required.add(tupleKey(names, assignment));
    }
  }

  return required;
}

function uncoveredTuplesForAssignment(
  assignment: Record<string, string>,
  dimensions: Dimension[],
  uncovered: Set<string>,
  t: number,
): string[] {
  const covered: string[] = [];
  const dimensionCombinations = combinations(dimensions, t);

  for (const subset of dimensionCombinations) {
    const names = subset.map((dimension) => dimension.name);
    const values: Record<string, string> = {};
    for (const name of names) {
      const value = assignment[name];
      if (value === undefined) {
        continue;
      }
      values[name] = value;
    }
    const key = tupleKey(names, values);
    if (uncovered.has(key)) {
      covered.push(key);
    }
  }

  return covered;
}

function greedyCover(
  fullAssignments: Array<Record<string, string>>,
  dimensions: Dimension[],
  t: number,
): Array<Record<string, string>> {
  const required = buildRequiredTuples(dimensions, t);
  const uncovered = new Set(required);
  const selected: Array<Record<string, string>> = [];

  while (uncovered.size > 0) {
    let bestAssignment: Record<string, string> | undefined;
    let bestCoverage: string[] = [];

    for (const assignment of fullAssignments) {
      const coverage = uncoveredTuplesForAssignment(assignment, dimensions, uncovered, t);
      if (coverage.length === 0) {
        continue;
      }
      if (
        bestAssignment === undefined ||
        coverage.length > bestCoverage.length ||
        (coverage.length === bestCoverage.length &&
          compareUnicodeScalars(
            serializeAssignment(assignment),
            serializeAssignment(bestAssignment),
          ) < 0)
      ) {
        bestAssignment = assignment;
        bestCoverage = coverage;
      }
    }

    if (bestAssignment === undefined) {
      throw new Error("unable to construct t-way covering selection");
    }

    selected.push(bestAssignment);
    for (const key of bestCoverage) {
      uncovered.delete(key);
    }
  }

  const unique = new Map<string, Record<string, string>>();
  for (const assignment of selected) {
    unique.set(serializeAssignment(assignment), assignment);
  }

  return [...unique.values()].sort((left, right) =>
    compareUnicodeScalars(serializeAssignment(left), serializeAssignment(right)),
  );
}

function buildOmittedCombinations(
  fullAssignments: Array<Record<string, string>>,
  selected: Array<Record<string, string>>,
): OmittedCombination[] {
  const selectedKeys = new Set(selected.map((assignment) => serializeAssignment(assignment)));
  const omitted: OmittedCombination[] = [];

  for (const assignment of fullAssignments) {
    const key = serializeAssignment(assignment);
    if (selectedKeys.has(key)) {
      continue;
    }
    omitted.push({
      dimensions: { ...assignment },
      reason: "reduction-not-selected",
    });
  }

  return omitted;
}

export function planPairwise(
  dimensions: CombinatorialDimensions,
  t: number,
): CombinatorialPlan {
  assertPositiveInteger(t, "t");
  const normalized = normalizeDimensions(dimensions);
  if (t > normalized.length) {
    throw new Error("t must not exceed the number of dimensions");
  }

  const fullAssignments = cartesianAssignments(normalized);
  const selected =
    t >= normalized.length
      ? fullAssignments
      : greedyCover(fullAssignments, normalized, t);

  return {
    t,
    dimensions,
    selected,
    fullCombinationCount: fullAssignments.length,
    omittedCombinations: buildOmittedCombinations(fullAssignments, selected),
  };
}