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 ExecStatus commit(Space& home, const Choice& c, unsigned int a);
00130 virtual Actor* copy(Space& home, bool share);
00132 virtual size_t dispose(Space& home);
00134 static void post(Home home, ViewArray<typename ViewSel::View>& x,
00135 ViewSel& vi_s, ValSel& va_s, BranchFilter bf=NULL);
00136
00137 };
00138
00139
00141 template<class ViewSel>
00142 class GECODE_VTABLE_EXPORT PosChoice : public Choice {
00143 private:
00145 const Pos _pos;
00147 const typename ViewSel::Choice _viewchoice;
00148 public:
00150 PosChoice(const Brancher& b, unsigned int a, const Pos& p,
00151 const typename ViewSel::Choice& viewc);
00153 const Pos& pos(void) const;
00155 const typename ViewSel::Choice& viewchoice(void) const;
00157 virtual size_t size(void) const;
00158 };
00159
00161 template<class ViewSel, class ValSel>
00162 class GECODE_VTABLE_EXPORT PosValChoice : public PosChoice<ViewSel> {
00163 private:
00165 const typename ValSel::Choice _valchoice;
00167 const typename ValSel::Val _val;
00168 public:
00170 PosValChoice(const Brancher& b, const Pos& p,
00171 const typename ViewSel::Choice& viewc,
00172 const typename ValSel::Choice& valc,
00173 const typename ValSel::Val& n);
00175 const typename ValSel::Choice& valchoice(void) const;
00177 const typename ValSel::Val& val(void) const;
00179 virtual size_t size(void) const;
00180 };
00182
00183
00184
00185
00186
00187
00188
00189
00190 forceinline
00191 Pos::Pos(int p) : pos(p) {}
00192
00193
00194
00195
00196
00197
00198 template<class ViewSel>
00199 forceinline
00200 PosChoice<ViewSel>::PosChoice(const Brancher& b, unsigned int a,
00201 const Pos& p,
00202 const typename ViewSel::Choice& viewc)
00203 : Choice(b,a), _pos(p), _viewchoice(viewc) {}
00204 template<class ViewSel>
00205 forceinline const Pos&
00206 PosChoice<ViewSel>::pos(void) const {
00207 return _pos;
00208 }
00209 template<class ViewSel>
00210 forceinline const typename ViewSel::Choice&
00211 PosChoice<ViewSel>::viewchoice(void) const {
00212 return _viewchoice;
00213 }
00214 template<class ViewSel>
00215 forceinline size_t
00216 PosChoice<ViewSel>::size(void) const {
00217 return sizeof(PosChoice<ViewSel>) + _viewchoice.size();
00218 }
00219
00220
00221
00222
00223
00224
00225 template<class ViewSel, class ValSel>
00226 forceinline
00227 PosValChoice<ViewSel,ValSel>
00228 ::PosValChoice(const Brancher& b, const Pos& p,
00229 const typename ViewSel::Choice& viewc,
00230 const typename ValSel::Choice& valc,
00231 const typename ValSel::Val& n)
00232 : PosChoice<ViewSel>(b,ValSel::alternatives,p,viewc),
00233 _valchoice(valc), _val(n) {}
00234
00235 template<class ViewSel, class ValSel>
00236 forceinline const typename ValSel::Choice&
00237 PosValChoice<ViewSel,ValSel>::valchoice(void) const {
00238 return _valchoice;
00239 }
00240
00241 template<class ViewSel, class ValSel>
00242 forceinline const typename ValSel::Val&
00243 PosValChoice<ViewSel,ValSel>::val(void) const {
00244 return _val;
00245 }
00246
00247 template<class ViewSel, class ValSel>
00248 forceinline size_t
00249 PosValChoice<ViewSel, ValSel>::size(void) const {
00250 return sizeof(PosValChoice<ViewSel,ValSel>) + _valchoice.size();
00251 }
00252
00253
00254
00255
00256
00257
00258
00259 template<class ViewSel>
00260 forceinline
00261 ViewBrancher<ViewSel>::ViewBrancher(Home home,
00262 ViewArray<typename ViewSel::View>& x0,
00263 ViewSel& vi_s, BranchFilter bf0)
00264 : Brancher(home), x(x0), start(0), viewsel(vi_s), bf(bf0) {}
00265
00266
00267 template<class ViewSel>
00268 forceinline
00269 ViewBrancher<ViewSel>::ViewBrancher(Space& home, bool share,
00270 ViewBrancher& b)
00271 : Brancher(home,share,b), start(b.start), bf(b.bf) {
00272 x.update(home,share,b.x);
00273 viewsel.update(home,share,b.viewsel);
00274 }
00275
00276 template<class ViewSel>
00277 bool
00278 ViewBrancher<ViewSel>::status(const Space& home) const {
00279 if (bf == NULL) {
00280 for (int i=start; i < x.size(); i++)
00281 if (!x[i].assigned()) {
00282 start = i;
00283 return true;
00284 }
00285 } else {
00286 for (int i=start; i < x.size(); i++) {
00287 typename ViewSel::View::VarType y(x[i].varimp());
00288 if (!x[i].assigned() && bf(home,i,y)) {
00289 start = i;
00290 return true;
00291 }
00292 }
00293 }
00294 return false;
00295 }
00296
00297 template<class ViewSel>
00298 forceinline Pos
00299 ViewBrancher<ViewSel>::pos(Space& home) {
00300 assert(!x[start].assigned());
00301 int i = start;
00302 int b = i++;
00303 if (viewsel.init(home,x[b]) != VSS_BEST)
00304 for (; i < x.size(); i++)
00305 if (!x[i].assigned())
00306 switch (viewsel.select(home,x[i])) {
00307 case VSS_BETTER: b=i; break;
00308 case VSS_BEST: b=i; goto create;
00309 case VSS_TIE: case VSS_WORSE: break;
00310 default: GECODE_NEVER;
00311 }
00312 create:
00313 Pos p(b);
00314 return p;
00315 }
00316
00317 template<class ViewSel>
00318 forceinline typename ViewSel::View
00319 ViewBrancher<ViewSel>::view(const Pos& p) const {
00320 return x[p.pos];
00321 }
00322
00323 template<class ViewSel>
00324 forceinline size_t
00325 ViewBrancher<ViewSel>::dispose(Space& home) {
00326 viewsel.dispose(home);
00327 (void) Brancher::dispose(home);
00328 return sizeof(ViewBrancher<ViewSel>);
00329 }
00330
00331
00332
00333
00334
00335
00336
00337
00338 template<class ViewSel, class ValSel>
00339 forceinline
00340 ViewValBrancher<ViewSel,ValSel>::
00341 ViewValBrancher(Home home, ViewArray<typename ViewSel::View>& x,
00342 ViewSel& vi_s, ValSel& va_s, BranchFilter bf)
00343 : ViewBrancher<ViewSel>(home,x,vi_s,bf), valsel(va_s) {}
00344
00345 template<class ViewSel, class ValSel>
00346 void
00347 ViewValBrancher<ViewSel,ValSel>::
00348 post(Home home, ViewArray<typename ViewSel::View>& x,
00349 ViewSel& vi_s, ValSel& va_s, BranchFilter bf) {
00350 (void) new (home) ViewValBrancher<ViewSel,ValSel>(home,x,vi_s,va_s,bf);
00351 }
00352
00353 template<class ViewSel, class ValSel>
00354 forceinline
00355 ViewValBrancher<ViewSel,ValSel>::
00356 ViewValBrancher(Space& home, bool share, ViewValBrancher& b)
00357 : ViewBrancher<ViewSel>(home,share,b) {
00358 valsel.update(home,share,b.valsel);
00359 }
00360
00361 template<class ViewSel, class ValSel>
00362 Actor*
00363 ViewValBrancher<ViewSel,ValSel>::copy(Space& home, bool share) {
00364 return new (home)
00365 ViewValBrancher<ViewSel,ValSel>(home,share,*this);
00366 }
00367
00368 template<class ViewSel, class ValSel>
00369 const Choice*
00370 ViewValBrancher<ViewSel,ValSel>::choice(Space& home) {
00371 Pos p = ViewBrancher<ViewSel>::pos(home);
00372 typename ValSel::View v(ViewBrancher<ViewSel>::view(p).varimp());
00373 typename ValSel::Val val(valsel.val(home,v));
00374 return new PosValChoice<ViewSel,ValSel>
00375 (*this,p,
00376 viewsel.choice(home),valsel.choice(home),val);
00377 }
00378
00379 template<class ViewSel, class ValSel>
00380 ExecStatus
00381 ViewValBrancher<ViewSel,ValSel>
00382 ::commit(Space& home, const Choice& c, unsigned int a) {
00383 const PosValChoice<ViewSel,ValSel>& pvc
00384 = static_cast<const PosValChoice<ViewSel,ValSel>&>(c);
00385 typename ValSel::View
00386 v(ViewBrancher<ViewSel>::view(pvc.pos()).varimp());
00387 viewsel.commit(home, pvc.viewchoice(), a);
00388 valsel.commit(home, pvc.valchoice(), a);
00389 return me_failed(valsel.tell(home,a,v,pvc.val())) ? ES_FAILED : ES_OK;
00390 }
00391
00392 template<class ViewSel, class ValSel>
00393 forceinline size_t
00394 ViewValBrancher<ViewSel,ValSel>::dispose(Space& home) {
00395 valsel.dispose(home);
00396 (void) ViewBrancher<ViewSel>::dispose(home);
00397 return sizeof(ViewValBrancher<ViewSel,ValSel>);
00398 }
00399
00400 }
00401
00402