Skip to content

Instantly share code, notes, and snippets.

@dhkatz
Created June 23, 2019 21:36
Show Gist options
  • Save dhkatz/1203cad9d017aec6ec8ab71703d10c0a to your computer and use it in GitHub Desktop.
Save dhkatz/1203cad9d017aec6ec8ab71703d10c0a to your computer and use it in GitHub Desktop.
Directed Graph Execution Order in Lua
local ____symbolMetatable = {__tostring = function(self)
if self.description == nil then
return "Symbol()"
else
return "Symbol(" .. tostring(self.description) .. ")"
end
end}
function __TS__Symbol(description)
return setmetatable({description = description}, ____symbolMetatable)
end
Symbol = {
iterator = __TS__Symbol("Symbol.iterator"),
hasInstance = __TS__Symbol("Symbol.hasInstance"),
species = __TS__Symbol("Symbol.species"),
toStringTag = __TS__Symbol("Symbol.toStringTag"),
}
function __TS__InstanceOf(obj, classTbl)
if type(classTbl) ~= "table" then
error("Right-hand side of \'instanceof\' is not an object")
end
if classTbl[Symbol.hasInstance] ~= nil then
return not not classTbl[Symbol.hasInstance](classTbl, obj)
end
if obj ~= nil then
local luaClass = obj.constructor
while luaClass ~= nil do
if luaClass == classTbl then
return true
end
luaClass = luaClass.____super
end
end
return false
end
function __TS__Iterator(iterable)
if iterable[Symbol.iterator] then
local iterator = iterable[Symbol.iterator](iterable)
return function()
local result = iterator:next()
if not result.done then
return result.value
else
return nil
end
end
else
local i = 0
return function()
i = i + 1
return iterable[i]
end
end
end
Set = (function()
Set = {}
Set.name = "Set"
Set.__index = Set
Set.prototype = {}
Set.prototype.__index = Set.prototype
Set.prototype.constructor = Set
function Set.new(...)
local self = setmetatable({}, Set.prototype)
self:____constructor(...)
return self
end
function Set.prototype.____constructor(self, values)
self[Symbol.toStringTag] = "Set"
self.items = {}
self.size = 0
if values == nil then
return
end
local iterable = values
if iterable[Symbol.iterator] then
local iterator = iterable[Symbol.iterator](iterable)
while true do
local result = iterator:next()
if result.done then
break
end
self:add(result.value)
end
else
local array = values
self.size = #array
for ____, value in ipairs(array) do
self.items[value] = true
end
end
end
function Set.prototype.add(self, value)
if not self:has(value) then
self.size = self.size + 1
end
self.items[value] = true
return self
end
function Set.prototype.clear(self)
self.items = {}
self.size = 0
return
end
function Set.prototype.delete(self, value)
local contains = self:has(value)
if contains then
self.size = self.size - 1
end
self.items[value] = nil
return contains
end
function Set.prototype.forEach(self, callback)
for key in pairs(self.items) do
callback(_G, key, key, self)
end
end
function Set.prototype.has(self, value)
return self.items[value] == true
end
Set.prototype[Symbol.iterator] = function(self)
return self:values()
end
function Set.prototype.entries(self)
local items = self.items
local key
return {
[Symbol.iterator] = function(self)
return self
end,
next = function(self)
key = next(items, key)
return {
done = not key,
value = {
key,
key,
},
}
end,
}
end
function Set.prototype.keys(self)
local items = self.items
local key
return {
[Symbol.iterator] = function(self)
return self
end,
next = function(self)
key = next(items, key)
return {
done = not key,
value = key,
}
end,
}
end
function Set.prototype.values(self)
local items = self.items
local key
return {
[Symbol.iterator] = function(self)
return self
end,
next = function(self)
key = next(items, key)
return {
done = not key,
value = key,
}
end,
}
end
Set[Symbol.species] = Set
return Set
end)()
function __TS__ArrayPush(arr, ...)
local items = ({...})
for ____, item in ipairs(items) do
arr[#arr + 1] = item
end
return #arr
end
function __TS__ObjectKeys(obj)
local result = {}
for key in pairs(obj) do
result[#result + 1] = key
end
return result
end
function __TS__ArrayForEach(arr, callbackFn)
do
local i = 0
while i < #arr do
callbackFn(_G, arr[i + 1], i, arr)
i = i + 1
end
end
end
function __TS__ArrayIndexOf(arr, searchElement, fromIndex)
local len = #arr
if len == 0 then
return -1
end
local n = 0
if fromIndex then
n = fromIndex
end
if n >= len then
return -1
end
local k
if n >= 0 then
k = n
else
k = len + n
if k < 0 then
k = 0
end
end
do
local i = k
while i < len do
if arr[i + 1] == searchElement then
return i
end
i = i + 1
end
end
return -1
end
function __TS__ArrayFilter(arr, callbackfn)
local result = {}
do
local i = 0
while i < #arr do
if callbackfn(_G, arr[i + 1], i, arr) then
result[#result + 1] = arr[i + 1]
end
i = i + 1
end
end
return result
end
function __TS__ArrayUnshift(arr, ...)
local items = ({...})
do
local i = #items - 1
while i >= 0 do
table.insert(arr, 1, items[i + 1])
i = i - 1
end
end
return #arr
end
Vertex = {}
Vertex.name = "Vertex"
Vertex.__index = Vertex
Vertex.prototype = {}
Vertex.prototype.__index = Vertex.prototype
Vertex.prototype.constructor = Vertex
function Vertex.new(...)
local self = setmetatable({}, Vertex.prototype)
self:____constructor(...)
return self
end
function Vertex.prototype.____constructor(self, graph)
self.name = nil
self.graph = graph
self.edges = {
from = Set.new(),
to = Set.new(),
}
end
function Vertex.prototype.edge(self, node)
local ____ = self.edges
local from = ____.from
local ____ = node.edges
local to = ____.to
for edge in __TS__Iterator(to:values()) do
if edge.to == self then
return edge
end
end
local edge = Edge.new(self, node)
to:add(edge)
from:add(edge)
self.graph.edges:add(edge)
return edge
end
Edge = {}
Edge.name = "Edge"
Edge.__index = Edge
Edge.prototype = {}
Edge.prototype.__index = Edge.prototype
Edge.prototype.constructor = Edge
function Edge.new(...)
local self = setmetatable({}, Edge.prototype)
self:____constructor(...)
return self
end
function Edge.prototype.____constructor(self, from, to)
self.from = from
self.to = to
self.graph = from.graph or to.graph
end
function Edge.prototype.remove(self)
self.graph.edges:delete(self)
self.to.edges.to:delete(self)
self.from.edges.from:delete(self)
end
Digraph = {}
Digraph.name = "Digraph"
Digraph.__index = Digraph
Digraph.prototype = {}
Digraph.prototype.__index = Digraph.prototype
Digraph.prototype.constructor = Digraph
function Digraph.new(...)
local self = setmetatable({}, Digraph.prototype)
self:____constructor(...)
return self
end
function Digraph.prototype.____constructor(self)
self.nodes = {}
self.edges = Set.new()
self.cache = {}
end
function Digraph.prototype.node(self, node)
if type(node) == "string" then
local cached = self.cache[node]
if not cached then
local created = Vertex.new(self)
created.name = node
self.cache[node] = created
__TS__ArrayPush(self.nodes, created)
end
return self.cache[node]
end
if node.name ~= nil then
local cached = self.cache[node.name]
if cached then
__TS__ArrayForEach(__TS__ObjectKeys(node), function(____, key) return (function(o, i, v)
o[i] = v
return v
end)(cached, key, node[key]) end)
else
self.cache[node.name] = node
__TS__ArrayPush(self.nodes, node)
end
return self.cache[node.name]
else
local index = __TS__ArrayIndexOf(self.nodes, node)
if index == -1 then
__TS__ArrayPush(self.nodes, node)
return node
else
return self.nodes[index + 1]
end
end
end
function Digraph.prototype.sort(self)
local L = {}
local S = __TS__ArrayFilter(self.nodes, function(____, n) return n.edges.to.size == 0 end)
while #S > 0 do
local n = table.remove(S)
__TS__ArrayPush(L, n)
for e in __TS__Iterator(n.edges.from) do
local m = e.to
e:remove()
if m.edges.to.size == 0 then
__TS__ArrayUnshift(S, m)
end
end
end
if self.edges.size > 0 then
error("Could not create topological sort due to circular dependecies!")
else
return L
end
end
local a = {
name = "a",
dependecies = {},
}
local b = {
name = "b",
dependecies = {"a"},
}
local c = {
name = "c",
dependecies = {
"a",
"b",
},
}
local packages = {
b,
c,
a,
}
local G = Digraph.new()
for ____, pkg in ipairs(packages) do
local node = G:node(pkg.name)
for ____, dependecy in ipairs(pkg.dependecies) do
G:node(dependecy):edge(node)
end
end
for ____, pkg in ipairs(G:sort()) do
print(pkg.name)
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment