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