CharTree::combineDuplicateRoots() - Code Metrics - Stadly/PasswordPolice - Measure and Improve Code Quality continuously with Scrutinizer

CharTree::combineDuplicateRoots() A
last analyzed 2020-05-08 06:26 UTC

↳ Parent: CharTree

Complexity

Conditions	6
Paths	6

Size

Total Lines	23
Code Lines	15

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	16
CRAP Score	6

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	6
eloc	15
c	1
b	0
f	0
nc	6
nop	1
dl	0
loc	23
ccs	16
cts	16
cp	1
crap	6
rs	9.2222

<?php

declare(strict_types=1);

namespace Stadly\PasswordPolice;

use IteratorAggregate;
use Traversable;

final class CharTree implements IteratorAggregate
{
    /**
     * @var string|null Root of the character tree. No more than 1 character long.
     */
    private $root;

    /**
     * @var array<self> Branches of the character tree.
     */
    private $branches = [];

    /**
     * @var array<bool> Memoization of startsWith().
     */
    private $startsWithMemoization = [];

    /**
     * @var array<bool> Memoization of contains().
     */
    private $containsMemoization = [];

    /**
     * @var array<CharTree> Memoization of constructed character trees.
     */
    private static $constructMemoization = [];

    /**
     * @param string|null $root Root of the character tree. No more than 1 character long.
     * @param array<self> $branches Branches of the character tree.
     */
    private function __construct(?string $root, array $branches)
    {
        assert($root !== null || $branches === [], 'Empty tree cannot have branches.');
        assert($root === null || mb_strlen($root) <= 1, 'Root must contain at most one character.');

        $this->root = $root;
        $this->branches = $branches;
    }

    /**
     * @param string|null $root Root of the character tree. No more than 1 character long.
     * @param array<self> $branches Branches of the character tree.
     */
    private static function construct(?string $root, array $branches): self
    {
        if ($root === null) {
            assert($branches === [], 'Empty tree cannot have branches.');
            if (!isset(self::$constructMemoization['null'])) {
                self::$constructMemoization['null'] = new self($root, $branches);
            }
            return self::$constructMemoization['null'];
        }

        assert(mb_strlen($root) <= 1, 'Root must contain at most one character.');

        $hash = $root;
        ksort($branches, SORT_STRING);
        foreach ($branches as $branch) {
            // When PHP 7.1 is no longer supported, change to using spl_object_id.
            $branchHash = spl_object_hash($branch);
            $hash .= ';' . $branchHash;
        }

        if (!isset(self::$constructMemoization[$hash])) {
            self::$constructMemoization[$hash] = new self($root, $branches);
        }

        return self::$constructMemoization[$hash];
    }

    /**
     * @param string $string Root of the character tree.
     * @param array<self> $branches Branches of the character tree.
     */
    public static function fromString(string $string, array $branches = []): self
    {
        if (mb_strlen($string) > 1) {
            // Maximum one character in root.
            $branches = [self::fromString(mb_substr($string, 1), $branches)];
            $string = mb_substr($string, 0, 1);
        }

        $branches = self::promoteEmptyRoots($branches);
        $branches = self::combineDuplicateRoots($branches);

        if (count($branches) === 1) {
            $branch = reset($branches);
            if ($branch->root === null) {
                // If only one branch and its root is null, throw it away.
                $branches = [];
            } elseif ($string === '') {
                // If root is empty string and only one branch, use it.
                return $branch;
            }
        }

        return self::construct($string, $branches);
    }

    /**
     * @param array<self> $charTrees Character trees to combine.
     */
    public static function fromArray(array $charTrees): self
    {
        foreach ($charTrees as $charTree) {
            if ($charTree->root !== null) {
                return self::fromString('', $charTrees);
            }
        }

        return self::fromNothing();
    }

    /**
     * Construct empty character tree.
     */
    public static function fromNothing(): self
    {
        return self::construct(null, []);
    }

    /**
     * @param array<self> $charTrees Character trees to normalize.
     * @return array<self> Character trees where branches of trees with empty string roots have been promoted to trees.
     */
    private static function promoteEmptyRoots(array $charTrees): array
    {
        $normalized = [];
        foreach ($charTrees as $charTree) {
            if ($charTree->root === '') {
                if ($charTree->branches !== []) {
                    $normalized = array_merge($normalized, array_values($charTree->branches));
                } else {
                    $normalized[] = self::fromNothing();
                }
            } else {
                $normalized[] = $charTree;
            }
        }

        return $normalized;
    }

    /**
     * @param array<self> $charTrees Character trees to normalize.
     * @return array<self> Character trees where branches of trees with the same root have been combined.
     */
    private static function combineDuplicateRoots(array $charTrees): array
    {
        $normalized = [];
        foreach ($charTrees as $charTree) {
            if (isset($normalized[$charTree->root]) && $charTree->root !== null) {
                $normalizedCharTree = $normalized[$charTree->root];
                $normalizedBranches = array_values($normalizedCharTree->branches);
                if ($normalizedBranches === []) {
                    $normalizedBranches[] = self::fromNothing();
                }
                $branches = array_values($charTree->branches);
                if ($branches === []) {
                    $branches[] = self::fromNothing();
                }
                $charTree = self::fromString(
                    $charTree->root,
                    array_merge($normalizedBranches, $branches)
                );
            }
            $normalized[$charTree->root] = $charTree;
        }

        return $normalized;
    }

    /**
     * @return string|null Root of the character tree.
     */
    public function getRoot(): ?string
    {
        return $this->root;
    }

    /**
     * @return array<self> Branches of the character tree.
     */
    public function getBranches(): array
    {
        return $this->branches;
    }

    /**
     * @param string $string String to check.
     * @param bool $ignoreCase Whether character case should be ignored.
     * @return bool Whether the character tree contains the string.
     */
    public function contains(string $string, bool $ignoreCase = false): bool
    {
        $key = $string . ($ignoreCase ? 1 : 0);
        if (!isset($this->containsMemoization[$key])) {
            $this->containsMemoization[$key] = $this->calculateContains($string, $ignoreCase);
        }

        return $this->containsMemoization[$key];
    }

    /**
     * @param string $string String to check.
     * @param bool $ignoreCase Whether character case should be ignored.
     * @return bool Whether the character tree starts with the string.
     */
    public function startsWith(string $string, bool $ignoreCase = false): bool
    {
        $key = $string . ($ignoreCase ? 1 : 0);
        if (!isset($this->startsWithMemoization[$key])) {
            $this->startsWithMemoization[$key] = $this->calculateStartsWith($string, $ignoreCase);
        }

        return $this->startsWithMemoization[$key];
    }

    /**
     * @param string $string String to check.
     * @param bool $ignoreCase Whether character case should be ignored.
     * @return bool Whether the character tree contains the string. Memoization is not used.
     */
    private function calculateContains(string $string, bool $ignoreCase): bool
    {
        if ($this->startsWith($string, $ignoreCase)) {
            return true;
        }

        foreach ($this->branches as $branch) {
            if ($branch->contains($string, $ignoreCase)) {
                return true;
            }
        }

        return false;
    }

    /**
     * @param string $string String to check.
     * @param bool $ignoreCase Whether character case should be ignored.
     * @return bool Whether the character tree starts with the string. Memoization is not used.
     */
    private function calculateStartsWith(string $string, bool $ignoreCase): bool
    {
        if ($this->rootEquals($string, $ignoreCase)) {
            assert($this->root !== null);
            $stringTail = mb_substr($string, mb_strlen($this->root));
            if ($stringTail === '') {
                return true;
            } else {
                foreach ($this->branches as $branch) {
                    if ($branch->startsWith($stringTail, $ignoreCase)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    /**
     * @param string $string String to check.
     * @param bool $ignoreCase Whether character case should be ignored.
     * @return bool Whether the character tree's root equals the string.
     */
    private function rootEquals(string $string, bool $ignoreCase): bool
    {
        if ($this->root === null) {
            return false;
        }

        $root = mb_substr($string, 0, mb_strlen($this->root));
        if ($ignoreCase) {
            return strcasecmp($this->root, $root) === 0;
        }

        return $this->root === $root;
    }

    /**
     * @return Traversable<string> All strings in the character tree.
     */
    public function getIterator(): Traversable
    {
        if ($this->root !== null) {
            foreach ($this->branches as $branch) {
                if ($branch->root === null) {
                    yield $this->root;
                } else {
                    foreach ($branch as $string) {
                        yield $this->root . $string;
                    }
                }
            }

            if ($this->branches === []) {
                yield $this->root;
            }
        }
    }
}


1		<?php
2
3		declare(strict_types=1);
4
5		namespace Stadly\PasswordPolice;
6
7		use IteratorAggregate;
8		use Traversable;
9
10		final class CharTree implements IteratorAggregate
11		{
12		/**
13		* @var string\|null Root of the character tree. No more than 1 character long.
14		*/
15		private $root;
16
17		/**
18		* @var array<self> Branches of the character tree.
19		*/
20		private $branches = [];
21
22		/**
23		* @var array<bool> Memoization of startsWith().
24		*/
25		private $startsWithMemoization = [];
26
27		/**
28		* @var array<bool> Memoization of contains().
29		*/
30		private $containsMemoization = [];
31
32		/**
33		* @var array<CharTree> Memoization of constructed character trees.
34		*/
35		private static $constructMemoization = [];
36
37		/**
38		* @param string\|null $root Root of the character tree. No more than 1 character long.
39		* @param array<self> $branches Branches of the character tree.
40		*/
41	8	private function __construct(?string $root, array $branches)
42		{
43	8	assert($root !== null \|\| $branches === [], 'Empty tree cannot have branches.');
44	8	assert($root === null \|\| mb_strlen($root) <= 1, 'Root must contain at most one character.');
45
46	8	$this->root = $root;
47	8	$this->branches = $branches;
48	8	}
49
50		/**
51		* @param string\|null $root Root of the character tree. No more than 1 character long.
52		* @param array<self> $branches Branches of the character tree.
53		*/
54	27	private static function construct(?string $root, array $branches): self
55		{
56	27	if ($root === null) {
57	20	assert($branches === [], 'Empty tree cannot have branches.');
58	20	if (!isset(self::$constructMemoization['null'])) {
59	1	self::$constructMemoization['null'] = new self($root, $branches);
60		}
61	20	return self::$constructMemoization['null'];
62		}
63
64	24	assert(mb_strlen($root) <= 1, 'Root must contain at most one character.');
65
66	24	$hash = $root;
67	24	ksort($branches, SORT_STRING);
68	24	foreach ($branches as $branch) {
69		// When PHP 7.1 is no longer supported, change to using spl_object_id.
70	17	$branchHash = spl_object_hash($branch);
71	17	$hash .= ';' . $branchHash;
72		}
73
74	24	if (!isset(self::$constructMemoization[$hash])) {
75	7	self::$constructMemoization[$hash] = new self($root, $branches);
76		}
77
78	24	return self::$constructMemoization[$hash];
79		}
80
81		/**
82		* @param string $string Root of the character tree.
83		* @param array<self> $branches Branches of the character tree.
84		*/
85	9	public static function fromString(string $string, array $branches = []): self
86		{
87	9	if (mb_strlen($string) > 1) {
88		// Maximum one character in root.
89	3	$branches = [self::fromString(mb_substr($string, 1), $branches)];
90	3	$string = mb_substr($string, 0, 1);
91		}
92
93	9	$branches = self::promoteEmptyRoots($branches);
94	9	$branches = self::combineDuplicateRoots($branches);
95
96	9	if (count($branches) === 1) {
97	6	$branch = reset($branches);
98	6	if ($branch->root === null) {
99		// If only one branch and its root is null, throw it away.
100	3	$branches = [];
101	4	} elseif ($string === '') {
102		// If root is empty string and only one branch, use it.
103	2	return $branch;
104		}
105		}
106
107	9	return self::construct($string, $branches);
108		}
109
110		/**
111		* @param array<self> $charTrees Character trees to combine.
112		*/
113	4	public static function fromArray(array $charTrees): self
114		{
115	4	foreach ($charTrees as $charTree) {
116	3	if ($charTree->root !== null) {
117	3	return self::fromString('', $charTrees);
118		}
119		}
120
121	2	return self::fromNothing();
122		}
123
124		/**
125		* Construct empty character tree.
126		*/
127	1	public static function fromNothing(): self
128		{
129	1	return self::construct(null, []);
130		}
131
132		/**
133		* @param array<self> $charTrees Character trees to normalize.
134		* @return array<self> Character trees where branches of trees with empty string roots have been promoted to trees.
135		*/
136	24	private static function promoteEmptyRoots(array $charTrees): array
137		{
138	24	$normalized = [];
139	24	foreach ($charTrees as $charTree) {
140	21	if ($charTree->root === '') {
141	5	if ($charTree->branches !== []) {
142	1	$normalized = array_merge($normalized, array_values($charTree->branches));
143		} else {
144	5	$normalized[] = self::fromNothing();
145		}
146		} else {
147	21	$normalized[] = $charTree;
148		}
149		}
150
151	24	return $normalized;
152		}
153
154		/**
155		* @param array<self> $charTrees Character trees to normalize.
156		* @return array<self> Character trees where branches of trees with the same root have been combined.
157		*/
158	24	private static function combineDuplicateRoots(array $charTrees): array
159		{
160	24	$normalized = [];
161	24	foreach ($charTrees as $charTree) {
162	21	if (isset($normalized[$charTree->root]) && $charTree->root !== null) {
163	15	$normalizedCharTree = $normalized[$charTree->root];
164	15	$normalizedBranches = array_values($normalizedCharTree->branches);
165	15	if ($normalizedBranches === []) {
166	13	$normalizedBranches[] = self::fromNothing();
167		}
168	15	$branches = array_values($charTree->branches);
169	15	if ($branches === []) {
170	2	$branches[] = self::fromNothing();
171		}
172	15	$charTree = self::fromString(
173	15	$charTree->root,
174	15	array_merge($normalizedBranches, $branches)
175		);
176		}
177	21	$normalized[$charTree->root] = $charTree;
178		}
179
180	24	return $normalized;
181		}
182
183		/**
184		* @return string\|null Root of the character tree.
185		*/
186	1	public function getRoot(): ?string
187		{
188	1	return $this->root;
189		}
190
191		/**
192		* @return array<self> Branches of the character tree.
193		*/
194	1	public function getBranches(): array
195		{
196	1	return $this->branches;
197		}
198
199		/**
200		* @param string $string String to check.
201		* @param bool $ignoreCase Whether character case should be ignored.
202		* @return bool Whether the character tree contains the string.
203	5	*/
204		public function contains(string $string, bool $ignoreCase = false): bool
205	5	{
206	5	$key = $string . ($ignoreCase ? 1 : 0);
207		if (!isset($this->containsMemoization[$key])) {
208		$this->containsMemoization[$key] = $this->calculateContains($string, $ignoreCase);
209	5	}
210
211		return $this->containsMemoization[$key];
212		}
213
214		/**
215		* @param string $string String to check.
216	5	* @param bool $ignoreCase Whether character case should be ignored.
217		* @return bool Whether the character tree starts with the string.
218	5	*/
219	5	public function startsWith(string $string, bool $ignoreCase = false): bool
220		{
221		$key = $string . ($ignoreCase ? 1 : 0);
222	5	if (!isset($this->startsWithMemoization[$key])) {
223		$this->startsWithMemoization[$key] = $this->calculateStartsWith($string, $ignoreCase);
224		}
225
226		return $this->startsWithMemoization[$key];
227		}
228
229	5	/**
230		* @param string $string String to check.
231	5	* @param bool $ignoreCase Whether character case should be ignored.
232	4	* @return bool Whether the character tree contains the string. Memoization is not used.
233		*/
234		private function calculateContains(string $string, bool $ignoreCase): bool
235	3	{
236	3	if ($this->startsWith($string, $ignoreCase)) {
237	3	return true;
238		}
239
240		foreach ($this->branches as $branch) {
241	3	if ($branch->contains($string, $ignoreCase)) {
242		return true;
243		}
244		}
245
246		return false;
247		}
248	10
249		/**
250	10	* @param string $string String to check.
251	10	* @param bool $ignoreCase Whether character case should be ignored.
252	10	* @return bool Whether the character tree starts with the string. Memoization is not used.
253	4	*/
254		private function calculateStartsWith(string $string, bool $ignoreCase): bool
255	10	{
256	10	if ($this->rootEquals($string, $ignoreCase)) {
257	10	assert($this->root !== null);
258		$stringTail = mb_substr($string, mb_strlen($this->root));
259		if ($stringTail === '') {
260		return true;
261		} else {
262		foreach ($this->branches as $branch) {
263	8	if ($branch->startsWith($stringTail, $ignoreCase)) {
264		return true;
265		}
266		}
267		}
268		}
269	1
270		return false;
271	1	}
272	1
273	1	/**
274	1	* @param string $string String to check.
275		* @param bool $ignoreCase Whether character case should be ignored.
276	1	* @return bool Whether the character tree's root equals the string.
277	1	*/
278		private function rootEquals(string $string, bool $ignoreCase): bool
279		{
280		if ($this->root === null) {
281		return false;
282	1	}
283	1
284		$root = mb_substr($string, 0, mb_strlen($this->root));
285		if ($ignoreCase) {
286	1	return strcasecmp($this->root, $root) === 0;
287		}
288
289		return $this->root === $root;
290		}
291
292		/**
293		* @return Traversable<string> All strings in the character tree.
294		*/
295		public function getIterator(): Traversable
296		{
297		if ($this->root !== null) {
298		foreach ($this->branches as $branch) {
299		if ($branch->root === null) {
300		yield $this->root;
301		} else {
302		foreach ($branch as $string) {
303		yield $this->root . $string;
304		}
305		}
306		}
307
308		if ($this->branches === []) {
309		yield $this->root;
310		}
311		}
312		}
313		}
314

Stadly / PasswordPolice

CharTree::combineDuplicateRoots() A last analyzed 2020-05-08 06:26 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

CharTree::combineDuplicateRoots() A
last analyzed 2020-05-08 06:26 UTC