class-auxels-admin-assets.php
1 year ago
class-auxels-archive-menu-links.php
1 year ago
class-auxels-envato-elements.php
1 year ago
class-auxels-import-parser.php
3 years ago
class-auxels-import.php
3 years ago
class-auxels-search-post-type.php
6 months ago
class-auxels-wc-attribute-nav-menu.php
1 year ago
class-auxin-admin-dashboard.php
1 year ago
class-auxin-demo-importer.php
6 months ago
class-auxin-dependency-sorting.php
3 years ago
class-auxin-import.php
1 year ago
class-auxin-install.php
1 year ago
class-auxin-master-nav-menu-admin.php
1 year ago
class-auxin-page-template.php
1 year ago
class-auxin-permalink.php
1 year ago
class-auxin-plugin-requirements.php
3 years ago
class-auxin-post-type-base.php
1 year ago
class-auxin-svg-support-allowedattributes.php
7 years ago
class-auxin-svg-support-allowedtags.php
7 years ago
class-auxin-svg-support.php
1 year ago
class-auxin-walker-nav-menu-back.php
1 year ago
class-auxin-welcome-sections.php
1 year ago
class-auxin-welcome.php
6 months ago
class-auxin-whitelabel.php
3 years ago
class-auxin-widget-indie.php
1 year ago
class-auxin-widget-shortcode-map.php
11 months ago
class-auxin-widget.php
1 year ago
class-auxin-dependency-sorting.php
84 lines
| 1 | <?php |
| 2 | |
| 3 | /** |
| 4 | * Dependency sorting/resolution algorithm for PHP |
| 5 | * |
| 6 | */ |
| 7 | class Auxin_Dependency_Sorting { |
| 8 | |
| 9 | /** |
| 10 | * The sorted list of dependency graph items |
| 11 | * |
| 12 | * @var array |
| 13 | */ |
| 14 | public $sorted = array(); |
| 15 | |
| 16 | /** |
| 17 | * Stores the list of checked nodes in dependency graph |
| 18 | * |
| 19 | * @var array |
| 20 | */ |
| 21 | protected $checked = array(); |
| 22 | |
| 23 | /** |
| 24 | * Stores the input dependency graph |
| 25 | * |
| 26 | * @var array |
| 27 | */ |
| 28 | protected $graph = array(); |
| 29 | |
| 30 | |
| 31 | public function __construct(){} |
| 32 | |
| 33 | /** |
| 34 | * Check and sort dependencies for each node |
| 35 | * |
| 36 | * @param string $name The node name |
| 37 | * @param array $ancestors The nodes that are already collected |
| 38 | * @return void |
| 39 | */ |
| 40 | private function node_check( $name, $ancestors = array() ){ |
| 41 | $ancestors = (array) $ancestors; |
| 42 | |
| 43 | $ancestors[] = $name; |
| 44 | $this->checked[ $name ] = true; |
| 45 | |
| 46 | // sometimes a dependency is not in main nodes list |
| 47 | if( isset( $this->graph[ $name ] ) ){ |
| 48 | |
| 49 | foreach ( $this->graph[ $name ] as $dependency ) { |
| 50 | if( in_array( $dependency, $ancestors) ){ |
| 51 | throw new Exception( "Circular dependency for following node detected: " . $name ); |
| 52 | } |
| 53 | if( isset( $this->checked[ $dependency ] ) ){ |
| 54 | continue; |
| 55 | } |
| 56 | $this->node_check( $dependency, $ancestors ); |
| 57 | } |
| 58 | |
| 59 | } |
| 60 | |
| 61 | if( ! in_array( $name, $this->sorted ) ){ |
| 62 | $this->sorted[] = $name; |
| 63 | } |
| 64 | } |
| 65 | |
| 66 | /** |
| 67 | * Sorts and retrieves the list of sorted items based on defined dependencies |
| 68 | * |
| 69 | * @param array $graph The list of items and their dependencies |
| 70 | * @return array The sorted list of items based on defined dependencies |
| 71 | */ |
| 72 | public function resolve( $graph ) { |
| 73 | $this->graph = $graph; |
| 74 | |
| 75 | foreach ( $this->graph as $main_node => $ancestors) { |
| 76 | $this->node_check( $main_node ); |
| 77 | } |
| 78 | |
| 79 | return $this->sorted; |
| 80 | } |
| 81 | |
| 82 | } |
| 83 | |
| 84 |