Disjoint Set Algorithm
|Table of contents|
See here for the theoretical foundation for this page. It's effectively a data structure for efficient mergers of groups and comparison if two items are in the same or different groups.
Housebot allows undo's by adding an extra field to the data structure. The path compression is restricted to not cross an undo boundary. A boundary is simply defined to be a node with a boolean flag set. Housebot uses a function object for retaining the required undo/commit information.
Given the parent storage structure, any intermediate node being deleted could actually be used in the lookup of the parent of other nodes. Here are candidate solutions:
- When placing a new stone on the board, do not make it's group be its own parent. Instead give it a distinct parent (aka allocate a parent for it). Then, when stones merge, the new stones' parent will be this other node that was created instead of something that can later be deleted. This scheme relies on memory management (such as exists in Java or maybe a shared_ptr from boost for C++).