Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
sequence.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * David Rijsman <David.Rijsman@quintiq.com>
5 *
6 * Contributing authors:
7 * Christian Schulte <schulte@gecode.org>
8 *
9 * Copyright:
10 * David Rijsman, 2009
11 * Christian Schulte, 2009
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
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
39
40#include <algorithm>
41
42namespace Gecode {
43
44 using namespace Int;
45
46 void
47 sequence(Home home, const IntVarArgs& x, const IntSet &s,
48 int q, int l, int u, IntPropLevel) {
49 Limits::check(s.min(),"Int::sequence");
50 Limits::check(s.max(),"Int::sequence");
51
52 if (x.size() == 0)
53 throw TooFewArguments("Int::sequence");
54
55 Limits::check(q,"Int::sequence");
56 Limits::check(l,"Int::sequence");
57 Limits::check(u,"Int::sequence");
58
59 if (same(x))
60 throw ArgumentSame("Int::sequence");
61
62 if ((q < 1) || (q > x.size()))
63 throw OutOfLimits("Int::sequence");
64
66
67 // Normalize l and u
68 l=std::max(0,l); u=std::min(q,u);
69
70 // Lower bound of values taken can never exceed upper bound
71 if (u < l) {
72 home.fail(); return;
73 }
74
75 // Already subsumed as any number of values taken is okay
76 if ((0 == l) && (q == u))
77 return;
78
79 // All variables must take a value in s
80 if (l == q) {
81 for (int i=0; i<x.size(); i++) {
82 IntView xv(x[i]);
83 IntSetRanges ris(s);
84 GECODE_ME_FAIL(xv.inter_r(home,ris,false));
85 }
86 return;
87 }
88
89 // No variable can take a value in s
90 if (0 == u) {
91 for (int i=0; i<x.size(); i++) {
92 IntView xv(x[i]);
93 IntSetRanges ris(s);
94 GECODE_ME_FAIL(xv.minus_r(home,ris,false));
95 }
96 return;
97 }
98
99 ViewArray<IntView> xv(home,x);
100 if (s.size() == 1) {
103 (home,xv,s.min(),q,l,u)));
104 } else {
107 (home,xv,s,q,l,u)));
108 }
109 }
110
111 void
112 sequence(Home home, const BoolVarArgs& x, const IntSet& s,
113 int q, int l, int u, IntPropLevel) {
114 if ((s.min() < 0) || (s.max() > 1))
115 throw NotZeroOne("Int::sequence");
116
117 if (x.size() == 0)
118 throw TooFewArguments("Int::sequence");
119
120 Limits::check(q,"Int::sequence");
121 Limits::check(l,"Int::sequence");
122 Limits::check(u,"Int::sequence");
123
124 if (same(x))
125 throw ArgumentSame("Int::sequence");
126
127 if ((q < 1) || (q > x.size()))
128 throw OutOfLimits("Int::sequence");
129
131
132 // Normalize l and u
133 l=std::max(0,l); u=std::min(q,u);
134
135 // Lower bound of values taken can never exceed upper bound
136 if (u < l) {
137 home.fail(); return;
138 }
139
140 // Already subsumed as any number of values taken is okay
141 if ((0 == l) && (q == u))
142 return;
143
144 // Check whether the set is {0,1}, then the number of values taken is q
145 if ((s.min() == 0) && (s.max() == 1)) {
146 if ((l > 0) || (u < q))
147 home.fail();
148 return;
149 }
150 assert(s.min() == s.max());
151
152 // All variables must take a value in s
153 if (l == q) {
154 if (s.min() == 0) {
155 for (int i=0; i<x.size(); i++) {
156 BoolView xv(x[i]); GECODE_ME_FAIL(xv.zero(home));
157 }
158 } else {
159 assert(s.min() == 1);
160 for (int i=0; i<x.size(); i++) {
161 BoolView xv(x[i]); GECODE_ME_FAIL(xv.one(home));
162 }
163 }
164 return;
165 }
166
167 // No variable can take a value in s
168 if (0 == u) {
169 if (s.min() == 0) {
170 for (int i=0; i<x.size(); i++) {
171 BoolView xv(x[i]); GECODE_ME_FAIL(xv.one(home));
172 }
173 } else {
174 assert(s.min() == 1);
175 for (int i=0; i<x.size(); i++) {
176 BoolView xv(x[i]); GECODE_ME_FAIL(xv.zero(home));
177 }
178 }
179 return;
180 }
181
182 ViewArray<BoolView> xv(home,x);
183
186 (home,xv,s.min(),q,l,u)));
187 }
188
189}
190
191// STATISTICS: int-post
NNF * l
Left subtree.
union Gecode::@603::NNF::@65 u
Union depending on nodetype t.
Passing Boolean variables.
Definition int.hh:712
Home class for posting propagators
Definition core.hpp:856
void fail(void)
Mark space as failed.
Definition core.hpp:4039
Range iterator for integer sets.
Definition int.hh:292
Integer sets.
Definition int.hh:174
int min(int i) const
Return minimum of range at position i.
int max(int i) const
Return maximum of range at position i.
unsigned int size(void) const
Return size (cardinality) of set.
Passing integer variables.
Definition int.hh:656
Exception: Arguments contain same variable multiply
Definition exception.hpp:80
Boolean view for Boolean variables.
Definition view.hpp:1380
bool zero(void) const
Test whether view is assigned to be zero.
Definition bool.hpp:220
bool one(void) const
Test whether view is assigned to be one.
Definition bool.hpp:224
Integer view for integer variables.
Definition view.hpp:129
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition int.hpp:186
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition int.hpp:191
Exception: Not 0/1 integer
Definition exception.hpp:51
Exception: Value out of limits
Definition exception.hpp:44
Sequence propagator for array of integers
Definition sequence.hh:101
Exception: Too few arguments available in argument array
Definition exception.hpp:66
View arrays.
Definition array.hpp:253
#define GECODE_POST
Check for failure in a constraint post function.
Definition macros.hpp:40
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition macros.hpp:103
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition macros.hpp:77
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:974
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition limits.hpp:46
Gecode toplevel namespace
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition sequence.cpp:47
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1937
Post propagator for SetVar x
Definition set.hh:767