Generated on Sat Feb 7 2015 02:01:21 for Gecode by doxygen 1.8.9.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-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11  * $Revision: 13068 $
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
ExecStatus prune_lower(Space &home, int *dis, int n_dis)
Definition: int-base.hpp:155
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:109
bool initialized(void) const
Test whether graph has been initialized.
Definition: graph.hpp:49
Event for range-based overlap analysis.
Definition: nvalues.hh:62
void add(Space &home)
Add values of assigned views to value set.
Definition: int-base.hpp:72
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4032
int size(Space &home) const
Return a size estimate based on the union of all values.
Definition: int-base.hpp:124
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
void clear(unsigned int i)
Clear bit i.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-base.hpp:57
Mixed (n+1)-ary propagator.
Definition: propagator.hpp:268
First is subset of second iterator.
Domain consistent distinct propagator.
Definition: distinct.hh:251
Expensive.
Definition: core.hpp:564
int val
The value for the range (first or last value, depending on type)
Definition: nvalues.hh:67
No further events.
Definition: nvalues.hh:58
void eliminate(Space &home)
Eliminate subsumed views (all values included in the value set vs)
Definition: int-base.hpp:111
Range iterator for integer variable views
Definition: int.hpp:236
Handle to region.
Definition: region.hpp:61
Computation spaces.
Definition: core.hpp:1362
Value iterator for values in a bitset.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
ExecStatus all_in_valset(Space &home)
Propagate that all views must take values from value set.
Definition: int-base.hpp:145
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:134
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
void reset(void)
Reset iterator to start.
Execution has resulted in failure.
Definition: core.hpp:525
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Iterator over ranges.
Definition: val-set.hh:82
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
IntBase(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition: int-base.hpp:44
ExecStatus prune_upper(Space &home, Graph &g)
Definition: int-base.hpp:321
Range iterator for union of iterators.
int view
Which view does this range belong to.
Definition: nvalues.hh:69
unsigned int size(I &i)
Size of all ranges of range iterator i.
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
void purge(void)
Purge graph if necessary (reset information to avoid overflow)
Definition: graph.hpp:134
View-value graph for propagation of upper bound.
Definition: nvalues.hh:100
void set(unsigned int i)
Set bit i.
int size(void) const
Return size of maximal matching (excluding assigned views)
Definition: graph.hpp:45
bool mark(Space &home)
Definition: graph.hpp:155
ValSet vs
Value set storing the values of already assigned views.
Definition: nvalues.hh:142
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
void sync(Space &home)
Synchronize graph with new view domains.
Definition: graph.hpp:94
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
void disjoint(Space &home, Region &r, int *&dis, int &n_dis)
Definition: int-base.hpp:84
Integer view for integer variables.
Definition: view.hpp:129
const int infinity
Infinity for integers.
Definition: int.hh:117
RangeEventType ret
The event type.
Definition: nvalues.hh:65
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Range iterator for intersection of iterators.
Propagation cost.
Definition: core.hpp:537
ExecStatus
Definition: core.hpp:523
Symmetric diagonal bit matrix.
Definition: nvalues.hh:75
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:132
void free(T *b, long unsigned int n)
Delete n objects allocated from the region starting at b.
Definition: region.hpp:352
A range starts.
Definition: nvalues.hh:54
Execution is okay.
Definition: core.hpp:527
Class for storing values of already assigned views.
Definition: val-set.hh:48
Gecode toplevel namespace
void update(Space &home, bool share, ValSet &vs)
Update value set during cloning.
Definition: val-set.hpp:105
Number of values propagator for integer views base class.
Definition: nvalues.hh:136
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition: int-base.hpp:66
Home class for posting propagators
Definition: core.hpp:717
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
void init(Space &home, const ValSet &vs, const ViewArray< IntView > &x)
Initialize graph including values in vs.
Definition: graph.hpp:50
ExecStatus prune(Space &home)
Prune all values corresponding to unused edges.
Definition: graph.hpp:258