<feed xmlns='http://www.w3.org/2005/Atom'>
<title>puzzles/dsf.c, branch devel</title>
<subtitle>My sgt-puzzles tree</subtitle>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/'/>
<entry>
<title>Actually rewrite the dsf implementation.</title>
<updated>2023-04-20T17:42:50+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2023-04-20T16:13:47+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=68d242c5875ec1133429c656520b2d173c05e387'/>
<id>68d242c5875ec1133429c656520b2d173c05e387</id>
<content type='text'>
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.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
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.
</pre>
</div>
</content>
</entry>
<entry>
<title>Reorganise the dsf API into three kinds of dsf.</title>
<updated>2023-04-20T17:39:41+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2023-04-20T16:27:21+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=c5e253a9f9d3d651227ccad56e2c7526ee1f3eba'/>
<id>c5e253a9f9d3d651227ccad56e2c7526ee1f3eba</id>
<content type='text'>
This is preparing to separate out the auxiliary functionality, and
perhaps leave space for making more of it in future.

The previous name 'edsf' was too vague: the 'e' stood for 'extended',
and didn't say anything about _how_ it was extended. It's now called a
'flip dsf', since it tracks whether elements in the same class are
flipped relative to each other. More importantly, clients that are
going to use the flip tracking must say so when they allocate the dsf.

And Keen's need to track the minimal element of an equivalence class
is going to become a non-default feature, so there needs to be a new
kind of dsf that specially tracks those, and Keen will have to call it.

While I'm here, I've renamed the three dsf creation functions so that
they start with 'dsf_' like all the rest of the dsf API.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
This is preparing to separate out the auxiliary functionality, and
perhaps leave space for making more of it in future.

The previous name 'edsf' was too vague: the 'e' stood for 'extended',
and didn't say anything about _how_ it was extended. It's now called a
'flip dsf', since it tracks whether elements in the same class are
flipped relative to each other. More importantly, clients that are
going to use the flip tracking must say so when they allocate the dsf.

And Keen's need to track the minimal element of an equivalence class
is going to become a non-default feature, so there needs to be a new
kind of dsf that specially tracks those, and Keen will have to call it.

While I'm here, I've renamed the three dsf creation functions so that
they start with 'dsf_' like all the rest of the dsf API.
</pre>
</div>
</content>
</entry>
<entry>
<title>Introduce a new dsf_equivalent() function.</title>
<updated>2023-04-20T17:39:35+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2023-04-20T14:32:10+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=14e1e05510ac02a5502823bafe46d98c6fab3e5c'/>
<id>14e1e05510ac02a5502823bafe46d98c6fab3e5c</id>
<content type='text'>
Not very interesting, but the idiom for checking equivalence via two
calls to dsf_canonify is cumbersome enough to be worth abbreviating.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Not very interesting, but the idiom for checking equivalence via two
calls to dsf_canonify is cumbersome enough to be worth abbreviating.
</pre>
</div>
</content>
</entry>
<entry>
<title>Remove conditioned-out dsf diagnostic code.</title>
<updated>2023-04-20T16:30:03+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2023-04-20T13:57:42+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=088fdeee38599b1711ba8766d36c652f1355e36e'/>
<id>088fdeee38599b1711ba8766d36c652f1355e36e</id>
<content type='text'>
print_dsf was declared in puzzles.h, but never called, and its
definition was commented out. So it probably wouldn't still have
worked anyway. The other commented-out printfs in that file don't look
very useful either, and they just mean more stuff will need messing
about with as I continue to refactor.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
print_dsf was declared in puzzles.h, but never called, and its
definition was commented out. So it probably wouldn't still have
worked anyway. The other commented-out printfs in that file don't look
very useful either, and they just mean more stuff will need messing
about with as I continue to refactor.
</pre>
</div>
</content>
</entry>
<entry>
<title>Remove size parameter from dsf init and copy functions.</title>
<updated>2023-04-20T16:30:03+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2023-04-20T13:46:46+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=348aac4c85da21e09c29c58866d178df3204d73c'/>
<id>348aac4c85da21e09c29c58866d178df3204d73c</id>
<content type='text'>
Now that the dsf knows its own size internally, there's no need to
tell it again when one is copied or reinitialised.

This makes dsf_init much more about *re*initialising a dsf, since now
dsfs are always allocated using a function that will initialise them
anyway. So I think it deserves a rename.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Now that the dsf knows its own size internally, there's no need to
tell it again when one is copied or reinitialised.

This makes dsf_init much more about *re*initialising a dsf, since now
dsfs are always allocated using a function that will initialise them
anyway. So I think it deserves a rename.
</pre>
</div>
</content>
</entry>
<entry>
<title>Store a size field inside the DSF type.</title>
<updated>2023-04-20T16:30:01+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2023-04-20T13:25:22+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=dad2f35502c611dae758915cfb6dface4a303550'/>
<id>dad2f35502c611dae758915cfb6dface4a303550</id>
<content type='text'>
This permits bounds-checking of all inputs to dsf_canonify and
dsf_merge, so that any out-of-range values will provoke assertion
failure instead of undefined behaviour.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
This permits bounds-checking of all inputs to dsf_canonify and
dsf_merge, so that any out-of-range values will provoke assertion
failure instead of undefined behaviour.
</pre>
</div>
</content>
</entry>
<entry>
<title>Actually make DSF an opaque structure type.</title>
<updated>2023-04-20T16:23:23+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2023-04-20T13:12:11+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=095224d5711f3482d6be0ffc01621143f25c7104'/>
<id>095224d5711f3482d6be0ffc01621143f25c7104</id>
<content type='text'>
This makes good on all the previous preparatory commits, which I did
separately so that each one individually has a reasonably readable
diff, and all the mechanical changes are separated out from the
rewrites that needed actual thought.

Still no functional change, however: the DSF type wraps nothing but
the same int pointer that 'DSF *' used to store directly.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
This makes good on all the previous preparatory commits, which I did
separately so that each one individually has a reasonably readable
diff, and all the mechanical changes are separated out from the
rewrites that needed actual thought.

Still no functional change, however: the DSF type wraps nothing but
the same int pointer that 'DSF *' used to store directly.
</pre>
</div>
</content>
</entry>
<entry>
<title>Declare all dsfs as a dedicated type name 'DSF'.</title>
<updated>2023-04-20T16:23:21+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2023-04-20T13:06:43+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=89c438e149a91fffa74b2669f7e0cd05abc3420f'/>
<id>89c438e149a91fffa74b2669f7e0cd05abc3420f</id>
<content type='text'>
In this commit, 'DSF' is simply a typedef for 'int', so that the new
declaration form 'DSF *' translates to the same type 'int *' that dsfs
have always had. So all we're doing here is mechanically changing type
declarations throughout the code.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
In this commit, 'DSF' is simply a typedef for 'int', so that the new
declaration form 'DSF *' translates to the same type 'int *' that dsfs
have always had. So all we're doing here is mechanically changing type
declarations throughout the code.
</pre>
</div>
</content>
</entry>
<entry>
<title>Use a dedicated copy function to copy dsfs.</title>
<updated>2023-04-20T16:21:54+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2023-04-20T12:52:13+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=11a8149d673d96bec17d6487b5fa95b5bf5ffd6b'/>
<id>11a8149d673d96bec17d6487b5fa95b5bf5ffd6b</id>
<content type='text'>
Previously we were duplicating the contents of a dsf using straight-up
memcpy. Now there's a dsf_copy function wrapping the same memcpy.

For the moment, this still has to take a size parameter, because the
size isn't stored inside the dsf itself. But once we make a proper
data type, it will be.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Previously we were duplicating the contents of a dsf using straight-up
memcpy. Now there's a dsf_copy function wrapping the same memcpy.

For the moment, this still has to take a size parameter, because the
size isn't stored inside the dsf itself. But once we make a proper
data type, it will be.
</pre>
</div>
</content>
</entry>
<entry>
<title>Use a dedicated free function to free dsfs.</title>
<updated>2023-04-20T16:21:12+00:00</updated>
<author>
<name>Simon Tatham</name>
<email>anakin@pobox.com</email>
</author>
<published>2023-04-20T12:35:58+00:00</published>
<link rel='alternate' type='text/html' href='https://www.franklinwei.com/cgit/puzzles/commit/?id=bb561ee3b18be69e52b17cedde50eac96ea409da'/>
<id>bb561ee3b18be69e52b17cedde50eac96ea409da</id>
<content type='text'>
No functional change: currently, this just wraps the previous sfree
call.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
No functional change: currently, this just wraps the previous sfree
call.
</pre>
</div>
</content>
</entry>
</feed>
