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 Int { namespace Branch {
00039
00045 template<class ViewSel, class View>
00046 class PosValuesChoice : public PosChoice<ViewSel> {
00047 private:
00049 class PosMin {
00050 public:
00052 unsigned int pos;
00054 int min;
00055 };
00057 unsigned int n;
00059 PosMin* pm;
00060 public:
00062 PosValuesChoice(const Brancher& b, const Pos& p,
00063 const typename ViewSel::Choice& viewc, View x);
00065 int val(unsigned int a) const;
00067 virtual size_t size(void) const;
00069 virtual ~PosValuesChoice(void);
00070 };
00071
00072
00073 template<class ViewSel, class View>
00074 forceinline
00075 PosValuesChoice<ViewSel,View>::
00076 PosValuesChoice(const Brancher& b, const Pos& p,
00077 const typename ViewSel::Choice& viewc, View x)
00078 : PosChoice<ViewSel>(b,x.size(),p,viewc), n(0) {
00079 for (ViewRanges<View> r(x); r(); ++r)
00080 n++;
00081 pm = heap.alloc<PosMin>(n+1);
00082 unsigned int w=0;
00083 int i=0;
00084 for (ViewRanges<View> r(x); r(); ++r) {
00085 pm[i].min = r.min();
00086 pm[i].pos = w;
00087 w += r.width(); i++;
00088 }
00089 pm[i].pos = w;
00090 }
00091
00092 template<class ViewSel, class View>
00093 forceinline int
00094 PosValuesChoice<ViewSel,View>::val(unsigned int a) const {
00095 PosMin* l = &pm[0];
00096 PosMin* r = &pm[n-1];
00097 while (true) {
00098 PosMin* m = l + (r-l)/2;
00099 if (a < m->pos) {
00100 r=m-1;
00101 } else if (a >= (m+1)->pos) {
00102 l=m+1;
00103 } else {
00104 return m->min + static_cast<int>(a - m->pos);
00105 }
00106 }
00107 GECODE_NEVER;
00108 return 0;
00109 }
00110
00111 template<class ViewSel, class View>
00112 size_t
00113 PosValuesChoice<ViewSel,View>::size(void) const {
00114 return sizeof(PosValuesChoice<ViewSel,View>)+(n+1)*sizeof(PosMin);
00115 }
00116
00117 template<class ViewSel, class View>
00118 PosValuesChoice<ViewSel,View>::~PosValuesChoice(void) {
00119 heap.free<PosMin>(pm,n+1);
00120 }
00121
00122
00123 template<class ViewSel, class View>
00124 forceinline
00125 ViewValuesBrancher<ViewSel,View>::
00126 ViewValuesBrancher(Home home, ViewArray<typename ViewSel::View>& x,
00127 ViewSel& vi_s)
00128 : ViewBrancher<ViewSel>(home,x,vi_s) {}
00129
00130 template<class ViewSel, class View>
00131 void
00132 ViewValuesBrancher<ViewSel,View>::
00133 post(Home home, ViewArray<typename ViewSel::View>& x, ViewSel& vi_s) {
00134 (void) new (home) ViewValuesBrancher<ViewSel,View>(home,x,vi_s);
00135 }
00136
00137 template<class ViewSel, class View>
00138 forceinline
00139 ViewValuesBrancher<ViewSel,View>::
00140 ViewValuesBrancher(Space& home, bool share, ViewValuesBrancher& b)
00141 : ViewBrancher<ViewSel>(home,share,b) {}
00142
00143 template<class ViewSel, class View>
00144 Actor*
00145 ViewValuesBrancher<ViewSel,View>::copy(Space& home, bool share) {
00146 return new (home)
00147 ViewValuesBrancher<ViewSel,View>(home,share,*this);
00148 }
00149
00150 template<class ViewSel, class View>
00151 const Choice*
00152 ViewValuesBrancher<ViewSel,View>::choice(Space& home) {
00153 Pos p = ViewBrancher<ViewSel>::pos(home);
00154 View v(ViewBrancher<ViewSel>::view(p).var());
00155 return new PosValuesChoice<ViewSel,View>
00156 (*this,p,viewsel.choice(home),v);
00157 }
00158
00159 template<class ViewSel, class View>
00160 ExecStatus
00161 ViewValuesBrancher<ViewSel,View>
00162 ::commit(Space& home, const Choice& c, unsigned int a) {
00163 const PosValuesChoice<ViewSel,View>& pvc
00164 = static_cast<const PosValuesChoice<ViewSel,View>&>(c);
00165 View v(ViewBrancher<ViewSel>::view(pvc.pos()).var());
00166 viewsel.commit(home, pvc.viewchoice(), a);
00167 return me_failed(v.eq(home,pvc.val(a))) ? ES_FAILED : ES_OK;
00168 }
00169
00170 }}}
00171
00172