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 namespace Gecode {
00041
00050
00051 enum ViewSelStatus {
00052 VSS_BEST,
00053 VSS_BETTER,
00054 VSS_TIE,
00055 VSS_WORSE
00056 };
00057
00059 class Pos {
00060 public:
00062 const int pos;
00064 Pos(int p);
00065 };
00066
00075 template<class ViewSel>
00076 class ViewBrancher : public Brancher {
00077 protected:
00079 ViewArray<typename ViewSel::View> x;
00081 mutable int start;
00083 ViewSel viewsel;
00085 BranchFilter bf;
00087 Pos pos(Space& home);
00089 typename ViewSel::View view(const Pos& p) const;
00091 ViewBrancher(Space& home, bool share, ViewBrancher& b);
00093 ViewBrancher(Home home, ViewArray<typename ViewSel::View>& x,
00094 ViewSel& vi_s, BranchFilter bf0=NULL);
00095 public:
00097 virtual bool status(const Space& home) const;
00099 virtual size_t dispose(Space& home);
00100 };
00101
00102
00112 template<class ViewSel, class ValSel>
00113 class ViewValBrancher : public ViewBrancher<ViewSel> {
00114 protected:
00115 using ViewBrancher<ViewSel>::viewsel;
00116 using ViewBrancher<ViewSel>::x;
00118 ValSel valsel;
00120 ViewValBrancher(Space& home, bool share, ViewValBrancher& b);
00122 ViewValBrancher(Home home, ViewArray<typename ViewSel::View>& x,
00123 ViewSel& vi_s, ValSel& va_s, BranchFilter bf0);
00124 public:
00126 virtual const Choice* choice(Space& home);
00128 virtual const Choice* choice(const Space& home, Archive& e);
00130 virtual ExecStatus commit(Space& home, const Choice& c, unsigned int a);
00132 virtual Actor* copy(Space& home, bool share);
00134 virtual size_t dispose(Space& home);
00136 static void post(Home home, ViewArray<typename ViewSel::View>& x,
00137 ViewSel& vi_s, ValSel& va_s, BranchFilter bf=NULL);
00138
00139 };
00140
00141
00143 template<class ViewSel>
00144 class GECODE_VTABLE_EXPORT PosChoice : public Choice {
00145 private:
00147 const Pos _pos;
00149 const typename ViewSel::Choice _viewchoice;
00150 public:
00152 PosChoice(const Brancher& b, unsigned int a, const Pos& p,
00153 const typename ViewSel::Choice& viewc);
00155 const Pos& pos(void) const;
00157 const typename ViewSel::Choice& viewchoice(void) const;
00159 virtual size_t size(void) const;
00161 virtual void archive(Archive& e) const;
00162 };
00163
00165 template<class ViewSel, class ValSel>
00166 class GECODE_VTABLE_EXPORT PosValChoice : public PosChoice<ViewSel> {
00167 private:
00169 const typename ValSel::Choice _valchoice;
00171 const typename ValSel::Val _val;
00172 public:
00174 PosValChoice(const Brancher& b, const Pos& p,
00175 const typename ViewSel::Choice& viewc,
00176 const typename ValSel::Choice& valc,
00177 const typename ValSel::Val& n);
00179 const typename ValSel::Choice& valchoice(void) const;
00181 const typename ValSel::Val& val(void) const;
00183 virtual size_t size(void) const;
00185 virtual void archive(Archive& e) const;
00186 };
00188
00189
00190
00191
00192
00193
00194
00195
00196 forceinline
00197 Pos::Pos(int p) : pos(p) {}
00198
00199
00200
00201
00202
00203
00204 template<class ViewSel>
00205 forceinline
00206 PosChoice<ViewSel>::PosChoice(const Brancher& b, unsigned int a,
00207 const Pos& p,
00208 const typename ViewSel::Choice& viewc)
00209 : Choice(b,a), _pos(p), _viewchoice(viewc) {}
00210 template<class ViewSel>
00211 forceinline const Pos&
00212 PosChoice<ViewSel>::pos(void) const {
00213 return _pos;
00214 }
00215 template<class ViewSel>
00216 forceinline const typename ViewSel::Choice&
00217 PosChoice<ViewSel>::viewchoice(void) const {
00218 return _viewchoice;
00219 }
00220 template<class ViewSel>
00221 forceinline size_t
00222 PosChoice<ViewSel>::size(void) const {
00223 return sizeof(PosChoice<ViewSel>) + _viewchoice.size();
00224 }
00225 template<class ViewSel>
00226 forceinline void
00227 PosChoice<ViewSel>::archive(Archive& e) const {
00228 Choice::archive(e);
00229 e << _pos.pos;
00230 _viewchoice.archive(e);
00231 }
00232
00233
00234
00235
00236
00237 template<class ViewSel, class ValSel>
00238 forceinline
00239 PosValChoice<ViewSel,ValSel>
00240 ::PosValChoice(const Brancher& b, const Pos& p,
00241 const typename ViewSel::Choice& viewc,
00242 const typename ValSel::Choice& valc,
00243 const typename ValSel::Val& n)
00244 : PosChoice<ViewSel>(b,ValSel::alternatives,p,viewc),
00245 _valchoice(valc), _val(n) {}
00246
00247 template<class ViewSel, class ValSel>
00248 forceinline const typename ValSel::Choice&
00249 PosValChoice<ViewSel,ValSel>::valchoice(void) const {
00250 return _valchoice;
00251 }
00252
00253 template<class ViewSel, class ValSel>
00254 forceinline const typename ValSel::Val&
00255 PosValChoice<ViewSel,ValSel>::val(void) const {
00256 return _val;
00257 }
00258
00259 template<class ViewSel, class ValSel>
00260 forceinline size_t
00261 PosValChoice<ViewSel, ValSel>::size(void) const {
00262 return sizeof(PosValChoice<ViewSel,ValSel>) + _valchoice.size();
00263 }
00264
00265 template<class ViewSel, class ValSel>
00266 forceinline void
00267 PosValChoice<ViewSel, ValSel>::archive(Archive& e) const {
00268 PosChoice<ViewSel>::archive(e);
00269 _valchoice.archive(e);
00270 e << _val;
00271 }
00272
00273
00274
00275
00276
00277
00278 template<class ViewSel>
00279 forceinline
00280 ViewBrancher<ViewSel>::ViewBrancher(Home home,
00281 ViewArray<typename ViewSel::View>& x0,
00282 ViewSel& vi_s, BranchFilter bf0)
00283 : Brancher(home), x(x0), start(0), viewsel(vi_s), bf(bf0) {}
00284
00285
00286 template<class ViewSel>
00287 forceinline
00288 ViewBrancher<ViewSel>::ViewBrancher(Space& home, bool share,
00289 ViewBrancher& b)
00290 : Brancher(home,share,b), start(b.start), bf(b.bf) {
00291 x.update(home,share,b.x);
00292 viewsel.update(home,share,b.viewsel);
00293 }
00294
00295 template<class ViewSel>
00296 bool
00297 ViewBrancher<ViewSel>::status(const Space& home) const {
00298 if (bf == NULL) {
00299 for (int i=start; i < x.size(); i++)
00300 if (!x[i].assigned()) {
00301 start = i;
00302 return true;
00303 }
00304 } else {
00305 for (int i=start; i < x.size(); i++) {
00306 typename ViewSel::View::VarType y(x[i].varimp());
00307 if (!x[i].assigned() && bf(home,i,y)) {
00308 start = i;
00309 return true;
00310 }
00311 }
00312 }
00313 return false;
00314 }
00315
00316 template<class ViewSel>
00317 forceinline Pos
00318 ViewBrancher<ViewSel>::pos(Space& home) {
00319 assert(!x[start].assigned());
00320 int i = start;
00321 int b = i++;
00322 if (viewsel.init(home,x[b]) != VSS_BEST)
00323 for (; i < x.size(); i++)
00324 if (!x[i].assigned())
00325 switch (viewsel.select(home,x[i])) {
00326 case VSS_BETTER: b=i; break;
00327 case VSS_BEST: b=i; goto create;
00328 case VSS_TIE: case VSS_WORSE: break;
00329 default: GECODE_NEVER;
00330 }
00331 create:
00332 Pos p(b);
00333 return p;
00334 }
00335
00336 template<class ViewSel>
00337 forceinline typename ViewSel::View
00338 ViewBrancher<ViewSel>::view(const Pos& p) const {
00339 return x[p.pos];
00340 }
00341
00342 template<class ViewSel>
00343 forceinline size_t
00344 ViewBrancher<ViewSel>::dispose(Space& home) {
00345 viewsel.dispose(home);
00346 (void) Brancher::dispose(home);
00347 return sizeof(ViewBrancher<ViewSel>);
00348 }
00349
00350
00351
00352
00353
00354
00355
00356
00357 template<class ViewSel, class ValSel>
00358 forceinline
00359 ViewValBrancher<ViewSel,ValSel>::
00360 ViewValBrancher(Home home, ViewArray<typename ViewSel::View>& x,
00361 ViewSel& vi_s, ValSel& va_s, BranchFilter bf)
00362 : ViewBrancher<ViewSel>(home,x,vi_s,bf), valsel(va_s) {}
00363
00364 template<class ViewSel, class ValSel>
00365 void
00366 ViewValBrancher<ViewSel,ValSel>::
00367 post(Home home, ViewArray<typename ViewSel::View>& x,
00368 ViewSel& vi_s, ValSel& va_s, BranchFilter bf) {
00369 (void) new (home) ViewValBrancher<ViewSel,ValSel>(home,x,vi_s,va_s,bf);
00370 }
00371
00372 template<class ViewSel, class ValSel>
00373 forceinline
00374 ViewValBrancher<ViewSel,ValSel>::
00375 ViewValBrancher(Space& home, bool share, ViewValBrancher& b)
00376 : ViewBrancher<ViewSel>(home,share,b) {
00377 valsel.update(home,share,b.valsel);
00378 }
00379
00380 template<class ViewSel, class ValSel>
00381 Actor*
00382 ViewValBrancher<ViewSel,ValSel>::copy(Space& home, bool share) {
00383 return new (home)
00384 ViewValBrancher<ViewSel,ValSel>(home,share,*this);
00385 }
00386
00387 template<class ViewSel, class ValSel>
00388 const Choice*
00389 ViewValBrancher<ViewSel,ValSel>::choice(Space& home) {
00390 Pos p = ViewBrancher<ViewSel>::pos(home);
00391 typename ValSel::View v(ViewBrancher<ViewSel>::view(p).varimp());
00392 typename ValSel::Val val(valsel.val(home,v));
00393 return new PosValChoice<ViewSel,ValSel>
00394 (*this,p,
00395 viewsel.choice(home),valsel.choice(home),val);
00396 }
00397
00398 template<class ViewSel, class ValSel>
00399 const Choice*
00400 ViewValBrancher<ViewSel,ValSel>::choice(const Space& home, Archive& e) {
00401 int p; e >> p;
00402 typename ViewSel::Choice viewsc = viewsel.choice(home,e);
00403 typename ValSel::Choice valsc = valsel.choice(home,e);
00404 typename ValSel::Val val; e >> val;
00405 return new PosValChoice<ViewSel,ValSel>(*this,p,viewsc,valsc,val);
00406 }
00407
00408 template<class ViewSel, class ValSel>
00409 ExecStatus
00410 ViewValBrancher<ViewSel,ValSel>
00411 ::commit(Space& home, const Choice& c, unsigned int a) {
00412 const PosValChoice<ViewSel,ValSel>& pvc
00413 = static_cast<const PosValChoice<ViewSel,ValSel>&>(c);
00414 typename ValSel::View
00415 v(ViewBrancher<ViewSel>::view(pvc.pos()).varimp());
00416 viewsel.commit(home, pvc.viewchoice(), a);
00417 valsel.commit(home, pvc.valchoice(), a);
00418 return me_failed(valsel.tell(home,a,v,pvc.val())) ? ES_FAILED : ES_OK;
00419 }
00420
00421 template<class ViewSel, class ValSel>
00422 forceinline size_t
00423 ViewValBrancher<ViewSel,ValSel>::dispose(Space& home) {
00424 valsel.dispose(home);
00425 (void) ViewBrancher<ViewSel>::dispose(home);
00426 return sizeof(ViewValBrancher<ViewSel,ValSel>);
00427 }
00428
00429 }
00430
00431