File: int.hh

package info (click to toggle)
gecode 3.4.0-1
  • links: PTS
  • area: main
  • in suites: squeeze
  • size: 10,136 kB
  • ctags: 16,905
  • sloc: cpp: 124,581; perl: 2,004; makefile: 1,453; sh: 247
file content (353 lines) | stat: -rwxr-xr-x 11,981 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2005
 *     Mikael Lagerkvist, 2006
 *
 *  Last modified:
 *     $Date: 2010-06-03 13:11:11 +0200 (Thu, 03 Jun 2010) $ by $Author: tack $
 *     $Revision: 11013 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#ifndef __GECODE_TEST_INT_HH__
#define __GECODE_TEST_INT_HH__

#include "test/test.hh"

#include <gecode/int.hh>

namespace Test {

  /// Testing finite domain integers
  namespace Int {

    /**
     * \defgroup TaskTestInt Testing finite domain integers
     * \ingroup TaskTest
     */

    /**
     * \defgroup TaskTestIntInt General test support
     * \ingroup TaskTestInt
     */
    //@{
    /// %Base class for assignments
    class Assignment {
    protected:
      int n;            ///< Number of variables
      Gecode::IntSet d; ///< Domain for each variable
    public:
      /// Initialize assignments for \a n0 variables and values \a d0
      Assignment(int n0, const Gecode::IntSet& d0);
      /// Test whether all assignments have been iterated
      virtual bool operator()(void) const = 0;
      /// Move to next assignment
      virtual void operator++(void) = 0;
      /// Return value for variable \a i
      virtual int operator[](int i) const = 0;
      /// Return number of variables
      int size(void) const;
      /// Destructor
      virtual ~Assignment(void);
    };

    /// Generate all assignments
    class CpltAssignment : public Assignment {
    protected:
      Gecode::IntSetValues* dsv; ///< Iterator for each variable
    public:
      /// Initialize assignments for \a n0 variables and values \a d0
      CpltAssignment(int n, const Gecode::IntSet& d);
      /// Test whether all assignments have been iterated
      virtual bool operator()(void) const;
      /// Move to next assignment
      virtual void operator++(void);
      /// Return value for variable \a i
      virtual int operator[](int i) const;
      /// Destructor
      virtual ~CpltAssignment(void);
    };

    /// Generate random selection of assignments
    class RandomAssignment : public Assignment {
    protected:
      int* vals; ///< The current values for the variables
      int  a;    ///< How many assigments still to be generated
      /// Generate new value according to domain
      int randval(void);
    public:
      /// Initialize for \a a assignments for \a n0 variables and values \a d0
      RandomAssignment(int n, const Gecode::IntSet& d, int a);
      /// Test whether all assignments have been iterated
      virtual bool operator()(void) const;
      /// Move to next assignment
      virtual void operator++(void);
      /// Return value for variable \a i
      virtual int operator[](int i) const;
      /// Destructor
      virtual ~RandomAssignment(void);
    };

    /// Generate random selection of assignments
    class RandomMixAssignment : public Assignment {
    protected:
      int* vals; ///< The current values for the variables
      int  a;    ///< How many assigments still to be generated
      int _n1;   ///< How many variables in the second set
      Gecode::IntSet _d1; ///< Domain for second set of variables
      /// Generate new value according to domain \a d
      int randval(const Gecode::IntSet& d);
    public:
      /// Initialize for \a a assignments for \a n0 variables and values \a d0
      RandomMixAssignment(int n0, const Gecode::IntSet& d0,
                          int n1, const Gecode::IntSet& d1, int a0);
      /// Test whether all assignments have been iterated
      virtual bool operator()(void) const;
      /// Move to next assignment
      virtual void operator++(void);
      /// Return value for variable \a i
      virtual int operator[](int i) const;
      /// Destructor
      virtual ~RandomMixAssignment(void);
    };

    /// Level of consistency to test for
    enum ConTestLevel {
      CTL_NONE,     ///< No consistency-test
      CTL_DOMAIN,   ///< Test for domain-consistency
      CTL_BOUNDS_D, ///< Test for bounds(d)-consistency
      CTL_BOUNDS_Z, ///< Test for bounds(z)-consistency
    };

    class Test;

    /// Space for executing tests
    class TestSpace : public Gecode::Space {
    public:
      /// Initial domain
      Gecode::IntSet d;
      /// Variables to be tested
      Gecode::IntVarArray x;
      /// Control variable for reified propagators
      Gecode::BoolVar b;
      /// Whether the test is for a reified propagator
      bool reified;
      /// The test currently run
      Test* test;

      /**
       * \brief Create test space
       *
       * Creates \a n variables with domain \a d0 and stores whether
       * the test is for a reified propagator (\a r), and the test itself
       * (\a t).
       *
       */
      TestSpace(int n, Gecode::IntSet& d0, bool r, Test* t, bool log=true);
      /// Constructor for cloning \a s
      TestSpace(bool share, TestSpace& s);
      /// Copy space during cloning
      virtual Gecode::Space* copy(bool share);
      /// Test whether all variables are assigned
      bool assigned(void) const;
      /// Post propagator
      void post(void);
      /// Compute a fixpoint and check for failure
      bool failed(void);
      /// Perform integer tell operation on \a x[i]
      void rel(int i, Gecode::IntRelType irt, int n);
      /// Perform Boolean tell on \a b
      void rel(bool sol);
      /// Assign all (or all but one, if \a skip is true) variables to values in \a a
      void assign(const Assignment& a, bool skip=false);
      /// Assing a random variable to a random bound
      void bound(void);
      /** \brief Prune some random values from variable \a i
       *
       * If \a bounds_only is true, then the pruning is only done on the
       * bounds of the variable.
       */
      void prune(int i, bool bounds_only);
      /// Prune some random values for some random variable
      void prune(void);
      /// Prune values but not those in assignment \a a
      bool prune(const Assignment& a, bool testfix);
    };

    /**
     * \brief %Base class for tests with integer constraints
     *
     */
    class Test : public Base {
    protected:
      /// Number of variables
      int arity;
      /// Domain of variables
      Gecode::IntSet dom;
      /// Does the constraint also exist as reified constraint
      bool reified;
      /// Consistency level
      Gecode::IntConLevel icl;
      /// Whether to test for certain consistency
      ConTestLevel contest;
      /// Whether to perform search test
      bool testsearch;
      /// Whether to perform fixpoint test
      bool testfix;

    public:
      /**
       * \brief Constructor
       *
       * Constructs a test with name \a s and arity \a a and variable
       * domain \a d. Also tests for a reified constraint,
       * if \a r is true. The consistency level is
       * maintained for convenience.
       */
      Test(const std::string& s, int a, const Gecode::IntSet& d, bool r=false,
           Gecode::IntConLevel i=Gecode::ICL_DEF);
      /**
       * \brief Constructor
       *
       * Constructs a test with name \a s and arity \a a and variable
       * domain \a min ... \a max. Also tests for a reified constraint,
       * if \a r is true. The consistency level is
       * maintained for convenience.
       */
      Test(const std::string& s, int a, int min, int max, bool r=false,
           Gecode::IntConLevel i=Gecode::ICL_DEF);
      /// Create assignment
      virtual Assignment* assignment(void) const;
      /// Check for solution
      virtual bool solution(const Assignment&) const = 0;
      /// Whether to ignore assignment for reification
      virtual bool ignore(const Assignment&) const;
      /// Post constraint
      virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) = 0;
      /// Post reified constraint
      virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
                        Gecode::BoolVar b);
      /// Perform test
      virtual bool run(void);
      /// \name Mapping scalar values to strings
      //@{
      /// Map extensional propagation kind to string
      static std::string str(Gecode::ExtensionalPropKind epk);
      /// Map integer consistency level to string
      static std::string str(Gecode::IntConLevel icl);
      /// Map integer relation to string
      static std::string str(Gecode::IntRelType irl);
      /// Map Boolean operation to string
      static std::string str(Gecode::BoolOpType bot);
      /// Map integer to string
      static std::string str(int i);
      /// Map integer array to string
      static std::string str(const Gecode::IntArgs& i);
      //@}
      /// \name General support
      //@{
      /// Compare \a x and \a y with respect to \a r
      template<class T> static bool cmp(T x, Gecode::IntRelType r, T y);
      //@}
    };
    //@}

    /// Iterator for integer consistency levels
    class IntConLevels {
    private:
      /// Array of consistency levels
      static const Gecode::IntConLevel icls[3];
      /// Current position in level array
      int i;
    public:
      /// Initialize iterator
      IntConLevels(void);
      /// Test whether iterator is done
      bool operator()(void) const;
      /// Increment to next level
      void operator++(void);
      /// Return current level
      Gecode::IntConLevel icl(void) const;
    };

    /// Iterator for integer relation types
    class IntRelTypes {
    private:
      /// Array of relation types
      static const Gecode::IntRelType irts[6];
      /// Current position in relation type array
      int i;
    public:
      /// Initialize iterator
      IntRelTypes(void);
      /// Reset iterator
      void reset(void);
      /// Test whether iterator is done
      bool operator()(void) const;
      /// Increment to next relation type
      void operator++(void);
      /// Return current relation type
      Gecode::IntRelType irt(void) const;
    };

    /// Iterator for Boolean operation types
    class BoolOpTypes {
    private:
      /// Array of operation types
      static const Gecode::BoolOpType bots[5];
      /// Current position in operation type array
      int i;
    public:
      /// Initialize iterator
      BoolOpTypes(void);
      /// Test whether iterator is done
      bool operator()(void) const;
      /// Increment to next operation type
      void operator++(void);
      /// Return current operation type
      Gecode::BoolOpType bot(void) const;
    };

  }
}

/**
 * \brief Print assignment \a
 * \relates Assignment
 */
std::ostream& operator<<(std::ostream& os, const Test::Int::Assignment& a);

#include "test/int.hpp"

#endif

// STATISTICS: test-int