main page
modules
namespaces
classes
files
Gecode home
Generated on Sat Nov 9 2013 19:18:27 for Gecode by
doxygen
1.8.4
gecode
int
nvalues
int-eq.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, 2011
8
*
9
* Last modified:
10
* $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11
* $Revision: 13068 $
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/rel.hh
>
39
#include <
gecode/int/distinct.hh
>
40
41
namespace
Gecode {
namespace
Int {
namespace
NValues {
42
43
template
<
class
VY>
44
forceinline
45
EqInt<VY>::EqInt
(
Home
home,
ValSet
& vs,
ViewArray<IntView>
&
x
, VY y)
46
:
IntBase
<VY>(home,vs,x,y) {
47
home.
notice
(*
this
,
AP_WEAKLY
);
48
}
49
50
template
<
class
VY>
51
inline
ExecStatus
52
EqInt<VY>::post
(
Home
home,
ViewArray<IntView>
&
x
, VY y) {
53
if
(x.
size
() == 0) {
54
GECODE_ME_CHECK
(y.eq(home,0));
55
return
ES_OK
;
56
}
57
58
x.
unique
(home);
59
60
if
(x.
size
() == 1) {
61
GECODE_ME_CHECK
(y.eq(home,1));
62
return
ES_OK
;
63
}
64
65
GECODE_ME_CHECK
(y.gq(home,1));
66
GECODE_ME_CHECK
(y.lq(home,x.
size
()));
67
68
if
(y.max() == 1) {
69
assert(y.assigned());
70
return
Rel::NaryEqDom<IntView>::post
(home,x);
71
}
72
73
if
(y.min() == x.
size
()) {
74
assert(y.assigned());
75
return
Distinct::Dom<IntView>::post
(home,x);
76
}
77
78
// Eliminate assigned views and store them into the value set
79
ValSet
vs;
80
int
n
= x.
size
();
81
for
(
int
i
=n;
i
--; )
82
if
(x[
i
].
assigned
()) {
83
vs.
add
(home, x[
i
].val());
84
x[
i
] = x[--
n
];
85
}
86
87
GECODE_ME_CHECK
(y.gq(home,vs.
size
()));
88
GECODE_ME_CHECK
(y.lq(home,n + vs.
size
()));
89
90
if
(n == 0) {
91
assert(y.val() == vs.
size
());
92
return
ES_OK
;
93
}
94
x.
size
(n);
95
(void)
new
(home)
EqInt<VY>
(home, vs,
x
, y);
96
return
ES_OK
;
97
}
98
99
template
<
class
VY>
100
forceinline
101
EqInt<VY>::EqInt
(
Space
& home,
bool
share,
EqInt<VY>
&
p
)
102
:
IntBase
<VY>(home, share, p) {}
103
104
template
<
class
VY>
105
Propagator
*
106
EqInt<VY>::copy
(
Space
& home,
bool
share) {
107
return
new
(home)
EqInt<VY>
(home, share, *
this
);
108
}
109
110
template
<
class
VY>
111
forceinline
size_t
112
EqInt<VY>::dispose
(
Space
& home) {
113
home.
ignore
(*
this
,
AP_WEAKLY
);
114
(void)
IntBase<VY>::dispose
(home);
115
return
sizeof
(*this);
116
}
117
118
template
<
class
VY>
119
ExecStatus
120
EqInt<VY>::propagate
(
Space
& home,
const
ModEventDelta
& med) {
121
// Add assigned views to value set
122
if
(
IntView::me
(med) ==
ME_INT_VAL
)
123
add(home);
124
125
GECODE_ME_CHECK
(y.gq(home, vs.size()));
126
GECODE_ME_CHECK
(y.lq(home,
x
.size() + vs.size()));
127
128
if
(
x
.size() == 0)
129
return
home.
ES_SUBSUMED
(*
this
);
130
131
// All values must be in the value set
132
if
(y.max() == vs.size())
133
return
all_in_valset(home);
134
135
// Compute positions of disjoint views and eliminate subsumed views
136
Region
r
(home);
137
int
* dis;
int
n_dis;
138
disjoint
(home,r,dis,n_dis);
139
140
// The number might have changed due to elimination of subsumed views
141
GECODE_ME_CHECK
(y.lq(home,
x
.size() + vs.size()));
142
143
if
(
x
.size() == 0) {
144
assert(y.val() == vs.size());
145
return
home.
ES_SUBSUMED
(*
this
);
146
}
147
148
GECODE_ES_CHECK
(prune_upper(home,g));
149
150
// No lower bound pruning possible
151
if
(n_dis == 0)
152
return
ES_NOFIX
;
153
154
// Only if the propagator is at fixpoint here, continue with
155
// propagating the lower bound
156
if
(
IntView::me
(
Propagator::modeventdelta
()) !=
ME_INT_NONE
)
157
return
ES_NOFIX
;
158
159
// Do lower bound-based pruning
160
GECODE_ES_CHECK
(prune_lower(home,dis,n_dis));
161
162
return
ES_NOFIX
;
163
}
164
165
}}}
166
167
// STATISTICS: int-prop