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
00047
00048 class Pos {
00049 public:
00051 const int pos;
00053 Pos(int p);
00054 };
00055
00057 class GECODE_VTABLE_EXPORT PosChoice : public Choice {
00058 private:
00060 const Pos _pos;
00061 public:
00063 PosChoice(const Brancher& b, unsigned int a, const Pos& p);
00065 const Pos& pos(void) const;
00067 virtual size_t size(void) const;
00069 virtual void archive(Archive& e) const;
00070 };
00071
00078 template<class View, class Filter, int n>
00079 class ViewBrancher : public Brancher {
00080 protected:
00082 typedef typename View::VarType Var;
00084 ViewArray<View> x;
00086 mutable int start;
00088 ViewSel<View>* vs[n];
00090 Filter f;
00092 Pos pos(Space& home);
00094 View view(const Pos& p) const;
00096 ViewBrancher(Space& home, bool shared, ViewBrancher<View,Filter,n>& b);
00098 ViewBrancher(Home home, ViewArray<View>& x, ViewSel<View>* vs[n],
00099 BranchFilter<Var> bf);
00100 public:
00102 virtual bool status(const Space& home) const;
00104 virtual size_t dispose(Space& home);
00105 };
00106
00108
00109
00110
00111
00112
00113
00114 forceinline
00115 Pos::Pos(int p) : pos(p) {}
00116
00117
00118
00119
00120
00121 forceinline
00122 PosChoice::PosChoice(const Brancher& b, unsigned int a, const Pos& p)
00123 : Choice(b,a), _pos(p) {}
00124 forceinline const Pos&
00125 PosChoice::pos(void) const {
00126 return _pos;
00127 }
00128 forceinline size_t
00129 PosChoice::size(void) const {
00130 return sizeof(PosChoice);
00131 }
00132 forceinline void
00133 PosChoice::archive(Archive& e) const {
00134 Choice::archive(e);
00135 e << _pos.pos;
00136 }
00137
00138 template<class View, class Filter, int n>
00139 forceinline
00140 ViewBrancher<View,Filter,n>::ViewBrancher(Home home, ViewArray<View>& x0,
00141 ViewSel<View>* vs0[n],
00142 BranchFilter<Var> bf)
00143 : Brancher(home), x(x0), start(0), f(bf) {
00144 for (int i=0; i<n; i++)
00145 vs[i] = vs0[i];
00146 for (int i=0; i<n; i++)
00147 if (f.notice() || vs[i]->notice()) {
00148 home.notice(*this,AP_DISPOSE,true);
00149 break;
00150 }
00151 }
00152
00153 template<class View, class Filter, int n>
00154 forceinline
00155 ViewBrancher<View,Filter,n>::ViewBrancher(Space& home, bool shared,
00156 ViewBrancher<View,Filter,n>& vb)
00157 : Brancher(home,shared,vb), start(vb.start),
00158 f(home,shared,vb.f) {
00159 x.update(home,shared,vb.x);
00160 for (int i=0; i<n; i++)
00161 vs[i] = vb.vs[i]->copy(home,shared);
00162 }
00163
00164 template<class View, class Filter, int n>
00165 bool
00166 ViewBrancher<View,Filter,n>::status(const Space& home) const {
00167 for (int i=start; i < x.size(); i++)
00168 if (!x[i].assigned() && f(home,x[i],i)) {
00169 start = i;
00170 return true;
00171 }
00172 return false;
00173 }
00174
00175 template<class View, class Filter, int n>
00176 inline Pos
00177 ViewBrancher<View,Filter,n>::pos(Space& home) {
00178 assert(!x[start].assigned());
00179 int s;
00180 if (f) {
00181 if (n == 1) {
00182 s = vs[0]->select(home,x,start,f);
00183 } else {
00184 Region r(home);
00185 int* ties = r.alloc<int>(x.size()-start+1);
00186 int n_ties;
00187 vs[0]->ties(home,x,start,ties,n_ties,f);
00188 for (int i=1; (i < n-1) && (n_ties > 1); i++)
00189 vs[i]->brk(home,x,ties,n_ties);
00190 if (n_ties > 1)
00191 s = vs[n-1]->select(home,x,ties,n_ties);
00192 else
00193 s = ties[0];
00194 }
00195 } else {
00196 if (n == 1) {
00197 s = vs[0]->select(home,x,start);
00198 } else {
00199 Region r(home);
00200 int* ties = r.alloc<int>(x.size()-start+1);
00201 int n_ties;
00202 vs[0]->ties(home,x,start,ties,n_ties);
00203 for (int i=1; (i < n-1) && (n_ties > 1); i++)
00204 vs[i]->brk(home,x,ties,n_ties);
00205 if (n_ties > 1)
00206 s = vs[n-1]->select(home,x,ties,n_ties);
00207 else
00208 s = ties[0];
00209 }
00210 }
00211 Pos p(s);
00212 return p;
00213 }
00214
00215 template<class View, class Filter, int n>
00216 forceinline View
00217 ViewBrancher<View,Filter,n>::view(const Pos& p) const {
00218 return x[p.pos];
00219 }
00220
00221 template<class View, class Filter, int n>
00222 forceinline size_t
00223 ViewBrancher<View,Filter,n>::dispose(Space& home) {
00224 for (int i=0; i<n; i++)
00225 if (f.notice() || vs[i]->notice()) {
00226 home.ignore(*this,AP_DISPOSE,true);
00227 break;
00228 }
00229 for (int i=0; i<n; i++)
00230 vs[i]->dispose(home);
00231 (void) Brancher::dispose(home);
00232 return sizeof(ViewBrancher<View,Filter,n>);
00233 }
00234
00235 }
00236
00237