Generated on Thu Feb 14 2013 20:59:31 for Gecode by doxygen 1.8.3.1
int-base.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2011
8  *
9  * Last modified:
10  * $Date: 2012-02-22 16:04:20 +1100 (Wed, 22 Feb 2012) $ by $Author: tack $
11  * $Revision: 12537 $
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 <gecode/int/distinct.hh>
39 
40 namespace Gecode { namespace Int { namespace NValues {
41 
42  template<class VY>
46  vs(vs0) {}
47 
48  template<class VY>
50  IntBase<VY>::IntBase(Space& home, bool share, IntBase<VY>& p)
51  : MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>(home, share, p) {
52  vs.update(home, share, p.vs);
53  }
54 
55  template<class VY>
56  forceinline size_t
58  vs.dispose(home);
60  ::dispose(home);
61  return sizeof(*this);
62  }
63 
64  template<class VY>
65  PropCost
66  IntBase<VY>::cost(const Space&, const ModEventDelta&) const {
67  return PropCost::quadratic(PropCost::HI, x.size());
68  }
69 
70  template<class VY>
71  void
73  int n=x.size();
74  for (int i=n; i--; )
75  if (x[i].assigned()) {
76  vs.add(home, x[i].val());
77  x[i] = x[--n];
78  }
79  x.size(n);
80  }
81 
82  template<class VY>
83  void
84  IntBase<VY>::disjoint(Space& home, Region& r, int*& dis, int& n_dis) {
85  // Compute positions of disjoint views
86  int n=x.size();
87  dis = r.alloc<int>(n); n_dis = 0;
88 
89  int i=0;
90  while (i < n)
91  switch (vs.compare(x[i])) {
93  // All values are already contained in vs, eliminate x[i]
94  x[i].cancel(home, *this, PC_INT_DOM);
95  x[i] = x[--n];
96  break;
98  dis[n_dis++] = i++;
99  break;
101  i++;
102  break;
103  default:
104  GECODE_NEVER;
105  }
106  x.size(n);
107  }
108 
109  template<class VY>
110  void
112  int n=x.size();
113  for (int i=n; i--; )
114  if (vs.subset(x[i])) {
115  // All values are already contained in vs, eliminate x[i]
116  x[i].cancel(home, *this, PC_INT_DOM);
117  x[i] = x[--n];
118  }
119  x.size(n);
120  }
121 
122  template<class VY>
123  int
124  IntBase<VY>::size(Space& home) const {
125  Region r(home);
126  assert(x.size() > 0);
127  ValSet::Ranges vsr(vs);
128  ViewRanges<IntView> xr(x[x.size()-1]);
129  Iter::Ranges::NaryUnion u(r,vsr,xr);
130  for (int i=x.size()-1; i--; ) {
131  ViewRanges<IntView> xir(x[i]);
132  u |= xir;
133  }
134  unsigned int s = Iter::Ranges::size(u);
135 
136  // To avoid overflow
137  if (static_cast<unsigned int>(x.size()+vs.size()) < s)
138  return x.size() + vs.size();
139  else
140  return static_cast<int>(s);
141  }
142 
143  template<class VY>
144  ExecStatus
146  for (int i=x.size(); i--; ) {
147  ValSet::Ranges vsr(vs);
148  GECODE_ME_CHECK(x[i].inter_r(home, vsr, false));
149  }
150  return home.ES_SUBSUMED(*this);
151  }
152 
153  template<class VY>
154  ExecStatus
155  IntBase<VY>::prune_lower(Space& home, int* dis, int n_dis) {
156  assert(n_dis > 0);
157 
158  // At least one more value will be needed
159  GECODE_ME_CHECK(y.gq(home,vs.size() + 1));
160 
161  Region r(home);
162 
163  // Only one additional value is allowed
164  if (y.max() == vs.size() + 1) {
165  // Compute possible values
166  ViewRanges<IntView>* r_dis = r.alloc<ViewRanges<IntView> >(n_dis);
167  for (int i=n_dis; i--; )
168  r_dis[i] = ViewRanges<IntView>(x[dis[i]]);
169  Iter::Ranges::NaryInter iv(r, r_dis, n_dis);
170  // Is there a common value at all?
171  if (!iv())
172  return ES_FAILED;
173  ValSet::Ranges vsr(vs);
174  Iter::Ranges::NaryUnion pv(r,iv,vsr);
175  // Enforce common values
176  for (int i=x.size(); i--; ) {
177  pv.reset();
178  GECODE_ME_CHECK(x[i].inter_r(home, pv, false));
179  }
180  return ES_OK;
181  }
182 
183  // Compute independent set for lower bound
184  // ovl is a bit-matrix defining whether two views overlap
185  SymBitMatrix ovl(r,x.size());
186  // deg[i] is the degree of x[i]
187  int* deg = r.alloc<int>(x.size());
188  // ovl_i[i] is an array of indices j such that x[j] overlaps with x[i]
189  int** ovl_i = r.alloc<int*>(x.size());
190  // n_ovl_i[i] defines how many integers are stored for ovl_i[i]
191  int* n_ovl_i = r.alloc<int>(x.size());
192  {
193 #ifndef NDEBUG
194  // Initialize all to null pointers so that things crash ;-)
195  for (int i=x.size(); i--; )
196  ovl_i[i] = NULL;
197 #endif
198  // For each i there can be at most n_dis-1 entries in ovl_i[i]
199  int* m = r.alloc<int>(n_dis*(n_dis-1));
200  for (int i=n_dis; i--; ) {
201  deg[dis[i]] = 0;
202  ovl_i[dis[i]] = m; m += n_dis-1;
203  }
204  }
205 
206  // Initialize overlap matrix by analyzing the view ranges
207  {
208  // Compute how many events are needed
209  // One event for the end marker
210  int n_re = 1;
211  // Two events for each range
212  for (int i=n_dis; i--; )
213  for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx)
214  n_re += 2;
215 
216  // Allocate and initialize events
217  RangeEvent* re = r.alloc<RangeEvent>(n_re);
218  int j=0;
219  for (int i=n_dis; i--; )
220  for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx) {
221  // Event when a range starts
222  re[j].ret=RET_FST; re[j].val=rx.min(); re[j].view=dis[i]; j++;
223  // Event when a range ends
224  re[j].ret=RET_LST; re[j].val=rx.max(); re[j].view=dis[i]; j++;
225  }
226  // Make this the last event
227  re[j].ret=RET_END; re[j].val=Int::Limits::infinity;
228  assert(j+1 == n_re);
229  // Sort and process events
230  Support::quicksort(re,n_re);
231 
232  // Current views with a range being active
233  Support::BitSet<Region> cur(r,static_cast<unsigned int>(x.size()));
234  // Process all events
235  for (int i=0; true; i++)
236  switch (re[i].ret) {
237  case RET_FST:
238  // Process all overlapping views
240  j(); ++j) {
241  int di = re[i].view, dj = j.val();
242  if (!ovl.get(di,dj)) {
243  ovl.set(di,dj);
244  ovl_i[di][deg[di]++] = dj;
245  ovl_i[dj][deg[dj]++] = di;
246  }
247  }
248  cur.set(static_cast<unsigned int>(re[i].view));
249  break;
250  case RET_LST:
251  cur.clear(static_cast<unsigned int>(re[i].view));
252  break;
253  case RET_END:
254  goto done;
255  default:
256  GECODE_NEVER;
257  }
258  done:
259  r.free<RangeEvent>(re,n_re);
260  }
261 
262  // While deg changes, n_ovl_i remains unchanged and is needed, so copy it
263  for (int i=n_dis; i--; ) {
264  assert(deg[dis[i]] < n_dis);
265  n_ovl_i[dis[i]] = deg[dis[i]];
266  }
267 
268  // Views in the independent set
269  int* ind = r.alloc<int>(n_dis);
270  int n_ind = 0;
271 
272  while (n_dis > 0) {
273  int i_min = n_dis-1;
274  int d_min = deg[dis[i_min]];
275  unsigned int s_min = x[dis[i_min]].size();
276 
277  // Find view with smallest (degree,size)
278  for (int i=n_dis-1; i--; )
279  if ((d_min > deg[dis[i]]) ||
280  ((d_min == deg[dis[i]]) && (s_min > x[dis[i]].size()))) {
281  i_min = i;
282  d_min = deg[dis[i]];
283  s_min = x[dis[i]].size();
284  }
285 
286  // i_min refers to view with smallest (degree,size)
287  ind[n_ind++] = dis[i_min]; dis[i_min] = dis[--n_dis];
288 
289  // Filter out non disjoint views
290  for (int i=n_dis; i--; )
291  if (ovl.get(dis[i],ind[n_ind-1])) {
292  // Update degree information
293  for (int j=n_ovl_i[dis[i]]; j--; )
294  deg[ovl_i[dis[i]][j]]--;
295  // Eliminate view
296  dis[i] = dis[--n_dis];
297  }
298  }
299  // Enforce lower bound
300  GECODE_ME_CHECK(y.gq(home,vs.size() + n_ind));
301 
302  // Prune, if possible
303  if (vs.size() + n_ind == y.max()) {
304  // Only values from the indepent set a can be taken
305  ViewRanges<IntView>* r_ind = r.alloc<ViewRanges<IntView> >(n_ind);
306  for (int i=n_ind; i--; )
307  r_ind[i] = ViewRanges<IntView>(x[ind[i]]);
308  Iter::Ranges::NaryUnion v_ind(r, r_ind, n_ind);
309  ValSet::Ranges vsr(vs);
310  v_ind |= vsr;
311  for (int i=x.size(); i--; ) {
312  v_ind.reset();
313  GECODE_ME_CHECK(x[i].inter_r(home,v_ind,false));
314  }
315  }
316  return ES_OK;
317  }
318 
319  template<class VY>
322  if (!g.initialized()) {
323  g.init(home,vs,x);
324  } else {
325  g.purge();
326  g.sync(home);
327  }
328  GECODE_ME_CHECK(y.lq(home, g.size()));
329  if (y.min() == g.size()) {
330  // All values must be taken on
331  if (vs.size() + x.size() == g.size()) {
332  // This is in fact a distinct, simplify and rewrite
333  for (int i=x.size(); i--; ) {
334  ValSet::Ranges vsr(vs);
335  GECODE_ME_CHECK(x[i].minus_r(home, vsr, false));
336  }
338  }
339  if (g.mark(home))
340  GECODE_ES_CHECK(g.prune(home));
341  }
342  return ES_OK;
343  }
344 
345 }}}
346 
347 // STATISTICS: int-prop