Skip to content

Instantly share code, notes, and snippets.

@uupaa
Last active August 29, 2015 14:10
Show Gist options
  • Save uupaa/ad495d35af90a4859e2c to your computer and use it in GitHub Desktop.
Save uupaa/ad495d35af90a4859e2c to your computer and use it in GitHub Desktop.
solve the module dependency tree.
// モジュールリスト
    var list = [
      "nodemodule",
      "console",
      "valid",
      "help",
      "task",
      "test",
      "lv3",
      "reflection"
    ];

// モジュール依存性ツリー(package.jsonから収集)
    var tree = {
      "nodemodule": {},    // 依存関係なし
      "console": {},       // 他のモジュール(help)が参照している
      "valid": {
        "reflection": {},  // [1] reflection が valid より前に必要
        "help": {          // [2] help が valid より前に必要
          "lv3": {         // [8] lv3 が help や valid の前に必要
          }
        }
      },
      "help": {
        "reflection": {},  // [3] reflection が help より前に必要
        "console": {}      // [4] console が help より前に必要
      },
      "task": {
        "valid": {}        // [5] valid が task より前に必要
      },
      "test": {
        "valid": {},       // [6] valid が test より前に必要
        "task": {}         // [7] task が test より前に必要
      },
      "reflection": {},    // 他のモジュール(valid, help)が参照している
    };
// モジュール間の依存関係を解決したモジュールリストを取得する
var solvedModuleList = NodeModule_sortModuleListByDependencyOrder(list, tree);


solvedModuleList: [
      "nodemodule",
      "console",            // [4]
      "reflection",         // [1][3]
      "lv3",                // [8]
      "help",               // [2]
      "valid",              // [5][6]
      "task",               // [7]
      "test",
    ]
function NodeModule_sortModuleListByDependencyOrder(list,   // @arg ModuleNameStringArray - [moduleName, ...]
                                                    tree) { // @arg Object - module dependency tree. { moduleName: { subModuleName, ... }, ... }
                                                            // @ret ModuleNameStringArray - sorted new array. 
    var verbose = NodeModule["verbose"] || false;

    if (verbose) { console.log("list: " + JSON.stringify(list, null, 2)); }
    if (verbose) { console.log("tree: " + JSON.stringify(tree, null, 2)); }

    var pathList = _makePathList([], "", tree);

    for (var i = 0, iz = pathList.length; i < iz; ++i) {
        var path = pathList[i];
        var modules = path.split("/").slice(1); // "/a/b" -> ["a", "b"]

        for (var j = 0, jz = modules.length - 1; j < jz; ++j) {
            var moduleA = modules[j];
            var moduleB = modules[j + 1];
            var posA = list.indexOf(moduleA);
            var posB = list.indexOf(moduleB);

            if (posA >= 0 && posB >= 0) {
                if (posA < posB) { // moduleA need moduleB.
                    // move the mobuleB to before mobuleA.
                    list.splice(posB, 1); // Remove the moduleB,
                    list.splice(posA, 0, moduleB); // and injecting it to before moduleA.
                }
            }
        }
    }
    return list;
}

function _makePathList(result, dir, subtree) {
    for (var key in subtree) {
        var path = dir + "/" + key;

        result.push(path);
        _makePathList(result, path, subtree[key]);
    }
    return result;
}
console.log("pathList: " + JSON.stringify(pathList, null, 2)); 

pathList:  [
  "/nodemodule",
  "/console",
  "/valid/reflection",
  "/valid/help/lv3",
  "/valid/help",
  "/valid",
  "/help/reflection",
  "/help/console",
  "/help",
  "/task/valid",
  "/task",
  "/test/valid",
  "/test/task",
  "/test",
  "/reflection"
] 
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment