00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044 #include <gecode/int/gcc.hh>
00045
00046 namespace Gecode {
00047
00048 namespace {
00049
00051 template<class X>
00052 struct LessP {
00053 bool operator ()(const std::pair<X,int>& lhs,
00054 const std::pair<X,int>& rhs) {
00055 return lhs.second < rhs.second;
00056 }
00057 };
00058
00060 IntVar unify(Home home, IntVar x, IntVar y) {
00061 rel(home, x, IRT_EQ, y);
00062 return x;
00063 }
00065 IntSet unify(Home, const IntSet& x, const IntSet& y) {
00066 IntSetRanges xr(x);
00067 IntSetRanges yr(y);
00068 Iter::Ranges::Inter<IntSetRanges,IntSetRanges> i(xr,yr);
00069 IntSet z(i);
00070 return z;
00071 }
00072
00074 template<class A>
00075 void removeDuplicates(Home home, A& c, IntArgs& v) {
00076 typedef typename A::value_type S;
00077 typedef std::pair<S,int> P;
00078 Region re(home);
00079 P* a = re.alloc<P>(c.size());
00080 for (int i=c.size(); i--;)
00081 a[i] = P(c[i],v[i]);
00082 LessP<S> l;
00083 Support::quicksort(a,c.size(),l);
00084 A cc;
00085 IntArgs vv;
00086 int cur = a[0].second-1;
00087 for (int i=0; i<c.size(); i++) {
00088 if (a[i].second==cur) {
00089 cc[cc.size()-1] = unify(home, cc[cc.size()-1], a[i].first);
00090 } else {
00091 cc << a[i].first;
00092 vv << a[i].second;
00093 cur = a[i].second;
00094 }
00095 }
00096 re.free<P>(a,c.size());
00097 c = cc;
00098 v = vv;
00099 }
00100
00101 }
00102
00103 void count(Home home, const IntVarArgs& x,
00104 const IntVarArgs& _c, const IntArgs& _v,
00105 IntConLevel icl) {
00106 using namespace Int;
00107 IntVarArgs c(_c);
00108 IntArgs v(_v);
00109 if (v.size() != c.size())
00110 throw ArgumentSizeMismatch("Int::count");
00111 if (x.same(home))
00112 throw ArgumentSame("Int::count");
00113 if (home.failed())
00114 return;
00115
00116 removeDuplicates(home,c,v);
00117
00118 ViewArray<IntView> xv(home, x);
00119 ViewArray<GCC::CardView> cv(home, c.size());
00120
00121 for (int i = v.size(); i--; )
00122 cv[i].init(c[i],v[i]);
00123 switch (icl) {
00124 case ICL_BND:
00125 GECODE_ES_FAIL(
00126 (GCC::Bnd<GCC::CardView>::post(home,xv,cv)));
00127 break;
00128 case ICL_DOM:
00129 GECODE_ES_FAIL(
00130 (GCC::Dom<GCC::CardView>::post(home,xv,cv)));
00131 break;
00132 default:
00133 GECODE_ES_FAIL(
00134 (GCC::Val<GCC::CardView>::post(home,xv,cv)));
00135 }
00136 }
00137
00138
00139 void count(Home home, const IntVarArgs& x, const IntVarArgs& c,
00140 IntConLevel icl) {
00141 IntArgs values(c.size());
00142 for (int i = c.size(); i--; )
00143 values[i] = i;
00144 count(home, x, c, values, icl);
00145 }
00146
00147
00148 void count(Home home, const IntVarArgs& x,
00149 const IntSetArgs& _c, const IntArgs& _v,
00150 IntConLevel icl) {
00151 using namespace Int;
00152 IntSetArgs c(_c);
00153 IntArgs v(_v);
00154 if (v.size() != c.size())
00155 throw ArgumentSizeMismatch("Int::count");
00156 if (x.same(home))
00157 throw ArgumentSame("Int::count");
00158 for (int i=c.size(); i--; ) {
00159 Limits::check(v[i],"Int::count");
00160 Limits::check(c[i].min(),"Int::count");
00161 Limits::check(c[i].max(),"Int::count");
00162 }
00163
00164 if (home.failed())
00165 return;
00166
00167 removeDuplicates(home,c,v);
00168
00169 ViewArray<IntView> xv(home, x);
00170
00171 for (int i = v.size(); i--; ) {
00172 if (c[i].ranges() > 1) {
00173
00174 ViewArray<GCC::CardView> cv(home, v.size());
00175 for (int j = v.size(); j--; )
00176 cv[j].init(home,c[j],v[j]);
00177 switch (icl) {
00178 case ICL_BND:
00179 GECODE_ES_FAIL(
00180 (GCC::Bnd<GCC::CardView>::post(home, xv, cv)));
00181 break;
00182 case ICL_DOM:
00183 GECODE_ES_FAIL(
00184 (GCC::Dom<GCC::CardView>::post(home, xv, cv)));
00185 break;
00186 default:
00187 GECODE_ES_FAIL(
00188 (GCC::Val<GCC::CardView>::post(home, xv, cv)));
00189 }
00190 return;
00191 }
00192 }
00193
00194
00195 ViewArray<GCC::CardConst> cv(home, c.size());
00196
00197 for (int i = c.size(); i--; )
00198 cv[i].init(home,c[i].min(),c[i].max(),v[i]);
00199
00200 switch (icl) {
00201 case ICL_BND:
00202 GECODE_ES_FAIL(
00203 (GCC::Bnd<GCC::CardConst>::post(home, xv, cv)));
00204 break;
00205 case ICL_DOM:
00206 GECODE_ES_FAIL(
00207 (GCC::Dom<GCC::CardConst>::post(home, xv, cv)));
00208 break;
00209 default:
00210 GECODE_ES_FAIL(
00211 (GCC::Val<GCC::CardConst>::post(home, xv, cv)));
00212 }
00213 }
00214
00215
00216 void count(Home home, const IntVarArgs& x, const IntSetArgs& c,
00217 IntConLevel icl) {
00218 IntArgs values(c.size());
00219 for (int i = c.size(); i--; )
00220 values[i] = i;
00221 count(home, x, c, values, icl);
00222 }
00223
00224 void count(Home home, const IntVarArgs& x,
00225 const IntSet& c, const IntArgs& v,
00226 IntConLevel icl) {
00227 IntSetArgs cards(v.size());
00228 for (int i = v.size(); i--; )
00229 cards[i] = c;
00230 count(home, x, cards, v, icl);
00231 }
00232
00233 }
00234
00235