Differential D16068 Diff 38660 src/utils/PhutilEditDistanceMatrix.php

Changeset View

Standalone View

src/utils/PhutilEditDistanceMatrix.php

Show First 20 Lines • Show All 48 Lines • ▼ Show 20 Lines	final class PhutilEditDistanceMatrix extends Phobject {

private $insertCost = 1;		private $insertCost = 1;
private $deleteCost = 1;		private $deleteCost = 1;
private $replaceCost = 1;		private $replaceCost = 1;
private $transposeCost = null;		private $transposeCost = null;
private $alterCost = 0;		private $alterCost = 0;
private $maximumLength;		private $maximumLength;
private $computeString;		private $computeString;
		private $applySmoothing;

private $x;		private $x;
private $y;		private $y;
private $prefix;		private $prefix;
private $suffix;		private $suffix;

private $distanceMatrix = null;		private $distanceMatrix = null;
private $typeMatrix = null;		private $typeMatrix = null;
▲ Show 20 Lines • Show All 56 Lines • ▼ Show 20 Lines	public function setAlterCost($alter_cost) {
$this->alterCost = $alter_cost;		$this->alterCost = $alter_cost;
return $this;		return $this;
}		}

public function getAlterCost() {		public function getAlterCost() {
return $this->alterCost;		return $this->alterCost;
}		}

		public function setApplySmoothing($apply_smoothing) {
		$this->applySmoothing = $apply_smoothing;
		return $this;
		}

		public function getApplySmoothing() {
		return $this->applySmoothing;
		}

public function setSequences(array $x, array $y) {		public function setSequences(array $x, array $y) {

// NOTE: We strip common prefixes and suffixes from the inputs because		// NOTE: We strip common prefixes and suffixes from the inputs because
// the runtime of the edit distance algorithm is large and it is common		// the runtime of the edit distance algorithm is large and it is common
// to diff similar strings.		// to diff similar strings.

$xl = count($x);		$xl = count($x);
$yl = count($y);		$yl = count($y);
▲ Show 20 Lines • Show All 134 Lines • ▼ Show 20 Lines	while (true) {

$str .= $chr;		$str .= $chr;

if ($xx <= 0 && $yy <= 0) {		if ($xx <= 0 && $yy <= 0) {
break;		break;
}		}
}		}

return $this->padEditString(strrev($str));		$str = strrev($str);

		if ($this->getApplySmoothing()) {
		$str = $this->applySmoothing($str);
		}

		return $this->padEditString($str);
}		}

private function padEditString($str) {		private function padEditString($str) {
if ($this->prefix) {		if ($this->prefix) {
$str = str_repeat('s', count($this->prefix)).$str;		$str = str_repeat('s', count($this->prefix)).$str;
}		}
if ($this->suffix) {		if ($this->suffix) {
$str = $str.str_repeat('s', count($this->suffix));		$str = $str.str_repeat('s', count($this->suffix));
▲ Show 20 Lines • Show All 195 Lines • ▼ Show 20 Lines	foreach ($t as $xk => $xv) {
printf($p, idx($x, $xk - 1, '-'));		printf($p, idx($x, $xk - 1, '-'));
foreach ($xv as $yk => $yv) {		foreach ($xv as $yk => $yv) {
printf($p, ($yv == $this->getInfinity() ? 'inf' : $yv));		printf($p, ($yv == $this->getInfinity() ? 'inf' : $yv));
}		}
echo "\n";		echo "\n";
}		}
}		}

		private function applySmoothing($str) {
		$result = $str;

		// Smooth the string out, by replacing short runs of similar characters
		// with 'x' operations. This makes the result more readable to humans,
		// since there are fewer choppy runs of short added and removed substrings.
		do {
		$original = $result;
		$result = preg_replace('/([xdi])(s{3})([xdi])/', '$1xxx$3', $result);
		$result = preg_replace('/([xdi])(s{2})([xdi])/', '$1xx$3', $result);
		$result = preg_replace('/([xdi])(s{1})([xdi])/', '$1x$3', $result);
		} while ($result != $original);

		return $result;
		}

}		}