Generated on Tue Jan 19 2021 06:15:49 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  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <gecode/int/distinct.hh>
35 
36 namespace Gecode { namespace Int { namespace NValues {
37 
38  template<class VY>
42  vs(vs0) {}
43 
44  template<class VY>
48  vs.update(home, p.vs);
49  }
50 
51  template<class VY>
52  forceinline size_t
54  vs.dispose(home);
56  ::dispose(home);
57  return sizeof(*this);
58  }
59 
60  template<class VY>
61  PropCost
62  IntBase<VY>::cost(const Space&, const ModEventDelta&) const {
64  }
65 
66  template<class VY>
67  void
69  int n=x.size();
70  for (int i=n; i--; )
71  if (x[i].assigned()) {
72  vs.add(home, x[i].val());
73  x[i] = x[--n];
74  }
75  x.size(n);
76  }
77 
78  template<class VY>
79  void
80  IntBase<VY>::disjoint(Space& home, Region& r, int*& dis, int& n_dis) {
81  // Compute positions of disjoint views
82  int n=x.size();
83  dis = r.alloc<int>(n); n_dis = 0;
84 
85  int i=0;
86  while (i < n)
87  switch (vs.compare(x[i])) {
89  // All values are already contained in vs, eliminate x[i]
90  x[i].cancel(home, *this, PC_INT_DOM);
91  x[i] = x[--n];
92  break;
94  dis[n_dis++] = i++;
95  break;
97  i++;
98  break;
99  default:
100  GECODE_NEVER;
101  }
102  x.size(n);
103  }
104 
105  template<class VY>
106  void
108  int n=x.size();
109  for (int i=n; i--; )
110  if (vs.subset(x[i])) {
111  // All values are already contained in vs, eliminate x[i]
112  x[i].cancel(home, *this, PC_INT_DOM);
113  x[i] = x[--n];
114  }
115  x.size(n);
116  }
117 
118  template<class VY>
119  ExecStatus
121  for (int i=x.size(); i--; ) {
122  ValSet::Ranges vsr(vs);
123  GECODE_ME_CHECK(x[i].inter_r(home, vsr, false));
124  }
125  return home.ES_SUBSUMED(*this);
126  }
127 
128  template<class VY>
129  ExecStatus
130  IntBase<VY>::prune_lower(Space& home, int* dis, int n_dis) {
131  assert(n_dis > 0);
132 
133  // At least one more value will be needed
134  GECODE_ME_CHECK(y.gq(home,vs.size() + 1));
135 
136  Region r;
137 
138  // Only one additional value is allowed
139  if (y.max() == vs.size() + 1) {
140  // Compute possible values
141  ViewRanges<IntView>* r_dis = r.alloc<ViewRanges<IntView> >(n_dis);
142  for (int i=n_dis; i--; )
143  r_dis[i] = ViewRanges<IntView>(x[dis[i]]);
144  Iter::Ranges::NaryInter iv(r, r_dis, n_dis);
145  // Is there a common value at all?
146  if (!iv())
147  return ES_FAILED;
148  ValSet::Ranges vsr(vs);
149  Iter::Ranges::NaryUnion pv(r,iv,vsr);
150  // Enforce common values
151  for (int i=x.size(); i--; ) {
152  pv.reset();
153  GECODE_ME_CHECK(x[i].inter_r(home, pv, false));
154  }
155  return ES_OK;
156  }
157 
158  // Compute independent set for lower bound
159  // ovl is a bit-matrix defining whether two views overlap
160  SymBitMatrix ovl(r,x.size());
161  // deg[i] is the degree of x[i]
162  int* deg = r.alloc<int>(x.size());
163  // ovl_i[i] is an array of indices j such that x[j] overlaps with x[i]
164  int** ovl_i = r.alloc<int*>(x.size());
165  // n_ovl_i[i] defines how many integers are stored for ovl_i[i]
166  int* n_ovl_i = r.alloc<int>(x.size());
167  {
168 #ifndef NDEBUG
169  // Initialize all to null pointers so that things crash ;-)
170  for (int i=x.size(); i--; )
171  ovl_i[i] = NULL;
172 #endif
173  // For each i there can be at most n_dis-1 entries in ovl_i[i]
174  int* m = r.alloc<int>(n_dis*(n_dis-1));
175  for (int i=n_dis; i--; ) {
176  deg[dis[i]] = 0;
177  ovl_i[dis[i]] = m; m += n_dis-1;
178  }
179  }
180 
181  // Initialize overlap matrix by analyzing the view ranges
182  {
183  // Compute how many events are needed
184  // One event for the end marker
185  int n_re = 1;
186  // Two events for each range
187  for (int i=n_dis; i--; )
188  for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx)
189  n_re += 2;
190 
191  // Allocate and initialize events
192  RangeEvent* re = r.alloc<RangeEvent>(n_re);
193  {
194  int j=0;
195  for (int i=n_dis; i--; )
196  for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx) {
197  // Event when a range starts
198  re[j].ret=RET_FST; re[j].val=rx.min(); re[j].view=dis[i]; j++;
199  // Event when a range ends
200  re[j].ret=RET_LST; re[j].val=rx.max(); re[j].view=dis[i]; j++;
201  }
202  // Make this the last event
203  re[j].ret=RET_END; re[j].val=Int::Limits::infinity;
204  assert(j+1 == n_re);
205  }
206  // Sort and process events
207  Support::quicksort(re,n_re);
208 
209  // Current views with a range being active
210  Support::BitSet<Region> cur(r,static_cast<unsigned int>(x.size()));
211  // Process all events
212  for (int i=0; true; i++)
213  switch (re[i].ret) {
214  case RET_FST:
215  // Process all overlapping views
217  j(); ++j) {
218  int di = re[i].view, dj = j.val();
219  if (!ovl.get(di,dj)) {
220  ovl.set(di,dj);
221  ovl_i[di][deg[di]++] = dj;
222  ovl_i[dj][deg[dj]++] = di;
223  }
224  }
225  cur.set(static_cast<unsigned int>(re[i].view));
226  break;
227  case RET_LST:
228  cur.clear(static_cast<unsigned int>(re[i].view));
229  break;
230  case RET_END:
231  goto done;
232  default:
233  GECODE_NEVER;
234  }
235  done:
236  r.free<RangeEvent>(re,n_re);
237  }
238 
239  // While deg changes, n_ovl_i remains unchanged and is needed, so copy it
240  for (int i=n_dis; i--; ) {
241  assert(deg[dis[i]] < n_dis);
242  n_ovl_i[dis[i]] = deg[dis[i]];
243  }
244 
245  // Views in the independent set
246  int* ind = r.alloc<int>(n_dis);
247  int n_ind = 0;
248 
249  while (n_dis > 0) {
250  int i_min = n_dis-1;
251  int d_min = deg[dis[i_min]];
252  unsigned int s_min = x[dis[i_min]].size();
253 
254  // Find view with smallest (degree,size)
255  for (int i=n_dis-1; i--; )
256  if ((d_min > deg[dis[i]]) ||
257  ((d_min == deg[dis[i]]) && (s_min > x[dis[i]].size()))) {
258  i_min = i;
259  d_min = deg[dis[i]];
260  s_min = x[dis[i]].size();
261  }
262 
263  // i_min refers to view with smallest (degree,size)
264  ind[n_ind++] = dis[i_min]; dis[i_min] = dis[--n_dis];
265 
266  // Filter out non disjoint views
267  for (int i=n_dis; i--; )
268  if (ovl.get(dis[i],ind[n_ind-1])) {
269  // Update degree information
270  for (int j=n_ovl_i[dis[i]]; j--; )
271  deg[ovl_i[dis[i]][j]]--;
272  // Eliminate view
273  dis[i] = dis[--n_dis];
274  }
275  }
276  // Enforce lower bound
277  GECODE_ME_CHECK(y.gq(home,vs.size() + n_ind));
278 
279  // Prune, if possible
280  if (vs.size() + n_ind == y.max()) {
281  // Only values from the indepent set a can be taken
282  ViewRanges<IntView>* r_ind = r.alloc<ViewRanges<IntView> >(n_ind);
283  for (int i=n_ind; i--; )
284  r_ind[i] = ViewRanges<IntView>(x[ind[i]]);
285  Iter::Ranges::NaryUnion v_ind(r, r_ind, n_ind);
286  ValSet::Ranges vsr(vs);
287  v_ind |= vsr;
288  for (int i=x.size(); i--; ) {
289  v_ind.reset();
290  GECODE_ME_CHECK(x[i].inter_r(home,v_ind,false));
291  }
292  }
293  return ES_OK;
294  }
295 
296  template<class VY>
299  if (!g) {
300  g.init(home,vs,x);
301  } else {
302  g.purge();
303  g.sync();
304  }
305  GECODE_ME_CHECK(y.lq(home, g.size()));
306  if (y.min() == g.size()) {
307  // All values must be taken on
308  if (vs.size() + x.size() == g.size()) {
309  // This is in fact a distinct, simplify and rewrite
310  for (int i=x.size(); i--; ) {
311  ValSet::Ranges vsr(vs);
312  GECODE_ME_CHECK(x[i].minus_r(home, vsr, false));
313  }
314  GECODE_REWRITE(*this,Distinct::Dom<IntView>::post(home(*this),x));
315  }
316  if (g.mark())
317  GECODE_ES_CHECK(g.prune(home));
318  }
319  return ES_OK;
320  }
321 
322 }}}
323 
324 // STATISTICS: int-prop
ExecStatus prune_lower(Space &home, int *dis, int n_dis)
Definition: int-base.hpp:130
void free(void)
Free allocate memory.
Definition: region.hpp:356
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:116
Event for range-based overlap analysis.
Definition: nvalues.hh:58
void add(Space &home)
Add values of assigned views to value set.
Definition: int-base.hpp:68
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4714
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition: int-base.hpp:62
void sync(void)
Synchronize graph with new view domains.
Definition: graph.hpp:90
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3490
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:386
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-base.hpp:53
Mixed (n+1)-ary propagator.
Definition: pattern.hpp:272
First is subset of second iterator.
Domain consistent distinct propagator.
Definition: distinct.hh:283
int val
The value for the range (first or last value, depending on type)
Definition: nvalues.hh:63
No further events.
Definition: nvalues.hh:54
void eliminate(Space &home)
Eliminate subsumed views (all values included in the value set vs)
Definition: int-base.hpp:107
Range iterator for integer variable views
Definition: int.hpp:246
Handle to region.
Definition: region.hpp:55
#define forceinline
Definition: config.hpp:185
Computation spaces.
Definition: core.hpp:1701
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:91
ExecStatus all_in_valset(Space &home)
Propagate that all views must take values from value set.
Definition: int-base.hpp:120
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:130
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
void reset(void)
Reset iterator to start.
Gecode::IntArgs i({1, 2, 3, 4})
void dispose(Space &home)
Dispose value set.
Definition: val-set.hpp:126
Execution has resulted in failure.
Definition: core.hpp:473
Iterator over ranges.
Definition: val-set.hh:78
int size(void) const
Return size (number of values)
Definition: val-set.hpp:81
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:40
ExecStatus prune_upper(Space &home, Graph &g)
Definition: int-base.hpp:298
Range iterator for union of iterators.
int view
Which view does this range belong to.
Definition: nvalues.hh:65
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:130
void update(Space &home, ValSet &vs)
Update value set during cloning.
Definition: val-set.hpp:101
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1036
View-value graph for propagation of upper bound.
Definition: nvalues.hh:96
void set(unsigned int i)
Set bit i.
Expensive.
Definition: core.hpp:513
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
Definition: array.hpp:1331
ValSet vs
Value set storing the values of already assigned views.
Definition: nvalues.hh:138
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
void disjoint(Space &home, Region &r, int *&dis, int &n_dis)
Definition: int-base.hpp:80
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:767
RangeEventType ret
The event type.
Definition: nvalues.hh:61
Range iterator for intersection of iterators.
Iter::Ranges::CompareStatus compare(View x) const
Compare view x with value set.
Definition: val-set.hpp:161
Propagation cost.
Definition: core.hpp:485
ExecStatus
Definition: core.hpp:471
Symmetric diagonal bit matrix.
Definition: nvalues.hh:71
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
A range starts.
Definition: nvalues.hh:50
int size(void) const
Return size of maximal matching (excluding assigned views)
Definition: graph.hpp:41
Post propagator for SetVar x
Definition: set.hh:767
Execution is okay.
Definition: core.hpp:475
Class for storing values of already assigned views.
Definition: val-set.hh:44
Gecode toplevel namespace
bool subset(View x) const
Whether all values of x are included in the value set.
Definition: val-set.hpp:171
Number of values propagator for integer views base class.
Definition: nvalues.hh:132
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1138
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Home class for posting propagators
Definition: core.hpp:853
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
void add(Space &home, int v)
Add value v to value set.
Definition: val-set.hpp:45
void init(Space &home, const ValSet &vs, const ViewArray< IntView > &x)
Initialize graph including values in vs.
Definition: graph.hpp:46
ExecStatus prune(Space &home)
Prune all values corresponding to unused edges.
Definition: graph.hpp:255