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