main page
modules
namespaces
classes
files
Gecode home
Generated on Mon Jul 27 2020 00:00:00 for Gecode by
doxygen
1.8.18
gecode
int
rel
nq.hpp
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, 2004
8
*
9
* This file is part of Gecode, the generic constraint
10
* development environment:
11
* http://www.gecode.org
12
*
13
* Permission is hereby granted, free of charge, to any person obtaining
14
* a copy of this software and associated documentation files (the
15
* "Software"), to deal in the Software without restriction, including
16
* without limitation the rights to use, copy, modify, merge, publish,
17
* distribute, sublicense, and/or sell copies of the Software, and to
18
* permit persons to whom the Software is furnished to do so, subject to
19
* the following conditions:
20
*
21
* The above copyright notice and this permission notice shall be
22
* included in all copies or substantial portions of the Software.
23
*
24
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31
*
32
*/
33
34
#include <algorithm>
35
36
namespace
Gecode
{
namespace
Int {
namespace
Rel {
37
38
/*
39
* Disequality
40
*
41
*/
42
template
<
class
V0,
class
V1>
43
forceinline
44
Nq<V0,V1>::Nq
(
Home
home, V0 x0, V1 x1)
45
:
MixBinaryPropagator
<V0,
PC_INT_VAL
,V1,
PC_INT_VAL
>(home,x0,x1) {}
46
47
template
<
class
V0,
class
V1>
48
ExecStatus
49
Nq<V0,V1>::post
(
Home
home, V0 x0, V1 x1){
50
if
(x0.assigned()) {
51
GECODE_ME_CHECK
(x1.nq(home,x0.val()));
52
}
else
if
(x1.assigned()) {
53
GECODE_ME_CHECK
(x0.nq(home,x1.val()));
54
}
else
if
(x0 == x1) {
55
return
ES_FAILED
;
56
}
else
{
57
(void)
new
(home)
Nq<V0,V1>
(home,x0,x1);
58
}
59
return
ES_OK
;
60
}
61
62
template
<
class
V0,
class
V1>
63
forceinline
64
Nq<V0,V1>::Nq
(
Space
& home,
Nq<V0,V1>
&
p
)
65
:
MixBinaryPropagator
<V0,
PC_INT_VAL
,V1,
PC_INT_VAL
>(home,
p
) {}
66
67
template
<
class
V0,
class
V1>
68
Actor
*
69
Nq<V0,V1>::copy
(
Space
& home) {
70
return
new
(home)
Nq<V0,V1>
(home,*
this
);
71
}
72
73
template
<
class
V0,
class
V1>
74
PropCost
75
Nq<V0,V1>::cost
(
const
Space
&,
const
ModEventDelta
&)
const
{
76
return
PropCost::unary
(
PropCost::LO
);
77
}
78
79
template
<
class
V0,
class
V1>
80
ExecStatus
81
Nq<V0,V1>::propagate
(
Space
& home,
const
ModEventDelta
&) {
82
if
(x0.assigned()) {
83
GECODE_ME_CHECK
(x1.nq(home,x0.val()));
84
}
else
{
85
GECODE_ME_CHECK
(x0.nq(home,x1.val()));
86
}
87
return
home.
ES_SUBSUMED
(*
this
);
88
}
89
90
91
/*
92
* Nary disequality propagator
93
*/
94
template
<
class
View>
95
forceinline
96
NaryNq<View>::NaryNq
(
Home
home,
ViewArray<View>
&
x
)
97
:
NaryPropagator
<View,
PC_INT_VAL
>(home,
x
) {}
98
99
template
<
class
View>
100
PropCost
101
NaryNq<View>::cost
(
const
Space
&,
const
ModEventDelta
&)
const
{
102
return
PropCost::linear
(
PropCost::LO
,
x
.size());
103
}
104
105
template
<
class
View>
106
forceinline
107
NaryNq<View>::NaryNq
(
Space
& home,
NaryNq<View>
&
p
)
108
:
NaryPropagator
<View,
PC_INT_VAL
>(home,
p
) {}
109
110
template
<
class
View>
111
Actor
*
112
NaryNq<View>::copy
(
Space
& home) {
113
return
new
(home)
NaryNq<View>
(home,*
this
);
114
}
115
116
template
<
class
View>
117
inline
ExecStatus
118
NaryNq<View>::post
(
Home
home,
ViewArray<View>
&
x
) {
119
x
.unique();
120
// Try to find an assigned view
121
int
n
=
x
.size();
122
if
(
n
<= 1)
123
return
ES_FAILED
;
124
for
(
int
i
=
n
;
i
--; )
125
if
(
x
[
i
].
assigned
()) {
126
std::swap
(
x
[0],
x
[
i
]);
127
break
;
128
}
129
if
(
x
[0].
assigned
()) {
130
int
v
=
x
[0].val();
131
// Eliminate all equal views and possibly find disequal view
132
for
(
int
i
=
n
-1;
i
>0;
i
--)
133
if
(!
x
[
i
].in(
v
)) {
134
return
ES_OK
;
135
}
else
if
(
x
[
i
].
assigned
()) {
136
assert(
x
[
i
].val() ==
v
);
137
x
[
i
]=
x
[--
n
];
138
}
139
x
.size(
n
);
140
}
141
if
(
n
== 1)
142
return
ES_FAILED
;
143
if
(
n
== 2)
144
return
Nq<View,View>::post
(home,
x
[0],
x
[1]);
145
(void)
new
(home)
NaryNq
(home,
x
);
146
return
ES_OK
;
147
}
148
149
template
<
class
View>
150
forceinline
size_t
151
NaryNq<View>::dispose
(
Space
& home) {
152
(void)
NaryPropagator<View,PC_INT_VAL>::dispose
(home);
153
return
sizeof
(*this);
154
}
155
156
template
<
class
View>
157
ExecStatus
158
NaryNq<View>::propagate
(
Space
& home,
const
ModEventDelta
&) {
159
// Make sure that x[0] is assigned
160
if
(!
x
[0].
assigned
()) {
161
// Note that there is at least one assigned view
162
for
(
int
i
=1;
true
;
i
++)
163
if
(
x
[
i
].
assigned
()) {
164
std::swap
(
x
[0],
x
[
i
]);
165
break
;
166
}
167
}
168
int
v
=
x
[0].val();
169
int
n
=
x
.size();
170
for
(
int
i
=
n
-1;
i
>0;
i
--)
171
if
(!
x
[
i
].in(
v
)) {
172
x
.size(
n
);
173
return
home.
ES_SUBSUMED
(*
this
);
174
}
else
if
(
x
[
i
].
assigned
()) {
175
assert(
x
[
i
].val() ==
v
);
176
x
[
i
] =
x
[--
n
];
177
}
178
x
.size(
n
);
179
if
(
n
== 1)
180
return
ES_FAILED
;
181
if
(
n
== 2) {
182
GECODE_ME_CHECK
(
x
[1].nq(home,
v
));
183
return
home.
ES_SUBSUMED
(*
this
);
184
}
185
return
ES_FIX
;
186
}
187
188
189
190
}}}
191
192
// STATISTICS: int-prop
Gecode::Int::Rel::Nq::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition:
nq.hpp:81
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:767
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition:
core.hpp:3563
Gecode::Int::Rel::NaryNq::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition:
nq.hpp:158
Gecode::Int::Rel::Nq::post
static ExecStatus post(Home home, V0 x0, V1 x1)
Post propagator .
Definition:
nq.hpp:49
Gecode::Int::Rel::NaryNq::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition:
nq.hpp:101
Gecode::Int::Precede::assigned
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition:
single.hpp:43
Gecode::Int::Rel::NaryNq::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition:
nq.hpp:151
Gecode::PropCost::LO
@ LO
Cheap.
Definition:
core.hpp:513
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Gecode::PropCost::linear
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition:
core.hpp:4796
Gecode::Actor
Base-class for both propagators and branchers.
Definition:
core.hpp:628
Gecode::Int::Rel::Nq
Binary disequality propagator.
Definition:
rel.hh:460
Gecode
Gecode toplevel namespace
Gecode::MixBinaryPropagator
Mixed binary propagator.
Definition:
pattern.hpp:204
Gecode::Home
Home class for posting propagators
Definition:
core.hpp:856
Gecode::Int::Rel::NaryNq
Nary disequality propagator.
Definition:
rel.hh:318
Gecode::Int::Rel::Nq::Nq
Nq(Space &home, Nq< V0, V1 > &p)
Constructor for cloning p.
Definition:
nq.hpp:64
Gecode::PropCost::unary
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition:
core.hpp:4813
Gecode::NaryPropagator
n-ary propagator
Definition:
pattern.hpp:142
Gecode::swap
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition:
irt.hpp:37
Gecode::Int::Rel::NaryNq::post
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator .
Definition:
nq.hpp:118
Gecode::Int::Rel::NaryNq::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition:
nq.hpp:112
Gecode::PropCost
Propagation cost.
Definition:
core.hpp:486
Test::Int::Distinct::v
const int v[7]
Definition:
distinct.cpp:259
Gecode::Int::PC_INT_VAL
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition:
var-type.hpp:82
Gecode::ES_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition:
core.hpp:477
forceinline
#define forceinline
Definition:
config.hpp:185
Gecode::Int::Rel::Nq::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low unary)
Definition:
nq.hpp:75
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition:
macros.hpp:52
Gecode::ViewArray
View arrays.
Definition:
array.hpp:253
Gecode::Int::Rel::Nq::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition:
nq.hpp:69
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition:
core.hpp:474
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition:
core.hpp:89
Gecode::Int::Rel::NaryNq::NaryNq
NaryNq(Home home, ViewArray< View > &x)
Constructor for posting.
Definition:
nq.hpp:96
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition:
core.hpp:476
p
int p
Number of positive literals for node type.
Definition:
bool-expr.cpp:232
Gecode::ExecStatus
ExecStatus
Definition:
core.hpp:472