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 {
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 heap.ralloc(size);
00053 }
00054
00055 template<class Var>
00056 forceinline void
00057 LinExpr<Var>::Node::operator delete(void* p, size_t) {
00058 heap.rfree(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(Home home, IntRelType irt, IntConLevel icl) const {
00199 Region r(home);
00200 Int::Linear::Term<typename VarViewTraits<Var>::View>* ts =
00201 r.alloc<Int::Linear::Term<typename VarViewTraits<Var>::View> >(n->n);
00202 int c_o = 0;
00203 int i = n->fill(ts,0,1,0,c_o);
00204 Int::Linear::post(home, ts, i, irt, -c_o, icl);
00205 }
00206
00207 template<class Var>
00208 inline void
00209 LinExpr<Var>::post(Home home, IntRelType irt, const BoolVar& b,
00210 IntConLevel icl) const {
00211 Region r(home);
00212 Int::Linear::Term<typename VarViewTraits<Var>::View>* ts =
00213 r.alloc<Int::Linear::Term<typename VarViewTraits<Var>::View> >(n->n);
00214 int c_o = 0;
00215 int i = n->fill(ts,0,1,0,c_o);
00216 Int::Linear::post(home, ts, i, irt, -c_o, b, icl);
00217 }
00218
00219 template<>
00220 inline IntVar
00221 LinExpr<IntVar>::post(Home home, IntConLevel icl) const {
00222 Region r(home);
00223 Int::Linear::Term<Int::IntView>* ts =
00224 r.alloc<Int::Linear::Term<Int::IntView> >(n->n+1);
00225 int c_o = 0;
00226 int i = n->fill(ts,0,1,0,c_o);
00227 int min, max;
00228 Int::Linear::estimate(&ts[0],i,c_o,min,max);
00229 IntVar x(home, min, max);
00230 ts[i].x = x; ts[i].a = -1;
00231 Int::Linear::post(home, ts, i+1, IRT_EQ, -c_o, icl);
00232 return x;
00233 }
00234
00235 template<>
00236 inline IntVar
00237 LinExpr<BoolVar>::post(Home home, IntConLevel icl) const {
00238 Region r(home);
00239 Int::Linear::Term<Int::BoolView>* ts =
00240 r.alloc<Int::Linear::Term<Int::BoolView> >(n->n);
00241 int c_o = 0;
00242 int i = n->fill(ts,0,1,0,c_o);
00243 int min, max;
00244 Int::Linear::estimate(&ts[0],i,c_o,min,max);
00245 IntVar x(home, min, max);
00246 Int::Linear::post(home, ts, i, IRT_EQ, x, -c_o, icl);
00247 return x;
00248 }
00249
00250 inline LinExpr<IntVar>
00251 operator +(int c, const IntVar& x) {
00252 return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_ADD,c);
00253 }
00254 inline LinExpr<IntVar>
00255 operator +(int c, const LinExpr<IntVar>& e) {
00256 return LinExpr<IntVar>(e,LinExpr<IntVar>::NT_ADD,c);
00257 }
00258 inline LinExpr<IntVar>
00259 operator +(const IntVar& x, int c) {
00260 return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_ADD,c);
00261 }
00262 inline LinExpr<IntVar>
00263 operator +(const LinExpr<IntVar>& e, int c) {
00264 return LinExpr<IntVar>(e,LinExpr<IntVar>::NT_ADD,c);
00265 }
00266 inline LinExpr<IntVar>
00267 operator +(const IntVar& x, const IntVar& y) {
00268 return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_ADD,y);
00269 }
00270 inline LinExpr<IntVar>
00271 operator +(const IntVar& x, const LinExpr<IntVar>& e) {
00272 return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_ADD,e);
00273 }
00274 inline LinExpr<IntVar>
00275 operator +(const LinExpr<IntVar>& e, const IntVar& x) {
00276 return LinExpr<IntVar>(e,LinExpr<IntVar>::NT_ADD,x);
00277 }
00278 inline LinExpr<IntVar>
00279 operator +(const LinExpr<IntVar>& e1, const LinExpr<IntVar>& e2) {
00280 return LinExpr<IntVar>(e1,LinExpr<IntVar>::NT_ADD,e2);
00281 }
00282
00283 inline LinExpr<IntVar>
00284 operator -(int c, const IntVar& x) {
00285 return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_SUB,c);
00286 }
00287 inline LinExpr<IntVar>
00288 operator -(int c, const LinExpr<IntVar>& e) {
00289 return LinExpr<IntVar>(e,LinExpr<IntVar>::NT_SUB,c);
00290 }
00291 inline LinExpr<IntVar>
00292 operator -(const IntVar& x, int c) {
00293 return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_ADD,-c);
00294 }
00295 inline LinExpr<IntVar>
00296 operator -(const LinExpr<IntVar>& e, int c) {
00297 return LinExpr<IntVar>(e,LinExpr<IntVar>::NT_ADD,-c);
00298 }
00299 inline LinExpr<IntVar>
00300 operator -(const IntVar& x, const IntVar& y) {
00301 return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_SUB,y);
00302 }
00303 inline LinExpr<IntVar>
00304 operator -(const IntVar& x, const LinExpr<IntVar>& e) {
00305 return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_SUB,e);
00306 }
00307 inline LinExpr<IntVar>
00308 operator -(const LinExpr<IntVar>& e, const IntVar& x) {
00309 return LinExpr<IntVar>(e,LinExpr<IntVar>::NT_SUB,x);
00310 }
00311 inline LinExpr<IntVar>
00312 operator -(const LinExpr<IntVar>& e1, const LinExpr<IntVar>& e2) {
00313 return LinExpr<IntVar>(e1,LinExpr<IntVar>::NT_SUB,e2);
00314 }
00315 inline LinExpr<IntVar>
00316 operator -(const IntVar& x) {
00317 return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_SUB,0);
00318 }
00319 inline LinExpr<IntVar>
00320 operator -(const LinExpr<IntVar>& e) {
00321 return LinExpr<IntVar>(e,LinExpr<IntVar>::NT_SUB,0);
00322 }
00323
00324 inline LinExpr<IntVar>
00325 operator *(int a, const IntVar& x) {
00326 return LinExpr<IntVar>(x,a);
00327 }
00328 inline LinExpr<IntVar>
00329 operator *(const IntVar& x, int a) {
00330 return LinExpr<IntVar>(x,a);
00331 }
00332 inline LinExpr<IntVar>
00333 operator *(const LinExpr<IntVar>& e, int a) {
00334 return LinExpr<IntVar>(a,e);
00335 }
00336 inline LinExpr<IntVar>
00337 operator *(int a, const LinExpr<IntVar>& e) {
00338 return LinExpr<IntVar>(a,e);
00339 }
00340
00341
00342 inline LinExpr<BoolVar>
00343 operator +(int c, const BoolVar& x) {
00344 return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_ADD,c);
00345 }
00346 inline LinExpr<BoolVar>
00347 operator +(int c, const LinExpr<BoolVar>& e) {
00348 return LinExpr<BoolVar>(e,LinExpr<BoolVar>::NT_ADD,c);
00349 }
00350 inline LinExpr<BoolVar>
00351 operator +(const BoolVar& x, int c) {
00352 return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_ADD,c);
00353 }
00354 inline LinExpr<BoolVar>
00355 operator +(const LinExpr<BoolVar>& e, int c) {
00356 return LinExpr<BoolVar>(e,LinExpr<BoolVar>::NT_ADD,c);
00357 }
00358 inline LinExpr<BoolVar>
00359 operator +(const BoolVar& x, const BoolVar& y) {
00360 return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_ADD,y);
00361 }
00362 inline LinExpr<BoolVar>
00363 operator +(const BoolVar& x, const LinExpr<BoolVar>& e) {
00364 return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_ADD,e);
00365 }
00366 inline LinExpr<BoolVar>
00367 operator +(const LinExpr<BoolVar>& e, const BoolVar& x) {
00368 return LinExpr<BoolVar>(e,LinExpr<BoolVar>::NT_ADD,x);
00369 }
00370 inline LinExpr<BoolVar>
00371 operator +(const LinExpr<BoolVar>& e1, const LinExpr<BoolVar>& e2) {
00372 return LinExpr<BoolVar>(e1,LinExpr<BoolVar>::NT_ADD,e2);
00373 }
00374
00375 inline LinExpr<BoolVar>
00376 operator -(int c, const BoolVar& x) {
00377 return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_SUB,c);
00378 }
00379 inline LinExpr<BoolVar>
00380 operator -(int c, const LinExpr<BoolVar>& e) {
00381 return LinExpr<BoolVar>(e,LinExpr<BoolVar>::NT_SUB,c);
00382 }
00383 inline LinExpr<BoolVar>
00384 operator -(const BoolVar& x, int c) {
00385 return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_ADD,-c);
00386 }
00387 inline LinExpr<BoolVar>
00388 operator -(const LinExpr<BoolVar>& e, int c) {
00389 return LinExpr<BoolVar>(e,LinExpr<BoolVar>::NT_ADD,-c);
00390 }
00391 inline LinExpr<BoolVar>
00392 operator -(const BoolVar& x, const BoolVar& y) {
00393 return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_SUB,y);
00394 }
00395 inline LinExpr<BoolVar>
00396 operator -(const BoolVar& x, const LinExpr<BoolVar>& e) {
00397 return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_SUB,e);
00398 }
00399 inline LinExpr<BoolVar>
00400 operator -(const LinExpr<BoolVar>& e, const BoolVar& x) {
00401 return LinExpr<BoolVar>(e,LinExpr<BoolVar>::NT_SUB,x);
00402 }
00403 inline LinExpr<BoolVar>
00404 operator -(const LinExpr<BoolVar>& e1, const LinExpr<BoolVar>& e2) {
00405 return LinExpr<BoolVar>(e1,LinExpr<BoolVar>::NT_SUB,e2);
00406 }
00407 inline LinExpr<BoolVar>
00408 operator -(const BoolVar& x) {
00409 return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_SUB,0);
00410 }
00411 inline LinExpr<BoolVar>
00412 operator -(const LinExpr<BoolVar>& e) {
00413 return LinExpr<BoolVar>(e,LinExpr<BoolVar>::NT_SUB,0);
00414 }
00415
00416 inline LinExpr<BoolVar>
00417 operator *(int a, const BoolVar& x) {
00418 return LinExpr<BoolVar>(x,a);
00419 }
00420 inline LinExpr<BoolVar>
00421 operator *(const BoolVar& x, int a) {
00422 return LinExpr<BoolVar>(x,a);
00423 }
00424 inline LinExpr<BoolVar>
00425 operator *(const LinExpr<BoolVar>& e, int a) {
00426 return LinExpr<BoolVar>(a,e);
00427 }
00428 inline LinExpr<BoolVar>
00429 operator *(int a, const LinExpr<BoolVar>& e) {
00430 return LinExpr<BoolVar>(a,e);
00431 }
00432
00433
00434 forceinline IntVar
00435 post(Home, const IntVar& x, IntConLevel) {
00436 return x;
00437 }
00438
00439 inline IntVar
00440 post(Home home, int n, IntConLevel) {
00441 IntVar x(home, n, n);
00442 return x;
00443 }
00444
00445 template<class Var>
00446 inline IntVar
00447 post(Home home, const LinExpr<Var>& e, IntConLevel icl) {
00448 if (!home.failed())
00449 return e.post(home,icl);
00450 IntVar x(home,Int::Limits::min,Int::Limits::max);
00451 return x;
00452 }
00453
00454 }
00455
00456