|
135
|
1 # ancestor.py - generic DAG ancestor algorithm for mercurial
|
|
|
2 #
|
|
|
3 # Copyright 2006 Matt Mackall <mpm@selenic.com>
|
|
|
4 #
|
|
|
5 # This software may be used and distributed according to the terms of the
|
|
|
6 # GNU General Public License version 2, incorporated herein by reference.
|
|
|
7
|
|
|
8 import heapq
|
|
|
9
|
|
|
10 def ancestor(a, b, pfunc):
|
|
|
11 """
|
|
|
12 return the least common ancestor of nodes a and b or None if there
|
|
|
13 is no such ancestor.
|
|
|
14
|
|
|
15 pfunc must return a list of parent vertices
|
|
|
16 """
|
|
|
17
|
|
|
18 if a == b:
|
|
|
19 return a
|
|
|
20
|
|
|
21 # find depth from root of all ancestors
|
|
|
22 parentcache = {}
|
|
|
23 visit = [a, b]
|
|
|
24 depth = {}
|
|
|
25 while visit:
|
|
|
26 vertex = visit[-1]
|
|
|
27 pl = pfunc(vertex)
|
|
|
28 parentcache[vertex] = pl
|
|
|
29 if not pl:
|
|
|
30 depth[vertex] = 0
|
|
|
31 visit.pop()
|
|
|
32 else:
|
|
|
33 for p in pl:
|
|
|
34 if p == a or p == b: # did we find a or b as a parent?
|
|
|
35 return p # we're done
|
|
|
36 if p not in depth:
|
|
|
37 visit.append(p)
|
|
|
38 if visit[-1] == vertex:
|
|
|
39 depth[vertex] = min([depth[p] for p in pl]) - 1
|
|
|
40 visit.pop()
|
|
|
41
|
|
|
42 # traverse ancestors in order of decreasing distance from root
|
|
|
43 def ancestors(vertex):
|
|
|
44 h = [(depth[vertex], vertex)]
|
|
|
45 seen = set()
|
|
|
46 while h:
|
|
|
47 d, n = heapq.heappop(h)
|
|
|
48 if n not in seen:
|
|
|
49 seen.add(n)
|
|
|
50 yield (d, n)
|
|
|
51 for p in parentcache[n]:
|
|
|
52 heapq.heappush(h, (depth[p], p))
|
|
|
53
|
|
|
54 def generations(vertex):
|
|
|
55 sg, s = None, set()
|
|
|
56 for g, v in ancestors(vertex):
|
|
|
57 if g != sg:
|
|
|
58 if sg:
|
|
|
59 yield sg, s
|
|
|
60 sg, s = g, set((v,))
|
|
|
61 else:
|
|
|
62 s.add(v)
|
|
|
63 yield sg, s
|
|
|
64
|
|
|
65 x = generations(a)
|
|
|
66 y = generations(b)
|
|
|
67 gx = x.next()
|
|
|
68 gy = y.next()
|
|
|
69
|
|
|
70 # increment each ancestor list until it is closer to root than
|
|
|
71 # the other, or they match
|
|
|
72 try:
|
|
|
73 while 1:
|
|
|
74 if gx[0] == gy[0]:
|
|
|
75 for v in gx[1]:
|
|
|
76 if v in gy[1]:
|
|
|
77 return v
|
|
|
78 gy = y.next()
|
|
|
79 gx = x.next()
|
|
|
80 elif gx[0] > gy[0]:
|
|
|
81 gy = y.next()
|
|
|
82 else:
|
|
|
83 gx = x.next()
|
|
|
84 except StopIteration:
|
|
|
85 return None
|
