private function computeMatrix()

in src/utils/PhutilEditDistanceMatrix.php [358:496]

• 114 lines of code
• 30 McCabe index (conditional complexity)

  private function computeMatrix(array $x, array $y) {
    $xl = count($x);
    $yl = count($y);

    $m = array();

    $infinity = $this->getInfinity();

    $use_damerau = ($this->transposeCost !== null);
    if ($use_damerau) {
      // Initialize the default cost of a transpose.
      $m[-1][-1] = $infinity;

      // Initialize the character position dictionary for Damerau.
      $d = array();
      foreach ($x as $c) {
        $d[$c] = -1;
      }
      foreach ($y as $c) {
        $d[$c] = -1;
      }

      // Initialize the transpose costs for Damerau.
      for ($xx = 0; $xx <= $xl; $xx++) {
        $m[$xx][-1] = $infinity;
      }

      for ($yy = 0; $yy <= $yl; $yy++) {
        $m[-1][$yy] = $infinity;
      }
    }

    // Initialize the top row of the matrix.
    for ($xx = 0; $xx <= $xl; $xx++) {
      $m[$xx][0] = $xx * $this->deleteCost;
    }

    // Initialize the left column of the matrix.
    $cost = 0;
    for ($yy = 0; $yy <= $yl; $yy++) {
      $m[0][$yy] = $yy * $this->insertCost;
    }

    $use_types = ($this->computeString);
    if ($use_types) {
      $t = array();
      for ($xx = 0; $xx <= $xl; $xx++) {
        $t[$xx][0] = 'd';
      }
      for ($yy = 0; $yy <= $yl; $yy++) {
        $t[0][$yy] = 'i';
      }
      $t[0][0] = 's';
    }

    $alt_cost = $this->getAlterCost();
    if ($alt_cost && !$use_types) {
      throw new Exception(
        pht(
          'If you provide an alter cost with %s, you must enable '.
          'type computation with %s.',
          'setAlterCost()',
          'setComputeStrings()'));
    }

    // Build the edit distance matrix.
    for ($xx = 1; $xx <= $xl; $xx++) {
      $last_dy = -1;
      for ($yy = 1; $yy <= $yl; $yy++) {
        if ($use_damerau) {
          $dx = $d[$y[$yy - 1]];
          $dy = $last_dy;
        }

        if ($x[$xx - 1] === $y[$yy - 1]) {
          $rep_cost = $m[$xx - 1][$yy - 1] + 0;
          $rep_type = 's';
        } else {
          $rep_cost = $m[$xx - 1][$yy - 1] + $this->replaceCost;
          $rep_type = 'x';
        }

        $del_cost = $m[$xx - 1][$yy    ] + $this->deleteCost;
        $ins_cost = $m[$xx    ][$yy - 1] + $this->insertCost;
        if ($alt_cost) {
          $del_char = $t[$xx - 1][$yy    ];
          $ins_char = $t[$xx    ][$yy - 1];
          $rep_char = $t[$xx - 1][$yy - 1];

          if ($del_char !== 'd') {
            $del_cost += $alt_cost;
          }
          if ($ins_char !== 'i') {
            $ins_cost += $alt_cost;
          }
          if ($rep_char !== $rep_type) {
            $rep_cost += $alt_cost;
          }
        }

        if ($rep_cost <= $del_cost && $rep_cost <= $ins_cost) {
          $cost = $rep_cost;
          $type = $rep_type;
          if ($rep_type === 's') {
            $last_dy = $yy - 1;
          }
        } else if ($ins_cost <= $del_cost) {
          $cost = $ins_cost;
          $type = 'i';
        } else {
          $cost = $del_cost;
          $type = 'd';
        }

        if ($use_damerau) {
          $trn_count = (($xx - $dx - 2) + ($yy - $dy - 2) + 1);
          $trn_cost = $m[$dx][$dy] + ($trn_count * $this->transposeCost);
          if ($trn_cost < $cost) {
            $cost = $trn_cost;
            $type = array($dx + 1, $dy + 1, $type);
          }
        }

        $m[$xx][$yy] = $cost;
        if ($use_types) {
          $t[$xx][$yy] = $type;
        }
      }

      if ($use_damerau) {
        $d[$x[$xx - 1]] = ($xx - 1);
      }
    }

    $this->distanceMatrix = $m;
    if ($use_types) {
      $this->typeMatrix = $t;
    }
  }