-1

LIST: controller name => priority:required controllers

$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:

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:

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:

  1. Remove infinite loop controllers (ex: controller_loopexit1 & controller_loopexit2)
  2. Remove controllers that have a dependency of a controller that doesn`t exist (ex: controller_x depending on controller_not_exists.)
  3. Sort remaining items by priority number, lowest comes first
  4. Second sort by dependencies
Improve this question
7
  • Your input contains 7 items, your output only 4? How is "priority" defined? Commented May 6, 2021 at 5:22
  • Yes, that is correct, if the required controllers aren't met, then the item is removed Commented May 6, 2021 at 5:23
  • 1
    What you need is a topological sort. I answered a similar question here for dependencies which should get you started. Only additional thing you would have to add at the end is sort by priority. stackoverflow.com/questions/67219177/… Commented May 6, 2021 at 5:28
  • This should also help. Commented May 6, 2021 at 5:29
  • 1
    You have 2 independent problems here: 1) Removing the cycles 2) Sorting. You shouldn't mix 2 problems in the same question. Commented May 11, 2021 at 7:42

1 Answer 1

Reset to default
1
+50

Code:

<?php

include 'vendor/autoload.php';

class TheSortedControllers{

    private $inputControllerList = [];
    private $inputControllerMap = [];
    private $sorter = null;

    function __construct($inputControllerList){
        $this->inputControllerList = $inputControllerList;
        $this->sorter = new \MJS\TopSort\Implementations\StringSort();
    }

    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:

  1. 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.
  2. 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):

$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:

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):

$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:

Message: Circular dependency found: controller_loopexit1->controller_loopexit2->controller_loopexit1

Case 3

Input (Removed the controllers with circular dependency):

$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:

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):

$controllersList =  array(
    "controller_3" => "3",
    "controller_1" => "1:controller_2",
    "controller_2" => "2",
    "controller_4" => "1:controller_2&controller_1",
);

Output:

Array
(
    [0] => controller_2
    [1] => controller_1
    [2] => controller_4
    [3] => controller_3
)
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.