main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Feb 14 2013 20:59:41 for Gecode by
doxygen
1.8.3.1
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: 2012-02-22 16:04:20 +1100 (Wed, 22 Feb 2012) $
15
* $Revision: 12537 $
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,
IntConLevel
) {
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
if
(home.
failed
())
70
return
;
71
72
// Normalize l and u
73
l=
std::max
(0,l); u=
std::min
(q,u);
74
75
// Lower bound of values taken can never exceed upper bound
76
if
(u < l) {
77
home.
fail
();
return
;
78
}
79
80
// Already subsumed as any number of values taken is okay
81
if
((0 == l) && (q == u))
82
return
;
83
84
// All variables must take a value in s
85
if
(l == q) {
86
for
(
int
i
=x.
size
();
i
--; ) {
87
IntView
xv(x[
i
]);
88
IntSetRanges
ris(s);
89
GECODE_ME_FAIL
(xv.
inter_r
(home,ris,
false
));
90
}
91
return
;
92
}
93
94
// No variable can take a value in s
95
if
(0 == u) {
96
for
(
int
i
=x.
size
();
i
--; ) {
97
IntView
xv(x[
i
]);
98
IntSetRanges
ris(s);
99
GECODE_ME_FAIL
(xv.
minus_r
(home,ris,
false
));
100
}
101
return
;
102
}
103
104
ViewArray<IntView>
xv(home,x);
105
if
(s.
size
() == 1) {
106
GECODE_ES_FAIL
(
107
(
Sequence::Sequence<IntView,int>::post
108
(home,xv,s.
min
(),q,l,u)));
109
}
else
{
110
GECODE_ES_FAIL
(
111
(
Sequence::Sequence<IntView,IntSet>::post
112
(home,xv,s,q,l,u)));
113
}
114
}
115
116
void
117
sequence
(
Home
home,
const
BoolVarArgs
& x,
const
IntSet
& s,
118
int
q,
int
l,
int
u,
IntConLevel
) {
119
if
((s.
min
() < 0) || (s.
max
() > 1))
120
throw
NotZeroOne
(
"Int::sequence"
);
121
122
if
(x.
size
() == 0)
123
throw
TooFewArguments
(
"Int::sequence"
);
124
125
Limits::check
(q,
"Int::sequence"
);
126
Limits::check
(l,
"Int::sequence"
);
127
Limits::check
(u,
"Int::sequence"
);
128
129
if
(x.
same
(home))
130
throw
ArgumentSame
(
"Int::sequence"
);
131
132
if
((q < 1) || (q > x.
size
()))
133
throw
OutOfLimits
(
"Int::sequence"
);
134
135
if
(home.
failed
())
136
return
;
137
138
// Normalize l and u
139
l=
std::max
(0,l); u=
std::min
(q,u);
140
141
// Lower bound of values taken can never exceed upper bound
142
if
(u < l) {
143
home.
fail
();
return
;
144
}
145
146
// Already subsumed as any number of values taken is okay
147
if
((0 == l) && (q == u))
148
return
;
149
150
// Check whether the set is {0,1}, then the number of values taken is q
151
if
((s.
min
() == 0) && (s.
max
() == 1)) {
152
if
((l > 0) || (u < q))
153
home.
failed
();
154
return
;
155
}
156
assert(s.
min
() == s.
max
());
157
158
// All variables must take a value in s
159
if
(l == q) {
160
if
(s.
min
() == 0) {
161
for
(
int
i
=x.
size
();
i
--; ) {
162
BoolView
xv(x[
i
]);
GECODE_ME_FAIL
(xv.
zero
(home));
163
}
164
}
else
{
165
assert(s.
min
() == 1);
166
for
(
int
i
=x.
size
();
i
--; ) {
167
BoolView
xv(x[
i
]);
GECODE_ME_FAIL
(xv.
one
(home));
168
}
169
}
170
return
;
171
}
172
173
// No variable can take a value in s
174
if
(0 == u) {
175
if
(s.
min
() == 0) {
176
for
(
int
i
=x.
size
();
i
--; ) {
177
BoolView
xv(x[
i
]);
GECODE_ME_FAIL
(xv.
one
(home));
178
}
179
}
else
{
180
assert(s.
min
() == 1);
181
for
(
int
i
=x.
size
();
i
--; ) {
182
BoolView
xv(x[
i
]);
GECODE_ME_FAIL
(xv.
zero
(home));
183
}
184
}
185
return
;
186
}
187
188
ViewArray<BoolView>
xv(home,x);
189
190
GECODE_ES_FAIL
(
191
(
Sequence::Sequence<BoolView,int>::post
192
(home,xv,s.
min
(),q,l,u)));
193
}
194
195
}
196
197
// STATISTICS: int-post