annotate mercurial/ancestor.py @ 11717:a286a4ecbfeb

Merge with stable
author Matt Mackall <mpm@selenic.com>
date Sat, 31 Jul 2010 18:12:50 -0500
parents 67bb9d78f05e
children 4f8067c94729
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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 #
8225
46293a0c7e9f updated license to be explicit about GPL version 2
Martin Geisler <mg@lazybytes.net>
parents: 7882
diff changeset
5 # This software may be used and distributed according to the terms of the
10263
25e572394f5c Update license to GPLv2+
Matt Mackall <mpm@selenic.com>
parents: 8465
diff changeset
6 # GNU General Public License version 2 or any later version.
3135
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 """
9915
806e6b6cb8d8 ancestor: improve docstring
Sune Foldager <cryo@cyanite.org>
parents: 8465
diff changeset
12 return a minimal-distance ancestor of nodes a and b, or None if there is no
806e6b6cb8d8 ancestor: improve docstring
Sune Foldager <cryo@cyanite.org>
parents: 8465
diff changeset
13 such ancestor. Note that there can be several ancestors with the same
806e6b6cb8d8 ancestor: improve docstring
Sune Foldager <cryo@cyanite.org>
parents: 8465
diff changeset
14 (minimal) distance, and the one returned is arbitrary.
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
15
9915
806e6b6cb8d8 ancestor: improve docstring
Sune Foldager <cryo@cyanite.org>
parents: 8465
diff changeset
16 pfunc must return a list of parent vertices for a given vertex
3135
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
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
19 if a == b:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
20 return a
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
21
11418
67bb9d78f05e merge: sort arguments to stabilize the ancestor search
Matt Mackall <mpm@selenic.com>
parents: 10264
diff changeset
22 a, b = sorted([a, b])
67bb9d78f05e merge: sort arguments to stabilize the ancestor search
Matt Mackall <mpm@selenic.com>
parents: 10264
diff changeset
23
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
24 # 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
25 parentcache = {}
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
26 visit = [a, b]
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
27 depth = {}
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
28 while visit:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
29 vertex = visit[-1]
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
30 pl = pfunc(vertex)
7882
8d78fc991b71 ancestor: caching the parent list to improve performance
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 6429
diff changeset
31 parentcache[vertex] = pl
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
32 if not pl:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
33 depth[vertex] = 0
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
34 visit.pop()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
35 else:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
36 for p in pl:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
37 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
38 return p # we're done
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
39 if p not in depth:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
40 visit.append(p)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
41 if visit[-1] == vertex:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
42 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
43 visit.pop()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
44
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
45 # traverse ancestors in order of decreasing distance from root
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
46 def ancestors(vertex):
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
47 h = [(depth[vertex], vertex)]
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
48 seen = set()
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
49 while h:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
50 d, n = heapq.heappop(h)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
51 if n not in seen:
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
52 seen.add(n)
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
53 yield (d, n)
7882
8d78fc991b71 ancestor: caching the parent list to improve performance
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 6429
diff changeset
54 for p in parentcache[n]:
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
55 heapq.heappush(h, (depth[p], p))
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
56
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
57 def generations(vertex):
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
58 sg, s = None, set()
3673
eb0b4a2d70a9 white space and line break cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents: 3135
diff changeset
59 for g, v in ancestors(vertex):
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
60 if g != sg:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
61 if sg:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
62 yield sg, s
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
63 sg, s = g, set((v,))
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
64 else:
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
65 s.add(v)
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
66 yield sg, s
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
67
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
68 x = generations(a)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
69 y = generations(b)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
70 gx = x.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
71 gy = y.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
72
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
73 # 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
74 # the other, or they match
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
75 try:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
76 while 1:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
77 if gx[0] == gy[0]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
78 for v in gx[1]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
79 if v in gy[1]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
80 return v
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 gx = x.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
83 elif gx[0] > gy[0]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
84 gy = y.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
85 else:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
86 gx = x.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
87 except StopIteration:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
88 return None