Generated on Fri Oct 19 11:25:06 2018 for Gecode by doxygen 1.6.3

gcc.cpp

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  *     Guido Tack <tack@gecode.org>
00006  *
00007  *  Contributing authors:
00008  *     Christian Schulte <schulte@gecode.org>
00009  *
00010  *  Copyright:
00011  *     Patrick Pekczynski, 2004
00012  *     Christian Schulte, 2009
00013  *     Guido Tack, 2006
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #include <gecode/int/gcc.hh>
00041 
00042 namespace Gecode {
00043 
00044   namespace {
00045 
00047     template<class X>
00048     struct LessP {
00049       bool operator ()(const std::pair<X,int>& lhs,
00050                        const std::pair<X,int>& rhs) {
00051         return lhs.second < rhs.second;
00052       }
00053     };
00054 
00056     IntVar unify(Home home, IntVar x, IntVar y) {
00057       rel(home, x, IRT_EQ, y);
00058       return x;
00059     }
00061     IntSet unify(Home, const IntSet& x, const IntSet& y) {
00062       IntSetRanges xr(x);
00063       IntSetRanges yr(y);
00064       Iter::Ranges::Inter<IntSetRanges,IntSetRanges> i(xr,yr);
00065       IntSet z(i);
00066       return z;
00067     }
00068 
00070     template<class A>
00071     void removeDuplicates(Home home, A& c, IntArgs& v) {
00072       typedef typename A::value_type S;
00073       typedef std::pair<S,int> P;
00074       Region re;
00075       P* a = re.alloc<P>(c.size());
00076       for (int i=0; i<c.size(); i++)
00077         a[i] = P(c[i],v[i]);
00078       LessP<S> l;
00079       Support::quicksort(a,c.size(),l);
00080       A cc;
00081       IntArgs vv;
00082       int cur = a[0].second-1;
00083       for (int i=0; i<c.size(); i++) {
00084         if (a[i].second==cur) {
00085           cc[cc.size()-1] = unify(home, cc[cc.size()-1], a[i].first);
00086         } else {
00087           cc << a[i].first;
00088           vv << a[i].second;
00089           cur = a[i].second;
00090         }
00091       }
00092       re.free<P>(a,c.size());
00093       c = cc;
00094       v = vv;
00095     }
00096 
00097   }
00098 
00099   void count(Home home, const IntVarArgs& x,
00100              const IntVarArgs& _c, const IntArgs& _v,
00101              IntPropLevel ipl) {
00102     using namespace Int;
00103     IntVarArgs c(_c);
00104     IntArgs v(_v);
00105     if (v.size() != c.size())
00106       throw ArgumentSizeMismatch("Int::count");
00107     if (same(x))
00108       throw ArgumentSame("Int::count");
00109 
00110     GECODE_POST;
00111 
00112     removeDuplicates(home,c,v);
00113 
00114     ViewArray<IntView> xv(home, x);
00115     ViewArray<GCC::CardView> cv(home, c.size());
00116     // set the cardinality
00117     for (int i=0; i<v.size(); i++)
00118       cv[i].init(c[i],v[i]);
00119     switch (vbd(ipl)) {
00120     case IPL_BND:
00121       GECODE_ES_FAIL(
00122                      (GCC::Bnd<GCC::CardView>::post(home,xv,cv)));
00123       break;
00124     case IPL_DOM:
00125       GECODE_ES_FAIL(
00126                      (GCC::Dom<GCC::CardView>::post(home,xv,cv)));
00127       break;
00128     default:
00129       GECODE_ES_FAIL(
00130                      (GCC::Val<GCC::CardView>::post(home,xv,cv)));
00131     }
00132   }
00133 
00134   // domain is 0..|cards|- 1
00135   void count(Home home, const IntVarArgs& x, const IntVarArgs& c,
00136              IntPropLevel ipl) {
00137     IntArgs values(c.size());
00138     for (int i=0; i<c.size(); i++)
00139       values[i] = i;
00140     count(home, x, c, values, ipl);
00141   }
00142 
00143   // constant cards
00144   void count(Home home, const IntVarArgs& x,
00145              const IntSetArgs& _c, const IntArgs& _v,
00146              IntPropLevel ipl) {
00147     using namespace Int;
00148     IntSetArgs c(_c);
00149     IntArgs v(_v);
00150     if (v.size() != c.size())
00151       throw ArgumentSizeMismatch("Int::count");
00152     if (same(x))
00153       throw ArgumentSame("Int::count");
00154     for (int i=0; i<c.size(); i++) {
00155       Limits::check(v[i],"Int::count");
00156       Limits::check(c[i].min(),"Int::count");
00157       Limits::check(c[i].max(),"Int::count");
00158     }
00159 
00160     GECODE_POST;
00161 
00162     removeDuplicates(home,c,v);
00163 
00164     ViewArray<IntView> xv(home, x);
00165 
00166     for (int i=0; i<v.size(); i++) {
00167       if (c[i].ranges() > 1) {
00168         // Found hole, so create temporary variables
00169         ViewArray<GCC::CardView> cv(home, v.size());
00170         for (int j=0; j<v.size(); j++)
00171           cv[j].init(home,c[j],v[j]);
00172         switch (vbd(ipl)) {
00173         case IPL_BND:
00174           GECODE_ES_FAIL(
00175                          (GCC::Bnd<GCC::CardView>::post(home, xv, cv)));
00176           break;
00177         case IPL_DOM:
00178           GECODE_ES_FAIL(
00179                          (GCC::Dom<GCC::CardView>::post(home, xv, cv)));
00180           break;
00181         default:
00182           GECODE_ES_FAIL(
00183                          (GCC::Val<GCC::CardView>::post(home, xv, cv)));
00184         }
00185         return;
00186       }
00187     }
00188 
00189     // No holes: create CardConsts
00190     ViewArray<GCC::CardConst> cv(home, c.size());
00191 
00192     for (int i=0; i<c.size(); i++)
00193       cv[i].init(home,c[i].min(),c[i].max(),v[i]);
00194 
00195     switch (vbd(ipl)) {
00196     case IPL_BND:
00197       GECODE_ES_FAIL(
00198                      (GCC::Bnd<GCC::CardConst>::post(home, xv, cv)));
00199       break;
00200     case IPL_DOM:
00201       GECODE_ES_FAIL(
00202                      (GCC::Dom<GCC::CardConst>::post(home, xv, cv)));
00203       break;
00204     default:
00205       GECODE_ES_FAIL(
00206                      (GCC::Val<GCC::CardConst>::post(home, xv, cv)));
00207     }
00208   }
00209 
00210   // domain is 0..|cards|- 1
00211   void count(Home home, const IntVarArgs& x, const IntSetArgs& c,
00212              IntPropLevel ipl) {
00213     IntArgs values(c.size());
00214     for (int i=0; i<c.size(); i++)
00215       values[i] = i;
00216     count(home, x, c, values, ipl);
00217   }
00218 
00219   void count(Home home, const IntVarArgs& x,
00220              const IntSet& c, const IntArgs& v,
00221              IntPropLevel ipl) {
00222     IntSetArgs cards(v.size());
00223     for (int i=0; i<v.size(); i++)
00224       cards[i] = c;
00225     count(home, x, cards, v, ipl);
00226   }
00227 
00228 }
00229 
00230 // STATISTICS: int-post