this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
3/*
4 * Main authors:
5 * Jip J. Dekker <jip.dekker@monash.edu>
6 * Guido Tack <guido.tack@monash.edu>
7 */
8
9/* This Source Code Form is subject to the terms of the Mozilla Public
10 * License, v. 2.0. If a copy of the MPL was not distributed with this
11 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
12
13#include <minizinc/interpreter.hh>
14#include <minizinc/interpreter/primitives.hh>
15
16namespace MiniZinc {
17
18namespace BytecodePrimitives {
19IntPlus int_plus;
20IntMinus int_minus;
21IntSum int_sum;
22IntTimes int_times;
23
24IntLinEq int_lin_eq;
25IntLinEqReif int_lin_eq_reif;
26IntLinLe int_lin_le;
27IntLinLeReif int_lin_le_reif;
28
29MkIntVar mk_intvar;
30BoolNot boolnot;
31OpNot opnot;
32Clause clause;
33ClauseReif clause_reif;
34Forall forall;
35Exists exists;
36Uniform uniform;
37Sol sol;
38Sort sort;
39SortBy sortby;
40IntMax intmax;
41Infinity infinity;
42InfiniteDomain inf_dom;
43BooleanDomain bool_dom;
44SliceXd slice_xd;
45ArrayXd array_xd;
46IndexSet index_set;
47
48PrimitiveMap::Primitive* AllPrimitives[] = {
49 &int_plus, &int_minus,
50 &int_sum, &int_times,
51
52 &int_lin_eq, &int_lin_eq_reif,
53 &int_lin_le, &int_lin_le_reif,
54
55 &mk_intvar, &boolnot,
56 &opnot, &clause,
57 &clause_reif, &forall,
58 &exists, &uniform,
59 &sol, &sort,
60 &sortby, &intmax,
61 &infinity, &inf_dom,
62 &bool_dom, &slice_xd,
63 &array_xd, &index_set,
64};
65} // namespace BytecodePrimitives
66
67PrimitiveMap::PrimitiveMap(void) : _p(PrimitiveMap::MAX_ID + 1) {
68 for (PrimitiveMap::Primitive* p : BytecodePrimitives::AllPrimitives) {
69 _p[p->ident()] = p;
70 }
71 for (Primitive* p : _p) {
72 _s.insert(std::make_pair(p->name(), p));
73 }
74 _n.resize(_s.size());
75 for (auto& entry : _s) {
76 _n[entry.second->ident()] = entry.first;
77 }
78}
79
80PrimitiveMap& primitiveMap(void) {
81 static PrimitiveMap _pm;
82 return _pm;
83}
84
85namespace BytecodePrimitives {
86
87void Uniform::execute(Interpreter& i, const std::vector<Val>& args) {
88 assert(args.size() == 2);
89 assert(args[0].isInt() && args[1].isInt());
90
91 std::uniform_int_distribution<> dis(args[0].toInt(), args[1].toInt());
92 Val rnd = dis(generator);
93 i.pushAgg(rnd, -1);
94}
95
96void Sol::execute(Interpreter& i, const std::vector<Val>& args) {
97 assert(args.size() == 1);
98 if (args[0].isVar()) {
99 auto it = i.solutions.find(args[0].timestamp());
100 assert(it != i.solutions.end());
101 i.pushAgg(Val(it->second), -1);
102 } else {
103 assert(args[0].isInt());
104 i.pushAgg(args[0], -1);
105 }
106};
107
108void Sort::execute(Interpreter& i, const std::vector<Val>& args) {
109 assert(args.size() == 1);
110
111 Val al = args[0].toVec()->raw_data();
112 std::vector<int> ai(al.size());
113 for (int j = 0; j < al.size(); j++) {
114 ai[j] = al[j].toInt();
115 }
116 std::stable_sort(ai.begin(), ai.end());
117
118 std::vector<Val> sorted(al.size());
119 for (int j = 0; j < al.size(); j++) {
120 sorted[j] = Val(ai[j]);
121 }
122 Vec* al_sorted = Vec::a(&i, i.newIdent(), sorted);
123
124 i.pushAgg(Val(al_sorted), -1);
125};
126
127void SortBy::execute(Interpreter& i, const std::vector<Val>& args) {
128 assert(args.size() == 2);
129
130 Val al = args[0].toVec()->raw_data();
131 Val order_e = args[1].toVec()->raw_data();
132 std::vector<Val> order(order_e.size());
133 std::vector<int> a(order_e.size());
134 for (int j = 0; j < order.size(); j++) {
135 a[j] = j;
136 order[j] = order_e[j];
137 }
138 struct Ord {
139 std::vector<Val>& order;
140 explicit Ord(std::vector<Val>& order0) : order(order0) {}
141 bool operator()(int i, int j) { return order[i] < order[j]; }
142 } _ord(order);
143 std::stable_sort(a.begin(), a.end(), _ord);
144 std::vector<Val> sorted(a.size());
145 for (int j = sorted.size(); j--;) {
146 sorted[j] = al[a[j]];
147 }
148 Vec* al_sorted = Vec::a(&i, i.newIdent(), sorted);
149
150 i.pushAgg(Val(al_sorted), -1);
151};
152
153void Infinity::execute(Interpreter& i, const std::vector<Val>& args) {
154 assert(args.size() == 1);
155 assert(args[0].isInt());
156
157 if (args[0] > 0) {
158 i.pushAgg(Val::infinity(), -1);
159 } else {
160 i.pushAgg(-Val::infinity(), -1);
161 }
162}
163
164void InfiniteDomain::execute(Interpreter& i, const std::vector<Val>& args) {
165 assert(args.size() == 0);
166 i.pushAgg(i.infinite_domain(), -1);
167}
168
169void BooleanDomain::execute(Interpreter& i, const std::vector<Val>& args) {
170 assert(args.size() == 0);
171 i.pushAgg(i.boolean_domain(), -1);
172};
173
174void SliceXd::execute(Interpreter& i, const std::vector<Val>& args) {
175 assert(args.size() == 3);
176 assert(args[0].isVec() && args[1].isVec() && args[2].isVec());
177
178 Val content = args[0].toVec()->raw_data();
179 Val selection = args[1].toVec()->raw_data();
180 Val new_idxs = args[2].toVec()->raw_data();
181
182 std::vector<Val> idxs(args[1].size());
183 std::vector<Val> slice;
184 // Initialise indexes to the index lower bound
185 if (args[0].toVec()->hasIndexSet()) {
186 Val index_set = args[0].toVec()->index_set();
187 assert(index_set.size() / 2 == selection.size());
188 for (int j = 0; j < idxs.size(); ++j) {
189 idxs[j] = index_set[j * 2];
190 }
191 } else {
192 assert(selection.size() == 1);
193 idxs[0] = 1;
194 }
195
196 // Walk through array and make slice selection
197 int level = idxs.size() - 1;
198 int it = 0;
199 while (level >= 0) {
200 bool in_slice = true;
201 for (int k = 0; k < idxs.size(); ++k) {
202 assert(selection[k].size() == 2);
203 in_slice = in_slice && selection[k][0] <= idxs[k] && idxs[k] <= selection[k][1];
204 }
205
206 assert(it < content.size());
207 if (in_slice) {
208 slice.push_back(content[it]);
209 }
210 it++;
211
212 while (level >= 0) {
213 if (args[0].toVec()->hasIndexSet()) {
214 Val index_set = args[0].toVec()->index_set();
215 if (idxs[level] < index_set[level * 2 + 1]) {
216 idxs[level]++;
217 level = idxs.size() - 1;
218 break;
219 } else {
220 idxs[level] = index_set[level * 2];
221 level--;
222 }
223 } else {
224 assert(level == 0);
225 if (idxs[0] < content.size()) {
226 idxs[0]++;
227 // No need to reset level, there is only one.
228 break;
229 } else {
230 // Done (no need to reset index values).
231 level--;
232 }
233 }
234 }
235 }
236
237 // Format new index sets
238 std::vector<Val> dom;
239 dom.reserve(new_idxs.size() * 2);
240 for (int j = 0; j < new_idxs.size(); ++j) {
241 assert(new_idxs[j].size() == 2);
242 dom.push_back(new_idxs[j][0]);
243 dom.push_back(new_idxs[j][1]);
244 }
245
246 Vec* values = Vec::a(&i, i.newIdent(), slice);
247 Vec* idx = Vec::a(&i, i.newIdent(), dom);
248 Vec* nv = Vec::a(&i, i.newIdent(), {Val(values), Val(idx)}, true);
249
250 i.pushAgg(Val(nv), -1);
251}
252
253void ArrayXd::execute(Interpreter& i, const std::vector<Val>& args) {
254 assert(args.size() == 2);
255 assert(args[0].isVec());
256
257 // Array Elements
258 Val arr = args[0].toVec()->raw_data();
259
260 if (args[1].isInt()) {
261 assert(args[1].toInt() == 0);
262 i.pushAgg(arr, -1);
263 return;
264 }
265
266 assert(args[1].isVec());
267 assert(args[1].size() % 2 == 0);
268 // Check if the index sets actually match up
269 int prod = 1;
270 for (int i = 0; i < args[1].size(); i += 2) {
271 prod *= (args[1][i + 1].toInt() - args[1][i].toInt() + 1);
272 }
273 if (arr.size() != prod) {
274 throw std::runtime_error("ArrayXd cardinality mismatch");
275 }
276
277 Val ret = arr;
278 if (args[1].size() != 0 && !(args[1].size() == 2 && args[1][0].toInt() == 1)) {
279 ret = Val(Vec::a(&i, i.newIdent(), {arr, args[1]}, true));
280 }
281 i.pushAgg(ret, -1);
282}
283
284void IndexSet::execute(Interpreter& i, const std::vector<Val>& args) {
285 assert(args.size() == 2);
286 assert(args[0].isVec() && args[1].isInt());
287
288 Val ret;
289 if (!args[0].toVec()->hasIndexSet()) {
290 assert(args[1].toInt() == 1 || args[1] == 0);
291 ret = Val(Vec::a(&i, i.newIdent(), {Val(1), Val(args[0].size())}));
292 } else if (args[1] == 0) {
293 ret = args[0].toVec()->index_set();
294 } else {
295 assert(args[0].size() == 2);
296 assert(args[0][1].isVec());
297 assert(args[0][1].size() / 2 >= args[1].toInt());
298 Val index_sets = args[0].toVec()->index_set();
299 ret = Val(
300 Vec::a(&i, i.newIdent(),
301 {index_sets[(args[1].toInt() - 1) * 2], index_sets[(args[1].toInt() - 1) * 2 + 1]}));
302 }
303 i.pushAgg(ret, -1);
304}
305
306} // namespace BytecodePrimitives
307} // namespace MiniZinc