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