this repo has no description
dekker.one
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 */
40 forceinline
41 Item::Item(void)
42 : s(0) {}
43 forceinline
44 Item::Item(IntView b, int s0)
45 : DerivedView<IntView>(b), s(s0) {}
46
47 forceinline IntView
48 Item::bin(void) const {
49 return x;
50 }
51 forceinline
52 void Item::bin(IntView b) {
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
80 /// For sorting according to size
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 */
91 forceinline
92 SizeSet::SizeSet(void) {}
93 forceinline
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
113 forceinline
114 SizeSetMinusOne::SizeSetMinusOne(void) {}
115 forceinline
116 SizeSetMinusOne::SizeSetMinusOne(Region& region, int n_max)
117 : SizeSet(region,n_max), p(-1) {}
118 forceinline void
119 SizeSetMinusOne::minus(int s0) {
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
132 SizeSetMinusOne::total(void) const {
133 assert(p >= 0);
134 return t - s[p];
135 }
136 forceinline int
137 SizeSetMinusOne::operator [](int i) const {
138 assert(p >= 0);
139 return s[(i < p) ? i : i+1];
140 }
141
142
143
144 /*
145 * Packing propagator
146 *
147 */
148
149 forceinline
150 Pack::Pack(Home home, ViewArray<OffsetView>& l0, ViewArray<Item>& bs0)
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
158 forceinline
159 Pack::Pack(Space& home, Pack& p)
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
166 Pack::dispose(Space& home) {
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