3 ms·
The recursive algorithm works for any number of LCAs, as I argued. If you're referring to having multiple roots, there are two solutions: (a) define your 3-wa
by infinity0 7y ago
The recursive algorithm works for any number of LCAs, as I argued.
If you're referring to having multiple roots, there are two solutions:
(a) define your 3-way-merge primitive (the non-recursive version) to support merging two states against an imaginary "zero" that acts as the single root. So in the counter version you can imagine that everything "actually" starts from 0.
(b) arrange your application so there are never multiple roots. In some cases this not really a constraint, usually one single person starts a document and it doesn't make sense to merge something else in later. In some other cases (group chats, tree histories like git) this is probably not acceptable and you will need (a). But in the examples I just gave, a reasonable (a) is fairly straightforward to think of.
- contravariant 7y agoIf it works for 1 your algorithm works for any number so far I can follow. It's a bit tricky to show that the 3-way merge always works fine if you've got a single least common ancestor. But yeah it looks like you're fine because any update that both have in common will also have reached the LCA (this was the insight I was missing that explains why a single LCA works and multiple LCA do not if you naively apply the 3-way-merge).