Как я могу рекурсивно проверить массив включаемых зависимостей для других зависимостей?

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

• Держите стек, изначально с вашими начальными зависимостями (stack)
• Сохранить пустой массив со всеми (транзитивными) зависимостями (deps)
• Пока стек не пуст
  • pop последний элемент (el)
  • добавить el к deps
  • перебирает зависимости el
    • если зависимость в deps, ничего не делать
    • в противном случае нажмите на stack

Answer 2

Посмотрите, поможет ли это - небольшой мод для вашей функции.

(Кстати, это изнурительно из-за ваших соглашений об именах: $ include, $ include, $ this -> _ includes и $ this-> includes () !! Предлагаю вам использовать более подходящие имена. Я переименовал функцию в Calculate_include, но вы должны очистить и другие.)

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

Функция, которую вы ищете, называется flatten.Он принимает рекурсивный список и возвращает все элементы на каждом уровне.

В комментариях есть несколько реализаций в php: http://php.net/manual/en/function.array-values.php

Вот реализация в javascript: http://tech.karbassi.com/2009/12/17/pure-javascript-flatten-array/