68 lines
1.6 KiB
Plaintext
68 lines
1.6 KiB
Plaintext
--!strict
|
|
|
|
--[[
|
|
Given a reactive object, updates all dependent reactive objects.
|
|
Objects are only ever updated after all of their dependencies are updated,
|
|
are only ever updated once, and won't be updated if their dependencies are
|
|
unchanged.
|
|
]]
|
|
|
|
local PubTypes = require "../PubTypes"
|
|
|
|
type Set<T> = { [T]: any }
|
|
type Descendant = (PubTypes.Dependent & PubTypes.Dependency) | PubTypes.Dependent
|
|
|
|
-- Credit: https://blog.elttob.uk/2022/11/07/sets-efficient-topological-search.html
|
|
local function updateAll(root: PubTypes.Dependency)
|
|
local counters: { [Descendant]: number } = {}
|
|
local flags: { [Descendant]: boolean } = {}
|
|
local queue: { Descendant } = {}
|
|
local queueSize = 0
|
|
local queuePos = 1
|
|
|
|
for object in pairs(root.dependentSet) do
|
|
queueSize += 1
|
|
queue[queueSize] = object
|
|
flags[object] = true
|
|
end
|
|
|
|
-- Pass 1: counting up
|
|
while queuePos <= queueSize do
|
|
local next = queue[queuePos]
|
|
local counter = counters[next]
|
|
if counter == nil then
|
|
counters[next] = 1
|
|
else
|
|
counters[next] = counter + 1
|
|
end
|
|
if next.dependentSet ~= nil then
|
|
for object in pairs(next.dependentSet) do
|
|
queueSize += 1
|
|
queue[queueSize] = object
|
|
end
|
|
end
|
|
queuePos += 1
|
|
end
|
|
|
|
-- Pass 2: counting down + processing
|
|
queuePos = 1
|
|
while queuePos <= queueSize do
|
|
local next = queue[queuePos]
|
|
local counter = counters[next] - 1
|
|
counters[next] = counter
|
|
if
|
|
counter == 0
|
|
and flags[next]
|
|
and next:update()
|
|
and next.dependentSet ~= nil
|
|
then
|
|
for object in pairs(next.dependentSet) do
|
|
flags[object] = true
|
|
end
|
|
end
|
|
queuePos += 1
|
|
end
|
|
end
|
|
|
|
return updateAll
|