Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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$ by $Author$
11  * $Revision$
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>
52  vs.update(home, 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 {
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  ExecStatus
125  for (int i=x.size(); i--; ) {
126  ValSet::Ranges vsr(vs);
127  GECODE_ME_CHECK(x[i].inter_r(home, vsr, false));
128  }
129  return home.ES_SUBSUMED(*this);
130  }
131 
132  template<class VY>
133  ExecStatus
134  IntBase<VY>::prune_lower(Space& home, int* dis, int n_dis) {
135  assert(n_dis > 0);
136 
137  // At least one more value will be needed
138  GECODE_ME_CHECK(y.gq(home,vs.size() + 1));
139 
140  Region r;
141 
142  // Only one additional value is allowed
143  if (y.max() == vs.size() + 1) {
144  // Compute possible values
145  ViewRanges<IntView>* r_dis = r.alloc<ViewRanges<IntView> >(n_dis);
146  for (int i=n_dis; i--; )
147  r_dis[i] = ViewRanges<IntView>(x[dis[i]]);
148  Iter::Ranges::NaryInter iv(r, r_dis, n_dis);
149  // Is there a common value at all?
150  if (!iv())
151  return ES_FAILED;
152  ValSet::Ranges vsr(vs);
153  Iter::Ranges::NaryUnion pv(r,iv,vsr);
154  // Enforce common values
155  for (int i=x.size(); i--; ) {
156  pv.reset();
157  GECODE_ME_CHECK(x[i].inter_r(home, pv, false));
158  }
159  return ES_OK;
160  }
161 
162  // Compute independent set for lower bound
163  // ovl is a bit-matrix defining whether two views overlap
164  SymBitMatrix ovl(r,x.size());
165  // deg[i] is the degree of x[i]
166  int* deg = r.alloc<int>(x.size());
167  // ovl_i[i] is an array of indices j such that x[j] overlaps with x[i]
168  int** ovl_i = r.alloc<int*>(x.size());
169  // n_ovl_i[i] defines how many integers are stored for ovl_i[i]
170  int* n_ovl_i = r.alloc<int>(x.size());
171  {
172 #ifndef NDEBUG
173  // Initialize all to null pointers so that things crash ;-)
174  for (int i=x.size(); i--; )
175  ovl_i[i] = NULL;
176 #endif
177  // For each i there can be at most n_dis-1 entries in ovl_i[i]
178  int* m = r.alloc<int>(n_dis*(n_dis-1));
179  for (int i=n_dis; i--; ) {
180  deg[dis[i]] = 0;
181  ovl_i[dis[i]] = m; m += n_dis-1;
182  }
183  }
184 
185  // Initialize overlap matrix by analyzing the view ranges
186  {
187  // Compute how many events are needed
188  // One event for the end marker
189  int n_re = 1;
190  // Two events for each range
191  for (int i=n_dis; i--; )
192  for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx)
193  n_re += 2;
194 
195  // Allocate and initialize events
196  RangeEvent* re = r.alloc<RangeEvent>(n_re);
197  {
198  int j=0;
199  for (int i=n_dis; i--; )
200  for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx) {
201  // Event when a range starts
202  re[j].ret=RET_FST; re[j].val=rx.min(); re[j].view=dis[i]; j++;
203  // Event when a range ends
204  re[j].ret=RET_LST; re[j].val=rx.max(); re[j].view=dis[i]; j++;
205  }
206  // Make this the last event
207  re[j].ret=RET_END; re[j].val=Int::Limits::infinity;
208  assert(j+1 == n_re);
209  }
210  // Sort and process events
211  Support::quicksort(re,n_re);
212 
213  // Current views with a range being active
214  Support::BitSet<Region> cur(r,static_cast<unsigned int>(x.size()));
215  // Process all events
216  for (int i=0; true; i++)
217  switch (re[i].ret) {
218  case RET_FST:
219  // Process all overlapping views
221  j(); ++j) {
222  int di = re[i].view, dj = j.val();
223  if (!ovl.get(di,dj)) {
224  ovl.set(di,dj);
225  ovl_i[di][deg[di]++] = dj;
226  ovl_i[dj][deg[dj]++] = di;
227  }
228  }
229  cur.set(static_cast<unsigned int>(re[i].view));
230  break;
231  case RET_LST:
232  cur.clear(static_cast<unsigned int>(re[i].view));
233  break;
234  case RET_END:
235  goto done;
236  default:
237  GECODE_NEVER;
238  }
239  done:
240  r.free<RangeEvent>(re,n_re);
241  }
242 
243  // While deg changes, n_ovl_i remains unchanged and is needed, so copy it
244  for (int i=n_dis; i--; ) {
245  assert(deg[dis[i]] < n_dis);
246  n_ovl_i[dis[i]] = deg[dis[i]];
247  }
248 
249  // Views in the independent set
250  int* ind = r.alloc<int>(n_dis);
251  int n_ind = 0;
252 
253  while (n_dis > 0) {
254  int i_min = n_dis-1;
255  int d_min = deg[dis[i_min]];
256  unsigned int s_min = x[dis[i_min]].size();
257 
258  // Find view with smallest (degree,size)
259  for (int i=n_dis-1; i--; )
260  if ((d_min > deg[dis[i]]) ||
261  ((d_min == deg[dis[i]]) && (s_min > x[dis[i]].size()))) {
262  i_min = i;
263  d_min = deg[dis[i]];
264  s_min = x[dis[i]].size();
265  }
266 
267  // i_min refers to view with smallest (degree,size)
268  ind[n_ind++] = dis[i_min]; dis[i_min] = dis[--n_dis];
269 
270  // Filter out non disjoint views
271  for (int i=n_dis; i--; )
272  if (ovl.get(dis[i],ind[n_ind-1])) {
273  // Update degree information
274  for (int j=n_ovl_i[dis[i]]; j--; )
275  deg[ovl_i[dis[i]][j]]--;
276  // Eliminate view
277  dis[i] = dis[--n_dis];
278  }
279  }
280  // Enforce lower bound
281  GECODE_ME_CHECK(y.gq(home,vs.size() + n_ind));
282 
283  // Prune, if possible
284  if (vs.size() + n_ind == y.max()) {
285  // Only values from the indepent set a can be taken
286  ViewRanges<IntView>* r_ind = r.alloc<ViewRanges<IntView> >(n_ind);
287  for (int i=n_ind; i--; )
288  r_ind[i] = ViewRanges<IntView>(x[ind[i]]);
289  Iter::Ranges::NaryUnion v_ind(r, r_ind, n_ind);
290  ValSet::Ranges vsr(vs);
291  v_ind |= vsr;
292  for (int i=x.size(); i--; ) {
293  v_ind.reset();
294  GECODE_ME_CHECK(x[i].inter_r(home,v_ind,false));
295  }
296  }
297  return ES_OK;
298  }
299 
300  template<class VY>
303  if (!g) {
304  g.init(home,vs,x);
305  } else {
306  g.purge();
307  g.sync();
308  }
309  GECODE_ME_CHECK(y.lq(home, g.size()));
310  if (y.min() == g.size()) {
311  // All values must be taken on
312  if (vs.size() + x.size() == g.size()) {
313  // This is in fact a distinct, simplify and rewrite
314  for (int i=x.size(); i--; ) {
315  ValSet::Ranges vsr(vs);
316  GECODE_ME_CHECK(x[i].minus_r(home, vsr, false));
317  }
318  GECODE_REWRITE(*this,Distinct::Dom<IntView>::post(home(*this),x));
319  }
320  if (g.mark())
321  GECODE_ES_CHECK(g.prune(home));
322  }
323  return ES_OK;
324  }
325 
326 }}}
327 
328 // STATISTICS: int-prop
ExecStatus prune_lower(Space &home, int *dis, int n_dis)
Definition: int-base.hpp:134
void free(void)
Free allocate memory.
Definition: region.hpp:354
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:120
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:4634
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition: int-base.hpp:66
void sync(void)
Synchronize graph with new view domains.
Definition: graph.hpp:94
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3433
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:384
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-base.hpp:57
Mixed (n+1)-ary propagator.
Definition: pattern.hpp:276
First is subset of second iterator.
Domain consistent distinct propagator.
Definition: distinct.hh:253
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:240
Handle to region.
Definition: region.hpp:57
#define forceinline
Definition: config.hpp:182
Computation spaces.
Definition: core.hpp:1668
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:95
ExecStatus all_in_valset(Space &home)
Propagate that all views must take values from value set.
Definition: int-base.hpp:124
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.
void dispose(Space &home)
Dispose value set.
Definition: val-set.hpp:130
Execution has resulted in failure.
Definition: core.hpp:466
Iterator over ranges.
Definition: val-set.hh:82
int size(void) const
Return size (number of values)
Definition: val-set.hpp:85
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:302
Range iterator for union of iterators.
int view
Which view does this range belong to.
Definition: nvalues.hh:69
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
void update(Space &home, ValSet &vs)
Update value set during cloning.
Definition: val-set.hpp:105
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1029
View-value graph for propagation of upper bound.
Definition: nvalues.hh:100
void set(unsigned int i)
Set bit i.
Expensive.
Definition: core.hpp:506
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
Definition: array.hpp:1396
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:56
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
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:120
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:769
RangeEventType ret
The event type.
Definition: nvalues.hh:65
Range iterator for intersection of iterators.
Iter::Ranges::CompareStatus compare(View x) const
Compare view x with value set.
Definition: val-set.hpp:165
Propagation cost.
Definition: core.hpp:478
ExecStatus
Definition: core.hpp:464
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
A range starts.
Definition: nvalues.hh:54
int size(void) const
Return size of maximal matching (excluding assigned views)
Definition: graph.hpp:45
Post propagator for SetVar x
Definition: set.hh:769
Execution is okay.
Definition: core.hpp:468
Class for storing values of already assigned views.
Definition: val-set.hh:48
Gecode toplevel namespace
bool subset(View x) const
Whether all values of x are included in the value set.
Definition: val-set.hpp:175
Number of values propagator for integer views base class.
Definition: nvalues.hh:136
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1203
int ModEventDelta
Modification event deltas.
Definition: core.hpp:91
Home class for posting propagators
Definition: core.hpp:846
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
void add(Space &home, int v)
Add value v to value set.
Definition: val-set.hpp:49
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