main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Mar 7 2013 10:21:33 for Gecode by
doxygen
1.8.3.1
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
* Last modified:
10
* $Date: 2011-07-07 05:56:28 +1000 (Thu, 07 Jul 2011) $ by $Author: schulte $
11
* $Revision: 12151 $
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 <algorithm>
39
40
namespace
Gecode {
namespace
Int {
namespace
Rel {
41
42
/*
43
* Disequality
44
*
45
*/
46
template
<
class
View>
47
forceinline
48
Nq<View>::Nq
(
Home
home, View x0, View x1)
49
:
BinaryPropagator
<View,
PC_INT_VAL
>(home,x0,x1) {}
50
51
template
<
class
View>
52
ExecStatus
53
Nq<View>::post
(
Home
home, View x0, View x1){
54
if
(x0.assigned()) {
55
GECODE_ME_CHECK
(x1.nq(home,x0.val()));
56
}
else
if
(x1.assigned()) {
57
GECODE_ME_CHECK
(x0.nq(home,x1.val()));
58
}
else
if
(
same
(x0,x1)) {
59
return
ES_FAILED
;
60
}
else
{
61
(void)
new
(home)
Nq<View>
(home,x0,x1);
62
}
63
return
ES_OK
;
64
}
65
66
template
<
class
View>
67
forceinline
68
Nq<View>::Nq
(
Space
& home,
bool
share,
Nq<View>
& p)
69
:
BinaryPropagator
<View,
PC_INT_VAL
>(home,share,p) {}
70
71
template
<
class
View>
72
Actor
*
73
Nq<View>::copy
(
Space
& home,
bool
share) {
74
return
new
(home)
Nq<View>
(home,share,*
this
);
75
}
76
77
template
<
class
View>
78
PropCost
79
Nq<View>::cost
(
const
Space
&,
const
ModEventDelta
&)
const
{
80
return
PropCost::unary
(
PropCost::LO
);
81
}
82
83
template
<
class
View>
84
ExecStatus
85
Nq<View>::propagate
(
Space
& home,
const
ModEventDelta
&) {
86
if
(x0.assigned()) {
87
GECODE_ME_CHECK
(x1.nq(home,x0.val()));
88
}
else
{
89
GECODE_ME_CHECK
(x0.nq(home,x1.val()));
90
}
91
return
home.
ES_SUBSUMED
(*
this
);
92
}
93
94
95
/*
96
* Nary disequality propagator
97
*/
98
template
<
class
View>
99
forceinline
100
NaryNq<View>::NaryNq
(
Home
home,
ViewArray<View>
& x)
101
:
NaryPropagator
<View,
PC_INT_VAL
>(home,x) {}
102
103
template
<
class
View>
104
PropCost
105
NaryNq<View>::cost
(
const
Space
&,
const
ModEventDelta
&)
const
{
106
return
PropCost::linear
(
PropCost::LO
,x.size());
107
}
108
109
template
<
class
View>
110
forceinline
111
NaryNq<View>::NaryNq
(
Space
& home,
bool
share,
NaryNq<View>
& p)
112
:
NaryPropagator
<View,
PC_INT_VAL
>(home,share,p) {}
113
114
template
<
class
View>
115
Actor
*
116
NaryNq<View>::copy
(
Space
& home,
bool
share) {
117
return
new
(home)
NaryNq<View>
(home,share,*
this
);
118
}
119
120
template
<
class
View>
121
inline
ExecStatus
122
NaryNq<View>::post
(
Home
home,
ViewArray<View>
& x) {
123
x.
unique
(home);
124
// Try to find an assigned view
125
int
n = x.
size
();
126
if
(n <= 1)
127
return
ES_FAILED
;
128
for
(
int
i
=n;
i
--; )
129
if
(x[
i
].
assigned
()) {
130
std::swap(x[0],x[
i
]);
131
break
;
132
}
133
if
(x[0].
assigned
()) {
134
int
v
= x[0].val();
135
// Eliminate all equal views and possibly find disequal view
136
for
(
int
i
=n-1;
i
>0;
i
--)
137
if
(!x[
i
].in(v)) {
138
return
ES_OK
;
139
}
else
if
(x[
i
].
assigned
()) {
140
assert(x[
i
].val() == v);
141
x[
i
]=x[--n];
142
}
143
x.
size
(n);
144
}
145
if
(n == 1)
146
return
ES_FAILED
;
147
if
(n == 2)
148
return
Nq<View>::post
(home,x[0],x[1]);
149
(void)
new
(home)
NaryNq
(home,x);
150
return
ES_OK
;
151
}
152
153
template
<
class
View>
154
forceinline
size_t
155
NaryNq<View>::dispose
(
Space
& home) {
156
(void)
NaryPropagator<View,PC_INT_VAL>::dispose
(home);
157
return
sizeof
(*this);
158
}
159
160
template
<
class
View>
161
ExecStatus
162
NaryNq<View>::propagate
(
Space
& home,
const
ModEventDelta
&) {
163
// Make sure that x[0] is assigned
164
if
(!x[0].
assigned
()) {
165
// Note that there is at least one assigned view
166
for
(
int
i
=1;
true
;
i
++)
167
if
(x[
i
].
assigned
()) {
168
std::swap(x[0],x[
i
]);
169
break
;
170
}
171
}
172
int
v
= x[0].val();
173
int
n = x.size();
174
for
(
int
i
=n-1;
i
>0;
i
--)
175
if
(!x[
i
].in(v)) {
176
x.size(n);
177
return
home.
ES_SUBSUMED
(*
this
);
178
}
else
if
(x[
i
].
assigned
()) {
179
assert(x[
i
].val() == v);
180
x[
i
] = x[--n];
181
}
182
x.size(n);
183
if
(n == 1)
184
return
ES_FAILED
;
185
if
(n == 2) {
186
GECODE_ME_CHECK
(x[1].nq(home,v));
187
return
home.
ES_SUBSUMED
(*
this
);
188
}
189
return
ES_FIX
;
190
}
191
192
193
194
}}}
195
196
// STATISTICS: int-prop