Generated on Sun Aug 26 2012 08:43:23 for Gecode by doxygen 1.8.1.1
complement.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  * Christian Schulte <schulte@gecode.org>
8  *
9  * Copyright:
10  * Guido Tack, 2004
11  * Christian Schulte, 2004
12  *
13  * Last modified:
14  * $Date: 2011-05-02 08:24:42 +1000 (Mon, 02 May 2011) $ by $Author: tack $
15  * $Revision: 11973 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include <sstream>
43 
44 namespace Gecode { namespace Set {
45 
46  template<class View>
49 
50  template<class View>
53  : DerivedView<View>(y) {}
54 
55  template<class View>
58  switch(me) {
59  case ME_SET_LUB : return ME_SET_GLB;
60  case ME_SET_GLB : return ME_SET_LUB;
61  case ME_SET_CLUB : return ME_SET_CGLB;
62  case ME_SET_CGLB : return ME_SET_CLUB;
63  default: return me;
64  }
65  }
66 
67  template<class View>
70  switch(pc) {
71  case PC_SET_CLUB : return PC_SET_CGLB;
72  case PC_SET_CGLB : return PC_SET_CLUB;
73  default: return pc;
74  }
75  }
76 
77  template<class View>
78  forceinline unsigned int
80  return Limits::card - x.lubSize();
81  }
82 
83  template<class View>
84  forceinline unsigned int
86  return Limits::card - x.glbSize();
87  }
88 
89  template<class View>
90  forceinline unsigned int
92  return lubSize() - glbSize();
93  }
94 
95  template<class View>
96  forceinline bool
97  ComplementView<View>::contains(int n) const { return x.notContains(n); }
98 
99  template<class View>
100  forceinline bool
101  ComplementView<View>::notContains(int n) const { return x.contains(n); }
102 
103  template<class View>
104  forceinline unsigned int
106  return Limits::card - x.cardMax();
107  }
108 
109  template<class View>
110  forceinline unsigned int
112  return Limits::card - x.cardMin();
113  }
114 
115  template<class View>
116  forceinline int
118  GlbRanges<View> lb(x);
119  RangesCompl<GlbRanges<View> > lbc(lb);
120  if (lbc()) {
121  return lbc.min();
122  } else {
123  return BndSet::MIN_OF_EMPTY;
124  }
125  }
126 
127  template<class View>
128  forceinline int
130  GlbRanges<View> lb(x);
131  RangesCompl<GlbRanges<View> > lbc(lb);
132  if (lbc()) {
133  while(lbc()) ++lbc;
134  return lbc.max();
135  } else {
136  return BndSet::MAX_OF_EMPTY;
137  }
138  }
139 
140  template<class View>
141  forceinline int
143  LubRanges<View> ub(x);
144  RangesCompl<LubRanges<View> > ubc(ub);
145  if (ubc()) {
146  return ubc.min();
147  } else {
148  return BndSet::MIN_OF_EMPTY;
149  }
150  }
151 
152  template<class View>
153  forceinline int
155  LubRanges<View> ub(x);
156  RangesCompl<LubRanges<View> > ubc(ub);
157  if (ubc()) {
158  while (ubc()) ++ubc;
159  return ubc.max();
160  } else {
161  return BndSet::MAX_OF_EMPTY;
162  }
163  }
164 
165  template<class View>
167  ComplementView<View>::cardMin(Space& home, unsigned int c) {
168  if (c < Limits::card)
169  return me_negateset(x.cardMax(home, Limits::card - c));
170  return ME_SET_NONE;
171  }
172 
173  template<class View>
175  ComplementView<View>::cardMax(Space& home, unsigned int c) {
176  if (c < Limits::card)
177  return me_negateset(x.cardMin(home, Limits::card - c));
178  return ME_SET_NONE;
179  }
180 
181  template<class View>
184  return me_negateset((x.exclude(home, c)));
185  }
186 
187  template<class View>
190  return me_negateset((x.include(home, c)));
191  }
192 
193  template<class View>
198  return me_negateset((x.includeI(home, csi)));
199  }
200 
201  template<class View>
206  return me_negateset((x.includeI(home, csi)));
207  }
208 
209  template<class View>
211  ComplementView<View>::include(Space& home, int j, int k) {
212  return me_negateset(x.exclude(home,j,k));
213  }
214 
215  template<class View>
217  ComplementView<View>::exclude(Space& home, int j, int k) {
218  return me_negateset(x.include(home,j,k));
219  }
220 
221  template<class View>
222  template<class I> ModEvent
224  return me_negateset(x.includeI(home,iter));
225  }
226 
227  template<class View>
228  template<class I> ModEvent
230  return me_negateset(x.excludeI(home,iter));
231  }
232 
233  template<class View>
234  template<class I> ModEvent
236  RangesCompl<I> c(iter);
237  return me_negateset(x.includeI(home,c));
238  }
239 
240  template<class View>
241  forceinline void
243  bool schedule) {
244  x.subscribe(home,p, pc_negateset(pc),schedule);
245  }
246 
247  template<class View>
248  forceinline void
250  x.cancel(home,p, pc_negateset(pc));
251  }
252 
253  template<class View>
254  forceinline void
256  x.subscribe(home,a);
257  }
258 
259  template<class View>
260  forceinline void
262  x.cancel(home,a);
263  }
264 
265  template<class View>
266  forceinline void
268  return View::schedule(home,p,me_negateset(me));
269  }
270  template<class View>
273  return me_negateset(View::me(med));
274  }
275 
276  template<class View>
279  return me_negateset(View::med(me));
280  }
281 
282  /*
283  * Delta information for advisors
284  *
285  */
286 
287  template<class View>
290  return me_negateset(View::modevent(d));
291  }
292 
293  template<class View>
294  forceinline int
296  return x.lubMin(d);
297  }
298 
299  template<class View>
300  forceinline int
302  return x.lubMax(d);
303  }
304 
305  template<class View>
306  forceinline bool
308  return x.lubAny(d);
309  }
310 
311  template<class View>
312  forceinline int
314  return x.glbMin(d);
315  }
316 
317  template<class View>
318  forceinline int
320  return x.glbMax(d);
321  }
322 
323  template<class View>
324  forceinline bool
326  return x.glbAny(d);
327  }
328 
329 
334  template<class View>
335  class LubRanges<ComplementView<View> > {
336  private:
337  GlbRanges<View> lb;
339  public:
341 
342 
343  LubRanges(void) {}
347  void init(const ComplementView<View>& x);
349 
351 
352 
353  bool operator ()(void) const;
355  void operator ++(void);
357 
359 
360 
361  int min(void) const;
363  int max(void) const;
365  unsigned int width(void) const;
367  };
368 
369  template<class View>
372  : lb(s.base()), lbc(lb) {}
373 
374  template<class View>
375  forceinline void
377  lb.init(s.base());
378  lbc.init(lb);
379  }
380 
381  template<class View>
382  forceinline bool
383  LubRanges<ComplementView<View> >::operator ()(void) const { return lbc(); }
384 
385  template<class View>
386  forceinline void
387  LubRanges<ComplementView<View> >::operator ++(void) { return ++lbc; }
388 
389  template<class View>
390  forceinline int
391  LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }
392 
393  template<class View>
394  forceinline int
395  LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }
396 
397  template<class View>
398  forceinline unsigned int
399  LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }
400 
409  template<class View>
411  public LubRanges<View> {
412  public:
414 
415 
416  LubRanges(void) {}
420  void init(const ComplementView<ComplementView<View> >& x);
422  };
423 
424  template<class View>
428  LubRanges<View>(x) {}
429 
430  template<class View>
431  forceinline void
435  }
436 
441  template<class View>
442  class GlbRanges<ComplementView<View> > {
443  private:
444  LubRanges<View> ub;
446  public:
448 
449 
450  GlbRanges(void) {}
452  GlbRanges(const ComplementView<View> & x);
454  void init(const ComplementView<View> & x);
456 
458 
459 
460  bool operator ()(void) const;
462  void operator ++(void);
464 
466 
467 
468  int min(void) const;
470  int max(void) const;
472  unsigned int width(void) const;
474  };
475 
476  template<class View>
479  : ub(s.base()), ubc(ub) {}
480 
481  template<class View>
482  forceinline void
484  ub.init(s.base());
485  ubc.init(ub);
486  }
487 
488  template<class View>
489  forceinline bool
490  GlbRanges<ComplementView<View> >::operator ()(void) const { return ubc(); }
491 
492  template<class View>
493  forceinline void
494  GlbRanges<ComplementView<View> >::operator ++(void) { return ++ubc; }
495 
496  template<class View>
497  forceinline int
498  GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }
499 
500  template<class View>
501  forceinline int
502  GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }
503 
504  template<class View>
505  forceinline unsigned int
506  GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
507 
516  template<class View>
518  public GlbRanges<View> {
519  public:
521 
522 
523  GlbRanges(void) {}
527  void init(const ComplementView<ComplementView<View> >& x);
529  };
530 
531  template<class View>
535  GlbRanges<View>(x) {}
536 
537  template<class View>
538  forceinline void
542  }
543 
544  template<class Char, class Traits, class View>
545  std::basic_ostream<Char,Traits>&
546  operator <<(std::basic_ostream<Char,Traits>& os,
547  const ComplementView<View>& x) {
548  std::basic_ostringstream<Char,Traits> s;
549  s.copyfmt(os); s.width(0);
550  s << "(" << x.base() << ")^C";
551  return os << s.str();
552  }
553 
554 }}
555 
556 // STATISTICS: set-var