Generated on Thu Jul 6 07:06:50 2006 for Gecode by doxygen 1.4.7

common.icc

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