如何递归检查文件数组是否包含其他依赖项的依赖项？

Question

为了解释我的问题，让我首先指出这个数组：

<?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"
    )
);
?>

每当包含 JavaScript 文件时，都会根据这个数组检查它的依赖关系。然后，每个文件的所有依赖项都会添加到最终的$includes 数组中。当我添加包含依赖项的包含项并且其中一个依赖项也有自己的依赖项时，问题就出现了，例如：

<?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"
    )
);
?>

如您所见，添加的 '/Script/UI/Calendar/Main.js'依赖于 "/Script/UI/Dialogs.js" ，它有自己的依赖项。

我知道我必须递归地检查依赖项数组和最终包含数组，但我似乎无法理解逻辑。这里的一点帮助可能会很好。

更新

我将所有内容包装在一个类中以说明其目的（尽管实际的类要复杂得多并且具有各种其他包含处理功能：

<?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;
    }
}
?>

Answer 1

您正在寻找的函数称为展平。它采用递归列表并返回每个级别的所有元素。

这里的注释中有一些php的实现： http://php.net /manual/en/function.array-values.php

以下是 javascript 中的实现：http://tech.karbassi.com/2009/12/17/pure-javascript-flatten-array/

Answer 2

试试这个：

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

这基本上实现了 Artefacto 描述的算法。

Answer 3

看看这是否有效——对你的函数进行一个小修改。

（顺便说一句，由于您的命名约定，它令人费解： $includes、$include、$this->_includes 和 $this->includes()！建议您使用更好的名称。我已将函数重命名为calculate_includes ，但你也应该清理其他的。）

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;
    }

Answer 4

• 保留一个堆栈，最初包含您的初始依赖项 (stack)
• 保留一个包含所有（传递）依赖项的空数组 (deps)
• 虽然堆栈不是 空
  • 弹出最后一个元素 (el)
  • 将el添加到deps
  • 循环遍历 el 的依赖项
    • 如果依赖项位于 deps 中，则不执行任何操作
    • 否则，将推送到堆栈