--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/eggs/mercurial-1.7.3-py2.6-linux-x86_64.egg/mercurial/ancestor.py	Sat Jan 08 11:20:57 2011 +0530
@@ -0,0 +1,88 @@
+# ancestor.py - generic DAG ancestor algorithm for mercurial
+#
+# Copyright 2006 Matt Mackall <mpm@selenic.com>
+#
+# This software may be used and distributed according to the terms of the
+# GNU General Public License version 2 or any later version.
+
+import heapq
+
+def ancestor(a, b, pfunc):
+    """
+    return a minimal-distance ancestor of nodes a and b, or None if there is no
+    such ancestor. Note that there can be several ancestors with the same
+    (minimal) distance, and the one returned is arbitrary.
+
+    pfunc must return a list of parent vertices for a given vertex
+    """
+
+    if a == b:
+        return a
+
+    a, b = sorted([a, b])
+
+    # find depth from root of all ancestors
+    parentcache = {}
+    visit = [a, b]
+    depth = {}
+    while visit:
+        vertex = visit[-1]
+        pl = pfunc(vertex)
+        parentcache[vertex] = pl
+        if not pl:
+            depth[vertex] = 0
+            visit.pop()
+        else:
+            for p in pl:
+                if p == a or p == b: # did we find a or b as a parent?
+                    return p # we're done
+                if p not in depth:
+                    visit.append(p)
+            if visit[-1] == vertex:
+                depth[vertex] = min([depth[p] for p in pl]) - 1
+                visit.pop()
+
+    # traverse ancestors in order of decreasing distance from root
+    def ancestors(vertex):
+        h = [(depth[vertex], vertex)]
+        seen = set()
+        while h:
+            d, n = heapq.heappop(h)
+            if n not in seen:
+                seen.add(n)
+                yield (d, n)
+                for p in parentcache[n]:
+                    heapq.heappush(h, (depth[p], p))
+
+    def generations(vertex):
+        sg, s = None, set()
+        for g, v in ancestors(vertex):
+            if g != sg:
+                if sg:
+                    yield sg, s
+                sg, s = g, set((v,))
+            else:
+                s.add(v)
+        yield sg, s
+
+    x = generations(a)
+    y = generations(b)
+    gx = x.next()
+    gy = y.next()
+
+    # increment each ancestor list until it is closer to root than
+    # the other, or they match
+    try:
+        while 1:
+            if gx[0] == gy[0]:
+                for v in gx[1]:
+                    if v in gy[1]:
+                        return v
+                gy = y.next()
+                gx = x.next()
+            elif gx[0] > gy[0]:
+                gy = y.next()
+            else:
+                gx = x.next()
+    except StopIteration:
+        return None