Actually rewrite the dsf implementation.

This rewrite improves the core data structure implementation in two
ways. Firstly, when merging two equivalence classes, we check their
relative sizes, and choose the larger class's canonical element to be
the overall root of the new class tree. This minimises the number of
overlong paths to the root after the merge. Secondly, we defer path
compression until _after_ the two classes are merged, rather than do
it beforehand (via using edsf_canonify as a subroutine) and then have
to do it wastefully again afterwards.

The size-based root selection was what we _used_ to do, and delivers
the better asymptotic performance. I reverted it so that Keen could
track the min of each equivalence class. But since then I've realised
you can have the asymptotic goodness _and_ min-tracking if you store
the minima separately from the main data structure. So now Keen does
that, and other clients don't have to pay the cost.

Similarly, the flip tracking is now a cost that only users of flip
dsfs have to pay, because a normal one doesn't store that information
at all.

0 files changed, 0 insertions, 0 deletions