Generated on Tue Dec 13 2011 10:02:10 for Gecode by doxygen 1.7.4
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: 2011-09-07 16:15:16 +0200 (Wed, 07 Sep 2011) $ by $Author: schulte $
00011  *     $Revision: 12394 $
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     Iter::Ranges::NaryUnion 
00128       u(r,ValSet::Ranges(vs),ViewRanges<IntView>(x[x.size()-1]));
00129     for (int i=x.size()-1; i--; )
00130       u |= ViewRanges<IntView>(x[i]);
00131     unsigned int s = Iter::Ranges::size(u);
00132 
00133     // To avoid overflow
00134     if (static_cast<unsigned int>(x.size()+vs.size()) < s)
00135       return x.size() + vs.size();
00136     else
00137       return static_cast<int>(s);
00138   }
00139 
00140   template<class VY>
00141   ExecStatus
00142   IntBase<VY>::all_in_valset(Space& home) {
00143     for (int i=x.size(); i--; ) {
00144       ValSet::Ranges vsr(vs);
00145       GECODE_ME_CHECK(x[i].inter_r(home, vsr, false));
00146     }
00147     return home.ES_SUBSUMED(*this);
00148   }
00149 
00150   template<class VY>
00151   ExecStatus
00152   IntBase<VY>::prune_lower(Space& home, int* dis, int n_dis) {
00153     assert(n_dis > 0);
00154 
00155     // At least one more value will be needed
00156     GECODE_ME_CHECK(y.gq(home,vs.size() + 1));
00157 
00158     Region r(home);
00159 
00160     // Only one additional value is allowed
00161     if (y.max() == vs.size() + 1) {
00162       // Compute possible values
00163       ViewRanges<IntView>* r_dis = r.alloc<ViewRanges<IntView> >(n_dis);
00164       for (int i=n_dis; i--; )
00165         r_dis[i] = ViewRanges<IntView>(x[dis[i]]);
00166       Iter::Ranges::NaryInter iv(r, r_dis, n_dis);
00167       // Is there a common value at all?
00168       if (!iv())
00169         return ES_FAILED;
00170       ValSet::Ranges vsr(vs);
00171       Iter::Ranges::NaryUnion pv(r,iv,vsr);
00172       // Enforce common values
00173       for (int i=x.size(); i--; ) {
00174         pv.reset();
00175         GECODE_ME_CHECK(x[i].inter_r(home, pv, false));
00176       }
00177       return ES_OK;
00178     }
00179 
00180     // Compute independent set for lower bound
00181     // ovl is a bit-matrix defining whether two views overlap
00182     SymBitMatrix ovl(r,x.size());
00183     // deg[i] is the degree of x[i]
00184     int* deg = r.alloc<int>(x.size());
00185     // ovl_i[i] is an array of indices j such that x[j] overlaps with x[i]
00186     int** ovl_i = r.alloc<int*>(x.size());
00187     // n_ovl_i[i] defines how many integers are stored for ovl_i[i]
00188     int* n_ovl_i = r.alloc<int>(x.size());
00189     {
00190 #ifndef NDEBUG
00191       // Initialize all to null pointers so that things crash ;-)
00192       for (int i=x.size(); i--; )
00193         ovl_i[i] = NULL;
00194 #endif
00195       // For each i there can be at most n_dis-1 entries in ovl_i[i]
00196       int* m = r.alloc<int>(n_dis*(n_dis-1));
00197       for (int i=n_dis; i--; ) {
00198         deg[dis[i]] = 0; 
00199         ovl_i[dis[i]] = m; m += n_dis-1;
00200       }
00201     }
00202     
00203     // Initialize overlap matrix by analyzing the view ranges
00204     {
00205       // Compute how many events are needed
00206       // One event for the end marker
00207       int n_re = 1;
00208       // Two events for each range
00209       for (int i=n_dis; i--; )
00210         for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx)
00211           n_re += 2;
00212 
00213       // Allocate and initialize events
00214       RangeEvent* re = r.alloc<RangeEvent>(n_re);
00215       int j=0;
00216       for (int i=n_dis; i--; )
00217         for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx) {
00218           // Event when a range starts
00219           re[j].ret=RET_FST; re[j].val=rx.min(); re[j].view=dis[i]; j++;
00220           // Event when a range ends
00221           re[j].ret=RET_LST; re[j].val=rx.max(); re[j].view=dis[i]; j++;
00222         }
00223       // Make this the last event
00224       re[j].ret=RET_END; re[j].val=Int::Limits::infinity;
00225       assert(j+1 == n_re);
00226       // Sort and process events
00227       Support::quicksort(re,n_re);
00228 
00229       // Current views with a range being active
00230       Support::BitSet<Region> cur(r,static_cast<unsigned int>(x.size()));
00231       // Process all events
00232       for (int i=0; true; i++)
00233         switch (re[i].ret) {
00234         case RET_FST:
00235           // Process all overlapping views
00236           for (Iter::Values::BitSet<Support::BitSet<Region> > j(cur); 
00237                j(); ++j) {
00238             int di = re[i].view, dj = j.val();
00239             if (!ovl.get(di,dj))  {
00240               ovl.set(di,dj);
00241               ovl_i[di][deg[di]++] = dj; 
00242               ovl_i[dj][deg[dj]++] = di; 
00243             }
00244           }
00245           cur.set(static_cast<unsigned int>(re[i].view));
00246           break;
00247         case RET_LST:
00248           cur.clear(static_cast<unsigned int>(re[i].view));
00249           break;
00250         case RET_END:
00251           goto done;
00252         default:
00253           GECODE_NEVER;
00254         }
00255     done:
00256       r.free<RangeEvent>(re,n_re);
00257     }
00258 
00259     // While deg changes, n_ovl_i remains unchanged and is needed, so copy it
00260     for (int i=n_dis; i--; ) {
00261       assert(deg[dis[i]] < n_dis);
00262       n_ovl_i[dis[i]] = deg[dis[i]];
00263     }
00264     
00265     // Views in the independent set
00266     int* ind = r.alloc<int>(n_dis);
00267     int n_ind = 0;
00268 
00269     while (n_dis > 0) {
00270       int i_min = n_dis-1;
00271       int d_min = deg[dis[i_min]];
00272       unsigned int s_min = x[dis[i_min]].size(); 
00273 
00274       // Find view with smallest (degree,size)
00275       for (int i=n_dis-1; i--; )
00276         if ((d_min > deg[dis[i]]) || 
00277             ((d_min == deg[dis[i]]) && (s_min > x[dis[i]].size()))) {
00278           i_min = i;
00279           d_min = deg[dis[i]];
00280           s_min = x[dis[i]].size();
00281         }
00282 
00283       // i_min refers to view with smallest (degree,size)
00284       ind[n_ind++] = dis[i_min]; dis[i_min] = dis[--n_dis];
00285       
00286       // Filter out non disjoint views
00287       for (int i=n_dis; i--; )
00288         if (ovl.get(dis[i],ind[n_ind-1])) {
00289           // Update degree information
00290           for (int j=n_ovl_i[dis[i]]; j--; )
00291             deg[ovl_i[dis[i]][j]]--;
00292           // Eliminate view
00293           dis[i] = dis[--n_dis];
00294         }
00295     }
00296     // Enforce lower bound
00297     GECODE_ME_CHECK(y.gq(home,vs.size() + n_ind));
00298 
00299     // Prune, if possible
00300     if (vs.size() + n_ind == y.max()) {
00301       // Only values from the indepent set a can be taken
00302       ViewRanges<IntView>* r_ind = r.alloc<ViewRanges<IntView> >(n_ind);
00303       for (int i=n_ind; i--; )
00304         r_ind[i] = ViewRanges<IntView>(x[ind[i]]);
00305       Iter::Ranges::NaryUnion v_ind(r, r_ind, n_ind);
00306       ValSet::Ranges vsr(vs);
00307       v_ind |= vsr;
00308       for (int i=x.size(); i--; ) {
00309         v_ind.reset();
00310         GECODE_ME_CHECK(x[i].inter_r(home,v_ind,false));
00311       }
00312     } 
00313     return ES_OK;
00314   }
00315 
00316   template<class VY>
00317   forceinline ExecStatus
00318   IntBase<VY>::prune_upper(Space& home, Graph& g) {
00319     if (!g.initialized()) {
00320       g.init(home,vs,x);
00321     } else {
00322       g.purge();
00323       g.sync(home);
00324     }
00325     GECODE_ME_CHECK(y.lq(home, g.size()));
00326     if (y.min() == g.size()) {
00327       // All values must be taken on
00328       if (vs.size() + x.size() == g.size()) {
00329         // This is in fact a distinct, simplify and rewrite
00330         for (int i=x.size(); i--; ) {
00331           ValSet::Ranges vsr(vs);
00332           GECODE_ME_CHECK(x[i].minus_r(home, vsr, false));
00333         }
00334         GECODE_REWRITE(*this,Distinct::Dom<IntView>::post(home,x));
00335       }
00336       if (g.mark(home))
00337         GECODE_ES_CHECK(g.prune(home));
00338     }
00339     return ES_OK;
00340   }
00341 
00342 }}}
00343 
00344 // STATISTICS: int-prop