this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5 * Guido Tack <tack@gecode.org>
6 *
7 * Contributing authors:
8 * Christian Schulte <schulte@gecode.org>
9 *
10 * Copyright:
11 * Patrick Pekczynski, 2004
12 * Christian Schulte, 2009
13 * Guido Tack, 2006
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.org
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40#include <gecode/int/gcc.hh>
41
42namespace Gecode {
43
44 namespace {
45
46 /// Comparison operator
47 template<class X>
48 struct LessP {
49 bool operator ()(const std::pair<X,int>& lhs,
50 const std::pair<X,int>& rhs) {
51 return lhs.second < rhs.second;
52 }
53 };
54
55 /// Make \a x and \a y equal
56 IntVar unify(Home home, IntVar x, IntVar y) {
57 rel(home, x, IRT_EQ, y);
58 return x;
59 }
60 /// Make \a x and \a y equal
61 IntSet unify(Home, const IntSet& x, const IntSet& y) {
62 IntSetRanges xr(x);
63 IntSetRanges yr(y);
64 Iter::Ranges::Inter<IntSetRanges,IntSetRanges> i(xr,yr);
65 IntSet z(i);
66 return z;
67 }
68
69 /// Remove dupliate entries in \a v from both \a v and \a c
70 template<class A>
71 void removeDuplicates(Home home, A& c, IntArgs& v) {
72 typedef typename A::value_type S;
73 typedef std::pair<S,int> P;
74 Region re;
75 P* a = re.alloc<P>(c.size());
76 for (int i=0; i<c.size(); i++)
77 a[i] = P(c[i],v[i]);
78 LessP<S> l;
79 Support::quicksort(a,c.size(),l);
80 A cc;
81 IntArgs vv;
82 int cur = a[0].second-1;
83 for (int i=0; i<c.size(); i++) {
84 if (a[i].second==cur) {
85 cc[cc.size()-1] = unify(home, cc[cc.size()-1], a[i].first);
86 } else {
87 cc << a[i].first;
88 vv << a[i].second;
89 cur = a[i].second;
90 }
91 }
92 re.free<P>(a,c.size());
93 c = cc;
94 v = vv;
95 }
96
97 }
98
99 void count(Home home, const IntVarArgs& x,
100 const IntVarArgs& _c, const IntArgs& _v,
101 IntPropLevel ipl) {
102 using namespace Int;
103 IntVarArgs c(_c);
104 IntArgs v(_v);
105 if (v.size() != c.size())
106 throw ArgumentSizeMismatch("Int::count");
107 if (same(x))
108 throw ArgumentSame("Int::count");
109
110 GECODE_POST;
111
112 removeDuplicates(home,c,v);
113
114 ViewArray<IntView> xv(home, x);
115 ViewArray<GCC::CardView> cv(home, c.size());
116 // set the cardinality
117 for (int i=0; i<v.size(); i++)
118 cv[i].init(c[i],v[i]);
119 switch (vbd(ipl)) {
120 case IPL_BND:
121 GECODE_ES_FAIL(
122 (GCC::Bnd<GCC::CardView>::post(home,xv,cv)));
123 break;
124 case IPL_DOM:
125 GECODE_ES_FAIL(
126 (GCC::Dom<GCC::CardView>::post(home,xv,cv)));
127 break;
128 default:
129 GECODE_ES_FAIL(
130 (GCC::Val<GCC::CardView>::post(home,xv,cv)));
131 }
132 }
133
134 // domain is 0..|cards|- 1
135 void count(Home home, const IntVarArgs& x, const IntVarArgs& c,
136 IntPropLevel ipl) {
137 IntArgs values(c.size());
138 for (int i=0; i<c.size(); i++)
139 values[i] = i;
140 count(home, x, c, values, ipl);
141 }
142
143 // constant cards
144 void count(Home home, const IntVarArgs& x,
145 const IntSetArgs& _c, const IntArgs& _v,
146 IntPropLevel ipl) {
147 using namespace Int;
148 IntSetArgs c(_c);
149 IntArgs v(_v);
150 if (v.size() != c.size())
151 throw ArgumentSizeMismatch("Int::count");
152 if (same(x))
153 throw ArgumentSame("Int::count");
154 for (int i=0; i<c.size(); i++) {
155 Limits::check(v[i],"Int::count");
156 Limits::check(c[i].min(),"Int::count");
157 Limits::check(c[i].max(),"Int::count");
158 }
159
160 GECODE_POST;
161
162 removeDuplicates(home,c,v);
163
164 ViewArray<IntView> xv(home, x);
165
166 for (int i=0; i<v.size(); i++) {
167 if (c[i].ranges() > 1) {
168 // Found hole, so create temporary variables
169 ViewArray<GCC::CardView> cv(home, v.size());
170 for (int j=0; j<v.size(); j++)
171 cv[j].init(home,c[j],v[j]);
172 switch (vbd(ipl)) {
173 case IPL_BND:
174 GECODE_ES_FAIL(
175 (GCC::Bnd<GCC::CardView>::post(home, xv, cv)));
176 break;
177 case IPL_DOM:
178 GECODE_ES_FAIL(
179 (GCC::Dom<GCC::CardView>::post(home, xv, cv)));
180 break;
181 default:
182 GECODE_ES_FAIL(
183 (GCC::Val<GCC::CardView>::post(home, xv, cv)));
184 }
185 return;
186 }
187 }
188
189 // No holes: create CardConsts
190 ViewArray<GCC::CardConst> cv(home, c.size());
191
192 for (int i=0; i<c.size(); i++)
193 cv[i].init(home,c[i].min(),c[i].max(),v[i]);
194
195 switch (vbd(ipl)) {
196 case IPL_BND:
197 GECODE_ES_FAIL(
198 (GCC::Bnd<GCC::CardConst>::post(home, xv, cv)));
199 break;
200 case IPL_DOM:
201 GECODE_ES_FAIL(
202 (GCC::Dom<GCC::CardConst>::post(home, xv, cv)));
203 break;
204 default:
205 GECODE_ES_FAIL(
206 (GCC::Val<GCC::CardConst>::post(home, xv, cv)));
207 }
208 }
209
210 // domain is 0..|cards|- 1
211 void count(Home home, const IntVarArgs& x, const IntSetArgs& c,
212 IntPropLevel ipl) {
213 IntArgs values(c.size());
214 for (int i=0; i<c.size(); i++)
215 values[i] = i;
216 count(home, x, c, values, ipl);
217 }
218
219 void count(Home home, const IntVarArgs& x,
220 const IntSet& c, const IntArgs& v,
221 IntPropLevel ipl) {
222 IntSetArgs cards(v.size());
223 for (int i=0; i<v.size(); i++)
224 cards[i] = c;
225 count(home, x, cards, v, ipl);
226 }
227
228}
229
230// STATISTICS: int-post