equal
deleted
inserted
replaced
56 perfect = tot / 2 |
56 perfect = tot / 2 |
57 |
57 |
58 # find the best node to test |
58 # find the best node to test |
59 best_rev = None |
59 best_rev = None |
60 best_len = -1 |
60 best_len = -1 |
|
61 poison = {} |
61 for rev in candidates: |
62 for rev in candidates: |
|
63 if rev in poison: |
|
64 for c in children.get(rev, []): |
|
65 poison[c] = True # poison children |
|
66 continue |
62 l = ancestors[rev] |
67 l = ancestors[rev] |
63 ancestors[rev] = None |
68 ancestors[rev] = None |
64 if l != None: |
69 if l != None: |
65 if not l: |
70 if not l: |
66 a = [rev] |
71 a = [rev] |
70 a = {} |
75 a = {} |
71 for s in l: |
76 for s in l: |
72 a.update(dict.fromkeys(s)) |
77 a.update(dict.fromkeys(s)) |
73 a[rev] = None |
78 a[rev] = None |
74 a = a.keys() |
79 a = a.keys() |
|
80 |
|
81 x = len(a) # number of ancestors |
|
82 y = tot - x # number of non-ancestors |
|
83 value = min(x, y) # how good is this test? |
|
84 if value > best_len and rev not in skip: |
|
85 best_len = value |
|
86 best_rev = rev |
|
87 if value == perfect: # found a perfect candidate? quit early |
|
88 break |
|
89 |
|
90 if y < perfect: # all downhill from here? |
|
91 for c in children.get(rev, []): |
|
92 poison[c] = True # poison children |
|
93 continue |
|
94 |
75 for c in children.get(rev, []): |
95 for c in children.get(rev, []): |
76 if ancestors[c]: |
96 if ancestors[c]: |
77 ancestors[c].append(a) |
97 ancestors[c].append(a) |
78 else: |
98 else: |
79 ancestors[c] = [a] |
99 ancestors[c] = [a] |
80 if n in skip: |
|
81 continue |
|
82 a = len(a) # number of ancestors |
|
83 b = tot - a # number of non-ancestors |
|
84 value = min(a, b) # how good is this test? |
|
85 if value > best_len: |
|
86 best_len = value |
|
87 best_rev = rev |
|
88 if value == perfect: # found a perfect candidate? quit early |
|
89 break |
|
90 |
100 |
91 assert best_rev is not None |
101 assert best_rev is not None |
92 best_node = changelog.node(best_rev) |
102 best_node = changelog.node(best_rev) |
93 |
103 |
94 return (best_node, tot) |
104 return (best_node, tot) |