TYPO3CMS  8
 All Classes Namespaces Files Functions Variables Pages
DependencyOrderingService Class Reference

Public Member Functions

 orderByDependencies (array $items, $beforeKey= 'before', $afterKey= 'after')
 
 calculateOrder (array $dependencyGraph)
 
 findRootIds (array $dependencyGraph)
 

Protected Member Functions

 getIncomingEdgeCount (array $dependencyGraph, $identifier)
 
 findPathInGraph (array $graph, $from, $to)
 
 prepareDependencies (array $dependencies, $beforeKey= 'before', $afterKey= 'after')
 

Detailed Description

This class provides functionality to build an ordered list from a set of dependencies.

We use an adjacency matrix for the dependency graph (DAG)

Example structure of the DAG is: A => (A => FALSE, B => TRUE, C => FALSE) B => (A => FALSE, B => FALSE, C => FALSE) C => (A => TRUE, B => FALSE, C => FALSE)

A depends on B, C depends on A, B is independent

Definition at line 30 of file DependencyOrderingService.php.

Member Function Documentation

calculateOrder ( array  $dependencyGraph)

Calculate an ordered list for a dependencyGraph

Parameters
bool[][]$dependencyGraph
Returns
mixed[] Sorted array of keys of $dependencies
Exceptions
UnexpectedValueException

Definition at line 132 of file DependencyOrderingService.php.

References DependencyOrderingService\findRootIds(), and DependencyOrderingService\getIncomingEdgeCount().

Referenced by DependencyOrderingService\orderByDependencies().

findPathInGraph ( array  $graph,
  $from,
  $to 
)
protected

Find any path in the graph from given start node to destination node

Parameters
array$graphDirected graph
string$fromStart node
string$toDestination node
Returns
array Nodes of the found path; empty if no path is found

Definition at line 238 of file DependencyOrderingService.php.

findRootIds ( array  $dependencyGraph)

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.

Parameters
bool[][]$dependencyGraph
Returns
array List of identifiers which are root nodes

Definition at line 218 of file DependencyOrderingService.php.

References DependencyOrderingService\getIncomingEdgeCount().

Referenced by DependencyOrderingService\calculateOrder().

getIncomingEdgeCount ( array  $dependencyGraph,
  $identifier 
)
protected

Get the number of incoming edges in the dependency graph for given identifier

Parameters
array$dependencyGraph
string$identifier
Returns
int

Definition at line 198 of file DependencyOrderingService.php.

Referenced by DependencyOrderingService\calculateOrder(), and DependencyOrderingService\findRootIds().

orderByDependencies ( array  $items,
  $beforeKey = 'before',
  $afterKey = 'after' 
)

Order items by specified dependencies before/after

The dependencies of an items are specified as: 'someItemKey' => [ 'before' => ['someItemKeyA', 'someItemKeyB'] 'after' => ['someItemKeyC'] ]

If your items use different keys for specifying the relations, you can define the appropriate keys by setting the $beforeKey and $afterKey parameters accordingly.

Parameters
array$items
string$beforeKeyThe key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'
string$afterKeyThe key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'
Returns
array
Exceptions
UnexpectedValueException

Definition at line 50 of file DependencyOrderingService.php.

References DependencyOrderingService\calculateOrder().

prepareDependencies ( array  $dependencies,
  $beforeKey = 'before',
  $afterKey = 'after' 
)
protected

Prepare dependencies

Ensure that all discovered identifiers are added to the dependency list so we can reliably use the identifiers to build the matrix. Additionally fix all invalid or missing before/after arrays

Parameters
array$dependencies
string$beforeKeyThe key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'
string$afterKeyThe key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'
Returns
array Prepared dependencies

Definition at line 266 of file DependencyOrderingService.php.