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