Generated on Thu Mar 22 10:39:35 2012 for Gecode by doxygen 1.6.3

int-base.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2011
00008  *
00009  *  Last modified:
00010  *     $Date: 2012-02-22 06:04:20 +0100 (Wed, 22 Feb 2012) $ by $Author: tack $
00011  *     $Revision: 12537 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <gecode/int/distinct.hh>
00039 
00040 namespace Gecode { namespace Int { namespace NValues {
00041 
00042   template<class VY>
00043   forceinline
00044   IntBase<VY>::IntBase(Home home, ValSet& vs0, ViewArray<IntView>& x, VY y)
00045     : MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>(home,x,y),
00046       vs(vs0) {}
00047 
00048   template<class VY>
00049   forceinline
00050   IntBase<VY>::IntBase(Space& home, bool share, IntBase<VY>& p)
00051     : MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>(home, share, p) {
00052     vs.update(home, share, p.vs);
00053   }
00054 
00055   template<class VY>
00056   forceinline size_t
00057   IntBase<VY>::dispose(Space& home) {
00058     vs.dispose(home);
00059     (void) MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>
00060       ::dispose(home);
00061     return sizeof(*this);
00062   }
00063 
00064   template<class VY>
00065   PropCost 
00066   IntBase<VY>::cost(const Space&, const ModEventDelta&) const {
00067     return PropCost::quadratic(PropCost::HI, x.size());
00068   }
00069 
00070   template<class VY>
00071   void
00072   IntBase<VY>::add(Space& home) {
00073     int n=x.size();
00074     for (int i=n; i--; )
00075       if (x[i].assigned()) {
00076         vs.add(home, x[i].val());
00077         x[i] = x[--n];
00078       }
00079     x.size(n);
00080   }
00081 
00082   template<class VY>
00083   void
00084   IntBase<VY>::disjoint(Space& home, Region& r, int*& dis, int& n_dis) {
00085     // Compute positions of disjoint views
00086     int n=x.size();
00087     dis = r.alloc<int>(n); n_dis = 0;
00088 
00089     int i=0;
00090     while (i < n)
00091       switch (vs.compare(x[i])) {
00092       case Iter::Ranges::CS_SUBSET:
00093         // All values are already contained in vs, eliminate x[i]
00094         x[i].cancel(home, *this, PC_INT_DOM);
00095         x[i] = x[--n]; 
00096         break;
00097       case Iter::Ranges::CS_DISJOINT:
00098         dis[n_dis++] = i++; 
00099         break;
00100       case Iter::Ranges::CS_NONE:
00101         i++;
00102         break;
00103       default:
00104         GECODE_NEVER;
00105       }
00106     x.size(n);
00107   }
00108 
00109   template<class VY>
00110   void
00111   IntBase<VY>::eliminate(Space& home) {
00112     int n=x.size();
00113     for (int i=n; i--; )
00114       if (vs.subset(x[i])) {
00115         // All values are already contained in vs, eliminate x[i]
00116         x[i].cancel(home, *this, PC_INT_DOM);
00117         x[i] = x[--n]; 
00118       }
00119     x.size(n);
00120   }
00121 
00122   template<class VY>
00123   int
00124   IntBase<VY>::size(Space& home) const {
00125     Region r(home);
00126     assert(x.size() > 0);
00127     ValSet::Ranges vsr(vs);
00128     ViewRanges<IntView> xr(x[x.size()-1]);
00129     Iter::Ranges::NaryUnion u(r,vsr,xr);
00130     for (int i=x.size()-1; i--; ) {
00131       ViewRanges<IntView> xir(x[i]);
00132       u |= xir;
00133     }
00134     unsigned int s = Iter::Ranges::size(u);
00135 
00136     // To avoid overflow
00137     if (static_cast<unsigned int>(x.size()+vs.size()) < s)
00138       return x.size() + vs.size();
00139     else
00140       return static_cast<int>(s);
00141   }
00142 
00143   template<class VY>
00144   ExecStatus
00145   IntBase<VY>::all_in_valset(Space& home) {
00146     for (int i=x.size(); i--; ) {
00147       ValSet::Ranges vsr(vs);
00148       GECODE_ME_CHECK(x[i].inter_r(home, vsr, false));
00149     }
00150     return home.ES_SUBSUMED(*this);
00151   }
00152 
00153   template<class VY>
00154   ExecStatus
00155   IntBase<VY>::prune_lower(Space& home, int* dis, int n_dis) {
00156     assert(n_dis > 0);
00157 
00158     // At least one more value will be needed
00159     GECODE_ME_CHECK(y.gq(home,vs.size() + 1));
00160 
00161     Region r(home);
00162 
00163     // Only one additional value is allowed
00164     if (y.max() == vs.size() + 1) {
00165       // Compute possible values
00166       ViewRanges<IntView>* r_dis = r.alloc<ViewRanges<IntView> >(n_dis);
00167       for (int i=n_dis; i--; )
00168         r_dis[i] = ViewRanges<IntView>(x[dis[i]]);
00169       Iter::Ranges::NaryInter iv(r, r_dis, n_dis);
00170       // Is there a common value at all?
00171       if (!iv())
00172         return ES_FAILED;
00173       ValSet::Ranges vsr(vs);
00174       Iter::Ranges::NaryUnion pv(r,iv,vsr);
00175       // Enforce common values
00176       for (int i=x.size(); i--; ) {
00177         pv.reset();
00178         GECODE_ME_CHECK(x[i].inter_r(home, pv, false));
00179       }
00180       return ES_OK;
00181     }
00182 
00183     // Compute independent set for lower bound
00184     // ovl is a bit-matrix defining whether two views overlap
00185     SymBitMatrix ovl(r,x.size());
00186     // deg[i] is the degree of x[i]
00187     int* deg = r.alloc<int>(x.size());
00188     // ovl_i[i] is an array of indices j such that x[j] overlaps with x[i]
00189     int** ovl_i = r.alloc<int*>(x.size());
00190     // n_ovl_i[i] defines how many integers are stored for ovl_i[i]
00191     int* n_ovl_i = r.alloc<int>(x.size());
00192     {
00193 #ifndef NDEBUG
00194       // Initialize all to null pointers so that things crash ;-)
00195       for (int i=x.size(); i--; )
00196         ovl_i[i] = NULL;
00197 #endif
00198       // For each i there can be at most n_dis-1 entries in ovl_i[i]
00199       int* m = r.alloc<int>(n_dis*(n_dis-1));
00200       for (int i=n_dis; i--; ) {
00201         deg[dis[i]] = 0; 
00202         ovl_i[dis[i]] = m; m += n_dis-1;
00203       }
00204     }
00205     
00206     // Initialize overlap matrix by analyzing the view ranges
00207     {
00208       // Compute how many events are needed
00209       // One event for the end marker
00210       int n_re = 1;
00211       // Two events for each range
00212       for (int i=n_dis; i--; )
00213         for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx)
00214           n_re += 2;
00215 
00216       // Allocate and initialize events
00217       RangeEvent* re = r.alloc<RangeEvent>(n_re);
00218       int j=0;
00219       for (int i=n_dis; i--; )
00220         for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx) {
00221           // Event when a range starts
00222           re[j].ret=RET_FST; re[j].val=rx.min(); re[j].view=dis[i]; j++;
00223           // Event when a range ends
00224           re[j].ret=RET_LST; re[j].val=rx.max(); re[j].view=dis[i]; j++;
00225         }
00226       // Make this the last event
00227       re[j].ret=RET_END; re[j].val=Int::Limits::infinity;
00228       assert(j+1 == n_re);
00229       // Sort and process events
00230       Support::quicksort(re,n_re);
00231 
00232       // Current views with a range being active
00233       Support::BitSet<Region> cur(r,static_cast<unsigned int>(x.size()));
00234       // Process all events
00235       for (int i=0; true; i++)
00236         switch (re[i].ret) {
00237         case RET_FST:
00238           // Process all overlapping views
00239           for (Iter::Values::BitSet<Support::BitSet<Region> > j(cur); 
00240                j(); ++j) {
00241             int di = re[i].view, dj = j.val();
00242             if (!ovl.get(di,dj))  {
00243               ovl.set(di,dj);
00244               ovl_i[di][deg[di]++] = dj; 
00245               ovl_i[dj][deg[dj]++] = di; 
00246             }
00247           }
00248           cur.set(static_cast<unsigned int>(re[i].view));
00249           break;
00250         case RET_LST:
00251           cur.clear(static_cast<unsigned int>(re[i].view));
00252           break;
00253         case RET_END:
00254           goto done;
00255         default:
00256           GECODE_NEVER;
00257         }
00258     done:
00259       r.free<RangeEvent>(re,n_re);
00260     }
00261 
00262     // While deg changes, n_ovl_i remains unchanged and is needed, so copy it
00263     for (int i=n_dis; i--; ) {
00264       assert(deg[dis[i]] < n_dis);
00265       n_ovl_i[dis[i]] = deg[dis[i]];
00266     }
00267     
00268     // Views in the independent set
00269     int* ind = r.alloc<int>(n_dis);
00270     int n_ind = 0;
00271 
00272     while (n_dis > 0) {
00273       int i_min = n_dis-1;
00274       int d_min = deg[dis[i_min]];
00275       unsigned int s_min = x[dis[i_min]].size(); 
00276 
00277       // Find view with smallest (degree,size)
00278       for (int i=n_dis-1; i--; )
00279         if ((d_min > deg[dis[i]]) || 
00280             ((d_min == deg[dis[i]]) && (s_min > x[dis[i]].size()))) {
00281           i_min = i;
00282           d_min = deg[dis[i]];
00283           s_min = x[dis[i]].size();
00284         }
00285 
00286       // i_min refers to view with smallest (degree,size)
00287       ind[n_ind++] = dis[i_min]; dis[i_min] = dis[--n_dis];
00288       
00289       // Filter out non disjoint views
00290       for (int i=n_dis; i--; )
00291         if (ovl.get(dis[i],ind[n_ind-1])) {
00292           // Update degree information
00293           for (int j=n_ovl_i[dis[i]]; j--; )
00294             deg[ovl_i[dis[i]][j]]--;
00295           // Eliminate view
00296           dis[i] = dis[--n_dis];
00297         }
00298     }
00299     // Enforce lower bound
00300     GECODE_ME_CHECK(y.gq(home,vs.size() + n_ind));
00301 
00302     // Prune, if possible
00303     if (vs.size() + n_ind == y.max()) {
00304       // Only values from the indepent set a can be taken
00305       ViewRanges<IntView>* r_ind = r.alloc<ViewRanges<IntView> >(n_ind);
00306       for (int i=n_ind; i--; )
00307         r_ind[i] = ViewRanges<IntView>(x[ind[i]]);
00308       Iter::Ranges::NaryUnion v_ind(r, r_ind, n_ind);
00309       ValSet::Ranges vsr(vs);
00310       v_ind |= vsr;
00311       for (int i=x.size(); i--; ) {
00312         v_ind.reset();
00313         GECODE_ME_CHECK(x[i].inter_r(home,v_ind,false));
00314       }
00315     } 
00316     return ES_OK;
00317   }
00318 
00319   template<class VY>
00320   forceinline ExecStatus
00321   IntBase<VY>::prune_upper(Space& home, Graph& g) {
00322     if (!g.initialized()) {
00323       g.init(home,vs,x);
00324     } else {
00325       g.purge();
00326       g.sync(home);
00327     }
00328     GECODE_ME_CHECK(y.lq(home, g.size()));
00329     if (y.min() == g.size()) {
00330       // All values must be taken on
00331       if (vs.size() + x.size() == g.size()) {
00332         // This is in fact a distinct, simplify and rewrite
00333         for (int i=x.size(); i--; ) {
00334           ValSet::Ranges vsr(vs);
00335           GECODE_ME_CHECK(x[i].minus_r(home, vsr, false));
00336         }
00337         GECODE_REWRITE(*this,Distinct::Dom<IntView>::post(home,x));
00338       }
00339       if (g.mark(home))
00340         GECODE_ES_CHECK(g.prune(home));
00341     }
00342     return ES_OK;
00343   }
00344 
00345 }}}
00346 
00347 // STATISTICS: int-prop