00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 namespace Gecode { namespace Int { namespace BinPacking {
00039
00040
00041
00042
00043
00044 forceinline
00045 Item::Item(void)
00046 : s(0) {}
00047 forceinline
00048 Item::Item(IntView b, int s0)
00049 : DerivedView<IntView>(b), s(s0) {}
00050
00051 forceinline IntView
00052 Item::bin(void) const {
00053 return x;
00054 }
00055 forceinline
00056 void Item::bin(IntView b) {
00057 x = b;
00058 }
00059 forceinline int
00060 Item::size(void) const {
00061 return s;
00062 }
00063 forceinline void
00064 Item::size(int s0) {
00065 s = s0;
00066 }
00067
00068 forceinline void
00069 Item::update(Space& home, bool share, Item& i) {
00070 x.update(home,share,i.x);
00071 s = i.s;
00072 }
00073
00074
00075 forceinline bool
00076 same(const Item& i, const Item& j) {
00077 return same(i.bin(),j.bin()) && (i.size() == j.size());
00078 }
00079 forceinline bool
00080 before(const Item& i, const Item& j) {
00081 return before(i.bin(),j.bin())
00082 || (same(i.bin(),j.bin()) && (i.size() == j.size()));
00083 }
00084
00086 forceinline bool
00087 operator <(const Item& i, const Item& j) {
00088 return i.size() > j.size();
00089 }
00090
00091
00092
00093
00094
00095
00096 forceinline
00097 SizeSet::SizeSet(void) {}
00098 forceinline
00099 SizeSet::SizeSet(Region& region, int n_max)
00100 : n(0), t(0), s(region.alloc<int>(n_max)) {}
00101 forceinline void
00102 SizeSet::add(int s0) {
00103 t += s0; s[n++] = s0;
00104 }
00105 forceinline int
00106 SizeSet::card(void) const {
00107 return n;
00108 }
00109 forceinline int
00110 SizeSet::total(void) const {
00111 return t;
00112 }
00113 forceinline int
00114 SizeSet::operator [](int i) const {
00115 return s[i];
00116 }
00117
00118 forceinline
00119 SizeSetMinusOne::SizeSetMinusOne(void) {}
00120 forceinline
00121 SizeSetMinusOne::SizeSetMinusOne(Region& region, int n_max)
00122 : SizeSet(region,n_max), p(-1) {}
00123 forceinline void
00124 SizeSetMinusOne::minus(int s0) {
00125
00126 do
00127 p++;
00128 while (s[p] > s0);
00129 assert(p < n);
00130 }
00131 forceinline int
00132 SizeSetMinusOne::card(void) const {
00133 assert(p >= 0);
00134 return n - 1;
00135 }
00136 forceinline int
00137 SizeSetMinusOne::total(void) const {
00138 assert(p >= 0);
00139 return t - s[p];
00140 }
00141 forceinline int
00142 SizeSetMinusOne::operator [](int i) const {
00143 assert(p >= 0);
00144 return s[(i < p) ? i : i+1];
00145 }
00146
00147
00148
00149
00150
00151
00152
00153
00154 forceinline
00155 Pack::Pack(Home home, ViewArray<OffsetView>& l0, ViewArray<Item>& bs0)
00156 : Propagator(home), l(l0), bs(bs0), t(0) {
00157 l.subscribe(home,*this,PC_INT_BND);
00158 bs.subscribe(home,*this,PC_INT_DOM);
00159 for (int i=bs.size(); i--; )
00160 t += bs[i].size();
00161 }
00162
00163 forceinline
00164 Pack::Pack(Space& home, bool shared, Pack& p)
00165 : Propagator(home,shared,p), t(p.t) {
00166 l.update(home,shared,p.l);
00167 bs.update(home,shared,p.bs);
00168 }
00169
00170 forceinline size_t
00171 Pack::dispose(Space& home) {
00172 l.cancel(home,*this,PC_INT_BND);
00173 bs.cancel(home,*this,PC_INT_DOM);
00174 (void) Propagator::dispose(home);
00175 return sizeof(*this);
00176 }
00177
00178 template<class SizeSet>
00179 forceinline bool
00180 Pack::nosum(const SizeSet& s, int a, int b, int& ap, int& bp) {
00181 if ((a <= 0) || (b >= s.total()))
00182 return false;
00183 int n=s.card()-1;
00184 int sc=0;
00185 int kp=0;
00186 while (sc + s[n-kp] < a) {
00187 sc += s[n-kp];
00188 kp++;
00189 }
00190 int k=0;
00191 int sa=0, sb = s[n-kp];
00192 while ((sa < a) && (sb <= b)) {
00193 sa += s[k++];
00194 if (sa < a) {
00195 kp--;
00196 sb += s[n-kp];
00197 sc -= s[n-kp];
00198 while (sa + sc >= a) {
00199 kp--;
00200 sc -= s[n-kp];
00201 sb += s[n-kp] - s[n-kp-k-1];
00202 }
00203 }
00204 }
00205 ap = sa + sc; bp = sb;
00206 return sa < a;
00207 }
00208
00209 template<class SizeSet>
00210 forceinline bool
00211 Pack::nosum(const SizeSet& s, int a, int b) {
00212 int ap, bp;
00213 return nosum(s, a, b, ap, bp);
00214 }
00215
00216 }}}
00217
00218
00219