[PATCH 5 of 6] shrink-revlog: add "reverse postorder" and "postorder reverse" toposorts

[Greg Ward]

# HG changeset patch
# User Greg Ward <greg-hg at gerg.ca>
# Date 1267986530 18000
# Node ID 387ca8b2956255b86c653e9bb0ead2f1e0b9a5bc
# Parent  29b1e84ebeb75cc96537c789fbe5af9b4931b18c
shrink-revlog: add "reverse postorder" and "postorder reverse" toposorts.

Based on a patch by Benoit Boissinot, adapted to the pluggable sort
algorithm design.  toposort_reversepostorder() appears to be
equivalent to my toposort_parentdelta(), except it's closer to the
textbook algorithm.

diff --git a/contrib/shrink-revlog.py b/contrib/shrink-revlog.py
--- a/contrib/shrink-revlog.py
+++ b/contrib/shrink-revlog.py
@@ -149,6 +149,93 @@
     result.reverse()
     return result
 
+def toposort_reversepostorder(ui, rl):
+    # postorder of the reverse directed graph
+
+    # map rev to list of parent revs (p2 first)
+    parents = {}
+    heads = set()
+    ui.write('reading %d revs ' % len(rl))
+    try:
+        for rev in rl:
+            (p1, p2) = rl.parentrevs(rev)
+            if p1 == p2 == node.nullrev:
+                parents[rev] = ()       # root node
+            elif p1 == p2 or p2 == node.nullrev:
+                parents[rev] = (p1,)    # normal node
+            else:
+                parents[rev] = (p2, p1) # merge node
+
+            heads.add(rev)
+
+            for p in parents[rev]:
+                heads.discard(p)
+
+            if rev % 1000 == 0:
+                ui.write('.')
+    finally:
+        ui.write('\n')
+
+    ui.write('sorting ...')
+    result = []
+    visit = list(heads)
+    visit.sort(reverse=True)
+    finished = set()
+
+    while visit:
+        cur = visit[-1]
+        for p in parents[cur]:
+            if p not in finished:
+                visit.append(p)
+                break
+        else:
+            result.append(cur)
+            finished.add(cur)
+            visit.pop()
+    return result
+
+def toposort_postorderreverse(ui, rl):
+    # reverse-postorder of the reverse directed graph
+
+    children = {}
+    roots = set()
+    ui.write('reading %d revs ' % len(rl))
+    try:
+        for rev in rl:
+            (p1, p2) = rl.parentrevs(rev)
+            if p1 == p2 == node.nullrev:
+                roots.add(rev)
+
+            children[rev] = []
+
+            if p1 != node.nullrev:
+                children[p1].append(rev)
+            if p2 != node.nullrev:
+                children[p2].append(rev)
+
+            if rev % 1000 == 0:
+                ui.write('.')
+    finally:
+        ui.write('\n')
+
+    ui.write('sorting ...\n')
+    result = []
+    visit = list(roots)
+    visit.sort()
+    finished = set()
+    while visit:
+        cur = visit[-1]
+        for p in children[cur]:
+            if p not in finished:
+                visit.append(p)
+                break
+        else:
+            result.append(cur)
+            finished.add(cur)
+            visit.pop()
+    result.reverse()
+    return result
+
 def writerevs(ui, r1, r2, order, tr):
 
     ui.status(_('writing revs\n'))