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

match.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-25 13:22:19 +0100 (Fri, 25 Nov 2005) $ by $Author: tack $
00016  *     $Revision: 2644 $
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 
00029 
00030 #include "set/int.hh"
00031 
00032 #include "iter.hh"
00033 
00034 namespace Gecode { namespace Set { namespace Int {
00035 
00036   PropCost
00037   Match::cost(void) const {
00038     return PC_LINEAR_LO;
00039   }
00040 
00041   Match::~Match(void) {
00042     x0.cancel(this, PC_SET_ANY);
00043     xs.cancel(this, Gecode::Int::PC_INT_BND);
00044   }
00045 
00046   Actor*
00047   Match::copy(Space* home, bool share) {
00048     return new (home) Match(home,share,*this);
00049   }
00050 
00051   ExecStatus
00052   Match::propagate(Space* home) {
00053 
00054     int xs_size = xs.size();
00055 
00056     bool loopFlag;
00057 
00058     do {
00059       loopFlag = false;
00060 
00061       // Order int vars in xs
00062       GECODE_ME_CHECK(xs[0].gq(home,x0.lubMin()));
00063       for (int i=xs_size-1; i--; ) {
00064         GECODE_ME_CHECK(xs[i+1].gq(home,xs[i].min() + 1));
00065       }
00066 
00067       GECODE_ME_CHECK(xs[xs_size-1].lq(home,x0.lubMax()));
00068       for (int i=xs_size-2; i--; ) {
00069         GECODE_ME_CHECK(xs[i].lq(home,xs[i+1].max() - 1));
00070       }
00071 
00072       // if y from xs is assigned, add to glb(x0)
00073       for (int i=xs_size; i--; ) {
00074         if (xs[i].assigned())
00075           GECODE_ME_CHECK(x0.include(home,xs[i].val()));
00076       }
00077 
00078       // intersect every y in xs with lub(x0)
00079       for (int i=xs_size; i--; ) {
00080         LubRanges<SetView> ub(x0);
00081         ModEvent me = xs[i].inter(home,ub);
00082         if (me_modified(me)) {
00083           loopFlag = true;
00084         } else {
00085           GECODE_ME_CHECK(me);
00086         }
00087       }
00088 
00089       // remove gaps between vars in xs from lub(x0)
00090       ModEvent me1 =
00091         x0.exclude(home,Limits::Set::int_min,xs[0].min()-1);
00092       ModEvent me2 =
00093         x0.exclude(home,xs[xs_size-1].max()+1,Limits::Set::int_max);
00094       if (me_modified(me1)) {
00095         loopFlag = true;
00096       } else {
00097         GECODE_ME_CHECK(me1);
00098       }
00099       if (me_modified(me2)) {
00100         loopFlag = true;
00101       } else {
00102         GECODE_ME_CHECK(me2);
00103       }
00104       for (int i=xs_size-1; i--; ) {
00105         int start = xs[i].max() + 1;
00106         int end   = xs[i+1].min() - 1;
00107         if (start<=end) {
00108           ModEvent me = x0.exclude(home,start,end);
00109           if (me_modified(me)) {
00110             loopFlag = true;
00111           } else {
00112             GECODE_ME_CHECK(me);
00113           }
00114         }
00115       }
00116 
00117       // try to assign vars in xs from glb(x0)
00118       if (x0.glbSize()>0) {
00119 
00120         LubRanges<SetView> ub(x0);
00121         Iter::Ranges::ToValues<LubRanges<SetView> > ubv(ub);
00122         GlbRanges<SetView> lb(x0);
00123         Iter::Ranges::ToValues<GlbRanges<SetView> > lbv(lb);
00124 
00125         int i=0;
00126         for (; ubv() && lbv() && ubv.val()==lbv.val();
00127             ++ubv, ++lbv, i++) {
00128           ModEvent me = (xs[i].eq(home,lbv.val()));
00129           if (me_modified(me)) {
00130             loopFlag = true;
00131           } else {
00132             GECODE_ME_CHECK(me);
00133           }
00134         }
00135 
00136         if (i<xs_size-1 && x0.lubMax()==x0.glbMax()) {
00137           LubRanges<SetView> lbx0(x0);
00138           GlbRanges<SetView> ubx0(x0);
00139           Iter::Ranges::Inter<LubRanges<SetView>,GlbRanges<SetView> >
00140             inter(lbx0, ubx0);
00141           
00142           int to = x0.glbMax();
00143           int from = to;
00144           while (inter()) {
00145             from = inter.min();
00146             ++inter;
00147           }
00148 
00149           int i=xs_size-1;
00150           for (int j=to; j>=from;j--,i--) {
00151             ModEvent me = xs[i].eq(home,j);
00152             if (me_modified(me)) {
00153               loopFlag = true;
00154             } else {
00155               GECODE_ME_CHECK(me);
00156             }
00157           }
00158         }
00159       }
00160 
00161     } while (loopFlag);
00162 
00163     for (int i=xs_size; i--; )
00164       if (!xs[i].assigned())    
00165         return ES_FIX;
00166     return ES_SUBSUMED;
00167   }
00168 
00169 }}}
00170 
00171 // STATISTICS: set-prop