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