--[[
	Rychládrát.lua
	blah 2020

	A script for Golly that allows you to simulate Rychládrát. Writing a rule to
	be run by the RuleLoader algorithm would be impossible, since it has instant
	wire, so instead a dummy rule is used. If you don't already have it, copy /
	paste this into Golly:

@RULE Rychladrat
This rule cannot actually be implemented in RuleLoader. This rule is intended to
be used in conjunction with a Lua script. By itself, this .rule file is just
here to provide an appropriate colour palette.
@COLORS
0    0   0   0 Empty Space
1   64  64  64 Inactive Wire
2  255 255 255 Active Wire
3   37  37  69 Active Gate Output
4  150   0 150 Inactive NOR Gate
5  150 150   0 Inactive OR Gate
6  250   0   0 Inactive AND Gate
7    0 250 250 Inactive NAND Gate
8    0   0 250 Inactive XOR Gate
9   32  32  64 Inactive Gate Output
10 155   5 155 Active NOR Gate
11 155 155   5 Active OR Gate
12 255   5   5 Active AND Gate
13   5 255 255 Active NAND Gate
14   5   5 255 Active XOR Gate
15   0 127   0 Inactive Switch
16   0 255   0 Active Switch
17 127 127 127 Insulated Wire
@TABLE
n_states:18
neighborhood:vonNeumann
symmetries:permute

	Then, open a pattern you want to simulate, and then run this script. Press r
	to start simulation, space to simulate individual frames. - to slow down, =
	to speed up, c to set steps per frame to 964 (exactly 1 Důvěřivý cpu cycle),
	q to quit. Do not edit the pattern while the script is running.
]]

--------------------------------------------------------------------- SIMULATION

--[[
	This section contains the necessary code to simulate Rychládrát.

	The pattern is stored in pat, as a 2D matrix (table of tables). In many
	simulators, there are two such matrices; one is read from, and the next step
	of simulation is written to the other one. The matrices are then swapped. In
	this simulator, however, there is only one; changes to be made to it are
	stored in chg.

	A step of the simulation looks like this:

	SET new_chg TO EMPTY TABLE
	SET hash TO EMPTY TABLE
	FOR EVERY CHANGE LISTED IN chg:
		FOR ALL 5 CELLS IN NEIGHBOURHOOD:
			IF THEY'RE NOT ALREADY IN hash:
				EVALUATE THEM
				IF THEY CHANGE STATE:
					ADD THEM TO new_chg
					ADD THEM TO hash
	FOR EVERY CHANGE LISTED IN new_chg:
		APPLY IT
	SET chg TO new_chg

	Technically, this fails to account for the 'rays' that outputs emit when
	they change state. However, that doesn't really change the algorithm much.
	And speaking of the rays, instead of being calculated every time they're
	emitted, they are only generated once, and stored into the 'rays' variable.
	(If you want a challenge, try modifying gen_rays() to handle signal turns.)

	This description is also kind of non-literal. For example, this code doesn't
	really set new_chg to an empty table; that would be inefficient. Instead it
	stores a length variable, which is set to 0 when it's "cleared".

	Writing to the display is assumed to be expensive, especially if the changes
	you're writing get unwritten before the user can see them anyway. So dchg
	and dhash exist and serve a similar purpose to chg and hash, except they're
	not reset every step. They're only reset when results are displayed.

	chg is formatted like: {x, y, to, x, y, to, x, y, to...} every pair of 3
	consecutive values denotes that cell (x, y) should change to 'to'. dchg has
	a less efficient format.
]]
local pat
local width, height
local rays
local chg, chg_len
local new_chg, new_chg_len
local hash
local dchg = {}
local dhash = {}

function new_pattern()
	local ret = {}
	-- note: pattern is surrounded by a 1-cell border of 0s to simplify getting
	-- neighbours
	for y = 0, height + 1 do
		ret[y] = {}
		for x = 0, width + 1 do
			ret[y][x] = 0
		end
	end
	return ret
end

-- do not call this when a step is being simulated; only between steps
function set(x, y, to)
	pat[y][x] = to
	chg_len = chg_len + 3
	chg[chg_len - 2] = x
	chg[chg_len - 1] = y
	chg[chg_len] = to
end

local function new_set(x, y, to)
	-- only make change if it's not already in hash
	-- "y * width + x" is simply to ensure a unique value for all (x, y)
	local key = y * width + x
	if not hash[key] then
		-- using the local variable new_new_chg_len eliminates 3 GETTABUP
		-- commands in the bytecode
		local new_new_chg_len = new_chg_len + 3
		new_chg_len = new_new_chg_len
		new_chg[new_new_chg_len - 2] = x
		new_chg[new_new_chg_len - 1] = y
		new_chg[new_new_chg_len] = to
		-- then add it to hash
		hash[key] = true -- make non-nil

		-- same thing but with dhash and dchg
		if not dhash[key] then
			dchg[#dchg + 1] = {x = x, y = y, from = pat[y][x]}
			dhash[key] = true
		end
	end
end

-- apply changes
local function flush()
	local pat, chg = pat, chg
	for i = 1, chg_len, 3 do
		pat[chg[i + 1]][chg[i]] = chg[i + 2]
	end
end

local eval_cell, ray -- forward declarations

-- generate the changes for the next step, store in new_chg
local function gen_chg()
	local eval_cell = eval_cell
	hash = {}
	new_chg_len = 0
	for i = 1, chg_len, 3 do
		local x, y = chg[i], chg[i + 1]
		eval_cell(x, y - 1)
		eval_cell(x - 1, y)
		eval_cell(x, y)
		eval_cell(x + 1, y)
		eval_cell(x, y + 1)
	end
end

function step(times)
	times = times or 1
	for i = 1, times do
		gen_chg()

		-- swap chg and new_chg
		chg, new_chg = new_chg, chg
		chg_len = new_chg_len

		flush()
	end
end

-- called before first step, after pat has been written/modified
function init()
	-- init chg to change all cells to themselves
	-- at the same time, generate rays
	chg, new_chg = {}, {}
	chg_len, new_chg_len = 0, 0
	rays = {}
	for y = 1, height do
		for x = 1, width do
			set(x, y, pat[y][x])
			if pat[y][x] == 3 or pat[y][x] == 9 then
				gen_ray(x, y)
			end
		end
	end
end

-- amount of neighbours of (x, y) with state s
local function amt_neighbours(x, y, s)
	local a = 0
	-- saving pat[y] in its own variable should be faster than evaluating it
	-- twice. I can't detect an increase in speed but it's probably there.
	local mid = pat[y]
	if mid[x - 1] == s then a = a + 1 end
	if mid[x + 1] == s then a = a + 1 end
	if pat[y - 1][x] == s then a = a + 1 end
	if pat[y + 1][x] == s then a = a + 1 end
	return a
end

-- whether or not there are any neighbours of (x, y) with state s
local function any_neighbours(x, y, s)
	local mid = pat[y]
	if mid[x - 1] == s then return true end
	if mid[x + 1] == s then return true end
	if pat[y - 1][x] == s then return true end
	if pat[y + 1][x] == s then return true end
	return false
end

eval_cell = function(x, y)
	local c = pat[y][x]
	local new_c -- state that the center cell should take on next
	if c < 3 or c == 17 then -- these don't change, at least by themselves
		return
	elseif c == 9 or c == 3 then -- GATE OUTPUT
		-- if there is at least one active gate input, the output will be active

		-- this is very optimised. n is set to the 4 neighbouring cells and
		-- then if it's active we skip all the other cells because there's no
		-- need to test them.

		-- also, the first location tested is (x, y + 1). this is because many
		-- of the logic gates in the RAM of the computer have their inputs below
		-- their outputs. if you believe this is overthinking it, swap "y + 1"
		-- and "y - 1" in this section of code and then benchmark. There's a
		-- measurable difference.
		local n = pat[y + 1][x]
		if n >= 10 and n <= 14 then
			goto active
		end
		n = pat[y][x + 1]
		if n >= 10 and n <= 14 then
			goto active
		end
		n = pat[y][x - 1]
		if n >= 10 and n <= 14 then
			goto active
		end
		n = pat[y - 1][x]
		if n >= 10 and n <= 14 then
			goto active
		end
		new_c = 9
		goto new_c_found
		::active::
		new_c = 3
		::new_c_found::

		-- outputs only emit rays when they change
		if c ~= new_c then
			local s -- state to set wires to
			if new_c == 3 then
				s = 2
			else
				s = 1
			end
			ray(x, y, s)
		end
	-- GATE INPUTS
	elseif c == 5 or c == 11 then -- OR GATE
		if any_neighbours(x, y, 2) then
			new_c = 11
		else
			new_c = 5
		end
	elseif c == 4 or c == 10 then -- NOR GATE
		if any_neighbours(x, y, 2) then
			new_c = 4
		else
			new_c = 10
		end
	elseif c == 6 or c == 12 then -- AND GATE
		if any_neighbours(x, y, 1) then
			new_c = 6
		else
			new_c = 12
		end
	elseif c == 8 or c == 14 then -- XOR GATE
		if amt_neighbours(x, y, 2) == 1 then
			new_c = 14
		else
			new_c = 8
		end
	elseif c == 15 or c == 16 then -- SWITCH
		if any_neighbours(x, y, 9) then
			new_c = 15
		else
			new_c = 16
		end
	elseif c == 7 or c == 13 then -- NAND GATE
		if any_neighbours(x, y, 1) then
			new_c = 13
		else
			new_c = 7
		end
	end
	if c ~= new_c then
		new_set(x, y, new_c)
	end
end

-- generate lists of cells to be iterated through when an output changes state
function gen_ray(x, y)
	local new_ray = {}
	-- send ray right
	ray_dir(x, y, 1, 0, new_ray)
	-- send ray left
	ray_dir(x, y, -1, 0, new_ray)
	-- send ray down
	ray_dir(x, y, 0, 1, new_ray)
	-- send ray up
	ray_dir(x, y, 0, -1, new_ray)
	rays[y * width + x] = new_ray
end

function ray_dir(x, y, xoff, yoff, r)
	local ret = {}
	local c = 17
	repeat
		if c ~= 17 then
			ret[#ret + 1] = x
			ret[#ret + 1] = y
		end
		-- go to next cell
		x = x + xoff
		y = y + yoff
		c = pat[y][x]
	until not (c == 1 or c == 2 or c >= 15)
	if #ret ~= 0 then
		r[#r + 1] = ret
	end
end

-- iterate through lists generated by gen_ray()
ray = function(x, y, state)
	-- multiple rays setting the same cell in the same step of the simulation
	-- produces undefined behaviour
	local r = rays[y * width + x]
	for i = 1, #r do
		local v = r[i]
		for j = 2, #v, 2 do
			local x, y = v[j - 1], v[j]
			local c = pat[y][x]
			if c == 15 then -- inactive switch
				break
			elseif c <= 2 then -- active/inactive wire
				new_set(x, y, state)
			end
		end
	end
end

---------------------------------------------------------------- GOLLY INTERFACE
-- This section contains code for a UI using Golly.

local g = golly()

if g.getrule() ~= "Rychladrat" then
	g.warn("This is not a Rychládrát pattern. This script cannot simulate it.")
	g.exit()
end

local top, left -- location of simulated pattern in golly's copy

-- draw changes to pattern
function draw()
	for i = 1, #dchg do
		local c = dchg[i]
		if pat[c.y][c.x] ~= c.from then
			g.setcell(c.x + left, c.y + top, pat[c.y][c.x])
		end
	end
	dchg = {}
	dhash = {}
end

function load_pat()
	local r = g.getrect()
	left, top, width, height = table.unpack(r)
	if not left then -- empty pattern
		g.warn("There is no pattern to simulate. Open or create a Rychládrát" ..
		       " pattern first, then re-run this script.")
		g.exit()
	end

	-- call to new() is not needed, but is hackish way to prevent Golly from
	-- saving undo history
	--g.select(r) g.copy() g.new("") g.paste(left, top, "copy")
	-- wait no that doesn't change its performance for some reason.

	-- transform cell list into cell matrix
	local cl = g.getcells(r)
	pat = new_pattern()
	-- if the next 2 lines confuse you, read the Golly Lua help page's section
	-- on "cell arrays" (the +1s are because tables are indexed from 1, not 0)
	for i = 3, #cl, 3 do
		pat[cl[i - 1] + 1 - top][cl[i - 2] + 1 - left] = cl[i]
	end
	left = left - 1
	top = top - 1
	init()
end

local t = 0
function gstep(times)
	step(times)
	draw()
	g.update()
	t = t + times
	g.show("t = " .. t .. ", cpu cycle = " .. math.floor(t/964))
end

function gset(x, y, new)
	set(x, y, new)
	g.setcell(x + left, y + top, new)
	g.update()
end

------

load_pat()
g.getevent()
spf = 1 -- steps per frame
is_running = false
evts = 0 -- amount of events handled; used for timing when spf < 1

last_e = ""
while true do
	::loopstart::
	local e = g.getevent()
	if e == last_e and last_e ~= "" then
		goto loopstart
	end
	evts = evts + 1
	-- "none" in the event strings means no modifier key is held down
	if e == "key q none" then -- quit
		g.exit()
	elseif e == "key = none" then -- speed up
		spf = spf * 2
	elseif e == "key - none" then -- slow down
		spf = spf / 2
		if spf < 0.25 then
			spf = 0.25
		end

	-- input keys for Důvěřivý
	elseif e == "key up none" then
		gset(428, 425, 2)
	elseif e == "key left none" then
		gset(427, 426, 2)
	elseif e == "key right none" then
		gset(429, 426, 2)
	elseif e == "key down none" then
		gset(428, 427, 2)
	elseif e == "key return none" then
		gset(432, 426, 2)
	elseif e == "key delete none" then
		gset(434, 426, 2)
	elseif e == "kup up" then
		gset(428, 425, 1)
	elseif e == "kup left" then
		gset(427, 426, 1)
	elseif e == "kup right" then
		gset(429, 426, 1)
	elseif e == "kup down" then
		gset(428, 427, 1)
	elseif e == "kup return" then
		gset(432, 426, 1)
	elseif e == "kup delete" then
		gset(434, 426, 1)

	elseif e == "key space none" then -- simulate frame
		gstep(math.ceil(spf))
	elseif e == "key r none" then -- start/stop
		is_running = not is_running
	elseif e == "key c none" then -- set steps per frame to 1 cpu cycle
		spf = 964
	elseif e == "key b none" then -- benchmark
		local t = os.clock()
		gstep(964 * 3 * 100)
		t = os.clock() - t
		g.warn(t)
	else
		g.doevent(e) -- pass to golly
	end

	-- run step and sleep only if there's no user input left to interpret
	-- (otherwise events would pile up and take forever to parse)
	if e == "" then
		if is_running and evts % math.ceil(1 / spf) == 0 then
			gstep(math.ceil(spf))
		end
		-- sleeping is necessary not just to control speed, but also to prevent
		-- busy waiting 
		g.sleep(10)
	end
	last_e = e
end