ShortestCommonSuperstring::resetKeys() - Code Metrics - Inspection of "Optimized removeEmptyStrings()" - s9e/ShortestCommonSuperstring - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 96180f...6095ba )

by Josh

created 2016-12-22 10:29 UTC

ShortestCommonSuperstring::resetKeys() A

↳ Parent: ShortestCommonSuperstring

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
dl	0
loc	8
ccs	5
cts	5
cp	1
rs	9.4285
c	0
b	0
f	0
cc	2
eloc	4
nc	2
nop	0
crap	2

<?php

/**
* @package   s9e\ShortestCommonSuperstring
* @copyright Copyright (c) 2016 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)
	{
		$this->strings = array_unique($strings);
		$this->sortStrings();
		$this->removeEmptyStrings();
		$this->removeFullyOverlappingStrings();
		if (count($this->strings) > 1)
		{
			$this->len = strlen($this->strings[0]);
			while (--$this->len > 0)
			{
				$this->mergeStrings();
			}
		}

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

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

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

	/**
	* Return the list of keys pointing to strings whose prefix is identical to their suffix
	*
	* @return integer[]
	*/
	protected function getIdenticalAffixKeys()
	{
		$identicalAffixKeys = [];
		foreach ($this->prefixes as $k => $prefix)
		{
			if ($this->suffixes[$k] === $prefix)
			{
				$identicalAffixKeys[] = $k;
			}
		}

		return $identicalAffixKeys;
	}

	/**
	* 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($leftKey)
	{
		$suffix = $this->suffixes[$leftKey];
		foreach ($this->prefixes as $rightKey => $prefix)
		{
			if ($prefix === $suffix && $leftKey !== $rightKey)
			{
				$this->mergeStringPair($leftKey, $rightKey);

				return true;
			}
		}

		return false;
	}

	/**
	* Merge two stored strings together at current affix length
	*
	* @param  integer $leftKey  Left string's key
	* @param  integer $rightKey Right string's key
	* @return void
	*/
	protected function mergeStringPair($leftKey, $rightKey)
	{
		$this->strings[$leftKey] .= substr($this->strings[$rightKey], $this->len);
		$this->suffixes[$leftKey] = $this->suffixes[$rightKey];
		unset($this->prefixes[$rightKey], $this->strings[$rightKey]);
	}

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

		// Merge strings whose prefix is identical to their suffix
		$keys = $this->getIdenticalAffixKeys();
		$this->mergeStringsGroup($keys);

		// Merge the remaining strings that have a prefix stored
		$keys = array_diff(array_keys($this->prefixes), $keys);
		$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)
	{
		foreach ($keys as $leftKey)
		{
			if (isset($this->strings[$leftKey]))
			{
				while ($this->mergeString($leftKey))

				{
					// Keep going
				}
			}
		}
	}

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

	/**
	* Remove fully-overlapping strings from the list
	*
	* @return void
	*/
	protected function removeFullyOverlappingStrings()
	{
		$i = count($this->strings);
		while (--$i > 0)
		{
			$j = $i;
			while (--$j >= 0)
			{
				if (strpos($this->strings[$j], $this->strings[$i]) !== false)
				{
					unset($this->strings[$i]);
					break;
				}
			}
		}

		$this->resetKeys();
	}

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

		}
	}

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

	/**
	* Capture and stored affixes of current length
	*
	* Will only store affixes from strings that are longer than current affix length
	*
	* @return void
	*/
	protected function storeAffixes()
	{
		$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);
		}
	}
}

1		<?php
2
3		/**
4		* @package s9e\ShortestCommonSuperstring
5		* @copyright Copyright (c) 2016 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	11	public function getShortest(array $strings)
39		{
40	11	$this->strings = array_unique($strings);
41	11	$this->sortStrings();
42	11	$this->removeEmptyStrings();
43	11	$this->removeFullyOverlappingStrings();
44	11	if (count($this->strings) > 1)
45		{
46	9	$this->len = strlen($this->strings[0]);
47	9	while (--$this->len > 0)
48		{
49	9	$this->mergeStrings();
50		}
51		}
52
53	11	return implode('', $this->strings);
54		}
55
56		/**
57		* Compare strings
58		*
59		* @param string $a
60		* @param string $b
61		* @return integer
62		*/
63	9	protected static function compareStrings($a, $b)
64		{
65	9	$aLen = strlen($a);
66	9	$bLen = strlen($b);
67	9	if ($aLen !== $bLen)
68		{
69		// Longest first
70	3	return $bLen - $aLen;
71		}
72
73		// Lexical order
74	9	return ($a > $b) ? 1 : -1;
75		}
76
77		/**
78		* Return the list of keys pointing to strings whose prefix is identical to their suffix
79		*
80		* @return integer[]
81		*/
82	9	protected function getIdenticalAffixKeys()
83		{
84	9	$identicalAffixKeys = [];
85	9	foreach ($this->prefixes as $k => $prefix)
86		{
87	9	if ($this->suffixes[$k] === $prefix)
88		{
89	9	$identicalAffixKeys[] = $k;
90		}
91		}
92
93	9	return $identicalAffixKeys;
94		}
95
96		/**
97		* Match and merge a string by key
98		*
99		* @param integer $leftKey Left string's key
100		* @return bool Whether a match was found and strings merged
101		*/
102	9	protected function mergeString($leftKey)
103		{
104	9	$suffix = $this->suffixes[$leftKey];
105	9	foreach ($this->prefixes as $rightKey => $prefix)
106		{
107	9	if ($prefix === $suffix && $leftKey !== $rightKey)
108		{
109	7	$this->mergeStringPair($leftKey, $rightKey);
110
111	9	return true;
112		}
113		}
114
115	9	return false;
116		}
117
118		/**
119		* Merge two stored strings together at current affix length
120		*
121		* @param integer $leftKey Left string's key
122		* @param integer $rightKey Right string's key
123		* @return void
124		*/
125	7	protected function mergeStringPair($leftKey, $rightKey)
126		{
127	7	$this->strings[$leftKey] .= substr($this->strings[$rightKey], $this->len);
128	7	$this->suffixes[$leftKey] = $this->suffixes[$rightKey];
129	7	unset($this->prefixes[$rightKey], $this->strings[$rightKey]);
130	7	}
131
132		/**
133		* Merge all stored strings using current affix length
134		*
135		* @return void
136		*/
137	9	protected function mergeStrings()
138		{
139	9	$this->storeAffixes();
140
141		// Merge strings whose prefix is identical to their suffix
142	9	$keys = $this->getIdenticalAffixKeys();
143	9	$this->mergeStringsGroup($keys);
144
145		// Merge the remaining strings that have a prefix stored
146	9	$keys = array_diff(array_keys($this->prefixes), $keys);
147	9	$this->mergeStringsGroup($keys);
148
149	9	$this->resetKeys();
150	9	}
151
152		/**
153		* Match and merge strings from given group
154		*
155		* @param integer[] $keys List of keys
156		* @return void
157		*/
158	9	protected function mergeStringsGroup(array $keys)
159		{
160	9	foreach ($keys as $leftKey)
161		{
162	9	if (isset($this->strings[$leftKey]))
163		{
164	9	while ($this->mergeString($leftKey))
		1 ignored issue – show Unused Code introduced 2016-12-19 11:34 UTC by Report Bug Copy Issue Report This `while` loop is empty and can be removed. This check looks for `while` loops that have no statements or where all statements have been commented out. This may be the result of changes for debugging or the code may simply be obsolete. Consider removing the loop. Loading history...
165		{
166		// Keep going
167		}
168		}
169		}
170	9	}
171
172		/**
173		* Remove empty strings from the list
174		*
175		* @return void
176		*/
177	11	protected function removeEmptyStrings()
178		{
179	11	if (end($this->strings) === '')
180		{
181	1	array_pop($this->strings);
182		}
183	11	}
184
185		/**
186		* Remove fully-overlapping strings from the list
187		*
188		* @return void
189		*/
190	11	protected function removeFullyOverlappingStrings()
191		{
192	11	$i = count($this->strings);
193	11	while (--$i > 0)
194		{
195	9	$j = $i;
196	9	while (--$j >= 0)
197		{
198	9	if (strpos($this->strings[$j], $this->strings[$i]) !== false)
199		{
200	2	unset($this->strings[$i]);
201	2	break;
202		}
203		}
204		}
205
206	11	$this->resetKeys();
207	11	}
208
209		/**
210		* Reset the keys in the string list to remove the gaps
211		*
212		* @return void
213		*/
214	11	protected function resetKeys()
215		{
216	11	end($this->strings);
217	11	if (key($this->strings) !== count($this->strings) - 1)
218		{
219	6	$this->strings = array_values($this->strings);
		1 ignored issue – show Documentation Bug introduced 2016-12-22 10:31 UTC by Report Bug Copy Issue Report It seems like `array_values($this->strings)` of type `array<integer,?>` is incompatible with the declared type `array<integer,string>` of property `$strings`. Our type inference engine has found an assignment to a property that is incompatible with the declared type of that property. Either this assignment is in error or the assigned type should be added to the documentation/type hint for that property.. Loading history...
220		}
221	11	}
222
223		/**
224		* Sort the stored strings
225		*
226		* @return void
227		*/
228	11	protected function sortStrings()
229		{
230	11	usort($this->strings, [__CLASS__, 'compareStrings']);
231	11	}
232
233		/**
234		* Capture and stored affixes of current length
235		*
236		* Will only store affixes from strings that are longer than current affix length
237		*
238		* @return void
239		*/
240	9	protected function storeAffixes()
241		{
242	9	$this->prefixes = [];
243	9	$this->suffixes = [];
244	9	foreach ($this->strings as $str)
245		{
246	9	if (strlen($str) <= $this->len)
247		{
248	1	break;
249		}
250	9	$this->prefixes[] = substr($str, 0, $this->len);
251	9	$this->suffixes[] = substr($str, -$this->len);
252		}
253		}
254		}

s9e / ShortestCommonSuperstring

Push — master ( 96180f...6095ba )

ShortestCommonSuperstring::resetKeys() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like