Show More
@@ -154,6 +154,32 b' class incrementalmissingancestors(object' | |||
|
154 | 154 | '''grow the ancestor set by adding new bases''' |
|
155 | 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 | 183 | def missingancestors(self, revs): |
|
158 | 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 | 47 | self.bases = set(bases) |
|
48 | 48 | def addbases(self, newbases): |
|
49 | 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 | 55 | def missingancestors(self, revs): |
|
51 | 56 | res = set() |
|
52 | 57 | for rev in revs: |
@@ -98,12 +103,25 b' def test_missingancestors(seed, rng):' | |||
|
98 | 103 | # reference slow algorithm |
|
99 | 104 | naiveinc = naiveincrementalmissingancestors(ancs, bases) |
|
100 | 105 | seq = [] |
|
106 | revs = [] | |
|
101 | 107 | for _ in xrange(inccount): |
|
102 | 108 | if rng.random() < 0.2: |
|
103 | 109 | newbases = samplerevs(graphnodes) |
|
104 | 110 | seq.append(('addbases', newbases)) |
|
105 | 111 | inc.addbases(newbases) |
|
106 | 112 | naiveinc.addbases(newbases) |
|
113 | if rng.random() < 0.4: | |
|
114 | # larger set so that there are more revs to remove from | |
|
115 | revs = samplerevs(graphnodes, mu=1.5) | |
|
116 | seq.append(('removeancestorsfrom', revs)) | |
|
117 | hrevs = set(revs) | |
|
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: | |
|
107 | 125 | revs = samplerevs(graphnodes) |
|
108 | 126 | seq.append(('missingancestors', revs)) |
|
109 | 127 | h = inc.missingancestors(revs) |
General Comments 0
You need to be logged in to leave comments.
Login now