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
count.cpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Christian Schulte <schulte@gecode.org>
5
*
6
* Copyright:
7
* Christian Schulte, 2002
8
*
9
* Last modified:
10
* $Date: 2016-11-08 17:23:24 +0100 (Tue, 08 Nov 2016) $ by $Author: schulte $
11
* $Revision: 15253 $
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/count.hh
>
39
#include <
gecode/int/rel.hh
>
40
41
namespace
Gecode
{
42
43
void
44
count
(
Home
home,
const
IntVarArgs
&
x
,
int
n
,
45
IntRelType
irt,
int
m,
IntPropLevel
) {
46
using namespace
Int;
47
Limits::check
(
n
,
"Int::count"
);
48
Limits::check
(m,
"Int::count"
);
49
50
GECODE_POST
;
51
52
ViewArray<IntView>
xv(home,
x
);
53
ConstIntView
y
(
n
);
54
55
switch
(irt) {
56
case
IRT_EQ
:
57
GECODE_ES_FAIL
((
Count::EqInt<IntView,ConstIntView>
58
::
post
(home,xv,
y
,m)));
59
break
;
60
case
IRT_NQ
:
61
{
62
IntVar
z
(home,0,
x
.size());
63
GECODE_ME_FAIL
(
IntView
(
z
).nq(home,m));
64
GECODE_ES_FAIL
((
Count::EqView<IntView,ConstIntView,IntView,true,false>
65
::
post
(home,xv,
y
,
z
,0)));
66
}
67
break
;
68
case
IRT_LE
:
69
m--;
// FALL THROUGH
70
case
IRT_LQ
:
71
GECODE_ES_FAIL
((
Count::LqInt<IntView,ConstIntView>
72
::
post
(home,xv,
y
,m)));
73
break
;
74
case
IRT_GR
:
75
m++;
// FALL THROUGH
76
case
IRT_GQ
:
77
GECODE_ES_FAIL
((
Count::GqInt<IntView,ConstIntView>
78
::
post
(home,xv,
y
,m)));
79
break
;
80
default
:
81
throw
UnknownRelation
(
"Int::count"
);
82
}
83
}
84
85
void
86
count
(
Home
home,
const
IntVarArgs
&
x
,
IntVar
y
,
87
IntRelType
irt,
int
m,
IntPropLevel
ipl) {
88
using namespace
Int;
89
Limits::check
(m,
"Int::count"
);
90
GECODE_POST
;
91
ViewArray<IntView>
xv(home,
x
);
92
93
switch
(irt) {
94
case
IRT_EQ
:
95
{
96
ConstIntView
z
(m);
97
if
((
vbd
(ipl) ==
IPL_DOM
) || (
vbd
(ipl) ==
IPL_DEF
))
98
GECODE_ES_FAIL
((
Count::EqView<IntView,IntView,ConstIntView,true,true>
99
::
post
(home,xv,
y
,
z
,0)));
100
else
101
GECODE_ES_FAIL
((
Count::EqView<IntView,IntView,ConstIntView,true,false>
102
::
post
(home,xv,
y
,
z
,0)));
103
}
104
break
;
105
case
IRT_NQ
:
106
{
107
IntVar
z
(home,0,
x
.size());
108
GECODE_ME_FAIL
(
IntView
(
z
).nq(home,m));
109
GECODE_ES_FAIL
((
Count::EqView<IntView,IntView,IntView,true,false>
110
::
post
(home,xv,
y
,
z
,0)));
111
}
112
break
;
113
case
IRT_LE
:
114
m--;
// FALL THROUGH
115
case
IRT_LQ
:
116
GECODE_ES_FAIL
((
Count::LqInt<IntView,IntView>
117
::
post
(home,xv,
y
,m)));
118
break
;
119
case
IRT_GR
:
120
m++;
// FALL THROUGH
121
case
IRT_GQ
:
122
{
123
ConstIntView
z
(m);
124
if
((
vbd
(ipl) ==
IPL_DOM
) || (
vbd
(ipl) ==
IPL_DEF
))
125
GECODE_ES_FAIL
((
Count::GqView<IntView,IntView,ConstIntView,true,true>
126
::
post
(home,xv,
y
,
z
,0)));
127
else
128
GECODE_ES_FAIL
((
Count::GqView<IntView,IntView,ConstIntView,true,false>
129
::
post
(home,xv,
y
,
z
,0)));
130
}
131
break
;
132
default
:
133
throw
UnknownRelation
(
"Int::count"
);
134
}
135
}
136
137
void
138
count
(
Home
home,
const
IntVarArgs
&
x
,
const
IntSet
&
y
,
139
IntRelType
irt,
int
m,
IntPropLevel
) {
140
using namespace
Int;
141
142
if
(
y
.size() == 1) {
143
count
(home,
x
,
y
.min(),irt,m);
144
return
;
145
}
146
147
Limits::check
(
y
.min(),
"Int::count"
);
148
Limits::check
(
y
.max(),
"Int::count"
);
149
Limits::check
(m,
"Int::count"
);
150
151
GECODE_POST
;
152
153
ViewArray<IntView>
xv(home,
x
);
154
switch
(irt) {
155
case
IRT_EQ
:
156
GECODE_ES_FAIL
((
Count::EqInt<IntView,IntSet>::post
(home,xv,
y
,m)));
157
break
;
158
case
IRT_NQ
:
159
{
160
IntVar
z
(home,0,
x
.size());
161
GECODE_ME_FAIL
(
IntView
(
z
).nq(home,m));
162
GECODE_ES_FAIL
((
Count::EqView<IntView,IntSet,IntView,true,false>
163
::
post
(home,xv,
y
,
z
,0)));
164
}
165
break
;
166
case
IRT_LE
:
167
m--;
// FALL THROUGH
168
case
IRT_LQ
:
169
GECODE_ES_FAIL
((
Count::LqInt<IntView,IntSet>::post
(home,xv,
y
,m)));
170
break
;
171
case
IRT_GR
:
172
m++;
// FALL THROUGH
173
case
IRT_GQ
:
174
GECODE_ES_FAIL
((
Count::GqInt<IntView,IntSet>::post
(home,xv,
y
,m)));
175
break
;
176
default
:
177
throw
UnknownRelation
(
"Int::count"
);
178
}
179
}
180
181
void
182
count
(
Home
home,
const
IntVarArgs
&
x
,
const
IntArgs
&
y
,
183
IntRelType
irt,
int
m,
IntPropLevel
) {
184
using namespace
Int;
185
if
(
x
.size() !=
y
.size())
186
throw
ArgumentSizeMismatch
(
"Int::count"
);
187
Limits::check
(m,
"Int::count"
);
188
GECODE_POST
;
189
190
ViewArray<OffsetView>
xy(home,
x
.size());
191
for
(
int
i
=
x
.size();
i
--; )
192
xy[
i
] =
OffsetView
(
x
[
i
],-
y
[
i
]);
193
194
ZeroIntView
zero;
195
switch
(irt) {
196
case
IRT_EQ
:
197
GECODE_ES_FAIL
((
Count::EqInt<OffsetView,ZeroIntView>
198
::
post
(home,xy,zero,m)));
199
break
;
200
case
IRT_NQ
:
201
{
202
IntVar
z
(home,0,
x
.size());
203
GECODE_ME_FAIL
(
IntView
(
z
).nq(home,m));
204
GECODE_ES_FAIL
((
Count::EqView<OffsetView,ZeroIntView,IntView,true,false>
205
::
post
(home,xy,zero,
z
,0)));
206
}
207
break
;
208
case
IRT_LE
:
209
m--;
// FALL THROUGH
210
case
IRT_LQ
:
211
GECODE_ES_FAIL
((
Count::LqInt<OffsetView,ZeroIntView>
212
::
post
(home,xy,zero,m)));
213
break
;
214
case
IRT_GR
:
215
m++;
// FALL THROUGH
216
case
IRT_GQ
:
217
GECODE_ES_FAIL
((
Count::GqInt<OffsetView,ZeroIntView>
218
::
post
(home,xy,zero,m)));
219
break
;
220
default
:
221
throw
UnknownRelation
(
"Int::count"
);
222
}
223
}
224
225
void
226
count
(
Home
home,
const
IntVarArgs
&
x
,
int
n
,
227
IntRelType
irt,
IntVar
z
,
IntPropLevel
) {
228
using namespace
Int;
229
Limits::check
(
n
,
"Int::count"
);
230
GECODE_POST
;
231
ViewArray<IntView>
xv(home,
x
);
232
ConstIntView
yv(
n
);
233
switch
(irt) {
234
case
IRT_EQ
:
235
GECODE_ES_FAIL
((
Count::EqView<IntView,ConstIntView,IntView,true,false>
236
::
post
(home,xv,yv,
z
,0)));
237
break
;
238
case
IRT_NQ
:
239
{
240
IntVar
nz(home,0,
x
.size());
241
GECODE_ES_FAIL
((
Rel::Nq<IntView,IntView>::post
(home,
z
,nz)));
242
GECODE_ES_FAIL
((
Count::EqView<IntView,ConstIntView,IntView,true,false>
243
::
post
(home,xv,yv,nz,0)));
244
}
245
break
;
246
case
IRT_LE
:
247
GECODE_ES_FAIL
((
Count::LqView<IntView,ConstIntView,IntView,true>
248
::
post
(home,xv,yv,
z
,-1)));
249
break
;
250
case
IRT_LQ
:
251
GECODE_ES_FAIL
((
Count::LqView<IntView,ConstIntView,IntView,true>
252
::
post
(home,xv,yv,
z
,0)));
253
break
;
254
case
IRT_GR
:
255
GECODE_ES_FAIL
((
Count::GqView<IntView,ConstIntView,IntView,true,false>
256
::
post
(home,xv,yv,
z
,1)));
257
break
;
258
case
IRT_GQ
:
259
GECODE_ES_FAIL
((
Count::GqView<IntView,ConstIntView,IntView,true,false>
260
::
post
(home,xv,yv,
z
,0)));
261
break
;
262
default
:
263
throw
UnknownRelation
(
"Int::count"
);
264
}
265
}
266
267
void
268
count
(
Home
home,
const
IntVarArgs
&
x
,
IntVar
y
,
269
IntRelType
irt,
IntVar
z
,
IntPropLevel
ipl) {
270
using namespace
Int;
271
GECODE_POST
;
272
ViewArray<IntView>
xv(home,
x
);
273
switch
(irt) {
274
case
IRT_EQ
:
275
if
((
vbd
(ipl) ==
IPL_DOM
) || (
vbd
(ipl) ==
IPL_DEF
))
276
GECODE_ES_FAIL
((
Count::EqView<IntView,IntView,IntView,true,true>
277
::
post
(home,xv,
y
,
z
,0)));
278
else
279
GECODE_ES_FAIL
((
Count::EqView<IntView,IntView,IntView,true,false>
280
::
post
(home,xv,
y
,
z
,0)));
281
break
;
282
case
IRT_NQ
:
283
{
284
IntVar
nz(home,0,
x
.size());
285
GECODE_ES_FAIL
((
Rel::Nq<IntView,IntView>::post
(home,
z
,nz)));
286
GECODE_ES_FAIL
((
Count::EqView<IntView,IntView,IntView,true,false>
287
::
post
(home,xv,
y
,nz,0)));
288
}
289
break
;
290
case
IRT_LE
:
291
GECODE_ES_FAIL
((
Count::LqView<IntView,IntView,IntView,true>
292
::
post
(home,xv,
y
,
z
,-1)));
293
break
;
294
case
IRT_LQ
:
295
GECODE_ES_FAIL
((
Count::LqView<IntView,IntView,IntView,true>
296
::
post
(home,xv,
y
,
z
,0)));
297
break
;
298
case
IRT_GR
:
299
if
((
vbd
(ipl) ==
IPL_DOM
) || (
vbd
(ipl) ==
IPL_DEF
))
300
GECODE_ES_FAIL
((
Count::GqView<IntView,IntView,IntView,true,true>
301
::
post
(home,xv,
y
,
z
,1)));
302
else
303
GECODE_ES_FAIL
((
Count::GqView<IntView,IntView,IntView,true,false>
304
::
post
(home,xv,
y
,
z
,1)));
305
break
;
306
case
IRT_GQ
:
307
if
((
vbd
(ipl) ==
IPL_DOM
) || (
vbd
(ipl) ==
IPL_DEF
))
308
GECODE_ES_FAIL
((
Count::GqView<IntView,IntView,IntView,true,true>
309
::
post
(home,xv,
y
,
z
,0)));
310
else
311
GECODE_ES_FAIL
((
Count::GqView<IntView,IntView,IntView,true,false>
312
::
post
(home,xv,
y
,
z
,0)));
313
break
;
314
default
:
315
throw
UnknownRelation
(
"Int::count"
);
316
}
317
}
318
319
void
320
count
(
Home
home,
const
IntVarArgs
&
x
,
const
IntSet
&
y
,
321
IntRelType
irt,
IntVar
z
,
IntPropLevel
) {
322
using namespace
Int;
323
324
if
(
y
.size() == 1) {
325
count
(home,
x
,
y
.min(),irt,
z
);
326
return
;
327
}
328
329
Limits::check
(
y
.min(),
"Int::count"
);
330
Limits::check
(
y
.max(),
"Int::count"
);
331
332
GECODE_POST
;
333
ViewArray<IntView>
xv(home,
x
);
334
switch
(irt) {
335
case
IRT_EQ
:
336
GECODE_ES_FAIL
((
Count::EqView<IntView,IntSet,IntView,true,false>
337
::
post
(home,xv,
y
,
z
,0)));
338
break
;
339
case
IRT_NQ
:
340
{
341
IntVar
nz(home,0,
x
.size());
342
GECODE_ES_FAIL
((
Rel::Nq<IntView,IntView>::post
(home,
z
,nz)));
343
GECODE_ES_FAIL
((
Count::EqView<IntView,IntSet,IntView,true,false>
344
::
post
(home,xv,
y
,nz,0)));
345
}
346
break
;
347
case
IRT_LE
:
348
GECODE_ES_FAIL
((
Count::LqView<IntView,IntSet,IntView,true>
349
::
post
(home,xv,
y
,
z
,-1)));
350
break
;
351
case
IRT_LQ
:
352
GECODE_ES_FAIL
((
Count::LqView<IntView,IntSet,IntView,true>
353
::
post
(home,xv,
y
,
z
,0)));
354
break
;
355
case
IRT_GR
:
356
GECODE_ES_FAIL
((
Count::GqView<IntView,IntSet,IntView,true,false>
357
::
post
(home,xv,
y
,
z
,1)));
358
break
;
359
case
IRT_GQ
:
360
GECODE_ES_FAIL
((
Count::GqView<IntView,IntSet,IntView,true,false>
361
::
post
(home,xv,
y
,
z
,0)));
362
break
;
363
default
:
364
throw
UnknownRelation
(
"Int::count"
);
365
}
366
}
367
368
void
369
count
(
Home
home,
const
IntVarArgs
&
x
,
const
IntArgs
&
y
,
370
IntRelType
irt,
IntVar
z
,
IntPropLevel
) {
371
using namespace
Int;
372
if
(
x
.size() !=
y
.size())
373
throw
ArgumentSizeMismatch
(
"Int::count"
);
374
GECODE_POST
;
375
376
ViewArray<OffsetView>
xy(home,
x
.size());
377
for
(
int
i
=
x
.size();
i
--; )
378
xy[
i
] =
OffsetView
(
x
[
i
],-
y
[
i
]);
379
380
ZeroIntView
u
;
381
switch
(irt) {
382
case
IRT_EQ
:
383
GECODE_ES_FAIL
((
Count::EqView<OffsetView,ZeroIntView,IntView,true,false>
384
::
post
(home,xy,
u
,
z
,0)));
385
break
;
386
case
IRT_NQ
:
387
{
388
IntVar
nz(home,0,
x
.size());
389
GECODE_ES_FAIL
((
Rel::Nq<IntView,IntView>::post
(home,
z
,nz)));
390
GECODE_ES_FAIL
((
Count::EqView<OffsetView,ZeroIntView,IntView,true,false>
391
::
post
(home,xy,
u
,nz,0)));
392
}
393
break
;
394
case
IRT_LE
:
395
GECODE_ES_FAIL
((
Count::LqView<OffsetView,ZeroIntView,IntView,true>
396
::
post
(home,xy,
u
,
z
,-1)));
397
break
;
398
case
IRT_LQ
:
399
GECODE_ES_FAIL
((
Count::LqView<OffsetView,ZeroIntView,IntView,true>
400
::
post
(home,xy,
u
,
z
,0)));
401
break
;
402
case
IRT_GR
:
403
GECODE_ES_FAIL
((
Count::GqView<OffsetView,ZeroIntView,IntView,true,false>
404
::
post
(home,xy,
u
,
z
,1)));
405
break
;
406
case
IRT_GQ
:
407
GECODE_ES_FAIL
((
Count::GqView<OffsetView,ZeroIntView,IntView,true,false>
408
::
post
(home,xy,
u
,
z
,0)));
409
break
;
410
default
:
411
throw
UnknownRelation
(
"Int::count"
);
412
}
413
}
414
415
}
416
417
// STATISTICS: int-post
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::IntRelType
IntRelType
Relation types for integers.
Definition:
int.hh:906
Gecode::y
Post propagator for SetVar SetOpType SetVar y
Definition:
set.hh:784
Gecode::Int::Count::LqView
Propagator for counting views (less or equal to number of equal views)
Definition:
count.hh:345
Gecode::Int::ConstIntView
Constant integer view.
Definition:
view.hpp:804
GECODE_ES_FAIL
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition:
macros.hpp:107
Gecode::IRT_GQ
@ IRT_GQ
Greater or equal ( )
Definition:
int.hh:911
Gecode::IntVarArgs
Passing integer variables.
Definition:
int.hh:639
Gecode::IRT_LE
@ IRT_LE
Less ( )
Definition:
int.hh:910
Gecode::Int::Count::LqInt
Propagator for counting views (less or equal integer to number of equal views)
Definition:
count.hh:233
count.hh
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::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::Int::Count::EqInt
Propagator for counting views (equal integer to number of equal views)
Definition:
count.hh:173
u
union Gecode::@579::NNF::@61 u
Union depending on nodetype t.
Gecode::Int::Rel::Nq
Binary disequality propagator.
Definition:
rel.hh:464
Gecode::Int::ZeroIntView
Zero integer view.
Definition:
view.hpp:959
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::Count::GqInt
Propagator for counting views (greater or equal integer to number of equal views)
Definition:
count.hh:203
Gecode::Home
Home class for posting propagators
Definition:
core.hpp:922
Gecode::IPL_DOM
@ IPL_DOM
Domain propagation Preferences: prefer speed or memory.
Definition:
int.hh:960
Gecode::post
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition:
trace-filter.cpp:142
Gecode::IntVar
Integer variables.
Definition:
int.hh:353
Gecode::Int::OffsetView
Offset integer view.
Definition:
view.hpp:422
rel.hh
Gecode::count
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition:
count.cpp:44
Gecode::IPL_DEF
@ IPL_DEF
Simple propagation levels.
Definition:
int.hh:957
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::Int::Count::EqView
Propagator for counting views (equal to number of equal views)
Definition:
count.hh:310
GECODE_ME_FAIL
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition:
macros.hpp:81
Gecode::IRT_EQ
@ IRT_EQ
Equality ( )
Definition:
int.hh:907
Gecode::Int::UnknownRelation
Exception: Unknown relation passed as argument
Definition:
exception.hpp:91
Gecode::IRT_NQ
@ IRT_NQ
Disequality ( )
Definition:
int.hh:908
Gecode::ViewArray< IntView >
Gecode::Int::Count::GqView
Propagator for counting views (greater or equal to number of equal views)
Definition:
count.hh:380
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:238
Gecode::IRT_GR
@ IRT_GR
Greater ( )
Definition:
int.hh:912
Gecode::IntArgs
Passing integer arguments.
Definition:
int.hh:610
Gecode::IRT_LQ
@ IRT_LQ
Less or equal ( )
Definition:
int.hh:909