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

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"有其自己的依赖。

我知道我将不得不递归检查依赖数组和final包含数组，但我似乎无法将我的头围绕逻辑​​。这里有一点帮助可能会很好。

UPDATE

我在一类包裹的一切来说明它的目的（尽管实际的类要复杂得多，有各种其他包括处理功能：

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

• 保持堆栈， （stack）
• 保留具有所有（传递）依赖关系的空数组（deps）
• 虽然堆栈不empty
  • pop的最后一个元素（el）
  • 添加el到deps
  • 环通的el
    • 的依赖，如果依赖是indeps，什么也不做
    • 否则，push它到stack

Answer 2

你正在寻找被称为扁平化功能。它需要递归列表并返回每个级别的所有元素。

这里有一些在PHP实现的评论：http://php.net/manual/en/function.array-values.php

这是在JavaScript中实现：http://tech.karbassi.com/2009/12/17/pure-javascript-flatten-array/

Answer 3

试试这个：

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 4

看看这是否有窍门 - 对你的功能的一个小型修改。（顺便说一句，因为你的命名约定：$ 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; 
    }