How can I recursively check an array of file include dependencies for other dependencies?
To explain my question, let me first point to this array:
<?php
$_depends = array(
'/Scripting/jquery.hyponiqs/jquery.dropdown.js' => array(
"/Scripting/jquery.externals/jquery.resize.js",
"/Scripting/jquery.externals/jquery.topzindex.js",
"/Scripting/jquery.externals/jquery.timers.js",
"/Scripting/jquery-ui.min.js",
"/Scripting/jquery.hyponiqs/hyponiqs.core.js",
),
'/Script/UI/Dialogs.js' => array(
"/Scripting/jquery.externals/jquery.resize.js",
"/Scripting/jquery.externals/jquery.topzindex.js"
),
'/Script/Display/List.js' => array(
"/Scripting/jquery.externals/jquery.timers.js"
)
);
?>
Whenever a JavaScript file is included, it is checked against this array for dependencies. All the dependencies for each file are then added to the final $includes
array. The problem comes when I add an include with dependencies and one of those dependencies also has its own dependencies, such as:
<?php
$_depends = array(
'/Scripting/jquery.hyponiqs/jquery.dropdown.js' => array(
"/Scripting/jquery.externals/jquery.resize.js",
"/Scripting/jquery.externals/jquery.topzindex.js",
"/Scripting/jquery.externals/jquery.timers.js",
"/Scripting/jquery-ui.min.js",
"/Scripting/jquery.hyponiqs/hyponiqs.core.js",
),
'/Script/UI/Dialogs.js' => array(
"/Scripting/jquery.externals/jquery.resize.js",
"/Scripting/jquery.externals/jquery.topzindex.js"
),
'/Script/Display/List.js' => array(
"/Scripting/jquery.externals/jquery.timers.js"
),
'/Script/UI/Calendar/Main.js' => array(
"/Scripting/jquery-ui.min.js",
"/Script/UI/Dialogs.js"
)
);
?>
As you can see, the added '/Script/UI/Calendar/Main.js'
depends on "/Script/UI/Dialogs.js"
which has its own dependencies.
I know that I would have to recursively check the dependency array and final includes array, but I can't seem to wrap my head around the logic. A little help here might be nice.
UPDATE
I wrapped everything in a class to illustrate its purpose (although the actual class is much more complicated and has various other include-handling functionality:
<?php
class Script_Depends {
private $_includes = array();
private $_depends = array(
'/Scripting/jquery.hyponiqs/jquery.dropdown.js' => array(
"/Scripting/jquery.externals/jquery.resize.js",
"/Scripting/jquery.externals/jquery.topzindex.js",
"/Scripting/jquery.externals/jquery.timers.js",
"/Scripting/jquery-ui.min.js",
"/Scripting/jquery.hyponiqs/hyponiqs.core.js",
),
'/Script/UI/Dialogs.js' => array(
开发者_开发技巧 "/Scripting/jquery.externals/jquery.resize.js",
"/Scripting/jquery.externals/jquery.topzindex.js"
),
'/Script/Display/List.js' => array(
"/Scripting/jquery.externals/jquery.timers.js"
),
'/Script/UI/Calendar/Main.js' => array(
"/Script/UI/Dialogs.js",
"/Scripting/jquery-ui.min.js"
)
);
public function includes($includes)
{
if (is_string($includes)) $includes = array($includes);
foreach ($includes as $include) {
if (isset($this->_depends[$include])) {
$this->_includes = $this->includes($this->_depends[$include]);
array_push($this->_includes, $include);
}
else {
array_push($this->_includes, $include);
}
}
$this->_includes = array_unique($this->_includes);
return $this->_includes;
}
}
?>
- Keep a stack, initially with your initial dependencies (
stack
) - Keep an empty array with all the (transitive) dependencies (
deps
) - While stack is not empty
- pop the last element (
el
) - add
el
todeps
- loop through the dependencies of
el
- if the dependency is in
deps
, do nothing - otherwise, push it to
stack
- if the dependency is in
- pop the last element (
The function you are looking for is called flatten. It takes a recursive list and returns all of the elements at every level.
There are some implementations in php in the comments here: http://php.net/manual/en/function.array-values.php
Here is an implementation in javascript: http://tech.karbassi.com/2009/12/17/pure-javascript-flatten-array/
Try this:
function getDependentFiles($file, $dependencies) {
$fileIndex = array();
$queue = array($file);
while (count($queue)) {
$f = array_shift($queue);
if (!isset($fileIndex[$f])) {
if (array_key_exists($f, $dependencies) && is_array($dependencies[$f])) {
$queue = array_merge($queue, $dependencies[$f]);
}
$fileIndex[$f] = true;
}
}
return array_keys($fileIndex);
}
var_dump(getDependentFiles('/Script/UI/Calendar/Main.js', $_depends));
This basically implements the algorithm described by Artefacto.
See if this does the trick -- a small mod to your function.
(BTW it is mind-bending because of your naming conventions: $includes, $include, $this->_includes and $this->includes()!! Suggest you use better names. I've renamed the function to calculate_includes, but you should clean up the others too.)
public function calculate_includes($includes) {
foreach ((array)$includes as $include) {
if(in_array($include, $this->_includes)) continue;
if (isset($this->_depends[$include])) {
$this->_includes = $this->calculate_includes($this->_depends[$include]);
} else {
array_push($this->_includes, $include);
}
}
$this->_includes = array_unique($this->_includes);
return $this->_includes;
}
精彩评论