Generated on Sat Feb 7 2015 02:01:30 for Gecode by doxygen 1.8.9.1
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  * Last modified:
14  * $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
15  * $Revision: 13068 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include <gecode/set.hh>
43 #include <gecode/int.hh>
44 
45 namespace Gecode { namespace Set { namespace Int {
46 
48  template<class I>
50  private:
52  int threshold;
54  I iter;
56  const SharedArray<int> elements;
58  const SharedArray<int> weights;
60  int index;
62  void next(void);
63  public:
65 
66  OverweightValues(void);
69  OverweightValues(int t,
70  SharedArray<int>& elements0,
71  SharedArray<int>& weights0,
72  I& i);
74  void init(int t,
75  SharedArray<int>& elements0,
76  SharedArray<int>& weights0,
77  I& i);
79 
81 
82  bool operator ()(void) const;
85  void operator ++(void);
87 
89  int val(void) const;
92  };
93 
94  template<class I>
95  forceinline void
97  while (iter()) {
98  while (elements[index]<iter.val()) index++;
99  assert(elements[index]==iter.val());
100  if (weights[index] > threshold) {
101  return;
102  }
103  ++iter;
104  }
105  }
106 
107  template<class I>
110 
111  template<class I>
114  SharedArray<int>& elements0,
115  SharedArray<int>& weights0,
116  I& i) : threshold(t),
117  iter(i),
118  elements(elements0),
119  weights(weights0),
120  index(0) {
121  next();
122  }
123 
124  template<class I>
125  forceinline void
127  SharedArray<int>& elements0,
128  SharedArray<int>& weights0,
129  I& i) {
130  threshold = t; iter = i;
131  elements = elements0; weights = weights0;
132  index = 0;
133  next();
134  }
135 
136  template<class I>
137  forceinline bool
138  OverweightValues<I>::operator ()(void) const { return iter(); }
139 
140  template<class I>
141  forceinline void
142  OverweightValues<I>::operator ++(void) { ++iter; next(); }
143 
144  template<class I>
145  forceinline int
146  OverweightValues<I>::val(void) const { return elements[index]; }
147 
148  template<class View>
151  const SharedArray<int>& elements0,
152  const SharedArray<int>& weights0,
153  View x0, Gecode::Int::IntView y0)
154  : Propagator(home), elements(elements0), weights(weights0),
155  x(x0), y(y0) {
156  home.notice(*this,AP_DISPOSE);
157  x.subscribe(home,*this, PC_SET_ANY);
158  y.subscribe(home,*this, Gecode::Int::PC_INT_BND);
159  }
160 
161  template<class View>
163  Weights<View>::Weights(Space& home, bool share, Weights& p)
164  : Propagator(home,share,p) {
165  x.update(home,share,p.x);
166  y.update(home,share,p.y);
167  elements.update(home,share,p.elements);
168  weights.update(home,share,p.weights);
169  }
170 
171  template<class View>
172  inline ExecStatus
174  const SharedArray<int>& weights,
175  View x, Gecode::Int::IntView y) {
176  if (elements.size() != weights.size())
177  throw ArgumentSizeMismatch("Weights");
178  Region r(home);
179  int* els_arr = r.alloc<int>(elements.size());
180  for (int i=elements.size(); i--;)
181  els_arr[i] = elements[i];
182  IntSet els(els_arr, elements.size());
183  IntSetRanges er(els);
184  GECODE_ME_CHECK(x.intersectI(home, er));
185  (void) new (home) Weights(home,elements,weights,x,y);
186  return ES_OK;
187  }
188 
189  template<class View>
190  PropCost
191  Weights<View>::cost(const Space&, const ModEventDelta&) const {
192  return PropCost::linear(PropCost::LO, y.size()+1);
193  }
194 
195  template<class View>
196  forceinline size_t
198  home.ignore(*this,AP_DISPOSE);
199  x.cancel(home,*this, PC_SET_ANY);
200  y.cancel(home,*this, Gecode::Int::PC_INT_BND);
201  elements.~SharedArray();
202  weights.~SharedArray();
203  (void) Propagator::dispose(home);
204  return sizeof(*this);
205  }
206 
207  template<class View>
208  Actor*
209  Weights<View>::copy(Space& home, bool share) {
210  return new (home) Weights(home,share,*this);
211  }
212 
214  template<class I>
216  int weightI(SharedArray<int>& elements,
218  I& iter) {
219  int sum = 0;
220  int i = 0;
222  for (; v(); ++v) {
223  // Skip all elements below the current
224  while (elements[i]<v.val()) i++;
225  assert(elements[i] == v.val());
226  sum += weights[i];
227  }
228  assert(!v());
229  return sum;
230  }
231 
232 
234  class IntLess {
235  public:
236  bool operator ()(int x, int y);
237  };
238 
239  forceinline bool
240  IntLess::operator ()(int x, int y) {
241  return x < y;
242  }
243 
244  template<class View>
245  ExecStatus
247 
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(home);
254  int* currentWeights = r.alloc<int>(size);
255 
258  for (int i=0; i<size; i++) {
259  if (!urv() || elements[i]<urv.val()) {
260  currentWeights[i] = 0;
261  } else {
262  assert(elements[i] == urv.val());
263  currentWeights[i] = weights[i];
264  ++urv;
265  }
266  }
267 
268  // Sort the weights of the unknown elements
269  IntLess il;
270  Support::quicksort<int>(currentWeights, size, il);
271 
272  // The maximum number of elements that can still be added to x
273  int delta = static_cast<int>(std::min(x.unknownSize(), x.cardMax() - x.glbSize()));
274 
275  // The weight of the elements already in x
276  GlbRanges<View> glb(x);
277  int glbWeight = weightI<GlbRanges<View> >(elements, weights, glb);
278 
279  // Compute the weight of the current lower bound of x, plus at most
280  // delta-1 further elements with smallest negative weights. This weight
281  // determines which elements in the upper bound cannot possibly be
282  // added to x (those whose weight would exceed the capacity even if
283  // all other elements are minimal)
284  int lowWeight = glbWeight;
285  for (int i=0; i<delta-1; i++) {
286  if (currentWeights[i] >= 0)
287  break;
288  lowWeight+=currentWeights[i];
289  }
290 
291  // Compute the lowest possible weight of x. If there is another element
292  // with negative weight left, then add its weight to lowWeight.
293  // Otherwise lowWeight is already the lowest possible weight.
294  int lowestWeight = lowWeight;
295  if (delta>0 && currentWeights[delta-1]<0)
296  lowestWeight+=currentWeights[delta-1];
297 
298  // If after including the minimal number of required elements,
299  // no more element with negative weight is available, then
300  // a tighter lower bound can be computed.
301  if ( (x.cardMin() - x.glbSize() > 0 &&
302  currentWeights[x.cardMin() - x.glbSize() - 1] >= 0) ||
303  currentWeights[0] >= 0 ) {
304  int lowestPosWeight = glbWeight;
305  for (unsigned int i=0; i<x.cardMin() - x.glbSize(); i++) {
306  lowestPosWeight += currentWeights[i];
307  }
308  lowestWeight = std::max(lowestWeight, lowestPosWeight);
309  }
310 
311  // Compute the highest possible weight of x as the weight of the lower
312  // bound plus the weight of the delta heaviest elements still in the
313  // upper bound.
314  int highestWeight = glbWeight;
315  for (int i=0; i<delta; i++) {
316  if (currentWeights[size-i-1]<=0)
317  break;
318  highestWeight += currentWeights[size-i-1];
319  }
320 
321  // Prune the weight using the computed bounds
322  GECODE_ME_CHECK(y.gq(home, lowestWeight));
323  GECODE_ME_CHECK(y.lq(home, highestWeight));
324 
325  // Exclude all elements that are too heavy from the set x.
326  // Elements are too heavy if their weight alone already
327  // exceeds the remaining capacity
328  int remainingCapacity = y.max()-lowWeight;
329 
330  UnknownRanges<View> ur2(x);
333  ov(remainingCapacity, elements, weights, urv2);
336  me = x.excludeI(home, ovr);
337  GECODE_ME_CHECK(me);
338  }
339  if (x.assigned()) {
340  // If x is assigned, just compute its weight and assign y.
341  GlbRanges<View> glb(x);
342  int w =
343  weightI<GlbRanges<View> >(elements, weights, glb);
344  GECODE_ME_CHECK(y.eq(home, w));
345  return home.ES_SUBSUMED(*this);
346  }
347 
348  return me_modified(me) ? ES_NOFIX : ES_FIX;
349  }
350 
351 }}}
352 
353 // STATISTICS: set-prop
NodeType t
Type of node.
Definition: bool-expr.cpp:234
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: weights.hpp:246
Value Iterator for values above a certain weight.
Definition: weights.hpp:49
Range iterator for the unknown set.
Definition: var-imp.hpp:406
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4041
Range iterator for integer sets.
Definition: int.hh:271
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
SharedArray< int > weights
Weights for the elements in the upper bound.
Definition: int.hh:266
Actor must always be disposed.
Definition: core.hpp:610
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
void operator++(void)
Move iterator to next value (if possible)
Definition: weights.hpp:142
int ModEvent
Type for modification events.
Definition: core.hpp:146
Base-class for propagators.
Definition: core.hpp:755
Handle to region.
Definition: region.hpp:61
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: weights.hpp:197
Propagation has computed fixpoint.
Definition: core.hpp:528
Computation spaces.
Definition: core.hpp:1362
Base-class for both propagators and branchers.
Definition: core.hpp:666
virtual Actor * copy(Space &home, bool)
Copy propagator during cloning.
Definition: weights.hpp:209
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: view.hpp:453
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
Gecode::IntArgs i(4, 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:216
Weights(Space &home, bool share, Weights &p)
Constructor for cloning p.
Definition: weights.hpp:163
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
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.
unsigned int size(I &i)
Size of all ranges of range iterator i.
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:173
bool operator()(void) const
Test whether iterator is still at a value or done.
Definition: weights.hpp:138
int size(void) const
Return number of elements.
Integer sets.
Definition: int.hh:171
int val(void) const
Return current value.
Definition: weights.hpp:146
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:271
void update(Space &home, bool share, VarImpView< Var > &y)
Update this view to be a clone of view y.
Definition: view.hpp:494
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as PC_LINEAR_LO)
Definition: weights.hpp:191
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
OverweightValues(void)
Default constructor.
Definition: weights.hpp:109
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:2849
View x
The set view.
Definition: int.hh:269
bool operator()(int x, int y)
Definition: weights.hpp:240
const Gecode::PropCond PC_SET_ANY
Propagate when any bound or the cardinality of a view changes.
Definition: var-type.hpp:248
const int v[7]
Definition: distinct.cpp:207
void update(Space &home, bool share, SharedHandle &sh)
Updating during cloning.
Definition: core.hpp:2656
Integer view for integer variables.
Definition: view.hpp:129
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
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:126
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.cpp:169
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
Propagation cost.
Definition: core.hpp:537
ExecStatus
Definition: core.hpp:523
#define forceinline
Definition: config.hpp:132
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
void weights(Home home, IntSharedArray elements, IntSharedArray weights, SetVar x, IntVar y)
Post propagator for .
Definition: int.cpp:179
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
int val(void) const
Return current value.
Propagator for weight of a set
Definition: int.hh:261
Gecode toplevel namespace
SharedArray< int > elements
List of elements in the upper bound.
Definition: int.hh:264
LinFloatExpr sum(const FloatVarArgs &x)
Construct linear float expression as sum of float variables.
Definition: float-expr.cpp:548
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
Exception: Arguments are of different size
Definition: exception.hpp:77
Sort order for integers.
Definition: weights.hpp:234