ancestor: remove unused genericancestor
authorMads Kiilerich <madski@unity3d.com>
Thu, 20 Mar 2014 01:35:07 +0100
changeset 20985 231ccc08670c
parent 20984 f4a87d1ee1aa
child 20986 6ae0c41e4b52
ancestor: remove unused genericancestor
mercurial/ancestor.py
--- a/mercurial/ancestor.py	Mon Apr 07 23:17:48 2014 +0200
+++ b/mercurial/ancestor.py	Thu Mar 20 01:35:07 2014 +0100
@@ -129,89 +129,6 @@
         return gca
     return deepest(gca)
 
-def genericancestor(a, b, pfunc):
-    """
-    Returns the common ancestor of a and b that is furthest from a
-    root (as measured by longest path) or None if no ancestor is
-    found. If there are multiple common ancestors at the same
-    distance, the first one found is returned.
-
-    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
-    # depth is stored as a negative for heapq
-    parentcache = {}
-    visit = [a, b]
-    depth = {}
-    while visit:
-        vertex = visit[-1]
-        pl = [p for p in pfunc(vertex) if p != nullrev]
-        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:
-                # -(maximum distance of parents + 1)
-                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 True:
-            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
-
 def missingancestors(revs, bases, pfunc):
     """Return all the ancestors of revs that are not ancestors of bases.