Generated on Thu Apr 11 13:58:54 2019 for Gecode by doxygen 1.6.3

branch.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00005  *     Christian Schulte <schulte@gecode.org>
00006  *
00007  *  Contributing authors:
00008  *     Vincent Barichard <Vincent.Barichard@univ-angers.fr>
00009  *
00010  *  Copyright:
00011  *     Mikael Lagerkvist, 2005
00012  *     Christian Schulte, 2009
00013  *     Vincent Barichard, 2012
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #include "test/branch.hh"
00041 
00042 #include <algorithm>
00043 #include <map>
00044 #include <vector>
00045 #include <iostream>
00046 
00047 #include <gecode/kernel.hh>
00048 #include <gecode/int.hh>
00049 #ifdef GECODE_HAS_SET_VARS
00050 #include <gecode/set.hh>
00051 #endif
00052 #ifdef GECODE_HAS_FLOAT_VARS
00053 #include <gecode/float.hh>
00054 #endif
00055 
00056 #include <gecode/search.hh>
00057 
00058 namespace Test { namespace Branch {
00059 
00061   double tbl(const Gecode::Space&, double w, double b) {
00062     return (w + (b-w)/2.0);
00063   }
00064 
00066   class IntTestSpace : public Gecode::Space {
00067   public:
00069     Gecode::IntVarArray x;
00071     Gecode::IntVarBranch vara, varb;
00073     Gecode::IntValBranch val;
00075     IntTestSpace(int n, Gecode::IntSet& d)
00076       : x(*this, n, d),
00077         vara(Gecode::INT_VAR_NONE()), varb(Gecode::INT_VAR_NONE()),
00078         val(Gecode::INT_VAL_MIN()) {}
00080     IntTestSpace(IntTestSpace& s)
00081       : Gecode::Space(s), vara(s.vara), varb(s.varb), val(s.val) {
00082       x.update(*this, s.x);
00083     }
00085     virtual Gecode::Space* copy(void) {
00086       return new IntTestSpace(*this);
00087     }
00088   };
00089 
00091   class BoolTestSpace : public Gecode::Space {
00092   public:
00094     Gecode::BoolVarArray x;
00096     BoolTestSpace(int n)
00097       : x(*this, n, 0, 1) {}
00099     BoolTestSpace(BoolTestSpace& s)
00100       : Gecode::Space(s) {
00101       x.update(*this, s.x);
00102     }
00104     virtual Gecode::Space* copy(void) {
00105       return new BoolTestSpace(*this);
00106     }
00107   };
00108 
00109 #ifdef GECODE_HAS_SET_VARS
00110 
00111   class SetTestSpace : public Gecode::Space {
00112   public:
00114     Gecode::SetVarArray x;
00116     SetTestSpace(int n, Gecode::IntSet& d)
00117       : x(*this, n, Gecode::IntSet::empty, d) {}
00119     SetTestSpace(SetTestSpace& s)
00120       : Gecode::Space(s) {
00121       x.update(*this, s.x);
00122     }
00124     virtual Gecode::Space* copy(void) {
00125       return new SetTestSpace(*this);
00126     }
00127   };
00128 #endif
00129 
00130 #ifdef GECODE_HAS_FLOAT_VARS
00131 
00132   class FloatTestSpace : public Gecode::Space {
00133   public:
00135     Gecode::FloatVarArray x;
00137     FloatTestSpace(int n, Gecode::FloatVal& d)
00138       : x(*this, n, d.min(), d.max()) {}
00140     FloatTestSpace(FloatTestSpace& s)
00141       : Gecode::Space(s) {
00142       x.update(*this, s.x);
00143     }
00145     virtual Gecode::Space* copy(void) {
00146       return new FloatTestSpace(*this);
00147     }
00148   };
00149 #endif
00150 
00156 
00157   const char* int_var_branch_name[] = {
00158     "SINGLE VARIABLE",
00159     "INT_VAR_NONE",
00160     "INT_VAR_RND",
00161     "INT_VAR_MERIT_MIN",
00162     "INT_VAR_MERIT_MAX",
00163     "INT_VAR_DEGREE_MIN",
00164     "INT_VAR_DEGREE_MAX",
00165     "INT_VAR_AFC_MIN",
00166     "INT_VAR_AFC_MAX",
00167     "INT_VAR_ACTION_MIN",
00168     "INT_VAR_ACTION_MAX",
00169     "INT_VAR_CHB_MIN",
00170     "INT_VAR_CHB_MAX",
00171     "INT_VAR_MIN_MIN",
00172     "INT_VAR_MIN_MAX",
00173     "INT_VAR_MAX_MIN",
00174     "INT_VAR_MAX_MAX",
00175     "INT_VAR_SIZE_MIN",
00176     "INT_VAR_SIZE_MAX",
00177     "INT_VAR_DEGREE_SIZE_MIN",
00178     "INT_VAR_DEGREE_SIZE_MAX",
00179     "INT_VAR_AFC_SIZE_MIN",
00180     "INT_VAR_AFC_SIZE_MAX",
00181     "INT_VAR_ACTION_SIZE_MIN",
00182     "INT_VAR_ACTION_SIZE_MAX",
00183     "INT_VAR_CHB_SIZE_MIN",
00184     "INT_VAR_CHB_SIZE_MAX",
00185     "INT_VAR_REGRET_MIN_MIN",
00186     "INT_VAR_REGRET_MIN_MAX",
00187     "INT_VAR_REGRET_MAX_MIN",
00188     "INT_VAR_REGRET_MAX_MAX"
00189   };
00191   const int n_int_var_branch =
00192     sizeof(int_var_branch_name)/sizeof(const char*);
00194   const char* bool_var_branch_name[] = {
00195     "SINGLE VARIABLE",
00196     "BOOL_VAR_NONE",
00197     "BOOL_VAR_RND",
00198     "BOOL_VAR_MERIT_MIN",
00199     "BOOL_VAR_MERIT_MAX",
00200     "BOOL_VAR_DEGREE_MIN",
00201     "BOOL_VAR_DEGREE_MAX",
00202     "BOOL_VAR_AFC_MIN",
00203     "BOOL_VAR_AFC_MAX",
00204     "BOOL_VAR_ACTION_MIN",
00205     "BOOL_VAR_ACTION_MAX",
00206     "BOOL_VAR_CHB_MIN",
00207     "BOOL_VAR_CHB_MAX"
00208   };
00210   const int n_bool_var_branch =
00211     sizeof(bool_var_branch_name)/sizeof(const char*);
00213   double int_merit(const Gecode::Space&, Gecode::IntVar x, int) {
00214     return x.min();
00215   }
00217   double bool_merit(const Gecode::Space&, Gecode::BoolVar x, int) {
00218     return x.min();
00219   }
00221   const char* int_val_branch_name[] = {
00222     "INT_VAL_MIN",
00223     "INT_VAL_MED",
00224     "INT_VAL_MAX",
00225     "INT_VAL_RND",
00226     "INT_VAL_SPLIT_MIN",
00227     "INT_VAL_SPLIT_MAX",
00228     "INT_VAL_RANGE_MIN",
00229     "INT_VAL_RANGE_MAX",
00230     "INT_VAL",
00231     "INT_VALUES_MIN",
00232     "INT_VALUES_MAX"
00233   };
00235   const int n_int_val_branch =
00236     sizeof(int_val_branch_name)/sizeof(const char*);
00238   const char* bool_val_branch_name[] = {
00239     "BOOL_VAL_MIN",
00240     "BOOL_VAL_MAX",
00241     "BOOL_VAL_RND",
00242     "BOOL_VAL"
00243   };
00245   const int n_bool_val_branch =
00246     sizeof(bool_val_branch_name)/sizeof(const char*);
00248   int int_val(const Gecode::Space&, Gecode::IntVar x, int) {
00249     return x.min();
00250   }
00252   int bool_val(const Gecode::Space&, Gecode::BoolVar x, int) {
00253     return x.min();
00254   }
00256 
00257 #ifdef GECODE_HAS_SET_VARS
00258 
00263 
00264   const char* set_var_branch_name[] = {
00265     "SINGLE VARIABLE",
00266     "SET_VAR_NONE",
00267     "SET_VAR_RND",
00268     "SET_VAR_MERIT_MIN",
00269     "SET_VAR_MERIT_MAX",
00270     "SET_VAR_DEGREE_MIN",
00271     "SET_VAR_DEGREE_MAX",
00272     "SET_VAR_AFC_MIN",
00273     "SET_VAR_AFC_MAX",
00274     "SET_VAR_ACTION_MIN",
00275     "SET_VAR_ACTION_MAX",
00276     "SET_VAR_CHB_MIN",
00277     "SET_VAR_CHB_MAX",
00278     "SET_VAR_MIN_MIN",
00279     "SET_VAR_MIN_MAX",
00280     "SET_VAR_MAX_MIN",
00281     "SET_VAR_MAX_MAX",
00282     "SET_VAR_SIZE_MIN",
00283     "SET_VAR_SIZE_MAX",
00284     "SET_VAR_DEGREE_SIZE_MIN",
00285     "SET_VAR_DEGREE_SIZE_MAX",
00286     "SET_VAR_AFC_SIZE_MIN",
00287     "SET_VAR_AFC_SIZE_MAX",
00288     "SET_VAR_ACTION_SIZE_MIN",
00289     "SET_VAR_ACTION_SIZE_MAX",
00290     "SET_VAR_CHB_SIZE_MIN",
00291     "SET_VAR_CHB_SIZE_MAX"
00292   };
00294   const int n_set_var_branch =
00295     sizeof(set_var_branch_name)/sizeof(const char*);
00297   double set_merit(const Gecode::Space&, Gecode::SetVar, int) {
00298     return 2.0;
00299   }
00301   const char* set_val_branch_name[] = {
00302     "SET_VAL_MIN_INC",
00303     "SET_VAL_MIN_EXC",
00304     "SET_VAL_MED_INC",
00305     "SET_VAL_MED_EXC",
00306     "SET_VAL_MAX_INC",
00307     "SET_VAL_MAX_EXC",
00308     "SET_VAL_RND_INC",
00309     "SET_VAL_RND_EXC",
00310     "SET_VAL"
00311   };
00313   const int n_set_val_branch =
00314     sizeof(set_val_branch_name)/sizeof(const char*);
00316   int set_val(const Gecode::Space&, Gecode::SetVar x, int) {
00317     Gecode::SetVarUnknownRanges r(x);
00318     return r.min();
00319   }
00321 #endif
00322 
00323 #ifdef GECODE_HAS_FLOAT_VARS
00324 
00329 
00330   const char* float_var_branch_name[] = {
00331     "SINGLE VARIABLE",
00332     "FLOAT_VAR_NONE",
00333     "FLOAT_VAR_RND",
00334     "FLOAT_VAR_MERIT_MIN",
00335     "FLOAT_VAR_MERIT_MAX",
00336     "FLOAT_VAR_DEGREE_MIN",
00337     "FLOAT_VAR_DEGREE_MAX",
00338     "FLOAT_VAR_AFC_MIN",
00339     "FLOAT_VAR_AFC_MAX",
00340     "FLOAT_VAR_ACTION_MIN",
00341     "FLOAT_VAR_ACTION_MAX",
00342     "FLOAT_VAR_CHB_MIN",
00343     "FLOAT_VAR_CHB_MAX",
00344     "FLOAT_VAR_MIN_MIN",
00345     "FLOAT_VAR_MIN_MAX",
00346     "FLOAT_VAR_MAX_MIN",
00347     "FLOAT_VAR_MAX_MAX",
00348     "FLOAT_VAR_SIZE_MIN",
00349     "FLOAT_VAR_SIZE_MAX",
00350     "FLOAT_VAR_DEGREE_SIZE_MIN",
00351     "FLOAT_VAR_DEGREE_SIZE_MAX",
00352     "FLOAT_VAR_AFC_SIZE_MIN",
00353     "FLOAT_VAR_AFC_SIZE_MAX",
00354     "FLOAT_VAR_ACTION_SIZE_MIN",
00355     "FLOAT_VAR_ACTION_SIZE_MAX",
00356     "FLOAT_VAR_CHB_SIZE_MIN",
00357     "FLOAT_VAR_CHB_SIZE_MAX"
00358   };
00360   const int n_float_var_branch =
00361     sizeof(float_var_branch_name)/sizeof(const char*);
00363   double float_merit(const Gecode::Space&, Gecode::FloatVar x, int) {
00364     return static_cast<double>(x.degree());
00365   }
00367   const char* float_val_branch_name[] = {
00368     "FLOAT_VAL_SPLIT_MIN",
00369     "FLOAT_VAL_SPLIT_MAX",
00370     "FLOAT_VAL_SPLIT_RND",
00371     "FLOAT_VAL"
00372   };
00374   const int n_float_val_branch =
00375     sizeof(float_val_branch_name)/sizeof(const char*);
00377   Gecode::FloatNumBranch float_val(const Gecode::Space&,
00378                                    Gecode::FloatVar x, int) {
00379     Gecode::FloatNumBranch nl; nl.n=x.med(); nl.l=true;
00380     return nl;
00381   }
00383 #endif
00384 
00386   class RunInfo {
00387   public:
00388     std::string var, val;
00389     unsigned int a_d, c_d;
00390     RunInfo(const std::string& vara, const std::string& varb,
00391             const std::string& valname,
00392             const Gecode::Search::Options& o)
00393       : var(vara + "::" + varb), val(valname), a_d(o.a_d), c_d(o.c_d) {}
00394     void print(std::ostream& o) const {
00395       o << "(" << var << ", " << val << ", " << a_d << ", " << c_d << ")";
00396     }
00397   };
00398 
00399 }}
00400 
00401 std::ostream&
00402 operator<<(std::ostream& os, const Test::Branch::RunInfo& ri) {
00403   ri.print(os);
00404   return os;
00405 }
00406 
00407 
00408 namespace Test { namespace Branch {
00409 
00411   template<class TestSpace>
00412   int solutions(TestSpace* c, Gecode::Search::Options& o, int maxNbSol = -1) {
00413     o.a_d = Base::rand(10);
00414     o.c_d = Base::rand(10);
00415     Gecode::DFS<TestSpace> e_s(c, o);
00416     delete c;
00417 
00418     // Find number of solutions
00419     int s = 0;
00420     do {
00421       Gecode::Space* ex = e_s.next();
00422       if (ex == NULL) break;
00423       delete ex;
00424       ++s;
00425       if ((maxNbSol >= 0) && (maxNbSol == s)) break;
00426     } while (true);
00427     return s;
00428   }
00429 
00430   IntTest::IntTest(const std::string& s, int a, const Gecode::IntSet& d)
00431     : Base("Int::Branch::"+s), arity(a), dom(d) {
00432   }
00433 
00434   bool
00435   IntTest::run(void) {
00436     using std::map;
00437     using std::vector;
00438     using std::string;
00439     using std::ostream;
00440     using namespace Gecode;
00441 
00442     // Results of tests run
00443     map<int, vector<RunInfo> > results;
00444     // Set up root space
00445     IntTestSpace* root = new IntTestSpace(arity,dom);
00446     post(*root, root->x);
00447     results.clear();
00448 
00449     IntArgs d(arity);
00450     for (int i=arity; i--; )
00451       d[i]=i;
00452 
00453     for (int vara = 0; vara<n_int_var_branch; vara++) {
00454       for (int varb = 1; varb<n_int_var_branch; varb++) {
00455         for (int val = 0; val<n_int_val_branch; val++) {
00456           Rnd r(1);
00457 
00458           IntValBranch ivb;
00459           switch (val) {
00460           case  0: ivb = INT_VAL_MIN(); break;
00461           case  1: ivb = INT_VAL_MED(); break;
00462           case  2: ivb = INT_VAL_MAX(); break;
00463           case  3: ivb = INT_VAL_RND(r); break;
00464           case  4: ivb = INT_VAL_SPLIT_MIN(); break;
00465           case  5: ivb = INT_VAL_SPLIT_MAX(); break;
00466           case  6: ivb = INT_VAL_RANGE_MIN(); break;
00467           case  7: ivb = INT_VAL_RANGE_MAX(); break;
00468           case  8: ivb = INT_VAL(&int_val); break;
00469           case  9: ivb = INT_VALUES_MIN(); break;
00470           case 10: ivb = INT_VALUES_MAX(); break;
00471           }
00472 
00473           IntTestSpace* c = static_cast<IntTestSpace*>(root->clone());
00474 
00475           if ((vara == 0) && (val < 11)) {
00476             for (int i=0; i<c->x.size(); i++)
00477               branch(*c, c->x[i], ivb);
00478           } else {
00479             Rnd ra(1);
00480             IntVarBranch ivba;
00481             IntAction iaa(*c, c->x, 0.9);
00482             IntCHB ica(*c, c->x);
00483             switch (vara) {
00484             case  0: ivba = INT_VAR_NONE(); break;
00485             case  1: ivba = INT_VAR_NONE(); break;
00486             case  2: ivba = INT_VAR_RND(ra); break;
00487             case  3: ivba = INT_VAR_MERIT_MIN(&int_merit); break;
00488             case  4: ivba = INT_VAR_MERIT_MAX(&int_merit); break;
00489             case  5: ivba = INT_VAR_DEGREE_MIN(); break;
00490             case  6: ivba = INT_VAR_DEGREE_MAX(); break;
00491             case  7: ivba = INT_VAR_AFC_MIN(0.5); break;
00492             case  8: ivba = INT_VAR_AFC_MAX(0.5); break;
00493             case  9: ivba = INT_VAR_ACTION_MIN(iaa); break;
00494             case 10: ivba = INT_VAR_ACTION_MAX(iaa); break;
00495             case 11: ivba = INT_VAR_CHB_MIN(ica); break;
00496             case 12: ivba = INT_VAR_CHB_MAX(ica); break;
00497             case 13: ivba = INT_VAR_MIN_MIN(); break;
00498             case 14: ivba = INT_VAR_MIN_MAX(); break;
00499             case 15: ivba = INT_VAR_MAX_MIN(); break;
00500             case 16: ivba = INT_VAR_MAX_MAX(); break;
00501             case 17: ivba = INT_VAR_SIZE_MIN(); break;
00502             case 18: ivba = INT_VAR_SIZE_MAX(); break;
00503             case 19: ivba = INT_VAR_DEGREE_SIZE_MIN(); break;
00504             case 20: ivba = INT_VAR_DEGREE_SIZE_MAX(); break;
00505             case 21: ivba = INT_VAR_AFC_SIZE_MIN(); break;
00506             case 22: ivba = INT_VAR_AFC_SIZE_MAX(); break;
00507             case 23: ivba = INT_VAR_ACTION_SIZE_MIN(iaa); break;
00508             case 24: ivba = INT_VAR_ACTION_SIZE_MAX(iaa); break;
00509             case 25: ivba = INT_VAR_CHB_SIZE_MIN(ica); break;
00510             case 26: ivba = INT_VAR_CHB_SIZE_MAX(ica); break;
00511             case 27: ivba = INT_VAR_REGRET_MIN_MIN(); break;
00512             case 28: ivba = INT_VAR_REGRET_MIN_MAX(); break;
00513             case 29: ivba = INT_VAR_REGRET_MAX_MIN(); break;
00514             case 30: ivba = INT_VAR_REGRET_MAX_MAX(); break;
00515             }
00516 
00517             Rnd rb(2);
00518             IntVarBranch ivbb;
00519             IntAction iab(*c, c->x, 0.9, &int_merit);
00520             IntCHB icb(*c, c->x, &int_merit);
00521             switch (varb) {
00522             case  0: ivbb = INT_VAR_NONE(); break;
00523             case  1: ivbb = INT_VAR_NONE(); break;
00524             case  2: ivbb = INT_VAR_RND(rb); break;
00525             case  3: ivbb = INT_VAR_MERIT_MIN(&int_merit,&tbl); break;
00526             case  4: ivbb = INT_VAR_MERIT_MAX(&int_merit,&tbl); break;
00527             case  5: ivbb = INT_VAR_DEGREE_MIN(&tbl); break;
00528             case  6: ivbb = INT_VAR_DEGREE_MAX(&tbl); break;
00529             case  7: ivbb = INT_VAR_AFC_MIN(0.5,&tbl); break;
00530             case  8: ivbb = INT_VAR_AFC_MAX(0.5,&tbl); break;
00531             case  9: ivbb = INT_VAR_ACTION_MIN(iab,&tbl); break;
00532             case 10: ivbb = INT_VAR_ACTION_MAX(iab,&tbl); break;
00533             case 11: ivbb = INT_VAR_CHB_MIN(icb,&tbl); break;
00534             case 12: ivbb = INT_VAR_CHB_MAX(icb,&tbl); break;
00535             case 13: ivbb = INT_VAR_MIN_MIN(&tbl); break;
00536             case 14: ivbb = INT_VAR_MIN_MAX(&tbl); break;
00537             case 15: ivbb = INT_VAR_MAX_MIN(&tbl); break;
00538             case 16: ivbb = INT_VAR_MAX_MAX(&tbl); break;
00539             case 17: ivbb = INT_VAR_SIZE_MIN(&tbl); break;
00540             case 18: ivbb = INT_VAR_SIZE_MAX(&tbl); break;
00541             case 19: ivbb = INT_VAR_DEGREE_SIZE_MIN(&tbl); break;
00542             case 20: ivbb = INT_VAR_DEGREE_SIZE_MAX(&tbl); break;
00543             case 21: ivbb = INT_VAR_AFC_SIZE_MIN(1.0,&tbl); break;
00544             case 22: ivbb = INT_VAR_AFC_SIZE_MAX(1.0,&tbl); break;
00545             case 23: ivbb = INT_VAR_ACTION_SIZE_MIN(iab,&tbl); break;
00546             case 24: ivbb = INT_VAR_ACTION_SIZE_MAX(iab,&tbl); break;
00547             case 25: ivbb = INT_VAR_CHB_SIZE_MIN(icb,&tbl); break;
00548             case 26: ivbb = INT_VAR_CHB_SIZE_MAX(icb,&tbl); break;
00549             case 27: ivbb = INT_VAR_REGRET_MIN_MIN(&tbl); break;
00550             case 28: ivbb = INT_VAR_REGRET_MIN_MAX(&tbl); break;
00551             case 29: ivbb = INT_VAR_REGRET_MAX_MIN(&tbl); break;
00552             case 30: ivbb = INT_VAR_REGRET_MAX_MAX(&tbl); break;
00553             }
00554 
00555             switch (Base::rand(9U)) {
00556             case 0U:
00557               branch(*c, c->x, ivba, ivb); break;
00558             case 1U:
00559               branch(*c, c->x, ivbb, ivb); break;
00560             case 2U:
00561               branch(*c, c->x, tiebreak(ivba,ivbb), ivb); break;
00562             case 3U:
00563               branch(*c, c->x, tiebreak(ivbb,ivba), ivb); break;
00564             case 4U:
00565               branch(*c, c->x, tiebreak(ivba,ivba,ivbb), ivb); break;
00566             case 5U:
00567               branch(*c, c->x, tiebreak(ivba,ivbb,ivbb), ivb); break;
00568             case 6U:
00569               branch(*c, c->x, tiebreak(ivbb,ivba,ivba), ivb); break;
00570             case 7U:
00571               branch(*c, c->x, tiebreak(ivba,ivba,ivbb,ivba), ivb); break;
00572             case 8U:
00573               branch(*c, c->x, tiebreak(ivbb,ivba,ivbb,ivba), ivb); break;
00574             }
00575 
00576           }
00577           Gecode::Search::Options o;
00578           results[solutions(c,o)].push_back
00579             (RunInfo(int_var_branch_name[vara],
00580                      int_var_branch_name[varb],
00581                      int_val_branch_name[val],
00582                      o));
00583         }
00584       }
00585     }
00586     if (results.size() > 1)
00587       goto failed;
00588     delete root;
00589     return true;
00590   failed:
00591     std::cout   << "FAILURE" << std::endl;
00592     for (map<int, vector<RunInfo> >::iterator it = results.begin();
00593          it != results.end(); ++it) {
00594       std::cout << "Number of solutions: " << it->first << std::endl;
00595       for (unsigned int i = 0; i < it->second.size(); ++i)
00596         std::cout << it->second[i] << " ";
00597       std::cout << std::endl;
00598     }
00599 
00600     delete root;
00601     return results.size() == 1;
00602   }
00603 
00604   BoolTest::BoolTest(const std::string& s, int a)
00605     : Base("Bool::Branch::"+s), arity(a) {
00606   }
00607 
00608   bool
00609   BoolTest::run(void) {
00610     using std::map;
00611     using std::vector;
00612     using std::string;
00613     using std::ostream;
00614     using namespace Gecode;
00615 
00616     // Results of tests run
00617     map<int, vector<RunInfo> > results;
00618     // Set up root space
00619     BoolTestSpace* root = new BoolTestSpace(arity);
00620     post(*root, root->x);
00621     results.clear();
00622 
00623     for (int vara = 0; vara<n_bool_var_branch; vara++) {
00624       for (int varb = 1; varb<n_bool_var_branch; varb++) {
00625         for (int val = 0; val<n_bool_val_branch; val++) {
00626 
00627           Rnd r(1);
00628 
00629           BoolValBranch bvb;
00630           switch (val) {
00631           case  0: bvb = BOOL_VAL_MIN(); break;
00632           case  1: bvb = BOOL_VAL_MAX(); break;
00633           case  2: bvb = BOOL_VAL_RND(r); break;
00634           case  3: bvb = BOOL_VAL(&bool_val); break;
00635           }
00636 
00637           BoolTestSpace* c = static_cast<BoolTestSpace*>(root->clone());
00638 
00639           if (vara == 0) {
00640             for (int i=0; i<c->x.size(); i++)
00641               branch(*c, c->x[i], bvb);
00642           } else {
00643 
00644 
00645             Rnd ra(1);
00646             BoolVarBranch bvba;
00647             BoolAction baa(*c, c->x, 0.9);
00648             BoolCHB bca(*c, c->x);
00649             switch (vara) {
00650             case  0: bvba = BOOL_VAR_NONE(); break;
00651             case  1: bvba = BOOL_VAR_NONE(); break;
00652             case  2: bvba = BOOL_VAR_RND(ra); break;
00653             case  3: bvba = BOOL_VAR_MERIT_MIN(&bool_merit); break;
00654             case  4: bvba = BOOL_VAR_MERIT_MAX(&bool_merit); break;
00655             case  5: bvba = BOOL_VAR_DEGREE_MIN(); break;
00656             case  6: bvba = BOOL_VAR_DEGREE_MAX(); break;
00657             case  7: bvba = BOOL_VAR_AFC_MIN(0.5); break;
00658             case  8: bvba = BOOL_VAR_AFC_MAX(0.5); break;
00659             case  9: bvba = BOOL_VAR_ACTION_MIN(baa); break;
00660             case 10: bvba = BOOL_VAR_ACTION_MAX(baa); break;
00661             case 11: bvba = BOOL_VAR_CHB_MIN(bca); break;
00662             case 12: bvba = BOOL_VAR_CHB_MAX(bca); break;
00663             }
00664 
00665             Rnd rb(2);
00666             BoolVarBranch bvbb;
00667             BoolAction bab(*c, c->x, 0.9, &bool_merit);
00668             BoolCHB bcb(*c, c->x, &bool_merit);
00669             switch (varb) {
00670             case  0: bvbb = BOOL_VAR_NONE(); break;
00671             case  1: bvbb = BOOL_VAR_NONE(); break;
00672             case  2: bvbb = BOOL_VAR_RND(rb); break;
00673             case  3: bvbb = BOOL_VAR_MERIT_MIN(&bool_merit,&tbl); break;
00674             case  4: bvbb = BOOL_VAR_MERIT_MAX(&bool_merit,&tbl); break;
00675             case  5: bvbb = BOOL_VAR_DEGREE_MIN(&tbl); break;
00676             case  6: bvbb = BOOL_VAR_DEGREE_MAX(&tbl); break;
00677             case  7: bvbb = BOOL_VAR_AFC_MIN(0.5,&tbl); break;
00678             case  8: bvbb = BOOL_VAR_AFC_MAX(0.5,&tbl); break;
00679             case  9: bvbb = BOOL_VAR_ACTION_MIN(bab,&tbl); break;
00680             case 10: bvbb = BOOL_VAR_ACTION_MAX(bab,&tbl); break;
00681             case 11: bvbb = BOOL_VAR_CHB_MIN(bcb,&tbl); break;
00682             case 12: bvbb = BOOL_VAR_CHB_MAX(bcb,&tbl); break;
00683             }
00684 
00685             switch (Base::rand(9U)) {
00686             case 0U:
00687               branch(*c, c->x, bvba, bvb); break;
00688             case 1U:
00689               branch(*c, c->x, bvbb, bvb); break;
00690             case 2U:
00691               branch(*c, c->x, tiebreak(bvba,bvbb), bvb); break;
00692             case 3U:
00693               branch(*c, c->x, tiebreak(bvbb,bvba), bvb); break;
00694             case 4U:
00695               branch(*c, c->x, tiebreak(bvba,bvba,bvbb), bvb); break;
00696             case 5U:
00697               branch(*c, c->x, tiebreak(bvba,bvbb,bvbb), bvb); break;
00698             case 6U:
00699               branch(*c, c->x, tiebreak(bvbb,bvba,bvba), bvb); break;
00700             case 7U:
00701               branch(*c, c->x, tiebreak(bvba,bvba,bvbb,bvba), bvb); break;
00702             case 8U:
00703               branch(*c, c->x, tiebreak(bvbb,bvba,bvbb,bvba), bvb); break;
00704             }
00705 
00706           }
00707           Gecode::Search::Options o;
00708           results[solutions(c,o)].push_back
00709             (RunInfo(int_var_branch_name[vara],
00710                      int_var_branch_name[varb],
00711                      int_val_branch_name[val],
00712                      o));
00713         }
00714       }
00715     }
00716     if (results.size() > 1)
00717       goto failed;
00718     delete root;
00719     return true;
00720   failed:
00721     std::cout   << "FAILURE" << std::endl;
00722     for (map<int, vector<RunInfo> >::iterator it = results.begin();
00723          it != results.end(); ++it) {
00724       std::cout << "Number of solutions: " << it->first << std::endl;
00725       for (unsigned int i = 0; i < it->second.size(); ++i)
00726         std::cout << it->second[i] << " ";
00727       std::cout << std::endl;
00728     }
00729 
00730     delete root;
00731     return results.size() == 1;
00732   }
00733 
00734 #ifdef GECODE_HAS_SET_VARS
00735   SetTest::SetTest(const std::string& s, int a, const Gecode::IntSet& d)
00736     : Base("Set::Branch::"+s), arity(a), dom(d) {
00737   }
00738 
00739   bool
00740   SetTest::run(void) {
00741     using std::map;
00742     using std::vector;
00743     using std::string;
00744     using std::ostream;
00745     using namespace Gecode;
00746 
00747     // Results of tests run
00748     map<int, vector<RunInfo> > results;
00749     // Set up root space
00750     SetTestSpace* root = new SetTestSpace(arity,dom);
00751     post(*root, root->x);
00752     root->status();
00753     results.clear();
00754 
00755     for (int vara = 0; vara<n_set_var_branch; vara++) {
00756       for (int varb = 1; varb<n_set_var_branch; varb++) {
00757         for (int val = 0; val<n_set_val_branch; val++) {
00758           Rnd r(1);
00759 
00760           SetValBranch svb;
00761           switch (val) {
00762           case 0: svb = SET_VAL_MIN_INC(); break;
00763           case 1: svb = SET_VAL_MIN_EXC(); break;
00764           case 2: svb = SET_VAL_MED_INC(); break;
00765           case 3: svb = SET_VAL_MED_EXC(); break;
00766           case 4: svb = SET_VAL_MAX_INC(); break;
00767           case 5: svb = SET_VAL_MAX_EXC(); break;
00768           case 6: svb = SET_VAL_RND_INC(r); break;
00769           case 7: svb = SET_VAL_RND_EXC(r); break;
00770           case 8: svb = SET_VAL(&set_val); break;
00771           }
00772 
00773           SetTestSpace* c = static_cast<SetTestSpace*>(root->clone());
00774 
00775           if (vara == 0) {
00776             for (int i=0; i<c->x.size(); i++)
00777               branch(*c, c->x[i], svb);
00778           } else {
00779             Rnd ra(1);
00780             SetVarBranch svba;
00781             SetAction saa(*c, c->x, 0.9);
00782             SetCHB sca(*c, c->x);
00783             switch (vara) {
00784             case  0: break;
00785             case  1: svba = SET_VAR_NONE(); break;
00786             case  2: svba = SET_VAR_RND(ra); break;
00787             case  3: svba = SET_VAR_MERIT_MIN(&set_merit); break;
00788             case  4: svba = SET_VAR_MERIT_MAX(&set_merit); break;
00789             case  5: svba = SET_VAR_DEGREE_MIN(); break;
00790             case  6: svba = SET_VAR_DEGREE_MAX(); break;
00791             case  7: svba = SET_VAR_AFC_MIN(0.5); break;
00792             case  8: svba = SET_VAR_AFC_MAX(0.5); break;
00793             case  9: svba = SET_VAR_ACTION_MIN(saa); break;
00794             case 10: svba = SET_VAR_ACTION_MAX(saa); break;
00795             case 11: svba = SET_VAR_CHB_MIN(sca); break;
00796             case 12: svba = SET_VAR_CHB_MAX(sca); break;
00797             case 13: svba = SET_VAR_MIN_MIN(); break;
00798             case 14: svba = SET_VAR_MIN_MAX(); break;
00799             case 15: svba = SET_VAR_MAX_MIN(); break;
00800             case 16: svba = SET_VAR_MAX_MAX(); break;
00801             case 17: svba = SET_VAR_SIZE_MIN(); break;
00802             case 18: svba = SET_VAR_SIZE_MAX(); break;
00803             case 19: svba = SET_VAR_DEGREE_SIZE_MIN(); break;
00804             case 20: svba = SET_VAR_DEGREE_SIZE_MAX(); break;
00805             case 21: svba = SET_VAR_AFC_SIZE_MIN(); break;
00806             case 22: svba = SET_VAR_AFC_SIZE_MAX(); break;
00807             case 23: svba = SET_VAR_ACTION_SIZE_MIN(saa); break;
00808             case 24: svba = SET_VAR_ACTION_SIZE_MAX(saa); break;
00809             case 25: svba = SET_VAR_CHB_SIZE_MIN(sca); break;
00810             case 26: svba = SET_VAR_CHB_SIZE_MAX(sca); break;
00811             }
00812 
00813             Rnd rb(2);
00814             SetVarBranch svbb;
00815             SetAction sab(*c, c->x, 0.9, &set_merit);
00816             SetCHB scb(*c, c->x, &set_merit);
00817             switch (varb) {
00818             case  0: break;
00819             case  1: svbb = SET_VAR_NONE(); break;
00820             case  2: svbb = SET_VAR_RND(rb); break;
00821             case  3: svbb = SET_VAR_MERIT_MIN(&set_merit,&tbl); break;
00822             case  4: svbb = SET_VAR_MERIT_MAX(&set_merit,&tbl); break;
00823             case  5: svbb = SET_VAR_DEGREE_MIN(&tbl); break;
00824             case  6: svbb = SET_VAR_DEGREE_MAX(&tbl); break;
00825             case  7: svbb = SET_VAR_AFC_MIN(0.5,&tbl); break;
00826             case  8: svbb = SET_VAR_AFC_MAX(0.5,&tbl); break;
00827             case  9: svbb = SET_VAR_ACTION_MIN(sab,&tbl); break;
00828             case 10: svbb = SET_VAR_ACTION_MAX(sab,&tbl); break;
00829             case 11: svbb = SET_VAR_CHB_MIN(scb,&tbl); break;
00830             case 12: svbb = SET_VAR_CHB_MAX(scb,&tbl); break;
00831             case 13: svbb = SET_VAR_MIN_MIN(&tbl); break;
00832             case 14: svbb = SET_VAR_MIN_MAX(&tbl); break;
00833             case 15: svbb = SET_VAR_MAX_MIN(&tbl); break;
00834             case 16: svbb = SET_VAR_MAX_MAX(&tbl); break;
00835             case 17: svbb = SET_VAR_SIZE_MIN(&tbl); break;
00836             case 18: svbb = SET_VAR_SIZE_MAX(&tbl); break;
00837             case 19: svbb = SET_VAR_DEGREE_SIZE_MIN(&tbl); break;
00838             case 20: svbb = SET_VAR_DEGREE_SIZE_MAX(&tbl); break;
00839             case 21: svbb = SET_VAR_AFC_SIZE_MIN(1.0,&tbl); break;
00840             case 22: svbb = SET_VAR_AFC_SIZE_MAX(1.0,&tbl); break;
00841             case 23: svbb = SET_VAR_ACTION_SIZE_MIN(sab,&tbl); break;
00842             case 24: svbb = SET_VAR_ACTION_SIZE_MAX(sab,&tbl); break;
00843             case 25: svbb = SET_VAR_CHB_SIZE_MIN(scb,&tbl); break;
00844             case 26: svbb = SET_VAR_CHB_SIZE_MAX(scb,&tbl); break;
00845             }
00846 
00847             switch (Base::rand(9U)) {
00848             case 0U:
00849               branch(*c, c->x, svba, svb); break;
00850             case 1U:
00851               branch(*c, c->x, svbb, svb); break;
00852             case 2U:
00853               branch(*c, c->x, tiebreak(svba,svbb), svb); break;
00854             case 3U:
00855               branch(*c, c->x, tiebreak(svbb,svba), svb); break;
00856             case 4U:
00857               branch(*c, c->x, tiebreak(svba,svba,svbb), svb); break;
00858             case 5U:
00859               branch(*c, c->x, tiebreak(svba,svbb,svbb), svb); break;
00860             case 6U:
00861               branch(*c, c->x, tiebreak(svbb,svba,svba), svb); break;
00862             case 7U:
00863               branch(*c, c->x, tiebreak(svba,svba,svbb,svba), svb); break;
00864             case 8U:
00865               branch(*c, c->x, tiebreak(svbb,svba,svbb,svba), svb); break;
00866             }
00867 
00868           }
00869           Gecode::Search::Options o;
00870           results[solutions(c,o)].push_back
00871             (RunInfo(set_var_branch_name[vara],
00872                      set_var_branch_name[varb],
00873                      set_val_branch_name[val],
00874                      o));
00875         }
00876       }
00877     }
00878     if (results.size() > 1)
00879       goto failed;
00880     delete root;
00881     return true;
00882   failed:
00883     std::cout   << "FAILURE" << std::endl;
00884     for (map<int, vector<RunInfo> >::iterator it = results.begin();
00885          it != results.end(); ++it) {
00886       std::cout << "Number of solutions: " << it->first << std::endl;
00887       for (unsigned int i = 0; i < it->second.size(); ++i)
00888         std::cout << it->second[i] << " ";
00889       std::cout << std::endl;
00890     }
00891 
00892     delete root;
00893     return results.size() == 1;
00894   }
00895 #endif
00896 
00897 #ifdef GECODE_HAS_FLOAT_VARS
00898   FloatTest::FloatTest(const std::string& s, int a, const Gecode::FloatVal& d, int nbs)
00899     : Base("Float::Branch::"+s), arity(a), dom(d), nbSols(nbs) {
00900   }
00901 
00902   bool
00903   FloatTest::run(void) {
00904     using std::map;
00905     using std::vector;
00906     using std::string;
00907     using std::ostream;
00908     using namespace Gecode;
00909 
00910     // Results of tests run
00911     map<int, vector<RunInfo> > results;
00912     // Set up root space
00913     FloatTestSpace* root = new FloatTestSpace(arity,dom);
00914     post(*root, root->x);
00915     root->status();
00916     results.clear();
00917 
00918     for (int vara = 0; vara<n_float_var_branch; vara++) {
00919       for (int varb = 1; varb<n_float_var_branch; varb++) {
00920         for (int val = 0; val<n_float_val_branch; val++) {
00921           Rnd r(1);
00922 
00923           FloatValBranch fvb;
00924           switch (val) {
00925           case 0: fvb = FLOAT_VAL_SPLIT_MIN(); break;
00926           case 1: fvb = FLOAT_VAL_SPLIT_MAX(); break;
00927           case 2: fvb = FLOAT_VAL_SPLIT_RND(r); break;
00928           case 3: fvb = FLOAT_VAL(&float_val); break;
00929           }
00930 
00931           FloatTestSpace* c = static_cast<FloatTestSpace*>(root->clone());
00932           if (vara == 0) {
00933             for (int i=0; i<c->x.size(); i++)
00934               branch(*c, c->x[i], fvb);
00935           } else {
00936             Rnd ra(1);
00937             FloatVarBranch fvba;
00938             FloatAction faa(*c, c->x, 0.9);
00939             FloatCHB fca(*c, c->x);
00940             switch (vara) {
00941             case  0: break;
00942             case  1: fvba = FLOAT_VAR_NONE(); break;
00943             case  2: fvba = FLOAT_VAR_RND(ra); break;
00944             case  3: fvba = FLOAT_VAR_MERIT_MIN(&float_merit); break;
00945             case  4: fvba = FLOAT_VAR_MERIT_MAX(&float_merit); break;
00946             case  5: fvba = FLOAT_VAR_DEGREE_MIN(); break;
00947             case  6: fvba = FLOAT_VAR_DEGREE_MAX(); break;
00948             case  7: fvba = FLOAT_VAR_AFC_MIN(0.5); break;
00949             case  8: fvba = FLOAT_VAR_AFC_MAX(0.5); break;
00950             case  9: fvba = FLOAT_VAR_ACTION_MIN(faa); break;
00951             case 10: fvba = FLOAT_VAR_ACTION_MAX(faa); break;
00952             case 11: fvba = FLOAT_VAR_CHB_MIN(fca); break;
00953             case 12: fvba = FLOAT_VAR_CHB_MAX(fca); break;
00954             case 13: fvba = FLOAT_VAR_MIN_MIN(); break;
00955             case 14: fvba = FLOAT_VAR_MIN_MAX(); break;
00956             case 15: fvba = FLOAT_VAR_MAX_MIN(); break;
00957             case 16: fvba = FLOAT_VAR_MAX_MAX(); break;
00958             case 17: fvba = FLOAT_VAR_SIZE_MIN(); break;
00959             case 18: fvba = FLOAT_VAR_SIZE_MAX(); break;
00960             case 19: fvba = FLOAT_VAR_DEGREE_SIZE_MIN(); break;
00961             case 20: fvba = FLOAT_VAR_DEGREE_SIZE_MAX(); break;
00962             case 21: fvba = FLOAT_VAR_AFC_SIZE_MIN(); break;
00963             case 22: fvba = FLOAT_VAR_AFC_SIZE_MAX(); break;
00964             case 23: fvba = FLOAT_VAR_ACTION_SIZE_MIN(faa); break;
00965             case 24: fvba = FLOAT_VAR_ACTION_SIZE_MAX(faa); break;
00966             case 25: fvba = FLOAT_VAR_CHB_SIZE_MIN(fca); break;
00967             case 26: fvba = FLOAT_VAR_CHB_SIZE_MAX(fca); break;
00968             }
00969 
00970             Rnd rb(2);
00971             FloatVarBranch fvbb;
00972             FloatAction fab(*c, c->x, 0.9, &float_merit);
00973             FloatCHB fcb(*c, c->x, &float_merit);
00974             switch (varb) {
00975             case  0: break;
00976             case  1: fvbb = FLOAT_VAR_NONE(); break;
00977             case  2: fvbb = FLOAT_VAR_RND(rb); break;
00978             case  3: fvbb = FLOAT_VAR_MERIT_MIN(&float_merit,&tbl); break;
00979             case  4: fvbb = FLOAT_VAR_MERIT_MAX(&float_merit,&tbl); break;
00980             case  5: fvbb = FLOAT_VAR_DEGREE_MIN(&tbl); break;
00981             case  6: fvbb = FLOAT_VAR_DEGREE_MAX(&tbl); break;
00982             case  7: fvbb = FLOAT_VAR_AFC_MIN(0.5,&tbl); break;
00983             case  8: fvbb = FLOAT_VAR_AFC_MAX(0.5,&tbl); break;
00984             case  9: fvbb = FLOAT_VAR_ACTION_MIN(fab,&tbl); break;
00985             case 10: fvbb = FLOAT_VAR_ACTION_MAX(fab,&tbl); break;
00986             case 11: fvbb = FLOAT_VAR_CHB_MIN(fcb,&tbl); break;
00987             case 12: fvbb = FLOAT_VAR_CHB_MAX(fcb,&tbl); break;
00988             case 13: fvbb = FLOAT_VAR_MIN_MIN(&tbl); break;
00989             case 14: fvbb = FLOAT_VAR_MIN_MAX(&tbl); break;
00990             case 15: fvbb = FLOAT_VAR_MAX_MIN(&tbl); break;
00991             case 16: fvbb = FLOAT_VAR_MAX_MAX(&tbl); break;
00992             case 17: fvbb = FLOAT_VAR_SIZE_MIN(&tbl); break;
00993             case 18: fvbb = FLOAT_VAR_SIZE_MAX(&tbl); break;
00994             case 19: fvbb = FLOAT_VAR_DEGREE_SIZE_MIN(&tbl); break;
00995             case 20: fvbb = FLOAT_VAR_DEGREE_SIZE_MAX(&tbl); break;
00996             case 21: fvbb = FLOAT_VAR_AFC_SIZE_MIN(1.0,&tbl); break;
00997             case 22: fvbb = FLOAT_VAR_AFC_SIZE_MAX(1.0,&tbl); break;
00998             case 23: fvbb = FLOAT_VAR_ACTION_SIZE_MIN(fab,&tbl); break;
00999             case 24: fvbb = FLOAT_VAR_ACTION_SIZE_MAX(fab,&tbl); break;
01000             case 25: fvbb = FLOAT_VAR_CHB_SIZE_MIN(fcb,&tbl); break;
01001             case 26: fvbb = FLOAT_VAR_CHB_SIZE_MAX(fcb,&tbl); break;
01002             }
01003 
01004             switch (Base::rand(9U)) {
01005             case 0U:
01006               branch(*c, c->x, fvba, fvb); break;
01007             case 1U:
01008               branch(*c, c->x, fvbb, fvb); break;
01009             case 2U:
01010               branch(*c, c->x, tiebreak(fvba,fvbb), fvb); break;
01011             case 3U:
01012               branch(*c, c->x, tiebreak(fvbb,fvba), fvb); break;
01013             case 4U:
01014               branch(*c, c->x, tiebreak(fvba,fvba,fvbb), fvb); break;
01015             case 5U:
01016               branch(*c, c->x, tiebreak(fvba,fvbb,fvbb), fvb); break;
01017             case 6U:
01018               branch(*c, c->x, tiebreak(fvbb,fvba,fvba), fvb); break;
01019             case 7U:
01020               branch(*c, c->x, tiebreak(fvba,fvba,fvbb,fvba), fvb); break;
01021             case 8U:
01022               branch(*c, c->x, tiebreak(fvbb,fvba,fvbb,fvba), fvb); break;
01023             }
01024 
01025           }
01026           Gecode::Search::Options o;
01027           results[solutions(c,o,nbSols)].push_back
01028             (RunInfo(float_var_branch_name[vara],
01029                      float_var_branch_name[varb],
01030                      float_val_branch_name[val],
01031                      o));
01032         }
01033       }
01034     }
01035     if (results.size() > 1)
01036       goto failed;
01037     delete root;
01038     return true;
01039   failed:
01040     std::cout   << "FAILURE" << std::endl;
01041     for (map<int, vector<RunInfo> >::iterator it = results.begin();
01042          it != results.end(); ++it) {
01043       std::cout << "Number of solutions: " << it->first << std::endl;
01044       for (unsigned int i = 0; i < it->second.size(); ++i)
01045         std::cout << it->second[i] << " ";
01046       std::cout << std::endl;
01047     }
01048 
01049     delete root;
01050     return results.size() == 1;
01051   }
01052 #endif
01053 
01054 }}
01055 
01056 // STATISTICS: test-branch