RangeComparatorLCS::longestCommonSubsequence() - Code Metrics - Inspection of "Merge pull request #3 from snebes/RangeDifference" - snebes/range-differencer - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 9bcdfc...42324d )

by Steve

created 2019-01-12 23:48 UTC

RangeComparatorLCS::longestCommonSubsequence() A

↳ Parent: RangeComparatorLCS

Complexity

Conditions	2
Paths	2

Size

Total Lines	8
Code Lines	4

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	2
eloc	4
nc	2
nop	0
dl	0
loc	8
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\AbstractLCS;

/**
 * RangeComparator using Longest Common Subsequence.
 *
 * @internal
 */
class RangeComparatorLCS extends AbstractLCS
{
    /** @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[0][$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;
    }

    /**
     * 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; $i < \count($lcsSide); $i++) {
for ($i=0; $i<count($array); $i++) { // calls count() on each iteration
}

// Better
for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once
}
            $lcsSide[$i] = 0;
        }
    }

    /**
     * {@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);
        }
    }
}


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

snebes / range-differencer

Push — master ( 9bcdfc...42324d )

RangeComparatorLCS::longestCommonSubsequence() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like