Generated on Wed Sep 5 2012 18:52:05 for Gecode by doxygen 1.8.1.1
conv.cpp
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  * Christian Schulte <schulte@gecode.org>
6  * Gabor Szokoli <szokoli@gecode.org>
7  *
8  * Copyright:
9  * Guido Tack, 2004
10  * Christian Schulte, 2004
11  * Gabor Szokoli, 2004
12  *
13  * Last modified:
14  * $Date: 2011-08-09 02:04:53 +1000 (Tue, 09 Aug 2011) $ by $Author: schulte $
15  * $Revision: 12253 $
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 <gecode/set/convex.hh>
43 
44 namespace Gecode { namespace Set { namespace Convex {
45 
46  Actor*
47  Convex::copy(Space& home, bool share) {
48  return new (home) Convex(home,share,*this);
49  }
50 
53  //I, drop ranges from UB that are shorter than cardMin
54  //II, add range LB.smallest to LB.largest to LB
55  //III, Drop ranges from UB that do not contain all elements of LB
56  //that is: range.min()>LB.smallest or range.max()<LB.largest
57  //This leaves only one range.
58  //II
59  if (x0.glbSize()>0) {
61  } else {
62  //If lower bound is empty, we can still constrain the cardinality
63  //maximum with the width of the longest range in UB.
64  //No need to do this if there is anything in LB because UB
65  //becomes a single range then.
66  LubRanges<SetView> ubRangeIt(x0);
67  unsigned int maxWidth = 0;
68  for (;ubRangeIt();++ubRangeIt) {
69  assert(ubRangeIt());
70  maxWidth = std::max(maxWidth, ubRangeIt.width());
71  }
72  GECODE_ME_CHECK( x0.cardMax(home,maxWidth) );
73  }
74 
75 
76  //I + III
77 
78  Region r(home);
79  LubRanges<SetView> ubRangeIt(x0);
80  Iter::Ranges::Cache ubRangeItC(r,ubRangeIt);
81 
82  for (; ubRangeItC(); ++ubRangeItC) {
83  if (ubRangeItC.width() < (unsigned int) x0.cardMin()
84  || ubRangeItC.min() > x0.glbMin() //No need to test for empty lb.
85  || ubRangeItC.max() < x0.glbMax()
86  ) {
87  GECODE_ME_CHECK( x0.exclude(home,ubRangeItC.min(), ubRangeItC.max()) );
88  }
89  }
90  if (x0.assigned())
91  return home.ES_SUBSUMED(*this);
92  return ES_FIX;
93  }
94 
95 }}}
96 
97 // STATISTICS: set-prop