branch.cpp

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, 2012
00008  *
00009  *  Last modified:
00010  *     $Date: 2013-03-05 20:51:24 +0100 (Tue, 05 Mar 2013) $ by $Author: schulte $
00011  *     $Revision: 13438 $
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 #include <gecode/int/branch.hh>
00039 
00040 namespace Gecode {
00041 
00042   BrancherHandle
00043   branch(Home home, const IntVarArgs& x,
00044          IntVarBranch vars, IntValBranch vals, IntBranchFilter bf) {
00045     using namespace Int;
00046     if (home.failed()) return BrancherHandle();
00047     vars.expand(home,x);
00048     ViewArray<IntView> xv(home,x);
00049     ViewSel<IntView>* vs[1] = { 
00050       Branch::viewselint(home,vars) 
00051     };
00052     switch (vals.select()) {
00053     case IntValBranch::SEL_VALUES_MIN:
00054       return Branch::ViewValuesBrancher<1,true>::post(home,xv,vs,bf);
00055       break;
00056     case IntValBranch::SEL_VALUES_MAX:
00057       return Branch::ViewValuesBrancher<1,false>::post(home,xv,vs,bf);
00058       break;
00059     default:
00060       return ViewValBrancher<IntView,1,int,2>::post
00061         (home,xv,vs,Branch::valselcommitint(home,x.size(),vals),bf);
00062     }
00063   }
00064 
00065   BrancherHandle
00066   branch(Home home, const IntVarArgs& x,
00067          TieBreak<IntVarBranch> vars, IntValBranch vals, IntBranchFilter bf) {
00068     using namespace Int;
00069     if (home.failed()) return BrancherHandle();
00070     vars.a.expand(home,x);
00071     if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
00072         (vars.a.select() == IntVarBranch::SEL_RND))
00073       vars.b = INT_VAR_NONE();
00074     vars.b.expand(home,x);
00075     if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
00076         (vars.b.select() == IntVarBranch::SEL_RND))
00077       vars.c = INT_VAR_NONE();
00078     vars.c.expand(home,x);
00079     if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
00080         (vars.c.select() == IntVarBranch::SEL_RND))
00081       vars.d = INT_VAR_NONE();
00082     vars.d.expand(home,x);
00083     if (vars.b.select() == IntVarBranch::SEL_NONE) {
00084       return branch(home,x,vars.a,vals,bf);
00085     } else {
00086       ViewArray<IntView> xv(home,x);
00087       if (vars.c.select() == IntVarBranch::SEL_NONE) {
00088         ViewSel<IntView>* vs[2] = { 
00089           Branch::viewselint(home,vars.a),Branch::viewselint(home,vars.b)
00090         };
00091         switch (vals.select()) {
00092         case IntValBranch::SEL_VALUES_MIN:
00093           return Branch::ViewValuesBrancher<2,true>::post(home,xv,vs,bf);
00094           break;
00095         case IntValBranch::SEL_VALUES_MAX:
00096           return Branch::ViewValuesBrancher<2,false>::post(home,xv,vs,bf);
00097           break;
00098         default:
00099           return ViewValBrancher<IntView,2,int,2>
00100             ::post(home,xv,vs,Branch::valselcommitint(home,x.size(),vals),bf);
00101         }
00102       } else if (vars.d.select() == IntVarBranch::SEL_NONE) {
00103         ViewSel<IntView>* vs[3] = { 
00104           Branch::viewselint(home,vars.a),Branch::viewselint(home,vars.b),
00105           Branch::viewselint(home,vars.c)
00106         };
00107         switch (vals.select()) {
00108         case IntValBranch::SEL_VALUES_MIN:
00109           return Branch::ViewValuesBrancher<3,true>::post(home,xv,vs,bf);
00110           break;
00111         case IntValBranch::SEL_VALUES_MAX:
00112           return Branch::ViewValuesBrancher<3,false>::post(home,xv,vs,bf);
00113           break;
00114         default:
00115           return ViewValBrancher<IntView,3,int,2>
00116             ::post(home,xv,vs,Branch::valselcommitint(home,x.size(),vals),bf);
00117         }
00118       } else {
00119         ViewSel<IntView>* vs[4] = { 
00120           Branch::viewselint(home,vars.a),Branch::viewselint(home,vars.b),
00121           Branch::viewselint(home,vars.c),Branch::viewselint(home,vars.d)
00122         };
00123         switch (vals.select()) {
00124         case IntValBranch::SEL_VALUES_MIN:
00125           return Branch::ViewValuesBrancher<4,true>::post(home,xv,vs,bf);
00126           break;
00127         case IntValBranch::SEL_VALUES_MAX:
00128           return Branch::ViewValuesBrancher<4,false>::post(home,xv,vs,bf);
00129           break;
00130         default:
00131           return ViewValBrancher<IntView,4,int,2>
00132             ::post(home,xv,vs,Branch::valselcommitint(home,x.size(),vals),bf);
00133         }
00134       }
00135     }
00136   }
00137 
00138   BrancherHandle
00139   branch(Home home, IntVar x, IntValBranch vals) {
00140     IntVarArgs xv(1); xv[0]=x;
00141     return branch(home, xv, INT_VAR_NONE(), vals);
00142   }
00143   
00144   BrancherHandle
00145   assign(Home home, const IntVarArgs& x, IntAssign ia,
00146          IntBranchFilter bf) {
00147     using namespace Int;
00148     if (home.failed()) return BrancherHandle();
00149     ViewArray<IntView> xv(home,x);
00150     ViewSel<IntView>* vs[1] = { 
00151       new (home) ViewSelNone<IntView>(home,INT_VAR_NONE())
00152     };
00153     return ViewValBrancher<IntView,1,int,1>::post
00154       (home,xv,vs,Branch::valselcommitint(home,ia),bf);
00155   }
00156 
00157   BrancherHandle
00158   assign(Home home, IntVar x, IntAssign ia) {
00159     IntVarArgs xv(1); xv[0]=x;
00160     return assign(home, xv, ia);
00161   }
00162   
00163 
00164   BrancherHandle
00165   branch(Home home, const BoolVarArgs& x,
00166          IntVarBranch vars, IntValBranch vals, BoolBranchFilter bf) {
00167     using namespace Int;
00168     if (home.failed()) return BrancherHandle();
00169     vars.expand(home,x);
00170     ViewArray<BoolView> xv(home,x);
00171     ViewSel<BoolView>* vs[1] = { 
00172       Branch::viewselbool(home,vars) 
00173     };
00174     return ViewValBrancher<BoolView,1,int,2>::post
00175       (home,xv,vs,Branch::valselcommitbool(home,x.size(),vals),bf);
00176   }
00177 
00178   BrancherHandle
00179   branch(Home home, const BoolVarArgs& x,
00180          TieBreak<IntVarBranch> vars, IntValBranch vals, 
00181          BoolBranchFilter bf) {
00182     using namespace Int;
00183     if (home.failed()) return BrancherHandle();
00184     vars.a.expand(home,x);
00185     if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
00186         (vars.a.select() == IntVarBranch::SEL_RND))
00187       vars.b = INT_VAR_NONE();
00188     vars.b.expand(home,x);
00189     if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
00190         (vars.b.select() == IntVarBranch::SEL_RND))
00191       vars.c = INT_VAR_NONE();
00192     vars.c.expand(home,x);
00193     if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
00194         (vars.c.select() == IntVarBranch::SEL_RND))
00195       vars.d = INT_VAR_NONE();
00196     vars.d.expand(home,x);
00197     if (vars.b.select() == IntVarBranch::SEL_NONE) {
00198       return branch(home,x,vars.a,vals,bf);
00199     } else {
00200       ViewArray<BoolView> xv(home,x);
00201       ValSelCommitBase<BoolView,int>* 
00202         vsc = Branch::valselcommitbool(home,x.size(),vals); 
00203       if (vars.c.select() == IntVarBranch::SEL_NONE) {
00204         ViewSel<BoolView>* vs[2] = { 
00205           Branch::viewselbool(home,vars.a),Branch::viewselbool(home,vars.b)
00206         };
00207         return ViewValBrancher<BoolView,2,int,2>::post(home,xv,vs,vsc,bf);
00208       } else if (vars.d.select() == IntVarBranch::SEL_NONE) {
00209         ViewSel<BoolView>* vs[3] = { 
00210           Branch::viewselbool(home,vars.a),Branch::viewselbool(home,vars.b),
00211           Branch::viewselbool(home,vars.c)
00212         };
00213         return ViewValBrancher<BoolView,3,int,2>::post(home,xv,vs,vsc,bf);
00214       } else {
00215         ViewSel<BoolView>* vs[4] = { 
00216           Branch::viewselbool(home,vars.a),Branch::viewselbool(home,vars.b),
00217           Branch::viewselbool(home,vars.c),Branch::viewselbool(home,vars.d)
00218         };
00219         return ViewValBrancher<BoolView,4,int,2>::post(home,xv,vs,vsc,bf);
00220       }
00221     }
00222   }
00223 
00224   BrancherHandle
00225   branch(Home home, BoolVar x, IntValBranch vals) {
00226     BoolVarArgs xv(1); xv[0]=x;
00227     return branch(home, xv, INT_VAR_NONE(), vals);
00228   }
00229   
00230   BrancherHandle
00231   assign(Home home, const BoolVarArgs& x, IntAssign ia,
00232          BoolBranchFilter bf) {
00233     using namespace Int;
00234     if (home.failed()) return BrancherHandle();
00235     ViewArray<BoolView> xv(home,x);
00236     ViewSel<BoolView>* vs[1] = { 
00237       new (home) ViewSelNone<BoolView>(home,INT_VAR_NONE())
00238     };
00239     return ViewValBrancher<BoolView,1,int,1>::post
00240       (home,xv,vs,Branch::valselcommitbool(home,ia),bf);
00241   }
00242 
00243   BrancherHandle
00244   assign(Home home, BoolVar x, IntAssign ia) {
00245     BoolVarArgs xv(1); xv[0]=x;
00246     return assign(home, xv, ia);
00247   }
00248   
00249 }
00250 
00251 // STATISTICS: int-post