Generated on Fri Jan 28 2022 04:43:06 for Gecode by doxygen 1.8.13
weights.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  * 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/set.hh>
39 #include <gecode/int.hh>
40 
41 namespace Gecode { namespace Set { namespace Int {
42 
44  template<class I>
46  private:
48  int threshold;
50  I iter;
52  const SharedArray<int> elements;
54  const SharedArray<int> weights;
56  int index;
58  void next(void);
59  public:
61 
62  OverweightValues(void);
65  OverweightValues(int t,
66  SharedArray<int>& elements0,
67  SharedArray<int>& weights0,
68  I& i);
70  void init(int t,
71  SharedArray<int>& elements0,
72  SharedArray<int>& weights0,
73  I& i);
75 
77 
78  bool operator ()(void) const;
81  void operator ++(void);
83 
85  int val(void) const;
88  };
89 
90  template<class I>
91  forceinline void
93  while (iter()) {
94  while (elements[index]<iter.val()) index++;
95  assert(elements[index]==iter.val());
96  if (weights[index] > threshold) {
97  return;
98  }
99  ++iter;
100  }
101  }
102 
103  template<class I>
106 
107  template<class I>
110  SharedArray<int>& elements0,
111  SharedArray<int>& weights0,
112  I& i) : threshold(t),
113  iter(i),
114  elements(elements0),
115  weights(weights0),
116  index(0) {
117  next();
118  }
119 
120  template<class I>
121  forceinline void
123  SharedArray<int>& elements0,
124  SharedArray<int>& weights0,
125  I& i) {
126  threshold = t; iter = i;
127  elements = elements0; weights = weights0;
128  index = 0;
129  next();
130  }
131 
132  template<class I>
133  forceinline bool
134  OverweightValues<I>::operator ()(void) const { return iter(); }
135 
136  template<class I>
137  forceinline void
138  OverweightValues<I>::operator ++(void) { ++iter; next(); }
139 
140  template<class I>
141  forceinline int
142  OverweightValues<I>::val(void) const { return elements[index]; }
143 
144  template<class View>
147  const SharedArray<int>& elements0,
148  const SharedArray<int>& weights0,
149  View x0, Gecode::Int::IntView y0)
150  : Propagator(home), elements(elements0), weights(weights0),
151  x(x0), y(y0) {
152  home.notice(*this,AP_DISPOSE);
153  x.subscribe(home,*this, PC_SET_ANY);
154  y.subscribe(home,*this, Gecode::Int::PC_INT_BND);
155  }
156 
157  template<class View>
160  : Propagator(home,p), elements(p.elements), weights(p.weights) {
161  x.update(home,p.x);
162  y.update(home,p.y);
163  }
164 
165  template<class View>
166  inline ExecStatus
168  const SharedArray<int>& weights,
169  View x, Gecode::Int::IntView y) {
170  if (elements.size() != weights.size())
171  throw ArgumentSizeMismatch("Weights");
172  Region r;
173  int* els_arr = r.alloc<int>(elements.size());
174  for (int i=elements.size(); i--;)
175  els_arr[i] = elements[i];
176  IntSet els(els_arr, elements.size());
177  IntSetRanges er(els);
178  GECODE_ME_CHECK(x.intersectI(home, er));
179  (void) new (home) Weights(home,elements,weights,x,y);
180  return ES_OK;
181  }
182 
183  template<class View>
184  PropCost
185  Weights<View>::cost(const Space&, const ModEventDelta&) const {
186  return PropCost::linear(PropCost::LO, y.size()+1);
187  }
188 
189  template<class View>
190  void
192  x.reschedule(home,*this, PC_SET_ANY);
193  y.reschedule(home,*this, Gecode::Int::PC_INT_BND);
194  }
195 
196  template<class View>
197  forceinline size_t
199  home.ignore(*this,AP_DISPOSE);
200  x.cancel(home,*this, PC_SET_ANY);
201  y.cancel(home,*this, Gecode::Int::PC_INT_BND);
202  elements.~SharedArray();
203  weights.~SharedArray();
204  (void) Propagator::dispose(home);
205  return sizeof(*this);
206  }
207 
208  template<class View>
209  Actor*
211  return new (home) Weights(home,*this);
212  }
213 
215  template<class I>
219  I& iter) {
220  int sum = 0;
221  int i = 0;
223  for (; v(); ++v) {
224  // Skip all elements below the current
225  while (elements[i]<v.val()) i++;
226  assert(elements[i] == v.val());
227  sum += weights[i];
228  }
229  assert(!v());
230  return sum;
231  }
232 
233 
235  class IntLess {
236  public:
237  bool operator ()(int x, int y);
238  };
239 
240  forceinline bool
242  return x < y;
243  }
244 
245  template<class View>
246  ExecStatus
248  ModEvent me = ME_SET_NONE;
249 
250  if (!x.assigned()) {
251  // Collect the weights of the elements in the unknown set in an array
252  int size = elements.size();
253  Region r;
254  int* minWeights = r.alloc<int>(size);
255  int* maxWeights = r.alloc<int>(size);
256 
259  for (int i=0; i<size; i++) {
260  if (!urv() || elements[i]<urv.val()) {
261  minWeights[i] = INT_MAX;
262  maxWeights[i] = INT_MIN;
263  } else {
264  assert(elements[i] == urv.val());
265  minWeights[i] = weights[i];
266  maxWeights[i] = weights[i];
267  ++urv;
268  }
269  }
270 
271  // Sort the weights of the unknown elements
272  IntLess il;
273  Support::quicksort<int>(minWeights, size, il);
274  Support::quicksort<int>(maxWeights, size, il);
275 
276  // The maximum number of elements that can still be added to x
277  int delta = static_cast<int>(std::min(x.unknownSize(), x.cardMax() - x.glbSize()));
278 
279  // The weight of the elements already in x
280  GlbRanges<View> glb(x);
281  int glbWeight = weightI<GlbRanges<View> >(elements, weights, glb);
282 
283  // Compute the weight of the current lower bound of x, plus at most
284  // delta-1 further elements with smallest negative weights. This weight
285  // determines which elements in the upper bound cannot possibly be
286  // added to x (those whose weight would exceed the capacity even if
287  // all other elements are minimal)
288  int lowWeight = glbWeight;
289  for (int i=0; i<delta-1; i++) {
290  if (minWeights[i] >= 0)
291  break;
292  lowWeight+=minWeights[i];
293  }
294 
295  // Compute the lowest possible weight of x. If there is another element
296  // with negative weight left, then add its weight to lowWeight.
297  // Otherwise lowWeight is already the lowest possible weight.
298  int lowestWeight = lowWeight;
299  if (delta>0 && minWeights[delta-1]<0)
300  lowestWeight+=minWeights[delta-1];
301 
302  // If after including the minimal number of required elements,
303  // no more element with negative weight is available, then
304  // a tighter lower bound can be computed.
305  if ( (x.cardMin() - x.glbSize() > 0 &&
306  minWeights[x.cardMin() - x.glbSize() - 1] >= 0) ||
307  minWeights[0] >= 0 ) {
308  int lowestPosWeight = glbWeight;
309  for (unsigned int i=0; i<x.cardMin() - x.glbSize(); i++) {
310  lowestPosWeight += minWeights[i];
311  }
312  lowestWeight = std::max(lowestWeight, lowestPosWeight);
313  }
314 
315  // Compute the highest possible weight of x as the weight of the lower
316  // bound plus the weight of the delta heaviest elements still in the
317  // upper bound.
318  int highestWeight = glbWeight;
319  for (int i=0; i<delta; i++) {
320  if (maxWeights[size-i-1]<=0)
321  break;
322  highestWeight += maxWeights[size-i-1];
323  }
324 
325  // Prune the weight using the computed bounds
326  GECODE_ME_CHECK(y.gq(home, lowestWeight));
327  GECODE_ME_CHECK(y.lq(home, highestWeight));
328 
329  // Exclude all elements that are too heavy from the set x.
330  // Elements are too heavy if their weight alone already
331  // exceeds the remaining capacity
332  int remainingCapacity = y.max()-lowWeight;
333 
334  UnknownRanges<View> ur2(x);
337  ov(remainingCapacity, elements, weights, urv2);
340  me = x.excludeI(home, ovr);
341  GECODE_ME_CHECK(me);
342  }
343  if (x.assigned()) {
344  // If x is assigned, just compute its weight and assign y.
345  GlbRanges<View> glb(x);
346  int w =
347  weightI<GlbRanges<View> >(elements, weights, glb);
348  GECODE_ME_CHECK(y.eq(home, w));
349  return home.ES_SUBSUMED(*this);
350  }
351 
352  // return me_modified(me) ? ES_NOFIX : ES_FIX;
353  return ES_NOFIX;
354  }
355 
356 }}}
357 
358 // STATISTICS: set-prop
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: view.hpp:527
void update(Space &home, VarImpView< Var > &y)
Update this view to be a clone of view y.
Definition: view.hpp:567
NodeType t
Type of node.
Definition: bool-expr.cpp:230
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: weights.hpp:247
Value Iterator for values above a certain weight.
Definition: weights.hpp:45
Range iterator for the unknown set.
Definition: var-imp.hpp:402
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4723
Range iterator for integer sets.
Definition: int.hh:292
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3490
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
SharedArray< int > weights
Weights for the elements in the upper bound.
Definition: int.hh:262
Actor must always be disposed.
Definition: core.hpp:561
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:166
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:386
void operator++(void)
Move iterator to next value (if possible)
Definition: weights.hpp:138
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: weights.hpp:210
int ModEvent
Type for modification events.
Definition: core.hpp:62
Base-class for propagators.
Definition: core.hpp:1023
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:81
Handle to region.
Definition: region.hpp:55
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: view.hpp:532
Weights(Space &home, Weights &p)
Constructor for cloning p.
Definition: weights.hpp:159
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: weights.hpp:198
#define forceinline
Definition: config.hpp:185
Computation spaces.
Definition: core.hpp:1701
int val(void) const
Return current value.
Base-class for both propagators and branchers.
Definition: core.hpp:627
int val(void) const
Return current value.
Definition: weights.hpp:142
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: view.hpp:521
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
virtual void reschedule(Space &home)
Schedule function.
Definition: weights.hpp:191
Gecode::IntArgs i({1, 2, 3, 4})
int weightI(SharedArray< int > &elements, SharedArray< int > &weights, I &iter)
Compute the weight of the elements in the iterator I.
Definition: weights.hpp:217
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:121
int size(void) const
Return number of elements.
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
Range iterator from value iterator.
Value iterator from range iterator.
static ExecStatus post(Home home, const SharedArray< int > &elements, const SharedArray< int > &weights, View x, Gecode::Int::IntView y)
Post propagator for .
Definition: weights.hpp:167
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1036
Integer sets.
Definition: int.hh:174
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:140
Gecode::Int::IntView y
The integer view.
Definition: int.hh:267
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
OverweightValues(void)
Default constructor.
Definition: weights.hpp:105
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3176
View x
The set view.
Definition: int.hh:265
bool operator()(int x, int y)
Definition: weights.hpp:241
const Gecode::PropCond PC_SET_ANY
Propagate when any bound or the cardinality of a view changes.
Definition: var-type.hpp:248
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
const int v[7]
Definition: distinct.cpp:259
bool operator()(void) const
Test whether iterator is still at a value or done.
Definition: weights.hpp:134
Integer view for integer variables.
Definition: view.hpp:129
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
void init(int t, SharedArray< int > &elements0, SharedArray< int > &weights0, I &i)
Initialize with elements/weights pairs, threshold t and iterator i.
Definition: weights.hpp:122
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4001
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3209
Propagation cost.
Definition: core.hpp:485
ExecStatus
Definition: core.hpp:471
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:139
Post propagator for SetVar x
Definition: set.hh:767
Execution is okay.
Definition: core.hpp:475
Propagation has not computed fixpoint.
Definition: core.hpp:474
Propagator for weight of a set
Definition: int.hh:257
Gecode toplevel namespace
SharedArray< int > elements
List of elements in the upper bound.
Definition: int.hh:260
int max(void) const
Return maximum of domain.
Definition: int.hpp:62
LinFloatExpr sum(const FloatVarArgs &x)
Construct linear float expression as sum of float variables.
Definition: float-expr.cpp:546
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as PC_LINEAR_LO)
Definition: weights.hpp:185
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Home class for posting propagators
Definition: core.hpp:853
Exception: Arguments are of different size
Definition: exception.hpp:73
Sort order for integers.
Definition: weights.hpp:235