Generated on Wed Jan 4 17:49:14 2006 for Gecode by doxygen 1.4.6

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