The Quantum Exact Simulation Toolkit v4.2.0
Loading...
Searching...
No Matches
lists.cpp
1/** @file
2 * Testing utilities which generate lists of integers.
3 *
4 * @author Tyson Jones
5 */
6
7#include <catch2/generators/catch_generators.hpp>
8#include <catch2/generators/catch_generators_range.hpp>
9#include <catch2/generators/catch_generators_adapters.hpp>
10
11#include "quest.h"
12
13#include "config.hpp"
14#include "lists.hpp"
15#include "macros.hpp"
16#include "random.hpp"
17#include "linalg.hpp"
18
19#include <tuple>
20#include <vector>
21#include <limits>
22#include <algorithm>
23
24using std::tuple;
25using std::vector;
26
27using Catch::Generators::IGenerator;
28using Catch::Generators::GeneratorWrapper;
29
30
31
32/*
33 * PRIVATE
34 */
35
36
37vector<int> getGeneratorElems(GeneratorWrapper<int>& gen) {
38
39 vector<int> list;
40 do { list.push_back(gen.get()); } while (gen.next());
41
42 return list;
43}
44
45
46
47/*
48 * SUBLISTS
49 */
50
51
52vector<int> getSublist(vector<int> list, int start, int len) {
53
54 return vector<int>(list.begin() + start, list.begin() + start + len);
55}
56
57
58vector<qcomp> getSublist(vector<qcomp> list, int start, int len) {
59
60 return vector<qcomp>(list.begin() + start, list.begin() + start + len);
61}
62
63
64
65/*
66 * RANGE
67 */
68
69
70vector<int> getRange(int start, int endExcl) {
71 DEMAND( endExcl >= start );
72
73 vector<int> out(endExcl - start);
74
75 for (size_t i=0; i<out.size(); i++)
76 out[i] = start + i;
77
78 return out;
79}
80
81
82vector<int> getRange(int endExcl) {
83 return getRange(0, endExcl);
84}
85
86
87
88/*
89 * COMPLEMENTS
90 */
91
92
93vector<int> getComplement(vector<int> listA, vector<int> listB) {
94
95 std::sort(listA.begin(), listA.end());
96 std::sort(listB.begin(), listB.end());
97
98 vector<int> out;
99 std::set_difference(
100 listA.begin(), listA.end(),
101 listB.begin(), listB.end(),
102 std::back_inserter(out));
103
104 return out;
105}
106
107
108
109/*
110 * SUBLIST GENERATORs
111 */
112
113
114/// @private
115class SublistGenerator final : public IGenerator<vector<int>> {
116
117 // list of all possible (unique) elements
118 vector<int> list;
119
120 // output sublist of user-specified length
121 int sublen;
122 vector<int> sublist;
123
124 // indicates which elements of list are in sublist
125 vector<bool> featured;
126
127private:
128
129 void prepareSublist() {
130
131 // choose the next combination
132 int j=0;
133 for (size_t i=0; i<list.size(); i++)
134 if (featured[i])
135 sublist[j++] = list[i];
136
137 // prepare for permuting
138 std::sort(sublist.begin(), sublist.end());
139 }
140
141public:
142
143 SublistGenerator(vector<int> list, int sublen):
144 list(list),
145 sublen(sublen)
146 {
147 // ensure sublist would not be longer than list
148 DEMAND( sublen <= list.size() );
149
150 // populate sublist with first elements
151 sublist.resize(sublen);
152 featured.resize(list.size());
153 fill(featured.end() - sublen, featured.end(), true);
154
155 prepareSublist();
156 }
157
158 vector<int> const& get() const override {
159
160 // return a copy of sublist
161 return sublist;
162 }
163
164 bool next() override {
165
166 // offer next permutation of the current combination
167 if (std::next_permutation(sublist.begin(), sublist.end()))
168 return true;
169
170 // else generate the next combination
171 if (std::next_permutation(featured.begin(), featured.end())) {
172
173 prepareSublist();
174 return true;
175 }
176
177 // else indicate generator is exhausted
178 return false;
179 }
180};
181
182
183GeneratorWrapper<vector<int>> sublists(GeneratorWrapper<int>&& gen, int sublen) {
184
185 vector<int> list;
186 do { list.push_back(gen.get()); } while (gen.next());
187
188 return GeneratorWrapper<vector<int>>(
189 Catch::Detail::make_unique<SublistGenerator>(
190 list, sublen));
191}
192
193
194
195/*
196 * DISJOINT SUBLISTS GENERATOR
197 */
198
199
200/// @private
201class DisjointSublistsGenerator : public IGenerator<listpair> {
202
203 // list of all possible (unique) elements
204 vector<int> list;
205
206 // lengths of each sublist
207 int sublen1;
208 int sublen2;
209 listpair sublists;
210
211 // underlying generator
212 SublistGenerator subGen;
213
214public:
215
216 DisjointSublistsGenerator(vector<int> list, int sublen1, int sublen2):
217 list(list),
218 sublen1(sublen1),
219 sublen2(sublen2),
220 subGen(list, sublen1 + sublen2)
221 {
222 static_cast<void>(next()); // ignore bool return
223 }
224
225 listpair const& get() const override {
226 return sublists;
227 }
228
229 bool next() override {
230
231 // stop when sublist generator is exhausted
232 if (!subGen.next())
233 return false;
234
235 // else, obtain the next (sublist) sequence
236 vector<int> combined = subGen.get();
237 vector<int> sublist1 = getSublist(combined, 0, sublen1);
238 vector<int> sublist2 = getSublist(combined, sublen1, sublen2);
239
240 sublists = {sublist1, sublist2};
241 return true;
242 }
243};
244
245
246GeneratorWrapper<listpair> disjointsublists(GeneratorWrapper<int>&& gen, int sublen1, int sublen2) {
247
248 vector<int> list;
249 do { list.push_back(gen.get()); } while (gen.next());
250
251 return GeneratorWrapper<listpair>(
252 Catch::Detail::make_unique<DisjointSublistsGenerator>(
253 list, sublen1, sublen2));
254}
255
256
257
258/*
259 * GENERATOR WRAPPERS
260 */
261
262
263listpair GENERATE_CTRLS_AND_TARGS(int numQubits, int numCtrls, int numTargs) {
264 DEMAND( numQubits >= numCtrls + numTargs );
265
266 // impose a limit on the number of {ctrls,targs} to generate (max-int if none set)
267 int numPerms = getNumPermutations(numQubits, numCtrls + numTargs);
268 int maxPerms = getMaxNumTestedQubitPermutations();
269 if (maxPerms == 0)
270 maxPerms = std::numeric_limits<int>::max();
271
272 // if all permutations are permitted, determinstically generate each in turn.
273 // note this wastefully generates all orderings of ctrl qubits, despite that
274 // this has no effect on all API operations, but we carefully check anyway!
275 if (numPerms < maxPerms)
276 return GENERATE_COPY( disjointsublists(range(0,numQubits), numCtrls, numTargs) );
277
278 // otherwise generate as many random {ctrls,targs} as permitted
279 GENERATE_COPY( range(0,maxPerms) );
280 return getRandomFixedNumCtrlsTargs(numQubits, numCtrls, numTargs);
281}
282
283
284vector<int> GENERATE_TARGS(int numQubits, int numTargs) {
285 DEMAND( numQubits >= numTargs );
286
287 auto [ctrls, targs] = GENERATE_CTRLS_AND_TARGS(numQubits, 0, numTargs);
288 return targs;
289}