export function autoAddCollapsingSubPaths(from: Path, to: Path): [Path, Path] {
  const deleteCollapsingSubPathsFn = (p: Path) => {
    return p.getSubPaths().some(s => s.isCollapsing())
      ? p
          .mutate()
          .deleteCollapsingSubPaths()
          .build()
      : p;
  };
  from = deleteCollapsingSubPathsFn(from);
  to = deleteCollapsingSubPathsFn(to);

  const numFrom = from.getSubPaths().length;
  const numTo = to.getSubPaths().length;
  if (numFrom === numTo) {
    return [from, to];
  }
  // TODO: allow the user to specify the location of collapsing paths?
  const pm = (numFrom < numTo ? from : to).mutate();
  for (let subIdx = Math.min(numFrom, numTo); subIdx < Math.max(numFrom, numTo); subIdx++) {
    const opp = numFrom < numTo ? to : from;
    const pole = opp.getPoleOfInaccessibility(subIdx);
    pm.addCollapsingSubPath(pole, opp.getSubPath(subIdx).getCommands().length);
  }
  if (numFrom < numTo) {
    from = pm.build();
  } else {
    to = pm.build();
  }
  return [from, to];
}

 const deleteCollapsingSubPathsFn = (p: Path) => {
   return p.getSubPaths().some(s => s.isCollapsing())
     ? p
         .mutate()
         .deleteCollapsingSubPaths()
         .build()
     : p;
 };

export function autoConvert(from: Path, to: Path): [Path, Path] {
  [from, to] = autoUnconvertSubPaths(from, to);
  const numFrom = from.getSubPaths().length;
  const numTo = to.getSubPaths().length;
  for (let subIdx = 0; subIdx < Math.min(numFrom, numTo); subIdx++) {
    // Only auto convert when the number of commands in both canvases
    // are equal. Otherwise we'll wait for the user to add more points.
    [from, to] = autoConvertSubPath(from, to, subIdx);
  }
  return [from, to];
}

 const alignmentInfos = fromPaths.map(generatedFromPath => {
   const fromCmds = generatedFromPath.getSubPath(subIdx).getCommands();
   const toCmds = to.getSubPath(subIdx).getCommands();
   return {
     generatedFromPath,
     alignment: align(fromCmds, toCmds, getScoreFn),
   };
 });

 // @Override
 interpolateValue(start: Path, end: Path, fraction: number) {
   if (!start || !end || !start.isMorphableWith(end) || !fraction) {
     return start;
   }
   if (fraction === 1) {
     return end;
   }
   return PathUtil.interpolate(start, end, fraction);
 }

export function autoFix(from: Path, to: Path): [Path, Path] {
  [from, to] = autoUnconvertSubPaths(from, to);
  [from, to] = autoAddCollapsingSubPaths(from, to);
  [from, to] = orderSubPaths(from, to);

  const min = Math.min(from.getSubPaths().length, to.getSubPaths().length);
  for (let subIdx = 0; subIdx < min; subIdx++) {
    // Pass the command with the larger subpath as the 'from' command.
    const numFromCmds = from.getSubPath(subIdx).getCommands().length;
    const numToCmds = to.getSubPath(subIdx).getCommands().length;
    const shouldSwap = numFromCmds < numToCmds;
    if (shouldSwap) {
      [from, to] = [to, from];
    }
    [from, to] = alignSubPath(from, to, subIdx);
    if (shouldSwap) {
      [from, to] = [to, from];
    }
  }
  for (let subIdx = 0; subIdx < min; subIdx++) {
    [from, to] = permuteSubPath(from, to, subIdx);
  }
  return [from, to];
}

function permuteSubPath(from: Path, to: Path, subIdx: number): [Path, Path] {
  if (from.isClockwise(subIdx) !== to.isClockwise(subIdx)) {
    // Make sure the paths share the same direction.
    to = to
      .mutate()
      .reverseSubPath(subIdx)
      .build();
  }

  // Create and return a list of reversed and shifted from paths to test.
  // Each generated 'from path' will be aligned with the target 'to path'.
  const fromPaths: Path[] = [from];
  if (from.getSubPath(subIdx).isClosed()) {
    for (let i = 1; i < from.getSubPath(subIdx).getCommands().length - 1; i++) {
      // TODO: we need to find a way to reduce the number of paths to try.
      fromPaths.push(
        from
          .mutate()
          .shiftSubPathBack(subIdx, i)
          .build(),
      );
    }
  }

  let bestFromPath = from;
  let min = Infinity;
  for (const fromPath of fromPaths) {
    const fromCmds = fromPath.getSubPath(subIdx).getCommands();
    let sumOfSquares = 0;
    const toCmds = to.getSubPath(subIdx).getCommands();
    fromCmds.forEach(
      (c, cmdIdx) => (sumOfSquares += MathUtil.distance(c.end, toCmds[cmdIdx].end) ** 2),
    );
    if (sumOfSquares < min) {
      min = sumOfSquares;
      bestFromPath = fromPath;
    }
  }

  return [bestFromPath, to];
}

function autoConvertSubPath(from: Path, to: Path, subIdx: number): [Path, Path] {
  const numFrom = from.getSubPath(subIdx).getCommands().length;
  const numTo = to.getSubPath(subIdx).getCommands().length;
  if (numFrom !== numTo) {
    // Only auto convert when the number of commands in both subpaths are equal.
    return [from, to];
  }
  const fromPm = from.mutate();
  const toPm = to.mutate();
  for (let cmdIdx = 0; cmdIdx < numFrom; cmdIdx++) {
    const fromCmd = from.getCommand(subIdx, cmdIdx);
    const toCmd = to.getCommand(subIdx, cmdIdx);
    if (fromCmd.type === toCmd.type) {
      continue;
    }
    if (fromCmd.canConvertTo(toCmd.type)) {
      fromPm.convertCommand(subIdx, cmdIdx, toCmd.type);
    } else if (toCmd.canConvertTo(fromCmd.type)) {
      toPm.convertCommand(subIdx, cmdIdx, fromCmd.type);
    }
  }
  return [fromPm.build(), toPm.build()];
}

/**
 * Reorders the subpaths in each path to minimize the distance each shape will
 * travel during the morph.
 */
function orderSubPaths(from: Path, to: Path): [Path, Path] {
  if (from.getSubPaths().length > 8 || to.getSubPaths().length > 8) {
    // Don't attempt to order paths with many subpaths.
    return [from, to];
  }

  const shouldSwap = from.getSubPaths().length < to.getSubPaths().length;
  if (shouldSwap) {
    [from, to] = [to, from];
  }

  const fromSubPaths = from.getSubPaths();
  const toSubPaths = to.getSubPaths();

  const distances = fromSubPaths.map((f, i) => {
    return toSubPaths.map((t, j) => {
      const pole1 = from.getPoleOfInaccessibility(i);
      const pole2 = to.getPoleOfInaccessibility(j);
      return MathUtil.distance(pole1, pole2);
    });
  });

  let min = Infinity;
  let best: number[] = [];

  (function recurseFn(arr: number[], order: number[] = []) {
    if (order.length === toSubPaths.length) {
      let sum = 0;
      for (let i = 0; i < order.length; i++) {
        sum += distances[order[i]][i];
      }
      if (sum < min) {
        min = sum;
        best = order;
      }
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      const [cur] = arr.splice(i, 1);
      recurseFn([...arr], [...order, cur]);
      if (arr.length) {
        arr.splice(i, 0, cur);
      }
    }
  })(_.range(fromSubPaths.length));

  const pm = from.mutate();
  for (let i = 0; i < best.length; i++) {
    const m = best[i];
    pm.moveSubPath(m, i);
    for (let j = i + 1; j < best.length; j++) {
      const n = best[j];
      if (n < m) {
        best[j]++;
      }
    }
  }
  from = pm.build();

  if (shouldSwap) {
    [from, to] = [to, from];
  }

  return [from, to];
}