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
gcc.cpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5
* Guido Tack <tack@gecode.org>
6
*
7
* Contributing authors:
8
* Christian Schulte <schulte@gecode.org>
9
*
10
* Copyright:
11
* Patrick Pekczynski, 2004
12
* Christian Schulte, 2009
13
* Guido Tack, 2006
14
*
15
* Last modified:
16
* $Date: 2016-05-23 22:18:23 +0200 (Mon, 23 May 2016) $ by $Author: schulte $
17
* $Revision: 15073 $
18
*
19
* This file is part of Gecode, the generic constraint
20
* development environment:
21
* http://www.gecode.org
22
*
23
* Permission is hereby granted, free of charge, to any person obtaining
24
* a copy of this software and associated documentation files (the
25
* "Software"), to deal in the Software without restriction, including
26
* without limitation the rights to use, copy, modify, merge, publish,
27
* distribute, sublicense, and/or sell copies of the Software, and to
28
* permit persons to whom the Software is furnished to do so, subject to
29
* the following conditions:
30
*
31
* The above copyright notice and this permission notice shall be
32
* included in all copies or substantial portions of the Software.
33
*
34
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41
*
42
*/
43
44
#include <
gecode/int/gcc.hh
>
45
46
namespace
Gecode
{
47
48
namespace
{
49
51
template
<
class
X>
52
struct
LessP {
53
bool
operator ()(
const
std::pair<X,int>& lhs,
54
const
std::pair<X,int>& rhs) {
55
return
lhs.second < rhs.second;
56
}
57
};
58
60
IntVar unify(Home home, IntVar
x
, IntVar
y
) {
61
rel
(home,
x
,
IRT_EQ
,
y
);
62
return
x
;
63
}
65
IntSet unify(Home,
const
IntSet&
x
,
const
IntSet&
y
) {
66
IntSetRanges xr(
x
);
67
IntSetRanges yr(
y
);
68
Iter::Ranges::Inter<IntSetRanges,IntSetRanges>
i
(xr,yr);
69
IntSet
z
(
i
);
70
return
z
;
71
}
72
74
template
<
class
A>
75
void
removeDuplicates(Home home, A&
c
, IntArgs&
v
) {
76
typedef
typename
A::value_type S;
77
typedef
std::pair<S,int> P;
78
Region re(home);
79
P*
a
= re.alloc<P>(
c
.size());
80
for
(
int
i
=
c
.size();
i
--;)
81
a
[
i
] = P(
c
[
i
],
v
[
i
]);
82
LessP<S>
l
;
83
Support::quicksort
(
a
,
c
.size(),
l
);
84
A cc;
85
IntArgs vv;
86
int
cur =
a
[0].second-1;
87
for
(
int
i
=0;
i
<
c
.size();
i
++) {
88
if
(
a
[
i
].second==cur) {
89
cc[cc.size()-1] = unify(home, cc[cc.size()-1],
a
[
i
].first);
90
}
else
{
91
cc <<
a
[
i
].first;
92
vv <<
a
[
i
].second;
93
cur =
a
[
i
].second;
94
}
95
}
96
re.free<P>(
a
,
c
.size());
97
c
= cc;
98
v
= vv;
99
}
100
101
}
102
103
void
count
(
Home
home,
const
IntVarArgs
&
x
,
104
const
IntVarArgs
&
_c
,
const
IntArgs
& _v,
105
IntPropLevel
ipl) {
106
using namespace
Int;
107
IntVarArgs
c
(
_c
);
108
IntArgs
v
(_v);
109
if
(
v
.size() !=
c
.size())
110
throw
ArgumentSizeMismatch
(
"Int::count"
);
111
if
(
x
.
same
(home))
112
throw
ArgumentSame
(
"Int::count"
);
113
114
GECODE_POST
;
115
116
removeDuplicates(home,
c
,
v
);
117
118
ViewArray<IntView>
xv(home,
x
);
119
ViewArray<GCC::CardView>
cv(home,
c
.size());
120
// set the cardinality
121
for
(
int
i
=
v
.size();
i
--; )
122
cv[
i
].init(
c
[
i
],
v
[
i
]);
123
switch
(
vbd
(ipl)) {
124
case
IPL_BND
:
125
GECODE_ES_FAIL
(
126
(
GCC::Bnd<GCC::CardView>::post
(home,xv,cv)));
127
break
;
128
case
IPL_DOM
:
129
GECODE_ES_FAIL
(
130
(
GCC::Dom<GCC::CardView>::post
(home,xv,cv)));
131
break
;
132
default
:
133
GECODE_ES_FAIL
(
134
(
GCC::Val<GCC::CardView>::post
(home,xv,cv)));
135
}
136
}
137
138
// domain is 0..|cards|- 1
139
void
count
(
Home
home,
const
IntVarArgs
&
x
,
const
IntVarArgs
&
c
,
140
IntPropLevel
ipl) {
141
IntArgs
values
(
c
.size());
142
for
(
int
i
=
c
.size();
i
--; )
143
values
[
i
] =
i
;
144
count
(home,
x
,
c
,
values
, ipl);
145
}
146
147
// constant cards
148
void
count
(
Home
home,
const
IntVarArgs
&
x
,
149
const
IntSetArgs
&
_c
,
const
IntArgs
& _v,
150
IntPropLevel
ipl) {
151
using namespace
Int;
152
IntSetArgs
c
(
_c
);
153
IntArgs
v
(_v);
154
if
(
v
.size() !=
c
.size())
155
throw
ArgumentSizeMismatch
(
"Int::count"
);
156
if
(
x
.
same
(home))
157
throw
ArgumentSame
(
"Int::count"
);
158
for
(
int
i
=
c
.size();
i
--; ) {
159
Limits::check
(
v
[
i
],
"Int::count"
);
160
Limits::check
(
c
[
i
].
min
(),
"Int::count"
);
161
Limits::check
(
c
[
i
].
max
(),
"Int::count"
);
162
}
163
164
GECODE_POST
;
165
166
removeDuplicates(home,
c
,
v
);
167
168
ViewArray<IntView>
xv(home,
x
);
169
170
for
(
int
i
=
v
.size();
i
--; ) {
171
if
(
c
[
i
].ranges() > 1) {
172
// Found hole, so create temporary variables
173
ViewArray<GCC::CardView>
cv(home,
v
.size());
174
for
(
int
j =
v
.size(); j--; )
175
cv[j].init(home,
c
[j],
v
[j]);
176
switch
(
vbd
(ipl)) {
177
case
IPL_BND
:
178
GECODE_ES_FAIL
(
179
(
GCC::Bnd<GCC::CardView>::post
(home, xv, cv)));
180
break
;
181
case
IPL_DOM
:
182
GECODE_ES_FAIL
(
183
(
GCC::Dom<GCC::CardView>::post
(home, xv, cv)));
184
break
;
185
default
:
186
GECODE_ES_FAIL
(
187
(
GCC::Val<GCC::CardView>::post
(home, xv, cv)));
188
}
189
return
;
190
}
191
}
192
193
// No holes: create CardConsts
194
ViewArray<GCC::CardConst>
cv(home,
c
.size());
195
196
for
(
int
i
=
c
.size();
i
--; )
197
cv[
i
].init(home,
c
[
i
].
min
(),
c
[
i
].
max
(),
v
[
i
]);
198
199
switch
(
vbd
(ipl)) {
200
case
IPL_BND
:
201
GECODE_ES_FAIL
(
202
(
GCC::Bnd<GCC::CardConst>::post
(home, xv, cv)));
203
break
;
204
case
IPL_DOM
:
205
GECODE_ES_FAIL
(
206
(
GCC::Dom<GCC::CardConst>::post
(home, xv, cv)));
207
break
;
208
default
:
209
GECODE_ES_FAIL
(
210
(
GCC::Val<GCC::CardConst>::post
(home, xv, cv)));
211
}
212
}
213
214
// domain is 0..|cards|- 1
215
void
count
(
Home
home,
const
IntVarArgs
&
x
,
const
IntSetArgs
&
c
,
216
IntPropLevel
ipl) {
217
IntArgs
values
(
c
.size());
218
for
(
int
i
=
c
.size();
i
--; )
219
values
[
i
] =
i
;
220
count
(home,
x
,
c
,
values
, ipl);
221
}
222
223
void
count
(
Home
home,
const
IntVarArgs
&
x
,
224
const
IntSet
&
c
,
const
IntArgs
&
v
,
225
IntPropLevel
ipl) {
226
IntSetArgs
cards(
v
.size());
227
for
(
int
i
=
v
.size();
i
--; )
228
cards[
i
] =
c
;
229
count
(home,
x
, cards,
v
, ipl);
230
}
231
232
}
233
234
// STATISTICS: int-post
Gecode::values
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition:
minimodel.hh:1868
gcc.hh
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:784
Gecode::Int::ArgumentSizeMismatch
Exception: Arguments are of different size
Definition:
exception.hpp:77
Gecode::y
Post propagator for SetVar SetOpType SetVar y
Definition:
set.hh:784
GECODE_ES_FAIL
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition:
macros.hpp:107
Gecode::Int::GCC::Dom
Domain consistent global cardinality propagator.
Definition:
gcc.hh:223
Gecode::Int::GCC::Val
Value consistent global cardinality propagator.
Definition:
gcc.hh:67
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:53
Gecode::IntVarArgs
Passing integer variables.
Definition:
int.hh:639
Gecode::z
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition:
set.hh:784
Test::Int::Basic::i
Gecode::IntArgs i(4, 1, 2, 3, 4)
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::IntPropLevel
IntPropLevel
Propagation levels for integer propagators.
Definition:
int.hh:955
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition:
sort.hpp:134
Gecode
Gecode toplevel namespace
Gecode::IntSet
Integer sets.
Definition:
int.hh:174
Gecode::vbd
IntPropLevel vbd(IntPropLevel ipl)
Extract value, bounds, or domain propagation from propagation level.
Definition:
ipl.hpp:41
Gecode::Int::ArgumentSame
Exception: Arguments contain same variable multiply
Definition:
exception.hpp:84
Gecode::ArgArray< IntSet >
Gecode::Home
Home class for posting propagators
Definition:
core.hpp:922
a
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
Test::Int::GCC::c
Create c
Definition:
gcc.cpp:314
Gecode::IPL_DOM
@ IPL_DOM
Domain propagation Preferences: prefer speed or memory.
Definition:
int.hh:960
Gecode::IPL_BND
@ IPL_BND
Bounds propagation.
Definition:
int.hh:959
Test::Int::Precede::_c
Multi _c(Gecode::IntArgs(3, 1, 2, 3))
Test::Int::Distinct::v
const int v[7]
Definition:
distinct.cpp:263
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition:
rel.cpp:47
Gecode::count
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition:
count.cpp:44
l
NNF * l
Left subtree.
Definition:
bool-expr.cpp:244
GECODE_POST
#define GECODE_POST
Check for failure in a constraint post function.
Definition:
macros.hpp:44
Gecode::IRT_EQ
@ IRT_EQ
Equality ( )
Definition:
int.hh:907
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:71
Gecode::ViewArray< IntView >
Gecode::Int::GCC::Bnd
Bounds consistent global cardinality propagator.
Definition:
gcc.hh:117
Gecode::IntArgs
Passing integer arguments.
Definition:
int.hh:610