Generated on Sat May 25 2013 18:00:41 for Gecode by doxygen 1.8.3.1
const.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, 2004
8  *
9  * Last modified:
10  * $Date: 2010-07-28 17:35:33 +0200 (Wed, 28 Jul 2010) $ by $Author: schulte $
11  * $Revision: 11294 $
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 Set {
39 
44  class ArrayRanges {
45  private:
46  int *_ranges;
47  int _size;
48  int _pos;
49  public:
51 
52 
53  ArrayRanges(void) : _ranges(NULL), _size(0), _pos(0) {}
55  ArrayRanges(int *ranges, int size)
56  : _ranges(ranges), _size(size), _pos(0) {}
58  void init(int* ranges, int size) {
59  _ranges = ranges; _size = size; _pos = 0;
60  }
62 
64 
65 
66  bool operator ()(void) const { return _pos<_size; }
68  void operator ++(void) { _pos++; }
70 
72 
73 
74  int min(void) const { return _ranges[_pos*2]; }
76  int max(void) const { return _ranges[_pos*2+1]; }
78  unsigned int width(void) const {
79  return static_cast<unsigned int>(_ranges[_pos*2+1]-_ranges[_pos*2]+1);
80  }
82  };
83 
85  ConstSetView::ConstSetView(void) : ranges(NULL), size(0), domSize(0) {}
86 
89  size = dom.ranges();
90  domSize = 0;
91  if (size > 0) {
92  ranges = home.alloc<int>(2*size);
93  IntSetRanges dr(dom);
94  for (int i=0; dr(); ++dr, i+=2) {
95  int min = dr.min(); int max = dr.max();
96  ranges[i] = min;
97  ranges[i+1] = max;
98  domSize += static_cast<unsigned int>(max-min+1);
99  }
100  } else {
101  ranges = NULL;
102  }
103  }
104 
105  forceinline unsigned int
106  ConstSetView::glbSize(void) const { return domSize; }
107 
108  forceinline unsigned int
109  ConstSetView::lubSize(void) const { return domSize; }
110 
111  forceinline unsigned int
112  ConstSetView::unknownSize(void) const { return 0; }
113 
114  forceinline bool
116  for (int j=size; j--; ) {
117  if (ranges[2*j+1] < i)
118  return false;
119  if (ranges[2*j] >= i)
120  return true;
121  }
122  return false;
123  }
124 
125  forceinline bool
127  return !contains(i);
128  }
129 
130  forceinline unsigned int
131  ConstSetView::cardMin(void) const { return domSize; }
132 
133  forceinline unsigned int
134  ConstSetView::cardMax(void) const { return domSize; }
135 
136  forceinline int
137  ConstSetView::lubMin(void) const {
138  return size==0 ? BndSet::MIN_OF_EMPTY : ranges[0];
139  }
140 
141  forceinline int
142  ConstSetView::lubMax(void) const {
143  return size==0 ? BndSet::MAX_OF_EMPTY : ranges[size*2-1];
144  }
145 
146  forceinline int
147  ConstSetView::glbMin(void) const { return lubMin(); }
148 
149  forceinline int
150  ConstSetView::glbMax(void) const { return lubMax(); }
151 
153  ConstSetView::cardMin(Space&,unsigned int c) {
154  return c<=domSize ? ME_SET_NONE : ME_SET_FAILED;
155  }
156 
158  ConstSetView::cardMax(Space&,unsigned int c) {
159  return c>=domSize ? ME_SET_NONE : ME_SET_FAILED;
160  }
161 
164  return contains(c) ? ME_SET_NONE : ME_SET_FAILED;
165  }
166 
169  return contains(c) ? ME_SET_FAILED : ME_SET_NONE;
170  }
171 
174  return (size==0 ||
175  (size==1 &&
176  ranges[0]==ranges[1] && ranges[0]==c)) ?
178  }
179 
182  return (glbMin()>=i && glbMax()<=j) ?
184  }
185 
188  Iter::Ranges::Singleton single(i,j);
189  ArrayRanges ar(ranges, size);
190  return (single() && Iter::Ranges::subset(single, ar)) ?
192  }
193 
196  Iter::Ranges::Singleton single(i,j);
197  ArrayRanges ar(ranges, size);
198  return (single() && Iter::Ranges::subset(single, ar)) ?
200  }
201 
202  template<class I> ModEvent
204  ArrayRanges ar(ranges, size);
205  return (i() && Iter::Ranges::subset(i, ar)) ? ME_SET_FAILED : ME_SET_NONE;
206  }
207 
208  template<class I> ModEvent
210  ArrayRanges ar(ranges, size);
212  }
213 
214  template<class I> ModEvent
216  ArrayRanges ar(ranges, size);
218  }
219 
220  forceinline void
221  ConstSetView::update(Space& home, bool share, ConstSetView& p) {
222  ConstView<SetView>::update(home,share,p);
223  // dispose old ranges
224  if (size > 0)
225  home.free<int>(ranges, 2);
226 
227  domSize = p.domSize;
228  size = p.size;
229  if (size == 0) {
230  ranges = NULL;
231  } else {
232  // copy ranges from p
233  ranges = home.alloc<int>(2*size);
234  for (int i=size; i--; ) {
235  ranges[2*i] = p.ranges[2*i];
236  ranges[2*i+1] = p.ranges[2*i+1];
237  }
238  }
239  }
240 
241 
242  /*
243  * Delta information for advisors
244  *
245  */
246  forceinline int
247  ConstSetView::glbMin(const Delta&) const {
248  GECODE_NEVER;
249  return 0;
250  }
251  forceinline int
252  ConstSetView::glbMax(const Delta&) const {
253  GECODE_NEVER;
254  return 0;
255  }
256  forceinline bool
257  ConstSetView::glbAny(const Delta&) const {
258  GECODE_NEVER;
259  return false;
260  }
261  forceinline int
262  ConstSetView::lubMin(const Delta&) const {
263  GECODE_NEVER;
264  return 0;
265  }
266  forceinline int
267  ConstSetView::lubMax(const Delta&) const {
268  GECODE_NEVER;
269  return 0;
270  }
271  forceinline bool
272  ConstSetView::lubAny(const Delta&) const {
273  GECODE_NEVER;
274  return false;
275  }
276 
279 
280 
281 
282  forceinline unsigned int
283  EmptyView::glbSize(void) const { return 0; }
284 
285  forceinline unsigned int
286  EmptyView::lubSize(void) const { return 0; }
287 
288  forceinline unsigned int
289  EmptyView::unknownSize(void) const { return 0; }
290 
291  forceinline bool
292  EmptyView::contains(int) const { return false; }
293 
294  forceinline bool
295  EmptyView::notContains(int) const { return true; }
296 
297  forceinline unsigned int
298  EmptyView::cardMin(void) const { return 0; }
299 
300  forceinline unsigned int
301  EmptyView::cardMax(void) const { return 0; }
302 
303  forceinline int
304  EmptyView::lubMin(void) const { return 0; }
305 
306  forceinline int
307  EmptyView::lubMax(void) const { return 0; }
308 
309  forceinline int
310  EmptyView::glbMin(void) const { return 0; }
311 
312  forceinline int
313  EmptyView::glbMax(void) const { return 0; }
314 
316  EmptyView::cardMin(Space&,unsigned int c) {
317  return c==0 ? ME_SET_NONE : ME_SET_FAILED;
318  }
319 
321  EmptyView::cardMax(Space&,unsigned int) {
322  return ME_SET_NONE;
323  }
324 
325 
328  return ME_SET_FAILED;
329  }
330 
333 
336 
338  EmptyView::intersect(Space&,int,int) { return ME_SET_NONE; }
339 
342  return ME_SET_FAILED; }
343 
345  EmptyView::exclude(Space&,int,int) { return ME_SET_NONE; }
346 
347  template<class I> ModEvent
349  return ME_SET_NONE;
350  }
351 
352  template<class I> ModEvent
354  return i() ? ME_SET_FAILED : ME_SET_NONE;
355  }
356 
357  template<class I> ModEvent
359  return ME_SET_NONE;
360  }
361 
362  /*
363  * Delta information for advisors
364  *
365  */
366  forceinline int
367  EmptyView::glbMin(const Delta&) const {
368  GECODE_NEVER;
369  return 0;
370  }
371 
372  forceinline int
373  EmptyView::glbMax(const Delta&) const {
374  GECODE_NEVER;
375  return 0;
376  }
377 
378  forceinline bool
379  EmptyView::glbAny(const Delta&) const {
380  GECODE_NEVER;
381  return false;
382  }
383 
384  forceinline int
385  EmptyView::lubMin(const Delta&) const {
386  GECODE_NEVER;
387  return 0;
388  }
389 
390  forceinline int
391  EmptyView::lubMax(const Delta&) const {
392  GECODE_NEVER;
393  return 0;
394  }
395 
396  forceinline bool
397  EmptyView::lubAny(const Delta&) const {
398  GECODE_NEVER;
399  return false;
400  }
401 
402  // Constant universe variable
403 
406 
407  forceinline unsigned int
408  UniverseView::glbSize(void) const { return Set::Limits::card; }
409 
410  forceinline unsigned int
411  UniverseView::lubSize(void) const { return Set::Limits::card; }
412 
413  forceinline unsigned int
414  UniverseView::unknownSize(void) const { return 0; }
415 
416  forceinline bool
417  UniverseView::contains(int) const { return true; }
418 
419  forceinline bool
420  UniverseView::notContains(int) const { return false; }
421 
422  forceinline unsigned int
423  UniverseView::cardMin(void) const { return Set::Limits::card; }
424 
425  forceinline unsigned int
426  UniverseView::cardMax(void) const { return Limits::card; }
427 
428  forceinline int
429  UniverseView::lubMin(void) const { return Limits::card; }
430 
431  forceinline int
432  UniverseView::lubMax(void) const { return Limits::card; }
433 
434  forceinline int
435  UniverseView::glbMin(void) const { return Limits::card; }
436 
437  forceinline int
438  UniverseView::glbMax(void) const { return Limits::card; }
439 
441  UniverseView::cardMin(Space&,unsigned int c) {
443  }
444 
446  UniverseView::cardMax(Space&,unsigned int c) {
447  return c>=Limits::card ? ME_SET_NONE : ME_SET_FAILED;
448  }
449 
450 
453  return ME_SET_NONE;
454  }
455 
458 
461 
464 
467 
468  template<class I> ModEvent
470  return i() ? ME_SET_FAILED : ME_SET_NONE;
471  }
472 
473  template<class I> forceinline ModEvent
475  return ME_SET_NONE;
476  }
477 
480  return (i>Limits::min ||
482  }
483 
484  template<class I> forceinline ModEvent
486  return (i() &&
487  (i.min()>Limits::min ||
488  i.max()<Limits::max) ) ?
490  }
491 
492 
493  /*
494  * Delta information for advisors
495  *
496  */
497  forceinline int
498  UniverseView::glbMin(const Delta&) const {
499  GECODE_NEVER;
500  return 0;
501  }
502 
503  forceinline int
504  UniverseView::glbMax(const Delta&) const {
505  GECODE_NEVER;
506  return 0;
507  }
508 
509  forceinline bool
510  UniverseView::glbAny(const Delta&) const {
511  GECODE_NEVER;
512  return false;
513  }
514 
515  forceinline int
516  UniverseView::lubMin(const Delta&) const {
517  GECODE_NEVER;
518  return 0;
519  }
520 
521  forceinline int
522  UniverseView::lubMax(const Delta&) const {
523  GECODE_NEVER;
524  return 0;
525  }
526 
527  forceinline bool
528  UniverseView::lubAny(const Delta&) const {
529  GECODE_NEVER;
530  return false;
531  }
532 
533  /*
534  * Iterators
535  *
536  */
537 
542  template<>
544  public:
546 
547 
548  LubRanges(void) {}
550  LubRanges(const EmptyView& x) { (void)x; }
552  void init(const EmptyView& x) { (void)x; }
554  };
555 
560  template<>
562  public:
564 
565 
566  GlbRanges(void) {}
568  GlbRanges(const EmptyView& x) { (void)x; }
570  void init(const EmptyView& x) { (void)x; }
572  };
573 
578  template<>
580  public:
582 
583 
584  LubRanges(void)
585  : Iter::Ranges::Singleton(Limits::min,
586  Limits::max) {}
589  : Iter::Ranges::Singleton(Limits::min,
590  Limits::max) {
591  (void)x;
592  }
594  void init(const UniverseView& x) { (void)x; }
596  };
597 
602  template<>
604  public:
606 
607 
608  GlbRanges(void)
609  : Iter::Ranges::Singleton(Limits::min,
610  Limits::max) {}
613  : Iter::Ranges::Singleton(Limits::min,
614  Limits::max) {
615  (void)x;
616  }
618  void init(const UniverseView& x) { (void)x; }
620  };
621 
622 
627  template<>
629  private:
630  ArrayRanges ar;
631  public:
633 
634 
635  LubRanges(void) {}
637  LubRanges(const ConstSetView& x) : ar(x.ranges,x.size) {}
639  void init(const ConstSetView& x) {
640  ar.init(x.ranges,x.size);
641  }
643 
645 
646 
647  bool operator ()(void) const { return ar(); }
649  void operator ++(void) { ++ar; }
651 
653 
654 
655  int min(void) const { return ar.min(); }
657  int max(void) const { return ar.max(); }
659  unsigned int width(void) const { return ar.width(); }
661  };
662 
667  template<>
668  class GlbRanges<ConstSetView> : public LubRanges<ConstSetView> {
669  public:
671 
672 
673  GlbRanges(void) {}
677  void init(const ConstSetView& x) {
679  }
681  };
682 
683  /*
684  * Testing
685  *
686  */
687  forceinline bool
688  same(const ConstSetView& x, const ConstSetView& y) {
689  if ((x.size != y.size) || (x.domSize != y.domSize))
690  return false;
691  for (int i=x.size; i--; )
692  if (x.ranges[2*i] != y.ranges[2*i] ||
693  x.ranges[2*i+1] != y.ranges[2*i+1])
694  return false;
695  return true;
696  }
697  forceinline bool
698  before(const ConstSetView& x, const ConstSetView& y) {
699  if (x.size < y.size)
700  return true;
701  if (x.domSize < y.domSize)
702  return true;
703  for (int i=x.size; i--; )
704  if (x.ranges[2*i] < y.ranges[2*i] ||
705  x.ranges[2*i+1] < y.ranges[2*i+1])
706  return true;
707  return false;
708  }
709 
710 
711  forceinline bool
712  same(const EmptyView&, const EmptyView&) {
713  return true;
714  }
715  forceinline bool
716  same(const UniverseView&, const UniverseView&) {
717  return true;
718  }
719 
720 }}
721 
722 // STATISTICS: set-var
723