[PATCH 1 of 2] revlogdag: add linearize function

[Sune Foldager]

# HG changeset patch
# User Sune Foldager <cryo at cyanite.org>
# Date 1305727154 -7200
# Node ID d05bc567f5368ac6ee1bd3f27a7746200906759f
# Parent  ad5c68a0db6ae578cf7e0154f7209e2e10ee2b2b
revlogdag: add linearize function

See the docstring for a detailed explanation. The linearizer was originally
written by Benoit Boissinot.

diff -r ad5c68a0db6a -r d05bc567f536 mercurial/dagutil.py
--- a/mercurial/dagutil.py	Wed May 18 15:45:57 2011 +0200
+++ b/mercurial/dagutil.py	Wed May 18 15:59:14 2011 +0200
@@ -205,6 +205,34 @@
         assert headrevs
         return headrevs
 
+    def linearize(self, ixs):
+        '''linearize and topologically sort a list of revisions
+
+        The linearization process tries to create long runs of revs where
+        a child rev comes immediately after its first parent. This is done by
+        visiting the heads of the given revs in inverse topological order,
+        and for each visited rev, visiting its second parent, then its first
+        parent, then adding the rev itself to the output list.
+        '''
+        sorted = []
+        visit = list(self.headsetofconnecteds(ixs))
+        visit.sort(reverse=True)
+        finished = set()
+
+        while visit:
+            cur = visit.pop()
+            if cur < 0:
+                cur = -cur - 1
+                if cur not in finished:
+                    sorted.append(cur)
+                    finished.add(cur)
+            else:
+                visit.append(-cur - 1)
+                visit += [p for p in self.parents(cur)
+                          if p in ixs and p not in finished]
+        assert len(sorted) == len(ixs)
+        return sorted
+
 
 class inverserevlogdag(revlogbaseddag, genericdag):
     '''inverse of an existing revlog dag; see revlogdag.inverse()'''