Generated on Fri Jan 10 2020 11:38:25 for Gecode by doxygen 1.8.16
rel-test.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2003
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 namespace Gecode { namespace Int {
35 
36  /*
37  * Testing equality
38  *
39  */
40 
41  template<class VX, class VY>
43  rtest_eq_bnd(VX x, VY y) {
44  if ((x.min() > y.max()) || (x.max() < y.min())) return RT_FALSE;
45  return (x.assigned() && y.assigned()) ? RT_TRUE : RT_MAYBE;
46  }
47 
48  template<class VX, class VY>
49  RelTest
51  ViewRanges<VX> rx(x);
52  ViewRanges<VY> ry(y);
53  while (rx() && ry()) {
54  if (rx.max() < ry.min()) {
55  ++rx;
56  } else if (ry.max() < rx.min()) {
57  ++ry;
58  } else return RT_MAYBE;
59  }
60  return RT_FALSE;
61  }
62 
63  template<class VX, class VY>
65  rtest_eq_dom(VX x, VY y) {
66  RelTest rt = rtest_eq_bnd(x,y);
67  if (rt != RT_MAYBE) return rt;
68  return (x.range() && y.range()) ? RT_MAYBE : rtest_eq_dom_check(x,y);
69  }
70 
71 
72  template<class VX>
74  rtest_eq_bnd(VX x, int n) {
75  if ((n > x.max()) || (n < x.min())) return RT_FALSE;
76  return x.assigned() ? RT_TRUE : RT_MAYBE;
77  }
78 
79  template<class VX>
80  RelTest
81  rtest_eq_dom_check(VX x, int n) {
82  ViewRanges<VX> rx(x);
83  while (n > rx.max()) ++rx;
84  return (n >= rx.min()) ? RT_MAYBE : RT_FALSE;
85  }
86 
87  template<class VX>
89  rtest_eq_dom(VX x, int n) {
90  RelTest rt = rtest_eq_bnd(x,n);
91  if (rt != RT_MAYBE) return rt;
92  return x.range() ? RT_MAYBE : rtest_eq_dom_check(x,n);
93  }
94 
95 
96 
97  /*
98  * Testing disequality
99  *
100  */
101 
102  template<class VX, class VY>
104  rtest_nq_bnd(VX x, VY y) {
105  if ((x.min() > y.max()) || (x.max() < y.min())) return RT_TRUE;
106  return (x.assigned() && y.assigned()) ? RT_FALSE : RT_MAYBE;
107  }
108 
109  template<class VX, class VY>
112  ViewRanges<VX> rx(x);
113  ViewRanges<VY> ry(y);
114  while (rx() && ry()) {
115  if (rx.max() < ry.min()) {
116  ++rx;
117  } else if (ry.max() < rx.min()) {
118  ++ry;
119  } else return RT_MAYBE;
120  }
121  return RT_TRUE;
122  }
123 
124  template<class VX, class VY>
126  rtest_nq_dom(VX x, VY y) {
127  RelTest rt = rtest_nq_bnd(x,y);
128  if (rt != RT_MAYBE) return rt;
129  return (x.range() && y.range()) ? RT_MAYBE : rtest_nq_dom_check(x,y);
130  }
131 
132 
133  template<class VX>
135  rtest_nq_bnd(VX x, int n) {
136  if ((n > x.max()) || (n < x.min())) return RT_TRUE;
137  return (x.assigned()) ? RT_FALSE : RT_MAYBE;
138  }
139 
140  template<class VX>
142  rtest_nq_dom_check(VX x, int n) {
143  ViewRanges<VX> rx(x);
144  while (n > rx.max()) ++rx;
145  return (n >= rx.min()) ? RT_MAYBE : RT_TRUE;
146  }
147 
148  template<class VX>
150  rtest_nq_dom(VX x, int n) {
151  RelTest rt = rtest_nq_bnd(x,n);
152  if (rt != RT_MAYBE) return rt;
153  return x.range() ? RT_MAYBE : rtest_nq_dom_check(x,n);
154  }
155 
156 
157  /*
158  * Testing inequalities
159  *
160  */
161 
162  template<class VX, class VY>
164  rtest_lq(VX x, VY y) {
165  if (x.max() <= y.min()) return RT_TRUE;
166  if (x.min() > y.max()) return RT_FALSE;
167  return RT_MAYBE;
168  }
169 
170  template<class VX>
172  rtest_lq(VX x, int n) {
173  if (x.max() <= n) return RT_TRUE;
174  if (x.min() > n) return RT_FALSE;
175  return RT_MAYBE;
176  }
177 
178  template<class VX, class VY>
180  rtest_le(VX x, VY y) {
181  if (x.max() < y.min()) return RT_TRUE;
182  if (x.min() >= y.max()) return RT_FALSE;
183  return RT_MAYBE;
184  }
185 
186  template<class VX>
188  rtest_le(VX x, int n) {
189  if (x.max() < n) return RT_TRUE;
190  if (x.min() >= n) return RT_FALSE;
191  return RT_MAYBE;
192  }
193 
194  template<class VX, class VY>
196  rtest_gq(VX x, VY y) {
197  if (x.max() < y.min()) return RT_FALSE;
198  if (x.min() >= y.max()) return RT_TRUE;
199  return RT_MAYBE;
200  }
201 
202  template<class VX>
204  rtest_gq(VX x, int n) {
205  if (x.max() < n) return RT_FALSE;
206  if (x.min() >= n) return RT_TRUE;
207  return RT_MAYBE;
208  }
209 
210  template<class VX, class VY>
212  rtest_gr(VX x, VY y) {
213  if (x.max() <= y.min()) return RT_FALSE;
214  if (x.min() > y.max()) return RT_TRUE;
215  return RT_MAYBE;
216  }
217 
218  template<class VX>
220  rtest_gr(VX x, int n) {
221  if (x.max() <= n) return RT_FALSE;
222  if (x.min() > n) return RT_TRUE;
223  return RT_MAYBE;
224  }
225 
226 }}
227 
228 // STATISTICS: int-var
229 
RelTest rtest_gq(VX x, VY y)
Test whether view x is greater or equal than view y.
Definition: rel-test.hpp:196
Post propagator for SetVar x
Definition: set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
RelTest rtest_eq_bnd(VX x, VY y)
Test whether views x and y are equal (use bounds information)
Definition: rel-test.hpp:43
RelTest rtest_nq_dom_check(VX x, VY y)
Definition: rel-test.hpp:111
int min(void) const
Return smallest value of range.
RelTest rtest_lq(VX x, VY y)
Test whether view x is less or equal than view y.
Definition: rel-test.hpp:164
RelTest rtest_gr(VX x, VY y)
Test whether view x is greater than view y.
Definition: rel-test.hpp:212
Relation does hold.
Definition: view.hpp:1737
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:111
RelTest rtest_nq_dom(VX x, VY y)
Test whether views x and y are different (use full domain information)
Definition: rel-test.hpp:126
Gecode toplevel namespace
Relation may hold or not.
Definition: view.hpp:1736
Range iterator for integer views.
Definition: view.hpp:54
RelTest rtest_eq_dom_check(VX x, VY y)
Definition: rel-test.hpp:50
RelTest rtest_eq_dom(VX x, VY y)
Test whether views x and y are equal (use full domain information)
Definition: rel-test.hpp:65
Relation does not hold.
Definition: view.hpp:1735
RelTest rtest_nq_bnd(VX x, VY y)
Test whether views x and y are different (use bounds information)
Definition: rel-test.hpp:104
RelTest rtest_le(VX x, VY y)
Test whether view x is less than view y.
Definition: rel-test.hpp:180
int max(void) const
Return largest value of range.
#define forceinline
Definition: config.hpp:185
RelTest
Result of testing relation.
Definition: view.hpp:1734
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234