this repo has no description
dekker.one
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 * Christian Schulte <schulte@gecode.org>
8 *
9 * Copyright:
10 * Guido Tack, 2004
11 * Christian Schulte, 2004
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#include <sstream>
39
40namespace Gecode { namespace Set {
41
42 template<class View>
43 forceinline
44 ComplementView<View>::ComplementView(void) {}
45
46 template<class View>
47 forceinline
48 ComplementView<View>::ComplementView(View& y)
49 : DerivedView<View>(y) {}
50
51 template<class View>
52 forceinline ModEvent
53 ComplementView<View>::me_negateset(ModEvent me) {
54 switch(me) {
55 case ME_SET_LUB : return ME_SET_GLB;
56 case ME_SET_GLB : return ME_SET_LUB;
57 case ME_SET_CLUB : return ME_SET_CGLB;
58 case ME_SET_CGLB : return ME_SET_CLUB;
59 default: return me;
60 }
61 }
62
63 template<class View>
64 forceinline PropCond
65 ComplementView<View>::pc_negateset(PropCond pc) {
66 switch(pc) {
67 case PC_SET_CLUB : return PC_SET_CGLB;
68 case PC_SET_CGLB : return PC_SET_CLUB;
69 default: return pc;
70 }
71 }
72
73 template<class View>
74 forceinline unsigned int
75 ComplementView<View>::glbSize(void) const {
76 return Limits::card - x.lubSize();
77 }
78
79 template<class View>
80 forceinline unsigned int
81 ComplementView<View>::lubSize(void) const {
82 return Limits::card - x.glbSize();
83 }
84
85 template<class View>
86 forceinline unsigned int
87 ComplementView<View>::unknownSize(void) const {
88 return lubSize() - glbSize();
89 }
90
91 template<class View>
92 forceinline bool
93 ComplementView<View>::contains(int n) const { return x.notContains(n); }
94
95 template<class View>
96 forceinline bool
97 ComplementView<View>::notContains(int n) const { return x.contains(n); }
98
99 template<class View>
100 forceinline unsigned int
101 ComplementView<View>::cardMin(void) const {
102 return Limits::card - x.cardMax();
103 }
104
105 template<class View>
106 forceinline unsigned int
107 ComplementView<View>::cardMax(void) const {
108 return Limits::card - x.cardMin();
109 }
110
111 template<class View>
112 forceinline int
113 ComplementView<View>::lubMin(void) const {
114 GlbRanges<View> lb(x);
115 RangesCompl<GlbRanges<View> > lbc(lb);
116 if (lbc()) {
117 return lbc.min();
118 } else {
119 return BndSet::MIN_OF_EMPTY;
120 }
121 }
122
123 template<class View>
124 forceinline int
125 ComplementView<View>::lubMax(void) const {
126 GlbRanges<View> lb(x);
127 RangesCompl<GlbRanges<View> > lbc(lb);
128 if (lbc()) {
129 while(lbc()) ++lbc;
130 return lbc.max();
131 } else {
132 return BndSet::MAX_OF_EMPTY;
133 }
134 }
135
136 template<class View>
137 forceinline int
138 ComplementView<View>::glbMin(void) const {
139 LubRanges<View> ub(x);
140 RangesCompl<LubRanges<View> > ubc(ub);
141 if (ubc()) {
142 return ubc.min();
143 } else {
144 return BndSet::MIN_OF_EMPTY;
145 }
146 }
147
148 template<class View>
149 forceinline int
150 ComplementView<View>::glbMax(void) const {
151 LubRanges<View> ub(x);
152 RangesCompl<LubRanges<View> > ubc(ub);
153 if (ubc()) {
154 while (ubc()) ++ubc;
155 return ubc.max();
156 } else {
157 return BndSet::MAX_OF_EMPTY;
158 }
159 }
160
161 template<class View>
162 forceinline ModEvent
163 ComplementView<View>::cardMin(Space& home, unsigned int c) {
164 if (c < Limits::card)
165 return me_negateset(x.cardMax(home, Limits::card - c));
166 return ME_SET_NONE;
167 }
168
169 template<class View>
170 forceinline ModEvent
171 ComplementView<View>::cardMax(Space& home, unsigned int c) {
172 if (c < Limits::card)
173 return me_negateset(x.cardMin(home, Limits::card - c));
174 return ME_SET_NONE;
175 }
176
177 template<class View>
178 forceinline ModEvent
179 ComplementView<View>::include(Space& home, int c) {
180 return me_negateset((x.exclude(home, c)));
181 }
182
183 template<class View>
184 forceinline ModEvent
185 ComplementView<View>::exclude(Space& home, int c) {
186 return me_negateset((x.include(home, c)));
187 }
188
189 template<class View>
190 forceinline ModEvent
191 ComplementView<View>::intersect(Space& home, int c) {
192 Iter::Ranges::Singleton si(c,c);
193 RangesCompl<Iter::Ranges::Singleton> csi(si);
194 return me_negateset((x.includeI(home, csi)));
195 }
196
197 template<class View>
198 forceinline ModEvent
199 ComplementView<View>::intersect(Space& home, int i, int j) {
200 Iter::Ranges::Singleton si(i,j);
201 RangesCompl<Iter::Ranges::Singleton> csi(si);
202 return me_negateset((x.includeI(home, csi)));
203 }
204
205 template<class View>
206 forceinline ModEvent
207 ComplementView<View>::include(Space& home, int j, int k) {
208 return me_negateset(x.exclude(home,j,k));
209 }
210
211 template<class View>
212 forceinline ModEvent
213 ComplementView<View>::exclude(Space& home, int j, int k) {
214 return me_negateset(x.include(home,j,k));
215 }
216
217 template<class View>
218 template<class I> ModEvent
219 ComplementView<View>::excludeI(Space& home,I& iter) {
220 return me_negateset(x.includeI(home,iter));
221 }
222
223 template<class View>
224 template<class I> ModEvent
225 ComplementView<View>::includeI(Space& home,I& iter) {
226 return me_negateset(x.excludeI(home,iter));
227 }
228
229 template<class View>
230 template<class I> ModEvent
231 ComplementView<View>::intersectI(Space& home,I& iter) {
232 RangesCompl<I> c(iter);
233 return me_negateset(x.includeI(home,c));
234 }
235
236 template<class View>
237 forceinline void
238 ComplementView<View>::subscribe(Space& home, Propagator& p, PropCond pc,
239 bool schedule) {
240 x.subscribe(home,p, pc_negateset(pc),schedule);
241 }
242
243 template<class View>
244 forceinline void
245 ComplementView<View>::cancel(Space& home, Propagator& p, PropCond pc) {
246 x.cancel(home,p, pc_negateset(pc));
247 }
248
249 template<class View>
250 forceinline void
251 ComplementView<View>::subscribe(Space& home, Advisor& a) {
252 x.subscribe(home,a);
253 }
254
255 template<class View>
256 forceinline void
257 ComplementView<View>::cancel(Space& home, Advisor& a) {
258 x.cancel(home,a);
259 }
260
261 template<class View>
262 forceinline void
263 ComplementView<View>::schedule(Space& home, Propagator& p, ModEvent me) {
264 return View::schedule(home,p,me_negateset(me));
265 }
266 template<class View>
267 forceinline ModEvent
268 ComplementView<View>::me(const ModEventDelta& med) {
269 return me_negateset(View::me(med));
270 }
271
272 template<class View>
273 forceinline ModEventDelta
274 ComplementView<View>::med(ModEvent me) {
275 return me_negateset(View::med(me));
276 }
277
278 /*
279 * Delta information for advisors
280 *
281 */
282
283 template<class View>
284 forceinline ModEvent
285 ComplementView<View>::modevent(const Delta& d) {
286 return me_negateset(View::modevent(d));
287 }
288
289 template<class View>
290 forceinline int
291 ComplementView<View>::glbMin(const Delta& d) const {
292 return x.lubMin(d);
293 }
294
295 template<class View>
296 forceinline int
297 ComplementView<View>::glbMax(const Delta& d) const {
298 return x.lubMax(d);
299 }
300
301 template<class View>
302 forceinline bool
303 ComplementView<View>::glbAny(const Delta& d) const {
304 return x.lubAny(d);
305 }
306
307 template<class View>
308 forceinline int
309 ComplementView<View>::lubMin(const Delta& d) const {
310 return x.glbMin(d);
311 }
312
313 template<class View>
314 forceinline int
315 ComplementView<View>::lubMax(const Delta& d) const {
316 return x.glbMax(d);
317 }
318
319 template<class View>
320 forceinline bool
321 ComplementView<View>::lubAny(const Delta& d) const {
322 return x.glbAny(d);
323 }
324
325
326 /**
327 * \brief %Range iterator for least upper bound of complement set views
328 * \ingroup TaskActorSetView
329 */
330 template<class View>
331 class LubRanges<ComplementView<View> > {
332 private:
333 GlbRanges<View> lb;
334 RangesCompl<GlbRanges<View> > lbc;
335 public:
336 /// \name Constructors and initialization
337 //@{
338 /// Default constructor
339 LubRanges(void) {}
340 /// Initialize with ranges for view \a x
341 LubRanges(const ComplementView<View>& x);
342 /// Initialize with ranges for view \a x
343 void init(const ComplementView<View>& x);
344 //@}
345
346 /// \name Iteration control
347 //@{
348 /// Test whether iterator is still at a range or done
349 bool operator ()(void) const;
350 /// Move iterator to next range (if possible)
351 void operator ++(void);
352 //@}
353
354 /// \name Range access
355 //@{
356 /// Return smallest value of range
357 int min(void) const;
358 /// Return largest value of range
359 int max(void) const;
360 /// Return width of ranges (distance between minimum and maximum)
361 unsigned int width(void) const;
362 //@}
363 };
364
365 template<class View>
366 forceinline
367 LubRanges<ComplementView<View> >::LubRanges(const ComplementView<View>& s)
368 : lb(s.base()), lbc(lb) {}
369
370 template<class View>
371 forceinline void
372 LubRanges<ComplementView<View> >::init(const ComplementView<View>& s) {
373 lb.init(s.base());
374 lbc.init(lb);
375 }
376
377 template<class View>
378 forceinline bool
379 LubRanges<ComplementView<View> >::operator ()(void) const { return lbc(); }
380
381 template<class View>
382 forceinline void
383 LubRanges<ComplementView<View> >::operator ++(void) { return ++lbc; }
384
385 template<class View>
386 forceinline int
387 LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }
388
389 template<class View>
390 forceinline int
391 LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }
392
393 template<class View>
394 forceinline unsigned int
395 LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }
396
397 /**
398 * \brief Range iterator for the least upper bound of double-complement-views
399 *
400 * This class provides (by specialization) a range iterator
401 * for the least upper bounds of complements of complement set views.
402 *
403 * \ingroup TaskActorSet
404 */
405 template<class View>
406 class LubRanges<ComplementView<ComplementView<View> > > :
407 public LubRanges<View> {
408 public:
409 /// \name Constructors and initialization
410 //@{
411 /// Default constructor
412 LubRanges(void) {}
413 /// Initialize with ranges for view \a x
414 LubRanges(const ComplementView<ComplementView<View> >& x);
415 /// Initialize with ranges for view \a x
416 void init(const ComplementView<ComplementView<View> >& x);
417 //@}
418 };
419
420 template<class View>
421 forceinline
422 LubRanges<ComplementView<ComplementView<View> > >::
423 LubRanges(const ComplementView<ComplementView<View> >& x) :
424 LubRanges<View>(x) {}
425
426 template<class View>
427 forceinline void
428 LubRanges<ComplementView<ComplementView<View> > >::
429 init(const ComplementView<ComplementView<View> >& x) {
430 LubRanges<View>::init(x);
431 }
432
433 /**
434 * \brief %Range iterator for greatest lower bound of complement set views
435 * \ingroup TaskActorSetView
436 */
437 template<class View>
438 class GlbRanges<ComplementView<View> > {
439 private:
440 LubRanges<View> ub;
441 RangesCompl<LubRanges<View> > ubc;
442 public:
443 /// \name Constructors and initialization
444 //@{
445 /// Default constructor
446 GlbRanges(void) {}
447 /// Initialize with ranges for view \a x
448 GlbRanges(const ComplementView<View> & x);
449 /// Initialize with ranges for view \a x
450 void init(const ComplementView<View> & x);
451 //@}
452
453 /// \name Iteration control
454 //@{
455 /// Test whether iterator is still at a range or done
456 bool operator ()(void) const;
457 /// Move iterator to next range (if possible)
458 void operator ++(void);
459 //@}
460
461 /// \name Range access
462 //@{
463 /// Return smallest value of range
464 int min(void) const;
465 /// Return largest value of range
466 int max(void) const;
467 /// Return width of ranges (distance between minimum and maximum)
468 unsigned int width(void) const;
469 //@}
470 };
471
472 template<class View>
473 forceinline
474 GlbRanges<ComplementView<View> >::GlbRanges(const ComplementView<View> & s)
475 : ub(s.base()), ubc(ub) {}
476
477 template<class View>
478 forceinline void
479 GlbRanges<ComplementView<View> >::init(const ComplementView<View> & s) {
480 ub.init(s.base());
481 ubc.init(ub);
482 }
483
484 template<class View>
485 forceinline bool
486 GlbRanges<ComplementView<View> >::operator ()(void) const { return ubc(); }
487
488 template<class View>
489 forceinline void
490 GlbRanges<ComplementView<View> >::operator ++(void) { return ++ubc; }
491
492 template<class View>
493 forceinline int
494 GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }
495
496 template<class View>
497 forceinline int
498 GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }
499
500 template<class View>
501 forceinline unsigned int
502 GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
503
504 /**
505 * \brief Range iterator for the greatest lower bound of double-complement-views
506 *
507 * This class provides (by specialization) a range iterator
508 * for the greatest lower bounds of complements of complement set views.
509 *
510 * \ingroup TaskActorSet
511 */
512 template<class View>
513 class GlbRanges<ComplementView<ComplementView<View> > > :
514 public GlbRanges<View> {
515 public:
516 /// \name Constructors and initialization
517 //@{
518 /// Default constructor
519 GlbRanges(void) {}
520 /// Initialize with ranges for view \a x
521 GlbRanges(const ComplementView<ComplementView<View> >& x);
522 /// Initialize with ranges for view \a x
523 void init(const ComplementView<ComplementView<View> >& x);
524 //@}
525 };
526
527 template<class View>
528 forceinline
529 GlbRanges<ComplementView<ComplementView<View> > >::
530 GlbRanges(const ComplementView<ComplementView<View> >& x) :
531 GlbRanges<View>(x) {}
532
533 template<class View>
534 forceinline void
535 GlbRanges<ComplementView<ComplementView<View> > >::
536 init(const ComplementView<ComplementView<View> >& x) {
537 GlbRanges<View>::init(x);
538 }
539
540 template<class Char, class Traits, class View>
541 std::basic_ostream<Char,Traits>&
542 operator <<(std::basic_ostream<Char,Traits>& os,
543 const ComplementView<View>& x) {
544 std::basic_ostringstream<Char,Traits> s;
545 s.copyfmt(os); s.width(0);
546 s << "(" << x.base() << ")^C";
547 return os << s.str();
548 }
549
550
551 template<class View>
552 forceinline bool
553 operator ==(const ComplementView<View>& x, const ComplementView<View>& y) {
554 return x.base() == y.base();
555 }
556
557 template<class View>
558 forceinline bool
559 operator !=(const ComplementView<View>& x, const ComplementView<View>& y) {
560 return x.base() != y.base();
561 }
562
563}}
564
565// STATISTICS: set-var