ShortestCommonSuperstring::removeFullyOverlappingStrings() - Code Metrics - Inspection of "Improved removeFullyOverlappingStrings() performan..." - s9e/ShortestCommonSuperstring - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( dae48d...f3e57a )

by Josh

created 2016-12-22 11:00 UTC

removeFullyOverlappingStrings() B

↳ Parent: ShortestCommonSuperstring

Complexity

Conditions	5
Paths	4

Size

Total Lines	21
Code Lines	12

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	13
CRAP Score	5

Importance

Changes

Metric	Value
dl	0
loc	21
ccs	13
cts	13
cp	1
rs	8.7624
c	0
b	0
f	0
cc	5
eloc	12
nc	4
nop	0
crap	5

<?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()
	{
		$strlen = array_map('strlen', $this->strings);
		$i      = count($this->strings);
		while (--$i > 0)
		{
			$str = $this->strings[$i];
			$len = $strlen[$i];
			$j   = $i;
			while (--$j >= 0)
			{
				if ($strlen[$j] > $len && strpos($this->strings[$j], $str) !== 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	$strlen = array_map('strlen', $this->strings);
193	11	$i = count($this->strings);
194	11	while (--$i > 0)
195		{
196	9	$str = $this->strings[$i];
197	9	$len = $strlen[$i];
198	9	$j = $i;
199	9	while (--$j >= 0)
200		{
201	9	if ($strlen[$j] > $len && strpos($this->strings[$j], $str) !== false)
202		{
203	2	unset($this->strings[$i]);
204	2	break;
205		}
206		}
207		}
208
209	11	$this->resetKeys();
210	11	}
211
212		/**
213		* Reset the keys in the string list to remove the gaps
214		*
215		* @return void
216		*/
217	11	protected function resetKeys()
218		{
219	11	end($this->strings);
220	11	if (key($this->strings) !== count($this->strings) - 1)
221		{
222	6	$this->strings = array_values($this->strings);
223		}
224	11	}
225
226		/**
227		* Sort the stored strings
228		*
229		* @return void
230		*/
231	11	protected function sortStrings()
232		{
233	11	usort($this->strings, [__CLASS__, 'compareStrings']);
234	11	}
235
236		/**
237		* Capture and stored affixes of current length
238		*
239		* Will only store affixes from strings that are longer than current affix length
240		*
241		* @return void
242		*/
243	9	protected function storeAffixes()
244		{
245	9	$this->prefixes = [];
246	9	$this->suffixes = [];
247	9	foreach ($this->strings as $str)
248		{
249	9	if (strlen($str) <= $this->len)
250		{
251	1	break;
252		}
253	9	$this->prefixes[] = substr($str, 0, $this->len);
254	9	$this->suffixes[] = substr($str, -$this->len);
255		}
256		}
257		}

s9e / ShortestCommonSuperstring

Push — master ( dae48d...f3e57a )

removeFullyOverlappingStrings() B

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like