16 util, |
16 util, |
17 ) |
17 ) |
18 |
18 |
19 if pycompat.ispy3: |
19 if pycompat.ispy3: |
20 long = int |
20 long = int |
21 xrange = range |
|
22 |
21 |
23 |
22 |
24 def buildgraph(rng, nodes=100, rootprob=0.05, mergeprob=0.2, prevprob=0.7): |
23 def buildgraph(rng, nodes=100, rootprob=0.05, mergeprob=0.2, prevprob=0.7): |
25 """nodes: total number of nodes in the graph |
24 """nodes: total number of nodes in the graph |
26 rootprob: probability that a new node (not 0) will be a root |
25 rootprob: probability that a new node (not 0) will be a root |
28 prevprob: probability that p1 will be the previous node |
27 prevprob: probability that p1 will be the previous node |
29 |
28 |
30 return value is a graph represented as an adjacency list. |
29 return value is a graph represented as an adjacency list. |
31 """ |
30 """ |
32 graph = [None] * nodes |
31 graph = [None] * nodes |
33 for i in xrange(nodes): |
32 for i in range(nodes): |
34 if i == 0 or rng.random() < rootprob: |
33 if i == 0 or rng.random() < rootprob: |
35 graph[i] = [nullrev] |
34 graph[i] = [nullrev] |
36 elif i == 1: |
35 elif i == 1: |
37 graph[i] = [0] |
36 graph[i] = [0] |
38 elif rng.random() < mergeprob: |
37 elif rng.random() < mergeprob: |
51 return graph |
50 return graph |
52 |
51 |
53 |
52 |
54 def buildancestorsets(graph): |
53 def buildancestorsets(graph): |
55 ancs = [None] * len(graph) |
54 ancs = [None] * len(graph) |
56 for i in xrange(len(graph)): |
55 for i in range(len(graph)): |
57 ancs[i] = {i} |
56 ancs[i] = {i} |
58 if graph[i] == [nullrev]: |
57 if graph[i] == [nullrev]: |
59 continue |
58 continue |
60 for p in graph[i]: |
59 for p in graph[i]: |
61 ancs[i].update(ancs[p]) |
60 ancs[i].update(ancs[p]) |
112 print('* output: ', output, file=sys.stderr) |
111 print('* output: ', output, file=sys.stderr) |
113 print('* expected:', expected, file=sys.stderr) |
112 print('* expected:', expected, file=sys.stderr) |
114 nerrs[0] += 1 |
113 nerrs[0] += 1 |
115 gerrs[0] += 1 |
114 gerrs[0] += 1 |
116 |
115 |
117 for g in xrange(graphcount): |
116 for g in range(graphcount): |
118 graph = buildgraph(rng) |
117 graph = buildgraph(rng) |
119 ancs = buildancestorsets(graph) |
118 ancs = buildancestorsets(graph) |
120 gerrs = [0] |
119 gerrs = [0] |
121 for _ in xrange(testcount): |
120 for _ in range(testcount): |
122 # start from nullrev to include it as a possibility |
121 # start from nullrev to include it as a possibility |
123 graphnodes = range(nullrev, len(graph)) |
122 graphnodes = range(nullrev, len(graph)) |
124 bases = samplerevs(graphnodes) |
123 bases = samplerevs(graphnodes) |
125 |
124 |
126 # fast algorithm |
125 # fast algorithm |
127 inc = ancestor.incrementalmissingancestors(graph.__getitem__, bases) |
126 inc = ancestor.incrementalmissingancestors(graph.__getitem__, bases) |
128 # reference slow algorithm |
127 # reference slow algorithm |
129 naiveinc = naiveincrementalmissingancestors(ancs, bases) |
128 naiveinc = naiveincrementalmissingancestors(ancs, bases) |
130 seq = [] |
129 seq = [] |
131 for _ in xrange(inccount): |
130 for _ in range(inccount): |
132 if rng.random() < 0.2: |
131 if rng.random() < 0.2: |
133 newbases = samplerevs(graphnodes) |
132 newbases = samplerevs(graphnodes) |
134 seq.append(('addbases', newbases)) |
133 seq.append(('addbases', newbases)) |
135 inc.addbases(newbases) |
134 inc.addbases(newbases) |
136 naiveinc.addbases(newbases) |
135 naiveinc.addbases(newbases) |
213 The bigger graph at the end has been produced by the random generator |
212 The bigger graph at the end has been produced by the random generator |
214 above, and we have some evidence that the other tests don't cover it. |
213 above, and we have some evidence that the other tests don't cover it. |
215 """ |
214 """ |
216 for i, (bases, revs) in enumerate( |
215 for i, (bases, revs) in enumerate( |
217 ( |
216 ( |
218 ({1, 2, 3, 4, 7}, set(xrange(10))), |
217 ({1, 2, 3, 4, 7}, set(range(10))), |
219 ({10}, set({11, 12, 13, 14})), |
218 ({10}, set({11, 12, 13, 14})), |
220 ({7}, set({1, 2, 3, 4, 5})), |
219 ({7}, set({1, 2, 3, 4, 5})), |
221 ) |
220 ) |
222 ): |
221 ): |
223 print("%% removeancestorsfrom(), example %d" % (i + 1)) |
222 print("%% removeancestorsfrom(), example %d" % (i + 1)) |