LIST: controller name => priority:required controllers
JavaScript
x
$array(
"controller_3" => "3",
"controller_1" => "1:controller_2",
"controller_2" => "2",
"controller_4" => "1:controller_2&controller_1",
"controller_x" => "2:controller_not_exists",
"controller_loopexit1" => "4:controller_loopexit2",
"controller_loopexit2" => "5:controller_loopexit1"
)
sorted and expected output:
JavaScript
controller_2
controller_1
controller_4
controller_3
First sort by priority, then reorder based on required controllers to be loaded before. ensure not to be stuck in an infinite loop due to controllers requiring each other.
I assume I’ll need something like this:
JavaScript
function cmp($a, $b) {
if ($a == $b) {
return 0;
}
return ($a < $b) ? -1 : 1;
}
uasort($controllers_array, 'cmp');
Please help solve this with these steps:
- Remove infinite loop controllers (ex: controller_loopexit1 & controller_loopexit2)
- Remove controllers that have a dependency of a controller that doesn`t exist (ex: controller_x depending on controller_not_exists.)
- Sort remaining items by priority number, lowest comes first
- Second sort by dependencies
Advertisement
Answer
Code:
JavaScript
<?php
include 'vendor/autoload.php';
class TheSortedControllers{
private $inputControllerList = [];
private $inputControllerMap = [];
private $sorter = null;
function __construct($inputControllerList){
$this->inputControllerList = $inputControllerList;
$this->sorter = new MJSTopSortImplementationsStringSort();
}
function inputMapper(){
$controllersList = $this->inputControllerList;
foreach($controllersList as $controllerId=>$controllerData){
$controllerData = (explode(":",$controllerData));
$this->inputControllerMap[$controllerId]['priority'] = (int)$controllerData[0];
if(isset($controllerData[1])){
$this->inputControllerMap[$controllerId]['required'] = explode("&",$controllerData[1]);
}
}
}
function sortByPriority($a, $b)
{
return $a['priority'] - $b['priority'];
}
function sort(){
$this->inputMapper();
uasort($this->inputControllerMap, array($this, "sortByPriority"));
foreach($this->inputControllerMap as $controllerID=>$controllerData){
$required = $controllerData['required'] ?? [];
$this->sorter->add($controllerID, $required);
}
return $this->sorter->sort();
}
}
$controllersList = array(
"controller_3" => "3",
"controller_1" => "1:controller_2",
"controller_2" => "2",
"controller_4" => "1:controller_2&controller_1",
);
$theSortedControllers = new TheSortedControllers($controllersList);
try {
$outputControllersList = $theSortedControllers->sort();
print_r($outputControllersList);
} catch (Exception $e) {
echo 'Message: ' .$e->getMessage();
}
Usage:
- I am using https://github.com/marcj/topsort.php. To use it you
must have Composer. Run
composer require marcj/topsort
to install the code dependency. - That’s it. In case of an exception, the code does not automatically remove the nodes (controllers), it’s best to use human intervention to make sure you resolve those exceptions and have a proper input.
Examples:
Case 1
Input (Your Original Input – Missing Dependency):
JavaScript
$controllersList = array(
"controller_3" => "3",
"controller_1" => "1:controller_2",
"controller_2" => "2",
"controller_4" => "1:controller_2&controller_1",
"controller_x" => "2:controller_not_exists",
"controller_loopexit1" => "4:controller_loopexit2",
"controller_loopexit2" => "5:controller_loopexit1"
);
Output:
JavaScript
Message: Dependency `controller_not_exists` not found, required by `controller_x`
Case 2
Input (Add the missing dependency, you still have circular-dependency/infinite-loop):
JavaScript
$controllersList = array(
"controller_3" => "3",
"controller_1" => "1:controller_2",
"controller_2" => "2",
"controller_4" => "1:controller_2&controller_1",
"controller_x" => "2:controller_not_exists",
"controller_loopexit1" => "4:controller_loopexit2",
"controller_loopexit2" => "5:controller_loopexit1",
"controller_not_exists" => "10:controller_2",
);
Output:
JavaScript
Message: Circular dependency found: controller_loopexit1->controller_loopexit2->controller_loopexit1
Case 3
Input (Removed the controllers with circular dependency):
JavaScript
$controllersList = array(
"controller_3" => "3",
"controller_1" => "1:controller_2",
"controller_2" => "2",
"controller_4" => "1:controller_2&controller_1",
"controller_x" => "2:controller_not_exists",
"controller_not_exists" => "10:controller_2",
);
Output:
JavaScript
Array
(
[0] => controller_2
[1] => controller_1
[2] => controller_4
[3] => controller_not_exists
[4] => controller_x
[5] => controller_3
)
Case 4
Input (Removed controller_not_exists
and controller_x
):
JavaScript
$controllersList = array(
"controller_3" => "3",
"controller_1" => "1:controller_2",
"controller_2" => "2",
"controller_4" => "1:controller_2&controller_1",
);
Output:
JavaScript
Array
(
[0] => controller_2
[1] => controller_1
[2] => controller_4
[3] => controller_3
)