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 
40 namespace Gecode { namespace Set { namespace Precede {
41 
42   template<class View>
43   forceinline
Index(Space & home,Propagator & p,Council<Index> & c,int i0)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
Index(Space & home,Index & a)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
updateAlpha(Space & home)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
updateBeta(Space & home)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
Single(Home home,ViewArray<View> & x0,int s0,int t0,int b,int g)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
post(Home home,ViewArray<View> & x,int s,int t)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
Single(Space & home,Single & p)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*
copy(Space & home)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
dispose(Space & home)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
cost(const Space &,const ModEventDelta &) const185   Single<View>::cost(const Space&, const ModEventDelta&) const {
186     return PropCost::linear(PropCost::LO, x.size());
187   }
188 
189   template<class View>
190   void
reschedule(Space & home)191   Single<View>::reschedule(Space& home) {
192     View::schedule(home, *this, ME_SET_BB);
193   }
194 
195   template<class View>
196   ExecStatus
advise(Space & home,Advisor & a0,const Delta &)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
propagate(Space & home,const ModEventDelta &)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
258