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  *  This file is part of Gecode, the generic constraint
10  *  development environment:
11  *     http://www.gecode.org
12  *
13  *  Permission is hereby granted, free of charge, to any person obtaining
14  *  a copy of this software and associated documentation files (the
15  *  "Software"), to deal in the Software without restriction, including
16  *  without limitation the rights to use, copy, modify, merge, publish,
17  *  distribute, sublicense, and/or sell copies of the Software, and to
18  *  permit persons to whom the Software is furnished to do so, subject to
19  *  the following conditions:
20  *
21  *  The above copyright notice and this permission notice shall be
22  *  included in all copies or substantial portions of the Software.
23  *
24  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <gecode/int/rel.hh>
35 
36 namespace Gecode { namespace Int { namespace Arithmetic {
37 
38   /*
39    * Ternary bounds consistent maximum
40    *
41    */
42 
43   template<class View>
44   forceinline ExecStatus
prop_max_bnd(Space & home,View x0,View x1,View x2)45   prop_max_bnd(Space& home, View x0, View x1, View x2) {
46     bool mod = false;
47     do {
48       mod = false;
49       {
50         ModEvent me = x2.lq(home,std::max(x0.max(),x1.max()));
51         if (me_failed(me)) return ES_FAILED;
52         mod |= me_modified(me);
53       }
54       {
55         ModEvent me = x2.gq(home,std::max(x0.min(),x1.min()));
56         if (me_failed(me)) return ES_FAILED;
57         mod |= me_modified(me);
58       }
59       {
60         ModEvent me = x0.lq(home,x2.max());
61         if (me_failed(me)) return ES_FAILED;
62         mod |= me_modified(me);
63       }
64       {
65         ModEvent me = x1.lq(home,x2.max());
66         if (me_failed(me)) return ES_FAILED;
67         mod |= me_modified(me);
68       }
69     } while (mod);
70     return ES_OK;
71   }
72 
73   template<class View>
74   forceinline
MaxBnd(Home home,View x0,View x1,View x2)75   MaxBnd<View>::MaxBnd(Home home, View x0, View x1, View x2)
76     : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
77 
78   template<class View>
79   ExecStatus
post(Home home,View x0,View x1,View x2)80   MaxBnd<View>::post(Home home, View x0, View x1, View x2) {
81     GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min())));
82     GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
83     if (x0 == x1)
84       return Rel::EqBnd<View,View>::post(home,x0,x2);
85     if (x0 == x2)
86       return Rel::Lq<View,View>::post(home,x1,x2);
87     if (x1 == x2)
88       return Rel::Lq<View,View>::post(home,x0,x2);
89     (void) new (home) MaxBnd<View>(home,x0,x1,x2);
90     return ES_OK;
91   }
92 
93   template<class View>
94   forceinline
MaxBnd(Space & home,MaxBnd<View> & p)95   MaxBnd<View>::MaxBnd(Space& home, MaxBnd<View>& p)
96     : TernaryPropagator<View,PC_INT_BND>(home,p) {}
97 
98   template<class View>
99   forceinline
MaxBnd(Space & home,Propagator & p,View x0,View x1,View x2)100   MaxBnd<View>::MaxBnd(Space& home, Propagator& p,
101                  View x0, View x1, View x2)
102     : TernaryPropagator<View,PC_INT_BND>(home,p,x0,x1,x2) {}
103 
104   template<class View>
105   Actor*
copy(Space & home)106   MaxBnd<View>::copy(Space& home) {
107     return new (home) MaxBnd<View>(home,*this);
108   }
109 
110   template<class View>
111   ExecStatus
propagate(Space & home,const ModEventDelta &)112   MaxBnd<View>::propagate(Space& home, const ModEventDelta&) {
113     GECODE_ES_CHECK(prop_max_bnd(home,x0,x1,x2));
114     if ((x0.max() <= x1.min()) || (x0.max() < x2.min()))
115       GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x1,x2)));
116     if ((x1.max() <= x0.min()) || (x1.max() < x2.min()))
117       GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x0,x2)));
118     return x0.assigned() && x1.assigned() && x2.assigned() ?
119       home.ES_SUBSUMED(*this) : ES_FIX;
120   }
121 
122   /*
123    * Nary bounds consistent maximum
124    *
125    */
126 
127   template<class View>
128   forceinline
NaryMaxBnd(Home home,ViewArray<View> & x,View y)129   NaryMaxBnd<View>::NaryMaxBnd(Home home, ViewArray<View>& x, View y)
130     : NaryOnePropagator<View,PC_INT_BND>(home,x,y) {}
131 
132   template<class View>
133   ExecStatus
post(Home home,ViewArray<View> & x,View y)134   NaryMaxBnd<View>::post(Home home, ViewArray<View>& x, View y) {
135     assert(x.size() > 0);
136     x.unique();
137     if (x.size() == 1)
138       return Rel::EqBnd<View,View>::post(home,x[0],y);
139     if (x.size() == 2)
140       return MaxBnd<View>::post(home,x[0],x[1],y);
141     int l = x[0].min();
142     int u = x[0].max();
143     for (int i=1; i<x.size(); i++) {
144       l = std::max(l,x[i].min());
145       u = std::max(u,x[i].max());
146     }
147     GECODE_ME_CHECK(y.gq(home,l));
148     GECODE_ME_CHECK(y.lq(home,u));
149     if (x.same(y)) {
150       // Check whether y occurs in x
151       for (int i=0; i<x.size(); i++)
152         GECODE_ES_CHECK((Rel::Lq<View,View>::post(home,x[i],y)));
153     } else {
154       (void) new (home) NaryMaxBnd<View>(home,x,y);
155     }
156     return ES_OK;
157   }
158 
159   template<class View>
160   forceinline
NaryMaxBnd(Space & home,NaryMaxBnd<View> & p)161   NaryMaxBnd<View>::NaryMaxBnd(Space& home, NaryMaxBnd<View>& p)
162     : NaryOnePropagator<View,PC_INT_BND>(home,p) {}
163 
164   template<class View>
165   Actor*
copy(Space & home)166   NaryMaxBnd<View>::copy(Space& home) {
167     if (x.size() == 1)
168       return new (home) Rel::EqBnd<View,View>(home,*this,x[0],y);
169     if (x.size() == 2)
170       return new (home) MaxBnd<View>(home,*this,x[0],x[1],y);
171     return new (home) NaryMaxBnd<View>(home,*this);
172   }
173 
174   /// Status of propagation for nary max
175   enum MaxPropStatus {
176     MPS_ASSIGNED  = 1<<0, ///< All views are assigned
177     MPS_REMOVED   = 1<<1, ///< A view is removed
178     MPS_NEW_BOUND = 1<<2  ///< Telling has found a new upper bound
179   };
180 
181   template<class View>
182   forceinline ExecStatus
prop_nary_max_bnd(Space & home,Propagator & p,ViewArray<View> & x,View y,PropCond pc)183   prop_nary_max_bnd(Space& home, Propagator& p,
184                     ViewArray<View>& x, View y, PropCond pc) {
185   rerun:
186     assert(x.size() > 0);
187     int maxmax = x[0].max();
188     int maxmin = x[0].min();
189     for (int i=1; i<x.size(); i++) {
190       maxmax = std::max(x[i].max(),maxmax);
191       maxmin = std::max(x[i].min(),maxmin);
192     }
193     GECODE_ME_CHECK(y.lq(home,maxmax));
194     GECODE_ME_CHECK(y.gq(home,maxmin));
195     maxmin = y.min();
196     maxmax = y.max();
197     int status = MPS_ASSIGNED;
198     for (int i=x.size(); i--; ) {
199       ModEvent me = x[i].lq(home,maxmax);
200       if (me == ME_INT_FAILED)
201         return ES_FAILED;
202       if (me_modified(me) && (x[i].max() != maxmax))
203         status |= MPS_NEW_BOUND;
204       if (x[i].max() < maxmin) {
205         x.move_lst(i,home,p,pc);
206         status |= MPS_REMOVED;
207       } else if (!x[i].assigned())
208         status &= ~MPS_ASSIGNED;
209     }
210     if (x.size() == 0)
211       return ES_FAILED;
212     if ((status & MPS_REMOVED) != 0)
213       goto rerun;
214     if (((status & MPS_ASSIGNED) != 0) && y.assigned())
215       return home.ES_SUBSUMED(p);
216     return ((status & MPS_NEW_BOUND) != 0) ? ES_NOFIX : ES_FIX;
217   }
218 
219   template<class View>
220   ExecStatus
propagate(Space & home,const ModEventDelta &)221   NaryMaxBnd<View>::propagate(Space& home, const ModEventDelta&) {
222     ExecStatus es = prop_nary_max_bnd(home,*this,x,y,PC_INT_BND);
223     GECODE_ES_CHECK(es);
224     if (x.size() == 1)
225       GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this),x[0],y)));
226     return es;
227   }
228 
229 
230   /*
231    * Ternary domain consistent maximum
232    *
233    */
234 
235   template<class View>
236   forceinline
MaxDom(Home home,View x0,View x1,View x2)237   MaxDom<View>::MaxDom(Home home, View x0, View x1, View x2)
238     : TernaryPropagator<View,PC_INT_DOM>(home,x0,x1,x2) {}
239 
240   template<class View>
241   ExecStatus
post(Home home,View x0,View x1,View x2)242   MaxDom<View>::post(Home home, View x0, View x1, View x2) {
243     GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min())));
244     GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
245     if (x0 == x1)
246       return Rel::EqDom<View,View>::post(home,x0,x2);
247     if (x0 == x2)
248       return Rel::Lq<View,View>::post(home,x1,x2);
249     if (x1 == x2)
250       return Rel::Lq<View,View>::post(home,x0,x2);
251     (void) new (home) MaxDom<View>(home,x0,x1,x2);
252     return ES_OK;
253   }
254 
255   template<class View>
256   forceinline
MaxDom(Space & home,MaxDom<View> & p)257   MaxDom<View>::MaxDom(Space& home, MaxDom<View>& p)
258     : TernaryPropagator<View,PC_INT_DOM>(home,p) {}
259 
260   template<class View>
261   forceinline
MaxDom(Space & home,Propagator & p,View x0,View x1,View x2)262   MaxDom<View>::MaxDom(Space& home, Propagator& p,
263                        View x0, View x1, View x2)
264     : TernaryPropagator<View,PC_INT_DOM>(home,p,x0,x1,x2) {}
265 
266   template<class View>
267   Actor*
copy(Space & home)268   MaxDom<View>::copy(Space& home) {
269     return new (home) MaxDom<View>(home,*this);
270   }
271 
272   template<class View>
273   PropCost
cost(const Space &,const ModEventDelta & med) const274   MaxDom<View>::cost(const Space&, const ModEventDelta& med) const {
275     return PropCost::ternary((View::me(med) == ME_INT_DOM) ?
276                              PropCost::HI : PropCost::LO);
277   }
278 
279   template<class View>
280   ExecStatus
propagate(Space & home,const ModEventDelta & med)281   MaxDom<View>::propagate(Space& home, const ModEventDelta& med) {
282     if (View::me(med) != ME_INT_DOM) {
283       GECODE_ES_CHECK(prop_max_bnd(home,x0,x1,x2));
284       if ((x0.max() <= x1.min()) || (x0.max() < x2.min()))
285         GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x1,x2)));
286       if ((x1.max() <= x0.min()) || (x1.max() < x2.min()))
287         GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x2)));
288       return x0.assigned() && x1.assigned() && x2.assigned() ?
289         home.ES_SUBSUMED(*this) :
290         home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
291     }
292     ViewRanges<View> r0(x0), r1(x1);
293     Iter::Ranges::Union<ViewRanges<View>,ViewRanges<View> > u(r0,r1);
294     GECODE_ME_CHECK(x2.inter_r(home,u,false));
295     if (rtest_nq_dom(x0,x2) == RT_TRUE) {
296       GECODE_ES_CHECK((Rel::Lq<View,View>::post(Home(home),x0,x2)));
297       GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x1,x2)));
298     }
299     if (rtest_nq_dom(x1,x2) == RT_TRUE) {
300       GECODE_ES_CHECK((Rel::Lq<View,View>::post(Home(home),x1,x2)));
301       GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x0,x2)));
302     }
303     return ES_FIX;
304   }
305 
306   /*
307    * Nary domain consistent maximum
308    *
309    */
310 
311   template<class View>
312   forceinline
NaryMaxDom(Home home,ViewArray<View> & x,View y)313   NaryMaxDom<View>::NaryMaxDom(Home home, ViewArray<View>& x, View y)
314     : NaryOnePropagator<View,PC_INT_DOM>(home,x,y) {}
315 
316   template<class View>
317   ExecStatus
post(Home home,ViewArray<View> & x,View y)318   NaryMaxDom<View>::post(Home home, ViewArray<View>& x, View y) {
319     assert(x.size() > 0);
320     x.unique();
321     if (x.size() == 1)
322       return Rel::EqDom<View,View>::post(home,x[0],y);
323     if (x.size() == 2)
324       return MaxDom<View>::post(home,x[0],x[1],y);
325     int l = x[0].min();
326     int u = x[0].max();
327     for (int i=0; i<x.size(); i++) {
328       l = std::max(l,x[i].min());
329       u = std::max(u,x[i].max());
330     }
331     GECODE_ME_CHECK(y.gq(home,l));
332     GECODE_ME_CHECK(y.lq(home,u));
333     if (x.same(y)) {
334       // Check whether y occurs in x
335       for (int i=0; i<x.size(); i++)
336         GECODE_ES_CHECK((Rel::Lq<View,View>::post(home,x[i],y)));
337     } else {
338       (void) new (home) NaryMaxDom<View>(home,x,y);
339     }
340     return ES_OK;
341   }
342 
343   template<class View>
344   forceinline
NaryMaxDom(Space & home,NaryMaxDom<View> & p)345   NaryMaxDom<View>::NaryMaxDom(Space& home, NaryMaxDom<View>& p)
346     : NaryOnePropagator<View,PC_INT_DOM>(home,p) {}
347 
348   template<class View>
349   Actor*
copy(Space & home)350   NaryMaxDom<View>::copy(Space& home) {
351     if (x.size() == 1)
352       return new (home) Rel::EqDom<View,View>(home,*this,x[0],y);
353     if (x.size() == 2)
354       return new (home) MaxDom<View>(home,*this,x[0],x[1],y);
355     return new (home) NaryMaxDom<View>(home,*this);
356   }
357 
358   template<class View>
359   PropCost
cost(const Space &,const ModEventDelta & med) const360   NaryMaxDom<View>::cost(const Space&, const ModEventDelta& med) const {
361     if (View::me(med) == ME_INT_DOM)
362       return PropCost::linear(PropCost::HI, y.size());
363     else
364       return PropCost::linear(PropCost::LO, x.size());
365   }
366 
367   template<class View>
368   ExecStatus
propagate(Space & home,const ModEventDelta & med)369   NaryMaxDom<View>::propagate(Space& home, const ModEventDelta& med) {
370     if (View::me(med) != ME_INT_DOM) {
371       ExecStatus es = prop_nary_max_bnd(home,*this,x,y,PC_INT_DOM);
372       GECODE_ES_CHECK(es);
373       return (es == ES_FIX) ?
374         home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM)) :
375         home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
376     }
377     Region r;
378     ViewRanges<View>* i_x = r.alloc<ViewRanges<View> >(x.size());
379     for (int i=0; i<x.size(); i++) {
380       ViewRanges<View> i_xi(x[i]); i_x[i]=i_xi;
381     }
382     Iter::Ranges::NaryUnion u(r, i_x, x.size());
383     GECODE_ME_CHECK(y.inter_r(home,u,false));
384     for (int i = x.size(); i--; )
385       if (rtest_nq_dom(x[i],y) == RT_TRUE) {
386         GECODE_ES_CHECK((Rel::Lq<View,View>::post(Home(home),x[i],y)));
387         x.move_lst(i,home,*this,PC_INT_DOM);
388       }
389     assert(x.size() > 0);
390     if (x.size() == 1)
391       GECODE_REWRITE(*this,(Rel::EqDom<View,View>::post(home(*this),x[0],y)));
392     return ES_FIX;
393   }
394 
395 }}}
396 
397 // STATISTICS: int-prop
398 
399