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

seq-u.cc

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-24 18:03:01 +0100 (Thu, 24 Nov 2005) $ by $Author: tack $
00016  *     $Revision: 2639 $
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 #include "set.hh"
00029 #include "set/sequence.hh"
00030 
00031 namespace Gecode { namespace Set { namespace Sequence {
00032 
00033   /*
00034    * "Sequenced union" propagator
00035    *
00036    */
00037 
00038   Actor*
00039   SeqU::copy(Space* home, bool share) {
00040     return new (home) SeqU(home,share,*this);
00041   }
00042 
00043   //Enforces sequentiality and ensures y contains union of Xi lower bounds.
00044   ExecStatus
00045   SeqU::propagate(Space* home) {
00046     /*
00047 CHECK THIS
00048     bool ubevent = GECODE_VME2ME(VTI_SET, varmodevent()) &
00049       (ME_SET_LUB | ME_SET_BB | ME_SET_CLUB | ME_SET_CBB | ME_SET_VAL);
00050     bool lbevent = GECODE_VME2ME(VTI_SET, varmodevent()) &
00051       (ME_SET_GLB | ME_SET_BB | ME_SET_CGLB | ME_SET_CBB | ME_SET_VAL);
00052     bool anybevent = GECODE_VME2ME(VTI_SET, varmodevent()) &
00053       (ME_SET_LUB | ME_SET_GLB | ME_SET_BB |
00054        ME_SET_CLUB | ME_SET_CGLB | ME_SET_CBB | ME_SET_VAL);
00055     bool cardevent = GECODE_VME2ME(VTI_SET, varmodevent()) &
00056       (ME_SET_CARD | ME_SET_CLUB | ME_SET_CGLB | ME_SET_CBB);
00057     */
00058 
00059     bool ubevent = true;
00060     bool lbevent = true;
00061     bool anybevent = true;
00062     bool cardevent = true;
00063 
00064 
00065     bool modified=false;
00066     bool oldModified;
00067     do {
00068       oldModified = modified;
00069       modified = false;
00070       if (oldModified || lbevent)
00071         GECODE_ME_CHECK(propagateSeq(home,modified,x));
00072       if (oldModified || lbevent)
00073         GECODE_ME_CHECK(propagateSeqUnion(home,modified,x,y));
00074       if (oldModified || modified || ubevent)
00075         GECODE_ME_CHECK(RelOp::unionNXiUB(home,modified,x,y,unionOfDets));
00076       if (oldModified || modified || ubevent)
00077         GECODE_ME_CHECK(RelOp::partitionNYUB(home,modified,x,y,unionOfDets));
00078       if (oldModified || modified || anybevent)
00079         GECODE_ME_CHECK(RelOp::partitionNXiLB(home,modified,x,y,unionOfDets));
00080       if (oldModified || modified || cardevent)
00081         GECODE_ME_CHECK(RelOp::partitionNCard(home,modified,x,y,unionOfDets));
00082     } while (modified);
00083 
00084     //TODO: We might be able to detect VAL events and disperse this
00085     //functionality:
00086     //removing ground sets from x, accumulating the value:
00087     int xsize = x.size();
00088     int j=0;
00089     for (int i=0;i<xsize;i++){
00090       x[j] = x[i];
00091       if (x[j].assigned()) {
00092         GlbRanges<SetView> det(x[j]);
00093         unionOfDets.includeI(home,det);
00094         BndSetRanges dets(unionOfDets);
00095         GECODE_ME_CHECK( y.includeI(home,dets) );
00096       } else {
00097         j++;
00098       }
00099     }
00100     x.size(j);
00101 
00102     // When we run out of variables, make a final check and disolve:
00103     if (x.size()==0) {
00104       BndSetRanges all1(unionOfDets);
00105       GECODE_ME_CHECK( y.intersectI(home,all1) );
00106       BndSetRanges all2(unionOfDets);
00107       GECODE_ME_CHECK( y.includeI(home,all2) );
00108       unionOfDets.dispose(home);
00109       return ES_SUBSUMED;
00110     }
00111 
00112     return ES_FIX;
00113   }
00114 
00115 }}}
00116 
00117 // STATISTICS: set-prop