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 *
6 * Copyright:
7 * Guido Tack, 2005
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include "test/set.hh"
35#include "test/int.hh"
36#include <gecode/minimodel.hh>
37
38using namespace Gecode;
39
40namespace Test { namespace Set {
41
42 /// %Tests for set channeling constraints
43 namespace Channel {
44
45 /**
46 * \defgroup TaskTestSetChannel %Set channeling constraints
47 * \ingroup TaskTestSet
48 */
49 //@{
50
51 static IntSet d1(0,2);
52 static IntSet d_12(-1,2);
53
54 static IntSet d2(-1,3);
55 static IntSet d3(0,3);
56
57 static IntSet d4(0,4);
58
59 static IntSet ds_33(-3,3);
60
61 /// %Test for sorted channeling constraint
62 class ChannelSorted : public SetTest {
63 public:
64 /// Create and register test
65 ChannelSorted(const char* t)
66 : SetTest(t,1,ds_33,false,3) {}
67 /// %Test whether \a x is solution
68 virtual bool solution(const SetAssignment& x) const {
69 if (x.ints()[0]>=x.ints()[1] ||
70 x.ints()[1]>=x.ints()[2])
71 return false;
72 CountableSetValues xr(x.lub, x[0]);
73 if (!xr())
74 return false;
75 if (xr.val() != x.ints()[0])
76 return false;
77 ++xr;
78 if (!xr())
79 return false;
80 if (xr.val() != x.ints()[1])
81 return false;
82 ++xr;
83 if (!xr())
84 return false;
85 if (xr.val() != x.ints()[2])
86 return false;
87 ++xr;
88 if (xr())
89 return false;
90 return true;
91 }
92 /// Post constraint on \a x
93 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
94 Gecode::channelSorted(home, y, x[0]);
95 }
96 };
97 ChannelSorted _channelSorted("Channel::Sorted");
98
99 /// %Test for integer channel constraint
100 class ChannelInt : public SetTest {
101 private:
102 int ssize, isize;
103 public:
104 /// Create and register test
105 ChannelInt(const char* t, const IntSet& d, int _ssize, int _isize)
106 : SetTest(t,_ssize,d,false,_isize), ssize(_ssize), isize(_isize) {}
107 /// %Test whether \a x is solution
108 virtual bool solution(const SetAssignment& x) const {
109 for (int i=0; i<isize; i++) {
110 if (x.ints()[i] < 0 || x.ints()[i] >= ssize)
111 return false;
112 Iter::Ranges::Singleton single(i,i);
113 CountableSetRanges csr(x.lub, x[x.ints()[i]]);
114 if (!Iter::Ranges::subset(single, csr))
115 return false;
116 }
117 for (int i=0; i<ssize; i++) {
118 int size = 0;
119 for (CountableSetValues csv(x.lub, x[i]); csv(); ++csv) {
120 if (csv.val() < 0 || csv.val() >= isize) return false;
121 if (x.ints()[csv.val()] != i) return false;
122 size++;
123 }
124 }
125 return true;
126 }
127 /// Post constraint on \a x
128 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
129 Gecode::channel(home, y, x);
130 }
131 };
132
133 ChannelInt _channelint1("Channel::Int::1", d2, 2, 3);
134 ChannelInt _channelint2("Channel::Int::2", d3, 3, 3);
135
136 /// %Test for Boolean channel constraint
137 class ChannelBool : public SetTest {
138 private:
139 int isize;
140 public:
141 /// Create and register test
142 ChannelBool(const char* t, const IntSet& d, int _isize)
143 : SetTest(t,1,d,false,_isize), isize(_isize) {}
144 /// %Test whether \a x is solution
145 virtual bool solution(const SetAssignment& x) const {
146 for (int i=0; i<isize; i++) {
147 if (x.ints()[i] < 0 || x.ints()[i] > 1)
148 return false;
149 }
150 int cur = 0;
151 for (CountableSetValues csv(x.lub, x[0]); csv(); ++csv) {
152 if (csv.val() < 0 || csv.val() >= isize) return false;
153 if (x.ints()[csv.val()] != 1) return false;
154 for (; cur<csv.val(); cur++)
155 if (x.ints()[cur] != 0) return false;
156 cur = csv.val() + 1;
157 }
158 for (; cur<isize; cur++)
159 if (x.ints()[cur] != 0) return false;
160 return true;
161 }
162 /// Post constraint on \a x
163 virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
164 BoolVarArgs b(y.size());
165 for (int i=y.size(); i--;)
166 b[i] = channel(home, y[i]);
167 Gecode::channel(home, b, x[0]);
168 }
169 };
170
171 ChannelBool _channelbool1("Channel::Bool::1", d2, 3);
172 ChannelBool _channelbool2("Channel::Bool::2", d3, 3);
173 ChannelBool _channelbool3("Channel::Bool::3", d4, 5);
174
175 /// %Test for set channel constraint
176 class ChannelSet : public SetTest {
177 private:
178 int _x0size, _x1size;
179 public:
180 /// Create and register test
181 ChannelSet(const char* t, const IntSet& d, int x0size, int x1size)
182 : SetTest(t,x0size+x1size,d,false), _x0size(x0size), _x1size(x1size) {}
183 /// %Test whether \a x is solution
184 virtual bool solution(const SetAssignment& x) const {
185 for (int i=0; i<_x0size; i++) {
186 CountableSetRanges x0ir(x.lub, x[i]);
187 IntSet x0is(x0ir);
188 if (x0is.min() < 0 || x0is.max() >= _x1size)
189 return false;
190 for (int j=0; j<_x1size; j++) {
191 CountableSetRanges x1ir(x.lub, x[_x0size+j]);
192 IntSet x1is(x1ir);
193 if (x1is.min() < 0 || x1is.max() >= _x0size)
194 return false;
195 bool jInI = x0is.in(j);
196 bool iInJ = x1is.in(i);
197 if (jInI != iInJ)
198 return false;
199 }
200 }
201 return true;
202 }
203 /// Post constraint on \a x
204 virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
205 SetVarArgs x0(x.slice(0,1,_x0size));
206 SetVarArgs x1(x.slice(_x0size));
207 Gecode::channel(home, x0,x1);
208 }
209 };
210
211 ChannelSet _channelSet12("Channel::Set::1::2", d1, 2,2);
212 ChannelSet _channelSet13("Channel::Set::1::3", d1, 2,3);
213 ChannelSet _channelSet22("Channel::Set::2::2", d3, 2,2);
214 ChannelSet _channelSet23("Channel::Set::2::3", d3, 2,3);
215 ChannelSet _channelSet32("Channel::Set::3::2", d_12, 2,2);
216 ChannelSet _channelSet33("Channel::Set::3::3", d_12, 2,3);
217
218}}}
219
220// STATISTICS: test-set