Mercurial > hg
annotate mercurial/ancestor.py @ 7983:7b813bdbd5d0
Change double spaces to single spaces in help texts.
author | Martin Geisler <mg@daimi.au.dk> |
---|---|
date | Sat, 04 Apr 2009 21:09:43 +0200 |
parents | 8d78fc991b71 |
children | 46293a0c7e9f |
rev | line source |
---|---|
3135
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
1 # ancestor.py - generic DAG ancestor algorithm for mercurial |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
2 # |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
3 # Copyright 2006 Matt Mackall <mpm@selenic.com> |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
4 # |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
5 # This software may be used and distributed according to the terms |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
6 # of the GNU General Public License, incorporated herein by reference. |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
7 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
8 import heapq |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
9 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
10 def ancestor(a, b, pfunc): |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
11 """ |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
12 return the least common ancestor of nodes a and b or None if there |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
13 is no such ancestor. |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
14 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
15 pfunc must return a list of parent vertices |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
16 """ |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
17 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
18 if a == b: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
19 return a |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
20 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
21 # find depth from root of all ancestors |
7882
8d78fc991b71
ancestor: caching the parent list to improve performance
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
6429
diff
changeset
|
22 parentcache = {} |
3135
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
23 visit = [a, b] |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
24 depth = {} |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
25 while visit: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
26 vertex = visit[-1] |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
27 pl = pfunc(vertex) |
7882
8d78fc991b71
ancestor: caching the parent list to improve performance
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
6429
diff
changeset
|
28 parentcache[vertex] = pl |
3135
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
29 if not pl: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
30 depth[vertex] = 0 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
31 visit.pop() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
32 else: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
33 for p in pl: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
34 if p == a or p == b: # did we find a or b as a parent? |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
35 return p # we're done |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
36 if p not in depth: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
37 visit.append(p) |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
38 if visit[-1] == vertex: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
39 depth[vertex] = min([depth[p] for p in pl]) - 1 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
40 visit.pop() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
41 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
42 # traverse ancestors in order of decreasing distance from root |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
43 def ancestors(vertex): |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
44 h = [(depth[vertex], vertex)] |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
45 seen = {} |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
46 while h: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
47 d, n = heapq.heappop(h) |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
48 if n not in seen: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
49 seen[n] = 1 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
50 yield (d, n) |
7882
8d78fc991b71
ancestor: caching the parent list to improve performance
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents:
6429
diff
changeset
|
51 for p in parentcache[n]: |
3135
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
52 heapq.heappush(h, (depth[p], p)) |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
53 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
54 def generations(vertex): |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
55 sg, s = None, {} |
3673
eb0b4a2d70a9
white space and line break cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3135
diff
changeset
|
56 for g, v in ancestors(vertex): |
3135
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
57 if g != sg: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
58 if sg: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
59 yield sg, s |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
60 sg, s = g, {v:1} |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
61 else: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
62 s[v] = 1 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
63 yield sg, s |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
64 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
65 x = generations(a) |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
66 y = generations(b) |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
67 gx = x.next() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
68 gy = y.next() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
69 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
70 # increment each ancestor list until it is closer to root than |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
71 # the other, or they match |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
72 try: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
73 while 1: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
74 if gx[0] == gy[0]: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
75 for v in gx[1]: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
76 if v in gy[1]: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
77 return v |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
78 gy = y.next() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
79 gx = x.next() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
80 elif gx[0] > gy[0]: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
81 gy = y.next() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
82 else: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
83 gx = x.next() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
84 except StopIteration: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
85 return None |