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
00039
00040
00041
00042 #ifndef __GECODE_INT_BIN_PACKING_HH__
00043 #define __GECODE_INT_BIN_PACKING_HH__
00044
00045 #include <gecode/int.hh>
00046
00052 namespace Gecode { namespace Int { namespace BinPacking {
00053
00057 class Item : public DerivedView<IntView> {
00058 protected:
00059 using DerivedView<IntView>::x;
00061 int s;
00062 public:
00064 Item(void);
00066 Item(IntView b, int s);
00067
00069 IntView bin(void) const;
00071 void bin(IntView b);
00073 int size(void) const;
00075 void size(int s);
00076
00078 void update(Space& home, bool share, Item& i);
00079 };
00080
00082 bool same(const Item& i, const Item& j);
00084 bool before(const Item& i, const Item& j);
00085
00087 bool operator <(const Item& i, const Item& j);
00088
00089
00091 class SizeSet {
00092 protected:
00094 int n;
00096 int t;
00098 int* s;
00099 public:
00101 SizeSet(void);
00103 SizeSet(Region& region, int n_max);
00105 void add(int s);
00107 int card(void) const;
00109 int total(void) const;
00111 int operator [](int i) const;
00112 };
00113
00115 class SizeSetMinusOne : public SizeSet {
00116 protected:
00118 int p;
00119 public:
00121 SizeSetMinusOne(void);
00123 SizeSetMinusOne(Region& region, int n);
00125 void minus(int s);
00127 int card(void) const;
00129 int total(void) const;
00131 int operator [](int i) const;
00132 };
00133
00134
00145 class Pack : public Propagator {
00146 protected:
00148 ViewArray<OffsetView> l;
00150 ViewArray<Item> bs;
00152 int t;
00154 Pack(Home home, ViewArray<OffsetView>& l, ViewArray<Item>& bs);
00156 Pack(Space& home, bool share, Pack& p);
00157 public:
00159 GECODE_INT_EXPORT
00160 static ExecStatus post(Home home,
00161 ViewArray<OffsetView>& l, ViewArray<Item>& bs);
00163 template<class SizeSet>
00164 bool nosum(const SizeSet& s, int a, int b, int& ap, int& bp);
00166 template<class SizeSet>
00167 bool nosum(const SizeSet& s, int a, int b);
00169 GECODE_INT_EXPORT
00170 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00172 GECODE_INT_EXPORT
00173 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00175 GECODE_INT_EXPORT
00176 virtual void reschedule(Space& home);
00178 GECODE_INT_EXPORT
00179 virtual Actor* copy(Space& home, bool share);
00181 virtual size_t dispose(Space& home);
00182 };
00183
00184
00186 class ConflictGraph {
00187 protected:
00189 Home& home;
00191 const IntVarArgs& b;
00193 unsigned int bins;
00195 int nodes(void) const;
00196
00198 class NodeSet : public Support::RawBitSetBase {
00199 public:
00201 NodeSet(void);
00203 NodeSet(Region& r, int n);
00205 NodeSet(Region& r, int n, const NodeSet& ns);
00207 void allocate(Region& r, int n);
00209 void init(Region& r, int n);
00211 bool in(int i) const;
00213 void incl(int i);
00215 void excl(int i);
00217 void copy(int n, const NodeSet& ns);
00219 void empty(int n);
00226 static bool iwn(NodeSet& iwa, const NodeSet& a,
00227 NodeSet& iwb, const NodeSet& b,
00228 const NodeSet& c, int n);
00229 };
00230
00232 class Node {
00233 public:
00235 NodeSet n;
00237 unsigned int d;
00239 unsigned int w;
00241 Node(void);
00242 };
00244 Node* node;
00245
00247 class Nodes {
00248 private:
00250 const NodeSet& ns;
00252 unsigned int c;
00253 public:
00255 Nodes(const NodeSet& ns);
00257
00258
00259 void operator ++(void);
00261
00263
00264
00265 int operator ()(void) const;
00267 };
00268
00270
00271
00272 class Clique {
00273 public:
00275 NodeSet n;
00277 unsigned int c;
00279 unsigned int w;
00281 Clique(Region& r, int m);
00283 void incl(int i, unsigned int w);
00285 void excl(int i, unsigned int w);
00286 };
00287
00289 int pivot(const NodeSet& a, const NodeSet& b) const;
00291 GECODE_INT_EXPORT
00292 ExecStatus bk(NodeSet& p, NodeSet& x);
00294
00296
00297
00298 Clique cur;
00300 Clique max;
00302 ExecStatus clique(void);
00304 ExecStatus clique(int i);
00306 ExecStatus clique(int i, int j);
00308 ExecStatus clique(int i, int j, int k);
00310 public:
00312 ConflictGraph(Home& home, Region& r, const IntVarArgs& b,
00313 int m);
00315 void edge(int i, int j, bool add=true);
00317 bool adjacent(int i, int j) const;
00319 ExecStatus post(void);
00321 IntSet maxclique(void) const;
00323 ~ConflictGraph(void);
00324 };
00325
00326 }}}
00327
00328 #include <gecode/int/bin-packing/propagate.hpp>
00329 #include <gecode/int/bin-packing/conflict-graph.hpp>
00330
00331 #endif
00332
00333
00334