Generated on for Gecode by doxygen 1.17.0
extensional.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 * Linnea Ingmar <linnea.ingmar@hotmail.com>
6 * Christian Schulte <schulte@gecode.dev>
7 *
8 * Copyright:
9 * Linnea Ingmar, 2017
10 * Mikael Zayenz Lagerkvist, 2007
11 * Christian Schulte, 2005
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.dev
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38#include "test/int.hh"
39
40#include <gecode/minimodel.hh>
41#include <climits>
42#include <cstdlib>
43#include <iostream>
44#include <string>
45
46namespace Test { namespace Int {
47
49 namespace Extensional {
50
56 std::string
58 switch (epk) {
59 case Gecode::EPK_DENSE:
60 return "Dense";
61 case Gecode::EPK_SPARSE:
62 return "Sparse";
63 case Gecode::EPK_DENSE_COMPRESSED:
64 return "DenseCompressed";
65 case Gecode::EPK_AUTO:
66 return "Auto";
67 default:
69 return "Unknown";
70 }
71 }
72
74 class RegSimpleA : public Test {
75 public:
77 RegSimpleA(void) : Test("Extensional::Reg::Simple::A",4,2,2) {}
79 virtual bool solution(const Assignment& x) const {
80 return (((x[0] == 0) || (x[0] == 2)) &&
81 ((x[1] == -1) || (x[1] == 1)) &&
82 ((x[2] == 0) || (x[2] == 1)) &&
83 ((x[3] == 0) || (x[3] == 1)));
84 }
85
86 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
87 using namespace Gecode;
88 extensional(home, x,
89 (REG(0) | REG(2)) +
90 (REG(-1) | REG(1)) +
91 (REG(7) | REG(0) | REG(1)) +
92 (REG(0) | REG(1)));
93 }
94 };
95
97 class RegSimpleB : public Test {
98 public:
100 RegSimpleB(void) : Test("Extensional::Reg::Simple::B",4,2,2) {}
102 virtual bool solution(const Assignment& x) const {
103 return (x[0]<x[1]) && (x[1]<x[2]) && (x[2]<x[3]);
104 }
105
106 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
107 using namespace Gecode;
108 extensional(home, x,
109 (REG(-2) + REG(-1) + REG(0) + REG(1)) |
110 (REG(-2) + REG(-1) + REG(0) + REG(2)) |
111 (REG(-2) + REG(-1) + REG(1) + REG(2)) |
112 (REG(-2) + REG(0) + REG(1) + REG(2)) |
113 (REG(-1) + REG(0) + REG(1) + REG(2)));
114 }
115 };
116
118 class RegSimpleC : public Test {
119 public:
121 RegSimpleC(void) : Test("Extensional::Reg::Simple::C",6,0,1) {}
123 virtual bool solution(const Assignment& x) const {
124 int pos = 0;
125 int s = x.size();
126
127 while (pos < s && x[pos] == 0) ++pos;
128 if (pos + 4 > s) return false;
129
130 for (int i = 0; i < 2; ++i, ++pos)
131 if (x[pos] != 1) return false;
132 if (pos + 2 > s) return false;
133
134 for (int i = 0; i < 1; ++i, ++pos)
135 if (x[pos] != 0) return false;
136 while (pos < s && x[pos] == 0) ++pos;
137 if (pos + 1 > s) return false;
138
139 for (int i = 0; i < 1; ++i, ++pos)
140 if (x[pos] != 1) return false;
141 while (pos < s) if (x[pos++] != 0) return false;
142 return true;
143
144 }
145
146 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
147 using namespace Gecode;
148 extensional(home, x,
149 *REG(0) + REG(1)(2,2) + +REG(0) + REG(1)(1,1) + *REG(0));
150 }
151 };
152
154 class RegDistinct : public Test {
155 public:
157 RegDistinct(void) : Test("Extensional::Reg::Distinct",4,-1,4) {}
159 virtual bool solution(const Assignment& x) const {
160 for (int i=0; i<x.size(); i++) {
161 if ((x[i] < 0) || (x[i] > 3))
162 return false;
163 for (int j=i+1; j<x.size(); j++)
164 if (x[i]==x[j])
165 return false;
166 }
167 return true;
168 }
169
170 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
171 using namespace Gecode;
172 extensional(home, x,
173 (REG(0)+REG(1)+REG(2)+REG(3)) |
174 (REG(0)+REG(1)+REG(3)+REG(2)) |
175 (REG(0)+REG(2)+REG(1)+REG(3)) |
176 (REG(0)+REG(2)+REG(3)+REG(1)) |
177 (REG(0)+REG(3)+REG(1)+REG(2)) |
178 (REG(0)+REG(3)+REG(2)+REG(1)) |
179 (REG(1)+REG(0)+REG(2)+REG(3)) |
180 (REG(1)+REG(0)+REG(3)+REG(2)) |
181 (REG(1)+REG(2)+REG(0)+REG(3)) |
182 (REG(1)+REG(2)+REG(3)+REG(0)) |
183 (REG(1)+REG(3)+REG(0)+REG(2)) |
184 (REG(1)+REG(3)+REG(2)+REG(0)) |
185 (REG(2)+REG(0)+REG(1)+REG(3)) |
186 (REG(2)+REG(0)+REG(3)+REG(1)) |
187 (REG(2)+REG(1)+REG(0)+REG(3)) |
188 (REG(2)+REG(1)+REG(3)+REG(0)) |
189 (REG(2)+REG(3)+REG(0)+REG(1)) |
190 (REG(2)+REG(3)+REG(1)+REG(0)) |
191 (REG(3)+REG(0)+REG(1)+REG(2)) |
192 (REG(3)+REG(0)+REG(2)+REG(1)) |
193 (REG(3)+REG(1)+REG(0)+REG(2)) |
194 (REG(3)+REG(1)+REG(2)+REG(0)) |
195 (REG(3)+REG(2)+REG(0)+REG(1)) |
196 (REG(3)+REG(2)+REG(1)+REG(0)));
197 }
198 };
199
201 class RegRoland : public Test {
202 public:
205 : Test("Extensional::Reg::Roland::"+str(n),n,0,1) {}
206
207 virtual bool solution(const Assignment& x) const {
208 int n = x.size();
209 return
210 ((n > 1) && (x[n-2] == 0)) ||
211 ((n > 0) && (x[n-1] == 0));
212 }
213
214 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
215 using namespace Gecode;
216 REG r0(0), r1(1);
217 REG r01 = r0 | r1;
218 extensional(home, x, *r01 + r0 + r01(0,1));
219 }
220 };
221
223 class RegSharedA : public Test {
224 public:
226 RegSharedA(void) : Test("Extensional::Reg::Shared::A",4,2,2) {}
228 virtual bool solution(const Assignment& x) const {
229 return (((x[0] == 0) || (x[0] == 2)) &&
230 ((x[1] == -1) || (x[1] == 1)) &&
231 ((x[2] == 0) || (x[2] == 1)) &&
232 ((x[3] == 0) || (x[3] == 1)));
233 }
234
235 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
236 using namespace Gecode;
237 IntVarArgs y(8);
238 for (int i=0; i<4; i++)
239 y[i]=y[i+4]=x[i];
240 unshare(home,y);
241 extensional(home, y,
242 ((REG(0) | REG(2)) +
243 (REG(-1) | REG(1)) +
244 (REG(7) | REG(0) | REG(1)) +
245 (REG(0) | REG(1)))(2,2));
246 }
247 };
248
250 class RegSharedB : public Test {
251 public:
253 RegSharedB(void) : Test("Extensional::Reg::Shared::B",4,2,2) {}
255 virtual bool solution(const Assignment& x) const {
256 return (((x[0] == 0) || (x[0] == 2)) &&
257 ((x[1] == -1) || (x[1] == 1)) &&
258 ((x[2] == 0) || (x[2] == 1)) &&
259 ((x[3] == 0) || (x[3] == 1)));
260 }
261
262 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
263 using namespace Gecode;
264 IntVarArgs y(12);
265 for (int i=0; i<4; i++)
266 y[i]=y[i+4]=y[i+8]=x[i];
267 unshare(home,y);
268 extensional(home, y,
269 ((REG(0) | REG(2)) +
270 (REG(-1) | REG(1)) +
271 (REG(7) | REG(0) | REG(1)) +
272 (REG(0) | REG(1)))(3,3));
273 }
274 };
275
277 class RegSharedC : public Test {
278 public:
280 RegSharedC(void) : Test("Extensional::Reg::Shared::C",4,0,1) {}
282 virtual bool solution(const Assignment& x) const {
283 return (x[1]==1) && (x[2]==0) && (x[3]==1);
284 }
285
286 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
287 using namespace Gecode;
289 for (int i=0; i<4; i++)
290 y[i]=y[i+4]=channel(home,x[i]);
291 unshare(home,y);
292 extensional(home,y,
293 ((REG(0) | REG(1)) + REG(1) + REG(0) + REG(1))(2,2));
294 }
295 };
296
298 class RegSharedD : public Test {
299 public:
301 RegSharedD(void) : Test("Extensional::Reg::Shared::D",4,0,1) {}
303 virtual bool solution(const Assignment& x) const {
304 return (x[1]==1) && (x[2]==0) && (x[3]==1);
305 }
306
307 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
308 using namespace Gecode;
310 for (int i=0; i<4; i++)
311 y[i]=y[i+4]=y[i+8]=channel(home,x[i]);
312 unshare(home, y);
313 extensional(home, y,
314 ((REG(0) | REG(1)) + REG(1) + REG(0) + REG(1))(3,3));
315 }
316 };
317
319 class RegEmptyDFA : public Test {
320 public:
322 RegEmptyDFA(void) : Test("Extensional::Reg::Empty::DFA",1,0,0) {
323 testsearch = false;
324 }
325
326 virtual bool solution(const Assignment& x) const {
327 (void)x;
328 return false;
329 }
330
331 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
332 Gecode::DFA d;
333 Gecode::extensional(home, x, d);
334 }
335 };
336
338 class RegEmptyREG : public Test {
339 public:
341 RegEmptyREG(void) : Test("Extensional::Reg::Empty::REG",1,0,0) {
342 testsearch = false;
343 }
344
345 virtual bool solution(const Assignment& x) const {
346 (void)x;
347 return false;
348 }
349
350 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
352 Gecode::extensional(home, x, r);
353 }
354 };
355
357 class RegOpt : public Test {
358 protected:
360 int n;
361 public:
363 RegOpt(int n0)
364 : Test("Extensional::Reg::Opt::"+str(n0),1,0,15), n(n0) {}
365
366 virtual bool solution(const Assignment& x) const {
367 return (x[0] < n) && ((x[0] & 1) == 0);
368 }
369
370 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
371 using namespace Gecode;
373 DFA::Transition* ti = t;
374 int* f = new int[n+1];
375 int* fi = f;
376 for (int i=0; i<n; i++) {
377 ti->i_state = 0;
378 ti->symbol = i;
379 ti->o_state = i+1;
380 ti++;
381 if ((i & 1) == 0) {
382 *fi = i+1; fi++;
383 }
384 }
385 ti->i_state = -1;
386 *fi = -1;
387 DFA d(0, t, f, false);
388 delete [] t;
389 delete [] f;
390 extensional(home, x, d);
391 }
392
393 };
394
397 public:
400 : Test("Extensional::Reg::Sparse::AcyclicReconvergence",
401 4,0,3,false,Gecode::IPL_DOM) {}
402
403 virtual bool solution(const Assignment& x) const {
404 return
405 ((x[0] == 0) && (x[1] == 2) &&
406 (x[2] == 2) && (x[3] == 2)) ||
407 ((x[0] == 1) && (x[1] == 0) &&
408 (x[2] == 3) && (x[3] == 3));
409 }
410
411 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
412 using namespace Gecode;
413 // State 1 is reached at depth one by 0 and at depth two by 1,0.
414 // Its two acyclic suffixes have the corresponding lengths.
415 DFA d(0,
416 {
417 {0,0,1}, {0,1,2}, {2,0,1},
418 {1,2,3}, {3,2,4}, {4,2,7},
419 {1,3,5}, {5,3,7}
420 },
421 {7},false);
422 extensional(home,x,d);
423 }
424 };
425
427 class RegCyclicFrontier : public Test {
428 public:
431 : Test("Extensional::Reg::Sparse::CyclicFrontier",
432 7,0,1,false,Gecode::IPL_DOM) {}
433
434 virtual bool solution(const Assignment& x) const {
435 int parity = 0;
436 for (int i=0; i<x.size(); i++)
437 parity ^= x[i];
438 return parity == 0;
439 }
440
441 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
442 using namespace Gecode;
443 DFA d(0,
444 {
445 {0,0,0}, {0,1,1},
446 {1,0,1}, {1,1,0}
447 },
448 {0},false);
449 extensional(home,x,d);
450 }
451 };
452
455 public:
458 : Test("Extensional::Reg::Sparse::StateNumbering",
459 2,0,1,false,Gecode::IPL_DOM) {}
460
461 virtual bool solution(const Assignment& x) const {
462 return (x[0] == 0) && (x[1] == 1);
463 }
464
465 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
466 using namespace Gecode;
467 DFA d(1000000,
468 {
469 {1000000,0,2000000},
470 {2000000,1,3000000}
471 },
472 {3000000},false);
473 extensional(home,x,d);
474 }
475 };
476
478 class RegDuplicateFinals : public Test {
479 protected:
481 bool sparse;
482 public:
483 RegDuplicateFinals(bool minimize0, bool sparse0)
484 : Test(std::string("Extensional::Reg::DuplicateFinals::")+
485 (sparse0 ? "Sparse::" : "Dense::")+
486 (minimize0 ? "Minimize" : "Keep"),
487 1,0,1,false,Gecode::IPL_DOM),
488 minimize(minimize0), sparse(sparse0) {}
489
490 virtual bool
491 solution(const Assignment& x) const {
492 return x[0] == 0;
493 }
494
495 virtual void
497 using namespace Gecode;
498 const int start = sparse ? 100 : 0;
499 const int final = sparse ? 200 : 1;
500 DFA d(start,{{start,0,final}},
501 {final,final,final,final,final,final,final,final},minimize);
502 extensional(home,x,d);
503 }
504 };
505
508 public:
511 : Test("Extensional::Reg::Sparse::BoolCyclicFrontier",
512 7,0,1,false,Gecode::IPL_DOM) {}
513
514 virtual bool solution(const Assignment& x) const {
515 int parity = 0;
516 for (int i=0; i<x.size(); i++)
517 parity ^= x[i];
518 return parity == 0;
519 }
520
521 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
522 using namespace Gecode;
523 BoolVarArgs b(x.size());
524 for (int i=0; i<x.size(); i++)
525 b[i] = channel(home,x[i]);
526 DFA d(0,
527 {
528 {0,0,0}, {0,1,1},
529 {1,0,1}, {1,1,0}
530 },
531 {0},false);
532 extensional(home,b,d);
533 }
534 };
535
538 protected:
540 static const int n_dfa_states = 4;
542 static const int n_symbols = 3;
546 unsigned int allowed[5];
548 unsigned int finals;
549 public:
551 RegRandomDifferential(unsigned int seed)
552 : Test("Extensional::Reg::Sparse::RandomDifferential::" +
553 Test::str(static_cast<int>(seed)),
554 5,0,n_symbols-1,false,Gecode::IPL_DOM),
555 finals(0) {
556 unsigned int random = seed;
557 for (int state=0; state<n_dfa_states; state++)
558 for (int symbol=0; symbol<n_symbols; symbol++) {
559 random = 1664525U * random + 1013904223U;
560 next[state][symbol] =
561 ((random & 7U) == 0U) ? -1 :
562 static_cast<int>((random >> 8) % n_dfa_states);
563 }
564 for (int i=0; i<5; i++) {
565 random = 1664525U * random + 1013904223U;
566 allowed[i] = 1U + ((random >> 12) % 7U);
567 }
568 random = 1664525U * random + 1013904223U;
569 finals = 1U + ((random >> 16) % 15U);
570 }
571
572 virtual bool solution(const Assignment& x) const {
573 int state = 0;
574 for (int i=0; i<x.size(); i++) {
575 const int symbol = x[i];
576 if (((allowed[i] & (1U << symbol)) == 0U) ||
577 (next[state][symbol] < 0))
578 return false;
579 state = next[state][symbol];
580 }
581 return (finals & (1U << state)) != 0U;
582 }
583
584 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
585 using namespace Gecode;
587 int n_transitions = 0;
588 for (int state=0; state<n_dfa_states; state++)
589 for (int symbol=0; symbol<n_symbols; symbol++)
590 if (next[state][symbol] >= 0)
591 transitions[n_transitions++] =
592 DFA::Transition(state,symbol,next[state][symbol]);
593 transitions[n_transitions].i_state = -1;
594 int final_states[n_dfa_states+1];
595 int n_final_states = 0;
596 for (int state=0; state<n_dfa_states; state++)
597 if ((finals & (1U << state)) != 0U)
598 final_states[n_final_states++] = state;
599 final_states[n_final_states] = -1;
600 DFA d(0,transitions,final_states,false);
601 for (int i=0; i<x.size(); i++)
602 for (int symbol=0; symbol<n_symbols; symbol++)
603 if ((allowed[i] & (1U << symbol)) == 0U)
604 rel(home,x[i],IRT_NQ,symbol);
605 extensional(home,x,d);
606 }
607 };
608
611 protected:
613 static const int n_fa_states = 4;
615 static const int n_symbols = 3;
619 unsigned int allowed[5];
620 public:
622 RegRandomNFADifferential(unsigned int seed)
623 : Test(TestTags::check(),
624 "Extensional::Reg::Sparse::RandomNFADifferential::" +
625 Test::str(static_cast<int>(seed)),
626 5,0,n_symbols-1,false,Gecode::IPL_DOM) {
627 unsigned int random = seed;
628 for (int state=0; state<n_fa_states; state++)
629 for (int symbol=0; symbol<n_symbols; symbol++)
630 for (int output=0; output<n_fa_states; output++) {
631 random = 1664525U * random + 1013904223U;
632 next[state][symbol][output] = ((random >> 29) == 0U);
633 }
634 // Keep a nondeterministic fork and both of its branches relevant.
635 next[0][0][1] = true;
636 next[0][0][2] = true;
637 next[1][1][3] = true;
638 next[2][2][3] = true;
639 for (int symbol=0; symbol<n_symbols; symbol++)
640 next[3][symbol][3] = true;
641 for (int i=0; i<5; i++) {
642 random = 1664525U * random + 1013904223U;
643 allowed[i] = 1U + ((random >> 12) % 7U);
644 }
645 // Ensure both branches of the fixed fork can occur.
646 allowed[0] |= 1U;
647 allowed[1] |= 6U;
648 }
649
650 virtual bool solution(const Assignment& x) const {
651 unsigned int states = 1U;
652 for (int i=0; i<x.size(); i++) {
653 const int symbol = x[i];
654 if ((allowed[i] & (1U << symbol)) == 0U)
655 return false;
656 unsigned int outputs = 0U;
657 for (int state=0; state<n_fa_states; state++)
658 if ((states & (1U << state)) != 0U)
659 for (int output=0; output<n_fa_states; output++)
660 if (next[state][symbol][output])
661 outputs |= 1U << output;
662 states = outputs;
663 }
664 return (states & (1U << 3)) != 0U;
665 }
666
667 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
668 using namespace Gecode;
670 transitions[n_fa_states*n_symbols*n_fa_states+1];
671 int n_transitions = 0;
672 for (int state=0; state<n_fa_states; state++)
673 for (int symbol=0; symbol<n_symbols; symbol++)
674 for (int output=0; output<n_fa_states; output++)
675 if (next[state][symbol][output])
676 transitions[n_transitions++] =
677 DFA::Transition(state,symbol,output);
678 transitions[n_transitions].i_state = -1;
679 int final_states[] = {3,-1};
680 DFA d = DFA::nfa(0,transitions,final_states);
681 for (int i=0; i<x.size(); i++)
682 for (int symbol=0; symbol<n_symbols; symbol++)
683 if ((allowed[i] & (1U << symbol)) == 0U)
684 rel(home,x[i],IRT_NQ,symbol);
685 extensional(home,x,d);
686 }
687 };
688
690 class RegNFAPrefix : public Test {
691 protected:
694 public:
697 : Test(TestTags::check(),
698 "Extensional::Reg::Sparse::NFAPrefix::" +
699 std::string(b ? "Bool" : "Int"),
700 5,0,1,false,Gecode::IPL_DOM), boolean(b) {}
701
702 virtual bool solution(const Assignment& x) const {
703 return (x[0] == 0) && (x[1] == 0) && (x[2] == x[3]);
704 }
705
706 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
707 using namespace Gecode;
708 // The first assigned layer has one edge and can be discarded on
709 // cloning. The second has two edges and must be retained. Two
710 // paths read the prefix 0,0,0,0, while only one reads 0,0,1,1.
711 DFA d = DFA::nfa(0,
712 {
713 {0,0,1}, {1,0,2}, {1,0,3},
714 {2,0,4}, {3,0,4}, {3,1,5},
715 {4,0,6}, {5,1,6}, {6,0,7}, {6,1,7}
716 },
717 {7});
718 if (boolean) {
719 BoolVarArgs b(x.size());
720 for (int i=0; i<x.size(); i++)
721 b[i] = channel(home,x[i]);
722 extensional(home,b,d);
723 } else {
724 extensional(home,x,d);
725 }
726 }
727 };
728
731 public:
734 : Test("Extensional::Reg::Sparse::PositionDomainPruning",
735 3,0,1,false,Gecode::IPL_DOM) {}
736
737 virtual bool solution(const Assignment& x) const {
738 return (x[0] == 0) && (x[1] == 0) && (x[2] == 0);
739 }
740
741 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
742 using namespace Gecode;
743 DFA d(0,
744 {
745 {0,0,1}, {0,1,2},
746 {1,0,3}, {2,1,4},
747 {3,0,5}, {4,1,6}
748 },
749 {5,6},false);
750 rel(home,x[2],IRT_EQ,0);
751 extensional(home,x,d);
752 }
753 };
754
756 class RegNoAcceptingPath : public Test {
757 public:
760 : Test("Extensional::Reg::Sparse::NoAcceptingPath",
761 3,0,0,false,Gecode::IPL_DOM) {
762 testsearch = false;
763 }
764
765 virtual bool solution(const Assignment& x) const {
766 (void)x;
767 return false;
768 }
769
770 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
771 using namespace Gecode;
772 // Every position has a forward transition, but the sole final state
773 // is only reached after four symbols.
774 DFA d(0,
775 {
776 {0,0,1}, {1,0,2}, {2,0,3}, {3,0,4}
777 },
778 {4},false);
779 extensional(home,x,d);
780 }
781 };
782
784 class RegTerminalMerged : public Test {
785 public:
788 : Test("Extensional::Reg::Sparse::TerminalMerged",
789 1,0,2,false,Gecode::IPL_DOM) {}
790
791 virtual bool solution(const Assignment& x) const {
792 (void)x;
793 return true;
794 }
795
796 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
797 using namespace Gecode;
798 DFA d(0,
799 {
800 {0,0,1}, {0,1,2}, {0,2,3}
801 },
802 {1,2,3},false);
803 extensional(home,x,d);
804 }
805 };
806
808 class RegTerminalUnmerged : public Test {
809 public:
812 : Test("Extensional::Reg::Sparse::TerminalUnmerged",
813 8,0,1,false,Gecode::IPL_DOM) {}
814
815 virtual bool solution(const Assignment& x) const {
816 return x[7] == 0;
817 }
818
819 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
820 using namespace Gecode;
821 // Symbols are unique per level. No symbol labels more than 128
822 // transitions, selecting the smallest Degree type, but 256 edges
823 // enter final states.
824 const int n_states = 511;
825 const int n_transitions = n_states - 1;
826 DFA::Transition* t = new DFA::Transition[n_transitions+1];
827 int ti = 0;
828 for (int depth=0; depth<8; depth++) {
829 const int first = (1 << depth) - 1;
830 const int width = 1 << depth;
831 for (int j=0; j<width; j++) {
832 const int i = first+j;
833 t[ti++] = DFA::Transition(i,2*depth,2*i+1);
834 t[ti++] = DFA::Transition(i,2*depth+1,2*i+2);
835 }
836 }
837 t[ti].i_state = -1;
838 int* f = new int[257];
839 for (int i=0; i<256; i++)
840 f[i] = 255+i;
841 f[256] = -1;
842 DFA d(0,t,f,false);
843 delete [] t;
844 delete [] f;
845 // Every word reaches the final layer, where only the even symbol
846 // has a transition into a final state.
847 IntVarArgs symbols(x.size());
848 for (int i=0; i<x.size()-1; i++)
849 symbols[i] = expr(home,2*i+x[i]);
850 symbols[7] = expr(home,14+2*x[7]);
851 extensional(home,symbols,d);
852 }
853 };
854
857 public:
860
862 : x(*this,3,0,2), list(*this,max) {
863 Gecode::extensional(*this,list,d);
864 }
865
867 : Gecode::Space(s) {
868 x.update(*this,s.x);
869 list.update(*this,s.list);
870 }
871
872 virtual Gecode::Space*
873 copy(void) {
874 return new OpenRegularSpace(*this);
875 }
876 };
877
880 public:
882 : ::Test::Base("Int::Extensional::OpenReg::Incremental",
883 TestTags::check()) {}
884
885 virtual bool
886 run(void) {
887 using namespace Gecode;
888 DFA d(0,{{0,0,1},{1,1,2}},{2},false);
889 OpenRegularSpace s(d);
890
891 if (s.status() == SS_FAILED)
892 return false;
893 s.list.append(s,s.x[0]);
894 if ((s.status() == SS_FAILED) ||
895 !s.x[0].assigned() || (s.x[0].val() != 0))
896 return false;
897 s.list.append(s,s.x[1]);
898 if ((s.status() == SS_FAILED) ||
899 !s.x[1].assigned() || (s.x[1].val() != 1))
900 return false;
901 s.list.close(s);
902 if ((s.status() == SS_FAILED) ||
903 !s.list.length().assigned() ||
904 (s.list.length().val() != 2))
905 return false;
906
907 // Pruning the first item to 1 also closes its aliased length.
908 DFA alias_dfa(0,{{0,1,1},{1,2,2}},{2},false);
909 OpenRegularSpace alias(alias_dfa,2);
910 alias.list.append(alias,alias.list.length());
911 return alias.status() == SS_FAILED;
912 }
913 };
914
917 public:
919 : ::Test::Base("Int::Extensional::OpenReg::LengthWake") {}
920
921 virtual bool
922 run(void) {
923 using namespace Gecode;
924 DFA d(0,{{0,0,1},{1,1,2}},{2},false);
925 OpenRegularSpace s(d,3);
926 rel(s,s.list.length(),IRT_GQ,2);
927 if (s.status() == SS_FAILED)
928 return false;
929 return (s.list.known_length() == 2) &&
930 s.list[0].assigned() &&
931 (s.list[0].val() == 0) &&
932 s.list[1].assigned() &&
933 (s.list[1].val() == 1);
934 }
935 };
936
939 public:
941 : ::Test::Base("Int::Extensional::OpenReg::MaxLength",
942 TestTags::check()) {}
943
944 virtual bool
945 run(void) {
946 using namespace Gecode;
947 // Accept 00 or 1000: only the first word fits a maximum of three.
948 DFA d(0,{{0,0,1},{1,0,5},{0,1,2},{2,0,3},{3,0,4},{4,0,5}},
949 {5},false);
950 OpenRegularSpace short_list(d,1);
951 if (short_list.status() != SS_FAILED)
952 return false;
953 OpenRegularSpace initial(d,3);
954 initial.list.append(initial,initial.x[0]);
955 if ((initial.status() == SS_FAILED) ||
956 !initial.x[0].assigned() || (initial.x[0].val() != 0))
957 return false;
958
959 OpenRegularSpace source(d,4);
960 source.list.append(source,source.x[0]);
961 if ((source.status() == SS_FAILED) || (source.x[0].size() != 2))
962 return false;
963 OpenRegularSpace* clone =
964 static_cast<OpenRegularSpace*>(source.clone());
965 rel(*clone,clone->list.length(),IRT_LQ,3);
966 const bool clone_ok = (clone->status() != SS_FAILED) &&
967 clone->x[0].assigned() && (clone->x[0].val() == 0);
968 delete clone;
969 if (!clone_ok || (source.x[0].size() != 2))
970 return false;
971
972 // A bound reduction also checks an already consumed prefix.
973 rel(source,source.x[0],IRT_EQ,1);
974 if (source.status() == SS_FAILED)
975 return false;
976 rel(source,source.list.length(),IRT_LQ,3);
977 if (source.status() != SS_FAILED)
978 return false;
979
980 // Keep the shorter nondeterministic path, even with a cycle.
981 DFA nfa = DFA::nfa(0,
982 {{0,0,1},{0,0,2},{1,0,3},{3,0,4},{4,0,5},{2,1,2},{2,0,5}},
983 {5});
984 OpenRegularSpace nondeterministic(nfa,2);
985 nondeterministic.list.append(nondeterministic,nondeterministic.x[0]);
986 if (nondeterministic.status() == SS_FAILED)
987 return false;
988 nondeterministic.list.append(nondeterministic,nondeterministic.x[1]);
989 if ((nondeterministic.status() == SS_FAILED) ||
990 !nondeterministic.x[1].assigned() ||
991 (nondeterministic.x[1].val() != 0))
992 return false;
993
994 // Pruning an item aliased with length lowers the maximum while open.
995 DFA alias_dfa(0,
996 {{0,2,1},{1,0,2},{2,0,3},{3,0,4},{0,3,5},{5,0,6},{6,0,4}},
997 {4},false);
998 OpenRegularSpace alias(alias_dfa,5);
999 alias.list.append(alias,alias.list.length());
1000 alias.list.append(alias,alias.x[0]);
1001 return (alias.status() != SS_FAILED) &&
1002 alias.list.length().assigned() &&
1003 (alias.list.length().val() == 3);
1004 }
1005 };
1006
1009 public:
1011 : ::Test::Base("Int::Extensional::OpenReg::Backward") {}
1012
1013 virtual bool
1014 run(void) {
1015 using namespace Gecode;
1016 DFA d(0,
1017 {
1018 {0,0,1}, {0,1,2},
1019 {1,0,3}, {2,1,4},
1020 {3,2,5}, {4,2,5}
1021 },
1022 {5},false);
1023 OpenRegularSpace s(d);
1024 rel(s,s.x[1],IRT_EQ,0);
1025 s.list.append(s,s.x[0]);
1026 if ((s.status() == SS_FAILED) ||
1027 (s.x[0].min() != 0) || (s.x[0].max() != 1))
1028 return false;
1029 s.list.append(s,s.x[1]);
1030 return (s.status() != SS_FAILED) &&
1031 s.x[0].assigned() && (s.x[0].val() == 0);
1032 }
1033 };
1034
1037 public:
1039 : ::Test::Base("Int::Extensional::OpenReg::DomainWake") {}
1040
1041 virtual bool
1042 run(void) {
1043 using namespace Gecode;
1044 DFA d(0,
1045 {
1046 {0,0,1}, {0,1,2},
1047 {1,0,3}, {2,1,4},
1048 {3,2,5}, {4,2,5}
1049 },
1050 {5},false);
1051 OpenRegularSpace s(d);
1052 s.list.append(s,s.x[0]);
1053 s.list.append(s,s.x[1]);
1054 if ((s.status() == SS_FAILED) || s.x[0].assigned())
1055 return false;
1056 rel(s,s.x[1],IRT_EQ,0);
1057 return (s.status() != SS_FAILED) &&
1058 s.x[0].assigned() && (s.x[0].val() == 0);
1059 }
1060 };
1061
1064 public:
1066 : ::Test::Base("Int::Extensional::OpenReg::Clone",TestTags::check()) {}
1067
1068 virtual bool
1069 run(void) {
1070 using namespace Gecode;
1071 DFA d(0,{{0,0,1},{1,1,2}},{2},false);
1072 OpenRegularSpace source(d);
1073 source.list.append(source,source.x[0]);
1074 if (source.status() == SS_FAILED)
1075 return false;
1076
1077 OpenRegularSpace* clone =
1078 static_cast<OpenRegularSpace*>(source.clone());
1079 clone->list.append(*clone,clone->x[1]);
1080 clone->list.close(*clone);
1081 const bool clone_ok =
1082 (clone->status() != SS_FAILED) &&
1083 (clone->list.known_length() == 2);
1084 delete clone;
1085
1086 source.list.close(source);
1087 const bool source_failed = source.status() == SS_FAILED;
1088 return clone_ok && source_failed &&
1089 (source.list.known_length() == 1);
1090 }
1091 };
1092
1094 class OpenRegularEmpty : public Test {
1095 public:
1096 enum class Kind { ACCEPT, REJECT, NO_FINALS };
1097 protected:
1099 public:
1101 : Test("Extensional::OpenReg::Empty::"+str(static_cast<int>(k)),1,0,0),
1102 kind(k) {}
1103 virtual bool solution(const Assignment&) const {
1104 return kind == Kind::ACCEPT;
1105 }
1107 using namespace Gecode;
1108 OpenIntVarList list(home,8);
1109 if (kind == Kind::ACCEPT) {
1110 extensional(home,list,DFA());
1111 } else if (kind == Kind::REJECT) {
1112 extensional(home,list,DFA(0,{{0,0,1}},{1},false));
1113 } else {
1114 extensional(home,list,
1115 DFA(0,{{0,0,0}},std::initializer_list<int>{},false));
1116 }
1117 if (kind != Kind::NO_FINALS)
1118 list.close(home);
1119 }
1120 };
1121
1123 class OpenRegularClosed : public Test {
1124 public:
1126 : Test("Extensional::OpenReg::Closed",3,0,2,false,Gecode::IPL_DOM) {}
1127 virtual bool solution(const Assignment& x) const {
1128 int parity = 0;
1129 for (int i=0; i<x.size(); i++) {
1130 if (x[i] == 2)
1131 return false;
1132 parity ^= x[i];
1133 }
1134 return parity == 0;
1135 }
1136 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
1137 using namespace Gecode;
1138 OpenIntVarList list(home,x.size());
1139 for (int i=0; i<x.size(); i++)
1140 list.append(home,x[i]);
1141 list.close(home);
1142 DFA d(0,{{0,0,0},{0,1,1},{1,0,1},{1,1,0}},{0},false);
1143 extensional(home,list,d);
1144 }
1145 };
1146
1149 using namespace Gecode;
1150 REG expression;
1151 for (int i = 0; i<ts.tuples(); i++) {
1152 REG r;
1153 for (int j = 0; j<ts.arity(); j++) {
1154 r += REG(ts[i][j]);
1155 }
1156 expression |= r;
1157 }
1158 DFA dfa(expression);
1159 return dfa;
1160 }
1161
1163 class TupleSetBase : public Test {
1164 protected:
1168 bool pos;
1171 public:
1174 : Test(TestTags::sweep(),
1175 "Extensional::TupleSet::" + extensional_kind_name(epk0) +
1176 "::" + str(p) + "::Base",
1177 4,1,5,true,Gecode::IPL_DOM),
1178 t(4), pos(p), epk(epk0) {
1179 using namespace Gecode;
1180 IntArgs t1({2, 1, 2, 4});
1181 IntArgs t2({2, 2, 1, 4});
1182 IntArgs t3({4, 3, 4, 1});
1183 IntArgs t4({1, 3, 2, 3});
1184 IntArgs t5({3, 3, 3, 2});
1185 t.add(t1).add(t1).add(t2).add(t2)
1186 .add(t3).add(t3).add(t4).add(t4)
1187 .add(t5).add(t5).add(t5).add(t5)
1188 .add(t5).add(t5).add(t5).add(t5)
1189 .add(t1).add(t1).add(t2).add(t2)
1190 .add(t3).add(t3).add(t4).add(t4)
1191 .add(t5).add(t5).add(t5).add(t5)
1192 .add(t5).add(t5).add(t5).add(t5)
1193 .finalize(epk);
1194 }
1195
1196 virtual bool solution(const Assignment& x) const {
1197 return pos == ((x[0] == 1 && x[1] == 3 && x[2] == 2 && x[3] == 3) ||
1198 (x[0] == 2 && x[1] == 1 && x[2] == 2 && x[3] == 4) ||
1199 (x[0] == 2 && x[1] == 2 && x[2] == 1 && x[3] == 4) ||
1200 (x[0] == 3 && x[1] == 3 && x[2] == 3 && x[3] == 2) ||
1201 (x[0] == 4 && x[1] == 3 && x[2] == 4 && x[3] == 1));
1202 }
1203
1204 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
1205 using namespace Gecode;
1206 TupleSet ts = TupleSet(t.arity(),tupleset2dfa(t),epk);
1207 assert(t == ts);
1208 assert(ts.representation() == epk);
1209 extensional(home, x, t, pos, ipl);
1210 }
1211
1213 Gecode::Reify r) {
1214 extensional(home, x, t, pos, r, ipl);
1215 }
1216 };
1217
1219 class TupleSetTest : public Test {
1220 protected:
1222 bool pos;
1228 bool toDFA;
1229 public:
1231 TupleSetTest(const std::string& s, bool p,
1232 Gecode::IntSet d0, Gecode::TupleSet ts0, bool td,
1235 : Test(tags,
1236 "Extensional::TupleSet::" + extensional_kind_name(epk0) +
1237 "::" + str(p) + "::" + s,
1238 ts0.arity(),d0,true,Gecode::IPL_DOM),
1239 pos(p), epk(epk0), ts(ts0), toDFA(td) {
1240 }
1241
1242 virtual bool solution(const Assignment& x) const {
1243 using namespace Gecode;
1244 for (int i=ts.tuples(); i--; ) {
1245 TupleSet::Tuple t = ts[i];
1246 bool same = true;
1247 for (int j=0; (j < ts.arity()) && same; j++)
1248 if (t[j] != x[j])
1249 same = false;
1250 if (same)
1251 return pos;
1252 }
1253 return !pos;
1254 }
1255
1256 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
1257 using namespace Gecode;
1258 if (toDFA) {
1259 TupleSet t = TupleSet(ts.arity(),tupleset2dfa(ts),epk);
1260 assert(ts == t);
1261 assert(t.representation() == epk);
1262 }
1263 extensional(home, x, ts, pos, ipl);
1264 }
1265
1267 Gecode::Reify r) {
1268 using namespace Gecode;
1269 extensional(home, x, ts, pos, r, ipl);
1270 }
1271 };
1272
1274 public:
1276 RandomTupleSetTest(const std::string& s, bool p,
1279 : TupleSetTest(s,p,d0,ts0,false,epk0) {
1280 testsearch = false;
1281 }
1282
1283 virtual Assignment* assignment(void) const {
1284 using namespace Gecode;
1285 return new RandomAssignment(arity, dom, 1000, _rand);
1286 }
1287 };
1288
1292 void tuple(Gecode::Support::RandomGenerator& rand) {
1293 if ((a % 2) == 0) {
1294 int row = rand(t.tuples());
1295 for (int i=0; i<n; i++)
1296 vals[i] = t[row][i];
1297 }
1298 }
1299 public:
1302 : RandomAssignment(t0.arity(),d,32,rand), t(t0) {
1303 tuple(rand);
1304 }
1307 tuple(rand);
1308 }
1309 };
1310
1312 class SparseTupleSet : public Test {
1314 public:
1315 SparseTupleSet(const std::string& name, int arity, int size)
1316 : Test("Extensional::TupleSet::Sparse::"+name,
1317 arity,0,size-1,false,Gecode::IPL_DOM), t(arity) {
1318 const int factors[] = {1,arity == 3 ? 7 : 3,
1319 arity == 3 ? 11 : 5,7,11,13};
1320 for (int i=0; i<size; i++) {
1322 for (int j=0; j<arity; j++)
1323 row[j] = (i*factors[j]) % size;
1324 t.add(row);
1325 }
1326 t.finalize(Gecode::EPK_SPARSE);
1327 testsearch = false;
1328 contest = CTL_NONE;
1329 }
1330 virtual Assignment* assignment(void) const {
1331 return new SparseAssignment(t,dom,_rand);
1332 }
1333 virtual bool solution(const Assignment& x) const {
1334 const int size = dom.max()+1;
1335 const int factors[] = {1,arity == 3 ? 7 : 3,
1336 arity == 3 ? 11 : 5,7,11,13};
1337 for (int i=1; i<arity; i++)
1338 if (x[i] != (x[0]*factors[i]) % size)
1339 return false;
1340 return true;
1341 }
1342 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
1343 Gecode::extensional(home,x,t,true,ipl);
1344 }
1345 };
1346
1349 bool nonempty;
1351 public:
1353 : Test("Extensional::TupleSet::Sparse::Nullary::"+str(n),
1354 1,0,0), nonempty(n), t(0) {
1355 if (nonempty)
1356 t.add(Gecode::IntArgs(0));
1357 t.finalize(Gecode::EPK_SPARSE);
1358 }
1359 virtual bool solution(const Assignment&) const {
1360 return nonempty;
1361 }
1365 };
1366
1369 int kind;
1371 public:
1372 SparseTupleSetIncremental(const std::string& name, int k)
1373 : Test("Extensional::TupleSet::Sparse::Incremental"+name,
1374 2,0,k == 2 ? 1 : 3,false,Gecode::IPL_DOM), kind(k), t(2) {
1375 using namespace Gecode;
1376 if (kind == 2)
1377 t.add(IntArgs({0,1})).add(IntArgs({1,0}));
1378 else
1379 t.add(IntArgs({0,0})).add(IntArgs({1,1}))
1380 .add(IntArgs({2,kind == 1 ? 1 : 2})).add(IntArgs({3,3}));
1381 t.finalize(EPK_SPARSE);
1382 }
1383 virtual bool solution(const Assignment& x) const {
1384 if (kind == 0)
1385 return (x[0] == 2) && (x[1] == 2);
1386 if (kind == 1)
1387 return false;
1388 return (x[0] == 1) && (x[1] == 0);
1389 }
1390 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
1391 using namespace Gecode;
1392 if (kind == 2) {
1393 BoolVarArgs b(2);
1394 for (int i=0; i<2; i++)
1395 b[i] = channel(home,x[i]);
1396 extensional(home,b,t,true,ipl);
1397 rel(home,b[0],IRT_NQ,0);
1398 } else {
1399 extensional(home,x,t,true,ipl);
1400 if (kind == 0) {
1401 rel(home,x[0],IRT_NQ,0);
1402 rel(home,x[0],IRT_NQ,1);
1403 rel(home,x[1],IRT_NQ,3);
1404 } else {
1405 rel(home,x[0],IRT_EQ,2);
1406 rel(home,x[1],IRT_NQ,1);
1407 }
1408 }
1409 }
1410 };
1411
1414 public:
1416 : ::Test::Base("Int::Extensional::TupleSet::Sparse::DisabledFailure") {}
1417
1418 virtual bool run(void) {
1419 using namespace Gecode;
1420
1421 class DisabledSpace : public Space {
1422 public:
1423 IntVarArray x;
1424 DisabledSpace(const TupleSet& t)
1425 : x(*this,2,0,1) {
1426 extensional(*this,x,t,true,IPL_DOM);
1427 }
1428 DisabledSpace(DisabledSpace& s)
1429 : Space(s) {
1430 x.update(*this,s.x);
1431 }
1432 virtual Space* copy(void) {
1433 return new DisabledSpace(*this);
1434 }
1435 };
1436
1437 TupleSet ts(2);
1438 ts.add(IntArgs({0,0})).add(IntArgs({1,1}));
1439 ts.finalize(EPK_SPARSE);
1440
1441 DisabledSpace* s = new DisabledSpace(ts);
1442 if (s->status() == SS_FAILED) {
1443 delete s;
1444 return false;
1445 }
1446 PropagatorGroup::all.disable(*s);
1447 rel(*s,s->x[0],IRT_EQ,0);
1448 rel(*s,s->x[1],IRT_EQ,1);
1449 if (s->status() == SS_FAILED) {
1450 delete s;
1451 return false;
1452 }
1453
1454 PropagatorGroup::all.enable(*s);
1455 const bool failed = (s->status() == SS_FAILED);
1456 delete s;
1457 return failed;
1458 }
1459 };
1460
1463 public:
1465 : ::Test::Base("Int::Extensional::TupleSet::Sparse::WideDelta") {}
1466
1467 virtual bool run(void) {
1468 using namespace Gecode;
1469
1470 const int gap = 1000000000;
1471 const int lower = gap / 2;
1472 TupleSet ts(1);
1473 ts.add(IntArgs({0})).add(IntArgs({gap}));
1474 ts.finalize(EPK_SPARSE);
1475
1476 class NegativeSpace : public Space {
1477 public:
1478 IntVar x;
1479 NegativeSpace(const TupleSet& t, int gap0, int lower0)
1480 : x(*this,0,gap0) {
1481 extensional(*this,IntVarArgs({x}),t,false,IPL_DOM);
1482 rel(*this,x,IRT_GQ,lower0);
1483 }
1484 NegativeSpace(NegativeSpace& s)
1485 : Space(s) {
1486 x.update(*this,s.x);
1487 }
1488 virtual Space* copy(void) {
1489 return new NegativeSpace(*this);
1490 }
1491 };
1492
1493 NegativeSpace* n = new NegativeSpace(ts,gap,lower);
1494 if ((n->status() == SS_FAILED) ||
1495 (n->x.min() != lower) || (n->x.max() != gap-1)) {
1496 delete n;
1497 return false;
1498 }
1499 delete n;
1500
1501 class ReifiedSpace : public Space {
1502 public:
1503 IntVar x;
1504 BoolVar b;
1505 ReifiedSpace(const TupleSet& t, int gap0, int lower0)
1506 : x(*this,0,gap0), b(*this,0,1) {
1507 extensional(*this,IntVarArgs({x}),t,true,
1508 Reify(b,RM_EQV),IPL_DOM);
1509 rel(*this,x,IRT_GQ,lower0);
1510 }
1511 ReifiedSpace(ReifiedSpace& s)
1512 : Space(s) {
1513 x.update(*this,s.x);
1514 b.update(*this,s.b);
1515 }
1516 virtual Space* copy(void) {
1517 return new ReifiedSpace(*this);
1518 }
1519 };
1520
1521 ReifiedSpace* r = new ReifiedSpace(ts,gap,lower);
1522 const bool ok = (r->status() != SS_FAILED) &&
1523 (r->x.min() == lower) && (r->x.max() == gap) &&
1524 !r->b.assigned();
1525 delete r;
1526 return ok;
1527 }
1528 };
1529
1532 public:
1534 : ::Test::Base(
1535 "Int::Extensional::TupleSet::Support::SingleRepresentation") {}
1536
1537 virtual bool run(void) {
1538 using namespace Gecode;
1539 TupleSet ts(2);
1540 for (int i=0; i<100; i++)
1541 ts.add(IntArgs({i, (i*3) % 100}));
1542 ts.finalize(EPK_SPARSE);
1543 if (ts.representation() != EPK_SPARSE) {
1544 std::cerr << "ERROR: Sparse support not available" << std::endl;
1545 return false;
1546 }
1547 if (ts.fst(0)->supports(ts.words(),ts.fst(0)->min) != nullptr) {
1548 std::cerr << "ERROR: Sparse range exposed dense support"
1549 << std::endl;
1550 return false;
1551 }
1552
1553 TupleSet tc(2);
1554 for (int i=0; i<100; i++)
1555 tc.add(IntArgs({i, (i*7) % 100}));
1556 tc.finalize(EPK_DENSE_COMPRESSED);
1557 if (tc.representation() != EPK_DENSE_COMPRESSED) {
1558 std::cerr << "ERROR: Compressed support not available" << std::endl;
1559 return false;
1560 }
1561 if (tc.fst(0)->supports(tc.words(),tc.fst(0)->min) != nullptr) {
1562 std::cerr << "ERROR: Compressed range exposed dense support"
1563 << std::endl;
1564 return false;
1565 }
1566
1567 TupleSet td(2);
1568 for (int i=0; i<100; i++)
1569 td.add(IntArgs({i, (i*11) % 100}));
1570 td.finalize();
1571 if (td.representation() != EPK_DENSE) {
1572 std::cerr << "ERROR: Default finalize did not keep dense support"
1573 << std::endl;
1574 return false;
1575 }
1576 if (td.fst(0)->supports(td.words(),td.fst(0)->min) == nullptr) {
1577 std::cerr << "ERROR: Dense range lost support data" << std::endl;
1578 return false;
1579 }
1580
1581 TupleSet empty_sparse(2);
1582 empty_sparse.finalize(EPK_SPARSE);
1583 if (empty_sparse.representation() != EPK_SPARSE) {
1584 std::cerr << "ERROR: Empty sparse table forgot representation"
1585 << std::endl;
1586 return false;
1587 }
1588 TupleSet empty_compressed(2);
1589 empty_compressed.finalize(EPK_DENSE_COMPRESSED);
1590 if (empty_compressed.representation() != EPK_DENSE_COMPRESSED) {
1591 std::cerr << "ERROR: Empty compressed table forgot representation"
1592 << std::endl;
1593 return false;
1594 }
1595 return true;
1596 }
1597 };
1598
1601 public:
1603 : ::Test::Base(
1604 "Int::Extensional::TupleSet::Support::OffsetBoundary") {}
1605
1606 virtual bool run(void) {
1608 const unsigned long long max =
1609 static_cast<unsigned long long>
1610 (std::numeric_limits<unsigned int>::max());
1611 unsigned int n_offsets = 0U;
1612 if (!support_offsets_size(max-1ULL,n_offsets) ||
1613 (n_offsets != std::numeric_limits<unsigned int>::max()))
1614 return false;
1615 if (support_offsets_size(max,n_offsets))
1616 return false;
1617 return !support_offsets_size(max+1ULL,n_offsets);
1618 }
1619 };
1620
1623 public:
1625 : ::Test::Base(
1626 "Int::Extensional::TupleSet::Support::TerminalFailure") {}
1627
1628 virtual bool run(void) {
1629 using namespace Gecode;
1630
1631 const int n = 371000;
1632 TupleSet ts(2);
1633 for (int i=0; i<n; i++)
1634 ts.add(IntArgs({i,n+i}));
1635
1636 bool rejected = false;
1637 try {
1638 ts.finalize(EPK_DENSE);
1639 } catch (const Gecode::Int::OutOfLimits&) {
1640 rejected = true;
1641 }
1642 if (!rejected || !ts.failed() || ts.finalized())
1643 return false;
1644
1645 try {
1646 (void) ts.representation();
1647 return false;
1648 } catch (const Gecode::Int::NotYetFinalized&) {
1649 }
1650
1651 try {
1652 ts.finalize(EPK_SPARSE);
1653 return false;
1654 } catch (const Gecode::Int::AlreadyFinalized&) {
1655 }
1656
1657 try {
1658 ts.add(IntArgs({0,0}));
1659 return false;
1660 } catch (const Gecode::Int::AlreadyFinalized&) {
1661 }
1662
1663 class PostingSpace : public Space {
1664 public:
1665 IntVarArray x;
1666 PostingSpace(const TupleSet& t)
1667 : x(*this,2,0,1) {
1668 extensional(*this,x,t);
1669 }
1670 PostingSpace(PostingSpace& s)
1671 : Space(s) {
1672 x.update(*this,s.x);
1673 }
1674 virtual Space* copy(void) {
1675 return new PostingSpace(*this);
1676 }
1677 };
1678
1679 try {
1680 PostingSpace* s = new PostingSpace(ts);
1681 delete s;
1682 return false;
1683 } catch (const Gecode::Int::NotYetFinalized&) {
1684 }
1685 return true;
1686 }
1687 };
1688
1691 public:
1693 : ::Test::Base(
1694 "Int::Extensional::TupleSet::Support::DFARepresentation") {}
1695
1696 virtual bool run(void) {
1697 using namespace Gecode;
1698
1699 DFA dfa((REG(0) + REG(1)) | (REG(2) + REG(3)));
1700 TupleSet sparse(2,dfa,EPK_SPARSE);
1701 if ((sparse.representation() != EPK_SPARSE) ||
1702 (sparse.tuples() != 2))
1703 return false;
1704
1705 TupleSet compressed(2,dfa,EPK_DENSE_COMPRESSED);
1706 if ((compressed.representation() != EPK_DENSE_COMPRESSED) ||
1707 (compressed.tuples() != 2))
1708 return false;
1709
1710 TupleSet dense(2,dfa);
1711 if ((dense.representation() != EPK_DENSE) || (dense.tuples() != 2))
1712 return false;
1713
1714 TupleSet empty(3,dfa,EPK_SPARSE);
1715 return (empty.representation() == EPK_SPARSE) &&
1716 (empty.tuples() == 0);
1717 }
1718 };
1719
1722 public:
1724 : ::Test::Base(
1725 "Int::Extensional::TupleSet::Support::DisabledClone") {}
1726
1727 virtual bool run(void) {
1728 using namespace Gecode;
1729
1730 enum Mode {
1731 MODE_POSITIVE,
1732 MODE_NEGATIVE,
1733 MODE_REIFIED
1734 };
1735
1736 class CloneSpace : public Space {
1737 public:
1738 IntVarArray x;
1739 BoolVar b;
1740 CloneSpace(const TupleSet& t, Mode mode)
1741 : x(*this,2,0,2), b(*this,0,1) {
1742 if (mode == MODE_REIFIED)
1743 extensional(*this,x,t,true,Reify(b,RM_EQV),IPL_DOM);
1744 else
1745 extensional(*this,x,t,mode == MODE_POSITIVE,IPL_DOM);
1746 }
1747 CloneSpace(CloneSpace& s)
1748 : Space(s) {
1749 x.update(*this,s.x);
1750 b.update(*this,s.b);
1751 }
1752 virtual Space* copy(void) {
1753 return new CloneSpace(*this);
1754 }
1755 };
1756
1757 auto check = [](ExtensionalPropKind epk) {
1758 TupleSet ts(2);
1759 ts.add(IntArgs({0,0})).add(IntArgs({1,1})).add(IntArgs({2,2}));
1760 ts.finalize(epk);
1761
1762 CloneSpace* source = new CloneSpace(ts,MODE_POSITIVE);
1763 if (source->status() == SS_FAILED) {
1764 delete source;
1765 return false;
1766 }
1767 PropagatorGroup::all.disable(*source);
1768 rel(*source,source->x[0],IRT_EQ,1);
1769 if ((source->status() == SS_FAILED) ||
1770 !source->x[0].assigned() || (source->x[0].val() != 1) ||
1771 (source->x[1].size() != 3)) {
1772 delete source;
1773 return false;
1774 }
1775
1776 CloneSpace* clone = static_cast<CloneSpace*>(source->clone());
1777 PropagatorGroup::all.enable(*clone);
1778 const bool clone_ok = (clone->status() != SS_FAILED) &&
1779 clone->x[1].assigned() && (clone->x[1].val() == 1);
1780 delete clone;
1781
1782 PropagatorGroup::all.enable(*source);
1783 const bool source_ok = (source->status() != SS_FAILED) &&
1784 source->x[1].assigned() && (source->x[1].val() == 1);
1785 delete source;
1786 return clone_ok && source_ok;
1787 };
1788
1789 auto check_empty = [](ExtensionalPropKind epk, Mode mode) {
1790 TupleSet ts(2);
1791 ts.add(IntArgs({0,0})).add(IntArgs({1,1}));
1792 ts.finalize(epk);
1793
1794 CloneSpace* source = new CloneSpace(ts,mode);
1795 if (source->status() == SS_FAILED) {
1796 delete source;
1797 return false;
1798 }
1799 PropagatorGroup::all.disable(*source);
1800 if (mode == MODE_NEGATIVE) {
1801 rel(*source,source->x[0],IRT_EQ,2);
1802 } else {
1803 rel(*source,source->x[0],IRT_EQ,0);
1804 rel(*source,source->x[1],IRT_EQ,1);
1805 }
1806 if (source->status() == SS_FAILED) {
1807 delete source;
1808 return false;
1809 }
1810
1811 auto verify = [mode](CloneSpace& s) {
1812 const SpaceStatus status = s.status();
1813 if (mode == MODE_POSITIVE)
1814 return status == SS_FAILED;
1815 if (status == SS_FAILED)
1816 return false;
1817 if (mode == MODE_REIFIED)
1818 return s.b.assigned() && (s.b.val() == 0);
1819 return s.x[1].size() == 3;
1820 };
1821
1822 CloneSpace* clone = static_cast<CloneSpace*>(source->clone());
1823 PropagatorGroup::all.enable(*clone);
1824 const bool clone_ok = verify(*clone);
1825 delete clone;
1826
1827 PropagatorGroup::all.enable(*source);
1828 const bool source_ok = verify(*source);
1829 delete source;
1830 return clone_ok && source_ok;
1831 };
1832
1833 for (ExtensionalPropKind epk :
1834 {EPK_DENSE,EPK_DENSE_COMPRESSED}) {
1835 if (!check(epk))
1836 return false;
1837 for (Mode mode : {MODE_POSITIVE,MODE_NEGATIVE,MODE_REIFIED})
1838 if (!check_empty(epk,mode))
1839 return false;
1840 }
1841 return true;
1842 }
1843 };
1844
1847 public:
1849 : ::Test::Base(
1850 "Int::Extensional::TupleSet::Auto::DefaultDispatch",
1851 TestTags::check()) {}
1852
1853 virtual bool run(void) {
1854 using namespace Gecode;
1855
1856 TupleSet dense(2);
1857 dense.add(IntArgs({0,0})).add(IntArgs({1,1}));
1858 dense.finalize(EPK_AUTO);
1859 if (dense.representation() != EPK_DENSE) {
1860 std::cerr << "ERROR: Small AUTO table did not select dense"
1861 << std::endl;
1862 return false;
1863 }
1864
1865 class PositiveSpace : public Space {
1866 public:
1867 IntVarArray x;
1868 PositiveSpace(const TupleSet& t) : x(*this,2,0,1) {
1869 extensional(*this, x, t);
1870 branch(*this, x, INT_VAR_NONE(), INT_VAL_MIN());
1871 }
1872 PositiveSpace(PositiveSpace& s) : Space(s) {
1873 x.update(*this,s.x);
1874 }
1875 virtual Space* copy(void) {
1876 return new PositiveSpace(*this);
1877 }
1878 };
1879
1880 PositiveSpace* dense_root = new PositiveSpace(dense);
1881 DFS<PositiveSpace> dense_engine(dense_root);
1882 delete dense_root;
1883 int dense_solutions = 0;
1884 while (PositiveSpace* sol = dense_engine.next()) {
1885 if (sol->x[0].val() != sol->x[1].val()) {
1886 delete sol;
1887 return false;
1888 }
1889 dense_solutions++;
1890 delete sol;
1891 }
1892 if (dense_solutions != 2)
1893 return false;
1894
1895 const int n = 5000;
1896 TupleSet compressed(2);
1897 for (int i=0; i<n; i++)
1898 compressed.add(IntArgs({i, (i*7) % n}));
1899 compressed.finalize(EPK_AUTO);
1900 if (compressed.representation() != EPK_DENSE_COMPRESSED) {
1901 std::cerr << "ERROR: Large AUTO table did not select compressed"
1902 << std::endl;
1903 return false;
1904 }
1905
1906 class ReifiedSpace : public Space {
1907 public:
1908 IntVarArray x;
1909 BoolVar b;
1910 ReifiedSpace(const TupleSet& t, int n0)
1911 : x(*this,2,0,n0-1), b(*this,0,1) {
1912 extensional(*this, x, t, Reify(b,RM_EQV));
1913 rel(*this, b, IRT_EQ, 1);
1914 rel(*this, x[0], IRT_EQ, 3);
1915 branch(*this, x, INT_VAR_NONE(), INT_VAL_MIN());
1916 }
1917 ReifiedSpace(ReifiedSpace& s) : Space(s) {
1918 x.update(*this,s.x);
1919 b.update(*this,s.b);
1920 }
1921 virtual Space* copy(void) {
1922 return new ReifiedSpace(*this);
1923 }
1924 };
1925
1926 ReifiedSpace* compressed_root = new ReifiedSpace(compressed,n);
1927 DFS<ReifiedSpace> compressed_engine(compressed_root);
1928 delete compressed_root;
1929 ReifiedSpace* compressed_sol = compressed_engine.next();
1930 if (compressed_sol == nullptr)
1931 return false;
1932 const bool ok =
1933 (compressed_sol->x[0].val() == 3) &&
1934 (compressed_sol->x[1].val() == ((3*7) % n));
1935 delete compressed_sol;
1936 ReifiedSpace* extra = compressed_engine.next();
1937 const bool no_extra = (extra == nullptr);
1938 delete extra;
1939 return ok && no_extra;
1940 }
1941 };
1942
1945 public:
1947 : ::Test::Base(
1948 "Int::Extensional::TupleSet::DenseCompressed::WideGap") {}
1949
1950 virtual bool run(void) {
1951 using namespace Gecode;
1952
1953 const int gap = 1000000000;
1954 TupleSet ts(1);
1955 ts.add(IntArgs({0})).add(IntArgs({gap}));
1956 ts.finalize(EPK_DENSE_COMPRESSED);
1957
1958 class NegativeSpace : public Space {
1959 public:
1960 IntVar x;
1961 NegativeSpace(const TupleSet& t, int gap0)
1962 : x(*this,0,gap0) {
1963 extensional(*this, IntVarArgs({x}), t, false, IPL_DOM);
1964 }
1965 NegativeSpace(NegativeSpace& s) : Space(s) {
1966 x.update(*this,s.x);
1967 }
1968 virtual Space* copy(void) {
1969 return new NegativeSpace(*this);
1970 }
1971 };
1972
1973 NegativeSpace* ns = new NegativeSpace(ts,gap);
1974 if (ns->status() == SS_FAILED) {
1975 delete ns;
1976 return false;
1977 }
1978 if (ns->x.in(0) || ns->x.in(gap)) {
1979 delete ns;
1980 return false;
1981 }
1982 delete ns;
1983
1984 class ReifiedSpace : public Space {
1985 public:
1986 IntVar x;
1987 BoolVar b;
1988 ReifiedSpace(const TupleSet& t, int gap0, bool force)
1989 : x(*this,0,gap0), b(*this,0,1) {
1990 extensional(*this, IntVarArgs({x}), t, true,
1991 Reify(b,RM_EQV), IPL_DOM);
1992 if (force) {
1993 rel(*this, b, IRT_EQ, 1);
1994 rel(*this, x, IRT_EQ, 0);
1995 }
1996 }
1997 ReifiedSpace(ReifiedSpace& s) : Space(s) {
1998 x.update(*this,s.x);
1999 b.update(*this,s.b);
2000 }
2001 virtual Space* copy(void) {
2002 return new ReifiedSpace(*this);
2003 }
2004 };
2005
2006 ReifiedSpace* rs = new ReifiedSpace(ts,gap,false);
2007 if (rs->status() == SS_FAILED) {
2008 delete rs;
2009 return false;
2010 }
2011 delete rs;
2012
2013 ReifiedSpace* rfs = new ReifiedSpace(ts,gap,true);
2014 if (rfs->status() == SS_FAILED) {
2015 delete rfs;
2016 return false;
2017 }
2018 if (!rfs->x.assigned() || (rfs->x.val() != 0) ||
2019 !rfs->b.assigned() || (rfs->b.val() != 1)) {
2020 delete rfs;
2021 return false;
2022 }
2023 delete rfs;
2024
2025 class PositiveDeltaSpace : public Space {
2026 public:
2027 IntVar x;
2028 PositiveDeltaSpace(const TupleSet& t, int gap0)
2029 : x(*this,0,gap0) {
2030 extensional(*this, IntVarArgs({x}), t, true, IPL_DOM);
2031 rel(*this, x, IRT_NQ, 0);
2032 }
2033 PositiveDeltaSpace(PositiveDeltaSpace& s) : Space(s) {
2034 x.update(*this,s.x);
2035 }
2036 virtual Space* copy(void) {
2037 return new PositiveDeltaSpace(*this);
2038 }
2039 };
2040
2041 PositiveDeltaSpace* ps = new PositiveDeltaSpace(ts,gap);
2042 if (ps->status() == SS_FAILED) {
2043 delete ps;
2044 return false;
2045 }
2046 if (!ps->x.assigned() || (ps->x.val() != gap)) {
2047 delete ps;
2048 return false;
2049 }
2050 delete ps;
2051
2052 return true;
2053 }
2054 };
2055
2057 class TupleSetLarge : public Test {
2058 protected:
2060 bool pos;
2065 public:
2068 : Test(TestTags::sweep(),
2069 "Extensional::TupleSet::" + extensional_kind_name(epk0) +
2070 "::" + str(p) + "::Large",
2071 5,1,5,true,Gecode::IPL_DOM),
2072 pos(p), epk(epk0), t(5) {
2073 using namespace Gecode;
2074
2075 CpltAssignment ass(5, IntSet(1, 5));
2076 while (ass.has_more()) {
2077 if (_rand(100) <= prob*100) {
2078 IntArgs tuple(5);
2079 for (int i = 5; i--; ) tuple[i] = ass[i];
2080 t.add(tuple);
2081 }
2082 ass.next(_rand);
2083 }
2084 t.finalize(epk);
2085 }
2086
2087 virtual bool solution(const Assignment& x) const {
2088 using namespace Gecode;
2089 for (int i = 0; i < t.tuples(); ++i) {
2090 TupleSet::Tuple l = t[i];
2091 bool same = true;
2092 for (int j = 0; j < t.arity() && same; ++j)
2093 if (l[j] != x[j]) same = false;
2094 if (same)
2095 return pos;
2096 }
2097 return !pos;
2098 }
2099
2100 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
2101 using namespace Gecode;
2102 extensional(home, x, t, pos, ipl);
2103 }
2104
2106 Gecode::Reify r) {
2107 using namespace Gecode;
2108 extensional(home, x, t, pos, r, ipl);
2109 }
2110 };
2111
2113 class TupleSetBool : public Test {
2114 protected:
2116 bool pos;
2121 public:
2124 : Test(TestTags::sweep(),
2125 "Extensional::TupleSet::" + extensional_kind_name(epk0) +
2126 "::" + str(p) + "::Bool",
2127 5,0,1,true), pos(p), epk(epk0), t(5) {
2128 using namespace Gecode;
2129
2130 CpltAssignment ass(5, IntSet(0, 1));
2131 while (ass.has_more()) {
2132 if (_rand(100) <= prob*100) {
2133 IntArgs tuple(5);
2134 for (int i = 5; i--; ) tuple[i] = ass[i];
2135 t.add(tuple);
2136 }
2137 ass.next(_rand);
2138 }
2139 t.finalize(epk);
2140 }
2141
2142 virtual bool solution(const Assignment& x) const {
2143 using namespace Gecode;
2144 for (int i = 0; i < t.tuples(); ++i) {
2145 TupleSet::Tuple l = t[i];
2146 bool same = true;
2147 for (int j = 0; j < t.arity() && same; ++j)
2148 if (l[j] != x[j])
2149 same = false;
2150 if (same)
2151 return pos;
2152 }
2153 return !pos;
2154 }
2155
2156 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
2157 using namespace Gecode;
2158 BoolVarArgs y(x.size());
2159 for (int i = x.size(); i--; )
2160 y[i] = channel(home, x[i]);
2161 extensional(home, y, t, pos, ipl);
2162 }
2163
2165 Gecode::Reify r) {
2166 using namespace Gecode;
2167 BoolVarArgs y(x.size());
2168 for (int i = x.size(); i--; )
2169 y[i] = channel(home, x[i]);
2170 extensional(home, y, t, pos, r, ipl);
2171 }
2172 };
2173
2176 public:
2180 using namespace Gecode;
2182 int arity = 2;
2183 int n_tuples = 5*5;
2184 while (n_tuples < size) {
2185 arity++;
2186 n_tuples*=5;
2187 }
2189 TupleSet ts(arity);
2190 CpltAssignment ass(arity, IntSet(0, 4));
2191 for (int i = size; i--; ) {
2192 assert(ass.has_more());
2193 IntArgs tuple(arity);
2194 for (int j = arity; j--; ) tuple[j] = ass[j];
2195 ts.add(tuple);
2196 ass.next(rand);
2197 }
2198 ts.finalize(epk);
2199 assert(ts.tuples() == size);
2200 // Create and register test
2201 (void) new TupleSetTest(std::to_string(size),pos,IntSet(0,4),ts,
2202 size <= 128, epk);
2203 }
2204 };
2205
2206 Gecode::TupleSet randomTupleSet(int n, int min, int max, double prob,
2209 using namespace Gecode;
2210 TupleSet t(n);
2211 CpltAssignment ass(n, IntSet(min, max));
2212 while (ass.has_more()) {
2213 if (rand(100) <= prob*100) {
2214 IntArgs tuple(n);
2215 for (int i = n; i--; ) tuple[i] = ass[i];
2216 t.add(tuple);
2217 }
2218 ass.next(rand);
2219 }
2220 t.finalize(epk);
2221 return t;
2222 }
2223
2225 class Create {
2226 public:
2228 Create(void) {
2229 // This code is executed on load, and thus a random number generator source from the supplied
2230 // seed is not available.
2231 // In order to get interesting data her, but still have deterministic and repeatable execution, a fixed seed
2232 // is used for a local random number generator.
2233 // TODO: Make this code later on test run, and use the supplied seed/random number generator.
2235
2236 using namespace Gecode;
2237 for (ExtensionalPropKind epk :
2238 { EPK_DENSE, EPK_SPARSE, EPK_DENSE_COMPRESSED }) {
2239 for (bool pos : { false, true }) {
2240 {
2241 TupleSet ts(4);
2242 ts.add({2, 1, 2, 4}).add({2, 2, 1, 4})
2243 .add({4, 3, 4, 1}).add({1, 3, 2, 3})
2244 .add({3, 3, 3, 2}).add({5, 1, 4, 4})
2245 .add({2, 5, 1, 5}).add({4, 3, 5, 1})
2246 .add({1, 5, 2, 5}).add({5, 3, 3, 2})
2247 .finalize(epk);
2248 (void) new TupleSetTest("A",pos,IntSet(0,6),ts,true,epk);
2249 }
2250 {
2251 TupleSet ts(4);
2252 ts.finalize(epk);
2253 (void) new TupleSetTest("Empty",pos,IntSet(1,2),ts,true,epk);
2254 }
2255 {
2256 TupleSet ts(4);
2257 for (int n=1024*16; n--; )
2258 ts.add({1,2,3,4});
2259 ts.finalize(epk);
2260 (void) new TupleSetTest("Assigned",pos,IntSet(1,4),ts,true,epk);
2261 }
2262 {
2263 TupleSet ts(1);
2264 ts.add({1}).add({2}).add({3}).finalize(epk);
2265 (void) new TupleSetTest("Single",pos,IntSet(-4,4),ts,true,epk);
2266 }
2267 {
2269 TupleSet ts(3);
2270 ts.add({m+0,m+1,m+2}).add({m+4,m+1,m+3})
2271 .add({m+2,m+3,m+0}).add({m+2,m+3,m+0})
2272 .add({m+1,m+2,m+5}).add({m+2,m+3,m+0})
2273 .add({m+3,m+6,m+5}).finalize(epk);
2274 (void) new TupleSetTest("Min",pos,IntSet(m,m+7),ts,true,epk);
2275 }
2276 {
2278 TupleSet ts(3);
2279 ts.add({M-0,M-1,M-2}).add({M-4,M-1,M-3})
2280 .add({M-2,M-3,M-0}).add({M-2,M-3,M-0})
2281 .add({M-1,M-2,M-5}).add({M-2,M-3,M-0})
2282 .add({M-3,M-6,M-5}).finalize(epk);
2283 (void) new TupleSetTest("Max",pos,IntSet(M-7,M),ts,true,epk);
2284 }
2285 {
2288 TupleSet ts(3);
2289 ts.add({M-0,m+1,M-2}).add({m+4,M-1,M-3})
2290 .add({m+2,M-3,m+0}).add({M-2,M-3,M-0})
2291 .finalize(epk);
2292 (void) new TupleSetTest("MinMax",pos,
2293 IntSet(IntArgs({m,m+1,m+4,M-3,M-2,M})),
2294 ts,true,epk);
2295 }
2296 {
2297 TupleSet ts(7);
2298 const int triangle_tuples =
2299 (epk == EPK_DENSE) ? 10000 : 1000;
2300 for (int i = 0; i < triangle_tuples; i++) {
2301 IntArgs tuple(7);
2302 for (int j = 0; j < 7; j++) {
2303 tuple[j] = rand(j+1);
2304 }
2305 ts.add(tuple);
2306 }
2307 ts.finalize(epk);
2308 (void) new RandomTupleSetTest("Triangle",pos,IntSet(0,6),ts,epk);
2309 }
2310 {
2311 for (int i = 0; i <= 64*6; i+=32)
2312 (void) TupleSetTestSize(i, pos, epk, rand);
2313 }
2314 {
2315 const double prob_small =
2316 (epk == EPK_DENSE) ? 0.05 : 0.01;
2317 (void) new RandomTupleSetTest("Rand(10,-1,2)", pos,
2318 IntSet(-1,2),
2319 randomTupleSet(10, -1, 2, prob_small,
2320 epk, rand),
2321 epk);
2322 if (epk == EPK_DENSE)
2323 (void) new RandomTupleSetTest("Rand(5,-10,10)", pos,
2324 IntSet(-10,10),
2325 randomTupleSet(5, -10, 10, 0.05,
2326 epk, rand),
2327 epk);
2328 }
2329 {
2330 TupleSet t(5);
2331 CpltAssignment ass(4, IntSet(1, 4));
2332 while (ass.has_more()) {
2333 IntArgs tuple(5);
2334 tuple[4] = 1;
2335 for (int i = 4; i--; ) tuple[i] = ass[i];
2336 t.add(tuple);
2337 ass.next(rand);
2338 }
2339 t.add({2,2,4,3,4});
2340 t.finalize(epk);
2341 (void) new TupleSetTest("FewLast",pos,IntSet(1,4),t,false,epk);
2342 }
2343 {
2344 TupleSet t(4);
2345 CpltAssignment ass(4, IntSet(1, 6));
2346 while (ass.has_more()) {
2347 t.add({ass[0],0,ass[1],ass[2]});
2348 ass.next(rand);
2349 }
2350 t.add({2,-1,3,4});
2351 t.finalize(epk);
2352 (void) new TupleSetTest("FewMiddle",pos,IntSet(-1,6),t,false,epk);
2353 }
2354 if (epk == EPK_DENSE) {
2355 TupleSet t(10);
2356 CpltAssignment ass(9, IntSet(1, 4));
2357 while (ass.has_more()) {
2358 if (rand(100) <= 0.25*100) {
2359 IntArgs tuple(10);
2360 tuple[0] = 2;
2361 for (int i = 9; i--; )
2362 tuple[i+1] = ass[i];
2363 t.add(tuple);
2364 }
2365 ass.next(rand);
2366 }
2367 t.add({1,1,1,1,1,1,1,1,1,1});
2368 t.add({1,2,3,4,4,2,1,2,3,3});
2369 t.finalize(epk);
2370 (void) new RandomTupleSetTest("FewHuge",pos,IntSet(1,4),t,epk);
2371 }
2372 (void) new TupleSetBase(pos,epk);
2373 (void) new TupleSetLarge(0.05,pos,epk);
2374 (void) new TupleSetBool(0.3,pos,epk);
2375 }
2376 }
2377 }
2378 };
2379
2381
2385
2387
2392
2397
2400
2401 RegOpt ro0(CHAR_MAX-1);
2402 RegOpt ro1(CHAR_MAX);
2403 RegOpt ro2(static_cast<int>(UCHAR_MAX-1));
2404 RegOpt ro3(static_cast<int>(UCHAR_MAX));
2405 RegOpt ro4(SHRT_MAX-1);
2406 RegOpt ro5(SHRT_MAX);
2407 RegOpt ro6(static_cast<int>(USHRT_MAX-1));
2408 RegOpt ro7(static_cast<int>(USHRT_MAX));
2409
2442
2445 public:
2447 using namespace Gecode;
2448 TupleSet equal(2), zero(2), full(2), first_zero(2);
2449 equal.add(IntArgs({0,0})).add(IntArgs({1,1})).finalize(EPK_SPARSE);
2450 zero.add(IntArgs({0,0})).finalize(EPK_SPARSE);
2451 full.add(IntArgs({0,0})).add(IntArgs({0,1}))
2452 .add(IntArgs({1,0})).add(IntArgs({1,1})).finalize(EPK_SPARSE);
2453 first_zero.add(IntArgs({0,0})).add(IntArgs({0,1}))
2454 .finalize(EPK_SPARSE);
2455 for (bool positive : {false,true}) {
2456 (void) new TupleSetTest("Equal",positive,IntSet(0,1),equal,
2457 false,EPK_SPARSE,TestTags::standard());
2458 (void) new TupleSetTest("Zero",positive,IntSet(0,1),zero,
2459 false,EPK_SPARSE,TestTags::standard());
2460 (void) new TupleSetTest("Full",positive,IntSet(0,1),full,
2461 false,EPK_SPARSE,TestTags::standard());
2462 (void) new TupleSetTest("FirstZero",positive,IntSet(0,1),first_zero,
2463 false,EPK_SPARSE,TestTags::standard());
2464 }
2465 }
2467
2486
2487 }
2488}}
2489
2490
2491// STATISTICS: test-int
Passing Boolean variables.
Definition int.hh:739
Boolean integer variables.
Definition int.hh:534
Specification of a DFA transition.
Definition int.hh:2629
int i_state
input state
Definition int.hh:2631
int o_state
output state Default constructor
Definition int.hh:2633
Finite automaton with deterministic construction by default.
Definition int.hh:2620
static DFA nfa(int s, Transition t[], int f[])
Construct a nondeterministic finite automaton.
Definition dfa.cpp:545
Depth-first search engine.
Definition search.hh:1211
Passing integer arguments.
Definition int.hh:653
Integer sets.
Definition int.hh:179
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Integer variables.
Definition int.hh:390
Exception: Tuple set already finalized
Exception: Tuple set not yet finalized
Exception: Value out of limits
Definition exception.hpp:44
Open list of integer variables.
Definition int.hh:1076
void close(Space &home)
Close the list at its materialized length.
IntVar length(void) const
Return the eventual-length variable.
void append(Space &home, Var x)
Append variable x.
static PropagatorGroup all
Group of all propagators.
Definition core.hpp:796
Regular expressions over integer values.
Reification specification.
Definition int.hh:1176
virtual T * next(void)
Return next solution (nullptr, if none exists or search has been stopped).
Definition base.hpp:46
Computation spaces.
Definition core.hpp:1787
int min
Minimum value.
Definition int.hh:2841
const BitSetData * supports(unsigned int n_words, int n) const
Return the dense supports for value n.
Definition tuple-set.hpp:50
Class representing a set of tuples.
Definition int.hh:2821
bool failed(void) const
Has tuple-set finalization failed.
int tuples(void) const
Number of tuples.
bool finalized(void) const
Is tuple set successfully finalized.
ExtensionalPropKind representation(void) const
Return materialized tuple-set representation.
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
int * Tuple
Type of a tuple.
Definition int.hh:2828
void finalize(void)
Finalize tuple set with dense support data.
const Range * fst(int i) const
Return first range for position i.
unsigned int words(void) const
Return number of required bit set words.
int arity(void) const
Arity of tuple set.
bool assigned(void) const
Test if all variables are assigned.
Definition array.hpp:1045
int size(void) const
Return size of array (number of elements).
Definition array.hpp:945
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition array.hpp:1032
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition var.hpp:116
Gecode::Support::RandomGenerator _rand
Random number generator.
Definition test.hh:238
Base(std::string s)
Create and register a standard test with name s.
Definition test.cpp:125
const std::string & name(void) const
Return name of test.
Definition test.hpp:91
TestTags tags(void) const
Return tags for test.
Definition test.hpp:95
Base class for assignments
Definition int.hh:73
Gecode::IntSet d
Domain for each variable.
Definition int.hh:76
int n
Number of variables.
Definition int.hh:75
int size(void) const
Return number of variables.
Definition int.hpp:46
Generate all assignments.
Definition int.hh:93
virtual void next(Gecode::Support::RandomGenerator &rand)
Move to next assignment.
Definition int.cpp:49
virtual bool has_more(void) const
Test whether all assignments have been iterated.
Definition int.hpp:61
Help class to create and register tests.
Create(void)
Perform creation and registration.
Dense-compressed iterators should skip unsupported value gaps.
Test backward pruning after appending a restricted variable.
Test independent extension after cloning.
Check domain consistency of the regular constraint on a closed open list.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
virtual bool solution(const Assignment &x) const
Check for solution.
Test domain notification on an appended variable.
Test empty words and automata without accepting states.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &)
Post constraint.
virtual bool solution(const Assignment &) const
Check for solution.
Test appending and closing an open regular list.
Materializing required positions wakes regular filtering.
Filter prefixes whose accepting continuations exceed the length bound.
Space used by open regular tests.
OpenRegularSpace(Gecode::DFA d, int max=8)
virtual Gecode::Space * copy(void)
Copying member function.
RandomTupleSetTest(const std::string &s, bool p, Gecode::IntSet d0, Gecode::TupleSet ts0, Gecode::ExtensionalPropKind epk0)
Create and register test.
virtual Assignment * assignment(void) const
Create and register initial assignment.
Test an acyclic DFA whose states can occur at different depths
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
virtual bool solution(const Assignment &x) const
Test whether x is solution
RegAcyclicReconvergence(void)
Create and register test.
Test the Boolean-view regular posting route
RegBoolCyclicFrontier(void)
Create and register test.
virtual bool solution(const Assignment &x) const
Test whether x is solution
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Test a cyclic DFA whose frontier states recur across many layers
RegCyclicFrontier(void)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Test with regular expression for distinct constraint
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegDistinct(void)
Create and register test.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Test repeated final states in dense and sparse DFA specifications
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
virtual bool solution(const Assignment &x) const
Check for solution.
RegDuplicateFinals(bool minimize0, bool sparse0)
RegEmptyDFA(void)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Test for empty regular expression
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegEmptyREG(void)
Create and register test.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Test cloning an assigned NFA prefix with branching and reconvergence
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegNFAPrefix(bool b)
Create and register test.
bool boolean
Whether to post through Boolean views.
virtual bool solution(const Assignment &x) const
Test whether x is a solution
Test failure when the forward frontier misses the terminal boundary
RegNoAcceptingPath(void)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Test for optimizations
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
virtual bool solution(const Assignment &x) const
Test whether x is solution
RegOpt(int n0)
Create and register test.
int n
DFA size characteristic.
Test backward pruning caused by a position-specific domain
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegPositionDomainPruning(void)
Create and register test.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Test deterministic generated DFAs against a reference runner
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
unsigned int finals
Final-state bit mask.
int next[n_dfa_states][n_symbols]
Transition table, with -1 denoting no transition.
unsigned int allowed[5]
Allowed-symbol bit masks for each position.
static const int n_dfa_states
Number of DFA states.
static const int n_symbols
Number of symbols.
virtual bool solution(const Assignment &x) const
Test whether x is solution
RegRandomDifferential(unsigned int seed)
Create and register test.
Test nondeterministic generated automata against a reference runner
unsigned int allowed[5]
Allowed-symbol bit masks for each position.
virtual bool solution(const Assignment &x) const
Test whether x is solution
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegRandomNFADifferential(unsigned int seed)
Create and register test.
bool next[n_fa_states][n_symbols][n_fa_states]
Transition relation.
static const int n_fa_states
Number of automaton states.
static const int n_symbols
Number of symbols.
Test with simple regular expression from Roland Yap
virtual bool solution(const Assignment &x) const
Test whether x is solution
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegRoland(int n)
Create and register test.
Test with simple regular expression and shared variables (uses unsharing)
virtual bool solution(const Assignment &x) const
Test whether x is solution
RegSharedA(void)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Test with simple regular expression and shared variables (uses unsharing)
RegSharedB(void)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Test with simple regular expression and shared variables (uses unsharing)
virtual bool solution(const Assignment &x) const
Test whether x is solution
RegSharedC(void)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Test with simple regular expression and shared variables (uses unsharing)
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegSharedD(void)
Create and register test.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Test with simple regular expression
virtual bool solution(const Assignment &x) const
Test whether x is solution
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegSimpleA(void)
Create and register test.
Test with simple regular expression
virtual bool solution(const Assignment &x) const
Test whether x is solution
RegSimpleB(void)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Test with simple regular expression
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
RegSimpleC(void)
Create and register test.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Test compacting sparse external DFA state identifiers
virtual bool solution(const Assignment &x) const
Test whether x is solution
RegSparseStateNumbering(void)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Test merging several reached DFA final states
virtual bool solution(const Assignment &x) const
Test whether x is solution
RegTerminalMerged(void)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Test retaining separate terminal states when merging would overflow
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
virtual bool solution(const Assignment &x) const
Test whether x is solution
RegTerminalUnmerged(void)
Create and register test.
Sample both table tuples and arbitrary assignments in large domains.
virtual void next(Gecode::Support::RandomGenerator &rand)
Move to next assignment.
SparseAssignment(const Gecode::TupleSet &t0, const Gecode::IntSet &d, Gecode::Support::RandomGenerator &rand)
Disabled sparse propagators must defer failure until re-enabled.
Tells issued after posting exercise sparse advisor updates.
SparseTupleSetIncremental(const std::string &name, int k)
virtual bool solution(const Assignment &x) const
Check for solution.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
The assignment harness needs one variable even for a nullary table.
virtual bool solution(const Assignment &) const
Check for solution.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &)
Post constraint.
Sparse delta processing must depend on supports, not numeric width.
Sparse tables with the original large support counts and arities.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
virtual bool solution(const Assignment &x) const
Check for solution.
virtual Assignment * assignment(void) const
Create the assignment generator (complete by default).
SparseTupleSet(const std::string &name, int arity, int size)
AUTO finalization should work with default tuple-set posting overloads.
bool pos
Whether the table is positive or negative.
TupleSetBase(bool p, Gecode::ExtensionalPropKind epk0)
Create and register test.
virtual bool solution(const Assignment &x) const
Test whether x is solution
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Gecode::TupleSet t
Simple test tupleset.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Gecode::ExtensionalPropKind epk
Support representation.
Gecode::TupleSet t
Tupleset used for testing.
Gecode::ExtensionalPropKind epk
Support representation.
TupleSetBool(double prob, bool p, Gecode::ExtensionalPropKind epk0)
Create and register test.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
virtual bool solution(const Assignment &x) const
Test whether x is solution
bool pos
Whether the table is positive or negative.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
DFA-derived tuple sets preserve the requested support representation.
Disabled compact propagators preserve pending work when cloned.
bool pos
Whether the table is positive or negative.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
TupleSetLarge(double prob, bool p, Gecode::ExtensionalPropKind epk0)
Create and register test.
Gecode::ExtensionalPropKind epk
Support representation.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Gecode::TupleSet t
Tupleset used for testing.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Sparse/compressed tuplesets should materialize only requested support.
Sparse offset arrays need a representable terminal entry.
Failed finalization is terminal and cannot expose partial support data.
Help class to create and register tests with a fixed table size.
TupleSetTestSize(int size, bool pos, Gecode::ExtensionalPropKind epk, Gecode::Support::RandomGenerator &rand)
Perform creation and registration.
virtual bool solution(const Assignment &x) const
Test whether x is solution
bool toDFA
Whether to validate dfa2tupleset.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
TupleSetTest(const std::string &s, bool p, Gecode::IntSet d0, Gecode::TupleSet ts0, bool td, Gecode::ExtensionalPropKind epk0, TestTags tags=TestTags::sweep())
Create and register test.
Gecode::TupleSet ts
The tuple set to use.
bool pos
Whether the table is positive or negative.
Gecode::ExtensionalPropKind epk
Support representation.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Generate random selection of assignments.
Definition int.hh:110
int a
How many assignments still to be generated Generate new value according to domain.
Definition int.hh:113
int * vals
The current values for the variables.
Definition int.hh:112
RandomAssignment(int n, const Gecode::IntSet &d, int a0, Gecode::Support::RandomGenerator &rand)
Initialize for a assignments for n0 variables and values d0.
Definition int.hpp:88
virtual void next(Gecode::Support::RandomGenerator &rand)
Move to next assignment.
Definition int.cpp:63
bool testsearch
Whether to perform search test.
Definition int.hh:285
static std::string str(bool b)
Map bool to string.
Definition int.hpp:278
Gecode::IntPropLevel ipl
Propagation level.
Definition int.hh:281
int arity
Number of variables.
Definition int.hh:273
Gecode::IntSet dom
Domain of variables.
Definition int.hh:275
ConTestLevel contest
Whether to test for certain consistency.
Definition int.hh:283
Set of test tags.
Definition test.hh:105
static TestTags sweep(void)
Expensive parameter sweeps.
Definition test.hpp:59
static TestTags standard(void)
Standard suite without expensive sweeps.
Definition test.hpp:55
LinearCongruentialGenerator< 2147483647, 48271, 44488, 3399 > RandomGenerator
Default values for linear congruential generator.
Definition random.hpp:183
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
ExtensionalPropKind
Support representation selection for extensional tuple sets.
Definition int.hh:2794
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
@ IRT_EQ
Equality ( ).
Definition int.hh:1226
@ IRT_NQ
Disequality ( ).
Definition int.hh:1227
@ IRT_GQ
Greater or equal ( ).
Definition int.hh:1230
@ IRT_LQ
Less or equal ( ).
Definition int.hh:1228
@ RM_EQV
Equivalence for reification (default).
Definition int.hh:1155
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:1279
Space(void)
Default constructor.
Definition core.cpp:121
Space * clone(void) const
Clone space.
Definition core.hpp:3384
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
SpaceStatus
Space status
Definition core.hpp:1726
@ SS_FAILED
Space is failed
Definition core.hpp:1727
bool support_offsets_size(unsigned long long n_vals, unsigned int &n_offsets)
const int min
Smallest allowed integer value.
Definition int.hh:123
const int max
Largest allowed integer value.
Definition int.hh:121
Gecode toplevel namespace
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition channel.cpp:41
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:988
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1936
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
void unshare(Home home, IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Replace multiple variable occurrences in x by fresh variables.
Definition unshare.cpp:136
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Tests for extensional (relation) constraints
TupleSetSupportOffsetBoundary tuple_set_support_offset_boundary
RegNoAcceptingPath reg_sparse_no_accepting_path
SparseTupleSetWideDelta sparse_tuple_set_wide_delta
TupleSetSingleRepresentation tuple_set_single_representation
SparseTupleSet sparse_tuple_set_high_arity("HighArity", 6, 1000)
TupleSetDisabledClone tuple_set_disabled_clone
RegOpt ro0(CHAR_MAX-1)
OpenRegularEmpty open_regular_empty_accept(OpenRegularEmpty::Kind::ACCEPT)
SparseTupleSet sparse_tuple_set_ternary("Ternary", 3, 1500)
RegRandomNFADifferential reg_sparse_random_nfa_differential_2(2)
RegDuplicateFinals reg_duplicate_finals_sparse_keep(false, true)
SparseTupleSetIncremental sparse_tuple_set_incremental_bool("Bool", 2)
OpenRegularBackward open_regular_backward
RegDuplicateFinals reg_duplicate_finals_dense_minimize(true, false)
RegTerminalUnmerged reg_sparse_terminal_unmerged
RegRandomDifferential reg_sparse_random_differential_3(3)
TupleSetAutoDefaultDispatch tuple_set_auto_default_dispatch
RegNFAPrefix reg_sparse_nfa_prefix_int(false)
RegTerminalMerged reg_sparse_terminal_merged
RegRandomDifferential reg_sparse_random_differential_1(1)
SparseTupleSetNullary sparse_tuple_set_nullary(true)
RegDuplicateFinals reg_duplicate_finals_sparse_minimize(true, true)
std::string extensional_kind_name(Gecode::ExtensionalPropKind epk)
Gecode::DFA tupleset2dfa(Gecode::TupleSet ts)
% Transform a TupleSet into a DFA
RegOpt ro7(static_cast< int >(USHRT_MAX))
RegDuplicateFinals reg_duplicate_finals_dense_keep(false, false)
OpenRegularDomainWake open_regular_domain_wake
OpenRegularClosed open_regular_closed
SparseTupleSetIncremental sparse_tuple_set_incremental_delta("Delta", 0)
RegCyclicFrontier reg_sparse_cyclic_frontier
RegOpt ro2(static_cast< int >(UCHAR_MAX-1))
RegRandomNFADifferential reg_sparse_random_nfa_differential_1(1)
OpenRegularIncremental open_regular_incremental
TupleSetDFARepresentation tuple_set_dfa_representation
class Test::Int::Extensional::CreateSparse create_sparse
RegAcyclicReconvergence reg_sparse_acyclic_reconvergence
RegSparseStateNumbering reg_sparse_state_numbering
OpenRegularClone open_regular_clone
RegOpt ro6(static_cast< int >(USHRT_MAX-1))
OpenRegularMaxLength open_regular_max_length
RegRandomNFADifferential reg_sparse_random_nfa_differential_4(4)
RegNFAPrefix reg_sparse_nfa_prefix_bool(true)
RegRandomNFADifferential reg_sparse_random_nfa_differential_3(3)
OpenRegularEmpty open_regular_empty_reject(OpenRegularEmpty::Kind::REJECT)
SparseTupleSetDisabledFailure sparse_tuple_set_disabled_failure
RegRandomDifferential reg_sparse_random_differential_4(4)
RegPositionDomainPruning reg_sparse_position_domain_pruning
Gecode::TupleSet randomTupleSet(int n, int min, int max, double prob, Gecode::ExtensionalPropKind epk, Gecode::Support::RandomGenerator &rand)
RegRandomDifferential reg_sparse_random_differential_2(2)
SparseTupleSetNullary sparse_tuple_set_empty(false)
SparseTupleSet sparse_tuple_set_unary("Unary", 1, 2000)
RegBoolCyclicFrontier reg_sparse_bool_cyclic_frontier
OpenRegularEmpty open_regular_no_finals(OpenRegularEmpty::Kind::NO_FINALS)
RegOpt ro4(SHRT_MAX-1)
RegOpt ro1(CHAR_MAX)
TupleSetTerminalFinalizationFailure tuple_set_terminal_failure
OpenRegularLengthWake open_regular_length_wake
RegOpt ro3(static_cast< int >(UCHAR_MAX))
RegOpt ro5(SHRT_MAX)
SparseTupleSetIncremental sparse_tuple_set_incremental_assign("Assign", 1)
DenseCompressedTupleSetWideGap dense_compressed_tuple_set_wide_gap
Testing finite domain integers.
Definition int.cpp:41
@ CTL_NONE
No consistency-test.
Definition int.hh:154
General test support.
Definition afc.cpp:41
Region r
Definition region.cpp:65
@ check
Basic integrity tests.
Definition test.hh:99
@ sweep
Really heavy sweep tests.
Definition test.hh:101
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56