Generated on Sat Feb 7 2015 02:01:26 for Gecode by doxygen 1.8.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  * Copyright:
7  * Guido Tack, 2011
8  *
9  * Last modified:
10  * $Date: 2013-02-14 16:29:11 +0100 (Thu, 14 Feb 2013) $ by $Author: schulte $
11  * $Revision: 13292 $
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 
79  template<class View>
80  forceinline unsigned int
82  return x.width();
83  }
84  template<class View>
85  forceinline unsigned int
86  CachedView<View>::size(void) const {
87  return x.size();
88  }
89  template<class View>
90  forceinline unsigned int
92  return x.regret_min();
93  }
94  template<class View>
95  forceinline unsigned int
97  return x.regret_max();
98  }
99 
100  /*
101  * Domain tests
102  *
103  */
104  template<class View>
105  forceinline bool
107  return x.range();
108  }
109  template<class View>
110  forceinline bool
111  CachedView<View>::in(int n) const {
112  return x.in(n);
113  }
114  template<class View>
115  forceinline bool
116  CachedView<View>::in(long long int n) const {
117  return x.in(n);
118  }
119 
120 
121  /*
122  * Domain update by value
123  *
124  */
125  template<class View>
128  return x.lq(home,n);
129  }
130  template<class View>
132  CachedView<View>::lq(Space& home, long long int n) {
133  return x.lq(home,n);
134  }
135  template<class View>
138  return x.le(home,n);
139  }
140  template<class View>
142  CachedView<View>::le(Space& home, long long int n) {
143  return x.le(home,n);
144  }
145  template<class View>
148  return x.gq(home,n);
149  }
150  template<class View>
152  CachedView<View>::gq(Space& home, long long int n) {
153  return x.gq(home,n);
154  }
155  template<class View>
158  return x.gr(home,n);
159  }
160  template<class View>
162  CachedView<View>::gr(Space& home, long long int n) {
163  return x.gr(home,n);
164  }
165  template<class View>
168  return x.nq(home,n);
169  }
170  template<class View>
172  CachedView<View>::nq(Space& home, long long int n) {
173  return x.nq(home,n);
174  }
175  template<class View>
178  return x.eq(home,n);
179  }
180  template<class View>
182  CachedView<View>::eq(Space& home, long long int n) {
183  return x.eq(home,n);
184  }
185 
186 
187  /*
188  * Iterator-based domain update
189  *
190  */
191  template<class View>
192  template<class I>
194  CachedView<View>::narrow_r(Space& home, I& i, bool depend) {
195  return x.narrow_r(home,i,depend);
196  }
197  template<class View>
198  template<class I>
200  CachedView<View>::inter_r(Space& home, I& i, bool depend) {
201  return x.inter_r(home,i,depend);
202  }
203  template<class View>
204  template<class I>
206  CachedView<View>::minus_r(Space& home, I& i, bool depend) {
207  return x.minus_r(home,i,depend);
208  }
209  template<class View>
210  template<class I>
212  CachedView<View>::narrow_v(Space& home, I& i, bool depend) {
213  return x.narrow_v(home,i,depend);
214  }
215  template<class View>
216  template<class I>
218  CachedView<View>::inter_v(Space& home, I& i, bool depend) {
219  return x.inter_v(home,i,depend);
220  }
221  template<class View>
222  template<class I>
224  CachedView<View>::minus_v(Space& home, I& i, bool depend) {
225  return x.minus_v(home,i,depend);
226  }
227 
228 
229 
230  /*
231  * Propagator modification events
232  *
233  */
234  template<class View>
237  return View::med(me);
238  }
239 
240 
241  /*
242  * Delta information for advisors
243  *
244  */
245  template<class View>
246  forceinline int
247  CachedView<View>::min(const Delta& d) const {
248  return x.min(d);
249  }
250  template<class View>
251  forceinline int
252  CachedView<View>::max(const Delta& d) const {
253  return x.max(d);
254  }
255  template<class View>
256  forceinline bool
257  CachedView<View>::any(const Delta& d) const {
258  return x.any(d);
259  }
260 
261 
262 
263  /*
264  * Cloning
265  *
266  */
267  template<class View>
268  void
270  DerivedView<View>::update(home,share,y);
271  if (y._firstRange) {
272  _firstRange = new (home) RangeList(y._firstRange->min(),
273  y._firstRange->max(),NULL);
274  RangeList* cur = _firstRange;
275 
276  for (RangeList* y_cur = y._firstRange->next(); y_cur != NULL;
277  y_cur = y_cur->next()) {
278  RangeList* next =
279  new (home) RangeList(y_cur->min(),y_cur->max(),NULL);
280  cur->next(next);
281  cur = next;
282  }
283  _lastRange = cur;
284  _size = y._size;
285  }
286  }
287 
288  /*
289  * Cache operations
290  *
291  */
292 
293  template<class View>
294  void
296  _firstRange = NULL;
297  for (int i=s.ranges(); i--;) {
298  _firstRange = new (home) RangeList(s.min(i),s.max(i),_firstRange);
299  if (i==s.ranges()-1)
300  _lastRange = _firstRange;
301  }
302  _size = s.size();
303  }
304 
305  template<class View>
306  void
308  _firstRange->dispose(home,_lastRange);
309  ViewRanges<View> xr(x);
310  _firstRange = new (home) RangeList(xr.min(),xr.max(),NULL);
311  ++xr;
312  RangeList* cur = _firstRange;
313  for (; xr(); ++xr) {
314  RangeList* next = new (home) RangeList(xr.min(),xr.max(),NULL);
315  cur->next(next);
316  cur = next;
317  }
318  _lastRange = cur;
319  _size = x.size();
320  }
321 
322  template<class View>
323  forceinline bool
325  return x.size() != _size;
326  }
327 
328 
333  template<class View>
334  class ViewRanges<CachedView<View> >
335  : public ViewRanges<View> {
336  public:
338 
339  ViewRanges(void);
342  ViewRanges(const CachedView<View>& x);
344  void init(const CachedView<View>& x);
346  };
347 
348  template<class View>
351 
352  template<class View>
356  }
357 
358  template<class View>
359  forceinline void
362  }
363 
364  template<class View>
367 
368  template<class View>
371  : cr(x._firstRange), dr(x.base()) {
372  Super::init(cr,dr);
373  }
374 
375  template<class View>
376  forceinline void
378  cr.init(x._firstRange);
379  dr.init(x.base());
380  Super::init(cr,dr);
381  }
382 
383  /*
384  * View comparison
385  *
386  */
387  template<class View>
388  forceinline bool
390  return same(x.base(),y.base()) && (x.offset() == y.offset());
391  }
392  template<class View>
393  forceinline bool
395  return before(x.base(),y.base())
396  || (same(x.base(),y.base()) && (x.offset() < y.offset()));
397  }
398 
399 }}
400 
401 // STATISTICS: int-var
402 
int min(void) const
Return minimum of domain.
Definition: cached.hpp:60
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: cached.hpp:167
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: cached.hpp:177
bool before(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:394
ViewRanges(void)
Default constructor.
int ModEvent
Type for modification events.
Definition: core.hpp:146
ModEvent gr(Space &home, int n)
Restrict domain values to be greater than n.
Definition: cached.hpp:157
Computation spaces.
Definition: core.hpp:1362
void init(const View &x)
Initialize with ranges for view x.
Base-class for derived views.
Definition: view.hpp:208
Range iterator for integer views.
Definition: view.hpp:54
Gecode::IntSet d(v, 7)
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: cached.hpp:70
bool range(void) const
Test whether domain is a range.
Definition: cached.hpp:106
bool same(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:389
int min(void) const
Return smallest value of range.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:134
View base(void) const
Return view from which this view is derived.
Definition: view.hpp:526
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: cached.hpp:200
void update(Space &home, bool share, DerivedView< View > &y)
Update this view to be a clone of view y.
Definition: view.hpp:590
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value)
Definition: cached.hpp:91
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition: cached.hpp:81
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: cached.hpp:127
RangeList * next(void) const
Return next element.
Definition: range-list.hpp:124
ModEvent narrow_r(Space &home, I &i, bool depends=true)
Replace domain by ranges described by i.
Definition: cached.hpp:194
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition: cached.hpp:137
int max(void) const
Return maximum of domain.
Definition: cached.hpp:65
CachedView(void)
Default constructor.
Definition: cached.hpp:46
Integer sets.
Definition: int.hh:171
void init(const CachedView< View > &x)
Initialize with ranges for view x.
Definition: cached.hpp:377
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:161
ViewDiffRanges(void)
Default constructor.
Definition: cached.hpp:366
void update(Space &home, bool share, CachedView< View > &y)
Update this view to be a clone of view y.
Definition: cached.hpp:269
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Generic domain change information to be supplied to advisors.
Definition: core.hpp:275
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: cached.hpp:86
unsigned int _size
Size of cached domain.
Definition: view.hpp:1116
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: cached.hpp:206
int val(void) const
Return assigned value (only if assigned)
Definition: cached.hpp:75
#define forceinline
Definition: config.hpp:132
Cached integer view.
Definition: view.hpp:1107
bool modified(void) const
Check whether cache differs from current domain.
Definition: cached.hpp:324
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: cached.hpp:212
bool any(const Delta &d) const
Test whether arbitrary values got pruned.
Definition: cached.hpp:257
Lists of ranges (intervals)
Definition: range-list.hpp:53
bool in(int n) const
Test whether n is contained in domain.
Definition: cached.hpp:111
int max(void) const
Return largest value of range.
Gecode toplevel namespace
void init(Iter::Ranges::RangeList &i, ViewRanges< View > &j)
Initialize with iterator i and j.
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value)
Definition: cached.hpp:96
void cache(Space &home)
Update cache to current domain.
Definition: cached.hpp:307
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
void initCache(Space &home, const IntSet &s)
Initialize cache to set s.
Definition: cached.hpp:295
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: cached.hpp:147
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: cached.hpp:224
Iter::Ranges::RangeList cr
Cached domain iterator.
Definition: view.hpp:1294
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: cached.hpp:218
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:121
RangeList * _firstRange
First cached range.
Definition: view.hpp:1112
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:115
ViewRanges< View > dr
Current domain iterator.
Definition: view.hpp:1296