Show More
@@ -9,6 +9,62 b' import heapq' | |||
|
9 | 9 | import util |
|
10 | 10 | from node import nullrev |
|
11 | 11 | |
|
12 | def commonancestorsheads(pfunc, *nodes): | |
|
13 | """Returns a set with the heads of all common ancestors of all nodes, | |
|
14 | heads(::nodes[0] and ::nodes[1] and ...) . | |
|
15 | ||
|
16 | pfunc must return a list of parent vertices for a given vertex. | |
|
17 | """ | |
|
18 | if not isinstance(nodes, set): | |
|
19 | nodes = set(nodes) | |
|
20 | if nullrev in nodes: | |
|
21 | return set() | |
|
22 | if len(nodes) <= 1: | |
|
23 | return nodes | |
|
24 | ||
|
25 | allseen = (1 << len(nodes)) - 1 | |
|
26 | seen = [0] * (max(nodes) + 1) | |
|
27 | for i, n in enumerate(nodes): | |
|
28 | seen[n] = 1 << i | |
|
29 | poison = 1 << (i + 1) | |
|
30 | ||
|
31 | gca = set() | |
|
32 | interesting = len(nodes) | |
|
33 | nv = len(seen) - 1 | |
|
34 | while nv >= 0 and interesting: | |
|
35 | v = nv | |
|
36 | nv -= 1 | |
|
37 | if not seen[v]: | |
|
38 | continue | |
|
39 | sv = seen[v] | |
|
40 | if sv < poison: | |
|
41 | interesting -= 1 | |
|
42 | if sv == allseen: | |
|
43 | gca.add(v) | |
|
44 | sv |= poison | |
|
45 | if v in nodes: | |
|
46 | # history is linear | |
|
47 | return set([v]) | |
|
48 | if sv < poison: | |
|
49 | for p in pfunc(v): | |
|
50 | sp = seen[p] | |
|
51 | if p == nullrev: | |
|
52 | continue | |
|
53 | if sp == 0: | |
|
54 | seen[p] = sv | |
|
55 | interesting += 1 | |
|
56 | elif sp != sv: | |
|
57 | seen[p] |= sv | |
|
58 | else: | |
|
59 | for p in pfunc(v): | |
|
60 | if p == nullrev: | |
|
61 | continue | |
|
62 | sp = seen[p] | |
|
63 | if sp and sp < poison: | |
|
64 | interesting -= 1 | |
|
65 | seen[p] = sv | |
|
66 | return gca | |
|
67 | ||
|
12 | 68 | def ancestors(pfunc, *orignodes): |
|
13 | 69 | """ |
|
14 | 70 | Returns the common ancestors of a and b that are furthest from a |
@@ -16,57 +72,6 b' def ancestors(pfunc, *orignodes):' | |||
|
16 | 72 | |
|
17 | 73 | pfunc must return a list of parent vertices for a given vertex. |
|
18 | 74 | """ |
|
19 | if not isinstance(orignodes, set): | |
|
20 | orignodes = set(orignodes) | |
|
21 | if nullrev in orignodes: | |
|
22 | return set() | |
|
23 | if len(orignodes) <= 1: | |
|
24 | return orignodes | |
|
25 | ||
|
26 | def candidates(nodes): | |
|
27 | allseen = (1 << len(nodes)) - 1 | |
|
28 | seen = [0] * (max(nodes) + 1) | |
|
29 | for i, n in enumerate(nodes): | |
|
30 | seen[n] = 1 << i | |
|
31 | poison = 1 << (i + 1) | |
|
32 | ||
|
33 | gca = set() | |
|
34 | interesting = len(nodes) | |
|
35 | nv = len(seen) - 1 | |
|
36 | while nv >= 0 and interesting: | |
|
37 | v = nv | |
|
38 | nv -= 1 | |
|
39 | if not seen[v]: | |
|
40 | continue | |
|
41 | sv = seen[v] | |
|
42 | if sv < poison: | |
|
43 | interesting -= 1 | |
|
44 | if sv == allseen: | |
|
45 | gca.add(v) | |
|
46 | sv |= poison | |
|
47 | if v in nodes: | |
|
48 | # history is linear | |
|
49 | return set([v]) | |
|
50 | if sv < poison: | |
|
51 | for p in pfunc(v): | |
|
52 | sp = seen[p] | |
|
53 | if p == nullrev: | |
|
54 | continue | |
|
55 | if sp == 0: | |
|
56 | seen[p] = sv | |
|
57 | interesting += 1 | |
|
58 | elif sp != sv: | |
|
59 | seen[p] |= sv | |
|
60 | else: | |
|
61 | for p in pfunc(v): | |
|
62 | if p == nullrev: | |
|
63 | continue | |
|
64 | sp = seen[p] | |
|
65 | if sp and sp < poison: | |
|
66 | interesting -= 1 | |
|
67 | seen[p] = sv | |
|
68 | return gca | |
|
69 | ||
|
70 | 75 | def deepest(nodes): |
|
71 | 76 | interesting = {} |
|
72 | 77 | count = max(nodes) + 1 |
@@ -123,7 +128,7 b' def ancestors(pfunc, *orignodes):' | |||
|
123 | 128 | k |= i |
|
124 | 129 | return set(n for (i, n) in mapping if k & i) |
|
125 | 130 | |
|
126 |
gca = c |
|
|
131 | gca = commonancestorsheads(pfunc, *orignodes) | |
|
127 | 132 | |
|
128 | 133 | if len(gca) <= 1: |
|
129 | 134 | return gca |
General Comments 0
You need to be logged in to leave comments.
Login now