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

gcc.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00004  *
00005  *  Copyright:
00006  *     Patrick Pekczynski, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-12-06 07:46:40 +0100 (Tue, 06 Dec 2005) $ by $Author: pekczynski $
00010  *     $Revision: 2696 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */     
00021 
00022 #include "int/gcc.hh"
00023 #include "int/linear.hh"
00024 #include "int/distinct.hh"
00025 
00026 namespace Gecode { namespace Int { namespace GCC {
00027 
00038   template<class Card>
00039   forceinline bool 
00040   check_alldiff(int n, Card& k){
00041     int left     = 0;
00042     int right    = k.size() - 1;
00043     bool alldiff = true;
00044 
00045     if (k.size() == 1) {
00046       return (n == 1 && k[0].min() == 1 && k[0].max() == 1);
00047     }
00048     if (n == k.size()) {
00049       while (left < right) {
00050         alldiff &= (k[left].max()  == 1 && 
00051                     k[left].min()  == 1 &&
00052                     k[right].max() == 1 &&
00053                     k[left].max()  == 1);
00054         if (!alldiff) {
00055           break;
00056         }
00057 
00058         left++;
00059         right--;
00060       }
00061     } else {
00062       if (n < k.size()) {
00063         while (left < right) {
00064           alldiff &= (k[left].max()  == 1 && 
00065                       k[left].min()  == 0 &&
00066                       k[right].max() == 1 &&
00067                       k[left].max()  == 0);
00068           if (!alldiff) {
00069             break;
00070           }
00071           left++;
00072           right--;
00073         }
00074       } else {
00075         return false;
00076       }
00077     }
00078     return alldiff;
00079   }
00080 
00084   template <class View>
00085   forceinline void
00086   x_setidx(ViewArray<View>& x) {
00087     for (int i = x.size(); i--; ) {
00088       x[i].index(i);
00089       x[i].oldindex(i);
00090     }
00091   }
00092 
00097   template <class View>
00098   forceinline int
00099   x_card(ViewArray<View>& x) {
00100 
00101     int n = x.size();
00102 
00103     GECODE_AUTOARRAY(ViewRanges<View>, xrange, n);
00104     for (int i = n; i--; ){
00105       ViewRanges<View> iter(x[i]);
00106       xrange[i] = iter;
00107     }
00108     
00109     Gecode::Iter::Ranges::NaryUnion<ViewRanges<View> > drl(&xrange[0], x.size());
00110     int r = 0;
00111     for ( ; drl(); ++drl){
00112       for (int v = drl.min(); v <=drl.max(); v++) {
00113         r ++;
00114       }
00115     }
00116     return r;
00117   }
00118   
00124   template <class Card, class View>
00125   forceinline void
00126   initcard(Space* home, ViewArray<View>& x, Card& k, int lb, int ub) {
00127     GECODE_AUTOARRAY(ViewRanges<View>, xrange, x.size());
00128     for (int i = x.size(); i--; ){
00129       ViewRanges<View> iter(x[i]);
00130       xrange[i] = iter;
00131     }
00132     
00133     Iter::Ranges::NaryUnion<ViewRanges<View> > drl(&xrange[0], x.size());
00134     int idx = 0;
00135     for ( ; drl(); ++drl){
00136       for (int v = drl.min(); v <= drl.max(); v++){
00137         k[idx].init(home, lb, ub, v);
00138         idx++;
00139       }
00140     }
00141   }
00142 
00148   template <class Card, class View, bool isView>
00149   forceinline void
00150   setcard(Space* home, ViewArray<View>& x, Card& k, int xmin, int xmax) {
00151 
00152     int idx = 0;
00153     for (int v = xmin; v <= xmax; v++) {
00154       k[idx].card(v);
00155       k[idx].counter(0);
00156       idx++;
00157     }
00158     
00159     bool assigned = true;
00160     for (int i = x.size(); i--; ) {
00161       assigned &= x[i].assigned();
00162     }
00163 
00164     if (assigned) {
00165       // check validity
00166       int size = xmax - (xmin - 1);
00167       GECODE_AUTOARRAY(int, count, size);
00168       for (int i = size; i--; ) {
00169         count[i] = 0;
00170       }
00171       for (int i = x.size(); i--; ) {
00172         count[x[i].val() - xmin]++;
00173       }
00174       for (int i = k.size(); i--; ) {
00175         if (k[i].min() > count[i]) {
00176           home->fail();
00177         }
00178       }
00179     }
00180   }
00181 
00182 
00190   template<class Card, bool isView>
00191   forceinline ExecStatus
00192   card_cons(Space* home, Card& k, int n) {
00193     for (int i = k.size(); i--; ) {
00194       if (k[i].min() > n) {
00195         return ES_FAILED;
00196       }
00197       ModEvent me = k[i].lq(home, n);
00198       if (me_failed(me)) {
00199         return ES_FAILED;
00200       }
00201     }
00202     return ES_OK;
00203   }
00204 
00210   template<class View, class Card, bool isView>
00211   forceinline void
00212   post_template(Space* home, ViewArray<View>& x, Card& k, IntConLevel& icl){ 
00213 
00214     int  n        = x_card(x);
00215     bool rewrite  = false; 
00216     if (!isView) {
00217      rewrite = check_alldiff(n, k);
00218     }
00219 
00220     GECODE_ES_FAIL(home, (card_cons<Card, isView>(home, k, x.size())));
00221 
00222     if (!isView && rewrite) {
00223       switch (icl) {
00224       case ICL_BND:
00225         GECODE_ES_FAIL(home,Distinct::Bnd<View>::post(home, x));
00226         break;
00227       case ICL_DOM:
00228         GECODE_ES_FAIL(home,Distinct::Dom<View>::post(home, x));
00229         break;
00230       default:
00231         GECODE_ES_FAIL(home,Distinct::Val<View>::post(home, x));
00232       }
00233     } else {
00234       switch (icl) {
00235       case ICL_BND:
00236       GECODE_ES_FAIL(home, (GCC::Bnd<View, Card, isView>::post(home, x, k)));
00237       break;
00238       case ICL_DOM:
00239         GECODE_ES_FAIL(home, (GCC::Dom<View, Card, isView>::post(home, x, k)));
00240         break;
00241       default:
00242         GECODE_ES_FAIL(home, (GCC::Val<View, Card, isView>::post(home, x, k)));
00243       }
00244     }
00245   }
00246   
00247 }}
00248 
00249   using namespace Int;
00250   using namespace Support;
00251 
00252 
00253   // Interfacing gcc with fixed cardinalities
00254   void gcc(Space* home, const IntVarArgs& x, const IntArgs& c, 
00255            int m, int unspec_low, int unspec_up, int min, int max,
00256            IntConLevel icl) {
00257 
00258     if (home->failed()) {
00259       return;
00260     }
00261     
00262     GccIdxView xv(home, x);
00263 
00264     x_setidx(xv);
00265 
00266     FixCard cv(c, xv, m, (m / 3), (max - (min - 1)), 
00267                min, max, unspec_low, unspec_up);
00268 
00269     // compute number of zero entries
00270     int z = 0;
00271     for (int j = cv.size(); j--; ){
00272       if (cv[j].max() == 0){
00273         z++;
00274       }
00275     }
00276 
00277     // if there are zero entries
00278     if (z > 0) {
00279 
00280       // reduce the occurences 
00281       FixCard red(cv.size() - z);
00282       IntArgs rem(z);
00283       z = 0;
00284       int c = 0;
00285       int r = red.size() - 1;
00286       for (int j = cv.size(); j--;) {
00287         if (cv[j].max() == 0){
00288           rem[z] = cv[j].card();
00289           z++;
00290         } else {
00291           red[r]= cv[j];
00292           r--;
00293         }
00294         c++;
00295       }
00296       
00297       IntSet zero(&rem[0], z);
00298       IntSetRanges remzero(zero);
00299       int n = xv.size();
00300       for (int i = n; i--; ) {
00301         GECODE_ME_FAIL(home, xv[i].minus(home, remzero));
00302       }
00303       GCC::post_template<GCC::IdxView, FixCard, false>(home, xv, red, icl);
00304     } else { 
00305       GCC::post_template<GCC::IdxView, FixCard, false>(home, xv, cv, icl);
00306     }
00307   }
00308 
00309   void gcc(Space* home, const IntVarArgs& x, const IntArgs& c, 
00310            int m, int unspec, int min, int max, 
00311            IntConLevel icl) {
00312     gcc(home, x, c, m, 0, unspec, min, max, icl);
00313   }
00314 
00315   void gcc(Space* home, const IntVarArgs& x, int lb, int ub,
00316            IntConLevel icl) {
00317     if (home->failed()) {
00318       return;
00319     }
00320    
00321     GccIdxView xv(home,x);
00322     x_setidx(xv);
00323 
00324     int values = x_card(xv);
00325     FixCard c(home, values);
00326     GCC::initcard(home, xv, c, lb, ub);
00327     GCC::post_template<GCC::IdxView, FixCard, false>(home, xv, c, icl);
00328   }
00329 
00330   // Interfacing gcc with cardinality variables
00331 
00332   void gcc(Space* home, const IntVarArgs& x, int ub, IntConLevel icl) {
00333     gcc(home, x, ub, ub, icl);
00334   }
00335 
00336   void gcc(Space* home, const IntVarArgs& x, const IntVarArgs& c, 
00337            int min, int max, IntConLevel icl) {
00338     
00339     if (home->failed()) {
00340       return;
00341     }
00342 
00343     GccIdxView xv(home, x);
00344     x_setidx(xv);
00345 
00346     linear(home, c, IRT_EQ, xv.size());
00347 
00348     VarCard cv(home, c);
00349 
00350     int interval = max - (min - 1);
00351 
00352     GECODE_AUTOARRAY(bool, done, interval);
00353     for (int i = 0; i < interval; i++) {
00354       done[i] = false;
00355     }
00356 
00357     GECODE_AUTOARRAY(ViewRanges<Gecode::Int::GCC::IdxView>, xrange, xv.size());
00358     for (int i = xv.size(); i--; ){
00359       ViewRanges<Gecode::Int::GCC::IdxView> iter(xv[i]);
00360       xrange[i] = iter;
00361     }
00362 
00363     Gecode::Iter::Ranges::NaryUnion<ViewRanges<Gecode::Int::GCC::IdxView> >     
00364       drl(&xrange[0], xv.size());
00365     Gecode::Iter::Ranges::Cache<
00366       Gecode::Iter::Ranges::
00367       NaryUnion<ViewRanges<Gecode::Int::GCC::IdxView> > > crl(drl);
00368     for ( ; crl(); ++crl) {
00369       for (int v = crl.min(); v <= crl.max(); v++) {
00370         done[v - min] = true;
00371       }
00372     }
00373 
00374     for (int i = 0; i < interval; i++) {
00375       if (!done[i]) {
00376         GECODE_ME_FAIL(home, cv[i].eq(home, 0));
00377       }
00378     }
00379 
00380     GCC::setcard<VarCard, Gecode::Int::GCC::IdxView, true>
00381       (home, xv, cv, min, max);
00382 
00383     GCC::post_template<GCC::IdxView, VarCard, true>(home, xv, cv, icl);
00384   }
00385 
00386   void gcc(Space* home, const IntVarArgs& x, const IntArgs& v, 
00387            const IntVarArgs& c,int m, int unspec, bool all, 
00388            int xmin, int xmax, IntConLevel icl) {
00389     gcc(home, x, v, c, m, 0, unspec, all, xmin, xmax, icl);
00390   }
00391 
00392   void gcc(Space* home, const IntVarArgs& x, const IntArgs& v, 
00393            const IntVarArgs& c,int m, 
00394            int unspec_low, int unspec_up, bool all, 
00395            int xmin, int xmax, IntConLevel icl) {
00396     
00397     if (m != c.size()) {
00398       throw ArgumentSizeMismatch("Int::gcc");
00399     }
00400     if (home->failed()) {
00401       return;
00402     }
00403 
00404     GccIdxView xv(home, x);
00405     x_setidx(xv);
00406 
00407     int interval = xmax - (xmin - 1);
00408 
00409     GECODE_AUTOARRAY(bool, done, interval);
00410     for (int i = 0; i < interval; i++) {
00411       done[i] = false;
00412     }
00413 
00414     GECODE_AUTOARRAY(ViewRanges<Gecode::Int::GCC::IdxView>, xrange, xv.size());
00415     for (int i = xv.size(); i--; ){
00416       ViewRanges<Gecode::Int::GCC::IdxView> iter(xv[i]);
00417       xrange[i] = iter;
00418     }
00419 
00420     Gecode::Iter::Ranges::NaryUnion<ViewRanges<Gecode::Int::GCC::IdxView> >     
00421       drl(&xrange[0], xv.size());
00422     Gecode::Iter::Ranges::Cache<
00423       Gecode::Iter::Ranges::
00424       NaryUnion<ViewRanges<Gecode::Int::GCC::IdxView> > > crl(drl);
00425     for ( ; crl(); ++crl) {
00426       for (int v = crl.min(); v <= crl.max(); v++) {
00427         done[v - xmin] = true;
00428       }
00429     }
00430 
00431     if (all) {
00432       for (int i = 0; i < interval; i++) {
00433         done[i] = true;
00434       }
00435     }
00436 
00437     // iterating over cardinality variables
00438     int ci  = 0;  
00439     // iterating over the new cardvars
00440     int cvi = 0;  
00441     IntVarArgs cv(interval);
00442     for (int i = xmin; i <= xmax; i++) {
00443       // value in var domain
00444       if (done[i - xmin]) {
00445         if (ci < m) {
00446           // specified wih cardinalities
00447           if (i == v[ci]) {
00448             cv[cvi] = c[ci];
00449             ci++;
00450             cvi++;
00451           } else {
00452             // value in domain but unspecified
00453             IntVar iv(home, unspec_low, unspec_up);
00454             cv[cvi] = iv; 
00455             cvi++;
00456           }
00457         } else {
00458           // in domain but after the specification
00459           IntVar iv(home, unspec_low, unspec_up);
00460           cv[cvi] = iv; 
00461           cvi++;
00462         }
00463       } else {
00464         // not in the variable domain of the current assignment
00465         if (ci < m) {
00466           // but is specified
00467           if (i == v[ci]) {
00468             cv[cvi] = c[ci];
00469             ci++;
00470             cvi++;
00471           } else {
00472             // unspecified and not in x
00473             IntVar iv(home, unspec_low, unspec_up);
00474             cv[cvi] = iv; 
00475             cvi++;
00476           }
00477         } else {
00478           // more values than specified
00479           IntVar iv(home, unspec_low, unspec_up);
00480           cv[cvi] = iv; 
00481           cvi++;
00482         }
00483       }
00484     }
00485 
00486     if (ci < m) {
00487       // still values left
00488       for (; ci < m; ci++) {
00489         cv[cvi] = c[ci];
00490         ci++;
00491         cvi++;
00492       }
00493     }
00494 
00495     linear(home, c, IRT_LQ, xv.size());
00496     VarCard cardv(home, cv);
00497 
00498     GCC::setcard<VarCard, Gecode::Int::GCC::IdxView, true>
00499       (home, xv, cardv, xmin, xmax);
00500     GCC::post_template<GCC::IdxView, VarCard, true>(home, xv, cardv, icl);
00501   }
00502 }
00503 
00504 
00505 // STATISTICS: int-post
00506