Generated on Sat Feb 7 2015 02:01:16 for Gecode by doxygen 1.8.9.1
rel.cpp
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  *
6  * Copyright:
7  * Guido Tack, 2005
8  *
9  * Last modified:
10  * $Date: 2014-04-29 08:01:25 +0200 (Tue, 29 Apr 2014) $ by $Author: schulte $
11  * $Revision: 14117 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include "test/set.hh"
39 
40 using namespace Gecode;
41 
42 namespace Test { namespace Set {
43 
45  namespace Rel {
46 
52 
53  static IntSet ds_33(-3,3);
54 
56  class RelBin : public SetTest {
57  private:
59  bool shared;
60  public:
62  RelBin(Gecode::SetRelType srt0, bool shared0)
63  : SetTest("Rel::Bin::"+str(srt0)+"::S"+(shared0 ? "1":"0"),
64  shared0 ? 1 : 2,ds_33,true)
65  , srt(srt0), shared(shared0){}
66  int minSymDiff(const SetAssignment& x) const {
67  int x1 = shared ? x[0] : x[1];
69  CountableSetRanges xr00(x.lub, x[0]);
70  CountableSetRanges xr10(x.lub, x1);
71  Diff a(xr00,xr10);
72  CountableSetRanges xr01(x.lub, x[0]);
73  CountableSetRanges xr11(x.lub, x1);
74  Diff b(xr11,xr01);
76  return u() ? u.min() : Gecode::Set::Limits::max+1;
77  }
78  bool in(int i, CountableSetRanges& c, bool eq=false) const {
79  if (eq && i==Gecode::Set::Limits::max+1)
80  return true;
82  return Iter::Ranges::subset(s,c);
83  }
85  bool solution(const SetAssignment& x) const {
86  int x1 = shared ? x[0] : x[1];
87  CountableSetRanges xr0(x.lub, x[0]);
88  CountableSetRanges xr1(x.lub, x1);
89  switch (srt) {
90  case SRT_EQ: return Iter::Ranges::equal(xr0, xr1);
91  case SRT_NQ: return !Iter::Ranges::equal(xr0, xr1);
92 
93  case SRT_LQ: return (!xr0()) || in(minSymDiff(x),xr1,true);
94  case SRT_LE: return xr0() ? in(minSymDiff(x),xr1) : xr1();
95  case SRT_GQ: return (!xr1()) || in(minSymDiff(x),xr0,true);
96  case SRT_GR: return xr1() ? in(minSymDiff(x),xr0) : xr0();
97 
98  case SRT_SUB: return Iter::Ranges::subset(xr0, xr1);
99  case SRT_SUP: return Iter::Ranges::subset(xr1, xr0);
100  case SRT_DISJ:
101  {
103  inter(xr0,xr1);
104  return !inter();
105  }
106  case SRT_CMPL:
107  {
109  return Iter::Ranges::equal(rc,xr1);
110  }
111  default:
112  GECODE_NEVER;
113  }
114  GECODE_NEVER;
115  return false;
116  }
118  void post(Space& home, SetVarArray& x, IntVarArray&) {
119  if (!shared)
120  Gecode::rel(home, x[0], srt, x[1]);
121  else
122  Gecode::rel(home, x[0], srt, x[0]);
123  }
125  void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
126  if (!shared)
127  Gecode::rel(home, x[0], srt, x[1], r);
128  else
129  Gecode::rel(home, x[0], srt, x[0], r);
130  }
131  };
132  RelBin _relbin_eq(Gecode::SRT_EQ,false);
133  RelBin _relbin_lq(Gecode::SRT_LQ,false);
134  RelBin _relbin_le(Gecode::SRT_LE,false);
135  RelBin _relbin_gq(Gecode::SRT_GQ,false);
136  RelBin _relbin_gr(Gecode::SRT_GR,false);
137  RelBin _relbin_nq(Gecode::SRT_NQ,false);
138  RelBin _relbin_sub(Gecode::SRT_SUB,false);
139  RelBin _relbin_sup(Gecode::SRT_SUP,false);
140  RelBin _relbin_disj(Gecode::SRT_DISJ,false);
141  RelBin _relbin_cmpl(Gecode::SRT_CMPL,false);
142  RelBin _relbin_shared_eq(Gecode::SRT_EQ,true);
143  RelBin _relbin_shared_lq(Gecode::SRT_LQ,true);
144  RelBin _relbin_shared_le(Gecode::SRT_LE,true);
145  RelBin _relbin_shared_gq(Gecode::SRT_GQ,true);
146  RelBin _relbin_shared_gr(Gecode::SRT_GR,true);
147  RelBin _relbin_shared_nq(Gecode::SRT_NQ,true);
148  RelBin _relbin_shared_sub(Gecode::SRT_SUB,true);
149  RelBin _relbin_shared_sup(Gecode::SRT_SUP,true);
152 
154 
155 }}}
156 
157 // STATISTICS: test-set
RelBin _relbin_shared_le(Gecode::SRT_LE, true)
bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: rel.cpp:85
SetRelType
Common relation types for sets.
Definition: set.hh:644
Range iterator for singleton range.
RelBin _relbin_le(Gecode::SRT_LE, false)
RelBin _relbin_nq(Gecode::SRT_NQ, false)
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
RelBin(Gecode::SetRelType srt0, bool shared0)
Create and register test.
Definition: rel.cpp:62
Integer variable array.
Definition: int.hh:741
RelBin _relbin_sup(Gecode::SRT_SUP, false)
Superset ( )
Definition: set.hh:648
RelBin _relbin_gr(Gecode::SRT_GR, false)
Complement.
Definition: set.hh:650
const int max
Largest allowed integer in integer set.
Definition: set.hh:99
RelBin _relbin_shared_sub(Gecode::SRT_SUB, true)
Computation spaces.
Definition: core.hpp:1362
RelBin _relbin_sub(Gecode::SRT_SUB, false)
RelBin _relbin_lq(Gecode::SRT_LQ, false)
int min(void) const
Return smallest value of range.
RelBin _relbin_cmpl(Gecode::SRT_CMPL, false)
Test for binary set relation constraint
Definition: rel.cpp:56
void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: rel.cpp:118
Gecode::IntArgs i(4, 1, 2, 3, 4)
RelBin _relbin_shared_cmpl(Gecode::SRT_CMPL, true)
Range iterator for computing intersection (binary)
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
RelBin _relbin_shared_disj(Gecode::SRT_DISJ, true)
int minSymDiff(const SetAssignment &x) const
Definition: rel.cpp:66
Less or equal ( )
Definition: set.hh:651
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:296
void post(Space &home, SetVarArray &x, IntVarArray &, Reify r)
Post reified constraint on x for b.
Definition: rel.cpp:125
Reification specification.
Definition: int.hh:854
RelBin _relbin_shared_lq(Gecode::SRT_LQ, true)
Subset ( )
Definition: set.hh:647
Gecode::IntSet lub
The common superset for all domains.
Definition: set.hh:170
Integer sets.
Definition: int.hh:171
Less ( )
Definition: set.hh:652
bool in(int i, CountableSetRanges &c, bool eq=false) const
Definition: rel.cpp:78
RelBin _relbin_shared_eq(Gecode::SRT_EQ, true)
RelBin _relbin_shared_sup(Gecode::SRT_SUP, true)
Range iterator for computing union (binary)
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:696
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
Create c
Definition: rel.cpp:562
General test support.
Definition: afc.cpp:43
Greater or equal ( )
Definition: set.hh:653
RelBin _relbin_eq(Gecode::SRT_EQ, false)
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Base class for tests with set constraints
Definition: set.hh:271
Generate all set assignments.
Definition: set.hh:158
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
Range iterator producing subsets of an IntSet.
Definition: set.hh:114
Greater ( )
Definition: set.hh:654
Equality ( )
Definition: set.hh:645
Disjoint ( )
Definition: set.hh:649
RelBin _relbin_shared_gr(Gecode::SRT_GR, true)
RelBin _relbin_shared_nq(Gecode::SRT_NQ, true)
bool subset(I &i, J &j)
Check whether range iterator i is subset of range iterator j.
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
Definition: view.hpp:662
Set variable array
Definition: set.hh:571
RelBin _relbin_shared_gq(Gecode::SRT_GQ, true)
Disequality ( )
Definition: set.hh:646
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
Range iterator for computing set difference.
Definition: ranges-diff.hpp:47
RelBin _relbin_disj(Gecode::SRT_DISJ, false)
RelBin _relbin_gq(Gecode::SRT_GQ, false)
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.