RangeComparatorLCS::longestCommonSubsequence() - Code Metrics - snebes/range-differencer - Measure and Improve Code Quality continuously with Scrutinizer

RangeComparatorLCS::longestCommonSubsequence() A
last analyzed 2019-09-10 16:36 UTC

↳ Parent: RangeComparatorLCS

Complexity

Conditions	2
Paths	2

Size

Total Lines	8
Code Lines	4

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	5
CRAP Score	2

Importance

Changes

Metric	Value
cc	2
eloc	4
nc	2
nop	0
dl	0
loc	8
ccs	5
cts	5
cp	1
crap	2
rs	10
c	0
b	0
f	0

<?php
/**
 * (c) Steve Nebes <[email protected]>
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */

declare(strict_types=1);

namespace SN\RangeDifferencer;

use SN\RangeDifferencer\Core\LCS;

/**
 * RangeComparator using Longest Common Subsequence.
 *
 * @internal
 */
class RangeComparatorLCS extends LCS
{
    /** @var RangeComparatorInterface */
    private $comparator1;

    /** @var RangeComparatorInterface */
    private $comparator2;

    /** @var int[][] */
    private $lcs;

    /**
     * Default values.
     *
     * @param RangeComparatorInterface $comparator1
     * @param RangeComparatorInterface $comparator2
     */
    public function __construct(RangeComparatorInterface $comparator1, RangeComparatorInterface $comparator2)
    {
        $this->comparator1 = $comparator1;
        $this->comparator2 = $comparator2;
    }

    /**
     * @param RangeComparatorInterface $left
     * @param RangeComparatorInterface $right
     * @return RangeDifference[]
     */
    public static function findDifferences(RangeComparatorInterface $left, RangeComparatorInterface $right): array
    {
        $lcs = new static($left, $right);
        $lcs->longestCommonSubsequence();

        return $lcs->getDifferences();
    }

    /**
     * @return int
     */
    protected function getLength1(): int
    {
        return $this->comparator1->getRangeCount();
    }

    /**
     * @return int
     */
    protected function getLength2(): int
    {
        return $this->comparator2->getRangeCount();
    }

    /**
     * @param int $lcsLength
     */
    protected function initializeLcs(int $lcsLength): void
    {
        $this->lcs = \array_fill(0, 2, \array_fill(0, $lcsLength, 0));
    }

    /**
     * @param int $i1
     * @param int $i2
     * @return bool
     */
    protected function isRangeEqual(int $i1, int $i2): bool
    {
        return $this->comparator1->rangesEqual($i1, $this->comparator2, $i2);
    }

    /**
     * @param int $sl1
     * @param int $sl2
     */
    protected function setLcs(int $sl1, int $sl2): void
    {
        $this->lcs[0][$sl1] = $sl1 + 1;
        $this->lcs[1][$sl1] = $sl2 + 1;
    }

    /**
     * @return RangeDifference[]
     */
    public function getDifferences(): array
    {
        $differences = [];
        $length = $this->getLength();

        if (0 === $length) {
            $differences[] = new RangeDifference(
                RangeDifference::CHANGE,
                0, $this->comparator2->getRangeCount(),
                0, $this->comparator1->getRangeCount());
        } else {
            $index1 = 0;
            $index2 = 0;
            $s1 = -1;
            $s2 = -1;

            while ($index1 < \count($this->lcs[0]) && $index2 < \count($this->lcs[1])) {
                // Move both LCS lists to the next occupied slot.
                while (0 === $l1 = $this->lcs[0][$index1]) {
                    $index1++;

                    if ($index1 >= \count($this->lcs[0])) {
                        break;
                    }
                }

                if ($index1 >= \count($this->lcs[0])) {
                    break;
                }

                while (0 === $l2 = $this->lcs[1][$index2]) {
                    $index2++;

                    if ($index2 >= \count($this->lcs[1])) {
                        break;
                    }
                }

                if ($index2 >= \count($this->lcs[1])) {
                    break;
                }

                // Convert the entry to an array index (see setLcs(int, int)).
                $end1 = $l1 - 1;
                $end2 = $l2 - 1;

                if (-1 === $s1 && (0 !== $end1 || 0 !== $end2)) {
                    // There is a diff at the beginning.
                    // TODO: We need to confirm that this is the proper order.
                    $differences[] = new RangeDifference(RangeDifference::CHANGE, 0, $end2, 0, $end1);
                } elseif ($end1 !== $s1 + 1 || $end2 !== $s2 + 1) {
                    // A diff was found on one of the sides.
                    $leftStart = $s1 + 1;
                    $leftLength = $end1 - $leftStart;
                    $rightStart = $s2 + 1;
                    $rightLength = $end2 - $rightStart;

                    // TODO: We need to confirm that this is the proper order.
                    $differences[] = new RangeDifference(
                        RangeDifference::CHANGE, $rightStart, $rightLength, $leftStart, $leftLength);
                }

                $s1 = $end1;
                $s2 = $end2;
                $index1++;
                $index2++;
            }

            if (-1 !== $s1 && ($s1 + 1 < $this->comparator1->getRangeCount() ||
                    $s2 + 1 < $this->comparator2->getRangeCount())) {
                $leftStart = $s1 < $this->comparator1->getRangeCount() ? $s1 + 1 : $s1;
                $rightStart = $s2 < $this->comparator2->getRangeCount() ? $s2 + 1 : $s2;

                // TODO: We need to confirm that this is the proper order.
                $differences[] = new RangeDifference(
                    RangeDifference::CHANGE,
                    $rightStart, $this->comparator2->getRangeCount() - $s2 + 1,
                    $leftStart, $this->comparator1->getRangeCount() - $s1 + 1);
            }
        }

        return $differences;
    }

    /**
     * {@inheritdoc}
     */
    public function longestCommonSubsequence(): void
    {
        parent::longestCommonSubsequence();

        // The LCS can be null if one of the sides is empty.
        if (null !== $this->lcs) {
            $this->compactAndShiftLCS($this->lcs[0], $this->getLength(), $this->comparator1);
            $this->compactAndShiftLCS($this->lcs[1], $this->getLength(), $this->comparator2);
        }
    }

    /**
     * This method takes an LCS result interspersed with zeros (i.e. empty slots  from the LCS algorithm), compacts it
     * and shifts the LCS chunks as far towards the front as possible. This tends to produce good results most of the
     * time.
     *
     * @param int[]                    $lcsSide
     * @param int                      $length
     * @param RangeComparatorInterface $comparator
     */
    private function compactAndShiftLCS(array &$lcsSide, int $length, RangeComparatorInterface $comparator): void
    {
        // If the LCS is empty, just return.
        if (0 === $length) {
            return;
        }

        // Skip any leading slots.
        $j = 0;

        while (0 === $lcsSide[$j]) {
            $j++;
        }

        // Put the first non-empty value in position 0.
        $lcsSide[0] = $lcsSide[$j];
        $j++;

        // Push all non-empty values down into the first N slots (where N is the length)
        for ($i = 1; $i < $length; $i++) {
            while (0 === $lcsSide[$j]) {
                $j++;
            }

            /*
             * Push the difference down as far as possible by comparing the line at the start of the diff with the line
             * and the end and adjusting if they are the same.
             */
            $nextLine = $lcsSide[$i - 1] + 1;

            if ($nextLine !== $lcsSide[$j] && $comparator->rangesEqual($nextLine - 1, $comparator, $lcsSide[$j] - 1)) {
                $lcsSide[$i] = $nextLine;
            } else {
                $lcsSide[$i] = $lcsSide[$j];
            }

            $j++;
        }

        // Zero all slots after the length.
        for ($i = $length, $iMax = \count($lcsSide); $i < $iMax; $i++) {
            $lcsSide[$i] = 0;
        }
    }
}


1		<?php
2		/**
3		* (c) Steve Nebes <[email protected]>
4		*
5		* For the full copyright and license information, please view the LICENSE
6		* file that was distributed with this source code.
7		*/
8
9		declare(strict_types=1);
10
11		namespace SN\RangeDifferencer;
12
13		use SN\RangeDifferencer\Core\LCS;
14
15		/**
16		* RangeComparator using Longest Common Subsequence.
17		*
18		* @internal
19		*/
20		class RangeComparatorLCS extends LCS
21		{
22		/** @var RangeComparatorInterface */
23		private $comparator1;
24
25		/** @var RangeComparatorInterface */
26		private $comparator2;
27
28		/** @var int[][] */
29		private $lcs;
30
31		/**
32		* Default values.
33		*
34		* @param RangeComparatorInterface $comparator1
35		* @param RangeComparatorInterface $comparator2
36		*/
37	30	public function __construct(RangeComparatorInterface $comparator1, RangeComparatorInterface $comparator2)
38		{
39	30	$this->comparator1 = $comparator1;
40	30	$this->comparator2 = $comparator2;
41	30	}
42
43		/**
44		* @param RangeComparatorInterface $left
45		* @param RangeComparatorInterface $right
46		* @return RangeDifference[]
47		*/
48	17	public static function findDifferences(RangeComparatorInterface $left, RangeComparatorInterface $right): array
49		{
50	17	$lcs = new static($left, $right);
51	17	$lcs->longestCommonSubsequence();
52
53	17	return $lcs->getDifferences();
54		}
55
56		/**
57		* @return int
58		*/
59	21	protected function getLength1(): int
60		{
61	21	return $this->comparator1->getRangeCount();
62		}
63
64		/**
65		* @return int
66		*/
67	21	protected function getLength2(): int
68		{
69	21	return $this->comparator2->getRangeCount();
70		}
71
72		/**
73		* @param int $lcsLength
74		*/
75	19	protected function initializeLcs(int $lcsLength): void
76		{
77	19	$this->lcs = \array_fill(0, 2, \array_fill(0, $lcsLength, 0));
78	19	}
79
80		/**
81		* @param int $i1
82		* @param int $i2
83		* @return bool
84		*/
85	18	protected function isRangeEqual(int $i1, int $i2): bool
86		{
87	18	return $this->comparator1->rangesEqual($i1, $this->comparator2, $i2);
88		}
89
90		/**
91		* @param int $sl1
92		* @param int $sl2
93		*/
94	17	protected function setLcs(int $sl1, int $sl2): void
95		{
96	17	$this->lcs[0][$sl1] = $sl1 + 1;
97	17	$this->lcs[1][$sl1] = $sl2 + 1;
98	17	}
99
100		/**
101		* @return RangeDifference[]
102		*/
103	23	public function getDifferences(): array
104		{
105	23	$differences = [];
106	23	$length = $this->getLength();
107
108	23	if (0 === $length) {
109	6	$differences[] = new RangeDifference(
110	6	RangeDifference::CHANGE,
111	6	0, $this->comparator2->getRangeCount(),
112	6	0, $this->comparator1->getRangeCount());
113		} else {
114	17	$index1 = 0;
115	17	$index2 = 0;
116	17	$s1 = -1;
117	17	$s2 = -1;
118
119	17	while ($index1 < \count($this->lcs[0]) && $index2 < \count($this->lcs[1])) {
120		// Move both LCS lists to the next occupied slot.
121	17	while (0 === $l1 = $this->lcs[0][$index1]) {
122	7	$index1++;
123
124	7	if ($index1 >= \count($this->lcs[0])) {
125	7	break;
126		}
127		}
128
129	17	if ($index1 >= \count($this->lcs[0])) {
130	7	break;
131		}
132
133	17	while (0 === $l2 = $this->lcs[1][$index2]) {
134		$index2++;
135
136		if ($index2 >= \count($this->lcs[1])) {
137		break;
138		}
139		}
140
141	17	if ($index2 >= \count($this->lcs[1])) {
142		break;
143		}
144
145		// Convert the entry to an array index (see setLcs(int, int)).
146	17	$end1 = $l1 - 1;
147	17	$end2 = $l2 - 1;
148
149	17	if (-1 === $s1 && (0 !== $end1 \|\| 0 !== $end2)) {
150		// There is a diff at the beginning.
151		// TODO: We need to confirm that this is the proper order.
152	2	$differences[] = new RangeDifference(RangeDifference::CHANGE, 0, $end2, 0, $end1);
153	17	} elseif ($end1 !== $s1 + 1 \|\| $end2 !== $s2 + 1) {
154		// A diff was found on one of the sides.
155	12	$leftStart = $s1 + 1;
156	12	$leftLength = $end1 - $leftStart;
157	12	$rightStart = $s2 + 1;
158	12	$rightLength = $end2 - $rightStart;
159
160		// TODO: We need to confirm that this is the proper order.
161	12	$differences[] = new RangeDifference(
162	12	RangeDifference::CHANGE, $rightStart, $rightLength, $leftStart, $leftLength);
163		}
164
165	17	$s1 = $end1;
166	17	$s2 = $end2;
167	17	$index1++;
168	17	$index2++;
169		}
170
171	17	if (-1 !== $s1 && ($s1 + 1 < $this->comparator1->getRangeCount() \|\|
172	17	$s2 + 1 < $this->comparator2->getRangeCount())) {
173	2	$leftStart = $s1 < $this->comparator1->getRangeCount() ? $s1 + 1 : $s1;
174	2	$rightStart = $s2 < $this->comparator2->getRangeCount() ? $s2 + 1 : $s2;
175
176		// TODO: We need to confirm that this is the proper order.
177	2	$differences[] = new RangeDifference(
178	2	RangeDifference::CHANGE,
179	2	$rightStart, $this->comparator2->getRangeCount() - $s2 + 1,
180	2	$leftStart, $this->comparator1->getRangeCount() - $s1 + 1);
181		}
182		}
183
184	23	return $differences;
185		}
186
187		/**
188		* {@inheritdoc}
189		*/
190	17	public function longestCommonSubsequence(): void
191		{
192	17	parent::longestCommonSubsequence();
193
194		// The LCS can be null if one of the sides is empty.
195	17	if (null !== $this->lcs) {
196	17	$this->compactAndShiftLCS($this->lcs[0], $this->getLength(), $this->comparator1);
197	17	$this->compactAndShiftLCS($this->lcs[1], $this->getLength(), $this->comparator2);
198		}
199	17	}
200
201		/**
202		* This method takes an LCS result interspersed with zeros (i.e. empty slots from the LCS algorithm), compacts it
203		* and shifts the LCS chunks as far towards the front as possible. This tends to produce good results most of the
204		* time.
205		*
206		* @param int[] $lcsSide
207		* @param int $length
208		* @param RangeComparatorInterface $comparator
209		*/
210	17	private function compactAndShiftLCS(array &$lcsSide, int $length, RangeComparatorInterface $comparator): void
211		{
212		// If the LCS is empty, just return.
213	17	if (0 === $length) {
214		return;
215		}
216
217		// Skip any leading slots.
218	17	$j = 0;
219
220	17	while (0 === $lcsSide[$j]) {
221	1	$j++;
222		}
223
224		// Put the first non-empty value in position 0.
225	17	$lcsSide[0] = $lcsSide[$j];
226	17	$j++;
227
228		// Push all non-empty values down into the first N slots (where N is the length)
229	17	for ($i = 1; $i < $length; $i++) {
230	17	while (0 === $lcsSide[$j]) {
231	5	$j++;
232		}
233
234		/*
235		* Push the difference down as far as possible by comparing the line at the start of the diff with the line
236		* and the end and adjusting if they are the same.
237		*/
238	17	$nextLine = $lcsSide[$i - 1] + 1;
239
240	17	if ($nextLine !== $lcsSide[$j] && $comparator->rangesEqual($nextLine - 1, $comparator, $lcsSide[$j] - 1)) {
241		$lcsSide[$i] = $nextLine;
242		} else {
243	17	$lcsSide[$i] = $lcsSide[$j];
244		}
245
246	17	$j++;
247		}
248
249		// Zero all slots after the length.
250	17	for ($i = $length, $iMax = \count($lcsSide); $i < $iMax; $i++) {
251	7	$lcsSide[$i] = 0;
252		}
253	17	}
254		}
255

snebes / range-differencer

RangeComparatorLCS::longestCommonSubsequence() A last analyzed 2019-09-10 16:36 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

RangeComparatorLCS::longestCommonSubsequence() A
last analyzed 2019-09-10 16:36 UTC