[TASK] Adjust position of unrelated items in ordered list 00/41000/2
authorMarkus Klein <markus.klein@typo3.org>
Wed, 8 Jul 2015 14:16:06 +0000 (16:16 +0200)
committerWouter Wolters <typo3@wouterwolters.nl>
Wed, 8 Jul 2015 17:44:21 +0000 (19:44 +0200)
Items without any dependency relation are output to the very end
of the order list by DependencyOrderService.

Resolves: #67986
Releases: master
Change-Id: I4d3968cd41fc274fbda658d0563d6f535e36e2ff
Reviewed-on: http://review.typo3.org/41000
Reviewed-by: Christian Kuhn <lolli@schwarzbu.ch>
Tested-by: Christian Kuhn <lolli@schwarzbu.ch>
Reviewed-by: Wouter Wolters <typo3@wouterwolters.nl>
Tested-by: Wouter Wolters <typo3@wouterwolters.nl>
typo3/sysext/core/Classes/Service/DependencyOrderingService.php
typo3/sysext/core/Documentation/Changelog/master/Feature-67293-DependencyOrderingService.rst
typo3/sysext/core/Tests/Unit/Service/DependencyOrderingServiceTest.php

index ef7714b..2180746 100644 (file)
@@ -130,22 +130,41 @@ class DependencyOrderingService {
         * @throws \UnexpectedValueException
         */
        public function calculateOrder(array $dependencyGraph) {
-               $rootIds = $this->findRootIds($dependencyGraph);
+               $rootIds = array_flip($this->findRootIds($dependencyGraph));
 
-               // This will contain our final result
+               // Add number of dependencies for each root node
+               foreach ($rootIds as $id => &$dependencies) {
+                       $dependencies = count(array_filter($dependencyGraph[$id]));
+               }
+               unset($dependencies);
+
+               // This will contain our final result in reverse order,
+               // meaning a result of [A, B, C] equals "A after B after C"
                $sortedIds = [];
 
-               // Walk through the graph
+               // Walk through the graph, level by level
                while (!empty($rootIds)) {
-                       $currentId = array_shift($rootIds);
+                       ksort($rootIds);
+                       // We take those with fewer dependencies first, to have them at the end of the list in the final result.
+                       $minimum = PHP_INT_MAX;
+                       $currentId = 0;
+                       foreach ($rootIds as $id => $count) {
+                               if ($count <= $minimum) {
+                                       $minimum = $count;
+                                       $currentId = $id;
+                               }
+                       }
+                       unset($rootIds[$currentId]);
+
                        array_push($sortedIds, $currentId);
 
+                       // Process the dependencies of the current node
                        foreach (array_filter($dependencyGraph[$currentId]) as $dependingId => $_) {
                                // Remove the edge to this dependency
                                $dependencyGraph[$currentId][$dependingId] = FALSE;
                                if (!$this->getIncomingEdgeCount($dependencyGraph, $dependingId)) {
-                                       // We found a new root, lets add it
-                                       array_unshift($rootIds, $dependingId);
+                                       // We found a new root, lets add it to the list
+                                       $rootIds[$dependingId] = count(array_filter($dependencyGraph[$dependingId]));
                                }
                        }
                }
@@ -188,6 +207,9 @@ class DependencyOrderingService {
        /**
         * Find all root nodes of a graph
         *
+        * Root nodes are those, where nothing else depends on (they can be the last in the loading order).
+        * If there are no dependencies at all, all nodes are root nodes.
+        *
         * @param bool[][] $dependencyGraph
         * @return array List of identifiers which are root nodes
         */
index 4c426d0..d70e6c6 100644 (file)
@@ -39,3 +39,5 @@ Example usage:
 ``$sortedHooks`` will then contain the content of ``$hooks``, but sorted according to the dependencies.
 
 The ``DependencyOrderingService`` class also detects cycles in the dependencies and will throw an Exception in case conflicting dependencies were defined.
+
+In case the initial list does not specify a dependency for an item, those items will be put last in the final sorted list.
index 6c27ad2..7cdb078 100644 (file)
@@ -28,10 +28,12 @@ class DependencyOrderingServiceTest extends UnitTestCase {
         * @test
         * @dataProvider orderByDependenciesBuildsCorrectOrderDataProvider
         * @param array $items
+        * @param string $beforeKey
+        * @param string $afterKey
         * @param array $expectedOrderedItems
         */
        public function orderByDependenciesBuildsCorrectOrder(array $items, $beforeKey, $afterKey, array $expectedOrderedItems) {
-               $orderedItems = (new DependencyOrderingService())->orderByDependencies($items);
+               $orderedItems = (new DependencyOrderingService())->orderByDependencies($items, $beforeKey, $afterKey);
                $this->assertSame($expectedOrderedItems, $orderedItems);
        }
 
@@ -48,8 +50,8 @@ class DependencyOrderingServiceTest extends UnitTestCase {
                                'before',
                                'after',
                                [ // $expectedOrderedItems
-                                       2 => [],
                                        1 => [],
+                                       2 => [],
                                ]
                        ],
                        'ordered' => [
@@ -81,13 +83,13 @@ class DependencyOrderingServiceTest extends UnitTestCase {
                                'before',
                                'after',
                                [ // $expectedOrderedItems
-                                       3 => [
-                                               'otherProperty' => TRUE
-                                       ],
                                        2 => [
                                                'before' => [ 1 ]
                                        ],
                                        1 => [],
+                                       3 => [
+                                               'otherProperty' => TRUE
+                                       ],
                                ]
                        ],
                        'reference to non-existing' => [