|
Warning: this is an htmlized version!
The original is here, and the conversion rules are here. |
-- canvas2.lua
-- Eduardo Ochs, 2010dec28
-- This file: (find-angg "LUA/canvas2.lua")
-- http://angg.twu.net/LUA/canvas2.lua
-- http://angg.twu.net/LUA/canvas2.lua.html
-- «.Class» (to "Class")
-- (find-es "lua5" "setvbuf")
io.stdout:setvbuf("no") -- sync errors
-- Basic functions.
string.trim = function (str)
local nspaces = string.reverse(str):match("[ \t]*()") - 1
return string.sub(str, 1, #str - nspaces)
end
string.adjustto = function (str, len)
str = string.sub(str, 1, len)
if #str < len then str = str .. string.rep(" ", len - #str) end
return str
end
string.replace = function (str, other, pos)
local left = string.sub(str, 1, pos - 1)
if #left < pos - 1 then left = left .. string.rep(" ", pos - #left - 1) end
local right = string.sub(str, pos + #other)
return left .. other .. right
end
table.transpose = function (T)
local TT = {}
for k,v in pairs(T) do TT[v] = k end
return TT
end
table.swaps = function (T, swaps)
if swaps then
for _,ab in ipairs(swaps) do
local a, b = ab[1], ab[2]
T[a], T[b] = T[b], T[a]
end
end
return T
end
table.size = function (T)
for i=1,10000000 do if T[i] == nil then return i-1 end end
end
table.negsize = function (T)
if not T[1] then return nil end
for i=1,-10000000,-1 do if T[i] == nil then return i+1 end end
end
table.assert = function (T, n, filler)
if n >= 1 then
for i=1,n do T[i] = T[i] or filler end
else
for i=1,n,-1 do T[i] = T[i] or filler end
end
end
table.replace1 = function (T, str, x, y)
table.assert(T, y, "")
T[y] = string.replace(T[y], str, x)
return T
end
table.replacemany = function (T, otherT, x, y)
for i=table.negsize(otherT),table.size(otherT) do
table.replace1(T, otherT[i], x, i+(y or 1)-1)
end
return T
end
string.tocanvas = function (str, initialy)
local T = {}
for i,li in ipairs(splitlines(str)) do
table.replace1(T, li, 1, i+(initialy or 1)-1)
end
return T
end
canvastostring = function (T)
return table.concat(T, "\n", table.negsize(T), table.size(T))
end
-- Tests for the basic functions.
assert(string.trim("abcd ") == "abcd")
assert(string.trim("abcde") == "abcde")
assert(string.adjustto("abcdef", 4) == "abcd")
assert(string.adjustto("abcdef", 8) == "abcdef ")
assert(string.replace("abcdef", "CD", 3) == "abCDef")
assert(string.replace("ab", "CD", 3) == "abCD")
assert(string.replace("a", "CD", 3) == "a CD")
assert(table.concat(table.transpose({on=1, tw=2, th=3}), " ") == "on tw th")
assert(table.concat(table.swaps({10, 20, 30, 40}, {{3, 4}})) == "10204030")
A = {[-5]=-50, [-3]=-30, [-2]=-20, [-1]=-10, [0]=0, 10, 20, 30, 40, 50, nil, 70}
assert(table.negsize(A) == -3)
assert(table.size(A) == 5)
strA = "-1\n0\n1\n2"
strB = "a\nb\nc"
assert(strA:tocanvas(-1)[-1] == "-1")
assert(canvastostring(strA:tocanvas(-1)) == strA)
CA = strA:tocanvas(-1)
CB = strB:tocanvas(0)
assert(canvastostring(table.replacemany(CA, CB, 3, 1)) == "-1\n0 a\n1 b\n2 c")
CA = strA:tocanvas(-1)
CB = strB:tocanvas(0)
assert(canvastostring(table.replacemany(CA, CB, 2, -1)) == " a\n-b\n0c\n1\n2")
-- «Class» (to ".Class")
-- A very simple object system.
-- For detailed documentation see:
-- (find-dn6 "eoo.lua")
-- (find-blogme4file "eoo.lua")
-- The metatable of each object points to its class,
-- and classes are callable, and act as creators.
-- New classes can be created with, e.g.:
-- Circle = Class { type = "Circle", __index = {...} }
-- then:
-- Circle {size = 1}
-- sets the metatable of the table {size = 1} to Circle,
-- and returns the table {size = 1} (with its mt modified).
-- Based on: (find-angg "LUA/tostring.lua")
-- See also: (find-angg ".emacs.templates" "class")
Class = {
type = "Class",
__call = function (class, o) return setmetatable(o, class) end,
}
setmetatable(Class, Class)
otype = function (o)
local mt = getmetatable(o)
return mt and mt.type or type(o)
end
Canvas = Class {
type = "Canvas",
__index = {
miny = function (C) return table.negsize(C) end,
maxy = function (C) return table.size(C) end,
width = function (C)
local w = 0
for y=C:miny(),C:maxy() do w = math.max(w, #C[y]) end
return w
end,
tostring = function (C) return canvastostring(C) end,
draw = function (C, obj, x, y)
if type(obj) == "string" then table.replace1(C, obj, x, y)
elseif type(obj) == "table" then table.replacemany(C, obj, x, y)
end
return C
end
},
}
CanvasFrom = function (str, initialy)
return Canvas(string.tocanvas(str, initialy))
end
-- Tests
C = Canvas {[0]="0", "1", "2"}
assert(C:tostring() == "0\n1\n2")
assert(C:miny() == 0)
assert(C:maxy() == 2)
CA, CB = CanvasFrom("0\n1\n2", 0), CanvasFrom("a\nb\nc", 1)
CA, CB = CanvasFrom("0\n1\n2", 0), CanvasFrom("a\nb\nc", 1)
CC = CA:draw(CB, 4, 1)
assert(CC:tostring() == "0\n1 a\n2 b\n c")
assert(CC:width() == 4)
-- The shapes of my DAGs can be described more easily with strings.
-- For example, the "Reh" dag has its four nodes placed like this:
-- 1
-- 2 3
-- 4
-- Its arrows are {{1, 2}, {1, 3}, {2, 4}}, and this can be extracted
-- from the string with the function shapetoarrows, below.
-- Once we have the list of arrows we have a way to calculate the
-- interior of an arbitray subset of {1, 2, 3, 4}, and once we have
-- the interior and binstrings[4] = {"0000", "0001", ...} we can
-- obtain all the open subsets of {1, 2, 3, 4}, by calculating the
-- interior of all the arbitrary subsets.
binstrings = {}
binstrings[1] = {"0", "1"}
for i=2,7 do
binstrings[i] = {}
for _,v in ipairs(binstrings[i-1]) do
table.insert(binstrings[i], v.."0")
table.insert(binstrings[i], v.."1")
end
end
assert(binstrings[6][63] == "111110")
cton = function (c) return tonumber(c, 36) end
intoshape = function (shape, short)
local f = function (c) return short:sub(cton(c), cton(c)) end
return (shape:gsub("(%w)", f))
end
shapetoarrows = function (shape)
local lines = splitlines(shape)
local arrows = {}
local coords = {}
local f = function (c1, c2)
if c1 and c2 then table.insert(arrows, {c1, c2}) end
end
for y=1,#lines-1 do
for x=1,#lines[y] do
local c = cton(lines[y]:sub(x, x))
local sw = cton(lines[y+1]:sub(x-1, x-1))
local s = cton(lines[y+1]:sub(x, x))
local se = cton(lines[y+1]:sub(x+1, x+1))
f(c, sw)
f(c, s)
f(c, se)
end
end
for y=1,#lines do
for x=1,#lines[y] do
local c = cton(lines[y]:sub(x, x))
if c then coords[c] = {x, y} end
end
end
return arrows, coords
end
arrowstostring = function (arrows)
return table.concat(map(table.concat, arrows), " ")
end
interior = function (short, arrows)
local T = split(short, ".")
for i=#arrows,1,-1 do
local src, tgt = arrows[i][1], arrows[i][2]
if (not T[src]) or (not T[tgt]) then
PP("Too short!", short, arrows)
end
if T[src] > T[tgt] then T[src] = T[tgt] end
end
return table.concat(T, "")
end
binstrings = {}
binstrings[1] = {"0", "1"}
for i=2,14 do
binstrings[i] = {}
for _,v in ipairs(binstrings[i-1]) do
table.insert(binstrings[i], v.."0")
table.insert(binstrings[i], v.."1")
end
end
-- Tests.
reh_shape = [[
1
2 3
4]]
reh_arrows, reh_coords = shapetoarrows(reh_shape)
assert(intoshape(reh_shape, "abcd") == " a\nb c\nd")
assert(arrowstostring(reh_arrows) == "12 13 24")
assert(interior("1001", reh_arrows) == "0001")
assert(binstrings[6][1] == "000000")
assert(binstrings[6][63] == "111110")
-- Calculate the topology.
shapenvertices = function (shape) -- count the digits
return #(string.gsub(shape, "%W", ""))
end
weightof = function (short) -- count the "1"s
return #(string.gsub(short, "[^1]", ""))
end
opensetsfor = function (shape)
local arrows = shapetoarrows(shape)
local nvertices = shapenvertices(shape)
local classicaltruthvals = binstrings[nvertices]
local opensets = {}
local rankedopensets = {}
for w=0,nvertices do rankedopensets[w] = {} end
for _,short in ipairs(classicaltruthvals) do
if short == interior(short, arrows) then
table.insert(opensets, short)
table.insert(rankedopensets[weightof(short)], 1, short)
end
end
local ctoopenset, opensettoc = {}, {}
local c = 0
for w=nvertices,0,-1 do
for _,openset in ipairs(rankedopensets[w]) do
c = c + 1
ctoopenset[c] = openset
opensettoc[openset] = c
end
end
return opensets, rankedopensets, ctoopenset, opensettoc
end
-- Tests.
-- (find-sh "lua51 ~/LUA/canvas2.lua")
assert(shapenvertices(reh_shape) == 4)
assert(weightof("1100111"), 5)
reh_opens, reh_ranked, c_to_rehopen, rehopen_to_c = opensetsfor(reh_shape)
assert(table.concat(reh_opens, " ") == "0000 0001 0010 0011 0101 0111 1111")
assert(table.concat(reh_ranked[2], " ") == "0101 0011")
-- Tools for printing Heyting algebras.
-- They don't always print the right diagrams without human intervention...
-- but these tools save a lot of work.
texargs = {[0]="",
"#1",
"#1#2",
"#1#2#3",
"#1#2#3#4",
"#1#2#3#4#5",
"#1#2#3#4#5#6",
"#1#2#3#4#5#6#7",
"#1#2#3#4#5#6#7#8",
"#1#2#3#4#5#6#7#8#9",
}
primesketch = function (shape, xscale, yscale)
local opens, ranked, ctoop, optoc = opensetsfor(shape)
local C = Canvas {""}
for y=0,#ranked do
for x=1,#ranked[y] do
local short = ranked[y][x]
local long = intoshape(shape, short)
local D = CanvasFrom(long)
C:draw(D, (x - 1) * xscale + 1, -y * yscale)
end
end
return C
end
primesketch2 = function (shape, biggershape, xscale, yscale, swaps)
local opens, ranked, ctoopen, opentoc = opensetsfor(shape)
local _, coords = shapetoarrows(biggershape)
ctoopen = table.swaps(ctoopen, swaps)
opentoc = table.transpose(ctoopen)
local C = Canvas {""}
for c,openset in ipairs(ctoopen) do
local xy = coords[c]
local x, y = xy[1], xy[2]
local bigx, bigy = (x - 1) * xscale + 1, (y - 1) * yscale
local D = CanvasFrom(intoshape(shape, openset))
C:draw(D, bigx, bigy)
end
return C
end
Shape = Class {
type = "Shape",
__index = {
into = function (Sh, short) return intoshape(Sh.sh, short) end,
intoc = function (Sh, short) return CanvasFrom(Sh:into(short)) end,
primesketch = function (Sh, xscale, yscale)
return primesketch(Sh.shape, xscale, yscale)
end,
primesketch2 = function (Sh, BiggerSh, xscale, yscale, swaps)
return primesketch2(Sh.shape, BiggerSh.shape, xscale, yscale, swaps)
end,
printsketch = function(Sh, xscale, yscale)
print("Topology for "..Sh.name.." (sketch, ranked):")
print(Sh:primesketch(xscale, yscale):tostring())
end,
printsketch2 = function(Sh, BiggerSh, xscale, yscale, swaps)
print("Topology for "..Sh.name.." (as "..BiggerSh.name.."):")
print(Sh:primesketch2(BiggerSh, xscale, yscale, swaps):tostring())
end,
texdef = function (Sh, lower)
local out = ""
local printf = function (...) out = out..format(...) end
local w, h = Sh.width, Sh.height
local pw = 6 * w + 2
local ph = 12 * h
local name = Sh.name
local args = texargs[Sh.nvertices]
local plower = (lower or 0) * 12
printf("\\def\\dag%s%s{%%\n", name, args)
printf(" \\dagpicture(%d,%d)(-4,0)[%d]{\n", pw, ph, plower)
for i,xy in ipairs(Sh.coords) do
local x, y = xy[1], xy[2]
local px, py = (x-1)*6, (h-y)*12
printf(" \\dagput(%3d,%3d){$#%d$}\n", px, py, i)
end
printf(" }}\n")
return out
end,
texcomment = function (Sh)
return "% "..Sh.shape:gsub("\n", "\n%% ")
end,
texbhbox = function (Sh)
local testargs = texargs[Sh.nvertices]:gsub("#", "")
return format("%s: $\\bhbox{\\dag%s %s}$", Sh.name, Sh.name, testargs)
end,
textest = function (Sh, lower)
printf("%%\15\n")
printf("%% (eedn4a-bounded)\n")
printf("%s\n", Sh:texdef(lower))
printf("\\edrxcolors\n")
printf("\\def\\bhbox{\\bicolorhbox}\n")
printf("%s\n", Sh:texbhbox())
printf("%%\15\n")
end,
},
}
ShapeFrom = function (name, shape)
local arrows, coords = shapetoarrows(shape)
local nvertices = shapenvertices(shape)
local opens, ranked, ctoopen, opentoc = opensetsfor(shape)
local C = CanvasFrom(shape, 1)
local width, height = C:width(), #C
return Shape {
name = name,
shape = shape,
arrows = arrows,
coords = coords,
opensets = opens,
rankedopensets = ranked,
width = width,
height = height,
nvertices = nvertices,
shape = shape,
}
end
-- Tests.
Reh = ShapeFrom("Reh", [[
1
2 3
4]])
Pot32 = ShapeFrom("Pot32", [[
1
2
3 4
5 6
7]])
-- Reh:printsketch(6, 4)
-- Pot32:printsketch(10, 6)
-- Reh:printsketch2(Pot32, 6, 4)
Lguill = ShapeFrom("Lguill", [[
1 2
3 4
5 6]])
-- PP(Lguill)
Lguill_prime = ShapeFrom("Lguill_prime", [[
1
2 3
4 5
6 7
8 9
A B
C]])
-- Lguill:printsketch(6, 4)
-- Lguill_prime:printsketch(6, 7)
-- Lguill:printsketch2(Lguill_prime, 4, 4)
Lguill:printsketch2(Lguill_prime, 4, 4, {{4, 5}})
-- Lguill = lguill_shape)
--[[
Topology for Lguill (as Lguill_prime):
1 1
1 1
1 1
1 0 0 1
1 1 1 1
1 1 1 1
0 0 0 1
1 1 0 1
1 1 1 1
0 0 0 0
1 0 0 1
1 1 1 1
0 0 0 0
1 0 0 0
1 0 1 1
0 0 0 0
0 0 0 0
1 0 0 1
0 0
0 0
0 0
--]]
-- print(primesketch2(reh_shape, bigpot_shape, 6, 4):tostring())
-- Reh = ShapeFrom("Reh", reh_shape)
-- PP(Reh)
-- print(Reh:primesketch(5, 5):tostring())
-- PP(Lguill)
-- print(Lguill:primesketch(5, 5):tostring())
-- (eejump 10)
-- (eejump 11)
-- Local Variables:
-- coding: raw-text-unix
-- modes: (fundamental-mode lua-mode)
-- End: