ParenthesesParser::comb() - Code Metrics - Inspection of "Implement link parsing" - adam-boduch/coyote - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Pull Request — master (#532)

by Daniel

created 2020-05-25 19:15 UTC

ParenthesesParser::comb() A

↳ Parent: ParenthesesParser

Complexity

Conditions	2
Paths	2

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	2
nc	2
nop	2
dl	0
loc	8
rs	10
c	0
b	0
f	0

<?php

namespace Coyote\Services\Parser\Parsers\Parentheses;

use Tests\Feature\Services\Parser\Parsers\Parentheses\ParenthesesParserTest;

/**
 * If you read {@link ParenthesesParserTest} you will see examples, of how this
 * class works.
 *
 * This class responsibility is to use symmetric or mismatched chunks returned
 * by {@link SymmetricParenthesesChunks} and "comb" them into valid/invalid
 * parentheses expressions. It is done in two steps:
 *  - Combing:
 *    - Iterates chunks first by pairs (if nestLevel is >= 0).
 *    - Then, iterates by triplets (if nestLevel is >= 1).
 *    - Then, iterates chunks by four of each (if nestLevel is >= 2), and so on
 *      Algorithm complexity is: o(n * c), where:
 *      - `n` - is the number of chunks, which is number of symmetric parentheses in input string divided by two.
 *      - `l` - nestLevel
 *      So for nestLevel=chunks (n=l), complexity is: o(n^2)
 *    After combing, `l` levels of parentheses should be joined into one. (So for example,
 *      for nestLevel=6, parentheses nested 7 times won't be parsed).
 *  - Squashing
 *    - Joins any two valid adjacent chunks into one, so they can be later for example
 *       rendered as a single link.
 */
class ParenthesesParser
{
    /** @var SymmetricParenthesesChunks */
    private $chunks;
    /** @var int */
    private $nestLevel;

    public function __construct(SymmetricParenthesesChunks $chunks, int $nestLevel)
    {
        $this->chunks = $chunks;
        $this->nestLevel = $nestLevel;
    }

    public function parse(string $content): array
    {
        $chunks = $this->chunks->chunk($content);
        $chunks = $this->comb($chunks, 1);
        $chunks = $this->flatMapMismatched($chunks);
        $chunks = $this->comb($chunks, $this->nestLevel - 1);
        $chunks = $this->squashChunks($chunks);
        return $chunks;
    }

    private function comb(array $elements, int $iterations): array
    {
        $result = $elements;
        for ($i = 0; $i < $iterations; $i++) {
            $result = $this->performCombIteration($result, $i + 1);
        }
        return $result;
    }

    private function performCombIteration(array $elements, int $nestLevel): array
    {
        // for $nestLevel < 0 this method doesn't make any sense
        // for $nestLevel = 0 this method doesn't have any effect
        if ($nestLevel < 0) {
            throw new \InvalidArgumentException();
        }
        $result = [];
        for ($i = 0; $i < count($elements); $i++) {
for ($i=0; $i<count($array); $i++) { // calls count() on each iteration
}

// Better
for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once
}
            $toComb = join(array_slice($elements, $i, $nestLevel + 1));
            if ($this->validExpression($toComb)) {
                $result[] = $toComb;
                $i += $nestLevel;
                continue;
            }
            $result[] = $elements[$i];
        }
        return $result;
    }

    private function flatMapMismatched(array $elements): array
    {
        $result = [];
        foreach ($elements as $element) {
            if ($this->validExpression($element)) {
                $result[] = $element;
            } else {
                $result = array_merge($result, pattern('([()])')->split($element));
            }
        }
        return array_values(array_filter($result, 'strlen'));
    }

    private function squashChunks(array $chunks): array
    {
        $result = [];
        $squashedChunks = null;
        foreach ($chunks as $chunk) {
            if ($this->validExpression($chunk)) {
                $squashedChunks .= $chunk;
            } else {
                if ($squashedChunks !== null) {
                    $result[] = $squashedChunks;
                    $squashedChunks = null;
                }
                $result[] = $chunk;
            }
        }
        if ($squashedChunks !== null) {
            $result[] = $squashedChunks;
        }
        return $result;
    }

    private function validExpression(string $expression): bool
    {
        return mb_substr_count($expression, '(') === mb_substr_count($expression, ')');
        // Technically, ")(" would also be considered a valid expression,
        // but `ParenthesesChunks` will not return such chunks.
    }
}


1			<?php
2
3			namespace Coyote\Services\Parser\Parsers\Parentheses;
4
5			use Tests\Feature\Services\Parser\Parsers\Parentheses\ParenthesesParserTest;
6
7			/**
8			* If you read {@link ParenthesesParserTest} you will see examples, of how this
9			* class works.
10			*
11			* This class responsibility is to use symmetric or mismatched chunks returned
12			* by {@link SymmetricParenthesesChunks} and "comb" them into valid/invalid
13			* parentheses expressions. It is done in two steps:
14			* - Combing:
15			* - Iterates chunks first by pairs (if nestLevel is >= 0).
16			* - Then, iterates by triplets (if nestLevel is >= 1).
17			* - Then, iterates chunks by four of each (if nestLevel is >= 2), and so on
18			* Algorithm complexity is: o(n * c), where:
19			* - `n` - is the number of chunks, which is number of symmetric parentheses in input string divided by two.
20			* - `l` - nestLevel
21			* So for nestLevel=chunks (n=l), complexity is: o(n^2)
22			* After combing, `l` levels of parentheses should be joined into one. (So for example,
23			* for nestLevel=6, parentheses nested 7 times won't be parsed).
24			* - Squashing
25			* - Joins any two valid adjacent chunks into one, so they can be later for example
26			* rendered as a single link.
27			*/
28			class ParenthesesParser
29			{
30			/** @var SymmetricParenthesesChunks */
31			private $chunks;
32			/** @var int */
33			private $nestLevel;
34
35			public function __construct(SymmetricParenthesesChunks $chunks, int $nestLevel)
36			{
37			$this->chunks = $chunks;
38			$this->nestLevel = $nestLevel;
39			}
40
41			public function parse(string $content): array
42			{
43			$chunks = $this->chunks->chunk($content);
44			$chunks = $this->comb($chunks, 1);
45			$chunks = $this->flatMapMismatched($chunks);
46			$chunks = $this->comb($chunks, $this->nestLevel - 1);
47			$chunks = $this->squashChunks($chunks);
48			return $chunks;
49			}
50
51			private function comb(array $elements, int $iterations): array
52			{
53			$result = $elements;
54			for ($i = 0; $i < $iterations; $i++) {
55			$result = $this->performCombIteration($result, $i + 1);
56			}
57			return $result;
58			}
59
60			private function performCombIteration(array $elements, int $nestLevel): array
61			{
62			// for $nestLevel < 0 this method doesn't make any sense
63			// for $nestLevel = 0 this method doesn't have any effect
64			if ($nestLevel < 0) {
65			throw new \InvalidArgumentException();
66			}
67			$result = [];
68			for ($i = 0; $i < count($elements); $i++) {
			0 ignored issues – show Performance Best Practice introduced 2020-05-05 19:26 UTC by Report Bug Copy Issue Report It seems like you are calling the size function `count()` as part of the test condition. You might want to compute the size beforehand, and not on each iteration. If the size of the collection does not change during the iteration, it is generally a good practice to compute it beforehand, and not on each iteration: for ($i=0; $i<count($array); $i++) { // calls count() on each iteration } // Better for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once } Loading history...
69			$toComb = join(array_slice($elements, $i, $nestLevel + 1));
70			if ($this->validExpression($toComb)) {
71			$result[] = $toComb;
72			$i += $nestLevel;
73			continue;
74			}
75			$result[] = $elements[$i];
76			}
77			return $result;
78			}
79
80			private function flatMapMismatched(array $elements): array
81			{
82			$result = [];
83			foreach ($elements as $element) {
84			if ($this->validExpression($element)) {
85			$result[] = $element;
86			} else {
87			$result = array_merge($result, pattern('([()])')->split($element));
88			}
89			}
90			return array_values(array_filter($result, 'strlen'));
91			}
92
93			private function squashChunks(array $chunks): array
94			{
95			$result = [];
96			$squashedChunks = null;
97			foreach ($chunks as $chunk) {
98			if ($this->validExpression($chunk)) {
99			$squashedChunks .= $chunk;
100			} else {
101			if ($squashedChunks !== null) {
102			$result[] = $squashedChunks;
103			$squashedChunks = null;
104			}
105			$result[] = $chunk;
106			}
107			}
108			if ($squashedChunks !== null) {
109			$result[] = $squashedChunks;
110			}
111			return $result;
112			}
113
114			private function validExpression(string $expression): bool
115			{
116			return mb_substr_count($expression, '(') === mb_substr_count($expression, ')');
117			// Technically, ")(" would also be considered a valid expression,
118			// but `ParenthesesChunks` will not return such chunks.
119			}
120			}
121

adam-boduch / coyote

Pull Request — master (#532)

ParenthesesParser::comb() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like