Show More
@@ -154,6 +154,32 b' class incrementalmissingancestors(object' | |||||
154 | '''grow the ancestor set by adding new bases''' |
|
154 | '''grow the ancestor set by adding new bases''' | |
155 | self.bases.update(newbases) |
|
155 | self.bases.update(newbases) | |
156 |
|
156 | |||
|
157 | def removeancestorsfrom(self, revs): | |||
|
158 | '''remove all ancestors of bases from the set revs (in place)''' | |||
|
159 | bases = self.bases | |||
|
160 | pfunc = self.pfunc | |||
|
161 | revs.difference_update(bases) | |||
|
162 | # nullrev is always an ancestor | |||
|
163 | revs.discard(nullrev) | |||
|
164 | if not revs: | |||
|
165 | return | |||
|
166 | # anything in revs > start is definitely not an ancestor of bases | |||
|
167 | # revs <= start needs to be investigated | |||
|
168 | start = max(bases) | |||
|
169 | keepcount = sum(1 for r in revs if r > start) | |||
|
170 | if len(revs) == keepcount: | |||
|
171 | # no revs to consider | |||
|
172 | return | |||
|
173 | ||||
|
174 | for curr in xrange(start, min(revs) - 1, -1): | |||
|
175 | if curr not in bases: | |||
|
176 | continue | |||
|
177 | revs.discard(curr) | |||
|
178 | bases.update(pfunc(curr)) | |||
|
179 | if len(revs) == keepcount: | |||
|
180 | # no more potential revs to discard | |||
|
181 | break | |||
|
182 | ||||
157 | def missingancestors(self, revs): |
|
183 | def missingancestors(self, revs): | |
158 | '''return all the ancestors of revs that are not ancestors of self.bases |
|
184 | '''return all the ancestors of revs that are not ancestors of self.bases | |
159 |
|
185 |
@@ -47,6 +47,11 b' class naiveincrementalmissingancestors(o' | |||||
47 | self.bases = set(bases) |
|
47 | self.bases = set(bases) | |
48 | def addbases(self, newbases): |
|
48 | def addbases(self, newbases): | |
49 | self.bases.update(newbases) |
|
49 | self.bases.update(newbases) | |
|
50 | def removeancestorsfrom(self, revs): | |||
|
51 | for base in self.bases: | |||
|
52 | if base != nullrev: | |||
|
53 | revs.difference_update(self.ancs[base]) | |||
|
54 | revs.discard(nullrev) | |||
50 | def missingancestors(self, revs): |
|
55 | def missingancestors(self, revs): | |
51 | res = set() |
|
56 | res = set() | |
52 | for rev in revs: |
|
57 | for rev in revs: | |
@@ -98,18 +103,31 b' def test_missingancestors(seed, rng):' | |||||
98 | # reference slow algorithm |
|
103 | # reference slow algorithm | |
99 | naiveinc = naiveincrementalmissingancestors(ancs, bases) |
|
104 | naiveinc = naiveincrementalmissingancestors(ancs, bases) | |
100 | seq = [] |
|
105 | seq = [] | |
|
106 | revs = [] | |||
101 | for _ in xrange(inccount): |
|
107 | for _ in xrange(inccount): | |
102 | if rng.random() < 0.2: |
|
108 | if rng.random() < 0.2: | |
103 | newbases = samplerevs(graphnodes) |
|
109 | newbases = samplerevs(graphnodes) | |
104 | seq.append(('addbases', newbases)) |
|
110 | seq.append(('addbases', newbases)) | |
105 | inc.addbases(newbases) |
|
111 | inc.addbases(newbases) | |
106 | naiveinc.addbases(newbases) |
|
112 | naiveinc.addbases(newbases) | |
107 | revs = samplerevs(graphnodes) |
|
113 | if rng.random() < 0.4: | |
108 | seq.append(('missingancestors', revs)) |
|
114 | # larger set so that there are more revs to remove from | |
109 | h = inc.missingancestors(revs) |
|
115 | revs = samplerevs(graphnodes, mu=1.5) | |
110 | r = naiveinc.missingancestors(revs) |
|
116 | seq.append(('removeancestorsfrom', revs)) | |
111 |
|
|
117 | hrevs = set(revs) | |
112 |
|
|
118 | rrevs = set(revs) | |
|
119 | inc.removeancestorsfrom(hrevs) | |||
|
120 | naiveinc.removeancestorsfrom(rrevs) | |||
|
121 | if hrevs != rrevs: | |||
|
122 | err(seed, graph, bases, seq, sorted(hrevs), | |||
|
123 | sorted(rrevs)) | |||
|
124 | else: | |||
|
125 | revs = samplerevs(graphnodes) | |||
|
126 | seq.append(('missingancestors', revs)) | |||
|
127 | h = inc.missingancestors(revs) | |||
|
128 | r = naiveinc.missingancestors(revs) | |||
|
129 | if h != r: | |||
|
130 | err(seed, graph, bases, seq, h, r) | |||
113 |
|
131 | |||
114 | # graph is a dict of child->parent adjacency lists for this graph: |
|
132 | # graph is a dict of child->parent adjacency lists for this graph: | |
115 | # o 13 |
|
133 | # o 13 |
General Comments 0
You need to be logged in to leave comments.
Login now