Generated on Mon Sep 17 2012 22:20:44 for Gecode by doxygen 1.8.1.1
set.hh
Go to the documentation of this file.
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  * Last modified:
12  * $Date: 2011-07-12 20:49:06 +1000 (Tue, 12 Jul 2011) $ by $Author: tack $
13  * $Revision: 12172 $
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 #ifndef __GECODE_TEST_SET_HH__
41 #define __GECODE_TEST_SET_HH__
42 
43 #include <gecode/set.hh>
44 #include "test/test.hh"
45 #include "test/int.hh"
46 
47 namespace Test {
48 
50  namespace Set {
51 
57 
58  class FakeSpace : public Gecode::Space {
59  public:
61  FakeSpace(void) {}
63  virtual Gecode::Space* copy(bool share) {
64  (void) share;
65  return NULL;
66  }
67  };
68 
74 
77  private:
79  int cur;
80  int i;
81  public:
85  CountableSetValues(const Gecode::IntSet& d0, int cur0)
86  : dv(d0), cur(cur0), i(1) {
87  if (! (i & cur))
88  operator++();
89  }
91  void init(const Gecode::IntSet& d0, int cur0) {
92  dv = d0;
93  cur = cur0;
94  i = 1;
95  if (! (i & cur))
96  operator++();
97  }
99  bool operator()(void) const {
100  return i<=cur;
101  }
103  void operator++(void) {
104  do {
105  ++dv;
106  i = i<<1;
107  } while (! (i & cur) && i<cur);
108  }
110  int val(void) const { return dv.val(); }
111  };
112 
115  : public Gecode::Iter::Values::ToRanges<CountableSetValues> {
116  private:
119  public:
123  CountableSetRanges(const Gecode::IntSet& d, int cur) : v(d, cur) {
125  }
127  void init(const Gecode::IntSet& d, int cur) {
128  v.init(d, cur);
130  }
131  };
132 
134  class CountableSet {
135  private:
137  Gecode::IntSet d;
139  unsigned int cur;
141  unsigned int lubmax;
142  public:
144  CountableSet(const Gecode::IntSet& s);
146  CountableSet(void) {}
148  void init(const Gecode::IntSet& s);
150  bool operator()(void) const { return cur<lubmax; }
152  void operator++(void);
154  int val(void) const;
155  };
156 
159  private:
161  int n;
163  CountableSet* dsv;
167  bool done;
168  public:
172  int withInt;
174  SetAssignment(int n, const Gecode::IntSet& d, int i = 0);
176  bool operator()(void) const { return !done; }
178  void operator++(void);
180  int operator[](int i) const {
181  assert((i>=0) && (i<n));
182  return dsv[i].val();
183  }
185  int intval(void) const { return ir[0]; }
187  const Test::Int::Assignment& ints(void) const { return ir; }
189  int size(void) const { return n; }
191  ~SetAssignment(void) { delete [] dsv; }
192  };
193 
194 
195  class SetTest;
196 
198  class SetTestSpace : public Gecode::Space {
199  public:
207  int withInt;
211  bool reified;
214 
224  SetTestSpace(int n, Gecode::IntSet& d0, int i, bool r, SetTest* t,
225  bool log=true);
227  SetTestSpace(bool share, SetTestSpace& s);
229  virtual Gecode::Space* copy(bool share);
231  void post(void);
233  bool failed(void);
235  void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is);
237  void cardinality(int i, int cmin, int cmax);
239  void rel(int i, Gecode::IntRelType irt, int n);
241  void rel(bool sol);
243  void assign(const SetAssignment& a);
245  bool assigned(void) const;
247  void removeFromLub(int v, int i, const SetAssignment& a);
249  void addToGlb(int v, int i, const SetAssignment& a);
251  bool fixprob(void);
253  bool prune(const SetAssignment& a);
254  };
255 
260  class SetTest : public Base {
261  private:
263  int arity;
265  Gecode::IntSet lub;
267  bool reified;
269  int withInt;
270 
272  void removeFromLub(int v, Gecode::SetVar& x, int i,
273  const Gecode::IntSet& a);
275  void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a);
276  SetAssignment* make_assignment(void);
277  public:
285  SetTest(const std::string& s,
286  int a, const Gecode::IntSet& d, bool r=false, int w=0)
287  : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w) {}
289  virtual bool solution(const SetAssignment&) const = 0;
291  virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
292  Gecode::IntVarArray& y) = 0;
297  virtual bool run(void);
298 
300 
301 
302  static std::string str(Gecode::SetRelType srt);
304  static std::string str(Gecode::SetOpType srt);
306  static std::string str(int i);
308  static std::string str(const Gecode::IntArgs& i);
310  };
312 
314  class SetRelTypes {
315  private:
317  static const Gecode::SetRelType srts[6];
319  int i;
320  public:
322  SetRelTypes(void);
324  bool operator()(void) const;
326  void operator++(void);
328  Gecode::SetRelType srt(void) const;
329  };
330 
332  class SetOpTypes {
333  private:
335  static const Gecode::SetOpType sots[4];
337  int i;
338  public:
340  SetOpTypes(void);
342  bool operator()(void) const;
344  void operator++(void);
346  Gecode::SetOpType sot(void) const;
347  };
348 
349 }}
350 
355 std::ostream&
356 operator<<(std::ostream&, const Test::Set::SetAssignment& a);
357 
358 #include "test/set.hpp"
359 
360 #endif
361 
362 // STATISTICS: test-set