Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
gcc.cpp
Go to the documentation of this file.
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
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
56 IntVar unify(Home home, IntVar x, IntVar y) {
57 rel(home, x, IRT_EQ, y);
58 return x;
59 }
61 IntSet unify(Home, const IntSet& x, const IntSet& y) {
62 IntSetRanges xr(x);
63 IntSetRanges yr(y);
65 IntSet z(i);
66 return z;
67 }
68
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;
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
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:
122 (GCC::Bnd<GCC::CardView>::post(home,xv,cv)));
123 break;
124 case IPL_DOM:
126 (GCC::Dom<GCC::CardView>::post(home,xv,cv)));
127 break;
128 default:
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
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:
175 (GCC::Bnd<GCC::CardView>::post(home, xv, cv)));
176 break;
177 case IPL_DOM:
179 (GCC::Dom<GCC::CardView>::post(home, xv, cv)));
180 break;
181 default:
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:
198 (GCC::Bnd<GCC::CardConst>::post(home, xv, cv)));
199 break;
200 case IPL_DOM:
202 (GCC::Dom<GCC::CardConst>::post(home, xv, cv)));
203 break;
204 default:
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
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Definition val.hpp:78
Home class for posting propagators
Definition core.hpp:856
Passing integer arguments.
Definition int.hh:634
Range iterator for integer sets.
Definition int.hh:292
Integer sets.
Definition int.hh:174
Passing integer variables.
Definition int.hh:662
Integer variables.
Definition int.hh:371
Exception: Arguments contain same variable multiply
Definition exception.hpp:80
Exception: Arguments are of different size
Definition exception.hpp:73
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition bnd.hpp:808
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition dom.hpp:299
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition val.hpp:287
Range iterator for computing intersection (binary)
Handle to region.
Definition region.hpp:55
View arrays.
Definition array.hpp:253
View & operator()(View &x)
Integer-precision integer scale view.
Definition view.hpp:632
#define GECODE_POST
Check for failure in a constraint post function.
Definition macros.hpp:40
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition macros.hpp:103
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:989
@ IRT_EQ
Equality ( )
Definition int.hh:941
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:994
@ IPL_BND
Bounds propagation.
Definition int.hh:993
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition limits.hpp:46
Finite domain integers.
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
ArgArray< IntSet > IntSetArgs
Passing set arguments.
Definition int.hh:625
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
IntPropLevel vbd(IntPropLevel ipl)
Extract value, bounds, or domain propagation from propagation level.
Definition ipl.hpp:37
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition set.hh:773
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1943
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:773
Gecode::FloatVal c(-8, 8)
Gecode::FloatVal a(-8, 5)
Gecode::IntArgs i({1, 2, 3, 4})