1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
<?php
namespace ParamProcessor;
/**
* Sorts a series of dependency pairs in linear order.
*
* Based on http://blog.metafoundry.com/2007/09/topological-sort-in-php.html
*
* @deprecated since 1.7
* @codingStandardsIgnoreFile
*/
class TopologicalSort {
private $mNodes = [];
private $mNodeNames = [];
/**
* Dependency pairs are a list of arrays in the form
* $name => $val where $key must come before $val in load order.
*/
public function __construct( array $dependencies = [], $parse = true ) {
$this->mNodeNames = array_keys( $dependencies );
if ( $parse ) {
$dependencies = $this->parseDependencyList( $dependencies );
}
// turn pairs into double-linked node tree
foreach ( $dependencies as $dpair ) {
$module = key( $dpair );
$dependency = current( $dpair );
if ( !isset( $this->mNodes[$module] ) ) $this->mNodes[$module] = new TSNode( $module );
if ( !isset( $this->mNodes[$dependency] ) ) $this->mNodes[$dependency] = new TSNode( $dependency );
if ( !in_array( $dependency, $this->mNodes[$module]->children ) ) $this->mNodes[$module]->children[] = $dependency;
if ( !in_array( $module, $this->mNodes[$dependency]->parents ) ) $this->mNodes[$dependency]->parents[] = $module;
}
}
/**
* Perform Topological Sort.
*
* @return array Sorted array
*/
public function doSort() {
$nodes = $this->mNodes;
// get nodes without parents
$root_nodes = array_values( $this->getRootNodes( $nodes ) );
// begin algorithm
$sorted = [];
while ( count( $nodes ) > 0 ) {
// check for circular reference
if ( $root_nodes === [] ) {
return [];
}
// remove this node from root_nodes
// and add it to the output
$n = array_pop( $root_nodes );
$sorted[] = $n->name;
// for each of its children
// queue the new node finally remove the original
for ( $i = count( $n->children ) - 1; $i >= 0; $i -- ) {
$childnode = $n->children[$i];
// remove the link from this node to its
// children ($nodes[$n->name]->children[$i]) AND
// remove the link from each child to this
// parent ($nodes[$childnode]->parents[?]) THEN
// remove this child from this node
unset( $nodes[$n->name]->children[$i] );
$parent_position = array_search ( $n->name, $nodes[$childnode]->parents );
unset( $nodes[$childnode]->parents[$parent_position] );
// check if this child has other parents
// if not, add it to the root nodes list
if ( !count( $nodes[$childnode]->parents ) ) {
array_push( $root_nodes, $nodes [$childnode] );
}
}
// nodes.Remove(n);
unset( $nodes[$n->name] );
}
$looseNodes = [];
// Return the result with the loose nodes (items with no dependencies) appended.
foreach( $this->mNodeNames as $name ) {
if ( !in_array( $name, $sorted ) ) {
$looseNodes[] = $name;
}
}
return array_merge( $sorted, $looseNodes );
}
/**
* Returns a list of node objects that do not have parents
*
* @param array $nodes array of node objects
*
* @return array of node objects
*/
private function getRootNodes( array $nodes ) {
$output = [];
foreach ( $nodes as $name => $node ) {
if ( !count ( $node->parents ) ) {
$output[$name] = $node;
}
}
return $output;
}
/**
* Parses an array of dependencies into an array of dependency pairs
*
* The array of dependencies would be in the form:
* $dependency_list = array(
* "name" => array("dependency1","dependency2","dependency3"),
* "name2" => array("dependencyA","dependencyB","dependencyC"),
* ...etc
* );
*
* @param array $dlist Array of dependency pairs for use as parameter in doSort method
*
* @return array
*/
private function parseDependencyList( array $dlist = [] ) {
$output = [];
foreach ( $dlist as $name => $dependencies ) {
foreach ( $dependencies as $d ) {
$output[] = [ $d => $name ];
}
}
return $output;
}
}
/**
* @deprecated since 1.7
*/
class TSNode {
public $name;
public $children = [];
public $parents = [];
public function __construct( $name = '' ) {
if ( !is_string( $name ) ) {
throw new \InvalidArgumentException( 'Name needs to be a string' );
}
$this->name = $name;
}
}
|
