Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
34namespace Gecode { namespace Int { namespace BinPacking {
35
36 /*
37 * Item
38 *
39 */
42 : s(0) {}
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
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
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
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3256
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1613
Home class for posting propagators
Definition core.hpp:856
Item combining bin and size information.
IntView bin(void) const
Return bin of item.
Definition propagate.hpp:48
void update(Space &home, Item &i)
Update item during cloning.
Definition propagate.hpp:65
Item(void)
Default constructor.
Definition propagate.hpp:41
int size(void) const
Return size of item.
Definition propagate.hpp:56
ViewArray< OffsetView > l
Views for load of bins.
ViewArray< Item > bs
Items with bin and size.
Pack(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Constructor for posting.
int t
Total size of all items.
bool nosum(const SizeSet &s, int a, int b, int &ap, int &bp)
Detect non-existence of sums in a .. b.
virtual size_t dispose(Space &home)
Destructor.
int operator[](int i) const
Return size of item i.
void minus(int s)
Discard size s.
SizeSetMinusOne(void)
Default constructor.
int p
Position of discarded item.
int total(void) const
Return total size.
int card(void) const
Return cardinality of set (number of entries)
int t
Total size of the set.
SizeSet(void)
Default constructor.
Definition propagate.hpp:92
void add(int s)
Add new size s.
Definition propagate.hpp:97
int total(void) const
Return total size.
int operator[](int i) const
Return size of item i.
int n
Number of size entries in the set.
int * s
Array of sizes (will have more elements)
int card(void) const
Return cardinality of set (number of entries)
Integer view for integer variables.
Definition view.hpp:129
friend class Space
Definition core.hpp:1068
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3505
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1744
View arrays.
Definition array.hpp:253
Bin-packing propagators
bool operator<(const Item &i, const Item &j)
Order, also for sorting according to size.
Definition propagate.hpp:82
bool operator!=(const Item &i, const Item &j)
Whether two items are not the same.
Definition propagate.hpp:76
bool operator==(const Item &i, const Item &j)
Whether two items are the same.
Definition propagate.hpp:72
Finite domain integers.
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
Gecode toplevel namespace
#define forceinline
Definition config.hpp:194