private function backtrackPath()

in src/Diff.php [250:305]

• 35 lines of code
• 8 McCabe index (conditional complexity)

  private function backtrackPath(
    vec<dict<int, int>> $best_points_at_cost,
  ): vec<this::TMove> {
    /* Start at the final position, and backtrack to (0, 0).
     *
     * We know the final (x, y), and that the final cost is
     * C\count($best_points_at_cost).
     *
     */
    $moves = vec[];
    $to_x = C\count($this->a);
    $to_y = C\count($this->b);

    /* Work backwards, finding the (x, y) at ($cost - 1), that gets us to
     * our target at ($cost) */
    foreach (Dict\reverse($best_points_at_cost) as $cost => $best_points) {
      $diagonal = $to_x - $to_y;

      /* Use point 3. again - it's either on ($diagonal -1) with ($x-1, $y)
       * or on ($diagonal + 1) with ($x, $y - 1), plus any number of
       * diagonal moves. Which?
       */
      if (
        $diagonal === -$cost ||
        (
          $diagonal !== $cost &&
          $best_points[$diagonal - 1] < $best_points[$diagonal + 1]
        )
      ) {
        $diagonal = $diagonal + 1;
      } else {
        $diagonal = $diagonal - 1;
      }
      $from_x = $best_points[$diagonal];
      $from_y = $from_x - $diagonal;

      // We found the move that cost us - now try to fill in free diagonal
      // moves
      while ($to_x > $from_x && $to_y > $from_y) {
        $moves[] = tuple(tuple($to_x - 1, $to_y - 1), tuple($to_x, $to_y));
        $to_x--;
        $to_y--;
      }

      if ($cost === 0) {
        // If cost is 0, there were only diagonals, which we just dealt with
        return $moves;
      }

      $moves[] = tuple(tuple($from_x, $from_y), tuple($to_x, $to_y));

      $to_x = $from_x;
      $to_y = $from_y;
    }
    invariant_violation('unreachable');
  }