-- This file:
--   http://angg.twu.net/LUA/DFS-old.lua.html
--   http://angg.twu.net/LUA/DFS-old.lua
--           (find-angg "LUA/DFS-old.lua")
-- Author: Eduardo Ochs <eduardoochs@gmail.com>
--
-- (defun e () (interactive) (find-angg "LUA/DFS-old.lua"))


DFS = Class {
  type = "DFS",
  new  = function ()
      return DFS {
        opened = SetL.new(),
        closed = SetL.new(),
	nodetok = Set.new(),
	ktonode = Set.new(),
        nodetoname = {},
        nodenames = Set.new(),
      }
    end,
  __index = {
    register = function (dfs, node)
        if not dfs.nodetok:has(node) then
          local k = rawtostring(node)
	  dfs.nodetok:add(node, k)
	  dfs.ktonode:add(k, node)
	end
	return dfs.nodetok:get(node)
      end,
    --
    rejecttarget = function (dfs, arrowname, tgt)
        local ot = otype(tgt)
        return ot == "Set" or ot == "SetL" or ot == "DFS"
      end,
    genarrows = function (dfs, o)
        local send = function (arrowname, tgt)
            if not dfs:rejecttarget(arrowname, tgt) then coy(arrowname, tgt) end
          end
        if type(o) == "table" then return cow(function ()
            for k,v in pairs(o) do
              if type(k) == "string" and type(v) == "table" then send(k, v) end
            end
            local mt = getmetatable(o)
            if type(mt) == "table" then send("__mt", mt) end
          end)
        end
      end,
    --
    isclosed = function (dfs, o) return dfs.closed:has(o) end,
    isopened = function (dfs, o) return dfs.opened:has(o) end,
    open  = function (dfs, o) dfs.opened:add(o) end,
    close = function (dfs, o) dfs.closed:add(o) end,
    recurse = function (dfs, o)
        if dfs:isclosed(o) then return end
        if dfs:isopened(o) then return end
        dfs:register(o)
	dfs:open(o)
	for arrowname,tgt in dfs:genarrows(o) do dfs:recurse(tgt) end
	dfs:close(o)
        return dfs
      end,
    --
    setdfsnumbers = function (dfs)
        dfs.openn  = Set.new()
        dfs.closen = Set.new()
        for i,node in ipairs(dfs.opened.list) do dfs.openn :add(node, i) end
        for i,node in ipairs(dfs.closed.list) do dfs.closen:add(node, i) end
        return dfs
      end,
    --
    setarrowname = function (dfs, src, tgt, arrowname)
        local anames = dfs.arrownames
        if not anames[src]      then anames[src]      = {} end
        if not anames[src][tgt] then anames[src][tgt] = SetL.new() end
	anames[src][tgt]:add(arrowname)
      end,
    setarrownames1 = function (dfs, src)
        for arrowname,tgt in dfs:genarrows(src) do
          dfs:setarrowname(src, tgt, arrowname)
        end  
      end,
    setarrownames = function (dfs)
        dfs.arrownames = {}
        for _,src in ipairs(dfs.opened.list) do dfs:setarrownames1(src) end
        return dfs
      end,
    --
    hasnode = function (dfs, node)
        return dfs.nodetok:has(node)
      end,
    hasnodename = function (dfs, node)
        return dfs.nodetoname[node]
      end,
    setnodename1 = function (dfs, node, name)
        dfs.nodetoname[node] = dfs.nodetoname[node] or name
      end,
    setnodenames1 = function (dfs, node, name)
        if not dfs:hasnode(node) then return end
        if dfs:hasnodename(node) then return end
        dfs.nodetoname[node] = name
        for arrowname,tgt in dfs:genarrows(node) do
	  dfs:setnodenames1(tgt, name.."."..arrowname)
        end
        return dfs
      end,
    setnodenames2 = function (dfs)
        for node,name in pairs(dfs.nodetoname) do
	  if not dfs.nodenames:has(name) then
	    dfs.nodenames:add(name, node)
          end
	end
        dfs.openedntonode = dfs.opened.list
        dfs.closedntonode = dfs.closed.list
        dfs.nodetoopenedn = transpose(dfs.openedntonode)
        dfs.nodetoclosedn = transpose(dfs.closedntonode)
        return dfs
      end,
    --
    nodenamessorted = function (dfs) return dfs.nodenames:ks() end,
    nodenamessortedc = function (dfs, sep)
        return table.concat(dfs:nodenamessorted(), sep or "\n")
      end,
    --
    nnodes = function (dfs) return #dfs.opened.list end,
    maxk = function (dfs) return dfs:nnodes() end,
    ntok = function (dfs, n) return dfs:nnodes() + 1 - n end,
    kton = function (dfs, k) return dfs:nnodes() + 1 - k end,
    nodeinfo = function (dfs, node, short)
        local maybenode
        if not short then maybenode = node end
	local n = dfs.nodetoclosedn[node]
        return {
	  node    = maybenode,
	  name    = dfs.nodetoname[node],
	  openedn = dfs.nodetoopenedn[node],
	  closedn = dfs.nodetoclosedn[node],
	  n       = n,
	  k       = dfs:ntok(n),
	}
      end,
    nameinfo = function (dfs, name, s) return dfs:nodeinfo(dfs.nodenames:get(name), s) end,
    openedninfo = function (dfs, n, s) return dfs:nodeinfo(dfs.openedntonode[n], s) end,
    closedninfo = function (dfs, n, s) return dfs:nodeinfo(dfs.closedntonode[n], s) end,
    ninfo = function (dfs, n, s) return dfs:closedninfo(n, s) end,
    kinfo = function (dfs, k, s) return dfs:ninfo(dfs:kton(k), s) end,
  },
}

classnames = [[ Class Blogme DFSTriangle DedTree ELispH ELispHF
  ELispInfo EevIntro HTable NamedFunction Rect Set SetL Sexp SexpSkel
  SynTree VTable ]]

dfs_from_G = function (thesenamesfirst)
    dfs = DFS.new()
    dfs:recurse(_G):setdfsnumbers():setarrownames()
    dfs:setnodename1(_G, "_G")
    for _,name in ipairs(split(thesenamesfirst or "Class")) do
      dfs:setnodenames1(expr(name), name)
    end
    -- for name,o in pairs(_G) do dfs:setnodenames1(o, name) end
    dfs:setnodenames2()
  end

tname = function (o) return dfs.nodetoname[o] end
PPT   = function (o) print(tname(o) or mytostringpv(o)); return o end

dofile "DFSTriangle.lua"  -- (find-angg "LUA/DFSTriangle.lua")


-- «test-triangle»  (to ".test-triangle")
--[==[
* (eepitch-lua51)
* (eepitch-kill)
* (eepitch-lua51)
dofile "DFS.lua"

dfs_from_G(classnames)
= dfs:nodenamessortedc()
for k=1,dfs:maxk() do PP(dfs:kinfo(k, "s")) end
for name,o in pairs(_G) do dfs:setnodenames1(o, name) end

dfst = DFSTriangle.from(dfs)
dfst:drawdiagonal()
dfst:setgrid0()
dfst:setgrid1()
dfst:setgrid2()
= dfst.r

--]==]


-- «test-tname»  (to ".test-tname")
--[==[
* (eepitch-lua51)
* (eepitch-kill)
* (eepitch-lua51)
dofile "DFS.lua"
dfs_from_G(classnames)
for name,o in pairs(_G) do dfs:setnodenames1(o, name) end

tname = function (o) return dfs:nodeinfo(o).name end
= tname(Set)
= tname(Set.__index)

PPV(Set)
PPV(Set.__index)
PPT(Set)
PPT(Set.__index)

--]==]