Generated on Sun Feb 17 15:24:15 2019 for Gecode by doxygen 1.6.3

lq.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2011
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 namespace Gecode { namespace Set { namespace Rel {
00035 
00039   class CharacteristicSets {
00040   protected:
00042     unsigned int xsize;
00044     Support::BitSetBase b;
00046     int* ub;
00048     bool xlm;
00050     bool xum;
00052     bool ylm;
00054     bool yum;
00056     bool get(unsigned int i) const;
00058     void set(unsigned int i, bool j);
00059 
00061     class CSIter {
00062     public:
00064       CharacteristicSets* cs;
00066       unsigned int i;
00068       unsigned int xoff;
00070       unsigned int yoff;
00072       void operator++ (void);
00074       CSIter(void);
00076       CSIter(CharacteristicSets& cs0, unsigned int xoff0, unsigned int yoff0);
00078       bool operator() (void) const;
00080       int val(void) const;
00081     };
00082 
00083   public:
00085     template<class View0, class View1>
00086     CharacteristicSets(Region& re, View0 x, View1 y);
00087 
00089     bool xmin(unsigned int i) const;
00091     bool xmax(unsigned int i) const;
00093     bool ymin(unsigned int i) const;
00095     bool ymax(unsigned int i) const;
00096 
00098     void xmin(unsigned int i, bool j);
00100     void xmax(unsigned int i, bool j);
00102     void ymin(unsigned int i, bool j);
00104     void ymax(unsigned int i, bool j);
00105 
00107     ModEvent xlq(unsigned int i, bool j);
00109     ModEvent xgq(unsigned int i, bool j);
00111     ModEvent ylq(unsigned int i, bool j);
00113     ModEvent ygq(unsigned int i, bool j);
00114 
00116     unsigned int size(void) const;
00117 
00119     template<class View0, class View1>
00120     ExecStatus prune(Space& home, View0 x, View1 y);
00121 
00122   };
00123 
00124 
00125   forceinline bool
00126   CharacteristicSets::get(unsigned int i) const {
00127     return b.get(i);
00128   }
00129   forceinline void
00130   CharacteristicSets::set(unsigned int i, bool j) {
00131     if (j)
00132       b.set(i);
00133     else
00134       b.clear(i);
00135   }
00136   forceinline unsigned int
00137   CharacteristicSets::size(void) const {
00138     return xsize;
00139   }
00140 
00141   forceinline
00142   CharacteristicSets::CSIter::CSIter(void) {}
00143   forceinline
00144   CharacteristicSets::CSIter::CSIter(CharacteristicSets& cs0,
00145                                      unsigned int xoff0, unsigned int yoff0)
00146     : cs(&cs0), i(0), xoff(xoff0), yoff(yoff0) {
00147     while ((i < cs->xsize) && !cs->get(xoff+2*i+yoff))
00148       i++;
00149   }
00150   forceinline void
00151   CharacteristicSets::CSIter::operator++ (void) {
00152     i++;
00153     while ((i < cs->xsize) && !cs->get(xoff+2*i+yoff))
00154       i++;
00155   }
00156   forceinline bool
00157   CharacteristicSets::CSIter::operator() (void) const {
00158     return i<cs->xsize;
00159   }
00160   forceinline int
00161   CharacteristicSets::CSIter::val(void) const {
00162     return cs->ub[i];
00163   }
00164 
00165 
00166   forceinline bool
00167   CharacteristicSets::xmin(unsigned int i) const {
00168     return get(2*i);
00169   }
00170   forceinline bool
00171   CharacteristicSets::xmax(unsigned int i) const {
00172     return get(2*i+1);
00173   }
00174   forceinline bool
00175   CharacteristicSets::ymin(unsigned int i) const {
00176     return get(2*xsize+2*i);
00177   }
00178   forceinline bool
00179   CharacteristicSets::ymax(unsigned int i) const {
00180     return get(2*xsize+2*i+1);
00181   }
00182 
00183   forceinline void
00184   CharacteristicSets::xmin(unsigned int i, bool j) {
00185     set(2*i,j);
00186   }
00187   forceinline void
00188   CharacteristicSets::xmax(unsigned int i, bool j) {
00189     set(2*i+1,j);
00190   }
00191   forceinline void
00192   CharacteristicSets::ymin(unsigned int i, bool j) {
00193     set(2*xsize+2*i,j);
00194   }
00195   forceinline void
00196   CharacteristicSets::ymax(unsigned int i, bool j) {
00197     set(2*xsize+2*i+1,j);
00198   }
00199 
00200   forceinline ModEvent
00201   CharacteristicSets::xlq(unsigned int i, bool j) {
00202     if (!j) {
00203       if (xmin(i)) return ME_SET_FAILED;
00204       if (xmax(i)) {
00205         xmax(i,false);
00206         xum=true;
00207       }
00208     }
00209     return ME_SET_NONE;
00210   }
00211   forceinline ModEvent
00212   CharacteristicSets::xgq(unsigned int i, bool j) {
00213     if (j) {
00214       if (!xmax(i)) return ME_SET_FAILED;
00215       if (!xmin(i)) {
00216         xmin(i,true);
00217         xlm=true;
00218       }
00219     }
00220     return ME_SET_NONE;
00221   }
00222   forceinline ModEvent
00223   CharacteristicSets::ylq(unsigned int i, bool j) {
00224     if (!j) {
00225       if (ymin(i)) return ME_SET_FAILED;
00226       if (ymax(i)) {
00227         ymax(i,false);
00228         yum=true;
00229       }
00230     }
00231     return ME_SET_NONE;
00232   }
00233   forceinline ModEvent
00234   CharacteristicSets::ygq(unsigned int i, bool j) {
00235     if (j) {
00236       if (!ymax(i)) return ME_SET_FAILED;
00237       if (!ymin(i)) {
00238         ymin(i,true);
00239         ylm=true;
00240       }
00241     }
00242     return ME_SET_NONE;
00243   }
00244 
00245   template<class View0, class View1>
00246   forceinline ExecStatus
00247   CharacteristicSets::prune(Space& home, View0 x, View1 y) {
00248     if (xlm) {
00249       CSIter i(*this,0,0);
00250       Iter::Values::ToRanges<CSIter> ir(i);
00251       GECODE_ME_CHECK(x.includeI(home,ir));
00252     }
00253     if (xum) {
00254       CSIter i(*this,0,1);
00255       Iter::Values::ToRanges<CSIter> ir(i);
00256       GECODE_ME_CHECK(x.intersectI(home,ir));
00257     }
00258     if (ylm) {
00259       CSIter i(*this,2*xsize,0);
00260       Iter::Values::ToRanges<CSIter> ir(i);
00261       GECODE_ME_CHECK(y.includeI(home,ir));
00262     }
00263     if (yum) {
00264       CSIter i(*this,2*xsize,1);
00265       Iter::Values::ToRanges<CSIter> ir(i);
00266       GECODE_ME_CHECK(y.intersectI(home,ir));
00267     }
00268     return ES_OK;
00269   }
00270 
00271   template<class View0, class View1>
00272   forceinline
00273   CharacteristicSets::CharacteristicSets(Region& re,View0 x, View1 y)
00274     : xlm(false), xum(false), ylm(false), yum(false) {
00275     LubRanges<View0> xlub(x);
00276     LubRanges<View1> ylub(y);
00277     Iter::Ranges::Union<LubRanges<View0>,LubRanges<View1> > xylub(xlub,ylub);
00278     Iter::Ranges::Cache xylubc(re,xylub);
00279     xsize = Iter::Ranges::size(xylubc);
00280     b.init(re,4*xsize);
00281     ub = re.alloc<int>(xsize);
00282     xylubc.reset();
00283     Iter::Ranges::ToValues<Iter::Ranges::Cache> xylubv(xylubc);
00284     LubRanges<View0> xur(x);
00285     GlbRanges<View0> xlr(x);
00286     LubRanges<View1> yur(y);
00287     GlbRanges<View1> ylr(y);
00288     Iter::Ranges::ToValues<LubRanges<View0> > xuv(xur);
00289     Iter::Ranges::ToValues<GlbRanges<View0> > xlv(xlr);
00290     Iter::Ranges::ToValues<LubRanges<View1> > yuv(yur);
00291     Iter::Ranges::ToValues<GlbRanges<View1> > ylv(ylr);
00292     for (unsigned int i=0; xylubv(); ++xylubv, ++i) {
00293       ub[i] = xylubv.val();
00294       if (xlv() && xylubv.val()==xlv.val()) {
00295         b.set(2*i);
00296         ++xlv;
00297       }
00298       if (xuv() && xylubv.val()==xuv.val()) {
00299         b.set(2*i+1);
00300         ++xuv;
00301       }
00302       if (ylv() && xylubv.val()==ylv.val()) {
00303         b.set(2*xsize+2*i);
00304         ++ylv;
00305       }
00306       if (yuv() && xylubv.val()==yuv.val()) {
00307         b.set(2*xsize+2*i+1);
00308         ++yuv;
00309       }
00310     }
00311   }
00312 
00313   template<class View0, class View1, bool strict>
00314   forceinline
00315   Lq<View0,View1,strict>::Lq(Home home, View0 x, View1 y)
00316     : MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {}
00317 
00318   template<class View0, class View1, bool strict>
00319   forceinline
00320   Lq<View0,View1,strict>::Lq(Space& home, Lq& p)
00321     : MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,p) {}
00322 
00323   template<class View0, class View1, bool strict>
00324   ExecStatus
00325   Lq<View0,View1,strict>::post(Home home, View0 x, View1 y) {
00326     if (strict)
00327       GECODE_ME_CHECK(y.cardMin(home,1));
00328     if (same(x,y))
00329       return strict ? ES_FAILED : ES_OK;
00330     (void) new (home) Lq(home,x,y);
00331     return ES_OK;
00332   }
00333 
00334   template<class View0, class View1, bool strict>
00335   Actor*
00336   Lq<View0,View1,strict>::copy(Space& home) {
00337     return new (home) Lq(home,*this);
00338   }
00339 
00340   template<class View0, class View1, bool strict>
00341   ExecStatus
00342   Lq<View0,View1,strict>::propagate(Space& home, const ModEventDelta&) {
00343     if ( (!strict) && x1.cardMax()==0) {
00344       GECODE_ME_CHECK(x0.cardMax(home,0));
00345     }
00346 
00347     if (x0.cardMax()==0) {
00348       return home.ES_SUBSUMED(*this);
00349     }
00350 
00351     if (x0.glbMin() < x1.lubMin())
00352       return ES_FAILED;
00353     if (x1.glbMin() < x0.lubMin())
00354       return home.ES_SUBSUMED(*this);
00355 
00356     bool assigned = x0.assigned() && x1.assigned();
00357 
00358     Region re;
00359     CharacteristicSets cs(re,x0,x1);
00360 
00361     /*
00362      * State 1
00363      *
00364      */
00365     unsigned int i=0;
00366     unsigned int firsti=0;
00367     unsigned int n=cs.size();
00368     while ((i<n) && (cs.xmin(i) == cs.ymax(i))) {
00369       // case: =, >=
00370       GECODE_ME_CHECK(cs.xlq(i,cs.ymax(i)));
00371       GECODE_ME_CHECK(cs.ygq(i,cs.xmin(i)));
00372       i++;
00373     }
00374 
00375     if (i == n) {// case: $
00376       if (strict) {
00377         return ES_FAILED;
00378       } else {
00379         GECODE_ES_CHECK(cs.prune(home,x0,x1));
00380         return home.ES_SUBSUMED(*this);
00381       }
00382     }
00383 
00384     // Possible cases left: <, <=, > (yields failure), ?
00385     GECODE_ME_CHECK(cs.xlq(i,cs.ymax(i)));
00386     GECODE_ME_CHECK(cs.ygq(i,cs.xmin(i)));
00387 
00388     if (cs.xmax(i) < cs.ymin(i)) { // case: < (after tell)
00389       GECODE_ES_CHECK(cs.prune(home,x0,x1));
00390       return home.ES_SUBSUMED(*this);
00391     }
00392 
00393     firsti=i;
00394 
00395     /*
00396      * State 2
00397      *   prefix: (?|<=)
00398      *
00399      */
00400     i++;
00401 
00402     while ((i < n) &&
00403            (cs.xmin(i) == cs.ymax(i)) &&
00404            (cs.xmax(i) == cs.ymin(i))) { // case: =
00405       i++;
00406     }
00407 
00408     if (i == n) { // case: $
00409       if (strict)
00410         goto rewrite_le;
00411       else
00412         goto rewrite_lq;
00413     }
00414 
00415     if (cs.xmax(i) < cs.ymin(i)) // case: <
00416       goto rewrite_lq;
00417 
00418     if (cs.xmin(i) > cs.ymax(i)) // case: >
00419       goto rewrite_le;
00420 
00421     if (cs.xmax(i) <= cs.ymin(i)) {
00422       // case: <= (invariant: not =, <)
00423       /*
00424        * State 3
00425        *   prefix: (?|<=),<=
00426        *
00427        */
00428       i++;
00429 
00430       while ((i < n) && (cs.xmax(i) == cs.ymin(i))) {// case: <=, =
00431         i++;
00432       }
00433 
00434       if (i == n) { // case: $
00435         if (strict) {
00436           GECODE_ES_CHECK(cs.prune(home,x0,x1));
00437           return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00438         } else {
00439           goto rewrite_lq;
00440         }
00441       }
00442 
00443       if (cs.xmax(i) < cs.ymin(i)) // case: <
00444         goto rewrite_lq;
00445 
00446       GECODE_ES_CHECK(cs.prune(home,x0,x1));
00447       return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00448     }
00449 
00450     if (cs.xmin(i) >= cs.ymax(i)) {
00451       // case: >= (invariant: not =, >)
00452       /*
00453        * State 4
00454        *   prefix: (?|<=) >=
00455        *
00456        */
00457       i++;
00458 
00459       while ((i < n) && (cs.xmin(i) == cs.ymax(i))) {
00460         // case: >=, =
00461         i++;
00462       }
00463 
00464       if (i == n) { // case: $
00465         if (strict) {
00466           goto rewrite_le;
00467         } else {
00468           GECODE_ES_CHECK(cs.prune(home,x0,x1));
00469           return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00470         }
00471       }
00472 
00473       if (cs.xmin(i) > cs.ymax(i)) // case: >
00474         goto rewrite_le;
00475 
00476       GECODE_ES_CHECK(cs.prune(home,x0,x1));
00477       return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00478     }
00479 
00480     GECODE_ES_CHECK(cs.prune(home,x0,x1));
00481     return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00482 
00483   rewrite_le:
00484     GECODE_ME_CHECK(cs.xlq(firsti,false));
00485     GECODE_ME_CHECK(cs.ygq(firsti,true));
00486     GECODE_ES_CHECK(cs.prune(home,x0,x1));
00487     return home.ES_SUBSUMED(*this);
00488   rewrite_lq:
00489     GECODE_ES_CHECK(cs.prune(home,x0,x1));
00490     return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00491   }
00492 
00493 }}}
00494 
00495 // STATISTICS: set-prop