main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Mar 24 2020 14:04:04 for Gecode by
doxygen
1.8.17
gecode
int
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
38
#include <
gecode/int/sequence.hh
>
39
40
#include <algorithm>
41
42
namespace
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
65
GECODE_POST
;
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) {
101
GECODE_ES_FAIL
(
102
(
Sequence::Sequence<IntView,int>::post
103
(home,xv,s.
min
(),q,
l
,
u
)));
104
}
else
{
105
GECODE_ES_FAIL
(
106
(
Sequence::Sequence<IntView,IntSet>::post
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
130
GECODE_POST
;
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
184
GECODE_ES_FAIL
(
185
(
Sequence::Sequence<BoolView,int>::post
186
(home,xv,s.
min
(),q,
l
,
u
)));
187
}
188
189
}
190
191
// STATISTICS: int-post
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:767
Gecode::Int::BoolView::zero
bool zero(void) const
Test whether view is assigned to be zero.
Definition:
bool.hpp:220
Gecode::IntSet::min
int min(int i) const
Return minimum of range at position i.
Definition:
int-set-1.hpp:152
GECODE_ES_FAIL
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition:
macros.hpp:103
Gecode::IntSet::max
int max(int i) const
Return maximum of range at position i.
Definition:
int-set-1.hpp:158
Gecode::IntVarArgs
Passing integer variables.
Definition:
int.hh:656
Gecode::Int::BoolView::one
bool one(void) const
Test whether view is assigned to be one.
Definition:
bool.hpp:224
Gecode::Int::Limits::check
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::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition:
float.hh:846
Gecode::IntPropLevel
IntPropLevel
Propagation levels for integer propagators.
Definition:
int.hh:974
sequence.hh
Gecode::IntSetRanges
Range iterator for integer sets.
Definition:
int.hh:292
Gecode::IntSet::size
unsigned int size(void) const
Return size (cardinality) of set.
Definition:
int-set-1.hpp:198
Gecode::Int::BoolView
Boolean view for Boolean variables.
Definition:
view.hpp:1380
Gecode::Int::NotZeroOne
Exception: Not 0/1 integer
Definition:
exception.hpp:51
Gecode
Gecode toplevel namespace
u
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
Gecode::Int::IntView::inter_r
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition:
int.hpp:186
Gecode::IntSet
Integer sets.
Definition:
int.hh:174
Gecode::Int::ArgumentSame
Exception: Arguments contain same variable multiply
Definition:
exception.hpp:80
Gecode::BoolVarArgs
Passing Boolean variables.
Definition:
int.hh:712
Gecode::Home
Home class for posting propagators
Definition:
core.hpp:856
l
NNF * l
Left subtree.
Definition:
bool-expr.cpp:240
Gecode::Home::fail
void fail(void)
Mark space as failed.
Definition:
core.hpp:4039
Gecode::Int::Sequence::Sequence
Sequence propagator for array of integers
Definition:
sequence.hh:101
GECODE_POST
#define GECODE_POST
Check for failure in a constraint post function.
Definition:
macros.hpp:40
Gecode::Int::IntView
Integer view for integer variables.
Definition:
view.hpp:129
GECODE_ME_FAIL
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition:
macros.hpp:77
Gecode::sequence
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel)
Post propagator for .
Definition:
sequence.cpp:47
Gecode::same
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition:
array.hpp:1937
Gecode::Int::OutOfLimits
Exception: Value out of limits
Definition:
exception.hpp:44
Gecode::ViewArray< IntView >
Gecode::Int::IntView::minus_r
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition:
int.hpp:191
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::Int::TooFewArguments
Exception: Too few arguments available in argument array
Definition:
exception.hpp:66
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:844