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 IntPropLevel ipl) {
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
00114 GECODE_POST;
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 (vbd(ipl)) {
00124 case IPL_BND:
00125 GECODE_ES_FAIL(
00126 (GCC::Bnd<GCC::CardView>::post(home,xv,cv)));
00127 break;
00128 case IPL_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 IntPropLevel ipl) {
00141 IntArgs values(c.size());
00142 for (int i = c.size(); i--; )
00143 values[i] = i;
00144 count(home, x, c, values, ipl);
00145 }
00146
00147
00148 void count(Home home, const IntVarArgs& x,
00149 const IntSetArgs& _c, const IntArgs& _v,
00150 IntPropLevel ipl) {
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 GECODE_POST;
00165
00166 removeDuplicates(home,c,v);
00167
00168 ViewArray<IntView> xv(home, x);
00169
00170 for (int i = v.size(); i--; ) {
00171 if (c[i].ranges() > 1) {
00172
00173 ViewArray<GCC::CardView> cv(home, v.size());
00174 for (int j = v.size(); j--; )
00175 cv[j].init(home,c[j],v[j]);
00176 switch (vbd(ipl)) {
00177 case IPL_BND:
00178 GECODE_ES_FAIL(
00179 (GCC::Bnd<GCC::CardView>::post(home, xv, cv)));
00180 break;
00181 case IPL_DOM:
00182 GECODE_ES_FAIL(
00183 (GCC::Dom<GCC::CardView>::post(home, xv, cv)));
00184 break;
00185 default:
00186 GECODE_ES_FAIL(
00187 (GCC::Val<GCC::CardView>::post(home, xv, cv)));
00188 }
00189 return;
00190 }
00191 }
00192
00193
00194 ViewArray<GCC::CardConst> cv(home, c.size());
00195
00196 for (int i = c.size(); i--; )
00197 cv[i].init(home,c[i].min(),c[i].max(),v[i]);
00198
00199 switch (vbd(ipl)) {
00200 case IPL_BND:
00201 GECODE_ES_FAIL(
00202 (GCC::Bnd<GCC::CardConst>::post(home, xv, cv)));
00203 break;
00204 case IPL_DOM:
00205 GECODE_ES_FAIL(
00206 (GCC::Dom<GCC::CardConst>::post(home, xv, cv)));
00207 break;
00208 default:
00209 GECODE_ES_FAIL(
00210 (GCC::Val<GCC::CardConst>::post(home, xv, cv)));
00211 }
00212 }
00213
00214
00215 void count(Home home, const IntVarArgs& x, const IntSetArgs& c,
00216 IntPropLevel ipl) {
00217 IntArgs values(c.size());
00218 for (int i = c.size(); i--; )
00219 values[i] = i;
00220 count(home, x, c, values, ipl);
00221 }
00222
00223 void count(Home home, const IntVarArgs& x,
00224 const IntSet& c, const IntArgs& v,
00225 IntPropLevel ipl) {
00226 IntSetArgs cards(v.size());
00227 for (int i = v.size(); i--; )
00228 cards[i] = c;
00229 count(home, x, cards, v, ipl);
00230 }
00231
00232 }
00233
00234