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 <gecode/minimodel.hh>
35
36#include "test/set.hh"
37
38using namespace Gecode;
39
40namespace Test { namespace Set {
41
42 /// %Tests for relation constraints
43 namespace Rel {
44
45 /**
46 * \defgroup TaskTestSetRel Relation constraints
47 * \ingroup TaskTestSet
48 */
49 //@{
50
51 static IntSet ds_33(-3,3);
52 static IntSet ds_03(0,3);
53
54 /// %Test for binary set relation constraint
55 class RelBin : public SetTest {
56 private:
57 Gecode::SetRelType srt;
58 bool shared;
59 public:
60 /// Create and register test
61 RelBin(Gecode::SetRelType srt0, bool shared0)
62 : SetTest("Rel::Bin::"+str(srt0)+"::S"+(shared0 ? "1":"0"),
63 shared0 ? 1 : 2,ds_33,true)
64 , srt(srt0), shared(shared0){}
65 int minSymDiff(const SetAssignment& x) const {
66 int x1 = shared ? x[0] : x[1];
67 typedef Iter::Ranges::Diff<CountableSetRanges,CountableSetRanges> Diff;
68 CountableSetRanges xr00(x.lub, x[0]);
69 CountableSetRanges xr10(x.lub, x1);
70 Diff a(xr00,xr10);
71 CountableSetRanges xr01(x.lub, x[0]);
72 CountableSetRanges xr11(x.lub, x1);
73 Diff b(xr11,xr01);
74 Iter::Ranges::Union<Diff,Diff> u(a,b);
75 return u() ? u.min() : Gecode::Set::Limits::max+1;
76 }
77 bool in(int i, CountableSetRanges& c, bool eq=false) const {
78 if (eq && i==Gecode::Set::Limits::max+1)
79 return true;
80 Iter::Ranges::Singleton s(i,i);
81 return Iter::Ranges::subset(s,c);
82 }
83 /// %Test whether \a x is solution
84 bool solution(const SetAssignment& x) const {
85 int x1 = shared ? x[0] : x[1];
86 CountableSetRanges xr0(x.lub, x[0]);
87 CountableSetRanges xr1(x.lub, x1);
88 switch (srt) {
89 case SRT_EQ: return Iter::Ranges::equal(xr0, xr1);
90 case SRT_NQ: return !Iter::Ranges::equal(xr0, xr1);
91
92 case SRT_LQ: return (!xr0()) || in(minSymDiff(x),xr1,true);
93 case SRT_LE: return xr0() ? in(minSymDiff(x),xr1) : xr1();
94 case SRT_GQ: return (!xr1()) || in(minSymDiff(x),xr0,true);
95 case SRT_GR: return xr1() ? in(minSymDiff(x),xr0) : xr0();
96
97 case SRT_SUB: return Iter::Ranges::subset(xr0, xr1);
98 case SRT_SUP: return Iter::Ranges::subset(xr1, xr0);
99 case SRT_DISJ:
100 {
101 Iter::Ranges::Inter<CountableSetRanges,CountableSetRanges>
102 inter(xr0,xr1);
103 return !inter();
104 }
105 case SRT_CMPL:
106 {
107 Gecode::Set::RangesCompl<CountableSetRanges> rc(xr0);
108 return Iter::Ranges::equal(rc,xr1);
109 }
110 default:
111 GECODE_NEVER;
112 }
113 GECODE_NEVER;
114 return false;
115 }
116 /// Post constraint on \a x
117 void post(Space& home, SetVarArray& x, IntVarArray&) {
118 if (!shared)
119 Gecode::rel(home, x[0], srt, x[1]);
120 else
121 Gecode::rel(home, x[0], srt, x[0]);
122 }
123 /// Post reified constraint on \a x for \a b
124 void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
125 if (!shared)
126 Gecode::rel(home, x[0], srt, x[1], r);
127 else
128 Gecode::rel(home, x[0], srt, x[0], r);
129 }
130 };
131
132 /// %Test for if-then-else-constraint
133 class ITE : public SetTest {
134 public:
135 /// Construct and register test
136 ITE(void)
137 : SetTest("ITE",3,ds_03,false,1) {}
138 /// Check whether \a x is a solution
139 virtual bool solution(const SetAssignment& x) const {
140 if ((x.intval() < 0) || (x.intval() > 1))
141 return false;
142 if (x.intval() == 1) {
143 CountableSetRanges xr0(x.lub, x[0]);
144 CountableSetRanges xr2(x.lub, x[2]);
145 return Iter::Ranges::equal(xr0,xr2);
146 } else {
147 CountableSetRanges xr1(x.lub, x[1]);
148 CountableSetRanges xr2(x.lub, x[2]);
149 return Iter::Ranges::equal(xr1,xr2);
150 }
151 }
152 /// Post constraint on \a x and \a y
153 void post(Space& home, SetVarArray& x, IntVarArray& y) {
154 Gecode::ite(home, Gecode::channel(home,y[0]), x[0], x[1], x[2]);
155 }
156 };
157
158 RelBin _relbin_eq(Gecode::SRT_EQ,false);
159 RelBin _relbin_lq(Gecode::SRT_LQ,false);
160 RelBin _relbin_le(Gecode::SRT_LE,false);
161 RelBin _relbin_gq(Gecode::SRT_GQ,false);
162 RelBin _relbin_gr(Gecode::SRT_GR,false);
163 RelBin _relbin_nq(Gecode::SRT_NQ,false);
164 RelBin _relbin_sub(Gecode::SRT_SUB,false);
165 RelBin _relbin_sup(Gecode::SRT_SUP,false);
166 RelBin _relbin_disj(Gecode::SRT_DISJ,false);
167 RelBin _relbin_cmpl(Gecode::SRT_CMPL,false);
168 RelBin _relbin_shared_eq(Gecode::SRT_EQ,true);
169 RelBin _relbin_shared_lq(Gecode::SRT_LQ,true);
170 RelBin _relbin_shared_le(Gecode::SRT_LE,true);
171 RelBin _relbin_shared_gq(Gecode::SRT_GQ,true);
172 RelBin _relbin_shared_gr(Gecode::SRT_GR,true);
173 RelBin _relbin_shared_nq(Gecode::SRT_NQ,true);
174 RelBin _relbin_shared_sub(Gecode::SRT_SUB,true);
175 RelBin _relbin_shared_sup(Gecode::SRT_SUP,true);
176 RelBin _relbin_shared_disj(Gecode::SRT_DISJ,true);
177 RelBin _relbin_shared_cmpl(Gecode::SRT_CMPL,true);
178
179 ITE _ite;
180 //@}
181
182}}}
183
184// STATISTICS: test-set