← Back to branch summary

~ubuntu-branches/ubuntu/natty/gecode/natty

« back to all changes in this revision

Viewing changes to test/int.cc

  • Committer: Bazaar Package Importer
  • Author(s): Kari Pahula
  • Date: 2005-12-24 07:51:25 UTC
  • Revision ID: james.westby@ubuntu.com-20051224075125-klkiqofvbfvusfvt
Tags: upstream-1.0.0.dfsg.1
Import upstream version 1.0.0.dfsg.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
test/int.cc
 
1
/*
 
2
 *  Main authors:
 
3
 *     Christian Schulte <schulte@gecode.org>
 
4
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 
5
 *
 
6
 *  Copyright:
 
7
 *     Christian Schulte, 2005
 
8
 *     Mikael Lagerkvist, 2005
 
9
 *
 
10
 *  Last modified:
 
11
 *     $Date: 2005-12-02 14:47:51 +0100 (Fri, 02 Dec 2005) $ by $Author: zayenz $
 
12
 *     $Revision: 2688 $
 
13
 *
 
14
 *  This file is part of Gecode, the generic constraint
 
15
 *  development environment:
 
16
 *     http://www.gecode.org
 
17
 *
 
18
 *  See the file "LICENSE" for information on usage and
 
19
 *  redistribution of this file, and for a
 
20
 *     DISCLAIMER OF ALL WARRANTIES.
 
21
 *
 
22
 */
 
23
 
 
24
#include "test/int.hh"
 
25
#include "test/log.hh"
 
26
#include <algorithm>
 
27
 
 
28
Assignment::Assignment(int n0, const IntSet& d0)
 
29
  : n(n0), dsv(new IntSetValues[n]), d(d0) {
 
30
  reset();
 
31
}
 
32
 
 
33
void 
 
34
Assignment::reset(void) {
 
35
  done = false;
 
36
  for (int i=n; i--; )
 
37
    dsv[i].init(d);
 
38
}
 
39
 
 
40
void 
 
41
Assignment::operator++(void) {
 
42
  int i = n-1;
 
43
  while (true) {
 
44
    ++dsv[i];
 
45
    if (dsv[i]())
 
46
      return;
 
47
    dsv[i].init(d);
 
48
    --i;
 
49
    if (i<0) {
 
50
      done = true;
 
51
      return;
 
52
    }
 
53
  }
 
54
}
 
55
 
 
56
std::ostream&
 
57
operator<<(std::ostream& os, const Assignment& a) {
 
58
  int n = a.size();
 
59
  os << "{";
 
60
  for (int i=0; i<n; i++)
 
61
    os << a[i] << ((i!=n-1) ? "," : "}");
 
62
  return os;
 
63
}
 
64
 
 
65
#define FORCE_FIXFLUSH                          \
 
66
do {                                            \
 
67
  if (random(opt.fixprob) == 0) {               \
 
68
    unsigned int alt;                           \
 
69
    Log::fixpoint();                            \
 
70
    if (status(alt) == SS_FAILED) return;       \
 
71
  }                                             \
 
72
  if (random(opt.flushprob) == 0) {             \
 
73
    flush();                                    \
 
74
    Log::flush();                               \
 
75
  }                                             \
 
76
} while(0)
 
77
 
 
78
class IntTestSpace : public Space {
 
79
public:
 
80
  IntVarArray x;
 
81
private:
 
82
  const Options opt;
 
83
 
 
84
public:
 
85
  IntTestSpace(int n, IntSet& d, const Options& o) 
 
86
    : x(this, n, d), opt(o) {
 
87
    Log::initial(x, "x");
 
88
  }
 
89
  IntTestSpace(bool share, IntTestSpace& s) : Space(share,s), opt(s.opt) {
 
90
    x.update(this, share, s.x);
 
91
  }
 
92
  virtual Space* copy(bool share) {
 
93
    return new IntTestSpace(share,*this);
 
94
  }
 
95
  bool is_failed(void) {
 
96
    unsigned int alt;
 
97
    Log::fixpoint();
 
98
    return status(alt) == SS_FAILED;
 
99
  }
 
100
  void assign(const Assignment& a) {
 
101
    for (int i=a.size(); i--; ) {
 
102
      Log::assign(Log::mk_name("x", i), a[i]);
 
103
      rel(this, x[i], IRT_EQ, a[i]);
 
104
      FORCE_FIXFLUSH;
 
105
    }
 
106
  }
 
107
  bool assigned(void) const {
 
108
    for (int i=x.size(); i--; )
 
109
      if (!x[i].assigned())
 
110
        return false;
 
111
    return true;
 
112
  }
 
113
  void prune(const Assignment& a) {
 
114
    // Select variable to be pruned
 
115
    int i = random(x.size());
 
116
    while (x[i].assigned()) {
 
117
      i = (i+1) % x.size();
 
118
    }
 
119
    // Select mode for pruning
 
120
    int m=random(3);
 
121
    if ((m == 0) && (a[i] < x[i].max())) {
 
122
      int v=a[i]+1+random(static_cast<unsigned int>(x[i].max()-a[i]));
 
123
      assert((v > a[i]) && (v <= x[i].max()));
 
124
      Log::prune(x[i], Log::mk_name("x", i), IRT_LE, v);
 
125
      rel(this, x[i], IRT_LE, v);
 
126
      Log::prune_result(x[i]);
 
127
    } else if ((m == 1) && (a[i] > x[i].min())) {
 
128
      int v=x[i].min()+random(static_cast<unsigned int>(a[i]-x[i].min()));
 
129
      assert((v < a[i]) && (v >= x[i].min()));
 
130
      Log::prune(x[i], Log::mk_name("x", i), IRT_GR, v);
 
131
      rel(this, x[i], IRT_GR, v);
 
132
      Log::prune_result(x[i]);
 
133
    } else  {
 
134
      int v;
 
135
      Int::ViewRanges<Int::IntView> it(x[i]);
 
136
      unsigned int skip = random(x[i].size()-1);
 
137
      while (true) {
 
138
        if (it.width() > skip) {
 
139
          v = it.min() + skip;
 
140
          if (v == a[i]) {
 
141
            if (it.width() == 1) {
 
142
              ++it; v = it.min();
 
143
            } else if (v < it.max()) {
 
144
              ++v;
 
145
            } else {
 
146
              --v;
 
147
            }
 
148
          }
 
149
          break;
 
150
        }
 
151
        skip -= it.width();
 
152
        ++it;
 
153
      }
 
154
      Log::prune(x[i], Log::mk_name("x", i), IRT_NQ, v);
 
155
      rel(this, x[i], IRT_NQ, v);
 
156
      Log::prune_result(x[i]);
 
157
    }
 
158
 
 
159
    FORCE_FIXFLUSH;
 
160
  }
 
161
  
 
162
};
 
163
 
 
164
 
 
165
Assignment* 
 
166
IntTest::make_assignment() {
 
167
  return new Assignment(arity, dom);
 
168
}
 
169
/*
 
170
bool
 
171
IntTest::do_search_test() {
 
172
  return true;
 
173
}
 
174
*/
 
175
#define CHECK(T,M)                              \
 
176
if (!(T)) {                                     \
 
177
  problem = (M);                                \
 
178
  delete s;                                     \
 
179
  goto failed;                                  \
 
180
}
 
181
 
 
182
bool 
 
183
IntTest::run(const Options& opt) {
 
184
  const char* test    = "NONE";
 
185
  const char* problem = "NONE";
 
186
  // Set up assignments
 
187
  Assignment* ap = make_assignment();
 
188
  Assignment& a = *ap;
 
189
  // Set up space for all solution search
 
190
  IntTestSpace* search_s = new IntTestSpace(arity,dom,opt);
 
191
  post(search_s,search_s->x);
 
192
  branch(search_s,search_s->x,BVAR_NONE,BVAL_MIN);
 
193
  Gecode::DFS<IntTestSpace> e_s(search_s);
 
194
  delete search_s;
 
195
  while (a()) {
 
196
    bool is_sol = solution(a);
 
197
    if (do_search_test()) {
 
198
      test = "Search";
 
199
      if (is_sol) {
 
200
        IntTestSpace* s = e_s.next();
 
201
        CHECK(s != NULL,    "Solutions exhausted");
 
202
        CHECK(!s->actors(), "No subsumtion");
 
203
        for (int i=a.size(); i--; ) {
 
204
          CHECK(s->x[i].assigned(), "Unassigned variable");
 
205
          CHECK(a[i] == s->x[i].val(), "Wrong value in solution");
 
206
        }
 
207
        delete s;
 
208
      }
 
209
    }
 
210
    {
 
211
      test = "Assignment (after posting)";
 
212
      Log::reset();
 
213
      IntTestSpace* s = new IntTestSpace(arity,dom,opt);
 
214
      post(s,s->x); s->assign(a);
 
215
      if (is_sol) {
 
216
        CHECK(!s->is_failed(), "Failed on solution");
 
217
        CHECK(!s->actors(), "No subsumtion");
 
218
      } else {
 
219
        CHECK(s->is_failed(), "Solved on non-solution");
 
220
      }
 
221
      delete s;
 
222
    }
 
223
    {
 
224
      test = "Assignment (before posting)";
 
225
      Log::reset();
 
226
      IntTestSpace* s = new IntTestSpace(arity,dom,opt);
 
227
      s->assign(a); post(s,s->x);
 
228
      if (is_sol) {
 
229
        CHECK(!s->is_failed(), "Failed on solution");
 
230
        CHECK(!s->actors(), "No subsumtion");
 
231
      } else {
 
232
        CHECK(s->is_failed(), "Solved on non-solution");
 
233
      }
 
234
      delete s;
 
235
    }
 
236
    if (reified) {
 
237
      test = "Assignment reified (before posting)";
 
238
      Log::reset();
 
239
      IntTestSpace* s = new IntTestSpace(arity,dom,opt);
 
240
      BoolVar b(s,0,1); 
 
241
      s->assign(a); post(s,s->x,b);
 
242
      CHECK(!s->is_failed(), "Failed");
 
243
      CHECK(!s->actors(), "No subsumtion");
 
244
      CHECK(b.assigned(), "Control variable unassigned");
 
245
      if (is_sol) {
 
246
        CHECK(b.val()==1, "Zero on solution");
 
247
      } else {
 
248
        CHECK(b.val()==0, "One on non-solution");
 
249
      }
 
250
      delete s;
 
251
    }
 
252
    if (reified) {
 
253
      test = "Assignment reified (after posting)";
 
254
      Log::reset();
 
255
      IntTestSpace* s = new IntTestSpace(arity,dom,opt);
 
256
      BoolVar b(s,0,1);
 
257
      post(s,s->x,b); s->assign(a);
 
258
      CHECK(!s->is_failed(), "Failed");
 
259
      CHECK(!s->actors(), "No subsumtion");
 
260
      CHECK(b.assigned(), "Control variable unassigned");
 
261
      if (is_sol) {
 
262
        CHECK(b.val()==1, "Zero on solution");
 
263
      } else {
 
264
        CHECK(b.val()==0, "One on non-solution");
 
265
      }
 
266
      delete s;
 
267
    }
 
268
    {
 
269
      test = "Prune";
 
270
      Log::reset();
 
271
      IntTestSpace* s = new IntTestSpace(arity,dom,opt);
 
272
      post(s,s->x);
 
273
      while (!s->failed() && !s->assigned())
 
274
        s->prune(a);
 
275
      s->assign(a);
 
276
      if (is_sol) {
 
277
        CHECK(!s->is_failed(), "Failed on solution");
 
278
        CHECK(!s->actors(), "No subsumtion");
 
279
      } else {
 
280
        CHECK(s->is_failed(), "Solved on non-solution");
 
281
      }
 
282
      delete s;
 
283
    }
 
284
    if (reified) {
 
285
      test = "Prune reified";
 
286
      Log::reset();
 
287
      IntTestSpace* s = new IntTestSpace(arity,dom,opt);
 
288
      BoolVar b(s,0,1);
 
289
      post(s,s->x,b);
 
290
      while (!s->failed() && !s->assigned() && !b.assigned())
 
291
        s->prune(a);
 
292
      CHECK(!s->is_failed(), "Failed");
 
293
      CHECK(!s->actors(), "No subsumtion");
 
294
      CHECK(b.assigned(), "Control variable unassigned");
 
295
      if (is_sol) {
 
296
        CHECK(b.val()==1, "Zero on solution");
 
297
      } else {
 
298
        CHECK(b.val()==0, "One on non-solution");
 
299
      }
 
300
      delete s;
 
301
    }
 
302
    ++a;
 
303
  }
 
304
  if (do_search_test()) {
 
305
    test = "Search";
 
306
    if (e_s.next() != NULL) {
 
307
      problem = "Excess solutions";
 
308
      goto failed;
 
309
    }
 
310
  }
 
311
  delete ap;
 
312
  return true;
 
313
 failed:
 
314
  std::cout << "FAILURE" << std::endl
 
315
            << "\t" << "Test:       " << test << std::endl
 
316
            << "\t" << "Problem:    " << problem << std::endl
 
317
            << "\t" << "Assignment: " << a << std::endl;
 
318
  delete ap;
 
319
  return false;
 
320
}
 
321
 
 
322
#undef CHECK
 
323
 
 
324
// STATISTICS: test-int
 
325