45 def __init__(self, ancs, bases): |
45 def __init__(self, ancs, bases): |
46 self.ancs = ancs |
46 self.ancs = ancs |
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: |
53 if rev != nullrev: |
58 if rev != nullrev: |
54 res.update(self.ancs[rev]) |
59 res.update(self.ancs[rev]) |
96 # fast algorithm |
101 # fast algorithm |
97 inc = ancestor.incrementalmissingancestors(graph.__getitem__, bases) |
102 inc = ancestor.incrementalmissingancestors(graph.__getitem__, bases) |
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 if h != r: |
117 hrevs = set(revs) |
112 err(seed, graph, bases, seq, h, r) |
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 |
116 # | |
134 # | |
117 # | o 12 |
135 # | o 12 |