main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Jan 28 2020 00:00:00 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
* Last modified:
14
* $Date: 2016-05-23 22:18:23 +0200 (Mon, 23 May 2016) $
15
* $Revision: 15073 $
16
*
17
* This file is part of Gecode, the generic constraint
18
* development environment:
19
* http://www.gecode.org
20
*
21
* Permission is hereby granted, free of charge, to any person obtaining
22
* a copy of this software and associated documentation files (the
23
* "Software"), to deal in the Software without restriction, including
24
* without limitation the rights to use, copy, modify, merge, publish,
25
* distribute, sublicense, and/or sell copies of the Software, and to
26
* permit persons to whom the Software is furnished to do so, subject to
27
* the following conditions:
28
*
29
* The above copyright notice and this permission notice shall be
30
* included in all copies or substantial portions of the Software.
31
*
32
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39
*
40
*/
41
42
#include <
gecode/int/sequence.hh
>
43
44
#include <algorithm>
45
46
namespace
Gecode
{
47
48
using namespace
Int;
49
50
void
51
sequence
(
Home
home,
const
IntVarArgs
&
x
,
const
IntSet
&s,
52
int
q,
int
l
,
int
u
,
IntPropLevel
) {
53
Limits::check
(s.
min
(),
"Int::sequence"
);
54
Limits::check
(s.
max
(),
"Int::sequence"
);
55
56
if
(
x
.size() == 0)
57
throw
TooFewArguments
(
"Int::sequence"
);
58
59
Limits::check
(q,
"Int::sequence"
);
60
Limits::check
(
l
,
"Int::sequence"
);
61
Limits::check
(
u
,
"Int::sequence"
);
62
63
if
(
x
.
same
(home))
64
throw
ArgumentSame
(
"Int::sequence"
);
65
66
if
((q < 1) || (q >
x
.size()))
67
throw
OutOfLimits
(
"Int::sequence"
);
68
69
GECODE_POST
;
70
71
// Normalize l and u
72
l
=
std::max
(0,
l
);
u
=
std::min
(q,
u
);
73
74
// Lower bound of values taken can never exceed upper bound
75
if
(
u
<
l
) {
76
home.
fail
();
return
;
77
}
78
79
// Already subsumed as any number of values taken is okay
80
if
((0 ==
l
) && (q ==
u
))
81
return
;
82
83
// All variables must take a value in s
84
if
(
l
== q) {
85
for
(
int
i
=
x
.size();
i
--; ) {
86
IntView
xv(
x
[
i
]);
87
IntSetRanges
ris(s);
88
GECODE_ME_FAIL
(xv.
inter_r
(home,ris,
false
));
89
}
90
return
;
91
}
92
93
// No variable can take a value in s
94
if
(0 ==
u
) {
95
for
(
int
i
=
x
.size();
i
--; ) {
96
IntView
xv(
x
[
i
]);
97
IntSetRanges
ris(s);
98
GECODE_ME_FAIL
(xv.
minus_r
(home,ris,
false
));
99
}
100
return
;
101
}
102
103
ViewArray<IntView>
xv(home,
x
);
104
if
(s.
size
() == 1) {
105
GECODE_ES_FAIL
(
106
(
Sequence::Sequence<IntView,int>::post
107
(home,xv,s.
min
(),q,
l
,
u
)));
108
}
else
{
109
GECODE_ES_FAIL
(
110
(
Sequence::Sequence<IntView,IntSet>::post
111
(home,xv,s,q,
l
,
u
)));
112
}
113
}
114
115
void
116
sequence
(
Home
home,
const
BoolVarArgs
&
x
,
const
IntSet
& s,
117
int
q,
int
l
,
int
u
,
IntPropLevel
) {
118
if
((s.
min
() < 0) || (s.
max
() > 1))
119
throw
NotZeroOne
(
"Int::sequence"
);
120
121
if
(
x
.size() == 0)
122
throw
TooFewArguments
(
"Int::sequence"
);
123
124
Limits::check
(q,
"Int::sequence"
);
125
Limits::check
(
l
,
"Int::sequence"
);
126
Limits::check
(
u
,
"Int::sequence"
);
127
128
if
(
x
.
same
(home))
129
throw
ArgumentSame
(
"Int::sequence"
);
130
131
if
((q < 1) || (q >
x
.size()))
132
throw
OutOfLimits
(
"Int::sequence"
);
133
134
GECODE_POST
;
135
136
// Normalize l and u
137
l
=
std::max
(0,
l
);
u
=
std::min
(q,
u
);
138
139
// Lower bound of values taken can never exceed upper bound
140
if
(
u
<
l
) {
141
home.
fail
();
return
;
142
}
143
144
// Already subsumed as any number of values taken is okay
145
if
((0 ==
l
) && (q ==
u
))
146
return
;
147
148
// Check whether the set is {0,1}, then the number of values taken is q
149
if
((s.
min
() == 0) && (s.
max
() == 1)) {
150
if
((
l
> 0) || (
u
< q))
151
home.
fail
();
152
return
;
153
}
154
assert(s.
min
() == s.
max
());
155
156
// All variables must take a value in s
157
if
(
l
== q) {
158
if
(s.
min
() == 0) {
159
for
(
int
i
=
x
.size();
i
--; ) {
160
BoolView
xv(
x
[
i
]);
GECODE_ME_FAIL
(xv.
zero
(home));
161
}
162
}
else
{
163
assert(s.
min
() == 1);
164
for
(
int
i
=
x
.size();
i
--; ) {
165
BoolView
xv(
x
[
i
]);
GECODE_ME_FAIL
(xv.
one
(home));
166
}
167
}
168
return
;
169
}
170
171
// No variable can take a value in s
172
if
(0 ==
u
) {
173
if
(s.
min
() == 0) {
174
for
(
int
i
=
x
.size();
i
--; ) {
175
BoolView
xv(
x
[
i
]);
GECODE_ME_FAIL
(xv.
one
(home));
176
}
177
}
else
{
178
assert(s.
min
() == 1);
179
for
(
int
i
=
x
.size();
i
--; ) {
180
BoolView
xv(
x
[
i
]);
GECODE_ME_FAIL
(xv.
zero
(home));
181
}
182
}
183
return
;
184
}
185
186
ViewArray<BoolView>
xv(home,
x
);
187
188
GECODE_ES_FAIL
(
189
(
Sequence::Sequence<BoolView,int>::post
190
(home,xv,s.
min
(),q,
l
,
u
)));
191
}
192
193
}
194
195
// STATISTICS: int-post
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:784
Gecode::Int::BoolView::zero
bool zero(void) const
Test whether view is assigned to be zero.
Definition:
bool.hpp:214
Gecode::IntSet::min
int min(int i) const
Return minimum of range at position i.
Definition:
int-set-1.hpp:115
GECODE_ES_FAIL
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition:
macros.hpp:107
Gecode::IntSet::max
int max(int i) const
Return maximum of range at position i.
Definition:
int-set-1.hpp:121
Gecode::IntVarArgs
Passing integer variables.
Definition:
int.hh:639
Test::Int::Basic::i
Gecode::IntArgs i(4, 1, 2, 3, 4)
Gecode::Int::BoolView::one
bool one(void) const
Test whether view is assigned to be one.
Definition:
bool.hpp:218
Gecode::VarImpVar::same
bool same(const VarImpVar< VarImp > &y) const
Test whether variable is the same as y.
Definition:
var.hpp:133
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:50
Gecode::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition:
float.hh:850
Gecode::IntPropLevel
IntPropLevel
Propagation levels for integer propagators.
Definition:
int.hh:955
sequence.hh
u
union Gecode::@579::NNF::@61 u
Union depending on nodetype t.
Gecode::IntSetRanges
Range iterator for integer sets.
Definition:
int.hh:274
Gecode::IntSet::size
unsigned int size(void) const
Return size (cardinality) of set.
Definition:
int-set-1.hpp:161
Gecode::Int::BoolView
Boolean view for Boolean variables.
Definition:
view.hpp:1315
Gecode::Int::NotZeroOne
Exception: Not 0/1 integer
Definition:
exception.hpp:55
Gecode
Gecode toplevel namespace
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:180
Gecode::IntSet
Integer sets.
Definition:
int.hh:174
Gecode::Int::ArgumentSame
Exception: Arguments contain same variable multiply
Definition:
exception.hpp:84
Gecode::BoolVarArgs
Passing Boolean variables.
Definition:
int.hh:693
Gecode::Home
Home class for posting propagators
Definition:
core.hpp:922
l
NNF * l
Left subtree.
Definition:
bool-expr.cpp:244
Gecode::Home::fail
void fail(void)
Mark space as failed.
Definition:
core.hpp:4090
Gecode::Int::Sequence::Sequence
Sequence propagator for array of integers
Definition:
sequence.hh:105
GECODE_POST
#define GECODE_POST
Check for failure in a constraint post function.
Definition:
macros.hpp:44
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:81
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:51
Gecode::Int::OutOfLimits
Exception: Value out of limits
Definition:
exception.hpp:48
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:185
Gecode::Int::TooFewArguments
Exception: Too few arguments available in argument array
Definition:
exception.hpp:70
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:848