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

val.icc

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, 2005
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 namespace Gecode { namespace Int { namespace GCC {
00022   
00023   template <class View, class Card, bool isView>
00024   forceinline ExecStatus
00025   prop_val(Space* home, ViewArray<View>& x, Card& k){
00026 
00027     bool mod = false;
00028     int  n   = x.size();
00029     int  m   = k.size();
00030 
00031     // count[i] denotes how often value k[i].card() occurs in x
00032     GECODE_AUTOARRAY(int,  count, m); 
00033     // stack of values having reached their maximum occurence
00034     GECODE_AUTOARRAY(int,  rem,   m); 
00035     // keep track whether a value is already on the stack
00036     GECODE_AUTOARRAY(bool, onrem, m); 
00037     // stacksize
00038     int rs = 0;
00039 
00040 
00041     // initialization
00042     int sum_min = 0;
00043     int removed = 0;
00044     for (int i = m; i--; ) {
00045 
00046       removed += k[i].counter();
00047       sum_min += k[i].min();
00048 
00049       count[i] = 0;
00050       onrem[i] = false;
00051 
00052     }
00053 
00054     for (int i = m; i--; ) {
00055       // less or equal than the total number of free variables 
00056       // to satisfy the required occurences
00057       if (!k[i].assigned()) {
00058         int mub     = n + removed - (sum_min - k[i].min());
00059         ModEvent me = k[i].lq(home, mub);
00060         GECODE_ME_CHECK(me);
00061         if (me_modified(me) && k[i].max() != mub) {
00062           mod |= ES_NOFIX;
00063         }
00064       }
00065     }
00066 
00067     
00068     // Due to lookup operation counting requires O(n \cdot log(n)) time
00069     bool all_assigned = true;
00070     // number of assigned views with respect to the current problem size
00071     int  noa   = 0;            
00072     // total number of assigned views wrt. the original probem size
00073     int  t_noa = 0;            
00074     for (int i = n; i--; ) {
00075       bool b = x[i].assigned();
00076       all_assigned &= b;
00077       if (b) {
00078         int idx = k.lookup(x[i].val());
00079         if (idx == -1) {
00080           return ES_FAILED;
00081         }
00082         count[idx]++;
00083         noa++;
00084       }
00085     }
00086     
00087     // number of unassigned views 
00088     int  non = x.size() - noa; 
00089 
00090     // check for subsumption
00091     if (all_assigned) {
00092 
00093       for (int i = m; i--; ) {
00094         int ci = count[i] + k[i].counter();
00095         if (!(k[i].min() <= ci && ci <= k[i].max())) {
00096           return ES_FAILED;
00097         }
00098         // the solution contains ci occurences of value k[i].card();
00099         if (isView) {
00100           ModEvent me = k[i].eq(home, ci);
00101           GECODE_ME_CHECK(me);
00102           mod |= k[i].assigned();
00103         }
00104       }
00105       return ES_SUBSUMED;
00106     }
00107 
00108     // total number of unsatisfied miminum occurences 
00109     int req = 0;    
00110 
00111     // number of values whose min requirements are not yet met
00112     int n_r = 0;    
00113 
00114     // if only one value is unsatisified single holds the index of that value
00115     int single = 0; 
00116 
00117     for (int i = m; i--; ) {
00118       int ci = count[i] + k[i].counter();
00119       t_noa += ci;
00120       if (ci == 0) {
00121         req += k[i].min();
00122         n_r++;
00123         single = i;
00124       }
00125 
00126       // number of unassigned views cannot satisfy 
00127       // the required minimum occurence
00128       if (req > non) {
00129         return ES_FAILED;
00130       }
00131     }
00132     
00133     // if only one unsatisfied occurences is left
00134     if (req == non && n_r == 1) {
00135       for (int i = n; i--; ) {
00136         // try to assign it
00137         if (!x[i].assigned()) {
00138           ModEvent me = x[i].eq(home, k[single].card());
00139           count[single]++;
00140           GECODE_ME_CHECK(me);
00141         }
00142       }
00143 
00144       for (int i = m; i--; ) {
00145         int ci = count[i] + k[i].counter();
00146         // consistency check
00147         if (!(k[i].min() <= ci && ci <= k[i].max())) {
00148           return ES_FAILED;
00149         }
00150         // the solution contains ci occurences of value k[i].card();
00151         if (isView) {
00152           ModEvent me = k[i].eq(home, ci);
00153           GECODE_ME_CHECK(me);
00154         }
00155       }
00156       return ES_SUBSUMED;
00157     }
00158     
00159     for (int i = m; i--; ) {
00160       int ci = count[i] + k[i].counter();
00161       if (ci == k[i].max() && !onrem[i]) {
00162         rem[rs] = k[i].card();
00163         k[i].counter(ci);
00164         rs++;
00165         onrem[i] = true;
00166         if (isView) {
00167           // the solution contains ci occurences of value k[i].card();
00168           ModEvent me = k[i].eq(home, ci);
00169           GECODE_ME_CHECK(me);
00170           mod |= k[i].assigned();
00171         }
00172       } else {
00173         if (ci > k[i].max()) {
00174           return ES_FAILED;
00175         }
00176 
00177         // in case of variable cardinalities
00178         if (isView) {
00179           if (ci > k[i].min()) {
00180             ModEvent me = k[i].gq(home, ci);
00181             GECODE_ME_CHECK(me);
00182             if (me_modified(me) && k[i].min() != ci) {
00183               mod |= ES_NOFIX;
00184             }
00185             mod |= k[i].assigned();
00186           }
00187           int occupied = t_noa - ci;
00188           int mub = x.size() + removed - occupied;
00189           ModEvent me = k[i].lq(home, mub);
00190           GECODE_ME_CHECK(me);
00191           if (me_failed(me) && k[i].max() != mub) {
00192             mod |= ES_NOFIX;
00193           }
00194           mod |= k[i].assigned();
00195         }
00196       }
00197     }
00198 
00199     // reduce the problem size
00200     for (int i = n; i--; ) {
00201       bool b = x[i].assigned();
00202       if (b) {
00203         int idx = k.lookup(x[i].val());
00204         if (idx == -1) {
00205           return ES_FAILED;
00206         }
00207         if (onrem[idx]) {
00208           x.move_lst(i);
00209         }
00210       }
00211     }
00212 
00213     // remove alredy satisfied values
00214     if (rs > 0) {
00215       IntSet remset(&rem[0], rs);
00216       IntSetRanges rr(remset);
00217       for (int i = x.size(); i--;) {
00218         if (!x[i].assigned()) {
00219           ModEvent me = x[i].minus(home, rr);
00220           if (me_failed(me)) {
00221             return ES_FAILED;
00222           }
00223           mod |= x[i].assigned();
00224         }
00225       }
00226     }
00227 
00228     
00229     // get min and max
00230     int cmin = x[x.size() - 1].min();
00231     int cmax = x[x.size() - 1].max();
00232     
00233     for (int i = x.size() - 1; i--; ) {
00234       if (x[i].min() < cmin) {
00235         cmin = x[i].min();
00236       }
00237       if (x[i].max() > cmax) {
00238         cmax = x[i].max();
00239       }
00240     }
00241 
00242     all_assigned = true;
00243 
00244     for (int i = m; i--; ) {
00245       count[i] = 0;
00246     }
00247 
00248     for (int i = x.size(); i--; ) {
00249       bool b = x[i].assigned();
00250       all_assigned &= b;
00251       if (b) {
00252         int idx = k.lookup(x[i].val());
00253         if (idx == -1) {
00254           return ES_FAILED;
00255         }
00256         count[idx]++;
00257       }
00258     }
00259 
00260     if (all_assigned) {
00261       for (int i = k.size(); i--; ) {
00262         int ci = count[i] + k[i].counter();
00263         if (!(k[i].min() <= ci && ci <= k[i].max())) {
00264           return ES_FAILED;
00265         }
00266         // the solution contains ci occurences of value k[i].card();
00267         if (isView) {
00268           ModEvent me = k[i].eq(home, ci);
00269           GECODE_ME_CHECK(me);
00270           mod |= k[i].assigned();
00271         }
00272       }
00273       return ES_SUBSUMED;
00274     } 
00275 
00276     return mod ? ES_NOFIX : ES_FIX;
00277   }
00278 
00279   /*
00280    * The propagator proper
00281    *
00282    */
00283 
00284   template <class View, class Card, bool isView>
00285   forceinline
00286   Val<View, Card, isView>::Val(Space* home, ViewArray<View>& x0, Card& k0)
00287     :Propagator(home, true), x(x0), k(k0){
00288     x.subscribe(home, this, PC_INT_VAL);
00289     k.subscribe(home, this, PC_INT_VAL);
00290   }
00291 
00292   template <class View, class Card, bool isView>
00293   forceinline
00294   Val<View, Card, isView>::Val(Space* home, bool share, 
00295                                Val<View, VarCard, isView>& p)
00296     : Propagator(home,share,p){
00297     x.update(home,share, p.x);
00298     k.update(home,share, p.k);
00299   }
00300 
00301   template <class View, class Card, bool isView>
00302   forceinline
00303   Val<View, Card, isView>::Val(Space* home, bool share, 
00304                                Val<View, FixCard, isView>& p)
00305     : Propagator(home,share,p), k(p.k.size()){
00306     x.update(home,share, p.x);
00307     k.update(home,share, p.k);
00308   }
00309 
00310   template <class View, class Card, bool isView>
00311   Val<View, Card, isView>::~Val(void){
00312     x.cancel(this, PC_INT_VAL);
00313     k.cancel(this, PC_INT_VAL);
00314   }
00315 
00316   template <class View, class Card, bool isView>
00317   Actor*
00318   Val<View, Card, isView>::copy(Space* home, bool share) {
00319     return new (home) Val<View, Card, isView>(home,share,*this);
00320   }
00321 
00322   template <class View, class Card, bool isView>
00323   ExecStatus Val<View, Card, isView>::post(Space* home, 
00324                                            ViewArray<View>& x0,
00325                                            Card& k0) {
00326     new (home) Val<View, Card, isView>(home, x0, k0);
00327     return ES_OK;
00328   }
00329 
00335   template <class View, class Card, bool isView>
00336   forceinline PropCost    
00337   Val<View, Card, isView>::cost (void) const {
00338     return PC_LINEAR_HI; 
00339   }
00340 
00341   template <class View, class Card, bool isView>
00342   forceinline ExecStatus 
00343   Val<View, Card, isView>::propagate(Space* home) {
00344     assert(x.size() > 0);
00345 
00346     int max = x[0].max();
00347     for (int i = 1; i < x.size(); i++) {
00348       if (x[i].max() > max) {
00349         max = x[i].max();
00350       }
00351     }
00352 
00353     for (int i = 0; i < k.size(); i++) {
00354       if (k[i].card() > max && 
00355           k[i].min() > 0 &&
00356           k[i].max() != k[i].counter() ){
00357         return ES_FAILED;
00358       }
00359     }
00360     ExecStatus es = prop_val<View, Card, isView>(home, x, k);
00361     return es;
00362   }
00363 
00364 }}}
00365 
00366 // STATISTICS: int-prop
00367