this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 * Christian Schulte <schulte@gecode.org>
6 *
7 * Copyright:
8 * Guido Tack, 2005
9 * Christian Schulte, 2005
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36#ifndef GECODE_TEST_SET_HH
37#define GECODE_TEST_SET_HH
38
39#include <gecode/set.hh>
40#include "test/test.hh"
41#include "test/int.hh"
42
43namespace Test {
44
45 /// Testing finite sets
46 namespace Set {
47
48 /**
49 * \defgroup TaskTestSet Testing finite sets
50 * \ingroup TaskTest
51 */
52
53 /**
54 * \defgroup TaskTestSetSupport General set test support
55 * \ingroup TaskTestSet
56 */
57 //@{
58
59 /// Value iterator producing subsets of an IntSet
60 class CountableSetValues {
61 private:
62 Gecode::IntSetValues dv;
63 int cur;
64 int i;
65 public:
66 /// Default constructor
67 CountableSetValues(void) {}
68 /// Initialize with set \a d0 and bit-pattern \a cur0
69 CountableSetValues(const Gecode::IntSet& d0, int cur0)
70 : dv(d0), cur(cur0), i(1) {
71 if (! (i & cur))
72 operator++();
73 }
74 /// Initialize with set \a d0 and bit-pattern \a cur0
75 void init(const Gecode::IntSet& d0, int cur0) {
76 dv = d0;
77 cur = cur0;
78 i = 1;
79 if (! (i & cur))
80 operator++();
81 }
82 /// Test if finished
83 bool operator()(void) const {
84 return i<=cur;
85 }
86 /// Move to next value
87 void operator++(void) {
88 do {
89 ++dv;
90 i = i<<1;
91 } while (! (i & cur) && i<cur);
92 }
93 /// Return current value
94 int val(void) const { return dv.val(); }
95 };
96
97 /// Range iterator producing subsets of an IntSet
98 class CountableSetRanges
99 : public Gecode::Iter::Values::ToRanges<CountableSetValues> {
100 private:
101 /// The corresponding value iterator
102 CountableSetValues v;
103 public:
104 /// Default constructor
105 CountableSetRanges(void) {}
106 /// Initialize with set \a d0 and bit-pattern \a cur0
107 CountableSetRanges(const Gecode::IntSet& d, int cur) : v(d, cur) {
108 Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
109 }
110 /// Initialize with set \a d0 and bit-pattern \a cur0
111 void init(const Gecode::IntSet& d, int cur) {
112 v.init(d, cur);
113 Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
114 }
115 };
116
117 /// Iterate all subsets of a given set
118 class CountableSet {
119 private:
120 /// The superset
121 Gecode::IntSet d;
122 /// Integer representing the current subset to iterate
123 unsigned int cur;
124 /// Endpoint of iteration
125 unsigned int lubmax;
126 public:
127 /// Initialize with set \a s
128 CountableSet(const Gecode::IntSet& s);
129 /// Default constructor
130 CountableSet(void) {}
131 /// Initialize with set \a s
132 void init(const Gecode::IntSet& s);
133 /// Check if still subsets left
134 bool operator()(void) const { return cur<lubmax; }
135 /// Move to next subset
136 void operator++(void);
137 /// Return current subset
138 int val(void) const;
139 };
140
141 /// Generate all set assignments
142 class SetAssignment {
143 private:
144 /// Arity
145 int n;
146 /// Iterator for each set variable
147 CountableSet* dsv;
148 /// Iterator for int variable
149 Test::Int::CpltAssignment ir;
150 /// Flag whether all assignments have been generated
151 bool done;
152 public:
153 /// The common superset for all domains
154 Gecode::IntSet lub;
155 /// How many integer variables to iterate
156 int withInt;
157 /// Initialize with \a n set variables, initial bound \a d and \a i int variables
158 SetAssignment(int n, const Gecode::IntSet& d, int i = 0);
159 /// Test whether all assignments have been iterated
160 bool operator()(void) const { return !done; }
161 /// Move to next assignment
162 void next(Gecode::Support::RandomGenerator& rand);
163 /// Return value for variable \a i
164 int operator[](int i) const {
165 assert((i>=0) && (i<n));
166 return dsv[i].val();
167 }
168 /// Return value for first integer variable
169 int intval(void) const { return ir[0]; }
170 /// Return assignment for integer variables
171 const Test::Int::Assignment& ints(void) const { return ir; }
172 /// Return arity
173 int size(void) const { return n; }
174 /// Destructor
175 ~SetAssignment(void) { delete [] dsv; }
176 };
177
178
179 class SetTest;
180
181 /// Space for executing set tests
182 class SetTestSpace : public Gecode::Space {
183 public:
184 /// Initial domain
185 Gecode::IntSet d;
186 /// Set variables to be tested
187 Gecode::SetVarArray x;
188 /// Int variables to be tested
189 Gecode::IntVarArray y;
190 /// How many integer variables are used by the test
191 int withInt;
192 /// Reification information
193 Gecode::Reify r;
194 /// Whether the test is for a reified propagator
195 bool reified;
196 /// The test currently run
197 SetTest* test;
198
199 /**
200 * \brief Create test space without reification
201 *
202 * Creates \a n set variables with domain \a d0,
203 * \a i integer variables with domain \a d0, and stores whether
204 * the test is for a reified propagator (\a r), and the test itself
205 * (\a t).
206 *
207 */
208 SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
209 bool log=true);
210 /**
211 * \brief Create test space with reification
212 *
213 * Creates \a n set variables with domain \a d0,
214 * \a i integer variables with domain \a d0, and stores whether
215 * the test is for a reified propagator (\a r), and the test itself
216 * (\a t).
217 *
218 */
219 SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
220 Gecode::ReifyMode rm, bool log=true);
221 /// Constructor for cloning \a s
222 SetTestSpace(SetTestSpace& s);
223 /// Copy space during cloning
224 virtual Gecode::Space* copy(void);
225 /// Post propagator
226 void post(void);
227 /// Compute a fixpoint and check for failure
228 bool failed(void);
229 /// Check for subsumption if \a b is true
230 bool subsumed(bool b);
231 /// Perform set tell operation on \a x[i]
232 void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is);
233 /// Perform cardinality tell operation on \a x[i]
234 void cardinality(int i, int cmin, int cmax);
235 /// Perform integer tell operation on \a y[i]
236 void rel(int i, Gecode::IntRelType irt, int n);
237 /// Perform Boolean tell on \a b
238 void rel(bool sol);
239 /// Assign all variables to values in \a a
240 void assign(const SetAssignment& a, Gecode::Support::RandomGenerator& rand);
241 /// Test whether all variables are assigned
242 bool assigned(void) const;
243 /// Remove value \a v from the upper bound of \a x[i]
244 void removeFromLub(int v, int i, const SetAssignment& a);
245 /// Remove value \a v from the upper bound of \a x[i]
246 void removeFromLub(int v, int i, const SetAssignment& a,
247 SetTestSpace& c);
248 /// Remove value \a v from the lower bound of \a x[i]
249 void addToGlb(int v, int i, const SetAssignment& a);
250 /// Remove value \a v from the lower bound of \a x[i]
251 void addToGlb(int v, int i, const SetAssignment& a,
252 SetTestSpace& c);
253 /// Perform fixpoint computation
254 bool fixprob(void);
255 /// Perform random pruning
256 bool prune(const SetAssignment& a, Gecode::Support::RandomGenerator& rand);
257 /// Return the number of propagators
258 unsigned int propagators(void);
259 /// Disable propagators in space and compute fixpoint (make all idle)
260 void disable(void);
261 /// Enable propagators in space
262 void enable(void);
263 /// Prune values also in a space \a c with disabled propagators, but not those in assignment \a a
264 bool disabled(const SetAssignment& a, SetTestSpace& c, Gecode::Support::RandomGenerator& rand);
265 /// Check whether propagation is the same as in \a c
266 bool same(SetTestSpace& c);
267 };
268
269 /**
270 * \brief %Base class for tests with set constraints
271 *
272 */
273 class SetTest : public Base {
274 private:
275 /// Number of variables
276 int arity;
277 /// Domain of variables (least upper bound)
278 Gecode::IntSet lub;
279 /// Does the constraint also exist as reified constraint
280 bool reified;
281 /// Number of additional integer variables
282 int withInt;
283
284 /// Remove \a v values from the least upper bound of \a x, but not those in \f$\mathrm{a}_i\f$
285 void removeFromLub(int v, Gecode::SetVar& x, int i,
286 const Gecode::IntSet& a);
287 /// Add \a v values to the greatest lower bound of \a x, but not those in \f$\mathrm{a}_i\f$
288 void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a);
289 /// Generate a set assignment
290 SetAssignment* make_assignment(void);
291 protected:
292 /// Whether to perform full tests for disabled propagators
293 bool disabled;
294 /// Whether to check for subsumption
295 bool testsubsumed;
296 public:
297 /**
298 * \brief Constructor
299 *
300 * Constructs a test with name \a s and arity \a a and variable
301 * domain \a d. Also tests for a reified constraint,
302 * if \a r is true. In addition, \a w integer variables are provided.
303 */
304 SetTest(const std::string& s,
305 int a, const Gecode::IntSet& d, bool r=false, int w=0)
306 : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w),
307 disabled(true), testsubsumed(true) {}
308 /// Check for solution
309 virtual bool solution(const SetAssignment&) const = 0;
310 /// Post propagator
311 virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
312 Gecode::IntVarArray& y) = 0;
313 /// Post reified propagator
314 virtual void post(Gecode::Space&, Gecode::SetVarArray&,
315 Gecode::IntVarArray&, Gecode::Reify) {}
316 /// Perform test
317 virtual bool run(void);
318
319 /// \name Mapping scalar values to strings
320 //@{
321 /// Map set relation to string
322 static std::string str(Gecode::SetRelType srt);
323 /// Map set operation to string
324 static std::string str(Gecode::SetOpType srt);
325 /// Map integer to string
326 static std::string str(int i);
327 /// Map integer array to string
328 static std::string str(const Gecode::IntArgs& i);
329 //@}
330 };
331 //@}
332
333 /// Iterator for set relation types
334 class SetRelTypes {
335 private:
336 /// Array of relation types
337 static const Gecode::SetRelType srts[6];
338 /// Current position in relation type array
339 int i;
340 public:
341 /// Initialize iterator
342 SetRelTypes(void);
343 /// Test whether iterator is done
344 bool operator()(void) const;
345 /// Increment to next relation type
346 void operator++(void);
347 /// Return current relation type
348 Gecode::SetRelType srt(void) const;
349 };
350
351 /// Iterator for Boolean operation types
352 class SetOpTypes {
353 private:
354 /// Array of operation types
355 static const Gecode::SetOpType sots[4];
356 /// Current position in operation type array
357 int i;
358 public:
359 /// Initialize iterator
360 SetOpTypes(void);
361 /// Test whether iterator is done
362 bool operator()(void) const;
363 /// Increment to next operation type
364 void operator++(void);
365 /// Return current operation type
366 Gecode::SetOpType sot(void) const;
367 };
368
369}}
370
371/**
372 * \brief Print assignment \a
373 * \relates SetAssignment
374 */
375std::ostream&
376operator<<(std::ostream&, const Test::Set::SetAssignment& a);
377
378#include "test/set.hpp"
379
380#endif
381
382// STATISTICS: test-set