Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
single.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christopher Mears <Chris.Mears@monash.edu>
5 *
6 * Contributing authors:
7 * Christian Schulte <schulte@gecode.org>
8 * Guido Tack <tack@gecode.org>
9 *
10 * Copyright:
11 * Christopher Mears, 2011
12 * Christian Schulte, 2011
13 * Guido Tack, 2011
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.org
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40namespace Gecode { namespace Set { namespace Precede {
41
42 template<class View>
45 Council<Index>& c, int i0)
46 : Advisor(home,p,c), i(i0) {}
47
48 template<class View>
51 : Advisor(home,a), i(a.i) {}
52
53
54 template<class View>
57 int n = x.size();
58 while (alpha < n) {
59 if (x[alpha].notContains(s)) {
60 GECODE_ME_CHECK(x[alpha].exclude(home, t));
61 } else if (x[alpha].contains(t)) {
62 GECODE_ME_CHECK(x[alpha].include(home, s));
63 } else {
64 break;
65 }
66 alpha++;
67 }
68 return ES_OK;
69 }
70
71 template<class View>
74 int n = x.size();
75 do {
76 beta++;
77 } while ((beta < n) &&
78 (x[beta].notContains(s) || x[beta].contains(t)));
79 if (beta > gamma) {
80 GECODE_ME_CHECK(x[alpha].exclude(home, t));
81 GECODE_ME_CHECK(x[alpha].include(home, s));
82 }
83 return ES_OK;
84 }
85
86 template<class View>
89 int s0, int t0, int b, int g)
90 : NaryPropagator<View, PC_SET_NONE>(home,x0),
91 c(home), s(s0), t(t0), alpha(0), beta(b), gamma(g) {
92 for (int i=x.size(); i--; )
93 if (!x[i].assigned())
94 x[i].subscribe(home,*new (home) Index(home,*this,c,i));
95 View::schedule(home, *this, ME_SET_BB);
96 }
97
98 template<class View>
99 inline ExecStatus
101 {
102 int alpha = 0;
103 while (alpha < x.size()) {
104 if (x[alpha].notContains(s)) {
105 GECODE_ME_CHECK(x[alpha].exclude(home, t));
106 } else if (x[alpha].contains(t)) {
107 GECODE_ME_CHECK(x[alpha].include(home, s));
108 } else {
109 break;
110 }
111 alpha++;
112 }
113 x.drop_fst(alpha);
114 if (x.size() == 0)
115 return ES_OK;
116 }
117 // alpha has been normalized to 0
118 int beta = 0, gamma = 0;
119 do {
120 gamma++;
121 } while ((gamma < x.size()) &&
122 (!x[gamma].notContains(s) || !x[gamma].contains(t)));
123 do {
124 beta++;
125 } while ((beta < x.size()) &&
126 (x[beta].notContains(s) || x[beta].contains(t)));
127 if (beta > gamma) {
128 GECODE_ME_CHECK(x[0].exclude(home, t));
129 GECODE_ME_CHECK(x[0].include(home, s));
130 return ES_OK;
131 }
132 if (gamma < x.size())
133 x.drop_lst(gamma);
134 (void) new (home) Single<View>(home, x, s, t, beta, gamma);
135 return ES_OK;
136 }
137
138
139
140 template<class View>
143 : NaryPropagator<View,PC_SET_NONE>(home, p),
144 s(p.s), t(p.t),
145 alpha(p.alpha), beta(p.beta), gamma(p.gamma) {
146 c.update(home, p.c);
147 }
148 template<class View>
151 // Try to eliminate assigned views at the beginning
152 if (alpha > 0) {
153 int i = 0;
154 while ((i < alpha) && x[i].assigned())
155 i++;
156 x.drop_fst(i);
157 for (Advisors<Index> as(c); as(); ++as)
158 as.advisor().i -= i;
159 alpha -= i; beta -= i; gamma -= i;
160 }
161 // Try to eliminate assigned views at the end
162 if (gamma < x.size()) {
163 int i = x.size()-1;
164 while ((i > gamma) && x[i].assigned())
165 i--;
166 x.drop_lst(i);
167 }
168 return new (home) Single<View>(home, *this);
169 }
170
171
172 template<class View>
173 inline size_t
175 // Cancel remaining advisors
176 for (Advisors<Index> as(c); as(); ++as)
177 x[as.advisor().i].cancel(home,as.advisor());
178 c.dispose(home);
180 return sizeof(*this);
181 }
182
183 template<class View>
185 Single<View>::cost(const Space&, const ModEventDelta&) const {
186 return PropCost::linear(PropCost::LO, x.size());
187 }
188
189 template<class View>
190 void
192 View::schedule(home, *this, ME_SET_BB);
193 }
194
195 template<class View>
198 Index& a(static_cast<Index&>(a0));
199 int i = a.i;
200 // Check for gamma
201 if ((beta <= gamma) && (i < gamma) &&
202 x[i].notContains(s) && x[i].contains(t))
203 gamma = i;
204 if (x[i].assigned()) {
205 a.dispose(home,c);
206 if (c.empty())
207 return ES_NOFIX;
208 } else if ((i < alpha) || (i > gamma)) {
209 x[i].cancel(home,a);
210 a.dispose(home,c);
211 return (c.empty()) ? ES_NOFIX : ES_FIX;
212 }
213 if (beta > gamma)
214 return ES_NOFIX;
215 if ((alpha == i) || (beta == i))
216 return ES_NOFIX;
217 return ES_FIX;
218 }
219
220 template<class View>
223 int n = x.size();
224 if (beta > gamma) {
225 GECODE_ME_CHECK(x[alpha].exclude(home, t));
226 GECODE_ME_CHECK(x[alpha].include(home, s));
227 return home.ES_SUBSUMED(*this);
228 }
229 if (alpha < n && (x[alpha].notContains(s) || x[alpha].contains(t))) {
230 if (x[alpha].notContains(s)) {
231 GECODE_ME_CHECK(x[alpha].exclude(home, t));
232 } else {
233 GECODE_ME_CHECK(x[alpha].include(home, s));
234 }
235 alpha++;
236 while (alpha < beta) {
237 if (x[alpha].notContains(s)) {
238 GECODE_ME_CHECK(x[alpha].exclude(home, t));
239 } else {
240 GECODE_ME_CHECK(x[alpha].include(home, s));
241 }
242 alpha++;
243 }
245 beta = alpha;
246 if (alpha < n)
248 } else if ((beta < n) && (x[beta].notContains(s) || x[beta].contains(t))) {
250 }
251
252 return (c.empty()) ? home.ES_SUBSUMED(*this) : ES_FIX;
253 }
254
255}}}
256
257// STATISTICS: set-prop
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition core.hpp:3838
friend class Council
Definition core.hpp:1296
Class to iterate over advisors of a council.
Definition core.hpp:1268
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Home class for posting propagators
Definition core.hpp:856
Index(Space &home, Propagator &p, Council< Index > &c, int i)
Create index advisor.
Definition single.hpp:49
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition single.hpp:183
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition single.hpp:211
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition single.hpp:136
virtual void reschedule(Space &home)
Schedule function.
Definition single.hpp:177
Single(Home home, ViewArray< View > &x, int s, int t, int beta, int gamma)
Constructor for posting.
Definition single.hpp:84
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition single.hpp:160
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition single.hpp:171
static ExecStatus post(Home home, ViewArray< View > &x, int s, int t)
Post propagator that s precedes t in x.
Definition single.hpp:96
n-ary propagator
Definition pattern.hpp:142
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition pattern.hpp:513
NaryPropagator(Space &home, NaryPropagator &p)
Propagation cost.
Definition core.hpp:486
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4803
Base-class for propagators.
Definition core.hpp:1066
friend class Space
Definition core.hpp:1068
friend class Advisor
Definition core.hpp:1070
Advisors for views (by position in array)
Definition precede.hh:67
Index(Space &home, Propagator &p, Council< Index > &c, int i)
Create index advisor.
Definition single.hpp:44
int i
The position of the view in the view array.
Definition precede.hh:70
Single value precedence propagator.
Definition precede.hh:63
int alpha
Pointers updated during propagation.
Definition precede.hh:81
ExecStatus updateBeta(Space &home)
Update the beta pointer.
Definition single.hpp:73
Council< Index > c
The advisor council.
Definition precede.hh:77
int s
The value s must precede t.
Definition precede.hh:79
Single(Home home, ViewArray< View > &x, int s, int t, int beta, int gamma)
Constructor for posting.
Definition single.hpp:88
ExecStatus updateAlpha(Space &home)
Update the alpha pointer.
Definition single.hpp:56
Computation spaces.
Definition core.hpp:1744
View arrays.
Definition array.hpp:253
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3570
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition single.hpp:43
Value precedence propagators.
Finite integer sets.
Definition var-imp.hpp:137
const Gecode::ModEvent ME_SET_BB
Domain operation has changed both greatest lower and least upper bound.
Definition var-type.hpp:172
const Gecode::PropCond PC_SET_NONE
Propagation condition to be ignored (convenience)
Definition var-type.hpp:199
Gecode toplevel namespace
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
#define forceinline
Definition config.hpp:194