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