Incremental merge_sorted?

[Aaron Bentley]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

John Arbash Meinel wrote:
> First think you could do is change the code so that outside the loop it
> does:
> 
> show_merge = getattr(lf, 'show_merge', None)
> 
> Then you can do:
> 
> if show_merge is None:
> 
>   merge_sorted_revisions = [count, rev_id, 0, True
>     for count, rev_id in enumerate(mainline_revs)]
> else:
>   merge_sorted_revisions = merge_sort(...)
> 
> Then we don't have to call merge_sort for the shorter forms. And we
> avoid the 'hasattr()' call in the middle of the loop.

I'll play with that.

> I think the code makes some assumptions that you've seen all the nodes,
> so that you don't have to do any more searching. I'm not sure how muh it
> can be tweaked.

I think the biggest problem is that the algorithm requires that a merged
revision appears only the first time it was merged.  I think that
requires examining the whole graph, if you're iterating through the
whole graph.

But if you're iterating backwards through part of the graph, you can
cheaply test whether the node is among the ancestors of your oldest
revision, so you can quickly throw out nodes you'll never use.

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFElIcH0F+nu1YWqI0RAiWfAJ9GfGPFECWETsLsRwPNyBm1fiW7QwCeOH4M
i13BxVl+H0uLa9zmUFavPHA=
=6Y9l
-----END PGP SIGNATURE-----