|
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 or any later version. |
|
7 |
|
8 import heapq |
|
9 |
|
10 def ancestor(a, b, pfunc): |
|
11 """ |
|
12 return a minimal-distance ancestor of nodes a and b, or None if there is no |
|
13 such ancestor. Note that there can be several ancestors with the same |
|
14 (minimal) distance, and the one returned is arbitrary. |
|
15 |
|
16 pfunc must return a list of parent vertices for a given vertex |
|
17 """ |
|
18 |
|
19 if a == b: |
|
20 return a |
|
21 |
|
22 a, b = sorted([a, b]) |
|
23 |
|
24 # find depth from root of all ancestors |
|
25 parentcache = {} |
|
26 visit = [a, b] |
|
27 depth = {} |
|
28 while visit: |
|
29 vertex = visit[-1] |
|
30 pl = pfunc(vertex) |
|
31 parentcache[vertex] = pl |
|
32 if not pl: |
|
33 depth[vertex] = 0 |
|
34 visit.pop() |
|
35 else: |
|
36 for p in pl: |
|
37 if p == a or p == b: # did we find a or b as a parent? |
|
38 return p # we're done |
|
39 if p not in depth: |
|
40 visit.append(p) |
|
41 if visit[-1] == vertex: |
|
42 depth[vertex] = min([depth[p] for p in pl]) - 1 |
|
43 visit.pop() |
|
44 |
|
45 # traverse ancestors in order of decreasing distance from root |
|
46 def ancestors(vertex): |
|
47 h = [(depth[vertex], vertex)] |
|
48 seen = set() |
|
49 while h: |
|
50 d, n = heapq.heappop(h) |
|
51 if n not in seen: |
|
52 seen.add(n) |
|
53 yield (d, n) |
|
54 for p in parentcache[n]: |
|
55 heapq.heappush(h, (depth[p], p)) |
|
56 |
|
57 def generations(vertex): |
|
58 sg, s = None, set() |
|
59 for g, v in ancestors(vertex): |
|
60 if g != sg: |
|
61 if sg: |
|
62 yield sg, s |
|
63 sg, s = g, set((v,)) |
|
64 else: |
|
65 s.add(v) |
|
66 yield sg, s |
|
67 |
|
68 x = generations(a) |
|
69 y = generations(b) |
|
70 gx = x.next() |
|
71 gy = y.next() |
|
72 |
|
73 # increment each ancestor list until it is closer to root than |
|
74 # the other, or they match |
|
75 try: |
|
76 while 1: |
|
77 if gx[0] == gy[0]: |
|
78 for v in gx[1]: |
|
79 if v in gy[1]: |
|
80 return v |
|
81 gy = y.next() |
|
82 gx = x.next() |
|
83 elif gx[0] > gy[0]: |
|
84 gy = y.next() |
|
85 else: |
|
86 gx = x.next() |
|
87 except StopIteration: |
|
88 return None |