Generated on for Gecode by doxygen 1.17.0
data.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
35
36#include <climits>
37#include <cmath>
38#include <cstdlib>
39#include <iomanip>
40#include <locale>
41#include <ostream>
42#include <sstream>
43#include <unordered_set>
44
45namespace Gecode { namespace Instance {
46
47 /*
48 * Errors and parameters
49 *
50 */
51
52 Error::Error(const std::string& m)
53 : Exception("Instance", m.c_str()), msg(m) {}
54
55 const char*
56 Error::what(void) const noexcept {
57 return msg.c_str();
58 }
59
61 : impl(std::make_shared<ParamsImpl>()) {}
62
63 void
64 Params::set(const std::string& name, const std::string& value) {
65 if (impl.use_count() > 1)
66 impl = std::make_shared<ParamsImpl>(*impl);
67 for (int i=0; i<impl->names.size(); i++)
68 if (impl->names[i] == name) {
69 impl->values[i] = value;
70 return;
71 }
72 impl->names.push(name);
73 impl->values.push(value);
74 }
75
76 void
77 Params::set(const std::string& assignments) {
78 size_t b = 0;
79 while (b <= assignments.size()) {
80 size_t e = assignments.find(',', b);
81 if (e == std::string::npos)
82 e = assignments.size();
83 std::string a = assignments.substr(b, e-b);
84 b = e+1;
85 if (a.empty())
86 continue;
87 size_t eq = a.find('=');
88 if ((eq == std::string::npos) || (eq == 0))
89 throw Error("parameter '" + a + "' must have the form name=value");
90 set(a.substr(0,eq), a.substr(eq+1));
91 }
92 }
93
94 bool
95 Params::get(const std::string& name, std::string& value) const {
96 for (int i=0; i<impl->names.size(); i++)
97 if (impl->names[i] == name) {
98 value = impl->values[i];
99 return true;
100 }
101 return false;
102 }
103
104 int
105 Params::size(void) const {
106 return impl->names.size();
107 }
108
109 std::string
110 Params::name(int i) const {
111 if ((i < 0) || (i >= impl->names.size()))
112 throw Error("parameter index out of range");
113 return impl->names[i];
114 }
115
116 /*
117 * Values
118 *
119 */
120
122 : rows(0), pending(0), started(false), missing(false), d(depth) {
123 c.type = t;
124 }
125
126 void
128 rows++;
129 missing = true;
130 if (!started)
131 pending++;
132 else if (d == 0)
133 throw ShapeError("is defined in only some repetitions");
134 else
135 c.lengths[1].push(0);
136 }
137
138 void
140 rows++;
141 if (!started) {
142 if (missing && (v.depth == 0))
143 throw ShapeError("is defined in only some repetitions");
144 started = true;
145 d = v.depth;
146 c.type = v.type;
147 c.depth = d+1;
148 c.lengths.clear();
149 for (int k=0; k<=d; k++)
150 c.lengths.push(Seq<int>());
151 for (int i=0; i<pending; i++)
152 c.lengths[1].push(0);
153 } else if (v.depth != d) {
154 throw ShapeError("has rows of different depths");
155 }
156 if (v.leaves() > 0) {
157 // The type follows the values; integers become floats if needed
158 if (c.leaves() == 0)
159 c.type = v.type;
160 else if ((c.type == ValueType::STRING) != (v.type == ValueType::STRING))
161 throw ShapeError("mixes strings and numbers");
162 else if ((c.type == ValueType::INT) && (v.type == ValueType::FLOAT))
163 c.to_float();
164 }
165 for (int k=0; k<d; k++)
166 for (int l : v.lengths[k])
167 c.lengths[k+1].push(l);
168 switch (c.type) {
169 case ValueType::INT:
170 for (long long int x : v.ints) c.ints.push(x);
171 break;
172 case ValueType::FLOAT:
173 for (long long int x : v.ints) c.reals.push(static_cast<double>(x));
174 for (double x : v.reals) c.reals.push(x);
175 break;
176 default:
177 for (std::string& x : v.strs) c.strs.push(std::move(x));
178 break;
179 }
180 }
181
182 Value
184 if (!started) {
185 // No rows added: every row is missing, so empty if it is a list
186 if ((d == 0) && (rows > 0))
187 throw ShapeError("is defined in no repetition");
188 c.depth = d+1;
189 c.lengths.clear();
190 for (int k=0; k<=d; k++)
191 c.lengths.push(Seq<int>());
192 for (int i=0; (d > 0) && (i<rows); i++)
193 c.lengths[1].push(0);
194 }
195 c.lengths[0].clear();
196 c.lengths[0].push(rows);
197 return std::move(c);
198 }
199
200 void
202 // The memory of earlier starts is reused (see clear_list)
203 while (starts.size() > depth)
204 starts.pop();
205 while (starts.size() < depth)
206 starts.push(Seq<int>());
207 for (int k=0; k<depth; k++) {
208 Seq<int>& s = starts[k];
209 s.clear();
210 s.reserve(lengths[k].size()+1);
211 int sum = 0;
212 for (int l : lengths[k]) {
213 s.push(sum);
214 sum += l;
215 }
216 s.push(sum);
217 }
218 }
219
220 void
221 Value::range(int level, int pos, int& from, int& to) const {
222 assert(starts.size() == depth);
223 from = pos; to = pos+1;
224 for (int k=level; k<depth; k++) {
225 from = starts[k][from];
226 to = starts[k][to];
227 }
228 }
229
230 /*
231 * Data access
232 *
233 */
234
235 namespace {
236
237 std::string
238 where(const std::string& n, const IntArgs& path, int np) {
239 std::string s = "'" + n;
240 for (int i=0; i<np; i++)
241 s += "[" + std::to_string(path[i]) + "]";
242 return s + "'";
243 }
244
246 const Value&
247 lookup(const std::shared_ptr<const DataImpl>& impl, const std::string& n) {
248 const Value* v = impl->find(n);
249 if (v == nullptr)
250 throw Error("no value named '" + n + "'");
251 return *v;
252 }
253
261 int
262 locate(const Value& v, const std::string& n, const IntArgs& path, bool leaf, int& level, int& pos) {
263 int np = path.size();
264 if (leaf ? (np != v.depth) : (np >= v.depth))
265 throw Error(where(n,path,np) + (leaf ? " is not a single value" : " is not an array"));
266 level = 0; pos = 0;
267 for (int i=0; i<np; i++) {
268 int len = v.lengths[level][pos];
269 if ((path[i] < 0) || (path[i] >= len))
270 throw Error("index out of range in " + where(n,path,i+1) + " (size " + std::to_string(len) + ")");
271 pos = v.starts[level][pos] + path[i];
272 level++;
273 }
274 return pos;
275 }
276
277 int
278 narrow(long long int x, const std::string& n) {
279 if ((x < INT_MIN) || (x > INT_MAX))
280 throw Error("value " + std::to_string(x) + " in '" + n + "' does not fit into an int");
281 return static_cast<int>(x);
282 }
283
284 long long int
285 integer_at(const std::shared_ptr<const DataImpl>& impl, const std::string& n, const IntArgs& path) {
286 const Value& v = lookup(impl,n);
287 int level, pos;
288 int i = locate(v,n,path,true,level,pos);
289 if (v.type != ValueType::INT)
290 throw Error(where(n,path,path.size()) + " is not an integer");
291 return v.ints[i];
292 }
293
294 double
295 number_at(const std::shared_ptr<const DataImpl>& impl, const std::string& n, const IntArgs& path) {
296 const Value& v = lookup(impl,n);
297 int level, pos;
298 int i = locate(v,n,path,true,level,pos);
299 if (v.type == ValueType::STRING)
300 throw Error(where(n,path,path.size()) + " is not a number");
301 return v.as_double(i);
302 }
303
304 std::string
305 text_at(const std::shared_ptr<const DataImpl>& impl, const std::string& n, const IntArgs& path) {
306 const Value& v = lookup(impl,n);
307 int level, pos;
308 int i = locate(v,n,path,true,level,pos);
309 if (v.type != ValueType::STRING)
310 throw Error(where(n,path,path.size()) + " is not a string");
311 return v.strs[i];
312 }
313
314 int
315 size_at(const std::shared_ptr<const DataImpl>& impl, const std::string& n, const IntArgs& path) {
316 const Value& v = lookup(impl,n);
317 int level, pos;
318 locate(v,n,path,false,level,pos);
319 return v.lengths[level][pos];
320 }
321
322 IntArgs
323 ints_at(const std::shared_ptr<const DataImpl>& impl, const std::string& n, const IntArgs& path) {
324 const Value& v = lookup(impl,n);
325 int level, pos;
326 locate(v,n,path,false,level,pos);
327 if ((v.type != ValueType::INT) && (v.leaves() > 0))
328 throw Error(where(n,path,path.size()) + " does not contain integers");
329 int from, to;
330 v.range(level,pos,from,to);
331 IntArgs a(to-from);
332 for (int i=from; i<to; i++)
333 a[i-from] = narrow(v.ints[i],n);
334 return a;
335 }
336
337 ArgArray<double>
338 numbers_at(const std::shared_ptr<const DataImpl>& impl, const std::string& n, const IntArgs& path) {
339 const Value& v = lookup(impl,n);
340 int level, pos;
341 locate(v,n,path,false,level,pos);
342 if ((v.type == ValueType::STRING) && (v.leaves() > 0))
343 throw Error(where(n,path,path.size()) + " does not contain numbers");
344 int from, to;
345 v.range(level,pos,from,to);
346 ArgArray<double> a(to-from);
347 for (int i=from; i<to; i++)
348 a[i-from] = v.as_double(i);
349 return a;
350 }
351
352 }
353
355 : impl(std::make_shared<DataImpl>()) {}
356
357 int
358 Data::entries(void) const {
359 return impl->entries.size();
360 }
361
362 std::string
363 Data::name(int i) const {
364 if ((i < 0) || (i >= impl->entries.size()))
365 throw Error("entry index out of range");
366 return impl->entries[i].name;
367 }
368
369 bool
370 Data::has(const std::string& n) const {
371 return impl->find(n) != nullptr;
372 }
373
375 Data::type(const std::string& n) const {
376 return lookup(impl,n).type;
377 }
378
379 int
380 Data::depth(const std::string& n) const {
381 return lookup(impl,n).depth;
382 }
383
384 int
385 Data::size(const std::string& n, const IntArgs& path) const {
386 return size_at(impl,n,path);
387 }
388
389 long long int
390 Data::integer(const std::string& n, const IntArgs& path) const {
391 return integer_at(impl,n,path);
392 }
393
394 double
395 Data::number(const std::string& n, const IntArgs& path) const {
396 return number_at(impl,n,path);
397 }
398
399 std::string
400 Data::text(const std::string& n, const IntArgs& path) const {
401 return text_at(impl,n,path);
402 }
403
404 IntArgs
405 Data::ints(const std::string& n, const IntArgs& path) const {
406 return ints_at(impl,n,path);
407 }
408
410 Data::numbers(const std::string& n, const IntArgs& path) const {
411 return numbers_at(impl,n,path);
412 }
413
414 /*
415 * Output
416 *
417 */
418
419 namespace {
420
426 void
427 print_real(std::ostream& os, double f) {
428 // Start with all integer digits to avoid "2e+01" for 20
429 int digits = (std::fabs(f) >= 1.0) && (std::fabs(f) < 1e17)
430 ? static_cast<int>(std::floor(std::log10(std::fabs(f)))) + 1 : 1;
431 for (int prec=std::max(digits,1); prec<=17; prec++) {
432 // Independent of the global and the stream's locale
433 std::ostringstream ss;
434 ss.imbue(std::locale::classic());
435 ss << std::setprecision(prec) << f;
436 std::istringstream back(ss.str());
437 back.imbue(std::locale::classic());
438 double g = 0.0;
439 back >> g;
440 if ((g == f) || (prec == 17)) {
441 std::string t = ss.str();
442 if (t.find_first_of(".e") == std::string::npos)
443 t += ".0";
444 os << t;
445 return;
446 }
447 }
448 }
449
451 void
452 print_quoted(std::ostream& os, const std::string& s) {
453 os << '"';
454 for (char c : s) {
455 if ((c == '"') || (c == '\\')) {
456 os << '\\' << c;
457 } else if (c == '\n') {
458 os << "\\n";
459 } else if (c == '\t') {
460 os << "\\t";
461 } else if (static_cast<unsigned char>(c) < 0x20) {
462 // Other control characters are written as \xXX
463 static const char hex[] = "0123456789abcdef";
464 os << "\\x" << hex[(c >> 4) & 0xf] << hex[c & 0xf];
465 } else {
466 os << c;
467 }
468 }
469 os << '"';
470 }
471
473 void
474 print_leaf(std::ostream& os, const Value& v, int i) {
475 switch (v.type) {
476 case ValueType::INT: os << std::to_string(v.ints[i]); break;
477 case ValueType::FLOAT: print_real(os, v.reals[i]); break;
478 default: print_quoted(os, v.strs[i]); break;
479 }
480 }
481
483 void
484 print_name(std::ostream& os, const std::string& n) {
485 static const std::unordered_set<std::string> keywords = {
486 "ann", "annotation", "any", "array", "bool", "case", "constraint", "default", "diff", "div", "else", "elseif",
487 "endif", "enum", "false", "float", "function", "if", "in", "include", "int", "intersect", "let", "list",
488 "maximize", "minimize", "mod", "not", "of", "op", "opt", "output", "par", "predicate", "record", "satisfy",
489 "set", "solve", "string", "subset", "superset", "symdiff", "test", "then", "true", "tuple", "type", "union",
490 "var", "where", "xor"
491 };
492 // MiniZinc identifiers start with a letter
493 bool plain = !n.empty() && is_letter(n[0]) && (keywords.count(n) == 0);
494 if (plain)
495 os << n;
496 else
497 os << '\'' << n << '\'';
498 }
499
506 void
507 print_list(std::ostream& os, const Value& v, Seq<int>& next, int level) {
508 int pos = next[level]++;
509 int len = v.lengths[level][pos];
510 os << '[';
511 for (int i=0; i<len; i++) {
512 if (i > 0) os << ", ";
513 if (level+1 == v.depth) {
514 print_leaf(os, v, next[v.depth]++);
515 } else {
516 os << '(';
517 print_list(os, v, next, level+1);
518 os << ",)";
519 }
520 }
521 os << ']';
522 }
523
525 bool
526 rectangular(const Value& v) {
527 for (int k=1; k<v.depth; k++)
528 for (int l : v.lengths[k])
529 if (l != v.lengths[k][0])
530 return false;
531 return true;
532 }
533
534 }
535
536 void
537 Data::dzn(std::ostream& os) const {
538 for (const Entry& en : impl->entries) {
539 const Value& v = en.value;
540 const std::string& n = en.name;
541 if (v.depth == 0) {
542 print_name(os, n);
543 os << " = ";
544 print_leaf(os, v, 0);
545 os << ";\n";
546 continue;
547 }
548 int nl = v.leaves();
549 // MiniZinc has array constructors up to array6d
550 if (rectangular(v) && (v.depth <= 6)) {
551 print_name(os, n);
552 os << " = ";
553 if ((v.depth == 2) && (v.size() > 0) && (v.lengths[1][0] > 0)) {
554 int cols = v.lengths[1][0];
555 os << "[|";
556 for (int i=0; i<nl; i++) {
557 if (i % cols == 0)
558 os << (i > 0 ? "\n | " : " ");
559 else
560 os << ", ";
561 print_leaf(os, v, i);
562 }
563 os << " |];\n";
564 continue;
565 }
566 // Arrays with an empty dimension need explicit index sets
567 bool empty = false;
568 for (int k=0; k<v.depth; k++)
569 empty = empty || (v.lengths[k].size() == 0) || (v.lengths[k][0] == 0);
570 bool nd = (v.depth > 2) || ((v.depth == 2) && empty);
571 if (nd) {
572 os << "array" << v.depth << "d(";
573 for (int k=0; k<v.depth; k++)
574 os << "1.." << (v.lengths[k].size() > 0 ? v.lengths[k][0] : 0) << ", ";
575 }
576 os << "[";
577 for (int i=0; i<nl; i++) {
578 if (i > 0) os << ", ";
579 print_leaf(os, v, i);
580 }
581 os << "]" << (nd ? ")" : "") << ";\n";
582 continue;
583 }
584 // Ragged or deeper: arrays of 1-tuples of arrays (MiniZinc 2.7 and later)
585 std::string type = std::string("array[int] of ") +
586 (v.type == ValueType::INT ? "int" : (v.type == ValueType::FLOAT ? "float" : "string"));
587 for (int k=1; k<v.depth; k++)
588 type = "array[int] of tuple(" + type + ")";
589 os << "% " << n << ": " << type << "\n";
590 print_name(os, n);
591 os << " = ";
592 Seq<int> next;
593 for (int k=0; k<=v.depth; k++)
594 next.push(0);
595 print_list(os, v, next, 0);
596 os << ";\n";
597 }
598 }
599
600}}
601
602// STATISTICS: instance-any
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
Argument array for non-primitive types.
Definition array.hpp:695
Exception(const char *l, const char *i) noexcept
Initialize with location l and information i.
Definition exception.cpp:42
FloatNum size(void) const
Return size of float value (distance between maximum and minimum).
Definition val.hpp:78
Column(ValueType t, int depth)
Empty column for rows of type t and depth depth.
Definition data.cpp:121
void skip(void)
Add a missing row.
Definition data.cpp:127
Value finish(void)
Return the array.
Definition data.cpp:183
void add(Value &v)
Add a row v; throws ShapeError with a phrase completing the name.
Definition data.cpp:139
Implementation of Data.
Definition impl.hpp:414
IntArgs ints(const std::string &n, const IntArgs &path=IntArgs()) const
Return all integers in the array or row n at path.
Definition data.cpp:405
int size(const std::string &n, const IntArgs &path=IntArgs()) const
Return the length of the array or row n at path.
Definition data.cpp:385
void dzn(std::ostream &os) const
Print all entries as MiniZinc data.
Definition data.cpp:537
double number(const std::string &n, const IntArgs &path=IntArgs()) const
Return the number n at path (integers are converted).
Definition data.cpp:395
ValueType type(const std::string &n) const
Return the value type of entry n.
Definition data.cpp:375
std::string text(const std::string &n, const IntArgs &path=IntArgs()) const
Return the string n at path.
Definition data.cpp:400
int depth(const std::string &n) const
Return the depth of entry n (0 for scalars).
Definition data.cpp:380
Data(void)
Empty data.
Definition data.cpp:354
bool has(const std::string &n) const
Test whether there is an entry n.
Definition data.cpp:370
std::string name(int i) const
Return name of entry i, in the order they were defined.
Definition data.cpp:363
long long int integer(const std::string &n, const IntArgs &path=IntArgs()) const
Return the integer n at path.
Definition data.cpp:390
ArgArray< double > numbers(const std::string &n, const IntArgs &path=IntArgs()) const
Return all numbers in the array or row n at path.
Definition data.cpp:410
int entries(void) const
Return number of entries.
Definition data.cpp:358
A named value.
Definition impl.hpp:400
std::string name
Name.
Definition impl.hpp:403
Value value
Value.
Definition impl.hpp:405
Exception for errors in specs and instance files
Definition instance.hh:337
Error(const std::string &m)
Initialize with message m.
Definition data.cpp:52
std::string msg
The full message.
Definition instance.hh:340
virtual const char * what(void) const noexcept override
Return the full message.
Definition data.cpp:56
Implementation of Params.
Definition impl.hpp:428
Params(void)
No parameters.
Definition data.cpp:60
std::string name(int i) const
Return the name of parameter i.
Definition data.cpp:110
bool get(const std::string &name, std::string &value) const
Return whether name is set, and if so store its value in value.
Definition data.cpp:95
int size(void) const
Return number of parameters.
Definition data.cpp:105
void set(const std::string &name, const std::string &value)
Set parameter name to value.
Definition data.cpp:64
Growable array on the Gecode heap.
Definition impl.hpp:118
void reserve(int m)
Make room for m elements.
Definition impl.hpp:172
void push(const T &v)
Append a copy of v.
Definition impl.hpp:176
void clear(void)
Remove all elements.
Definition impl.hpp:203
Error about the shape or type of a value, located by the caller.
Definition impl.hpp:238
A value: scalar or nested (possibly ragged) array.
Definition impl.hpp:255
void range(int level, int pos, int &from, int &to) const
Find leaf range of list pos at level level.
Definition data.cpp:221
Seq< Seq< int > > starts
Start of each list among the lists or leaves one level down (see index).
Definition impl.hpp:264
Seq< Seq< int > > lengths
List lengths per level.
Definition impl.hpp:262
int depth
Nesting depth (0 for scalars).
Definition impl.hpp:260
void index(void)
Compute starts, needed by range.
Definition data.cpp:201
int size(void) const
Return length of outermost list.
Definition impl.hpp:310
Passing integer arguments.
Definition int.hh:653
bool pos(const View &x)
Test whether x is positive.
Definition mult.hpp:41
Reading instance files described by reader specs.
ValueType
Type of the values in a data entry.
Definition instance.hh:349
@ FLOAT
Floating point numbers.
Definition instance.hh:351
bool is_letter(char c)
Test whether c is a letter.
Definition impl.hpp:60
Gecode toplevel namespace
void path(Home home, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a Hamiltonian path.
Definition circuit.cpp:169
LinIntExpr sum(const IntVarArgs &x)
Construct linear expression as sum of integer variables.
Definition int-expr.cpp:953
Gecode::FloatVal a(-8, 5)
Gecode::IntArgs i({1, 2, 3, 4})