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

partition.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 17:40:47 +0100 (Tue, 15 Nov 2005) $ by $Author: tack $
00016  *     $Revision: 2576 $
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 { namespace Set { namespace RelOp {
00029 
00030   /*
00031    * "Nary partition" propagator
00032    *
00033    */
00034 
00035   template <class View0, class View1>
00036   forceinline
00037   PartitionN<View0,View1>::PartitionN(Space* home, ViewArray<View0>& x, View1 y)
00038     : InhomNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home, x, y) {
00039     shared = x.shared() || viewarrayshared(x,y);
00040   }
00041 
00042   template <class View0, class View1>
00043   forceinline
00044   PartitionN<View0,View1>::PartitionN(Space* home, bool share, PartitionN& p)
00045     : InhomNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,share,p),
00046       shared(p.shared) {
00047     unionOfDets.update(home,p.unionOfDets);
00048   }
00049 
00050   template <class View0, class View1>
00051   Actor*
00052   PartitionN<View0,View1>::copy(Space* home, bool share) {
00053     return new (home) PartitionN(home,share,*this);
00054   }
00055 
00056   template <class View0, class View1>
00057   ExecStatus PartitionN<View0,View1>::post(Space* home, ViewArray<View0>& x,
00058                                            View1 y) {
00059     switch (x.size()) {
00060     case 0:
00061       GECODE_ME_CHECK(y.cardMax(home, 0));
00062       return ES_OK;
00063     case 1:
00064       return Rel::Eq<View0,View1>::post(home, x[0], y);
00065     default:
00066       (void) new (home) PartitionN<View0,View1>(home,x,y);
00067       return ES_OK;
00068     }
00069   }
00070 
00071   template <class View0, class View1>
00072   PropCost PartitionN<View0,View1>::cost(void) const {
00073     return PC_QUADRATIC_LO;
00074   }
00075 
00076   template <class View0, class View1>
00077   ExecStatus
00078   PartitionN<View0,View1>::propagate(Space* home) {
00079 
00080     ModEvent myMe0 = View0::pme(this);
00081     ModEvent myMe1 = View1::pme(this);
00082     bool ubevent =
00083       (myMe0==ME_SET_LUB || myMe0==ME_SET_BB || myMe0==ME_SET_CLUB ||
00084        myMe0==ME_SET_CBB || myMe0==ME_SET_VAL) ||
00085       (myMe1==ME_SET_LUB || myMe1==ME_SET_BB || myMe1==ME_SET_CLUB ||
00086        myMe1==ME_SET_CBB || myMe1==ME_SET_VAL);
00087 
00088     bool lbevent =
00089       (myMe0==ME_SET_GLB || myMe0==ME_SET_BB || myMe0==ME_SET_CGLB ||
00090        myMe0==ME_SET_CBB || myMe0==ME_SET_VAL) ||
00091       (myMe1==ME_SET_GLB || myMe1==ME_SET_BB || myMe1==ME_SET_CGLB ||
00092        myMe1==ME_SET_CBB || myMe1==ME_SET_VAL);
00093 
00094     bool anybevent =
00095       (myMe0==ME_SET_LUB || myMe0==ME_SET_GLB || myMe0==ME_SET_BB ||
00096        myMe0==ME_SET_CLUB || myMe0==ME_SET_CGLB || myMe0==ME_SET_CBB ||
00097        myMe0==ME_SET_VAL) ||
00098       (myMe1==ME_SET_LUB || myMe1==ME_SET_GLB || myMe1==ME_SET_BB ||
00099        myMe1==ME_SET_CLUB || myMe1==ME_SET_CGLB || myMe1==ME_SET_CBB ||
00100        myMe1==ME_SET_VAL);
00101 
00102     bool cardevent =
00103       (myMe0==ME_SET_CARD || myMe0==ME_SET_CLUB ||
00104        myMe0==ME_SET_CGLB || myMe0==ME_SET_CBB) ||
00105       (myMe1==ME_SET_CARD || myMe1==ME_SET_CLUB ||
00106        myMe1==ME_SET_CGLB || myMe1==ME_SET_CBB);
00107 
00108     bool modified = false;
00109     bool oldModified = false;
00110 
00111     do {
00112       oldModified = modified;
00113       modified = false;
00114       if (modified || anybevent)
00115         GECODE_ME_CHECK(partitionNXiUB(home,modified, x, y,unionOfDets));
00116       if (modified || oldModified || anybevent)
00117         GECODE_ME_CHECK(partitionNXiLB(home,modified, x, y,unionOfDets));
00118       if (modified || oldModified || ubevent)
00119         GECODE_ME_CHECK(partitionNYUB(home,modified, x, y,unionOfDets));
00120       if (modified || oldModified || lbevent)
00121         GECODE_ME_CHECK(partitionNYLB(home,modified, x, y,unionOfDets));
00122       if (modified || oldModified || ubevent)
00123         GECODE_ME_CHECK(unionNXiUB(home,modified, x, y,unionOfDets));
00124       if (modified || oldModified || cardevent)
00125         GECODE_ME_CHECK(partitionNCard(home,modified, x, y,unionOfDets));
00126     } while (modified);
00127 
00128     //removing assigned sets from x, accumulating the value:
00129     for(int i=0;i<x.size();i++){
00130       //Do not reverse! Eats away the end of the array!
00131       while (i<x.size() && x[i].assigned()) {
00132         GlbRanges<View0> det(x[i]);
00133         unionOfDets.includeI(home,det);
00134         x.move_lst(i);
00135       }
00136     }
00137     // When we run out of variables, make a final check and disolve:
00138     if (x.size()==0) {
00139       BndSetRanges all1(unionOfDets);
00140       GECODE_ME_CHECK( y.intersectI(home,all1) );
00141       BndSetRanges all2(unionOfDets);
00142       GECODE_ME_CHECK( y.includeI(home,all2) );
00143       unionOfDets.dispose(home);
00144       return ES_SUBSUMED;
00145     }
00146 
00147     return shared ? ES_NOFIX : ES_FIX;
00148   }
00149 
00150 }}}
00151 
00152 // STATISTICS: set-prop