CommitOrderCalculator::visit() - Code Metrics - Inspection of "[GH-1204] Add full support for foreign key constra..." - doctrine/dbal - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Pull Request — 2.10 (#3762)

by Benjamin

created 2019-12-29 21:52 UTC

CommitOrderCalculator::visit() B

↳ Parent: CommitOrderCalculator

Complexity

Conditions	10
Paths	12

Size

Total Lines	45
Code Lines	23

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
eloc	23
c	1
b	0
f	0
dl	0
loc	45
rs	7.6666
cc	10
nc	12
nop	1

How to fix Complexity

<?php

namespace Doctrine\DBAL\Internal;

use function array_reverse;

/**
 * CommitOrderCalculator implements topological sorting, which is an ordering
 * algorithm for directed graphs (DG) and/or directed acyclic graphs (DAG) by
 * using a depth-first searching (DFS) to traverse the graph built in memory.
 * This algorithm have a linear running time based on nodes (V) and dependency
 * between the nodes (E), resulting in a computational complexity of O(V + E).
 */
final class CommitOrderCalculator
{
    public const NOT_VISITED = 0;
    public const IN_PROGRESS = 1;
    public const VISITED     = 2;

    /**
     * Matrix of nodes (aka. vertex).
     * Keys are provided hashes and values are the node definition objects.
     *
     * @var array<string,CommitOrderNode>
     */
    private $nodeList = [];

    /**
     * Volatile variable holding calculated nodes during sorting process.
     *
     * @var array<object>
     */
    private $sortedNodeList = [];

    /**
     * Checks for node (vertex) existence in graph.
     */
    public function hasNode(string $hash) : bool
    {
        return isset($this->nodeList[$hash]);
    }

    /**
     * Adds a new node (vertex) to the graph, assigning its hash and value.
     *
     * @param object $node
     */
    public function addNode(string $hash, $node) : void
    {
        $vertex = new CommitOrderNode();

        $vertex->hash  = $hash;
        $vertex->state = self::NOT_VISITED;
        $vertex->value = $node;

        $this->nodeList[$hash] = $vertex;
    }

    /**
     * Adds a new dependency (edge) to the graph using their hashes.
     */
    public function addDependency(string $fromHash, string $toHash, int $weight) : void
    {
        $vertex = $this->nodeList[$fromHash];
        $edge   = new CommitOrderEdge();

        $edge->from   = $fromHash;
        $edge->to     = $toHash;
        $edge->weight = $weight;

        $vertex->dependencyList[$toHash] = $edge;
    }

    /**
     * Return a valid order list of all current nodes.
     * The desired topological sorting is the reverse post order of these searches.
     *
     * {@internal Highly performance-sensitive method.}
     *
     * @return array<object>
     */
    public function sort() : array
    {
        foreach ($this->nodeList as $vertex) {
            if ($vertex->state !== self::NOT_VISITED) {
                continue;
            }

            $this->visit($vertex);
        }

        $sortedList = $this->sortedNodeList;

        $this->nodeList       = [];
        $this->sortedNodeList = [];

        return array_reverse($sortedList);
    }

    /**
     * Visit a given node definition for reordering.
     *
     * {@internal Highly performance-sensitive method.}
     */
    private function visit(CommitOrderNode $vertex)
    {
        $vertex->state = self::IN_PROGRESS;

        foreach ($vertex->dependencyList as $edge) {
            $adjacentVertex = $this->nodeList[$edge->to];

            switch ($adjacentVertex->state) {
                case self::VISITED:
                    // Do nothing, since node was already visited
                    break;

                case self::IN_PROGRESS:
                    if (isset($adjacentVertex->dependencyList[$vertex->hash]) &&
                        $adjacentVertex->dependencyList[$vertex->hash]->weight < $edge->weight) {
                        // If we have some non-visited dependencies in the in-progress dependency, we
                        // need to visit them before adding the node.
                        foreach ($adjacentVertex->dependencyList as $adjacentEdge) {
                            $adjacentEdgeVertex = $this->nodeList[$adjacentEdge->to];

                            if ($adjacentEdgeVertex->state !== self::NOT_VISITED) {
                                continue;
                            }

                            $this->visit($adjacentEdgeVertex);
                        }

                        $adjacentVertex->state = self::VISITED;

                        $this->sortedNodeList[] = $adjacentVertex->value;
                    }
                    break;

                case self::NOT_VISITED:
                    $this->visit($adjacentVertex);
            }
        }

        if ($vertex->state === self::VISITED) {
            return;
        }

        $vertex->state = self::VISITED;

        $this->sortedNodeList[] = $vertex->value;
    }
}


1			<?php
2
3			namespace Doctrine\DBAL\Internal;
4
5			use function array_reverse;
6
7			/**
8			* CommitOrderCalculator implements topological sorting, which is an ordering
9			* algorithm for directed graphs (DG) and/or directed acyclic graphs (DAG) by
10			* using a depth-first searching (DFS) to traverse the graph built in memory.
11			* This algorithm have a linear running time based on nodes (V) and dependency
12			* between the nodes (E), resulting in a computational complexity of O(V + E).
13			*/
14			final class CommitOrderCalculator
15			{
16			public const NOT_VISITED = 0;
17			public const IN_PROGRESS = 1;
18			public const VISITED = 2;
19
20			/**
21			* Matrix of nodes (aka. vertex).
22			* Keys are provided hashes and values are the node definition objects.
23			*
24			* @var array<string,CommitOrderNode>
25			*/
26			private $nodeList = [];
27
28			/**
29			* Volatile variable holding calculated nodes during sorting process.
30			*
31			* @var array<object>
32			*/
33			private $sortedNodeList = [];
34
35			/**
36			* Checks for node (vertex) existence in graph.
37			*/
38			public function hasNode(string $hash) : bool
39			{
40			return isset($this->nodeList[$hash]);
41			}
42
43			/**
44			* Adds a new node (vertex) to the graph, assigning its hash and value.
45			*
46			* @param object $node
47			*/
48			public function addNode(string $hash, $node) : void
49			{
50			$vertex = new CommitOrderNode();
51
52			$vertex->hash = $hash;
53			$vertex->state = self::NOT_VISITED;
54			$vertex->value = $node;
55
56			$this->nodeList[$hash] = $vertex;
57			}
58
59			/**
60			* Adds a new dependency (edge) to the graph using their hashes.
61			*/
62			public function addDependency(string $fromHash, string $toHash, int $weight) : void
63			{
64			$vertex = $this->nodeList[$fromHash];
65			$edge = new CommitOrderEdge();
66
67			$edge->from = $fromHash;
68			$edge->to = $toHash;
69			$edge->weight = $weight;
70
71			$vertex->dependencyList[$toHash] = $edge;
72			}
73
74			/**
75			* Return a valid order list of all current nodes.
76			* The desired topological sorting is the reverse post order of these searches.
77			*
78			* {@internal Highly performance-sensitive method.}
79			*
80			* @return array<object>
81			*/
82			public function sort() : array
83			{
84			foreach ($this->nodeList as $vertex) {
85			if ($vertex->state !== self::NOT_VISITED) {
86			continue;
87			}
88
89			$this->visit($vertex);
90			}
91
92			$sortedList = $this->sortedNodeList;
93
94			$this->nodeList = [];
95			$this->sortedNodeList = [];
96
97			return array_reverse($sortedList);
98			}
99
100			/**
101			* Visit a given node definition for reordering.
102			*
103			* {@internal Highly performance-sensitive method.}
104			*/
105			private function visit(CommitOrderNode $vertex)
106			{
107			$vertex->state = self::IN_PROGRESS;
108
109			foreach ($vertex->dependencyList as $edge) {
110			$adjacentVertex = $this->nodeList[$edge->to];
111
112			switch ($adjacentVertex->state) {
113			case self::VISITED:
114			// Do nothing, since node was already visited
115			break;
116
117			case self::IN_PROGRESS:
118			if (isset($adjacentVertex->dependencyList[$vertex->hash]) &&
119			$adjacentVertex->dependencyList[$vertex->hash]->weight < $edge->weight) {
120			// If we have some non-visited dependencies in the in-progress dependency, we
121			// need to visit them before adding the node.
122			foreach ($adjacentVertex->dependencyList as $adjacentEdge) {
123			$adjacentEdgeVertex = $this->nodeList[$adjacentEdge->to];
124
125			if ($adjacentEdgeVertex->state !== self::NOT_VISITED) {
126			continue;
127			}
128
129			$this->visit($adjacentEdgeVertex);
130			}
131
132			$adjacentVertex->state = self::VISITED;
133
134			$this->sortedNodeList[] = $adjacentVertex->value;
135			}
136			break;
137
138			case self::NOT_VISITED:
139			$this->visit($adjacentVertex);
140			}
141			}
142
143			if ($vertex->state === self::VISITED) {
144			return;
145			}
146
147			$vertex->state = self::VISITED;
148
149			$this->sortedNodeList[] = $vertex->value;
150			}
151			}
152

doctrine / dbal

Pull Request — 2.10 (#3762)

CommitOrderCalculator::visit() B

Complexity

Size

Duplication

Importance

How to fix Complexity

Long Method

Duplication Side-by-Side

Filter issues like