bab.icc

00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Contributing authors:
00006  *     Guido Tack <tack@gecode.org>
00007  *
00008  *  Copyright:
00009  *     Christian Schulte, 2004
00010  *     Guido Tack, 2004
00011  *
00012  *  Last modified:
00013  *     $Date: 2006-08-04 16:03:17 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
00014  *     $Revision: 3511 $
00015  *
00016  *  This file is part of Gecode, the generic constraint
00017  *  development environment:
00018  *     http://www.gecode.org
00019  *
00020  *  See the file "LICENSE" for information on usage and
00021  *  redistribution of this file, and for a
00022  *     DISCLAIMER OF ALL WARRANTIES.
00023  *
00024  */
00025 
00026 namespace Gecode {
00027 
00028   /*
00029    * BAB search engine
00030    *
00031    */
00032 
00033   namespace Search {
00034 
00035     forceinline
00036     BabEngine::BabEngine(unsigned int c_d0, unsigned int a_d,
00037                          Stop* st, size_t sz)
00038       : EngineCtrl(st,sz), rcs(a_d), cur(NULL),
00039         mark(0), es(ES_SOLUTION), best(NULL),
00040         c_d(c_d0), d(0) {}
00041 
00042 
00043     forceinline void
00044     BabEngine::init(Space* s) {
00045       cur = s;
00046     }
00047 
00048     forceinline size_t
00049     BabEngine::stacksize(void) const {
00050       return rcs.stacksize();
00051     }
00052 
00053     forceinline
00054     BabEngine::~BabEngine(void) {
00055       rcs.reset();
00056       delete best;
00057       delete cur;
00058     }
00059   }
00060 
00061   /*
00062    * Control for bab search engine
00063    *
00064    */
00065 
00066   template <class T>
00067   forceinline
00068   BAB<T>::BAB(T* s, unsigned int c_d, unsigned int a_d, Search::Stop* st)
00069     : Search::BAB(s,c_d,a_d,st,sizeof(T)) {}
00070 
00071   template <class T>
00072   forceinline T*
00073   BAB<T>::next(void) {
00074     Space *s1, *s2;
00075     while (e.explore(s1,s2) == Search::BabEngine::ES_CONSTRAIN)
00076       static_cast<T*>(s1)->constrain(static_cast<T*>(s2));
00077     return static_cast<T*>(s1);
00078   }
00079 
00080 
00081 
00082 
00083   /*
00084    * BAB convenience
00085    *
00086    */
00087 
00088   template <class T>
00089   T*
00090   bab(T* s, unsigned int c_d, unsigned int a_d, Search::Stop* st) {
00091     BAB<T> b(s,c_d,a_d,st);
00092     T* l = NULL;
00093     while (T* n = b.next()) {
00094       delete l; l = n;
00095     }
00096     return l;
00097   }
00098 
00099 }
00100 
00101 // STATISTICS: search-any