--[[ 
    Date: 2014-8-1
    Licence: MIT
    Author: <leoma@credosemi.com>
            <xfguo@credosemi.com>
]]

--[[
  module_relation table

  key   -- module name
  value -- depandences (those the module refers to)
]]

local module_relation = {
  ['a'] = { 'c' },
  ['b'] = { 'c' },
  ['c'] = { },
  ['d'] = { },
}

--[[
    Graph matrix

          deps

      a   b   c   d
  
  a   0   0   1   0
  
  b   0   0   1   0
  
  c   0   0   0   0

  d   0   0   0   0

]]

local module_relation = {
  ['a'] = { 'b', 'c' },
  ['b'] = { 'c' },
  ['c'] = { },
}

--[[
    Graph matrix

         deps

      a   b   c
  
  a   0   1   1
  
  b   0   0   1
  
  c   0   0   0

]]

local module_relation = {
  ['a'] = { },
  ['b'] = { 'a' },
  ['c'] = { 'a' },
  ['d'] = { 'b', 'c' },
}
--[[
       Graph matrix

          deps

      a   b   c   d
  
  a   0   1   1   0
  
  b   0   0   1   0
  
  c   0   0   0   0

  d   0   0   0   0

]]

local module_relation = {
  ['a'] = { 'b' },
  ['b'] = { 'c' },
  ['c'] = { 'd' },
  ['d'] = { 'a' },
  ['e'] = { 'a' },
}
--[[
       Graph matrix

          deps

      a   b   c   d   e
  
  a   0   1   0   0   0
  
  b   0   0   1   0   0
  
  c   0   0   0   1   0

  d   0   0   0   0   1

  e   1   0   0   0   0
]]


local modules = 0
local graph_matrix = {}
local reg_seq = {}

for mod, deps in pairs(module_relation) do
    for _, v in ipairs(deps) do
        if graph_matrix[v] == nil then graph_matrix[v] = {} end
        graph_matrix[v][mod] = true
    end
    modules = modules + 1
end

mod = next(module_relation)
while mod ~= nil do
    if graph_matrix[mod] == nil or next(graph_matrix[mod]) == nil then
        table.insert(reg_seq, mod)
        for k in pairs(graph_matrix) do
            graph_matrix[k][mod] = nil
        end
        module_relation[mod] = nil
        mod = next(module_relation)
    else
        mod = next(module_relation, mod)
    end
end

local function rev_tab(t)
    local i = 1
    local j = #t
    while i < j do
        local tmp = t[i]
        t[i] = t[j]
        t[j] = tmp
        i = i + 1
        j = j - 1
    end
    return t
end

-- Register sequence
print("Register sequence:", unpack(rev_tab(reg_seq)))

if #reg_seq ~= modules then
    error("There's reference loop relationship amang these modules!")
end