Mercurial > hg
diff mercurial/ancestor.py @ 3135:b1db258e875c
Abstract ancestor algorithm into generic function
Make depth calculation non-recursive
Add simple shortcut for linear ancestry
Convert context to use ancestor function
make memoized parents function
Convert revlog to use ancestor function
author | Matt Mackall <mpm@selenic.com> |
---|---|
date | Wed, 20 Sep 2006 16:50:50 -0500 |
parents | |
children | eb0b4a2d70a9 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/mercurial/ancestor.py Wed Sep 20 16:50:50 2006 -0500 @@ -0,0 +1,83 @@ +# 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, incorporated herein by reference. + +import heapq + +def ancestor(a, b, pfunc): + """ + return the least common ancestor of nodes a and b or None if there + is no such ancestor. + + pfunc must return a list of parent vertices + """ + + if a == b: + return a + + # find depth from root of all ancestors + visit = [a, b] + depth = {} + while visit: + vertex = visit[-1] + pl = pfunc(vertex) + 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 = {} + while h: + d, n = heapq.heappop(h) + if n not in seen: + seen[n] = 1 + yield (d, n) + for p in pfunc(n): + heapq.heappush(h, (depth[p], p)) + + def generations(vertex): + sg, s = None, {} + for g,v in ancestors(vertex): + if g != sg: + if sg: + yield sg, s + sg, s = g, {v:1} + else: + s[v] = 1 + 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