ShortestCommonSuperstring::compareStrings() - Code Metrics - s9e/ShortestCommonSuperstring - Measure and Improve Code Quality continuously with Scrutinizer

ShortestCommonSuperstring::compareStrings() A
last analyzed 2021-04-30 19:41 UTC

↳ Parent: ShortestCommonSuperstring

Complexity

Conditions	3
Paths	3

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	6
CRAP Score	3

Importance

Changes

Metric	Value
dl	0
loc	13
ccs	6
cts	6
cp	1
rs	9.8333
c	0
b	0
f	0
cc	3
nc	3
nop	2
crap	3

<?php declare(strict_types=1);

/**
* @package   s9e\ShortestCommonSuperstring
* @copyright Copyright (c) 2016-2021 The s9e authors
* @license   http://www.opensource.org/licenses/mit-license.php The MIT License
*/
namespace s9e\ShortestCommonSuperstring;

class ShortestCommonSuperstring
{
	/**
	* @var integer Affix length for current iteration
	*/
	protected $len;

	/**
	* @var string[] Prefixes of current length
	*/
	protected $prefixes;

	/**
	* @var string[] Strings being merged
	*/
	protected $strings;

	/**
	* @var string[] Suffixes of current length
	*/
	protected $suffixes;

	/**
	* Get the shortest string that contains all given strings
	*
	* @param  string[] $strings
	* @return string
	*/
	public function getShortest(array $strings): string
	{
		$this->strings = array_unique($strings);
		$this->sortStrings();
		$this->removeEmptyStrings();
		$this->removeFullyOverlappingStrings();
		if (isset($this->strings[1]))
		{
			// Start with the longest partial match possible, which is equal to the length of the
			// second longest string minus 1
			$this->len = strlen($this->strings[1]);
			while (--$this->len > 0)
			{
				$this->mergeStrings();
			}
		}

		return implode('', $this->strings);
	}

	/**
	* Compare given strings
	*/
	protected static function compareStrings(string $a, string $b): int
	{
		$aLen = strlen($a);
		$bLen = strlen($b);
		if ($aLen !== $bLen)
		{
			// Longest first
			return $bLen - $aLen;
		}

		// Lexical order
		return ($a > $b) ? 1 : -1;
	}

	/**
	* Match and merge a string by key
	*
	* @param  integer $leftKey Left string's key
	* @return bool             Whether a match was found and strings merged
	*/
	protected function mergeString(int $leftKey): bool
	{
		// Temporarily remove this string's prefix from the array to avoid matches
		if (isset($this->prefixes[$leftKey]))
		{
			$prefix = $this->prefixes[$leftKey];
			unset($this->prefixes[$leftKey]);
		}

		// Search for a prefix that matches this string's suffix before restoring its prefix
		$rightKey = array_search($this->suffixes[$leftKey], $this->prefixes, true);
		if (isset($prefix))
		{
			$this->prefixes[$leftKey] = $prefix;
		}

		if ($rightKey === false)
		{
			return false;
		}

		$this->mergeStringPair($leftKey, $rightKey);

		return true;
	}

	/**
	* Merge two stored strings together at current affix length
	*/
	protected function mergeStringPair(int $leftKey, int $rightKey): void
	{
		$this->strings[$leftKey] .= substr($this->strings[$rightKey], $this->len);
		if (isset($this->suffixes[$rightKey]))
		{
			$this->suffixes[$leftKey] = $this->suffixes[$rightKey];
		}
		else
		{
			unset($this->suffixes[$leftKey]);
		}
		unset($this->prefixes[$rightKey], $this->strings[$rightKey], $this->suffixes[$rightKey]);
	}

	/**
	* Merge all stored strings using current affix length
	*/
	protected function mergeStrings(): void
	{
		$this->storeMatchingAffixes();

		// Merge strings whose prefix is identical to their suffix
		$keys = array_keys(array_intersect_assoc($this->prefixes, $this->suffixes));
		$this->mergeStringsGroup($keys);

		// Merge all the strings that can be used on the left side of the concatenation
		$keys = array_keys($this->suffixes);
		$this->mergeStringsGroup($keys);

		$this->resetKeys();
	}

	/**
	* Match and merge strings from given group
	*
	* @param  integer[] $keys List of keys
	* @return void
	*/
	protected function mergeStringsGroup(array $keys): void
	{
		foreach ($keys as $leftKey)
		{
			while (isset($this->suffixes[$leftKey]) && $this->mergeString($leftKey))
			{
				// Keep going as long as the left key has a suffix that matches a prefix
			}
		}
	}

	/**
	* Remove empty strings from the list
	*/
	protected function removeEmptyStrings(): void
	{
		if (end($this->strings) === '')
		{
			array_pop($this->strings);
		}
	}

	/**
	* Remove fully-overlapping strings from the list
	*/
	protected function removeFullyOverlappingStrings(): void
	{
		// Copy the list of strings ordered by ascending length and create a master string by
		// concatenating them all
		$strings = array_reverse($this->strings, true);
		$all     = implode('', $strings);
		$pos     = 0;
		foreach ($strings as $i => $str)
		{
			// Test whether current string potentially appears in any subsequent, bigger strings
			$pos += strlen($str);
			if (strpos($all, $str, $pos) === false)
			{
				continue;
			}

			// Iterate over strings from the longest to the one before current string
			$j = -1;
			while (++$j < $i)
			{
				if (strpos($strings[$j], $str) !== false)
				{
					unset($this->strings[$i]);
					break;
				}
			}
		}

		$this->resetKeys();
	}

	/**
	* Reset the keys in the string list to remove the gaps
	*/
	protected function resetKeys(): void
	{
		end($this->strings);
		if (key($this->strings) !== count($this->strings) - 1)
		{
			$this->strings = array_values($this->strings);
		}
	}

	/**
	* Sort the stored strings
	*/
	protected function sortStrings(): void
	{
		usort($this->strings, [__CLASS__, 'compareStrings']);
	}

	/**
	* Capture and store matching affixes of current length
	*
	* Will only store affixes from strings that are longer than current affix length and that have
	* a match on the other end of a string
	*/
	protected function storeMatchingAffixes(): void
	{
		$this->prefixes = [];
		$this->suffixes = [];
		foreach ($this->strings as $str)
		{
			if (strlen($str) <= $this->len)
			{
				break;
			}
			$this->prefixes[] = substr($str, 0, $this->len);
			$this->suffixes[] = substr($str, -$this->len);
		}

		// Only keep affixes with a match on the other end of a string
		$this->prefixes = array_intersect($this->prefixes, $this->suffixes);
		$this->suffixes = array_intersect($this->suffixes, $this->prefixes);
	}
}

1		<?php declare(strict_types=1);
2
3		/**
4		* @package s9e\ShortestCommonSuperstring
5		* @copyright Copyright (c) 2016-2021 The s9e authors
6		* @license http://www.opensource.org/licenses/mit-license.php The MIT License
7		*/
8		namespace s9e\ShortestCommonSuperstring;
9
10		class ShortestCommonSuperstring
11		{
12		/**
13		* @var integer Affix length for current iteration
14		*/
15		protected $len;
16
17		/**
18		* @var string[] Prefixes of current length
19		*/
20		protected $prefixes;
21
22		/**
23		* @var string[] Strings being merged
24		*/
25		protected $strings;
26
27		/**
28		* @var string[] Suffixes of current length
29		*/
30		protected $suffixes;
31
32		/**
33		* Get the shortest string that contains all given strings
34		*
35		* @param string[] $strings
36		* @return string
37		*/
38	12	public function getShortest(array $strings): string
39		{
40	12	$this->strings = array_unique($strings);
41	12	$this->sortStrings();
42	12	$this->removeEmptyStrings();
43	12	$this->removeFullyOverlappingStrings();
44	12	if (isset($this->strings[1]))
45		{
46		// Start with the longest partial match possible, which is equal to the length of the
47		// second longest string minus 1
48	10	$this->len = strlen($this->strings[1]);
49	10	while (--$this->len > 0)
50		{
51	10	$this->mergeStrings();
52		}
53		}
54
55	12	return implode('', $this->strings);
56		}
57
58		/**
59		* Compare given strings
60		*/
61	10	protected static function compareStrings(string $a, string $b): int
62		{
63	10	$aLen = strlen($a);
64	10	$bLen = strlen($b);
65	10	if ($aLen !== $bLen)
66		{
67		// Longest first
68	4	return $bLen - $aLen;
69		}
70
71		// Lexical order
72	10	return ($a > $b) ? 1 : -1;
73		}
74
75		/**
76		* Match and merge a string by key
77		*
78		* @param integer $leftKey Left string's key
79		* @return bool Whether a match was found and strings merged
80		*/
81	7	protected function mergeString(int $leftKey): bool
82		{
83		// Temporarily remove this string's prefix from the array to avoid matches
84	7	if (isset($this->prefixes[$leftKey]))
85		{
86	6	$prefix = $this->prefixes[$leftKey];
87	6	unset($this->prefixes[$leftKey]);
88		}
89
90		// Search for a prefix that matches this string's suffix before restoring its prefix
91	7	$rightKey = array_search($this->suffixes[$leftKey], $this->prefixes, true);
92	7	if (isset($prefix))
93		{
94	6	$this->prefixes[$leftKey] = $prefix;
95		}
96
97	7	if ($rightKey === false)
98		{
99	2	return false;
100		}
101
102	7	$this->mergeStringPair($leftKey, $rightKey);
103
104	7	return true;
105		}
106
107		/**
108		* Merge two stored strings together at current affix length
109		*/
110	7	protected function mergeStringPair(int $leftKey, int $rightKey): void
111		{
112	7	$this->strings[$leftKey] .= substr($this->strings[$rightKey], $this->len);
113	7	if (isset($this->suffixes[$rightKey]))
114		{
115	1	$this->suffixes[$leftKey] = $this->suffixes[$rightKey];
116		}
117		else
118		{
119	6	unset($this->suffixes[$leftKey]);
120		}
121	7	unset($this->prefixes[$rightKey], $this->strings[$rightKey], $this->suffixes[$rightKey]);
122		}
123
124		/**
125		* Merge all stored strings using current affix length
126		*/
127	10	protected function mergeStrings(): void
128		{
129	10	$this->storeMatchingAffixes();
130
131		// Merge strings whose prefix is identical to their suffix
132	10	$keys = array_keys(array_intersect_assoc($this->prefixes, $this->suffixes));
133	10	$this->mergeStringsGroup($keys);
134
135		// Merge all the strings that can be used on the left side of the concatenation
136	10	$keys = array_keys($this->suffixes);
137	10	$this->mergeStringsGroup($keys);
138
139	10	$this->resetKeys();
140		}
141
142		/**
143		* Match and merge strings from given group
144		*
145		* @param integer[] $keys List of keys
146		* @return void
147		*/
148	10	protected function mergeStringsGroup(array $keys): void
149		{
150	10	foreach ($keys as $leftKey)
151		{
152	7	while (isset($this->suffixes[$leftKey]) && $this->mergeString($leftKey))
153		{
154		// Keep going as long as the left key has a suffix that matches a prefix
155		}
156		}
157		}
158
159		/**
160		* Remove empty strings from the list
161		*/
162	12	protected function removeEmptyStrings(): void
163		{
164	12	if (end($this->strings) === '')
165		{
166	1	array_pop($this->strings);
167		}
168		}
169
170		/**
171		* Remove fully-overlapping strings from the list
172		*/
173	12	protected function removeFullyOverlappingStrings(): void
174		{
175		// Copy the list of strings ordered by ascending length and create a master string by
176		// concatenating them all
177	12	$strings = array_reverse($this->strings, true);
178	12	$all = implode('', $strings);
179	12	$pos = 0;
180	12	foreach ($strings as $i => $str)
181		{
182		// Test whether current string potentially appears in any subsequent, bigger strings
183	10	$pos += strlen($str);
184	10	if (strpos($all, $str, $pos) === false)
185		{
186	10	continue;
187		}
188
189		// Iterate over strings from the longest to the one before current string
190	2	$j = -1;
191	2	while (++$j < $i)
192		{
193	2	if (strpos($strings[$j], $str) !== false)
194		{
195	2	unset($this->strings[$i]);
196	2	break;
197		}
198		}
199		}
200
201	12	$this->resetKeys();
202		}
203
204		/**
205		* Reset the keys in the string list to remove the gaps
206		*/
207	12	protected function resetKeys(): void
208		{
209	12	end($this->strings);
210	12	if (key($this->strings) !== count($this->strings) - 1)
211		{
212	6	$this->strings = array_values($this->strings);
213		}
214		}
215
216		/**
217		* Sort the stored strings
218		*/
219	12	protected function sortStrings(): void
220		{
221	12	usort($this->strings, [__CLASS__, 'compareStrings']);
222		}
223
224		/**
225		* Capture and store matching affixes of current length
226		*
227		* Will only store affixes from strings that are longer than current affix length and that have
228		* a match on the other end of a string
229		*/
230	10	protected function storeMatchingAffixes(): void
231		{
232	10	$this->prefixes = [];
233	10	$this->suffixes = [];
234	10	foreach ($this->strings as $str)
235		{
236	10	if (strlen($str) <= $this->len)
237		{
238	1	break;
239		}
240	10	$this->prefixes[] = substr($str, 0, $this->len);
241	10	$this->suffixes[] = substr($str, -$this->len);
242		}
243
244		// Only keep affixes with a match on the other end of a string
245	10	$this->prefixes = array_intersect($this->prefixes, $this->suffixes);
246	10	$this->suffixes = array_intersect($this->suffixes, $this->prefixes);
247		}
248		}

s9e / ShortestCommonSuperstring

ShortestCommonSuperstring::compareStrings() A last analyzed 2021-04-30 19:41 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

ShortestCommonSuperstring::compareStrings() A
last analyzed 2021-04-30 19:41 UTC