Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.9.1
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 
38 namespace 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
60  CachedView<View>::min(void) const {
61  return x.min();
62  }
63  template<class View>
64  forceinline int
65  CachedView<View>::max(void) const {
66  return x.max();
67  }
68  template<class View>
69  forceinline int
70  CachedView<View>::med(void) const {
71  return x.med();
72  }
73  template<class View>
74  forceinline int
75  CachedView<View>::val(void) const {
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
93  CachedView<View>::size(void) const {
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
118  CachedView<View>::in(int n) const {
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);
321  ViewRanges<View> xr(x);
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  ViewRanges(void);
354  ViewRanges(const CachedView<View>& x);
356  void init(const CachedView<View>& x);
358  };
359 
360  template<class View>
363 
364  template<class View>
368  }
369 
370  template<class View>
371  forceinline void
373  ViewRanges<View>::init(x.base());
374  }
375 
376  template<class View>
379 
380  template<class View>
383  : cr(x._firstRange), dr(x.base()) {
384  Super::init(cr,dr);
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
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
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 ModEvent
Type for modification events.
Definition: core.hpp:62
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
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
const double base
Base for geometric restart sequence.
Definition: search.hh:126
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
#define forceinline
Definition: config.hpp:194