select-values.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2008 00008 * 00009 * Last modified: 00010 * $Date: 2010-09-01 12:02:08 +0200 (Wed, 01 Sep 2010) $ by $Author: schulte $ 00011 * $Revision: 11371 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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, BranchFilter bf) 00128 : ViewBrancher<ViewSel>(home,x,vi_s,bf) {} 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 BranchFilter bf) { 00135 (void) new (home) ViewValuesBrancher<ViewSel,View>(home,x,vi_s,bf); 00136 } 00137 00138 template<class ViewSel, class View> 00139 forceinline 00140 ViewValuesBrancher<ViewSel,View>:: 00141 ViewValuesBrancher(Space& home, bool share, ViewValuesBrancher& b) 00142 : ViewBrancher<ViewSel>(home,share,b) {} 00143 00144 template<class ViewSel, class View> 00145 Actor* 00146 ViewValuesBrancher<ViewSel,View>::copy(Space& home, bool share) { 00147 return new (home) 00148 ViewValuesBrancher<ViewSel,View>(home,share,*this); 00149 } 00150 00151 template<class ViewSel, class View> 00152 const Choice* 00153 ViewValuesBrancher<ViewSel,View>::choice(Space& home) { 00154 Pos p = ViewBrancher<ViewSel>::pos(home); 00155 View v(ViewBrancher<ViewSel>::view(p).varimp()); 00156 return new PosValuesChoice<ViewSel,View> 00157 (*this,p,viewsel.choice(home),v); 00158 } 00159 00160 template<class ViewSel, class View> 00161 ExecStatus 00162 ViewValuesBrancher<ViewSel,View> 00163 ::commit(Space& home, const Choice& c, unsigned int a) { 00164 const PosValuesChoice<ViewSel,View>& pvc 00165 = static_cast<const PosValuesChoice<ViewSel,View>&>(c); 00166 View v(ViewBrancher<ViewSel>::view(pvc.pos()).varimp()); 00167 viewsel.commit(home, pvc.viewchoice(), a); 00168 return me_failed(v.eq(home,pvc.val(a))) ? ES_FAILED : ES_OK; 00169 } 00170 00171 }}} 00172 00173 // STATISTICS: int-branch