Generated on Mon Nov 30 23:53:20 2009 for Gecode by doxygen 1.6.1

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: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $
00017  *     $Revision: 9878 $
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   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         count[idx]++;
00120         non--;
00121       }
00122 
00123     // check for subsumption
00124     if (non == 0) {
00125       for (int i = k.size(); i--; )
00126         GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
00127       return ES_SUBSUMED(p,home);
00128     }
00129 
00130     // total number of unsatisfied miminum occurences
00131     int req = 0;
00132     // number of values whose min requirements are not yet met
00133     int n_r = 0;
00134     // if only one value is unsatisified single holds the index of that value
00135     int single = -1;
00136     // total number of assigned views wrt. the original probem size
00137     int t_noa = 0;
00138 
00139     for (int i = k.size(); i--; ) {
00140       int ci = count[i] + k[i].counter();
00141       t_noa += ci;
00142       if (ci == 0) { // this works
00143         req += k[i].min();
00144         n_r++;
00145         single = i;
00146       }
00147 
00148       // number of unassigned views cannot satisfy
00149       // the required minimum occurence
00150       if (req > non)
00151         return ES_FAILED;
00152     }
00153 
00154     // if only one unsatisfied occurences is left
00155     if ((req == non) && (n_r == 1)) {
00156       // This works as the x are not shared!
00157       for (int i = x.size(); i--; ) {
00158         // try to assign it
00159         if (!x[i].assigned()) {
00160           GECODE_ME_CHECK(x[i].eq(home, k[single].card()));
00161           assert((single >= 0) && (single < k.size()));
00162           count[single]++;
00163         }
00164       }
00165       assert((single >= 0) && (single < k.size()));
00166 
00167       for (int i = k.size(); i--; )
00168         GECODE_ME_CHECK(k[i].eq(home, count[i] + k[i].counter()));
00169       return ES_SUBSUMED(p,home);
00170     }
00171 
00172     // Bitset for indexes that can be removed
00173     Support::BitSet<Region> rem(r,k.size());
00174 
00175     for (int i = k.size(); i--; ) {
00176       int ci = count[i] + k[i].counter();
00177       if ((ci == k[i].max()) && !rem.get(i)) {
00178         rem.set(i);
00179         k[i].counter(ci);
00180         // the solution contains ci occurences of value k[i].card();
00181         if (Card::propagate)
00182           GECODE_ME_CHECK(k[i].eq(home, ci));
00183       } else {
00184         if (ci > k[i].max())
00185           return ES_FAILED;
00186         
00187         // in case of variable cardinalities
00188         if (Card::propagate) {
00189           GECODE_ME_CHECK(k[i].gq(home, ci));
00190           int occupied = t_noa - ci;
00191           GECODE_ME_CHECK(k[i].lq(home, x.size() + removed - occupied));
00192         }
00193       }
00194       // reset counter
00195       count[i] = 0;
00196     }
00197 
00198     // reduce the problem size
00199     {
00200       int n_x = x.size();
00201       for (int i = n_x; i--; ) {
00202         if (x[i].assigned()) {
00203           int idx;
00204           if (!lookupValue(k,x[i].val(),idx))
00205             return ES_FAILED;
00206           if (rem.get(idx))
00207             x[i]=x[--n_x];
00208         }
00209       }
00210       x.size(n_x);
00211     }
00212 
00213     // remove values
00214     {
00215       // Values to prune
00216       int* p = r.alloc<int>(k.size());
00217       // Number of values to prune
00218       int n_p = 0;
00219       for (Iter::Values::BitSet<Support::BitSet<Region> > i(rem); i(); ++i)
00220         p[n_p++] = k[i.val()].card();
00221       Support::quicksort(p,n_p);
00222       for (int i = x.size(); i--;) {
00223         Iter::Values::Array pi(p,n_p);
00224         GECODE_ME_CHECK(x[i].minus_v(home, pi, false));
00225       }
00226     }
00227 
00228     {
00229       bool all_assigned = true;
00230 
00231       for (int i = x.size(); i--; ) {
00232         if (x[i].assigned()) {
00233           int idx;
00234           if (!lookupValue(k,x[i].val(),idx))
00235             return ES_FAILED;
00236           count[idx]++;
00237         } else {
00238           all_assigned = false;
00239         }
00240       }
00241       
00242       if (all_assigned) {
00243         for (int i = k.size(); i--; )
00244           GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
00245         return ES_SUBSUMED(p,home);
00246       }
00247     }
00248 
00249     if (Card::propagate) {
00250       // check again consistency of cardinalities
00251       int reqmin = 0;
00252       int allmax = 0;
00253       for (int i = k.size(); i--; ) {
00254         if (k[i].counter() > k[i].max())
00255           return ES_FAILED;
00256         allmax += k[i].max() - k[i].counter();
00257         if (k[i].counter() < k[i].min())
00258           reqmin += k[i].min() - k[i].counter();
00259         if (k[i].min() > x.size())
00260           return ES_FAILED;
00261         GECODE_ME_CHECK((k[i].lq(home, x.size())));
00262       }
00263 
00264       if ((x.size() < reqmin) || (allmax < x.size()))
00265         return ES_FAILED;
00266     }
00267 
00268     return ES_NOFIX;
00269   }
00270 
00271   template<class Card>
00272   ExecStatus
00273   Val<Card>::propagate(Space& home, const ModEventDelta&) {
00274     return prop_val<Card>(home, *this, x, k);
00275   }
00276 
00277   template<class Card>
00278   ExecStatus
00279   Val<Card>::post(Home home,
00280                   ViewArray<IntView>& x, ViewArray<Card>& k) {
00281     GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
00282 
00283     if (isDistinct<Card>(home,x,k))
00284       return Distinct::Val<IntView>::post(home,x);
00285    
00286     (void) new (home) Val<Card>(home,x,k);
00287     return ES_OK;
00288   }
00289 
00290 
00291 }}}
00292 
00293 // STATISTICS: int-prop
00294