main page
modules
namespaces
classes
files
Gecode home
Generated on Fri Aug 24 2012 04:52:16 for Gecode by
doxygen
1.8.1.1
gecode
set
dom.cpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Guido Tack <tack@gecode.org>
5
*
6
* Contributing authors:
7
* Gabor Szokoli <szokoli@gecode.org>
8
*
9
* Copyright:
10
* Guido Tack, 2004, 2005
11
*
12
* Last modified:
13
* $Date: 2011-08-25 00:34:16 +1000 (Thu, 25 Aug 2011) $ by $Author: tack $
14
* $Revision: 12346 $
15
*
16
* This file is part of Gecode, the generic constraint
17
* development environment:
18
* http://www.gecode.org
19
*
20
* Permission is hereby granted, free of charge, to any person obtaining
21
* a copy of this software and associated documentation files (the
22
* "Software"), to deal in the Software without restriction, including
23
* without limitation the rights to use, copy, modify, merge, publish,
24
* distribute, sublicense, and/or sell copies of the Software, and to
25
* permit persons to whom the Software is furnished to do so, subject to
26
* the following conditions:
27
*
28
* The above copyright notice and this permission notice shall be
29
* included in all copies or substantial portions of the Software.
30
*
31
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
32
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
33
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
34
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
35
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
36
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
37
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
38
*
39
*/
40
41
#include <
gecode/set.hh
>
42
#include <
gecode/set/rel.hh
>
43
44
namespace
Gecode {
45
46
void
47
dom
(
Home
home,
SetVar
s,
SetRelType
r
,
int
i
) {
48
Set::Limits::check
(i,
"Set::dom"
);
49
IntSet
d
(i,i);
50
dom
(home, s, r, d);
51
}
52
53
void
54
dom
(
Home
home,
SetVar
s,
SetRelType
r
,
int
i
,
int
j) {
55
Set::Limits::check
(i,
"Set::dom"
);
56
Set::Limits::check
(j,
"Set::dom"
);
57
IntSet
d
(i,j);
58
dom
(home, s, r, d);
59
}
60
61
void
62
dom
(
Home
home,
SetVar
s,
SetRelType
r
,
const
IntSet
& is) {
63
Set::Limits::check
(is,
"Set::dom"
);
64
if
(home.
failed
())
return
;
65
66
Set::SetView
_s(s);
67
68
switch
(r) {
69
case
SRT_EQ
:
70
{
71
if
(is.
ranges
() == 1) {
72
GECODE_ME_FAIL
(_s.
include
(home, is.
min
(), is.
max
()));
73
GECODE_ME_FAIL
(_s.
intersect
(home, is.
min
(), is.
max
()));
74
}
else
{
75
IntSetRanges
rd1(is);
76
GECODE_ME_FAIL
(_s.
includeI
(home, rd1));
77
IntSetRanges
rd2(is);
78
GECODE_ME_FAIL
(_s.
intersectI
(home, rd2));
79
}
80
}
81
break
;
82
case
SRT_LQ
:
83
{
84
Set::ConstSetView
cv(home, is);
85
GECODE_ES_FAIL
(
86
(
Set::Rel::Lq<Set::SetView,Set::ConstSetView,false>
87
::
post
(home,s,cv)));
88
}
89
break
;
90
case
SRT_LE
:
91
{
92
Set::ConstSetView
cv(home, is);
93
GECODE_ES_FAIL
(
94
(
Set::Rel::Lq<Set::SetView,Set::ConstSetView,true>
95
::
post
(home,s,cv)));
96
}
97
break
;
98
case
SRT_GQ
:
99
{
100
Set::ConstSetView
cv(home, is);
101
GECODE_ES_FAIL
(
102
(
Set::Rel::Lq<Set::ConstSetView,Set::SetView,false>
103
::
post
(home,cv,s)));
104
}
105
break
;
106
case
SRT_GR
:
107
{
108
Set::ConstSetView
cv(home, is);
109
GECODE_ES_FAIL
(
110
(
Set::Rel::Lq<Set::ConstSetView,Set::SetView,true>
111
::
post
(home,cv,s)));
112
}
113
break
;
114
case
SRT_DISJ
:
115
{
116
if
(is.
ranges
() == 1) {
117
GECODE_ME_FAIL
(_s.
exclude
(home, is.
min
(), is.
max
()));
118
}
else
{
119
IntSetRanges
rd
(is);
120
GECODE_ME_FAIL
(_s.
excludeI
(home, rd));
121
}
122
}
123
break
;
124
case
SRT_NQ
:
125
{
126
Set::ConstSetView
cv(home, is);
127
GECODE_ES_FAIL
(
128
(
Set::Rel::DistinctDoit<Set::SetView>::post
(home, s,
129
cv)));
130
}
131
break
;
132
case
SRT_SUB
:
133
{
134
if
(is.
ranges
() == 1) {
135
GECODE_ME_FAIL
(_s.
intersect
(home, is.
min
(), is.
max
()));
136
}
else
{
137
IntSetRanges
rd
(is);
138
GECODE_ME_FAIL
(_s.
intersectI
(home, rd));
139
}
140
}
141
break
;
142
case
SRT_SUP
:
143
{
144
if
(is.
ranges
() == 1) {
145
GECODE_ME_FAIL
(_s.
include
(home, is.
min
(), is.
max
()));
146
}
else
{
147
IntSetRanges
rd
(is);
148
GECODE_ME_FAIL
(_s.
includeI
(home, rd));
149
}
150
}
151
break
;
152
case
SRT_CMPL
:
153
{
154
if
(is.
ranges
() == 1) {
155
GECODE_ME_FAIL
(_s.
exclude
(home, is.
min
(), is.
max
()));
156
GECODE_ME_FAIL
(
157
_s.
include
(home,
158
Set::Limits::min
,
159
is.
min
()-1) );
160
GECODE_ME_FAIL
(
161
_s.
include
(home, is.
max
()+1,
162
Set::Limits::max
) );
163
}
else
{
164
IntSetRanges
rd1(is);
165
Set::RangesCompl<IntSetRanges >
rdC1(rd1);
166
GECODE_ME_FAIL
(_s.
includeI
(home, rdC1));
167
IntSetRanges
rd2(is);
168
Set::RangesCompl<IntSetRanges >
rdC2(rd2);
169
GECODE_ME_FAIL
(_s.
intersectI
(home, rdC2));
170
}
171
}
172
break
;
173
default
:
174
throw
Set::UnknownRelation
(
"Set::dom"
);
175
}
176
}
177
178
void
179
dom
(
Home
home,
SetVar
s,
SetRelType
r
,
int
i
,
BoolVar
b
) {
180
Set::Limits::check
(i,
"Set::dom"
);
181
IntSet
d
(i,i);
182
dom
(home, s, r, d, b);
183
}
184
185
void
186
dom
(
Home
home,
SetVar
s,
SetRelType
r
,
int
i
,
int
j,
BoolVar
b
) {
187
Set::Limits::check
(i,
"Set::dom"
);
188
Set::Limits::check
(j,
"Set::dom"
);
189
IntSet
d
(i,j);
190
dom
(home, s, r, d, b);
191
}
192
193
void
194
dom
(
Home
home,
SetVar
s,
SetRelType
r
,
const
IntSet
& is,
BoolVar
b
) {
195
Set::Limits::check
(is,
"Set::dom"
);
196
if
(home.
failed
())
return
;
197
switch
(r) {
198
case
SRT_EQ
:
199
{
200
Set::ConstSetView
cv(home, is);
201
GECODE_ES_FAIL
(
202
(
Set::Rel::ReEq
<
Set::SetView
,
203
Set::ConstSetView
>::
post
(home, s, cv, b)));
204
}
205
break
;
206
case
SRT_LQ
:
207
{
208
Set::ConstSetView
cv(home, is);
209
GECODE_ES_FAIL
(
210
(
Set::Rel::ReLq<Set::SetView,Set::ConstSetView,false>
211
::
post
(home,s,cv,b)));
212
}
213
break
;
214
case
SRT_LE
:
215
{
216
Set::ConstSetView
cv(home, is);
217
GECODE_ES_FAIL
(
218
(
Set::Rel::ReLq<Set::SetView,Set::ConstSetView,true>
219
::
post
(home,s,cv,b)));
220
}
221
break
;
222
case
SRT_GQ
:
223
{
224
Set::ConstSetView
cv(home, is);
225
GECODE_ES_FAIL
(
226
(
Set::Rel::ReLq<Set::ConstSetView,Set::SetView,false>
227
::
post
(home,cv,s,b)));
228
}
229
break
;
230
case
SRT_GR
:
231
{
232
Set::ConstSetView
cv(home, is);
233
GECODE_ES_FAIL
(
234
(
Set::Rel::ReLq<Set::ConstSetView,Set::SetView,true>
235
::
post
(home,cv,s,b)));
236
}
237
break
;
238
case
SRT_NQ
:
239
{
240
BoolVar
notb(home,0,1);
241
rel
(home, b,
IRT_NQ
, notb);
242
Set::ConstSetView
cv(home, is);
243
GECODE_ES_FAIL
(
244
(
Set::Rel::ReEq
<
Set::SetView
,
245
Set::ConstSetView
>::
post
(home, s, cv, notb)));
246
}
247
break
;
248
case
SRT_SUB
:
249
{
250
Set::ConstSetView
cv(home, is);
251
GECODE_ES_FAIL
(
252
(
Set::Rel::ReSubset<Set::SetView,Set::ConstSetView>
253
::
post
(home, s, cv, b)));
254
}
255
break
;
256
case
SRT_SUP
:
257
{
258
Set::ConstSetView
cv(home, is);
259
GECODE_ES_FAIL
(
260
(
Set::Rel::ReSubset<Set::ConstSetView,Set::SetView>
261
::
post
(home, cv, s, b)));
262
}
263
break
;
264
case
SRT_DISJ
:
265
{
266
// x||y <=> b is equivalent to
267
// ( y <= complement(x) and x<=complement(y) ) <=> b
268
269
// compute complement of is
270
IntSetRanges
dr1
(is);
271
Set::RangesCompl<IntSetRanges >
dc1(dr1);
272
IntSet
dcompl(dc1);
273
Set::ConstSetView
cvcompl(home, dcompl);
274
GECODE_ES_FAIL
(
275
(
Set::Rel::ReSubset<Set::SetView,Set::ConstSetView>
276
::
post
(home, s, cvcompl, b)));
277
}
278
break
;
279
case
SRT_CMPL
:
280
{
281
Set::SetView
sv(s);
282
283
IntSetRanges
dr1
(is);
284
Set::RangesCompl<IntSetRanges>
dc1(dr1);
285
IntSet
dcompl(dc1);
286
Set::ConstSetView
cvcompl(home, dcompl);
287
288
GECODE_ES_FAIL
(
289
(
Set::Rel::ReEq<Set::SetView,Set::ConstSetView>
290
::
post
(home, sv, cvcompl, b)));
291
}
292
break
;
293
default
:
294
throw
Set::UnknownRelation
(
"Set::dom"
);
295
}
296
}
297
298
}
299
300
// STATISTICS: set-post