如何遞歸檢查包含其他依賴項的文件包含依賴項的數組？

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