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 MiniModel {
00039
00040
00041
00042
00043
00044 template <class Var>
00045 forceinline
00046 LinExpr<Var>::Node::Node(void) : use(1) {
00047 }
00048
00049 template <class Var>
00050 forceinline void*
00051 LinExpr<Var>::Node::operator new(size_t size) {
00052 return Memory::malloc(size);
00053 }
00054
00055 template <class Var>
00056 forceinline void
00057 LinExpr<Var>::Node::operator delete(void* p, size_t) {
00058 Memory::free(p);
00059 }
00060
00061 template <class Var>
00062 bool
00063 LinExpr<Var>::Node::decrement(void) {
00064 if (--use == 0) {
00065 if ((l != NULL) && l->decrement())
00066 delete l;
00067 if ((r != NULL) && r->decrement())
00068 delete r;
00069 return true;
00070 }
00071 return false;
00072 }
00073
00074 template <class Var>
00075 int
00076 LinExpr<Var>::Node::fill(Int::Linear::Term<View> t[],
00077 int i, int m, int c_i, int& c_o) const {
00078 switch (this->t) {
00079 case NT_VAR:
00080 c_o = c_i;
00081 if (a != 0) {
00082 t[i].a=m*a; t[i].x=x;
00083 return i+1;
00084 } else {
00085 return i;
00086 }
00087 case NT_ADD:
00088 if (l == NULL) {
00089 return r->fill(t,i,m,c_i+m*c,c_o);
00090 } else {
00091 int c_m = 0;
00092 i = l->fill(t,i,m,c_i,c_m);
00093 return r->fill(t,i,m,c_m,c_o);
00094 }
00095 case NT_SUB:
00096 if (l == NULL) {
00097 return r->fill(t,i,-m,c_i+m*c,c_o);
00098 } else {
00099 int c_m = 0;
00100 i = l->fill(t,i,m,c_i,c_m);
00101 return r->fill(t,i,-m,c_m,c_o);
00102 }
00103 case NT_MUL:
00104 return l->fill(t,i,a*m,c_i,c_o);
00105 default:
00106 GECODE_NEVER;
00107 }
00108 GECODE_NEVER;
00109 return 0;
00110 }
00111
00112
00113
00114
00115
00116
00117
00118 template <class Var>
00119 inline
00120 LinExpr<Var>::LinExpr(void) :
00121 n(new Node) {
00122 n->n = 0;
00123 n->t = NT_VAR;
00124 n->l = n->r = NULL;
00125 n->a = 0;
00126 }
00127
00128 template <class Var>
00129 inline
00130 LinExpr<Var>::LinExpr(const Var& x, int a) :
00131 n(new Node) {
00132 n->n = 1;
00133 n->t = NT_VAR;
00134 n->l = n->r = NULL;
00135 n->a = a;
00136 n->x = x;
00137 }
00138
00139 template <class Var>
00140 inline
00141 LinExpr<Var>::LinExpr(const LinExpr& e0, NodeType t, const LinExpr& e1) :
00142 n(new Node) {
00143 n->n = e0.n->n+e1.n->n;
00144 n->t = t;
00145 n->l = e0.n; n->l->use++;
00146 n->r = e1.n; n->r->use++;
00147 }
00148
00149 template <class Var>
00150 inline
00151 LinExpr<Var>::LinExpr(const LinExpr& e, NodeType t, int c) :
00152 n(new Node) {
00153 n->n = e.n->n;
00154 n->t = t;
00155 n->l = NULL;
00156 n->r = e.n; n->r->use++;
00157 n->c = c;
00158 }
00159
00160 template <class Var>
00161 inline
00162 LinExpr<Var>::LinExpr(int a, const LinExpr& e) :
00163 n(new Node) {
00164 n->n = e.n->n;
00165 n->t = NT_MUL;
00166 n->l = e.n; n->l->use++;
00167 n->r = NULL;
00168 n->a = a;
00169 }
00170
00171 template <class Var>
00172 inline
00173 LinExpr<Var>::LinExpr(const LinExpr<Var>& e)
00174 : n(e.n) {
00175 n->use++;
00176 }
00177
00178 template <class Var>
00179 inline const LinExpr<Var>&
00180 LinExpr<Var>::operator=(const LinExpr<Var>& e) {
00181 if (this != &e) {
00182 if (n->decrement())
00183 delete n;
00184 n = e.n; n->use++;
00185 }
00186 return *this;
00187 }
00188
00189 template <class Var>
00190 forceinline
00191 LinExpr<Var>::~LinExpr(void) {
00192 if (n->decrement())
00193 delete n;
00194 }
00195
00196 template <class Var>
00197 inline void
00198 LinExpr<Var>::post(Space* home, IntRelType irt,
00199 IntConLevel icl, PropKind pk) const {
00200 GECODE_AUTOARRAY(Int::Linear::Term<View>, ts, n->n);
00201 int c_o = 0;
00202 int i = n->fill(ts,0,1,0,c_o);
00203 Int::Linear::post(home, ts, i, irt, -c_o, icl, pk);
00204 }
00205
00206 template <class Var>
00207 inline void
00208 LinExpr<Var>::post(Space* home, IntRelType irt, const BoolVar& b,
00209 IntConLevel icl, PropKind pk) const {
00210 GECODE_AUTOARRAY(Int::Linear::Term<View>, ts, n->n);
00211 int c_o = 0;
00212 int i = n->fill(ts,0,1,0,c_o);
00213 Int::Linear::post(home, ts, i, irt, -c_o, b, icl, pk);
00214 }
00215
00216 template <>
00217 inline IntVar
00218 LinExpr<IntVar>::post(Space* home, IntConLevel icl, PropKind pk) const {
00219 GECODE_AUTOARRAY(Int::Linear::Term<Int::IntView>, ts, n->n+1);
00220 int c_o = 0;
00221 int i = n->fill(ts,0,1,0,c_o);
00222 int min, max;
00223 Int::Linear::estimate(&ts[0],i,c_o,min,max);
00224 IntVar x(home, min, max);
00225 ts[i].x = x; ts[i].a = -1;
00226 Int::Linear::post(home, ts, i+1, IRT_EQ, -c_o, icl, pk);
00227 return x;
00228 }
00229
00230 template <>
00231 inline IntVar
00232 LinExpr<BoolVar>::post(Space* home, IntConLevel icl, PropKind pk) const {
00233 GECODE_AUTOARRAY(Int::Linear::Term<Int::BoolView>, ts, n->n+1);
00234 int c_o = 0;
00235 int i = n->fill(ts,0,1,0,c_o);
00236 int min, max;
00237 Int::Linear::estimate(&ts[0],i,c_o,min,max);
00238 IntVar x(home, min, max);
00239 Int::Linear::post(home, ts, i, IRT_EQ, x, -c_o, icl, pk);
00240 return x;
00241 }
00242
00243 }}
00244
00245 inline Gecode::MiniModel::LinExpr<Gecode::IntVar>
00246 operator+(int c,
00247 const Gecode::MiniModel::LinExpr<Gecode::IntVar>& e) {
00248 return Gecode::MiniModel::LinExpr<Gecode::IntVar>(e,Gecode::MiniModel::LinExpr<Gecode::IntVar>::NT_ADD,c);
00249 }
00250 inline Gecode::MiniModel::LinExpr<Gecode::IntVar>
00251 operator+(const Gecode::MiniModel::LinExpr<Gecode::IntVar>& e,
00252 int c) {
00253 return Gecode::MiniModel::LinExpr<Gecode::IntVar>(e,Gecode::MiniModel::LinExpr<Gecode::IntVar>::NT_ADD,c);
00254 }
00255 inline Gecode::MiniModel::LinExpr<Gecode::IntVar>
00256 operator+(const Gecode::MiniModel::LinExpr<Gecode::IntVar>& e1,
00257 const Gecode::MiniModel::LinExpr<Gecode::IntVar>& e2) {
00258 return Gecode::MiniModel::LinExpr<Gecode::IntVar>(e1,Gecode::MiniModel::LinExpr<Gecode::IntVar>::NT_ADD,e2);
00259 }
00260 inline Gecode::MiniModel::LinExpr<Gecode::IntVar>
00261 operator-(int c,
00262 const Gecode::MiniModel::LinExpr<Gecode::IntVar>& e) {
00263 return Gecode::MiniModel::LinExpr<Gecode::IntVar>(e,Gecode::MiniModel::LinExpr<Gecode::IntVar>::NT_SUB,c);
00264 }
00265 inline Gecode::MiniModel::LinExpr<Gecode::IntVar>
00266 operator-(const Gecode::MiniModel::LinExpr<Gecode::IntVar>& e,
00267 int c) {
00268 return Gecode::MiniModel::LinExpr<Gecode::IntVar>(e,Gecode::MiniModel::LinExpr<Gecode::IntVar>::NT_ADD,-c);
00269 }
00270 inline Gecode::MiniModel::LinExpr<Gecode::IntVar>
00271 operator-(const Gecode::MiniModel::LinExpr<Gecode::IntVar>& e1,
00272 const Gecode::MiniModel::LinExpr<Gecode::IntVar>& e2) {
00273 return Gecode::MiniModel::LinExpr<Gecode::IntVar>(e1,Gecode::MiniModel::LinExpr<Gecode::IntVar>::NT_SUB,e2);
00274 }
00275 inline Gecode::MiniModel::LinExpr<Gecode::IntVar>
00276 operator-(const Gecode::MiniModel::LinExpr<Gecode::IntVar>& e) {
00277 return Gecode::MiniModel::LinExpr<Gecode::IntVar>(e,Gecode::MiniModel::LinExpr<Gecode::IntVar>::NT_SUB,0);
00278 }
00279 inline Gecode::MiniModel::LinExpr<Gecode::IntVar>
00280 operator*(int a, const Gecode::IntVar& x) {
00281 return Gecode::MiniModel::LinExpr<Gecode::IntVar>(x,a);
00282 }
00283 inline Gecode::MiniModel::LinExpr<Gecode::IntVar>
00284 operator*(const Gecode::IntVar& x, int a) {
00285 return Gecode::MiniModel::LinExpr<Gecode::IntVar>(x,a);
00286 }
00287 inline Gecode::MiniModel::LinExpr<Gecode::IntVar>
00288 operator*(const Gecode::MiniModel::LinExpr<Gecode::IntVar>& e, int a) {
00289 return Gecode::MiniModel::LinExpr<Gecode::IntVar>(a,e);
00290 }
00291 inline Gecode::MiniModel::LinExpr<Gecode::IntVar>
00292 operator*(int a, const Gecode::MiniModel::LinExpr<Gecode::IntVar>& e) {
00293 return Gecode::MiniModel::LinExpr<Gecode::IntVar>(a,e);
00294 }
00295
00296
00297 inline Gecode::MiniModel::LinExpr<Gecode::BoolVar>
00298 operator+(int c,
00299 const Gecode::MiniModel::LinExpr<Gecode::BoolVar>& e) {
00300 return Gecode::MiniModel::LinExpr<Gecode::BoolVar>(e,Gecode::MiniModel::LinExpr<Gecode::BoolVar>::NT_ADD,c);
00301 }
00302 inline Gecode::MiniModel::LinExpr<Gecode::BoolVar>
00303 operator+(const Gecode::MiniModel::LinExpr<Gecode::BoolVar>& e,
00304 int c) {
00305 return Gecode::MiniModel::LinExpr<Gecode::BoolVar>(e,Gecode::MiniModel::LinExpr<Gecode::BoolVar>::NT_ADD,c);
00306 }
00307 inline Gecode::MiniModel::LinExpr<Gecode::BoolVar>
00308 operator+(const Gecode::MiniModel::LinExpr<Gecode::BoolVar>& e1,
00309 const Gecode::MiniModel::LinExpr<Gecode::BoolVar>& e2) {
00310 return Gecode::MiniModel::LinExpr<Gecode::BoolVar>(e1,Gecode::MiniModel::LinExpr<Gecode::BoolVar>::NT_ADD,e2);
00311 }
00312 inline Gecode::MiniModel::LinExpr<Gecode::BoolVar>
00313 operator-(int c,
00314 const Gecode::MiniModel::LinExpr<Gecode::BoolVar>& e) {
00315 return Gecode::MiniModel::LinExpr<Gecode::BoolVar>(e,Gecode::MiniModel::LinExpr<Gecode::BoolVar>::NT_SUB,c);
00316 }
00317 inline Gecode::MiniModel::LinExpr<Gecode::BoolVar>
00318 operator-(const Gecode::MiniModel::LinExpr<Gecode::BoolVar>& e,
00319 int c) {
00320 return Gecode::MiniModel::LinExpr<Gecode::BoolVar>(e,Gecode::MiniModel::LinExpr<Gecode::BoolVar>::NT_ADD,-c);
00321 }
00322 inline Gecode::MiniModel::LinExpr<Gecode::BoolVar>
00323 operator-(const Gecode::MiniModel::LinExpr<Gecode::BoolVar>& e1,
00324 const Gecode::MiniModel::LinExpr<Gecode::BoolVar>& e2) {
00325 return Gecode::MiniModel::LinExpr<Gecode::BoolVar>(e1,Gecode::MiniModel::LinExpr<Gecode::BoolVar>::NT_SUB,e2);
00326 }
00327 inline Gecode::MiniModel::LinExpr<Gecode::BoolVar>
00328 operator-(const Gecode::MiniModel::LinExpr<Gecode::BoolVar>& e) {
00329 return Gecode::MiniModel::LinExpr<Gecode::BoolVar>(e,Gecode::MiniModel::LinExpr<Gecode::BoolVar>::NT_SUB,0);
00330 }
00331 inline Gecode::MiniModel::LinExpr<Gecode::BoolVar>
00332 operator*(int a, const Gecode::BoolVar& x) {
00333 return Gecode::MiniModel::LinExpr<Gecode::BoolVar>(x,a);
00334 }
00335 inline Gecode::MiniModel::LinExpr<Gecode::BoolVar>
00336 operator*(const Gecode::BoolVar& x, int a) {
00337 return Gecode::MiniModel::LinExpr<Gecode::BoolVar>(x,a);
00338 }
00339 inline Gecode::MiniModel::LinExpr<Gecode::BoolVar>
00340 operator*(const Gecode::MiniModel::LinExpr<Gecode::BoolVar>& e, int a) {
00341 return Gecode::MiniModel::LinExpr<Gecode::BoolVar>(a,e);
00342 }
00343 inline Gecode::MiniModel::LinExpr<Gecode::BoolVar>
00344 operator*(int a, const Gecode::MiniModel::LinExpr<Gecode::BoolVar>& e) {
00345 return Gecode::MiniModel::LinExpr<Gecode::BoolVar>(a,e);
00346 }
00347
00348
00349 namespace Gecode {
00350
00351 forceinline IntVar
00352 post(Space*, const IntVar& x, IntConLevel, PropKind) {
00353 return x;
00354 }
00355
00356 inline IntVar
00357 post(Space* home, int n, IntConLevel, PropKind) {
00358 IntVar x(home, n, n);
00359 return x;
00360 }
00361
00362 template <class Var>
00363 inline IntVar
00364 post(Space* home, const MiniModel::LinExpr<Var>& e,
00365 IntConLevel icl, PropKind pk) {
00366 if (!home->failed())
00367 return e.post(home,icl,pk);
00368 IntVar x(home,Int::Limits::min,Int::Limits::max);
00369 return x;
00370 }
00371
00372 }
00373
00374