Generated on Fri Aug 24 2012 04:52:21 for Gecode by doxygen 1.8.1.1
match.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  * 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: 2010-07-15 01:46:18 +1000 (Thu, 15 Jul 2010) $ by $Author: schulte $
15  * $Revision: 11192 $
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 
43 
44 #include <gecode/set.hh>
45 #include <gecode/int.hh>
46 #include <gecode/set/rel.hh>
47 
48 namespace Gecode { namespace Set { namespace Int {
49 
50  template<class View>
53  : Propagator(home), x0(y0), xs(ys) {
54  x0.subscribe(home,*this, PC_SET_ANY);
56  }
57 
58  template<class View>
60  Match<View>::Match(Space& home, bool share, Match& p)
61  : Propagator(home,share,p) {
62  x0.update(home,share,p.x0);
63  xs.update(home,share,p.xs);
64  }
65 
66  template<class View>
69  unsigned int xs_size = static_cast<unsigned int>(xs.size());
70  GECODE_ME_CHECK(x0.cardMin(home,xs_size));
71  GECODE_ME_CHECK(x0.cardMax(home,xs_size));
72  if (xs_size == 1) {
73  SingletonView sv(xs[0]);
75  SingletonView>::post(home,x0, sv)));
76  } else {
77  // Sharing in xs is handled correctly in the propagator:
78  // if two views in xs are shared, this leads to failure.
79  (void) new (home) Match(home,x0,xs);
80  }
81  return ES_OK;
82  }
83 
84  template<class View>
85  PropCost
86  Match<View>::cost(const Space&, const ModEventDelta&) const {
87  return PropCost::linear(PropCost::LO, xs.size()+1);
88  }
89 
90  template<class View>
91  forceinline size_t
93  x0.cancel(home,*this, PC_SET_ANY);
94  xs.cancel(home,*this, Gecode::Int::PC_INT_BND);
95  (void) Propagator::dispose(home);
96  return sizeof(*this);
97  }
98 
99  template<class View>
100  Actor*
101  Match<View>::copy(Space& home, bool share) {
102  return new (home) Match(home,share,*this);
103  }
104 
105  template<class View>
106  ExecStatus
108 
109  int xs_size = xs.size();
110 
111  bool loopFlag;
112 
113  do {
114  loopFlag = false;
115 
116  // Order int vars in xs
117  GECODE_ME_CHECK(xs[0].gq(home,x0.lubMin()));
118  for (int i=xs_size-1; i--; ) {
119  GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i+1].gq(home,xs[i].min() + 1));
120  }
121 
122  GECODE_ME_CHECK_MODIFIED(loopFlag, xs[xs_size-1].lq(home,x0.lubMax()));
123  for (int i=xs_size-2; i--; ) {
124  GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].lq(home,xs[i+1].max() - 1));
125  }
126 
127  // if y from xs is assigned, add to glb(x0)
128  for (int i=xs_size; i--; ) {
129  if (xs[i].assigned()) {
130  GECODE_ME_CHECK_MODIFIED(loopFlag, x0.include(home,xs[i].val()));
131  }
132  }
133 
134  // intersect every y in xs with lub(x0)
135  for (int i=xs_size; i--; ) {
136  LubRanges<View> ub(x0);
137  GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].inter_r(home,ub,false));
138  }
139 
140  // remove gaps between vars in xs from lub(x0)
141  GECODE_ME_CHECK_MODIFIED(loopFlag,
142  x0.exclude(home,Limits::min,xs[0].min()-1));
143  GECODE_ME_CHECK_MODIFIED(loopFlag,
144  x0.exclude(home,xs[xs_size-1].max()+1,
145  Limits::max));
146 
147  for (int i=xs_size-1; i--; ) {
148  int start = xs[i].max() + 1;
149  int end = xs[i+1].min() - 1;
150  if (start<=end) {
151  GECODE_ME_CHECK_MODIFIED(loopFlag, x0.exclude(home,start,end));
152  }
153  }
154 
155  // try to assign vars in xs from glb(x0)
156  if (x0.glbSize()>0) {
157 
158  LubRanges<View> ub(x0);
160  GlbRanges<View> lb(x0);
162 
163  int i=0;
164  for (; ubv() && lbv() && ubv.val()==lbv.val();
165  ++ubv, ++lbv, i++) {
166  GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].eq(home,lbv.val()));
167  }
168 
169  if (i<xs_size-1 && x0.lubMax()==x0.glbMax()) {
170  LubRanges<View> lbx0(x0);
171  GlbRanges<View> ubx0(x0);
173  inter(lbx0, ubx0);
174 
175  int to = x0.glbMax();
176  int from = to;
177  while (inter()) {
178  from = inter.min();
179  ++inter;
180  }
181 
182  int i=xs_size-1;
183  for (int j=to; j>=from;j--,i--) {
184  GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].eq(home,j));
185  }
186  }
187  }
188 
189  } while (loopFlag);
190 
191  for (int i=xs_size; i--; )
192  if (!xs[i].assigned())
193  return ES_FIX;
194  return home.ES_SUBSUMED(*this);
195  }
196 
197 }}}
198 
199 // STATISTICS: set-prop