Generated on Tue May 22 09:39:45 2018 for Gecode by doxygen 1.6.3

val.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00005  *
00006  *  Contributing authors:
00007  *     Christian Schulte <schulte@gecode.org>
00008  *     Guido Tack <tack@gecode.org>
00009  *
00010  *  Copyright:
00011  *     Patrick Pekczynski, 2005
00012  *     Christian Schulte, 2009
00013  *     Guido Tack, 2009
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  */
00038 
00039 namespace Gecode { namespace Int { namespace GCC {
00040 
00041   template<class Card>
00042   forceinline
00043   Val<Card>::Val(Home home,
00044                  ViewArray<IntView>& x0, ViewArray<Card>& k0)
00045     : Propagator(home), x(x0), k(k0){
00046     x.subscribe(home, *this, PC_INT_VAL);
00047     k.subscribe(home, *this, PC_INT_VAL);
00048   }
00049 
00050   template<class Card>
00051   forceinline
00052   Val<Card>::Val(Space& home, Val<Card>& p)
00053     : Propagator(home,p) {
00054     x.update(home, p.x);
00055     k.update(home, p.k);
00056   }
00057 
00058   template<class Card>
00059   forceinline size_t
00060   Val<Card>::dispose(Space& home) {
00061     x.cancel(home,*this, PC_INT_VAL);
00062     k.cancel(home,*this, PC_INT_VAL);
00063     (void) Propagator::dispose(home);
00064     return sizeof(*this);
00065   }
00066 
00067   template<class Card>
00068   Actor*
00069   Val<Card>::copy(Space& home) {
00070     return new (home) Val<Card>(home,*this);
00071   }
00072 
00073   template<class Card>
00074   PropCost
00075   Val<Card>::cost(const Space&, const ModEventDelta&) const {
00076     /*
00077      * Complexity depends on the time needed for value lookup in \a k
00078      * which is O(n log n).
00079      */
00080     return PropCost::linear(PropCost::HI,x.size());
00081   }
00082 
00083   template<class Card>
00084   void
00085   Val<Card>::reschedule(Space& home) {
00086     x.reschedule(home, *this, PC_INT_VAL);
00087     k.reschedule(home, *this, PC_INT_VAL);
00088   }
00089 
00090   template<class Card>
00091   ExecStatus
00092   prop_val(Space& home, Propagator& p,
00093            ViewArray<IntView>& x, ViewArray<Card>& k) {
00094     assert(x.size() > 0);
00095 
00096     Region r;
00097     // count[i] denotes how often value k[i].card() occurs in x
00098     int* count = r.alloc<int>(k.size());
00099 
00100     // initialization
00101     int sum_min = 0;
00102     int removed = 0;
00103     for (int i = k.size(); i--; ) {
00104       removed += k[i].counter();
00105       sum_min += k[i].min();
00106       count[i] = 0;
00107     }
00108 
00109     // less than or equal than the total number of free variables
00110     // to satisfy the required occurences
00111     for (int i = k.size(); i--; )
00112       GECODE_ME_CHECK(k[i].lq(home, x.size()+removed-(sum_min - k[i].min())));
00113 
00114     // number of unassigned views
00115     int non = x.size();
00116 
00117     for (int i = x.size(); i--; )
00118       if (x[i].assigned()) {
00119         int idx;
00120         if (!lookupValue(k,x[i].val(),idx)) {
00121           return ES_FAILED;
00122         }
00123         count[idx]++;
00124         non--;
00125       }
00126 
00127     // check for subsumption
00128     if (non == 0) {
00129       for (int i = k.size(); i--; )
00130         GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
00131       return home.ES_SUBSUMED(p);
00132     }
00133 
00134     // total number of unsatisfied miminum occurences
00135     int req = 0;
00136     // number of values whose min requirements are not yet met
00137     int n_r = 0;
00138     // if only one value is unsatisified single holds the index of that value
00139     int single = -1;
00140     // total number of assigned views wrt. the original probem size
00141     int t_noa = 0;
00142 
00143     for (int i = k.size(); i--; ) {
00144       int ci = count[i] + k[i].counter();
00145       t_noa += ci;
00146       if (ci == 0) { // this works
00147         req += k[i].min();
00148         n_r++;
00149         single = i;
00150       }
00151 
00152       // number of unassigned views cannot satisfy
00153       // the required minimum occurence
00154       if (req > non) {
00155         return ES_FAILED;
00156       }
00157     }
00158 
00159     // if only one unsatisfied occurences is left
00160     if ((req == non) && (n_r == 1)) {
00161       // This works as the x are not shared!
00162       for (int i = x.size(); i--; ) {
00163         // try to assign it
00164         if (!x[i].assigned()) {
00165           GECODE_ME_CHECK(x[i].eq(home, k[single].card()));
00166           assert((single >= 0) && (single < k.size()));
00167           count[single]++;
00168         }
00169       }
00170       assert((single >= 0) && (single < k.size()));
00171 
00172       for (int i = k.size(); i--; )
00173         GECODE_ME_CHECK(k[i].eq(home, count[i] + k[i].counter()));
00174       return home.ES_SUBSUMED(p);
00175     }
00176 
00177     // Bitset for indexes that can be removed
00178     Support::BitSet<Region> rem(r,static_cast<unsigned int>(k.size()));
00179 
00180     for (int i = k.size(); i--; ) {
00181       int ci = count[i] + k[i].counter();
00182       if (ci == k[i].max()) {
00183         assert(!rem.get(i));
00184         rem.set(static_cast<unsigned int>(i));
00185         k[i].counter(ci);
00186         // the solution contains ci occurences of value k[i].card();
00187         GECODE_ME_CHECK(k[i].eq(home, ci));
00188       } else {
00189         if (ci > k[i].max()) {
00190           return ES_FAILED;
00191         }
00192 
00193         // in case of variable cardinalities
00194         if (Card::propagate) {
00195           GECODE_ME_CHECK(k[i].gq(home, ci));
00196           int occupied = t_noa - ci;
00197           GECODE_ME_CHECK(k[i].lq(home, x.size() + removed - occupied));
00198         }
00199       }
00200       // reset counter
00201       count[i] = 0;
00202     }
00203 
00204     // reduce the problem size
00205     {
00206       int n_x = x.size();
00207       for (int i = n_x; i--; ) {
00208         if (x[i].assigned()) {
00209           int idx;
00210           if (!lookupValue(k,x[i].val(),idx)) {
00211             return ES_FAILED;
00212           }
00213           if (rem.get(static_cast<unsigned int>(idx)))
00214             x[i]=x[--n_x];
00215         }
00216       }
00217       x.size(n_x);
00218     }
00219 
00220     // remove values
00221     {
00222       // Values to prune
00223       int* pr = r.alloc<int>(k.size());
00224       // Number of values to prune
00225       int n_pr = 0;
00226       for (Iter::Values::BitSet<Support::BitSet<Region> > i(rem); i(); ++i)
00227         pr[n_pr++] = k[i.val()].card();
00228       Support::quicksort(pr,n_pr);
00229       for (int i = x.size(); i--;) {
00230         Iter::Values::Array pi(pr,n_pr);
00231         GECODE_ME_CHECK(x[i].minus_v(home, pi, false));
00232       }
00233     }
00234 
00235     {
00236       bool all_assigned = true;
00237 
00238       for (int i = x.size(); i--; ) {
00239         if (x[i].assigned()) {
00240           int idx;
00241           if (!lookupValue(k,x[i].val(),idx)) {
00242             return ES_FAILED;
00243           }
00244           count[idx]++;
00245         } else {
00246           all_assigned = false;
00247         }
00248       }
00249 
00250       if (all_assigned) {
00251         for (int i = k.size(); i--; )
00252           GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
00253         return home.ES_SUBSUMED(p);
00254       }
00255     }
00256 
00257     if (Card::propagate) {
00258       // check again consistency of cardinalities
00259       int reqmin = 0;
00260       int allmax = 0;
00261       for (int i = k.size(); i--; ) {
00262         if (k[i].counter() > k[i].max()) {
00263           return ES_FAILED;
00264         }
00265         allmax += k[i].max() - k[i].counter();
00266         if (k[i].counter() < k[i].min())
00267           reqmin += k[i].min() - k[i].counter();
00268         GECODE_ME_CHECK((k[i].lq(home, x.size()+k[i].counter())));
00269       }
00270 
00271       if ((x.size() < reqmin) || (allmax < x.size())) {
00272         return ES_FAILED;
00273       }
00274     }
00275 
00276     return ES_NOFIX;
00277   }
00278 
00279   template<class Card>
00280   ExecStatus
00281   Val<Card>::propagate(Space& home, const ModEventDelta&) {
00282     return prop_val<Card>(home, *this, x, k);
00283   }
00284 
00285   template<class Card>
00286   ExecStatus
00287   Val<Card>::post(Home home,
00288                   ViewArray<IntView>& x, ViewArray<Card>& k) {
00289     GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
00290 
00291     if (isDistinct<Card>(x,k))
00292       return Distinct::Val<IntView>::post(home,x);
00293 
00294     (void) new (home) Val<Card>(home,x,k);
00295     return ES_OK;
00296   }
00297 
00298 
00299 }}}
00300 
00301 // STATISTICS: int-prop
00302