Generated on Thu Jul 21 2022 00:00:00 for Gecode by doxygen 1.9.5
cached.hpp
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 * Contributing authors:
7 * Samuel Gagnon <samuel.gagnon92@gmail.com>
8 *
9 * Copyright:
10 * Guido Tack, 2011
11 * Samuel Gagnon, 2018
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
38namespace Gecode { namespace Int {
39
40 /*
41 * Constructors and initialization
42 *
43 */
44 template<class View>
46 CachedView<View>::CachedView(void) : _size(0) {}
47 template<class View>
50 : DerivedView<View>(y), _firstRange(NULL), _lastRange(NULL),
51 _size(0) {}
52
53
54 /*
55 * Value access
56 *
57 */
58 template<class View>
59 forceinline int
61 return x.min();
62 }
63 template<class View>
64 forceinline int
66 return x.max();
67 }
68 template<class View>
69 forceinline int
71 return x.med();
72 }
73 template<class View>
74 forceinline int
76 return x.val();
77 }
78#ifdef GECODE_HAS_CBS
79 template<class View>
80 forceinline int
81 CachedView<View>::baseval(int val) const {
82 return val;
83 }
84#endif
85
86 template<class View>
87 forceinline unsigned int
89 return x.width();
90 }
91 template<class View>
92 forceinline unsigned int
94 return x.size();
95 }
96 template<class View>
97 forceinline unsigned int
99 return x.regret_min();
100 }
101 template<class View>
102 forceinline unsigned int
104 return x.regret_max();
105 }
106
107 /*
108 * Domain tests
109 *
110 */
111 template<class View>
112 forceinline bool
114 return x.range();
115 }
116 template<class View>
117 forceinline bool
119 return x.in(n);
120 }
121 template<class View>
122 forceinline bool
123 CachedView<View>::in(long long int n) const {
124 return x.in(n);
125 }
126
127
128 /*
129 * Domain update by value
130 *
131 */
132 template<class View>
135 return x.lq(home,n);
136 }
137 template<class View>
139 CachedView<View>::lq(Space& home, long long int n) {
140 return x.lq(home,n);
141 }
142 template<class View>
145 return x.le(home,n);
146 }
147 template<class View>
149 CachedView<View>::le(Space& home, long long int n) {
150 return x.le(home,n);
151 }
152 template<class View>
155 return x.gq(home,n);
156 }
157 template<class View>
159 CachedView<View>::gq(Space& home, long long int n) {
160 return x.gq(home,n);
161 }
162 template<class View>
165 return x.gr(home,n);
166 }
167 template<class View>
169 CachedView<View>::gr(Space& home, long long int n) {
170 return x.gr(home,n);
171 }
172 template<class View>
175 return x.nq(home,n);
176 }
177 template<class View>
179 CachedView<View>::nq(Space& home, long long int n) {
180 return x.nq(home,n);
181 }
182 template<class View>
185 return x.eq(home,n);
186 }
187 template<class View>
189 CachedView<View>::eq(Space& home, long long int n) {
190 return x.eq(home,n);
191 }
192
193
194 /*
195 * Iterator-based domain update
196 *
197 */
198 template<class View>
199 template<class I>
201 CachedView<View>::narrow_r(Space& home, I& i, bool depend) {
202 return x.narrow_r(home,i,depend);
203 }
204 template<class View>
205 template<class I>
207 CachedView<View>::inter_r(Space& home, I& i, bool depend) {
208 return x.inter_r(home,i,depend);
209 }
210 template<class View>
211 template<class I>
213 CachedView<View>::minus_r(Space& home, I& i, bool depend) {
214 return x.minus_r(home,i,depend);
215 }
216 template<class View>
217 template<class I>
219 CachedView<View>::narrow_v(Space& home, I& i, bool depend) {
220 return x.narrow_v(home,i,depend);
221 }
222 template<class View>
223 template<class I>
225 CachedView<View>::inter_v(Space& home, I& i, bool depend) {
226 return x.inter_v(home,i,depend);
227 }
228 template<class View>
229 template<class I>
231 CachedView<View>::minus_v(Space& home, I& i, bool depend) {
232 return x.minus_v(home,i,depend);
233 }
234
235
236
237 /*
238 * Propagator modification events
239 *
240 */
241 template<class View>
244 return View::med(me);
245 }
246
247
248 /*
249 * Delta information for advisors
250 *
251 */
252 template<class View>
253 forceinline int
254 CachedView<View>::min(const Delta& d) const {
255 return x.min(d);
256 }
257 template<class View>
258 forceinline int
259 CachedView<View>::max(const Delta& d) const {
260 return x.max(d);
261 }
262 template<class View>
263 forceinline unsigned int
265 return x.width(d);
266 }
267 template<class View>
268 forceinline bool
269 CachedView<View>::any(const Delta& d) const {
270 return x.any(d);
271 }
272
273
274
275 /*
276 * Cloning
277 *
278 */
279 template<class View>
280 void
283 if (y._firstRange) {
284 _firstRange = new (home) RangeList(y._firstRange->min(),
285 y._firstRange->max(),NULL);
286 RangeList* cur = _firstRange;
287
288 for (RangeList* y_cur = y._firstRange->next(); y_cur != NULL;
289 y_cur = y_cur->next()) {
290 RangeList* next =
291 new (home) RangeList(y_cur->min(),y_cur->max(),NULL);
292 cur->next(next);
293 cur = next;
294 }
295 _lastRange = cur;
296 _size = y._size;
297 }
298 }
299
300
301 /*
302 * Cache operations
303 *
304 */
305 template<class View>
306 void
308 _firstRange = NULL;
309 for (int i=s.ranges(); i--;) {
310 _firstRange = new (home) RangeList(s.min(i),s.max(i),_firstRange);
311 if (i==s.ranges()-1)
312 _lastRange = _firstRange;
313 }
314 _size = s.size();
315 }
316
317 template<class View>
318 void
320 _firstRange->dispose(home,_lastRange);
322 _firstRange = new (home) RangeList(xr.min(),xr.max(),NULL);
323 ++xr;
324 RangeList* cur = _firstRange;
325 for (; xr(); ++xr) {
326 RangeList* next = new (home) RangeList(xr.min(),xr.max(),NULL);
327 cur->next(next);
328 cur = next;
329 }
330 _lastRange = cur;
331 _size = x.size();
332 }
333
334 template<class View>
335 forceinline bool
337 return x.size() != _size;
338 }
339
340
345 template<class View>
346 class ViewRanges<CachedView<View> >
347 : public ViewRanges<View> {
348 public:
350
351
352 ViewRanges(void);
356 void init(const CachedView<View>& x);
358 };
359
360 template<class View>
362 ViewRanges<CachedView<View> >::ViewRanges(void) {}
363
364 template<class View>
368 }
369
370 template<class View>
371 forceinline void
374 }
375
376 template<class View>
379
380 template<class View>
383 : cr(x._firstRange), dr(x.base()) {
385 }
386
387 template<class View>
388 forceinline void
390 cr.init(x._firstRange);
391 dr.init(x.base());
392 Super::init(cr,dr);
393 }
394
395 /*
396 * View comparison
397 *
398 */
399 template<class View>
400 forceinline bool
402 return (x.base() == y.base()) && (x.offset() == y.offset());
403 }
404 template<class View>
405 forceinline bool
407 return !(x == y);
408 }
409
410}}
411
412// STATISTICS: int-var
413
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Generic domain change information to be supplied to advisors.
Definition: core.hpp:204
Base-class for derived views.
Definition: view.hpp:230
void update(Space &home, DerivedView< View > &y)
Update this view to be a clone of view y.
Definition: view.hpp:681
Integer sets.
Definition: int.hh:174
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:152
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:158
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:171
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:198
Cached integer view.
Definition: view.hpp:1166
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: cached.hpp:154
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: cached.hpp:93
bool any(const Delta &d) const
Test whether arbitrary values got pruned.
Definition: cached.hpp:269
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition: cached.hpp:144
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: cached.hpp:70
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition: cached.hpp:88
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: cached.hpp:225
ModEvent narrow_r(Space &home, I &i, bool depends=true)
Replace domain by ranges described by i.
Definition: cached.hpp:201
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: cached.hpp:231
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: cached.hpp:184
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: cached.hpp:213
bool in(int n) const
Test whether n is contained in domain.
Definition: cached.hpp:118
void initCache(Space &home, const IntSet &s)
Initialize cache to set s.
Definition: cached.hpp:307
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value)
Definition: cached.hpp:103
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: cached.hpp:219
bool range(void) const
Test whether domain is a range.
Definition: cached.hpp:113
int val(void) const
Return assigned value (only if assigned)
Definition: cached.hpp:75
void cache(Space &home)
Update cache to current domain.
Definition: cached.hpp:319
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: cached.hpp:134
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: cached.hpp:207
ModEvent gr(Space &home, int n)
Restrict domain values to be greater than n.
Definition: cached.hpp:164
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value)
Definition: cached.hpp:98
int min(void) const
Return minimum of domain.
Definition: cached.hpp:60
bool modified(void) const
Check whether cache differs from current domain.
Definition: cached.hpp:336
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: cached.hpp:174
void update(Space &home, CachedView< View > &y)
Update this view to be a clone of view y.
Definition: cached.hpp:281
int max(void) const
Return maximum of domain.
Definition: cached.hpp:65
CachedView(void)
Default constructor.
Definition: cached.hpp:46
void init(const CachedView< View > &x)
Initialize with ranges for view x.
Definition: cached.hpp:389
ViewRanges< View > dr
Current domain iterator.
Definition: view.hpp:1361
Iter::Ranges::RangeList cr
Cached domain iterator.
Definition: view.hpp:1359
ViewDiffRanges(void)
Default constructor.
Definition: cached.hpp:378
Range iterator for integer views.
Definition: view.hpp:54
int max(void) const
Return largest value of range.
int min(void) const
Return smallest value of range.
void init(const View &x)
Initialize with ranges for view x.
ViewRanges(void)
Default constructor.
void init(Iter::Ranges::RangeList &i, ViewRanges< View > &j)
Initialize with iterator i and j.
Lists of ranges (intervals)
Definition: range-list.hpp:49
RangeList * next(void) const
Return next element.
Definition: range-list.hpp:141
Computation spaces.
Definition: core.hpp:1742
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
bool operator==(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:401
bool operator!=(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:406
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
Post propagator for SetVar x
Definition: set.hh:767
int ModEvent
Type for modification events.
Definition: core.hpp:62
#define forceinline
Definition: config.hpp:194