1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  *  Main authors:
4  *     Christian Schulte <schulte@gecode.org>
5  *
6  *  Contributing authors:
7  *     Guido Tack <tack@gecode.org>
8  *
9  *  Copyright:
10  *     Christian Schulte, 2004
11  *     Guido Tack, 2004
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 <algorithm>
39 
40 namespace Gecode { namespace Int { namespace Element {
41 
42   /**
43    * \brief Class for bounds-equality test
44    *
45    */
46   template<class VA, class VC>
47   class RelTestBnd {
48   public:
49     RelTest operator ()(VA,VC);
50   };
51   /**
52    * \brief Class for bounds-equality test (specialized)
53    *
54    */
55   template<class VA>
56   class RelTestBnd<VA,ConstIntView> {
57   public:
58     RelTest operator ()(VA,ConstIntView);
59   };
60 
61   /**
62    * \brief Class for domain-equality test
63    *
64    */
65   template<class VA, class VC>
66   class RelTestDom {
67   public:
68     RelTest operator ()(VA,VC);
69   };
70   /**
71    * \brief Class for domain-equality test (specialized)
72    *
73    */
74   template<class VA>
75   class RelTestDom<VA,ConstIntView> {
76   public:
77     RelTest operator ()(VA,ConstIntView);
78   };
79 
80 
81   template<class VA, class VC>
82   forceinline RelTest
operator ()(VA x,VC y)83   RelTestBnd<VA,VC>::operator ()(VA x, VC y) {
84     return rtest_eq_bnd(x,y);
85   }
86   template<class VA>
87   forceinline RelTest
operator ()(VA x,ConstIntView y)88   RelTestBnd<VA,ConstIntView>::operator ()(VA x, ConstIntView y) {
89     return rtest_eq_bnd(x,y.val());
90   }
91 
92   template<class VA, class VC>
93   forceinline RelTest
operator ()(VA x,VC y)94   RelTestDom<VA,VC>::operator ()(VA x, VC y) {
95     return rtest_eq_dom(x,y);
96   }
97   template<class VA>
98   forceinline RelTest
operator ()(VA x,ConstIntView y)99   RelTestDom<VA,ConstIntView>::operator ()(VA x, ConstIntView y) {
100     return rtest_eq_dom(x,y.val());
101   }
102 
103 
104 
105 
106   /*
107    * Base class
108    *
109    */
110 
111   template<class VA, class VB, class VC, PropCond pc_ac>
View(Home home,IdxViewArray<VA> & iv0,VB y0,VC y1)112   View<VA,VB,VC,pc_ac>::View(Home home, IdxViewArray<VA>& iv0,
113                              VB y0, VC y1)
114     : Propagator(home), iv(iv0), x0(y0), x1(y1) {
115     x0.subscribe(home,*this,PC_INT_DOM);
116     x1.subscribe(home,*this,pc_ac);
117     iv.subscribe(home,*this,pc_ac);
118   }
119 
120   template<class VA, class VB, class VC, PropCond pc_ac>
121   forceinline
View(Space & home,View & p)122   View<VA,VB,VC,pc_ac>::View(Space& home, View& p)
123     : Propagator(home,p) {
124     x0.update(home,p.x0);
125     x1.update(home,p.x1);
126     iv.update(home,p.iv);
127   }
128 
129   template<class VA, class VB, class VC, PropCond pc_ac>
130   PropCost
cost(const Space &,const ModEventDelta &) const131   View<VA,VB,VC,pc_ac>::cost(const Space&, const ModEventDelta&) const {
132     // This is required for subscribing to variables in the
133     // above constructor, but this is then the only time this
134     // virtual function is ever used!
135     return PropCost::linear(PropCost::LO,iv.size()+2);
136   }
137 
138   template<class VA, class VB, class VC, PropCond pc_ac>
139   void
reschedule(Space & home)140   View<VA,VB,VC,pc_ac>::reschedule(Space& home) {
141     x0.reschedule(home,*this,PC_INT_DOM);
142     x1.reschedule(home,*this,pc_ac);
143     iv.reschedule(home,*this,pc_ac);
144   }
145 
146   template<class VA, class VB, class VC, PropCond pc_ac>
147   forceinline size_t
dispose(Space & home)148   View<VA,VB,VC,pc_ac>::dispose(Space& home) {
149     x0.cancel(home,*this,PC_INT_DOM);
150     x1.cancel(home,*this,pc_ac);
151     iv.cancel(home,*this,pc_ac);
152     (void) Propagator::dispose(home);
153     return sizeof(*this);
154   }
155 
156 
157 
158 
159   /**
160    * \brief Value iterator for indices in index-view map
161    *
162    */
163   template<class View>
164   class IterIdxView {
165   private:
166     const IdxView<View> *cur, *end;
167   public:
168     IterIdxView(void);
169     IterIdxView(const IdxView<View>*, const IdxView<View>*);
170     void init(const IdxView<View>*, const IdxView<View>*);
171     bool operator ()(void) const;
172     void operator ++(void);
173     int  val(void) const;
174   };
175 
176   template<class View>
177   forceinline
IterIdxView(void)178   IterIdxView<View>::IterIdxView(void) {}
179   template<class View>
180   forceinline
IterIdxView(const IdxView<View> * b,const IdxView<View> * e)181   IterIdxView<View>::IterIdxView(const IdxView<View>* b,
182                                  const IdxView<View>* e)
183     : cur(b), end(e) {}
184   template<class View>
185   forceinline void
init(const IdxView<View> * b,const IdxView<View> * e)186   IterIdxView<View>::init(const IdxView<View>* b,
187                           const IdxView<View>* e) {
188     cur=b; end=e;
189   }
190   template<class View>
191   forceinline bool
operator ()(void) const192   IterIdxView<View>::operator ()(void) const {
193     return cur < end;
194   }
195   template<class View>
196   forceinline void
operator ++(void)197   IterIdxView<View>::operator ++(void) {
198     cur++;
199   }
200   template<class View>
201   forceinline int
val(void) const202   IterIdxView<View>::val(void) const {
203     return cur->idx;
204   }
205 
206 
207 
208 
209   /*
210    * Generic scanning: does all but computing new domain for result
211    * (which is specific to bounds/domain version)
212    *
213    */
214 
215   template<class VA, class VB, class VC, PropCond pc_ac, class RelTest>
216   ExecStatus
scan(Space & home,IdxViewArray<VA> & iv,VB x0,VC x1,Propagator & p,RelTest rt)217   scan(Space& home, IdxViewArray<VA>& iv,
218        VB x0, VC x1, Propagator& p, RelTest rt) {
219     assert(iv.size() > 1);
220     /*
221      * Prunes pairs of index, variable
222      *  - checks for idx value removed
223      *  - checks for disequal variables
224      *
225      */
226     ViewValues<VB> vx0(x0);
227     int i = 0;
228     int j = 0;
229     while (vx0() && (i < iv.size())) {
230       if (iv[i].idx < vx0.val()) {
231         iv[i].view.cancel(home,p,pc_ac);
232         ++i;
233       } else if (iv[i].idx > vx0.val()) {
234         ++vx0;
235       } else {
236         assert(iv[i].idx == vx0.val());
237         switch (rt(iv[i].view,x1)) {
238         case RT_FALSE:
239           iv[i].view.cancel(home,p,pc_ac);
240           break;
241         case RT_TRUE:
242         case RT_MAYBE:
243           iv[j++] = iv[i];
244           break;
245         default: GECODE_NEVER;
246         }
247         ++vx0; ++i;
248       }
249     }
250     while (i < iv.size())
251       iv[i++].view.cancel(home,p,pc_ac);
252     bool adjust = (j<iv.size());
253     iv.size(j);
254 
255     if (iv.size() == 0)
256       return ES_FAILED;
257 
258     if (iv.size() == 1) {
259       GECODE_ME_CHECK(x0.eq(home,iv[0].idx));
260     } else if (adjust) {
261       IterIdxView<VA> v(&iv[0],&iv[0]+iv.size());
262       GECODE_ME_CHECK(x0.narrow_v(home,v,false));
263       assert(x0.size() == static_cast<unsigned int>(iv.size()));
264     }
265     return ES_OK;
266   }
267 
268 
269 
270 
271   /*
272    * Bounds consistent propagator
273    *
274    */
275 
276   template<class VA, class VB, class VC>
277   forceinline
ViewBnd(Home home,IdxViewArray<VA> & iv,VB x0,VC x1)278   ViewBnd<VA,VB,VC>::ViewBnd(Home home,
279                              IdxViewArray<VA>& iv, VB x0, VC x1)
280     : View<VA,VB,VC,PC_INT_BND>(home,iv,x0,x1) {}
281 
282   template<class VA, class VB, class VC>
283   ExecStatus
post(Home home,IdxViewArray<VA> & iv,VB x0,VC x1)284   ViewBnd<VA,VB,VC>::post(Home home,
285                           IdxViewArray<VA>& iv, VB x0, VC x1) {
286     GECODE_ME_CHECK(x0.gq(home,0));
287     GECODE_ME_CHECK(x0.le(home,iv.size()));
288     if (x0.assigned()) {
289       (void) new (home) Rel::EqBnd<VA,VC>(home,iv[x0.val()].view,x1);
290       return ES_OK;
291     } else {
292       assert(iv.size()>1);
293       (void) new (home) ViewBnd<VA,VB,VC>(home,iv,x0,x1);
294     }
295     return ES_OK;
296   }
297 
298 
299   template<class VA, class VB, class VC>
300   forceinline
ViewBnd(Space & home,ViewBnd & p)301   ViewBnd<VA,VB,VC>::ViewBnd(Space& home, ViewBnd& p)
302     : View<VA,VB,VC,PC_INT_BND>(home,p) {}
303 
304   template<class VA, class VB, class VC>
305   Actor*
copy(Space & home)306   ViewBnd<VA,VB,VC>::copy(Space& home) {
307     return new (home) ViewBnd<VA,VB,VC>(home,*this);
308   }
309 
310   template<class VA, class VB, class VC>
311   ExecStatus
propagate(Space & home,const ModEventDelta &)312   ViewBnd<VA,VB,VC>::propagate(Space& home, const ModEventDelta&) {
313     assert(iv.size() > 1);
314     RelTestBnd<VA,VC> rt;
315     GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_BND,RelTestBnd<VA,VC> >
316                      (home,iv,x0,x1,*this,rt)));
317     if (iv.size() == 1) {
318       ExecStatus es = home.ES_SUBSUMED(*this);
319       (void) new (home) Rel::EqBnd<VA,VC>(home(*this),iv[0].view,x1);
320       return es;
321     }
322     assert(iv.size() > 1);
323     // Compute new result
324     int min = iv[0].view.min();
325     int max = iv[0].view.max();
326     for (int i=1; i<iv.size(); i++) {
327       min = std::min(iv[i].view.min(),min);
328       max = std::max(iv[i].view.max(),max);
329     }
330     ExecStatus es = shared(x0,x1) ? ES_NOFIX : ES_FIX;
331     {
332      ModEvent me = x1.lq(home,max);
333      if (me_failed(me))
334        return ES_FAILED;
335      if (me_modified(me) && (x1.max() != max))
336        es = ES_NOFIX;
337     }
338     {
339      ModEvent me = x1.gq(home,min);
340      if (me_failed(me))
341        return ES_FAILED;
342      if (me_modified(me) && (x1.min() != min))
343        es = ES_NOFIX;
344     }
345     return (x1.assigned() && (min == max)) ?
346       home.ES_SUBSUMED(*this) : es;
347   }
348 
349 
350 
351 
352 
353   /*
354    * Domain consistent propagator
355    *
356    */
357 
358   template<class VA, class VB, class VC>
359   forceinline
ViewDom(Home home,IdxViewArray<VA> & iv,VB x0,VC x1)360   ViewDom<VA,VB,VC>::ViewDom(Home home,
361                              IdxViewArray<VA>& iv, VB x0, VC x1)
362     : View<VA,VB,VC,PC_INT_DOM>(home,iv,x0,x1) {}
363 
364   template<class VA, class VB, class VC>
365   ExecStatus
post(Home home,IdxViewArray<VA> & iv,VB x0,VC x1)366   ViewDom<VA,VB,VC>::post(Home home,
367                           IdxViewArray<VA>& iv, VB x0, VC x1){
368     GECODE_ME_CHECK(x0.gq(home,0));
369     GECODE_ME_CHECK(x0.le(home,iv.size()));
370     if (x0.assigned()) {
371       (void) new (home) Rel::EqDom<VA,VC>(home,iv[x0.val()].view,x1);
372       return ES_OK;
373     } else {
374       assert(iv.size()>1);
375       (void) new (home) ViewDom<VA,VB,VC>(home,iv,x0,x1);
376     }
377     return ES_OK;
378   }
379 
380 
381   template<class VA, class VB, class VC>
382   forceinline
ViewDom(Space & home,ViewDom & p)383   ViewDom<VA,VB,VC>::ViewDom(Space& home, ViewDom& p)
384     : View<VA,VB,VC,PC_INT_DOM>(home,p) {}
385 
386   template<class VA, class VB, class VC>
387   Actor*
copy(Space & home)388   ViewDom<VA,VB,VC>::copy(Space& home) {
389     return new (home) ViewDom<VA,VB,VC>(home,*this);
390   }
391 
392 
393   template<class VA, class VB, class VC>
394   PropCost
cost(const Space &,const ModEventDelta & med) const395   ViewDom<VA,VB,VC>::cost(const Space&, const ModEventDelta& med) const {
396     return PropCost::linear((VA::me(med) != ME_INT_DOM) ?
397                             PropCost::LO : PropCost::HI, iv.size()+2);
398   }
399 
400   template<class VA, class VB, class VC>
401   ExecStatus
propagate(Space & home,const ModEventDelta & med)402   ViewDom<VA,VB,VC>::propagate(Space& home, const ModEventDelta& med) {
403     assert(iv.size() > 1);
404     if (VA::me(med) != ME_INT_DOM) {
405       RelTestBnd<VA,VC> rt;
406       GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_DOM,RelTestBnd<VA,VC> >
407                        (home,iv,x0,x1,*this,rt)));
408       if (iv.size() == 1) {
409         ExecStatus es = home.ES_SUBSUMED(*this);
410         (void) new (home) Rel::EqDom<VA,VC>(home(*this),iv[0].view,x1);
411         return es;
412       }
413       // Compute new result
414       int min = iv[0].view.min();
415       int max = iv[0].view.max();
416       for (int i=1; i<iv.size(); i++) {
417         min = std::min(iv[i].view.min(),min);
418         max = std::max(iv[i].view.max(),max);
419       }
420       GECODE_ME_CHECK(x1.lq(home,max));
421       GECODE_ME_CHECK(x1.gq(home,min));
422       return (x1.assigned() && (min == max)) ?
423         home.ES_SUBSUMED(*this) :
424         home.ES_NOFIX_PARTIAL(*this,VA::med(ME_INT_DOM));
425     }
426     RelTestDom<VA,VC> rt;
427     GECODE_ES_CHECK((scan<VA,VB,VC,PC_INT_DOM,RelTestDom<VA,VC> >
428                      (home,iv,x0,x1,*this,rt)));
429     if (iv.size() == 1) {
430       ExecStatus es = home.ES_SUBSUMED(*this);
431       (void) new (home) Rel::EqDom<VA,VC>(home(*this),iv[0].view,x1);
432       return es;
433     }
434     assert(iv.size() > 1);
435 
436     if (x1.assigned()) {
437       for (int i=0; i<iv.size(); i++)
438         if (iv[i].view.in(x1.val()))
439           return shared(x0,x1) ? ES_NOFIX : ES_FIX;
440       return ES_FAILED;
441     } else {
442       Region r;
443       ViewRanges<VA>* i_view = r.alloc<ViewRanges<VA> >(iv.size());
444       for (int i=0; i<iv.size(); i++)
445         i_view[i].init(iv[i].view);
446       Iter::Ranges::NaryUnion i_val(r, i_view, iv.size());
447       ModEvent me = x1.inter_r(home,i_val);
448       r.free<ViewRanges<VA> >(i_view,iv.size());
449       GECODE_ME_CHECK(me);
450       return (shared(x0,x1) || me_modified(me)) ? ES_NOFIX : ES_FIX;
451     }
452   }
453 
454 }}}
455 
456 // STATISTICS: int-prop
457 
458