Changeset View
Changeset View
Standalone 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 $applySmoothing = self::SMOOTHING_NONE; | ||||
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; | ||||
const SMOOTHING_NONE = 'none'; | |||||
const SMOOTHING_INTERNAL = 'internal'; | |||||
const SMOOTHING_FULL = 'full'; | |||||
public function setMaximumLength($maximum_length) { | public function setMaximumLength($maximum_length) { | ||||
$this->maximumLength = $maximum_length; | $this->maximumLength = $maximum_length; | ||||
return $this; | return $this; | ||||
} | } | ||||
public function getMaximumLength() { | public function getMaximumLength() { | ||||
return coalesce($this->maximumLength, $this->getInfinity()); | return coalesce($this->maximumLength, $this->getInfinity()); | ||||
} | } | ||||
▲ Show 20 Lines • Show All 208 Lines • ▼ Show 20 Lines | while (true) { | ||||
if ($xx <= 0 && $yy <= 0) { | if ($xx <= 0 && $yy <= 0) { | ||||
break; | break; | ||||
} | } | ||||
} | } | ||||
$str = strrev($str); | $str = strrev($str); | ||||
// We pad the edit string before smoothing it, so ranges of similar | // For full smoothing, we pad the edit string before smoothing it, so | ||||
// characters at the beginning or end of the string can also be smoothed. | // ranges of similar characters at the beginning or end of the string can | ||||
// also be smoothed. | |||||
// For internal smoothing, we only smooth ranges within the change itself. | |||||
$smoothing = $this->getApplySmoothing(); | |||||
switch ($smoothing) { | |||||
case self::SMOOTHING_FULL: | |||||
$str = $this->padEditString($str); | $str = $this->padEditString($str); | ||||
$str = $this->applySmoothing($str, true); | |||||
if ($this->getApplySmoothing()) { | break; | ||||
$str = $this->applySmoothing($str); | case self::SMOOTHING_INTERNAL: | ||||
$str = $this->applySmoothing($str, false); | |||||
$str = $this->padEditString($str); | |||||
break; | |||||
case self::SMOOTHING_NONE: | |||||
$str = $this->padEditString($str); | |||||
break; | |||||
default: | |||||
throw new Exception( | |||||
pht( | |||||
'Unknown smoothing type "%s".', | |||||
$smoothing)); | |||||
} | } | ||||
return $str; | return $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; | ||||
▲ Show 20 Lines • Show All 198 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) { | private function applySmoothing($str, $full) { | ||||
$result = $str; | if ($full) { | ||||
$prefix = '(^|[xdi])'; | |||||
$suffix = '([xdi]|\z)'; | |||||
} else { | |||||
$prefix = '([xdi])'; | |||||
$suffix = '([xdi])'; | |||||
} | |||||
// Smooth the string out, by replacing short runs of similar characters | // Smooth the string out, by replacing short runs of similar characters | ||||
// with 'x' operations. This makes the result more readable to humans, | // with 'x' operations. This makes the result more readable to humans, | ||||
// since there are fewer choppy runs of short added and removed substrings. | // since there are fewer choppy runs of short added and removed substrings. | ||||
do { | do { | ||||
$original = $result; | $original = $str; | ||||
$result = preg_replace('/(^|[xdi])(s{3})([xdi]|\z)/', '$1xxx$3', $result); | $str = preg_replace('/'.$prefix.'(s{3})'.$suffix.'/', '$1xxx$3', $str); | ||||
$result = preg_replace('/(^|[xdi])(s{2})([xdi]|\z)/', '$1xx$3', $result); | $str = preg_replace('/'.$prefix.'(s{2})'.$suffix.'/', '$1xx$3', $str); | ||||
$result = preg_replace('/(^|[xdi])(s{1})([xdi]|\z)/', '$1x$3', $result); | $str = preg_replace('/'.$prefix.'(s{1})'.$suffix.'/', '$1x$3', $str); | ||||
} while ($result != $original); | } while ($str != $original); | ||||
return $result; | return $str; | ||||
} | } | ||||
} | } |