Mercurial > hg
comparison 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 |
comparison
equal
deleted
inserted
replaced
3134:abd9a05fca0b | 3135:b1db258e875c |
---|---|
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 | |
6 # of the GNU General Public License, 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 visit = [a, b] | |
23 depth = {} | |
24 while visit: | |
25 vertex = visit[-1] | |
26 pl = pfunc(vertex) | |
27 if not pl: | |
28 depth[vertex] = 0 | |
29 visit.pop() | |
30 else: | |
31 for p in pl: | |
32 if p == a or p == b: # did we find a or b as a parent? | |
33 return p # we're done | |
34 if p not in depth: | |
35 visit.append(p) | |
36 if visit[-1] == vertex: | |
37 depth[vertex] = min([depth[p] for p in pl]) - 1 | |
38 visit.pop() | |
39 | |
40 # traverse ancestors in order of decreasing distance from root | |
41 def ancestors(vertex): | |
42 h = [(depth[vertex], vertex)] | |
43 seen = {} | |
44 while h: | |
45 d, n = heapq.heappop(h) | |
46 if n not in seen: | |
47 seen[n] = 1 | |
48 yield (d, n) | |
49 for p in pfunc(n): | |
50 heapq.heappush(h, (depth[p], p)) | |
51 | |
52 def generations(vertex): | |
53 sg, s = None, {} | |
54 for g,v in ancestors(vertex): | |
55 if g != sg: | |
56 if sg: | |
57 yield sg, s | |
58 sg, s = g, {v:1} | |
59 else: | |
60 s[v] = 1 | |
61 yield sg, s | |
62 | |
63 x = generations(a) | |
64 y = generations(b) | |
65 gx = x.next() | |
66 gy = y.next() | |
67 | |
68 # increment each ancestor list until it is closer to root than | |
69 # the other, or they match | |
70 try: | |
71 while 1: | |
72 if gx[0] == gy[0]: | |
73 for v in gx[1]: | |
74 if v in gy[1]: | |
75 return v | |
76 gy = y.next() | |
77 gx = x.next() | |
78 elif gx[0] > gy[0]: | |
79 gy = y.next() | |
80 else: | |
81 gx = x.next() | |
82 except StopIteration: | |
83 return None |