author | Alexis S. L. Carvalho <alexis@cecm.usp.br> |
Thu, 08 Feb 2007 16:31:21 -0200 | |
changeset 4074 | 0f9381cf9723 |
parent 3673 | eb0b4a2d70a9 |
permissions | -rw-r--r-- |
3136
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 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
22 |
visit = [a, b] |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
23 |
depth = {} |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
24 |
while visit: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
25 |
vertex = visit[-1] |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
26 |
pl = pfunc(vertex) |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
27 |
if not pl: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
28 |
depth[vertex] = 0 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
29 |
visit.pop() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
30 |
else: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
31 |
for p in pl: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
32 |
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
|
33 |
return p # we're done |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
34 |
if p not in depth: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
35 |
visit.append(p) |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
36 |
if visit[-1] == vertex: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
37 |
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
|
38 |
visit.pop() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
39 |
|
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
40 |
# traverse ancestors in order of decreasing distance from root |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
41 |
def ancestors(vertex): |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
42 |
h = [(depth[vertex], vertex)] |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
43 |
seen = {} |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
44 |
while h: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
45 |
d, n = heapq.heappop(h) |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
46 |
if n not in seen: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
47 |
seen[n] = 1 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
48 |
yield (d, n) |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
49 |
for p in pfunc(n): |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
50 |
heapq.heappush(h, (depth[p], p)) |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
51 |
|
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
52 |
def generations(vertex): |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
53 |
sg, s = None, {} |
3673
eb0b4a2d70a9
white space and line break cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3136
diff
changeset
|
54 |
for g, v in ancestors(vertex): |
3136
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
55 |
if g != sg: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
56 |
if sg: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
57 |
yield sg, s |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
58 |
sg, s = g, {v:1} |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
59 |
else: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
60 |
s[v] = 1 |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
61 |
yield sg, s |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
62 |
|
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
63 |
x = generations(a) |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
64 |
y = generations(b) |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
65 |
gx = x.next() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
66 |
gy = y.next() |
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 |
# 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
|
69 |
# the other, or they match |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
70 |
try: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
71 |
while 1: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
72 |
if gx[0] == gy[0]: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
73 |
for v in gx[1]: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
74 |
if v in gy[1]: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
75 |
return v |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
76 |
gy = y.next() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
77 |
gx = x.next() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
78 |
elif gx[0] > gy[0]: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
79 |
gy = y.next() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
80 |
else: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
81 |
gx = x.next() |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
82 |
except StopIteration: |
b1db258e875c
Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
83 |
return None |