CharTree::startsWith() - Code Metrics - Inspection of "Memoize created character trees" - Stadly/PasswordPolice - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 49a7e1...6c8d7b )

by Magnar Ovedal

created 2019-04-15 10:23 UTC

CharTree::startsWith() A

↳ Parent: CharTree

Complexity

Conditions	2
Paths	2

Size

Total Lines	7
Code Lines	3

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	4
CRAP Score	2

Importance

Changes

Metric	Value
cc	2
eloc	3
nc	2
nop	1
dl	0
loc	7
ccs	4
cts	4
cp	1
crap	2
rs	10
c	0
b	0
f	0

<?php

declare(strict_types=1);

namespace Stadly\PasswordPolice;

use InvalidArgumentException;
use IteratorAggregate;
use Traversable;

final class CharTree implements IteratorAggregate
{
    /**
     * @var string|null
     */
    private $root;

    /**
     * @var self[]
     */
    private $branches = [];

    /**
     * @var bool[]
     */
    private $startsWithMemoization = [];

    /**
     * @var bool[]
     */
    private $containsMemoization = [];

    /**
     * @var CharTree[]
     */
    private static $charTreeMemoization = [];

    /**
     * @param string|null $root Root of the character tree. No more than 1 character long.
     * @param 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 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::$charTreeMemoization['null'])) {
                self::$charTreeMemoization['null'] = new self($root, $branches);
            }
            return self::$charTreeMemoization['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::$charTreeMemoization[$hash])) {
            self::$charTreeMemoization[$hash] = new self($root, $branches);
        }

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

    /**
     * @param string $string Root of the character tree.
     * @param self[] $branches Branches of the character tree.
     */
    public static function fromString(string $string, array $branches = []): self
    {
        if (1 < mb_strlen($string)) {
            // 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 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 self[] $charTrees Character trees to normalize.
     * @return 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 self[] $charTrees Character trees to normalize.
     * @return 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 self[] Branches of the character tree.
     */
    public function getBranches(): array
    {
        return $this->branches;
    }

    /**
     * @param int $length Length of each string in the character tree.
     * @return self Character tree containing the $length first characters of this character tree.
     */
    public function getTreeTrimmedToLength(int $length): self
    {
        if ($length < 0) {
            throw new InvalidArgumentException('Length must be non-negative.');
        }

        if ($this->root === null) {
            return $this;
        }

        if ($length === 0) {
            return self::fromString('');
        }

        $branches = [];
        $rootLength = mb_strlen($this->root);
        if ($rootLength < $length) {
            $branchLength = $length-$rootLength;
            foreach ($this->branches as $branch) {
                $branchTree = $branch->getTreeTrimmedToLength($branchLength);
                if ($branchTree->root !== null) {
                    $branches[] = $branchTree;
                }
            }

            if ($branches === []) {
                return self::fromNothing();
            }
        }

        return self::fromString($this->root, $branches);
    }

    /**
     * @param string $root Root that comes before the brances.
     * @return self Character tree containing the branches of this character tree that come after $root.
     */
    public function getBranchesAfterRoot(string $root): self
    {
        if ($this->root === null || $root === '') {
            return $this;
        }

        if ($this->root === $root) {
            return self::fromString('', $this->branches);
        }

        if ($this->root !== mb_substr($root, 0, mb_strlen($this->root))) {
            return self::fromNothing();
        }

        $rootTail = mb_substr($root, mb_strlen($this->root));
        $rootHead = mb_substr($rootTail, 0, 1);

        if (!isset($this->branches[$rootHead])) {
            return self::fromNothing();
        }

        return $this->branches[$rootHead]->getBranchesAfterRoot($rootTail);
    }

    /**
     * @param string $string String to check.
     * @return bool Whether the character tree contains the string.
     */
    public function contains(string $string): bool
    {
        if (!isset($this->containsMemoization[$string])) {
            $this->containsMemoization[$string] = $this->calculateContains($string);
        }

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

    /**
     * @param string $string String to check.
     * @return bool Whether the character tree starts with the string.
     */
    public function startsWith(string $string): bool
    {
        if (!isset($this->startsWithMemoization[$string])) {
            $this->startsWithMemoization[$string] = $this->calculateStartsWith($string);
        }

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

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

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

        return false;
    }

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

        return false;
    }

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

Stadly / PasswordPolice

Push — master ( 49a7e1...6c8d7b )

CharTree::startsWith() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like