Note the java algo is event-queue based — every newly concretized cell is an event added to the event queue. When we encounter this cell again after a dequeue, All registered dependents of this cell are checked. If the check results in a new cell concretized, this cell is enqueued.
In contrast, my c++ algo is a modified BFT. Key idea is, whenever a branch node can’t be concretized (due to an unresolved upstream reference) we basically ignore that node’s subtree. The other root nodes’s BFT would eventually visit this node, unless there’s a cycle.
I believe both algorithms are relatively easy to visualize at a high level. Which algo implementation is more tricky and error-prone? I guess the BFT but not really sure.
— Topo-sort — “topological sorting” is the reusable general technique for similar problems like even scheduling. As I described to Kyle, the idea is “Given a directed graph, assign (artificial) integer ranks to all nodes so that every arrow is from a low rank to a high rank”
There are linear time algorithms to assign the ranks. I think some form of BFT may work… need more thinking.
I think it depends on what’s more natural — start from leaf nodes or start from root nodes. The start level would use lower integers.
For a typical spreadsheet, I feel it’s natural to start from nodes that have no downstream.
My c++ implementation was similar to Kahn’s algorithm.
[[Algorithms]] P 550 presents an elegant DFT algo but not so intuitive to me yet. I think it DFT can’t solve this spreadsheet.
–Some additional notes on the c++ implementation
- 🙂 I encountered much few seg-faults than in other projects. I think it’s because very few arrays (including vectors) are used.
- Before I look up a map/set, I always use count() to verify.
- 🙂 I didn’t need to check against end() as lower_bound() and find() functions would require.
- no smart ptr needed. container of raw ptr worked well. See source code comments
- In fact, container of cell names (as strings) is even “safer”.
keep learning 活到老学到老 