Generated on Wed Jan 1 2020 10:37:59 for Gecode by doxygen 1.8.16
propagate.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, 2010
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 namespace Gecode { namespace Int { namespace BinPacking {
35 
36  /*
37  * Item
38  *
39  */
41  Item::Item(void)
42  : s(0) {}
44  Item::Item(IntView b, int s0)
45  : DerivedView<IntView>(b), s(s0) {}
46 
48  Item::bin(void) const {
49  return x;
50  }
53  x = b;
54  }
55  forceinline int
56  Item::size(void) const {
57  return s;
58  }
59  forceinline void
60  Item::size(int s0) {
61  s = s0;
62  }
63 
64  forceinline void
65  Item::update(Space& home, Item& i) {
66  x.update(home,i.x);
67  s = i.s;
68  }
69 
70 
71  forceinline bool
72  operator ==(const Item& i, const Item& j) {
73  return (i.bin() == j.bin()) && (i.size() == j.size());
74  }
75  forceinline bool
76  operator !=(const Item& i, const Item& j) {
77  return !(i == j);
78  }
79 
81  forceinline bool
82  operator <(const Item& i, const Item& j) {
83  return i.size() > j.size();
84  }
85 
86 
87  /*
88  * Size set
89  *
90  */
94  SizeSet::SizeSet(Region& region, int n_max)
95  : n(0), t(0), s(region.alloc<int>(n_max)) {}
96  forceinline void
97  SizeSet::add(int s0) {
98  t += s0; s[n++] = s0;
99  }
100  forceinline int
101  SizeSet::card(void) const {
102  return n;
103  }
104  forceinline int
105  SizeSet::total(void) const {
106  return t;
107  }
108  forceinline int
109  SizeSet::operator [](int i) const {
110  return s[i];
111  }
112 
117  : SizeSet(region,n_max), p(-1) {}
118  forceinline void
120  // This rests on the fact that items are removed in order
121  do
122  p++;
123  while (s[p] > s0);
124  assert(p < n);
125  }
126  forceinline int
127  SizeSetMinusOne::card(void) const {
128  assert(p >= 0);
129  return n - 1;
130  }
131  forceinline int
133  assert(p >= 0);
134  return t - s[p];
135  }
136  forceinline int
138  assert(p >= 0);
139  return s[(i < p) ? i : i+1];
140  }
141 
142 
143 
144  /*
145  * Packing propagator
146  *
147  */
148 
151  : Propagator(home), l(l0), bs(bs0), t(0) {
152  l.subscribe(home,*this,PC_INT_BND);
153  bs.subscribe(home,*this,PC_INT_DOM);
154  for (int i=0; i<bs.size(); i++)
155  t += bs[i].size();
156  }
157 
160  : Propagator(home,p), t(p.t) {
161  l.update(home,p.l);
162  bs.update(home,p.bs);
163  }
164 
165  forceinline size_t
167  l.cancel(home,*this,PC_INT_BND);
168  bs.cancel(home,*this,PC_INT_DOM);
169  (void) Propagator::dispose(home);
170  return sizeof(*this);
171  }
172 
173  template<class SizeSet>
174  forceinline bool
175  Pack::nosum(const SizeSet& s, int a, int b, int& ap, int& bp) {
176  if ((a <= 0) || (b >= s.total()))
177  return false;
178  int n=s.card()-1;
179  int sc=0;
180  int kp=0;
181  while (sc + s[n-kp] < a) {
182  sc += s[n-kp];
183  kp++;
184  }
185  int k=0;
186  int sa=0, sb = s[n-kp];
187  while ((sa < a) && (sb <= b)) {
188  sa += s[k++];
189  if (sa < a) {
190  kp--;
191  sb += s[n-kp];
192  sc -= s[n-kp];
193  while (sa + sc >= a) {
194  kp--;
195  sc -= s[n-kp];
196  sb += s[n-kp] - s[n-kp-k-1];
197  }
198  }
199  }
200  ap = sa + sc; bp = sb;
201  return sa < a;
202  }
203 
204  template<class SizeSet>
205  forceinline bool
206  Pack::nosum(const SizeSet& s, int a, int b) {
207  int ap, bp;
208  return nosum(s, a, b, ap, bp);
209  }
210 
211 }}}
212 
213 // STATISTICS: int-prop
214 
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1077
Example: Bin packing
int s
Size of item.
Definition: bin-packing.hh:57
bool nosum(const SizeSet &s, int a, int b, int &ap, int &bp)
Detect non-existence of sums in a .. b.
Definition: propagate.hpp:175
ViewArray< Item > bs
Items with bin and size.
Definition: bin-packing.hh:146
int t
Total size of all items.
Definition: bin-packing.hh:148
NodeType t
Type of node.
Definition: bool-expr.cpp:230
Computation spaces.
Definition: core.hpp:1742
int n
Number of size entries in the set.
Definition: bin-packing.hh:90
void update(Space &home, VarImpView< Var > &y)
Update this view to be a clone of view y.
Definition: view.hpp:567
Pack(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Constructor for posting.
Definition: propagate.hpp:150
ViewArray< OffsetView > l
Views for load of bins.
Definition: bin-packing.hh:144
bool operator<(const Item &i, const Item &j)
For sorting according to size.
Definition: propagate.hpp:82
int size(void) const
Return size of item.
Definition: propagate.hpp:56
Size sets.
Definition: bin-packing.hh:87
int p
Position of discarded item.
Definition: bin-packing.hh:114
Base-class for derived views.
Definition: view.hpp:230
Gecode toplevel namespace
Base-class for propagators.
Definition: core.hpp:1064
SizeSet(void)
Default constructor.
Definition: propagate.hpp:92
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
int card(void) const
Return cardinality of set (number of entries)
Definition: propagate.hpp:127
void minus(int s)
Discard size s.
Definition: propagate.hpp:119
SizeSetMinusOne(void)
Default constructor.
Definition: propagate.hpp:114
Home class for posting propagators
Definition: core.hpp:856
Handle to region.
Definition: region.hpp:55
void add(int s)
Add new size s.
Definition: propagate.hpp:97
bool operator!=(const Item &i, const Item &j)
Whether two items are not the same.
Definition: propagate.hpp:76
int card(void) const
Return cardinality of set (number of entries)
Definition: propagate.hpp:101
int operator[](int i) const
Return size of item i.
Definition: propagate.hpp:137
virtual size_t dispose(Space &home)
Destructor.
Definition: propagate.hpp:166
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
bool operator==(const Item &i, const Item &j)
Whether two items are the same.
Definition: propagate.hpp:72
Item(void)
Default constructor.
Definition: propagate.hpp:41
IntView x
View from which this view is derived.
Definition: view.hpp:238
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1607
int operator[](int i) const
Return size of item i.
Definition: propagate.hpp:109
IntView bin(void) const
Return bin of item.
Definition: propagate.hpp:48
Integer view for integer variables.
Definition: view.hpp:129
int t
Total size of the set.
Definition: bin-packing.hh:92
#define forceinline
Definition: config.hpp:185
int total(void) const
Return total size.
Definition: propagate.hpp:132
int total(void) const
Return total size.
Definition: propagate.hpp:105
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
View arrays.
Definition: array.hpp:253
void update(Space &home, Item &i)
Update item during cloning.
Definition: propagate.hpp:65
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
Gecode::IntArgs i({1, 2, 3, 4})
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
Bin-packing propagator.
Definition: bin-packing.hh:141
int * s
Array of sizes (will have more elements)
Definition: bin-packing.hh:94
Item combining bin and size information.
Definition: bin-packing.hh:53