Generated on Fri Oct 19 11:25:06 2018 for Gecode by doxygen 1.6.3

ldsb.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christopher Mears <chris.mears@monash.edu>
00005  *
00006  *  Copyright:
00007  *     Christopher Mears, 2012
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/int/ldsb.hh>
00035 #include <gecode/int/branch.hh>
00036 
00037 #include <map>
00038 
00039 namespace Gecode { namespace Int { namespace LDSB {
00040 
00041   std::pair<int,int>
00042   findVar(int *indices, unsigned int n_values, unsigned int seq_size, int index) {
00043     unsigned int seq = 0;
00044     unsigned int pos = 0;
00045     for (unsigned int i=0U ; i<n_values ; i++) {
00046       if (indices[i] == index)
00047         return std::pair<int,int>(seq,pos);
00048       pos++;
00049       if (pos == seq_size) {
00050         pos = 0;
00051         seq++;
00052       }
00053     }
00054     return std::pair<int,int>(-1,-1);
00055   }
00056 
00057 }}}
00058 
00059 namespace Gecode {
00060   using namespace Int::LDSB;
00061 
00062   SymmetryHandle VariableSymmetry(const IntVarArgs& vars) {
00063     ArgArray<VarImpBase*> a(vars.size());
00064     for (int i = 0 ; i < vars.size() ; i++)
00065       a[i] = vars[i].varimp();
00066     return SymmetryHandle(new VariableSymmetryObject(a));
00067   }
00068   SymmetryHandle VariableSymmetry(const BoolVarArgs& vars) {
00069     ArgArray<VarImpBase*> a(vars.size());
00070     for (int i = 0 ; i < vars.size() ; i++)
00071       a[i] = vars[i].varimp();
00072     return SymmetryHandle(new VariableSymmetryObject(a));
00073   }
00074   SymmetryHandle VariableSymmetry(const IntVarArgs& x,
00075                                   const IntArgs& indices) {
00076     IntVarArgs xs(indices.size());
00077     for (int i = 0 ; i < indices.size() ; i++)
00078       xs[i] = x[indices[i]];
00079     return VariableSymmetry(xs);
00080   }
00081   SymmetryHandle ValueSymmetry(const IntArgs& vs) {
00082     return SymmetryHandle(new ValueSymmetryObject(IntSet(vs)));
00083   }
00084   SymmetryHandle ValueSymmetry(const IntSet& vs) {
00085     return SymmetryHandle(new ValueSymmetryObject(vs));
00086   }
00087   SymmetryHandle ValueSymmetry(IntVar x) {
00088     return ValueSymmetry(IntSet(x.min(), x.max()));
00089   }
00090   SymmetryHandle VariableSequenceSymmetry(const IntVarArgs& vars, int ss) {
00091     ArgArray<VarImpBase*> a(vars.size());
00092     for (int i = 0 ; i < vars.size() ; i++)
00093       a[i] = vars[i].varimp();
00094     return SymmetryHandle(new VariableSequenceSymmetryObject(a, ss));
00095   }
00096   SymmetryHandle VariableSequenceSymmetry(const BoolVarArgs& vars, int ss) {
00097     ArgArray<VarImpBase*> a(vars.size());
00098     for (int i = 0 ; i < vars.size() ; i++)
00099       a[i] = vars[i].varimp();
00100     return SymmetryHandle(new VariableSequenceSymmetryObject(a, ss));
00101   }
00102   SymmetryHandle ValueSequenceSymmetry(const IntArgs& vs, int ss) {
00103     return SymmetryHandle(new ValueSequenceSymmetryObject(vs, ss));
00104   }
00105 
00106   SymmetryHandle values_reflect(int lower, int upper) {
00107     int n = (upper-lower+1)/2;
00108     IntArgs a(n*2);
00109     int i = lower;
00110     int j = upper;
00111     int k = 0;
00112     while (i < j) {
00113       a[k]   = j;
00114       a[n+k] = i;
00115       i++;
00116       j--;
00117       k++;
00118     }
00119     return ValueSequenceSymmetry(a,n);
00120   }
00121   SymmetryHandle values_reflect(const IntVar& x) {
00122     return values_reflect(x.min(), x.max());
00123   }
00124 }
00125 
00126 
00127 namespace Gecode { namespace Int { namespace LDSB {
00128 
00130   class VariableMap : public std::map<VarImpBase*,int> {};
00131 
00132   /*
00133    * The duplication in createIntSym/createBoolSym is undesirable,
00134    * and so is the use of dynamic_cast to tell the symmetries
00135    * apart.
00136    */
00137 
00139   SymmetryImp<IntView>*
00140   createIntSym(Space& home, const SymmetryHandle& s,
00141                VariableMap variableMap) {
00142     VariableSymmetryObject* varref    =
00143       dynamic_cast<VariableSymmetryObject*>(s.ref);
00144     ValueSymmetryObject* valref    =
00145       dynamic_cast<ValueSymmetryObject*>(s.ref);
00146     VariableSequenceSymmetryObject* varseqref =
00147       dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
00148     ValueSequenceSymmetryObject* valseqref =
00149       dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
00150     if (varref) {
00151       int n = varref->nxs;
00152       int* indices = home.alloc<int>(n);
00153       for (int i = 0 ; i < n ; i++) {
00154         VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
00155         if (index == variableMap.end())
00156           throw LDSBUnbranchedVariable("VariableSymmetryObject::createInt");
00157         indices[i] = index->second;
00158       }
00159       return new (home) VariableSymmetryImp<IntView>(home, indices, n);
00160     }
00161     if (valref) {
00162       int n = valref->values.size();
00163       int *vs = home.alloc<int>(n);
00164       int i = 0;
00165       for (IntSetValues v(valref->values) ; v() ; ++v) {
00166         vs[i] = v.val();
00167         i++;
00168       }
00169       return new (home) ValueSymmetryImp<IntView>(home, vs, n);
00170     }
00171     if (varseqref) {
00172       int n = varseqref->nxs;
00173       int* indices = home.alloc<int>(n);
00174       for (int i = 0 ; i < n ; i++) {
00175         VariableMap::const_iterator index =
00176           variableMap.find(varseqref->xs[i]);
00177         if (index == variableMap.end())
00178           throw LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createInt");
00179         indices[i] = index->second;
00180       }
00181       return new (home) VariableSequenceSymmetryImp<IntView>(home, indices, n,
00182         varseqref->seq_size);
00183     }
00184     if (valseqref) {
00185       unsigned int n = valseqref->values.size();
00186       int *vs = home.alloc<int>(n);
00187       for (unsigned int i = 0 ; i < n ; i++)
00188         vs[i] = valseqref->values[i];
00189       return new (home) ValueSequenceSymmetryImp<IntView>(home, vs, n,
00190         valseqref->seq_size);
00191     }
00192     GECODE_NEVER;
00193     return NULL;
00194   }
00195 
00197   SymmetryImp<BoolView>* createBoolSym(Space& home, const SymmetryHandle& s,
00198                                        VariableMap variableMap) {
00199     VariableSymmetryObject* varref    =
00200       dynamic_cast<VariableSymmetryObject*>(s.ref);
00201     ValueSymmetryObject* valref    =
00202       dynamic_cast<ValueSymmetryObject*>(s.ref);
00203     VariableSequenceSymmetryObject* varseqref =
00204       dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
00205     ValueSequenceSymmetryObject* valseqref =
00206       dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
00207     if (varref) {
00208       int n = varref->nxs;
00209       int* indices = home.alloc<int>(n);
00210       for (int i = 0 ; i < n ; i++) {
00211         VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
00212         if (index == variableMap.end())
00213           throw LDSBUnbranchedVariable("VariableSymmetryObject::createBool");
00214         indices[i] = index->second;
00215       }
00216       return new (home) VariableSymmetryImp<BoolView>(home, indices, n);
00217     }
00218     if (valref) {
00219       int n = valref->values.size();
00220       int *vs = home.alloc<int>(n);
00221       int i = 0;
00222       for (IntSetValues v(valref->values) ; v() ; ++v) {
00223         vs[i] = v.val();
00224         i++;
00225       }
00226       return new (home) ValueSymmetryImp<BoolView>(home, vs, n);
00227     }
00228     if (varseqref) {
00229       int n = varseqref->nxs;
00230       int* indices = home.alloc<int>(n);
00231       for (int i = 0 ; i < n ; i++) {
00232         VariableMap::const_iterator index =
00233           variableMap.find(varseqref->xs[i]);
00234         if (index == variableMap.end())
00235           throw LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createBool");
00236         indices[i] = index->second;
00237       }
00238       return new (home) VariableSequenceSymmetryImp<BoolView>(home, indices,
00239         n, varseqref->seq_size);
00240     }
00241     if (valseqref) {
00242       unsigned int n = valseqref->values.size();
00243       int *vs = home.alloc<int>(n);
00244       for (unsigned int i = 0 ; i < n ; i++)
00245         vs[i] = valseqref->values[i];
00246       return new (home) ValueSequenceSymmetryImp<BoolView>(home, vs, n,
00247         valseqref->seq_size);
00248     }
00249     GECODE_NEVER;
00250     return NULL;
00251   }
00252 }}}
00253 
00254 namespace Gecode {
00255 
00256   using namespace Int::LDSB;
00257 
00258   void
00259   branch(Home home, const IntVarArgs& x,
00260          IntVarBranch vars, IntValBranch vals,
00261          const Symmetries& syms,
00262          IntBranchFilter bf,
00263          IntVarValPrint vvp) {
00264     using namespace Int;
00265     if (home.failed()) return;
00266     vars.expand(home,x);
00267     ViewArray<IntView> xv(home,x);
00268     ViewSel<IntView>* vs[1] = {
00269       Branch::viewsel(home,vars)
00270     };
00271     switch (vals.select()) {
00272     case IntValBranch::SEL_SPLIT_MIN:
00273     case IntValBranch::SEL_SPLIT_MAX:
00274     case IntValBranch::SEL_RANGE_MIN:
00275     case IntValBranch::SEL_RANGE_MAX:
00276     case IntValBranch::SEL_VALUES_MIN:
00277     case IntValBranch::SEL_VALUES_MAX:
00278       throw LDSBBadValueSelection("Int::LDSB::branch");
00279       break;
00280     case IntValBranch::SEL_VAL_COMMIT:
00281       if (vals.commit())
00282         throw LDSBBadValueSelection("Int::LDSB::branch");
00283       // If vals.commit() is valid, it means it will commit with
00284       // binary branching, which is OK for LDSB, so we fall through.
00285     default:
00286       // Construct mapping from each variable in the array to its index
00287       // in the array.
00288       VariableMap variableMap;
00289       for (int i = 0 ; i < x.size() ; i++)
00290         variableMap[x[i].varimp()] = i;
00291 
00292       // Convert the modelling-level Symmetries object into an array of
00293       // SymmetryImp objects.
00294       int n = syms.size();
00295       SymmetryImp<IntView>** array =
00296         static_cast<Space&>(home).alloc<SymmetryImp<IntView>* >(n);
00297       for (int i = 0 ; i < n ; i++) {
00298         array[i] = createIntSym(home, syms[i], variableMap);
00299       }
00300 
00301       postldsbbrancher<IntView,1,int,2>
00302         (home,xv,vs,Branch::valselcommit(home,vals),
00303          array,n,bf,vvp);
00304     }
00305   }
00306 
00307   void
00308   branch(Home home, const IntVarArgs& x,
00309          TieBreak<IntVarBranch> vars, IntValBranch vals,
00310          const Symmetries& syms,
00311          IntBranchFilter bf,
00312          IntVarValPrint vvp) {
00313     using namespace Int;
00314     if (home.failed()) return;
00315     vars.a.expand(home,x);
00316     if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
00317         (vars.a.select() == IntVarBranch::SEL_RND))
00318       vars.b = INT_VAR_NONE();
00319     vars.b.expand(home,x);
00320     if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
00321         (vars.b.select() == IntVarBranch::SEL_RND))
00322       vars.c = INT_VAR_NONE();
00323     vars.c.expand(home,x);
00324     if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
00325         (vars.c.select() == IntVarBranch::SEL_RND))
00326       vars.d = INT_VAR_NONE();
00327     vars.d.expand(home,x);
00328     if (vars.b.select() == IntVarBranch::SEL_NONE) {
00329       branch(home,x,vars.a,vals,syms,bf,vvp);
00330     } else {
00331       // Construct mapping from each variable in the array to its index
00332       // in the array.
00333       VariableMap variableMap;
00334       for (int i = 0 ; i < x.size() ; i++)
00335         variableMap[x[i].varimp()] = i;
00336 
00337       // Convert the modelling-level Symmetries object into an array of
00338       // SymmetryImp objects.
00339       int n = syms.size();
00340       SymmetryImp<IntView>** array =
00341         static_cast<Space&>(home).alloc<SymmetryImp<IntView>* >(n);
00342       for (int i = 0 ; i < n ; i++) {
00343         array[i] = createIntSym(home, syms[i], variableMap);
00344       }
00345 
00346       ViewArray<IntView> xv(home,x);
00347       if (vars.c.select() == IntVarBranch::SEL_NONE) {
00348         ViewSel<IntView>* vs[2] = {
00349           Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
00350         };
00351         switch (vals.select()) {
00352         case IntValBranch::SEL_SPLIT_MIN:
00353         case IntValBranch::SEL_SPLIT_MAX:
00354         case IntValBranch::SEL_RANGE_MIN:
00355         case IntValBranch::SEL_RANGE_MAX:
00356         case IntValBranch::SEL_VALUES_MIN:
00357         case IntValBranch::SEL_VALUES_MAX:
00358           throw LDSBBadValueSelection("Int::LDSB::branch");
00359           break;
00360         case IntValBranch::SEL_VAL_COMMIT:
00361           if (vals.commit())
00362             throw LDSBBadValueSelection("Int::LDSB::branch");
00363           // If vals.commit() is valid, it means it will commit with
00364           // binary branching, which is OK for LDSB, so we fall through.
00365         default:
00366           postldsbbrancher<IntView,2,int,2>
00367             (home,xv,vs,Branch::valselcommit(home,vals),
00368              array,n,bf,vvp);
00369         }
00370       } else if (vars.d.select() == IntVarBranch::SEL_NONE) {
00371         ViewSel<IntView>* vs[3] = {
00372           Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
00373           Branch::viewsel(home,vars.c)
00374         };
00375         switch (vals.select()) {
00376         case IntValBranch::SEL_SPLIT_MIN:
00377         case IntValBranch::SEL_SPLIT_MAX:
00378         case IntValBranch::SEL_RANGE_MIN:
00379         case IntValBranch::SEL_RANGE_MAX:
00380         case IntValBranch::SEL_VALUES_MIN:
00381         case IntValBranch::SEL_VALUES_MAX:
00382           throw LDSBBadValueSelection("Int::LDSB::branch");
00383           break;
00384         case IntValBranch::SEL_VAL_COMMIT:
00385           if (vals.commit())
00386             throw LDSBBadValueSelection("Int::LDSB::branch");
00387           // If vals.commit() is valid, it means it will commit with
00388           // binary branching, which is OK for LDSB, so we fall through.
00389         default:
00390           postldsbbrancher<IntView,3,int,2>
00391             (home,xv,vs,Branch::valselcommit(home,vals),
00392              array,n,bf,vvp);
00393         }
00394       } else {
00395         ViewSel<IntView>* vs[4] = {
00396           Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
00397           Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
00398         };
00399         switch (vals.select()) {
00400         case IntValBranch::SEL_SPLIT_MIN:
00401         case IntValBranch::SEL_SPLIT_MAX:
00402         case IntValBranch::SEL_RANGE_MIN:
00403         case IntValBranch::SEL_RANGE_MAX:
00404         case IntValBranch::SEL_VALUES_MIN:
00405         case IntValBranch::SEL_VALUES_MAX:
00406           throw LDSBBadValueSelection("Int::LDSB::branch");
00407           break;
00408         case IntValBranch::SEL_VAL_COMMIT:
00409           if (vals.commit())
00410             throw LDSBBadValueSelection("Int::LDSB::branch");
00411           // If vals.commit() is valid, it means it will commit with
00412           // binary branching, which is OK for LDSB, so we fall through.
00413         default:
00414           postldsbbrancher<IntView,4,int,2>
00415             (home,xv,vs,Branch::valselcommit(home,vals),
00416              array,n,bf,vvp);
00417         }
00418       }
00419     }
00420   }
00421 
00422   void
00423   branch(Home home, const BoolVarArgs& x,
00424          BoolVarBranch vars, BoolValBranch vals,
00425          const Symmetries& syms,
00426          BoolBranchFilter bf,
00427          BoolVarValPrint vvp) {
00428     using namespace Int;
00429     if (home.failed()) return;
00430     vars.expand(home,x);
00431     ViewArray<BoolView> xv(home,x);
00432     ViewSel<BoolView>* vs[1] = {
00433       Branch::viewsel(home,vars)
00434     };
00435 
00436     // Construct mapping from each variable in the array to its index
00437     // in the array.
00438     VariableMap variableMap;
00439     for (int i = 0 ; i < x.size() ; i++)
00440       variableMap[x[i].varimp()] = i;
00441 
00442     // Convert the modelling-level Symmetries object into an array of
00443     // SymmetryImp objects.
00444     int n = syms.size();
00445     SymmetryImp<BoolView>** array =
00446       static_cast<Space&>(home).alloc<SymmetryImp<BoolView>* >(n);
00447     for (int i = 0 ; i < n ; i++) {
00448       array[i] = createBoolSym(home, syms[i], variableMap);
00449     }
00450 
00451     // Technically these "bad" value selection could in fact work with
00452     // LDSB, because they degenerate to binary splitting for
00453     // Booleans.  Nonetheless, we explicitly forbid them for
00454     // consistency with the integer version.
00455     switch (vals.select()) {
00456     case BoolValBranch::SEL_VAL_COMMIT:
00457       if (vals.commit())
00458         throw LDSBBadValueSelection("Int::LDSB::branch");
00459       // If vals.commit() is valid, it means it will commit with
00460       // binary branching, which is OK for LDSB, so we fall through.
00461     default:
00462       postldsbbrancher<BoolView,1,int,2>
00463         (home,xv,vs,Branch::valselcommit(home,vals),array,n,bf,vvp);
00464     }
00465   }
00466 
00467 
00468   void
00469   branch(Home home, const BoolVarArgs& x,
00470          TieBreak<BoolVarBranch> vars, BoolValBranch vals,
00471          const Symmetries& syms,
00472          BoolBranchFilter bf,
00473          BoolVarValPrint vvp) {
00474     using namespace Int;
00475     if (home.failed()) return;
00476     vars.a.expand(home,x);
00477     if ((vars.a.select() == BoolVarBranch::SEL_NONE) ||
00478         (vars.a.select() == BoolVarBranch::SEL_RND))
00479       vars.b = BOOL_VAR_NONE();
00480     vars.b.expand(home,x);
00481     if ((vars.b.select() == BoolVarBranch::SEL_NONE) ||
00482         (vars.b.select() == BoolVarBranch::SEL_RND))
00483       vars.c = BOOL_VAR_NONE();
00484     vars.c.expand(home,x);
00485     if ((vars.c.select() == BoolVarBranch::SEL_NONE) ||
00486         (vars.c.select() == BoolVarBranch::SEL_RND))
00487       vars.d = BOOL_VAR_NONE();
00488     vars.d.expand(home,x);
00489     if (vars.b.select() == BoolVarBranch::SEL_NONE) {
00490       branch(home,x,vars.a,vals,syms,bf,vvp);
00491     } else {
00492       // Construct mapping from each variable in the array to its index
00493       // in the array.
00494       VariableMap variableMap;
00495       for (int i = 0 ; i < x.size() ; i++)
00496         variableMap[x[i].varimp()] = i;
00497 
00498       // Convert the modelling-level Symmetries object into an array of
00499       // SymmetryImp objects.
00500       int n = syms.size();
00501       SymmetryImp<BoolView>** array =
00502         static_cast<Space&>(home).alloc<SymmetryImp<BoolView>* >(n);
00503       for (int i = 0 ; i < n ; i++) {
00504         array[i] = createBoolSym(home, syms[i], variableMap);
00505       }
00506 
00507       // Technically these "bad" value selection could in fact work with
00508       // LDSB, because they degenerate to binary splitting for
00509       // Booleans.  Nonetheless, we explicitly forbid them for
00510       // consistency with the integer version.
00511       switch (vals.select()) {
00512       case BoolValBranch::SEL_VAL_COMMIT:
00513         if (vals.commit())
00514           throw LDSBBadValueSelection("Int::LDSB::branch");
00515         // If vals.commit() is valid, it means it will commit with
00516         // binary branching, which is OK for LDSB, so we fall through.
00517       default:
00518         ;
00519         // Do nothing and continue.
00520       }
00521 
00522       ViewArray<BoolView> xv(home,x);
00523       ValSelCommitBase<BoolView,int>*
00524         vsc = Branch::valselcommit(home,vals);
00525       if (vars.c.select() == BoolVarBranch::SEL_NONE) {
00526         ViewSel<BoolView>* vs[2] = {
00527           Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
00528         };
00529         postldsbbrancher<BoolView,2,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
00530       } else if (vars.d.select() == BoolVarBranch::SEL_NONE) {
00531         ViewSel<BoolView>* vs[3] = {
00532           Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
00533           Branch::viewsel(home,vars.c)
00534         };
00535         postldsbbrancher<BoolView,3,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
00536       } else {
00537         ViewSel<BoolView>* vs[4] = {
00538           Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
00539           Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
00540         };
00541         postldsbbrancher<BoolView,4,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
00542       }
00543     }
00544   }
00545 
00546 }
00547 
00548 
00549 
00550 // STATISTICS: int-branch