Generated on Wed Mar 19 07:30:03 2008 for Gecode by doxygen 1.5.5

common.icc

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  *     Christian Schulte <schulte@gecode.org>
00006  *
00007  *  Contributing authors:
00008  *     Gabor Szokoli <szokoli@gecode.org>
00009  *
00010  *  Copyright:
00011  *     Guido Tack, 2004
00012  *     Christian Schulte, 2004
00013  *     Gabor Szokoli, 2004
00014  *
00015  *  Last modified:
00016  *     $Date: 2008-02-20 17:07:56 +0100 (Wed, 20 Feb 2008) $ by $Author: tack $
00017  *     $Revision: 6251 $
00018  *
00019  *  This file is part of Gecode, the generic constraint
00020  *  development environment:
00021  *     http://www.gecode.org
00022  *
00023  *  Permission is hereby granted, free of charge, to any person obtaining
00024  *  a copy of this software and associated documentation files (the
00025  *  "Software"), to deal in the Software without restriction, including
00026  *  without limitation the rights to use, copy, modify, merge, publish,
00027  *  distribute, sublicense, and/or sell copies of the Software, and to
00028  *  permit persons to whom the Software is furnished to do so, subject to
00029  *  the following conditions:
00030  *
00031  *  The above copyright notice and this permission notice shall be
00032  *  included in all copies or substantial portions of the Software.
00033  *
00034  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00035  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00036  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00037  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00038  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00039  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00040  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00041  *
00042  */
00043 
00044 #ifndef __GECODE_SET_RELOP_COMM_ICC__
00045 #define __GECODE_SET_RELOP_COMM_ICC__
00046 
00047 namespace Gecode { 
00048 
00049   template <class View0, class View1>
00050   forceinline bool
00051   viewarrayshared(const ViewArray<View0>& va,
00052                        const View1& y) {
00053     return va.shared(y);
00054   }
00055 
00056   template <>
00057   forceinline bool
00058   viewarrayshared<Set::SingletonView,Set::SetView>
00059   (const ViewArray<Set::SingletonView>&, const Set::SetView&) {
00060     return false;
00061   }
00062 
00063   template <>
00064   forceinline bool
00065   viewarrayshared<Set::ComplementView<Set::SingletonView>,Set::SetView>
00066   (const ViewArray<Set::ComplementView<Set::SingletonView> >&,
00067    const Set::SetView&) {
00068     return false;
00069   }
00070 
00071   template <>
00072   forceinline bool
00073   viewarrayshared<Set::ComplementView<Set::SingletonView>,
00074                        Set::ComplementView<Set::SetView> >
00075   (const ViewArray<Set::ComplementView<Set::SingletonView> >&,
00076    const Set::ComplementView<Set::SetView>&) {
00077     return false;
00078   }
00079 
00080 
00081 namespace Set { namespace RelOp {
00082 
00083   /*
00084    * Detect sharing between 3 variables
00085    *
00086    */
00087   template <class View0, class View1, class View2>
00088   forceinline bool
00089   shared(View0 v0, View1 v1, View2 v2) {
00090     return shared(v0,v1) || shared(v0,v2) || shared(v1,v2);
00091   }
00092 
00093   template <class View0, class View1, class View2>
00094   ExecStatus unionCard(Space* home,
00095                        bool& retmodified, View0& x0, View1& x1, View2& x2) {
00096     bool modified = false;
00097     do {
00098       retmodified |= modified;
00099       modified = false;
00100 
00101       {
00102         LubRanges<View0> x0ub(x0);
00103         LubRanges<View1> x1ub(x1);
00104         Iter::Ranges::Inter<LubRanges<View0>, LubRanges<View1> > i1(x0ub,x1ub);
00105         unsigned int s1 = Iter::Ranges::size(i1);
00106         unsigned int res = std::max(x0.cardMin()+
00107                                     (x1.cardMin()<s1 ?
00108                                      0 : x1.cardMin()-s1),
00109                                     std::max(x0.cardMin(),
00110                                              x1.cardMin()));
00111         GECODE_ME_CHECK_MODIFIED(modified, x2.cardMin(home,res));
00112       }
00113 
00114       {
00115         LubRanges<View0> x0ub(x0);
00116         LubRanges<View1> x1ub(x1);
00117         Iter::Ranges::Union<LubRanges<View0>, LubRanges<View1> > u1(x0ub,x1ub);
00118         unsigned int s1 = Iter::Ranges::size(u1);
00119         GECODE_ME_CHECK_MODIFIED(modified, 
00120                           x2.cardMax(home,
00121                                      std::min(x0.cardMax()+x1.cardMax(),s1)));
00122       }
00123 
00124       if (x2.cardMin() > x1.cardMax())
00125         GECODE_ME_CHECK_MODIFIED(modified,
00126                           x0.cardMin(home,x2.cardMin() - x1.cardMax()));
00127 
00128       if (x2.cardMin() > x0.cardMax())
00129         GECODE_ME_CHECK_MODIFIED(modified,
00130                           x1.cardMin(home,x2.cardMin() - x0.cardMax()));
00131 
00132       GECODE_ME_CHECK_MODIFIED(modified,
00133                         x0.cardMax(home,x2.cardMax()));
00134       GECODE_ME_CHECK_MODIFIED(modified,
00135                         x1.cardMax(home,x2.cardMax()));
00136     } while(modified);
00137     return ES_FIX;
00138   }
00139 
00140   template <class View0, class View1>
00141   ExecStatus
00142   unionNCard(Space* home, bool& modified, ViewArray<View0>& x,
00143              View1& y, GLBndSet& unionOfDets) {
00144     int xsize = x.size();
00145     // Max(Xi.cardMin) <= y.card <= Sum(Xi.cardMax)
00146     // Xi.card <=y.cardMax
00147     unsigned int cardMaxSum=unionOfDets.size();
00148     bool maxValid = true;
00149     for (int i=xsize; i--; ){
00150       cardMaxSum+=x[i].cardMax();
00151       if (cardMaxSum < x[i].cardMax()) { maxValid = false; } //overflow
00152       GECODE_ME_CHECK_MODIFIED(modified, y.cardMin(home,x[i].cardMin()) );
00153       GECODE_ME_CHECK_MODIFIED(modified, x[i].cardMax(home,y.cardMax()) );
00154     }
00155     if (maxValid) {
00156       GECODE_ME_CHECK_MODIFIED(modified, y.cardMax(home,cardMaxSum));
00157     }
00158     //y.cardMin - Sum(Xj.cardMax) <= Xi.card
00159 
00160     if (x.size() == 0)
00161       return ES_NOFIX;
00162 
00163     //TODO: overflow management is a waste now.
00164     {
00165       GECODE_AUTOARRAY(unsigned int, rightSum, xsize);
00166       rightSum[xsize-1]=0;
00167 
00168       for (int i=x.size()-1;i--;) {
00169         rightSum[i] = rightSum[i+1] + x[i+1].cardMax();
00170         if (rightSum[i] < rightSum[i+1]) {
00171           //overflow, fill the rest of the array.
00172           for (int j=i; j>0;j--) {
00173             rightSum[j]=Limits::card;
00174           }
00175           break;
00176         }
00177       }
00178 
00179       //Size of union of determied vars missing from x sneaked in here:
00180       unsigned int leftAcc=unionOfDets.size();
00181 
00182       for (int i=0; i<xsize;i++) {
00183         unsigned int jsum = leftAcc+rightSum[i];
00184         //If jsum did not overflow and is less than y.cardMin:
00185         if (jsum >= leftAcc &&  jsum < y.cardMin()) {
00186           GECODE_ME_CHECK_MODIFIED(modified, x[i].cardMin(home,y.cardMin()-jsum));
00187         }
00188         leftAcc += x[i].cardMax();
00189         if (leftAcc < x[i].cardMax()) {leftAcc = Limits::card;}
00190       }
00191     }
00192 
00193     //y.cardMin - |U(Xj.ub)| <= Xi.card
00194 
00195     {
00196       GECODE_AUTOARRAY(GLBndSet, rightUnion, xsize);
00197       new (&rightUnion[xsize-1]) GLBndSet(home);
00198       for (int i=xsize-1;i--;){
00199         BndSetRanges prev(rightUnion[i+1]);
00200         LubRanges<View0> prevX(x[i+1]);
00201         Iter::Ranges::Union< BndSetRanges,LubRanges<View0> >
00202           iter(prev,prevX);
00203         new (&rightUnion[i]) GLBndSet(home);
00204         rightUnion[i].includeI(home, iter);
00205       }
00206 
00207       //union of determied vars missing from x sneaked in here:
00208       GLBndSet leftAcc;
00209       leftAcc.update(home,unionOfDets);
00210       for (int i=0; i<xsize; i++) {
00211         BndSetRanges left(leftAcc);
00212         BndSetRanges right(rightUnion[i]);
00213         Iter::Ranges::Union<BndSetRanges,
00214           BndSetRanges> iter(left, right);
00215         unsigned int unionSize = Iter::Ranges::size(iter);
00216         if (y.cardMin() > unionSize) {
00217           GECODE_ME_CHECK_MODIFIED(modified,
00218                             x[i].cardMin(home, y.cardMin() - unionSize) );
00219         }
00220         LubRanges<View0> xiub(x[i]);
00221         leftAcc.includeI(home, xiub);
00222       }
00223 
00224       for (int i=xsize; i--;)
00225         rightUnion[i].dispose(home);
00226       leftAcc.dispose(home);
00227     }
00228 
00229     //no need for this: |y.lb - U(Xj.cardMax)| <= S.card
00230 
00231     return ES_NOFIX;
00232 
00233   }
00234 
00235   /*
00236    * Xi UB is subset of YUB
00237    * Subscribes to Y UB
00238    */
00239   template <class View0, class View1>
00240   ExecStatus
00241   unionNXiUB(Space* home,
00242              bool& modified, ViewArray<View0>& x, View1& y,
00243              GLBndSet &) {
00244     int xsize = x.size();
00245     for (int i=xsize; i--; ) {
00246       LubRanges<View1> yub(y);
00247       GECODE_ME_CHECK_MODIFIED(modified, x[i].intersectI(home, yub));
00248     }
00249     return ES_FIX;
00250   }
00251 
00252   // cardinality rules for PartitionN constraint
00253   template <class View0, class View1>
00254   ExecStatus
00255   partitionNCard(Space* home,
00256                  bool& modified, ViewArray<View0>& x, View1& y,
00257                  GLBndSet& unionOfDets) {
00258     unsigned int cardMinSum=unionOfDets.size();
00259     unsigned int cardMaxSum=unionOfDets.size();
00260     int xsize = x.size();
00261     for (int i=xsize; i--; ) {
00262       cardMinSum+=x[i].cardMin();
00263       if (cardMinSum < x[i].cardMin()) {
00264         //sum of mins overflows: fail the space.
00265         GECODE_ME_CHECK(ME_SET_FAILED);
00266       }
00267     }
00268     GECODE_ME_CHECK_MODIFIED(modified, y.cardMin(home,cardMinSum));
00269     for (int i=xsize; i--; ) {
00270       cardMaxSum+=x[i].cardMax();
00271       if (cardMaxSum < x[i].cardMax()) {
00272         //sum of maxes overflows: no useful information to tell.
00273         goto overflow;
00274       }
00275     }
00276     GECODE_ME_CHECK_MODIFIED(modified, y.cardMax(home,cardMaxSum));
00277 
00278     if (x.size() == 0)
00279       return ES_NOFIX;
00280 
00281   overflow:
00282 
00283     //Cardinality of each x[i] limited by cardinality of y minus all x[j]s:
00284 
00285     {
00286       GECODE_AUTOARRAY(unsigned int, rightMinSum, xsize);
00287       GECODE_AUTOARRAY(unsigned int, rightMaxSum, xsize);
00288       rightMinSum[xsize-1]=0;
00289       rightMaxSum[xsize-1]=0;
00290 
00291       for (int i=x.size()-1;i--;) {
00292         rightMaxSum[i] = rightMaxSum[i+1] + x[i+1].cardMax();
00293         if (rightMaxSum[i] < rightMaxSum[i+1]) {
00294           //overflow, fill the rest of the array.
00295           for (int j=i; j>0;j--) {
00296             rightMaxSum[j]=Limits::card;
00297           }
00298           break;
00299         }
00300       }
00301       for (int i=x.size()-1;i--;) {
00302         rightMinSum[i] = rightMinSum[i+1] + x[i+1].cardMin();
00303         if (rightMinSum[i] < rightMinSum[i+1]) {
00304           //overflow, fail the space
00305           GECODE_ME_CHECK(ME_SET_FAILED);
00306         }
00307       }
00308       unsigned int leftMinAcc=unionOfDets.size();
00309       unsigned int leftMaxAcc=unionOfDets.size();
00310 
00311       for (int i=0; i<xsize;i++) {
00312         unsigned int maxSum = leftMaxAcc+rightMaxSum[i];
00313         unsigned int minSum = leftMinAcc+rightMinSum[i];
00314         //If maxSum did not overflow and is less than y.cardMin:
00315         if (maxSum >= leftMaxAcc &&  maxSum < y.cardMin()) {
00316           GECODE_ME_CHECK_MODIFIED(modified, x[i].cardMin(home,y.cardMin()-maxSum));
00317         }
00318 
00319         //Overflow, fail.
00320         if (minSum < leftMinAcc || y.cardMax() < minSum) {
00321           GECODE_ME_CHECK(ME_SET_FAILED);
00322         }
00323         else {
00324           GECODE_ME_CHECK_MODIFIED(modified, x[i].cardMax(home,y.cardMax()-minSum));
00325         }
00326 
00327         leftMaxAcc += x[i].cardMax();
00328         if (leftMaxAcc < x[i].cardMax())
00329           leftMaxAcc = Limits::card;
00330         leftMinAcc += x[i].cardMin();
00331         if (leftMinAcc < x[i].cardMin())
00332           GECODE_ME_CHECK(ME_SET_FAILED);
00333       }
00334     }
00335 
00336     return ES_NOFIX;
00337   }
00338 
00339   // Xi LB includes YLB minus union Xj UB
00340   // Xi UB is subset of YUB minus union of Xj LBs
00341   template <class View0, class View1>
00342   ExecStatus
00343   partitionNXi(Space* home,
00344                bool& modified, ViewArray<View0>& x, View1& y) {
00345     int xsize = x.size();
00346     GECODE_AUTOARRAY(GLBndSet, afterUB, xsize);
00347     GECODE_AUTOARRAY(GLBndSet, afterLB, xsize);
00348 
00349     {
00350       GLBndSet sofarAfterUB;
00351       GLBndSet sofarAfterLB;
00352       for (int i=xsize; i--;) {
00353         new (&afterUB[i]) GLBndSet(home);
00354         new (&afterLB[i]) GLBndSet(home);
00355         afterUB[i].update(home,sofarAfterUB);
00356         afterLB[i].update(home,sofarAfterLB);
00357         LubRanges<View0> xiub(x[i]);
00358         GlbRanges<View0> xilb(x[i]);
00359         sofarAfterUB.includeI(home,xiub);
00360         sofarAfterLB.includeI(home,xilb);
00361       }
00362       sofarAfterUB.dispose(home);
00363       sofarAfterLB.dispose(home);
00364     }
00365 
00366     {
00367       GLBndSet sofarBeforeUB;
00368       GLBndSet sofarBeforeLB;
00369       for (int i=0; i<xsize; i++) {
00370         LubRanges<View1> yub(y);
00371         BndSetRanges slb(sofarBeforeLB);
00372         BndSetRanges afterlb(afterLB[i]);
00373         Iter::Ranges::Union<BndSetRanges,
00374           BndSetRanges> xjlb(slb, afterlb);
00375         Iter::Ranges::Diff<LubRanges<View1>,
00376           Iter::Ranges::Union<BndSetRanges,
00377           BndSetRanges> > diff1(yub, xjlb);
00378         GECODE_ME_CHECK_MODIFIED(modified, x[i].intersectI(home,diff1));
00379 
00380         GlbRanges<View1> ylb(y);
00381         BndSetRanges sub(sofarBeforeUB);
00382         BndSetRanges afterub(afterUB[i]);
00383         Iter::Ranges::Union<BndSetRanges,
00384           BndSetRanges> xjub(sub, afterub);
00385         Iter::Ranges::Diff<GlbRanges<View1>,
00386           Iter::Ranges::Union<BndSetRanges,
00387           BndSetRanges> > diff2(ylb, xjub);
00388         GECODE_ME_CHECK_MODIFIED(modified, x[i].includeI(home,diff2));
00389 
00390         LubRanges<View0> xiub(x[i]);
00391         GlbRanges<View0> xilb(x[i]);
00392         sofarBeforeUB.includeI(home,xiub);
00393         sofarBeforeLB.includeI(home,xilb);
00394       }
00395       sofarBeforeLB.dispose(home);
00396       sofarBeforeUB.dispose(home);
00397     }
00398 
00399     for (int i=xsize;i--;) {
00400       afterUB[i].dispose(home);
00401       afterLB[i].dispose(home);
00402     }
00403 
00404     return ES_NOFIX;
00405   }
00406 
00407   // Xi UB is subset of YUB minus union of Xj LBs
00408   template <class View0, class View1>
00409   ExecStatus
00410   partitionNXiUB(Space* home,
00411                  bool& modified, ViewArray<View0>& x, View1& y,
00412                  GLBndSet& unionOfDets) {
00413     int xsize = x.size();
00414     GECODE_AUTOARRAY(GLBndSet, afterLB, xsize);
00415 
00416     {
00417       GLBndSet sofarAfterLB;
00418       for (int i=xsize; i--;) {
00419         new (&afterLB[i]) GLBndSet(home);
00420         afterLB[i].update(home,sofarAfterLB);
00421         GlbRanges<View0> xilb(x[i]);
00422         sofarAfterLB.includeI(home,xilb);
00423       }
00424       sofarAfterLB.dispose(home);
00425     }
00426 
00427     {
00428       GLBndSet sofarBeforeLB;
00429       sofarBeforeLB.update(home,unionOfDets);
00430       for (int i=0; i<xsize; i++) {
00431         LubRanges<View1> yub(y);
00432         BndSetRanges slb(sofarBeforeLB);
00433         BndSetRanges afterlb(afterLB[i]);
00434         Iter::Ranges::Union<BndSetRanges,
00435           BndSetRanges> xjlb(slb, afterlb);
00436         Iter::Ranges::Diff<LubRanges<View1>,
00437           Iter::Ranges::Union<BndSetRanges,
00438           BndSetRanges> > diff1(yub, xjlb);
00439         GECODE_ME_CHECK_MODIFIED(modified, x[i].intersectI(home,diff1));
00440 
00441         GlbRanges<View0> xilb(x[i]);
00442         sofarBeforeLB.includeI(home,xilb);
00443       }
00444       sofarBeforeLB.dispose(home);
00445     }
00446     for (int i=xsize; i--;)
00447       afterLB[i].dispose(home);
00448     return ES_NOFIX;
00449   }
00450 
00451   // Xi LB includes YLB minus union Xj UB
00452   template <class View0, class View1>
00453   ExecStatus
00454   partitionNXiLB(Space* home,
00455                  bool& modified, ViewArray<View0>& x, View1& y,
00456                  GLBndSet& unionOfDets) {
00457     int xsize = x.size();
00458     GECODE_AUTOARRAY(GLBndSet, afterUB, xsize);
00459 
00460     {
00461       GLBndSet sofarAfterUB;
00462       for (int i=xsize; i--;) {
00463         new (&afterUB[i]) GLBndSet(home);
00464         afterUB[i].update(home,sofarAfterUB);
00465         LubRanges<View0> xiub(x[i]);
00466         sofarAfterUB.includeI(home,xiub);
00467       }
00468       sofarAfterUB.dispose(home);
00469     }
00470 
00471     {
00472       //The union of previously determined x[j]-s is added to the mix here:
00473       GLBndSet sofarBeforeUB;
00474       sofarBeforeUB.update(home,unionOfDets);
00475       for (int i=0; i<xsize; i++) {
00476         GlbRanges<View1> ylb(y);
00477         BndSetRanges sub(sofarBeforeUB);
00478         BndSetRanges afterub(afterUB[i]);
00479         Iter::Ranges::Union<BndSetRanges,
00480           BndSetRanges> xjub(sub, afterub);
00481         Iter::Ranges::Diff<GlbRanges<View1>,
00482           Iter::Ranges::Union<BndSetRanges,
00483           BndSetRanges> > diff2(ylb, xjub);
00484         GECODE_ME_CHECK_MODIFIED(modified, x[i].includeI(home,diff2));
00485 
00486         LubRanges<View0> xiub(x[i]);
00487         sofarBeforeUB.includeI(home,xiub);
00488       }
00489       sofarBeforeUB.dispose(home);
00490     }
00491     for (int i=xsize;i--;)
00492       afterUB[i].dispose(home);
00493     return ES_NOFIX;
00494   }
00495 
00496   // Y LB contains union of X LBs
00497   template <class View0, class View1>
00498   ExecStatus
00499   partitionNYLB(Space* home,
00500                 bool& modified, ViewArray<View0>& x, View1& y,
00501                 GLBndSet& unionOfDets) {
00502     assert(unionOfDets.isConsistent());
00503     int xsize = x.size();
00504     GECODE_AUTOARRAY(GlbRanges<View0>,xLBs,xsize);
00505     int nonEmptyCounter=0;
00506     for (int i = xsize; i--; ) {
00507       GlbRanges<View0> r(x[i]);
00508       if (r()) {
00509         xLBs[nonEmptyCounter] = r;
00510         nonEmptyCounter++;
00511       }
00512     }
00513     if (nonEmptyCounter !=0) {
00514       Iter::Ranges::NaryUnion<GlbRanges<View0> >
00515         xLBUnion(xLBs,nonEmptyCounter);
00516       BndSetRanges dets(unionOfDets);
00517       Iter::Ranges::Union<Iter::Ranges::NaryUnion<GlbRanges<View0> >,
00518         BndSetRanges>
00519         allUnion(xLBUnion,dets);
00520       GECODE_ME_CHECK_MODIFIED(modified, y.includeI(home,allUnion));
00521     }
00522     return ES_FIX;
00523   }
00524 
00525   // Y UB is subset of union of X UBs
00526   template <class View0, class View1>
00527   ExecStatus
00528   partitionNYUB(Space* home,
00529                 bool& modified, ViewArray<View0>& x, View1& y,
00530                 GLBndSet& unionOfDets) {
00531     int xsize = x.size();
00532     GECODE_AUTOARRAY(LubRanges<View0>,xUBs,xsize);
00533     int nonEmptyCounter=0;
00534     for (int i = xsize; i--; ) {
00535       LubRanges<View0> r(x[i]);
00536       if (r()) {
00537         xUBs[nonEmptyCounter] = r;
00538         nonEmptyCounter++;
00539       }
00540     }
00541     if (nonEmptyCounter !=0) {
00542       Iter::Ranges::NaryUnion<LubRanges<View0> >
00543         xUBUnion(xUBs,nonEmptyCounter);
00544       BndSetRanges dets(unionOfDets);
00545       Iter::Ranges::Union<Iter::Ranges::NaryUnion<LubRanges<View0> >,
00546         BndSetRanges>
00547         fullUnion(xUBUnion, dets);
00548       GECODE_ME_CHECK_MODIFIED(modified, y.intersectI(home,fullUnion));
00549     }
00550     return ES_FIX;
00551   }
00552 
00553 }}}
00554 
00555 #endif
00556 
00557 // STATISTICS: set-prop