merge-slicing: explain an alternative implementation in a comments
authorPierre-Yves David <pierre-yves.david@ens-lyon.org>
Fri, 24 Mar 2017 06:24:02 +0100
changeset 2217 37fa3d83f294
parent 2216 de76219b42b8
child 2218 9e30934d4487
merge-slicing: explain an alternative implementation in a comments It has a better time complexity so a C implementation would likely out perform the current implementation
hgext3rd/evolve/stablerange.py
--- a/hgext3rd/evolve/stablerange.py	Fri Mar 24 06:36:12 2017 +0100
+++ b/hgext3rd/evolve/stablerange.py	Fri Mar 24 06:24:02 2017 +0100
@@ -424,9 +424,9 @@
             # revision we needs
             result.append((bottomrevs[-1], rangeid[1]))
         else:
-            bheads = set(bottomrevs)
             parentrevs = cl.parentrevs
             parents = self._parents
+            bheads = set(bottomrevs)
             du = bheads.difference_update
             reachableroots = repo.changelog.reachableroots
             for r in bottomrevs:
@@ -442,6 +442,31 @@
                 start = self.depthrev(repo, h) - len(hrevs)
                 entry = (h, start)
                 result.append(entry)
+
+            # Talking about python code being slow, the following code is an
+            # alternative implementation.
+            #
+            # It complexity is better since is does a single traversal on the
+            # bottomset. However since it is all python it end up being
+            # slower.
+            # I'm keeping it here as an inspiration for a future C version
+            # branches = []
+            # for current in reversed(bottomrevs):
+            #     ps = parents(current, parentrevs)
+            #     found = False
+            #     for brevs, bexpect in branches:
+            #         if current in bexpect:
+            #             found = True
+            #             brevs.append(current)
+            #             bexpect.discard(current)
+            #             bexpect.update(ps)
+            #     if not found:
+            #         branches.append(([current], set(ps)))
+            # for revs, __ in reversed(branches):
+            #     head = revs[0]
+            #     index = self.depthrev(repo, head) - len(revs)
+            #     result.append((head, index))
+
         # top part is trivial
         top = (rangeid[0], globalindex)
         result.append(top)