CharTree::calculateStartsWith() - Code Metrics - Inspection of "Character tree to work on collections of strings" - Stadly/PasswordPolice - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 33a2c8...a2e523 )

by Magnar Ovedal

created 2019-04-11 15:06 UTC

CharTree::calculateStartsWith() A

↳ Parent: CharTree

Complexity

Conditions	6
Paths	4

Size

Total Lines	16
Code Lines	9

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	9
CRAP Score	6

Importance

Changes

Metric	Value
cc	6
eloc	9
nc	4
nop	1
dl	0
loc	16
ccs	9
cts	9
cp	1
crap	6
rs	9.2222
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 = [];

    /**
     * @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)
    {
        if ($root !== null && 1 < mb_strlen($root)) {
            throw new InvalidArgumentException('Root must contain at most one character.');
        }

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

    /**
     * @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) {
            if ($string === '') {
                // If root is empty and only one branch, use it.
                return reset($branches);
            }
            if (reset($branches)->root === null) {
                // If only one branch and its root is null, throw it away.
                $branches = [];
            }
        }

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

Stadly / PasswordPolice

Push — master ( 33a2c8...a2e523 )

CharTree::calculateStartsWith() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like