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

disjoint.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  *  Copyright:
00007  *     Guido Tack, 2004
00008  *     Christian Schulte, 2004
00009  *
00010  *  Last modified:
00011  *     $Date: 2005-11-24 18:03:01 +0100 (Thu, 24 Nov 2005) $ by $Author: tack $
00012  *     $Revision: 2639 $
00013  *
00014  *  This file is part of Gecode, the generic constraint
00015  *  development environment:
00016  *     http://www.gecode.org
00017  *
00018  *  See the file "LICENSE" for information on usage and
00019  *  redistribution of this file, and for a
00020  *     DISCLAIMER OF ALL WARRANTIES.
00021  *
00022  */
00023 
00024 
00025 
00026 #include "set/select.hh"
00027 #include "set/rel.hh"
00028 #include "set/rel-op.hh"
00029 #include "set.hh"
00030 
00031 #include "iter.hh"
00032 
00033 namespace Gecode { namespace Set { namespace Select {
00034 
00035   PropCost
00036   SelectDisjoint::cost(void) const {
00037     return PC_QUADRATIC_LO;
00038   }
00039 
00040   SelectDisjoint::~SelectDisjoint(void) {
00041     x1.cancel(this, PC_SET_ANY);
00042     iv.cancel(this,PC_SET_ANY);
00043   }
00044 
00045   Actor*
00046   SelectDisjoint::copy(Space* home, bool share) {
00047     return new (home) SelectDisjoint(home,share,*this);
00048   }
00049 
00050   ExecStatus
00051   SelectDisjoint::propagate(Space* home) {
00052     int n = iv.size();
00053 
00054     bool fix_flag;
00055     do {
00056       fix_flag=false;
00057 
00058       // Compute union of all selected elements' lower bounds
00059       GlbRanges<SetView> x1lb(x1);
00060       Iter::Ranges::ToValues<GlbRanges<SetView> > vx1lb(x1lb);
00061       GLBndSet unionOfSelected(home);
00062       for(int i=0; vx1lb(); ++vx1lb) {
00063         while (iv[i].idx < vx1lb.val()) i++;
00064         GlbRanges<SetView> clb(iv[i].var);
00065         unionOfSelected.includeI(home,clb);
00066       }
00067 
00068       {
00069         LubRanges<SetView> x1ub(x1);
00070         Iter::Ranges::ToValues<LubRanges<SetView> > vx1ub(x1ub);
00071         int i=0;
00072         int j=0;
00073         // Cancel all elements that are no longer in the upper bound
00074         while (vx1ub()) {
00075           if (iv[i].idx < vx1ub.val()) {
00076             iv[i].var.cancel(this, PC_SET_ANY);
00077             i++;
00078             continue;
00079           }
00080           iv[j] = iv[i];
00081           ++vx1ub;
00082           ++i; ++j;
00083         }
00084 
00085         // cancel the variables with index greater than
00086         // max of lub(x1)
00087         for (int k=i; k<n; k++) {
00088           iv[k].var.cancel(this, PC_SET_ANY);
00089         }
00090         n = j;
00091         iv.size(n);
00092       }
00093 
00094       {
00095       UnknownRanges<SetView> x1u(x1);
00096       Iter::Ranges::Cache<UnknownRanges<SetView> > x1uc(x1u);
00097       Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<SetView> > >
00098         vx1u(x1uc);
00099       int i=0;
00100       int j=0;
00101       while (vx1u()) {
00102         while (iv[i].idx < vx1u.val()) {
00103           iv[j] = iv[i];
00104           i++; j++;
00105         }
00106         assert(iv[i].idx == vx1u.val());
00107 
00108         SetView candidate = iv[i].var;
00109         int candidateInd = iv[i].idx;
00110 
00111         GlbRanges<SetView> clb(candidate);
00112         BndSetRanges uos(unionOfSelected);
00113         Iter::Ranges::Inter<GlbRanges<SetView>, BndSetRanges>
00114           inter(clb, uos);
00115         if (inter()) {
00116           ModEvent me = x1.exclude(home,candidateInd);
00117           fix_flag |= me_modified(me);
00118           GECODE_ME_CHECK(me);
00119 
00120           candidate.cancel(this, PC_SET_ANY);
00121           ++i;
00122           ++vx1u;
00123           continue;
00124         }
00125         iv[j] = iv[i];
00126         ++vx1u;
00127         ++i; ++j;
00128       }
00129 
00130       unionOfSelected.dispose(home);
00131 
00132       // copy remaining variables
00133       for (int k=i; k<n; k++) {
00134         iv[j] = iv[k];
00135         j++;
00136       }
00137       n = j;
00138       iv.size(n);
00139       }
00140 
00141       if (x1.cardMax()==0) {
00142         // Selector is empty, we're done
00143         return ES_SUBSUMED;
00144       }
00145 
00146       {
00147         // remove all elements in a selected variable from
00148         // all other selected variables
00149         GlbRanges<SetView> x1lb(x1);
00150         Iter::Ranges::ToValues<GlbRanges<SetView> > vx1lb(x1lb);
00151         int i=0;
00152         for (; vx1lb(); ++vx1lb) {
00153           while (iv[i].idx < vx1lb.val()) i++;
00154           assert(iv[i].idx==vx1lb.val());
00155           GlbRanges<SetView> x1lb2(x1);
00156           Iter::Ranges::ToValues<GlbRanges<SetView> > vx1lb2(x1lb2);
00157           for (int j=0; vx1lb2(); ++vx1lb2) {
00158             while (iv[j].idx < vx1lb2.val()) j++;
00159             assert(iv[j].idx==vx1lb2.val());
00160             if (iv[i].idx!=iv[j].idx) {
00161               GlbRanges<SetView> xilb(iv[i].var);
00162               ModEvent me = iv[j].var.excludeI(home,xilb);
00163               GECODE_ME_CHECK(me);
00164             }
00165           }
00166         }
00167       }
00168 
00169       // remove all elements from the selector that overlap
00170       // with all other possibly selected elements, if
00171       // at least two more elements need to be selected
00172       if (x1.cardMin()-x1.glbSize() > 1) {
00173         UnknownRanges<SetView> x1u(x1);
00174         Iter::Ranges::Cache<UnknownRanges<SetView> > x1uc(x1u);
00175         Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<SetView> > >
00176           vx1u(x1uc);
00177 
00178         for (; vx1u() && x1.cardMin()-x1.glbSize() > 1; ++vx1u) {
00179           int i = 0;
00180           while (iv[i].idx < vx1u.val()) i++;
00181           assert(iv[i].idx == vx1u.val());
00182           bool flag=true;
00183 
00184           UnknownRanges<SetView> x1u2(x1);
00185           Iter::Ranges::ToValues<UnknownRanges<SetView> > vx1u2(x1u2);
00186           for (; vx1u2(); ++vx1u2) {
00187             int j = 0;
00188             while (iv[j].idx < vx1u2.val()) j++;
00189             assert(iv[j].idx == vx1u2.val());
00190             if (iv[i].idx!=iv[j].idx) {
00191               GlbRanges<SetView> xjlb(iv[j].var);
00192               GlbRanges<SetView> xilb(iv[i].var);
00193               Iter::Ranges::Inter<GlbRanges<SetView>, GlbRanges<SetView> >
00194                 inter(xjlb, xilb);
00195               if (!inter()) {
00196                 flag = false;
00197                 goto here;
00198               }
00199             }
00200           }
00201         here:
00202           if (flag) {
00203             ModEvent me = x1.exclude(home,iv[i].idx);
00204             GECODE_ME_CHECK(me);
00205           }
00206         }
00207       }
00208 
00209       // if exactly two more elements need to be selected
00210       // and there is a possible element i such that all other pairs of
00211       // elements overlap, select i
00212       UnknownRanges<SetView> x1u(x1);
00213       Iter::Ranges::Cache<UnknownRanges<SetView> > x1uc(x1u);
00214       Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<SetView> > >
00215         vx1u(x1uc);
00216 
00217       for (; x1.cardMin()-x1.glbSize() == 2 && vx1u(); ++vx1u) {
00218         int i = 0;
00219         while (iv[i].idx < vx1u.val()) i++;
00220         assert (iv[i].idx == vx1u.val());
00221         bool flag=true;
00222 
00223         UnknownRanges<SetView> x1u2(x1);
00224         Iter::Ranges::ToValues<UnknownRanges<SetView> > vx1u2(x1u2);
00225         for (; vx1u2(); ++vx1u2) {
00226           int j = 0;
00227           while (iv[j].idx < vx1u2.val()) j++;
00228           assert (iv[j].idx == vx1u2.val());
00229           if (iv[i].idx!=iv[j].idx) {
00230             UnknownRanges<SetView> x1u3(x1);
00231             Iter::Ranges::ToValues<UnknownRanges<SetView> > vx1u3(x1u3);
00232             for (; vx1u3(); ++vx1u3) {
00233               int k = 0;
00234               while (iv[k].idx < vx1u3.val()) k++;
00235               assert (iv[k].idx == vx1u3.val());
00236               if (iv[j].idx!=iv[k].idx && iv[i].idx!=iv[k].idx) {
00237                 GlbRanges<SetView> xjlb(iv[j].var);
00238                 GlbRanges<SetView> xilb(iv[k].var);
00239                 Iter::Ranges::Inter<GlbRanges<SetView>, GlbRanges<SetView> >
00240                   inter(xjlb, xilb);
00241                 if (!inter()) {
00242                   flag = false;
00243                   goto here2;
00244                 }
00245               }
00246             }
00247           }
00248         }
00249       here2:
00250         if (flag) {
00251           ModEvent me = x1.include(home,iv[i].idx);
00252           GECODE_ME_CHECK(me);
00253           fix_flag=true;
00254         }
00255       }
00256     } while(fix_flag);
00257 
00258     return ES_FIX;
00259   }
00260 
00261 }}}
00262 
00263 // STATISTICS: set-prop