Generated on Tue Jul 18 2017 18:41:42 for Gecode by doxygen 1.8.13
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  * Last modified:
10  * $Date: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
11  * $Revision: 14967 $
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 namespace Gecode { namespace Int {
39 
40  /*
41  * Testing equality
42  *
43  */
44 
45  template<class VX, class VY>
47  rtest_eq_bnd(VX x, VY y) {
48  if ((x.min() > y.max()) || (x.max() < y.min())) return RT_FALSE;
49  return (x.assigned() && y.assigned()) ? RT_TRUE : RT_MAYBE;
50  }
51 
52  template<class VX, class VY>
53  RelTest
55  ViewRanges<VX> rx(x);
56  ViewRanges<VY> ry(y);
57  while (rx() && ry()) {
58  if (rx.max() < ry.min()) {
59  ++rx;
60  } else if (ry.max() < rx.min()) {
61  ++ry;
62  } else return RT_MAYBE;
63  }
64  return RT_FALSE;
65  }
66 
67  template<class VX, class VY>
69  rtest_eq_dom(VX x, VY y) {
70  RelTest rt = rtest_eq_bnd(x,y);
71  if (rt != RT_MAYBE) return rt;
72  return (x.range() && y.range()) ? RT_MAYBE : rtest_eq_dom_check(x,y);
73  }
74 
75 
76  template<class VX>
78  rtest_eq_bnd(VX x, int n) {
79  if ((n > x.max()) || (n < x.min())) return RT_FALSE;
80  return x.assigned() ? RT_TRUE : RT_MAYBE;
81  }
82 
83  template<class VX>
84  RelTest
85  rtest_eq_dom_check(VX x, int n) {
86  ViewRanges<VX> rx(x);
87  while (n > rx.max()) ++rx;
88  return (n >= rx.min()) ? RT_MAYBE : RT_FALSE;
89  }
90 
91  template<class VX>
93  rtest_eq_dom(VX x, int n) {
94  RelTest rt = rtest_eq_bnd(x,n);
95  if (rt != RT_MAYBE) return rt;
96  return x.range() ? RT_MAYBE : rtest_eq_dom_check(x,n);
97  }
98 
99 
100 
101  /*
102  * Testing disequality
103  *
104  */
105 
106  template<class VX, class VY>
108  rtest_nq_bnd(VX x, VY y) {
109  if ((x.min() > y.max()) || (x.max() < y.min())) return RT_TRUE;
110  return (x.assigned() && y.assigned()) ? RT_FALSE : RT_MAYBE;
111  }
112 
113  template<class VX, class VY>
116  ViewRanges<VX> rx(x);
117  ViewRanges<VY> ry(y);
118  while (rx() && ry()) {
119  if (rx.max() < ry.min()) {
120  ++rx;
121  } else if (ry.max() < rx.min()) {
122  ++ry;
123  } else return RT_MAYBE;
124  }
125  return RT_TRUE;
126  }
127 
128  template<class VX, class VY>
130  rtest_nq_dom(VX x, VY y) {
131  RelTest rt = rtest_nq_bnd(x,y);
132  if (rt != RT_MAYBE) return rt;
133  return (x.range() && y.range()) ? RT_MAYBE : rtest_nq_dom_check(x,y);
134  }
135 
136 
137  template<class VX>
139  rtest_nq_bnd(VX x, int n) {
140  if ((n > x.max()) || (n < x.min())) return RT_TRUE;
141  return (x.assigned()) ? RT_FALSE : RT_MAYBE;
142  }
143 
144  template<class VX>
146  rtest_nq_dom_check(VX x, int n) {
147  ViewRanges<VX> rx(x);
148  while (n > rx.max()) ++rx;
149  return (n >= rx.min()) ? RT_MAYBE : RT_TRUE;
150  }
151 
152  template<class VX>
154  rtest_nq_dom(VX x, int n) {
155  RelTest rt = rtest_nq_bnd(x,n);
156  if (rt != RT_MAYBE) return rt;
157  return x.range() ? RT_MAYBE : rtest_nq_dom_check(x,n);
158  }
159 
160 
161  /*
162  * Testing inequalities
163  *
164  */
165 
166  template<class VX, class VY>
168  rtest_lq(VX x, VY y) {
169  if (x.max() <= y.min()) return RT_TRUE;
170  if (x.min() > y.max()) return RT_FALSE;
171  return RT_MAYBE;
172  }
173 
174  template<class VX>
176  rtest_lq(VX x, int n) {
177  if (x.max() <= n) return RT_TRUE;
178  if (x.min() > n) return RT_FALSE;
179  return RT_MAYBE;
180  }
181 
182  template<class VX, class VY>
184  rtest_le(VX x, VY y) {
185  if (x.max() < y.min()) return RT_TRUE;
186  if (x.min() >= y.max()) return RT_FALSE;
187  return RT_MAYBE;
188  }
189 
190  template<class VX>
192  rtest_le(VX x, int n) {
193  if (x.max() < n) return RT_TRUE;
194  if (x.min() >= n) return RT_FALSE;
195  return RT_MAYBE;
196  }
197 
198  template<class VX, class VY>
200  rtest_gq(VX x, VY y) {
201  if (x.max() < y.min()) return RT_FALSE;
202  if (x.min() >= y.max()) return RT_TRUE;
203  return RT_MAYBE;
204  }
205 
206  template<class VX>
208  rtest_gq(VX x, int n) {
209  if (x.max() < n) return RT_FALSE;
210  if (x.min() >= n) return RT_TRUE;
211  return RT_MAYBE;
212  }
213 
214  template<class VX, class VY>
216  rtest_gr(VX x, VY y) {
217  if (x.max() <= y.min()) return RT_FALSE;
218  if (x.min() > y.max()) return RT_TRUE;
219  return RT_MAYBE;
220  }
221 
222  template<class VX>
224  rtest_gr(VX x, int n) {
225  if (x.max() <= n) return RT_FALSE;
226  if (x.min() > n) return RT_TRUE;
227  return RT_MAYBE;
228  }
229 
230 }}
231 
232 // STATISTICS: int-var
233 
Relation may hold or not.
Definition: view.hpp:1616
RelTest rtest_eq_dom(VX x, VY y)
Test whether views x and y are equal (use full domain information)
Definition: rel-test.hpp:69
RelTest rtest_gq(VX x, VY y)
Test whether view x is greater or equal than view y.
Definition: rel-test.hpp:200
RelTest rtest_eq_dom_check(VX x, VY y)
Definition: rel-test.hpp:54
RelTest rtest_le(VX x, VY y)
Test whether view x is less than view y.
Definition: rel-test.hpp:184
Range iterator for integer views.
Definition: view.hpp:54
RelTest rtest_lq(VX x, VY y)
Test whether view x is less or equal than view y.
Definition: rel-test.hpp:168
RelTest rtest_nq_dom_check(VX x, VY y)
Definition: rel-test.hpp:115
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Relation does not hold.
Definition: view.hpp:1615
RelTest
Result of testing relation.
Definition: view.hpp:1614
int min(void) const
Return smallest value of range.
RelTest rtest_nq_dom(VX x, VY y)
Test whether views x and y are different (use full domain information)
Definition: rel-test.hpp:130
RelTest rtest_eq_bnd(VX x, VY y)
Test whether views x and y are equal (use bounds information)
Definition: rel-test.hpp:47
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
#define forceinline
Definition: config.hpp:173
RelTest rtest_nq_bnd(VX x, VY y)
Test whether views x and y are different (use bounds information)
Definition: rel-test.hpp:108
int max(void) const
Return largest value of range.
Post propagator for SetVar x
Definition: set.hh:784
Gecode toplevel namespace
RelTest rtest_gr(VX x, VY y)
Test whether view x is greater than view y.
Definition: rel-test.hpp:216
Relation does hold.
Definition: view.hpp:1617