this repo has no description
dekker.one
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>
43 forceinline
44 Single<View>::Index::Index(Space& home, Propagator& p,
45 Council<Index>& c, int i0)
46 : Advisor(home,p,c), i(i0) {}
47
48 template<class View>
49 forceinline
50 Single<View>::Index::Index(Space& home, Index& a)
51 : Advisor(home,a), i(a.i) {}
52
53
54 template<class View>
55 forceinline ExecStatus
56 Single<View>::updateAlpha(Space& home) {
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>
72 forceinline ExecStatus
73 Single<View>::updateBeta(Space& home) {
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>
87 forceinline
88 Single<View>::Single(Home home, ViewArray<View>& x0,
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
100 Single<View>::post(Home home, ViewArray<View>& x, int s, int t) {
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>
141 forceinline
142 Single<View>::Single(Space& home, Single& p)
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>
149 Propagator*
150 Single<View>::copy(Space& home) {
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
174 Single<View>::dispose(Space& home) {
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);
179 (void) NaryPropagator<View,PC_SET_NONE>::dispose(home);
180 return sizeof(*this);
181 }
182
183 template<class View>
184 PropCost
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
191 Single<View>::reschedule(Space& home) {
192 View::schedule(home, *this, ME_SET_BB);
193 }
194
195 template<class View>
196 ExecStatus
197 Single<View>::advise(Space& home, Advisor& a0, const Delta&) {
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>
221 ExecStatus
222 Single<View>::propagate(Space& home, const ModEventDelta&) {
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 }
244 GECODE_ES_CHECK(updateAlpha(home));
245 beta = alpha;
246 if (alpha < n)
247 GECODE_ES_CHECK(updateBeta(home));
248 } else if ((beta < n) && (x[beta].notContains(s) || x[beta].contains(t))) {
249 GECODE_ES_CHECK(updateBeta(home));
250 }
251
252 return (c.empty()) ? home.ES_SUBSUMED(*this) : ES_FIX;
253 }
254
255}}}
256
257// STATISTICS: set-prop